Geek asks and answers

Unordered map for C ++ naive solution

I have a C ++ assignment where I have to develop a naive solution to Knut's problem with the container of my choice and study the generated performance data. See Problem below:

Three million men with different names were laid in the end, reaching from New York to California. Each participant was delivered a sheet of paper on which he wrote down his name and the name of the person, directly to the west of him on the line. The man at the extreme western end of the line did not understand what to do, so he threw away his newspaper; the remaining 2,999,999 sheets of paper were placed in a huge basket and delivered to the National Archives in Washington, DC. The contents of the basket were completely shuffled and transferred to magnetic tapes.

At this point, an informant scientist noticed that the tapes had enough information about restoring the list of people in their original order. And a computer scientist discovered a way to make a reconstruction with less than 1000 passes on data tapes, using only sequential access to the tapes and a small amount of random access memory. How is this possible?

[In other words, given the pairs (xi, xi + 1) for 1 ≤ i <N, in random order, where xi are different, how can we get the sequence x1 x2 .... xN, restricting all operations to sequential methods suitable for use on magnetic tapes. This is the problem of sorting in order, when there is no easy way to determine which of the two given keys precedes the other,

unordered_map, . , , - , :

(Name, Name) , ( ), ( ) .

 - identify an individual xc

 - append xc to empty list

 - while xc has westerly neighbour

 - xc < westerly neighbour of xc

 - append xc to list

 - xc < head of list

 - while xc has easterly neighbour

 - xc < easterly neighbour of xc

 - prepend xc to list

- xc , - ?

- , , :

Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg

, , , , ?

, , !

+5
2

, , . , - . , , (, , ), . , . , .

, xc . xc . ,

- while xc has westerly neighbour

" , , ".

, , , , .

0

, . , IMHO

:

identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
    if( xc < westerly neighbour of xc )
    {
        append xc to list
    }
    // Do not understand this:
    // - xc < head of list
}
while( while xc has easterly neighbour )
{
    if( xc < easterly neighbour of xc )
    {
        prepend xc to list
    }
}

( - ...)

identify an individual xc
append xc to empty list

while( xc has westerly neighbour )
{
    xc := westerly neighbour of xc
    append xc to list
    xc := head of list

    while( xc has easterly neighbour )
    {
        xc := easterly neighbour of xc
        prepend xc to list
    }
}

, : , , , . , .

Try

- : , . : 10 000 750 000 . ?

#include <vector>
#include <algorithm>
#include <iostream>
#include <list>

size_t constexpr max_men { 3000000 };

typedef std::tuple< int, int > neighbors_t;
typedef std::vector< neighbors_t > pool_t;

int main() {

  // Need a vector here for random_shuffle - but using it further down
  // just with sequencial methods.
  pool_t pool_list;
  for( size_t i { 0 }; i < max_men - 1; ++i ) {
    pool_list.push_back( std::make_tuple( i, i + 1) );
  }
  std::random_shuffle( pool_list.begin(), pool_list.end() );


  // Use the algorithm to get it sorted again

  // identify an individual xc:
  // Pick first from first tuple
  // append xc to empty list
  std::list<int> sorted_list;
  sorted_list.push_back( std::get<0>( pool_list.front() ) );

  // Count the number of tape scans
  size_t tape_scans { 0 };

  do {
    // Scan through the pool_list
    for( neighbors_t n : pool_list ) {

#if 0
      std::cout << "n [" << std::get<0>( n ) 
        << "] sorted_list [";
      for( int i : sorted_list ) {
        std::cout << i << " ";
      }
      std::cout << "]" << std::endl;
#endif

      // while( xc has westerly neighbour )
      // Found westerly neighbour
      if( std::get< 1 >( n ) == sorted_list.front() ) {
        // append xc to list
        sorted_list.push_front( std::get< 0 >( n ) );
      }
      if( std::get< 0 >( n ) == sorted_list.back() ) {
        // append xc to list
        sorted_list.push_back( std::get< 1 >( n ) );
      }
    } 
    ++tape_scans;
    std::cout << "Tape Scans needed [" << tape_scans 
          << "] sorted list size [" << sorted_list.size() << "]"
          << std::endl;
  } while( sorted_list.size() < max_men );

  std::cout << "Tape Scans needed [" << tape_scans << "]" << std::endl;

  return 0;
}
0

More articles:


All Articles