5

私は C++ の課題を抱えており、選択したコンテナーに関する Knuth 問題の単純な解決策を考案し、生成されたパフォーマンス データを調査する必要があります。以下の問題を参照してください。

異なる名前を持つ 300 万人の男性が、ニューヨークからカリフォルニアに至るまで、端から端まで敷設されました。各参加者には一枚の紙が渡され、その紙に自分の名前と列のすぐ西側にいる人の名前を書き留めました。列の最西端にいた男性は、何をすべきかわからなかったので、紙を捨てました。残りの 2,999,999 枚の紙片は巨大なバスケットに入れられ、ワシントン DC の国立公文書館に運ばれました。ここでバスケットの内容は完全にシャッフルされ、磁気テープに移されました。

この時点で、情報科学者は、元の順序で人々のリストを再構築するのに十分な情報がテープにあることに気付きました。そしてコンピューター科学者は、テープのシーケンシャル アクセスと少量のランダム アクセス メモリのみを使用して、データ テープを 1000 回未満のパスで再構成する方法を発見しました。これはどのように可能でしたか？

[言い換えると、1 ≤ i < N のペア (xi, xi+1) がランダムな順序で与えられ、xi が異なる場合、シーケンス x1 x2….xN をどのように取得し、すべての操作をシリアル手法に制限することができますか? 、磁気テープでの使用に適しています。これは、指定された 2 つのキーのどちらが他のキーよりも先行しているかを簡単に判断できない場合に、順序をソートする際の問題です。

調査の結果、リストや法線マップではなく、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 はコンテナの性質上順序を決定できないため、単なるランダムな要素ですか?

私の 2 番目の質問 - 私たちが与えられた名前は次のようなファイルにあります:

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

それで、最初の名前を1つのリストに入れ、次に姓を別のリストに入れる必要があるという素朴な解決策はありますか?

私が完全にオフになっている場合は申し訳ありませんが、私はこれを本当に理解しようとしました!

4

2 に答える 2

0

解決策は1つのリストを使用することだと思います。最初のタプルを選び、その名をリストの先頭に置き、西の隣人を次​​の項目に置きます。次に、その西側の隣人を名として持つタプルを見つけ（もちろん、それは難しい部分です）、そのタプルから西側の隣人を取得して、リストに追加します。最後に追加した人の名前のタプルが見つからなくなるまで繰り返します。その後、あなたはあなたが西海岸に到達したことを知っています。

したがって、最初のxcは本質的にランダムです。その後、xcは決定論的です。言う行

- while xc has westerly neighbour

本質的には、「現在の西側の隣人を自己名として持つタプルを見つける」と言っています。

もちろん、後者の部分では、同じロジックを逆に適用して、東に向かうチェーンを埋めます。

于 2013-01-27T19:54:41.777 に答える
0

初挑戦

コメントとして質問することは不可能なので、私はこれを答えとしてやっています。また、これを明確にすることは、答えの少なくとも半分は私見です

これは次の意味ですか？

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
    }
}

（これは解決策に近づくための試みにすぎません-私はまだアルゴリズムについて考えていませんでした...）

2回目の試行

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
    }
}

これはある程度理にかなっていると思われます。つまり、リストを調べて、西にあるすべての隣人を可能な限り収集し、この後、すべての東側でこれを実行します。したがって、元のリストを実行するたびに、ソートされたリストはますます長くなります。

3回目の試行

私見何かが欠けています：私が利用可能なすべての情報を解釈すると、私は次の解決策に到達します。ただし、これには元のテープをさらにスキャンする必要があります。指定された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;
}
于 2013-01-27T19:57:30.430 に答える