1

各要素に 1 バイトが関連付けられた、双方向にリンクされたリストがあるとします。ウィキペディアには優れたビジュアルがあります。数字が 16 進数であるふりをします。

https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/500px-Doubly-linked-list.svg.png

さて、文字列の最後のノード (この例では37ノード) へのポインタを指定して、リストから文字列を作成する単純な (「すぐにわかる」) 方法は次のとおりです。

using std::string;

string node::makeString()
{
  return this->prev->makeString() + this->data;
}

目標は文字列"\0x12\0x99\0x37"です。ただし、この関数では、作成中の文字列を何度も再割り当てする必要があり、多くの関数呼び出しのオーバーヘッドが必要です (末尾呼び出しを最適化することはできません)。間違いなく、私が気づいていない他の非効率性があります。

より良い方法はありますか？もちろん、理論上の時間の複雑さを最小限に抑えることだけを考えているわけではありません。私は実際に最速になる方法を見つけようとしています。

4

6 に答える 6

1

手元にある制約 (基本的にリストを逆にたどるのに行き詰まっている) を考えると、文字列も逆に構築し、すべての文字が追加されたら、文字列を逆にするのがおそらく最善です。

現在行っている方法では、二次的な複雑さが得られます。別の文字を挿入し、その文字を文字列に入れるたびに、既存のすべての文字を新しい文字列にコピーするため、各挿入は線形であり、N 回の挿入です。はおおよそ O(N 2 ) です。[注: 実際には、コードを読み間違えていました -- 悪いですが、それほど悪くはありません] 現在のところ、すべての文字が少なくとも 2 回コピーされると予想できます。1 回はスタックに、もう 1 回はスタックにコピーされます。宛先文字列。メモリ帯域幅の観点から考えると、おそらく非効率性が最も明白です。最低限、各呼び出しでは、ポインターを読み取り、現在の文字をスタックに書き込み、戻りアドレスを書き込む必要があります。これらはすべて、リンクされたリストから宛先文字列に 1 バイトをコピーするために必要です。64 ビットの実装を想定すると、ポインターの読み取りと書き込み (およびその他のオーバーヘッド) と実際に必要なデータのコピーの比率は 18:1 程度になります。

文字列を逆方向に作成してから逆方向に作成すると、文字列の末尾に新しい文字が追加されます。次に、追加するすべてのキャラクターに対して1回ではなく、1回だけ余分な移動をすべて行います。

を使用している場合std::vector<char>は、文字列の末尾に文字を追加すると、一定の複雑さが償却されると断言できます。(思い出すと) 複雑さの保証は得std::stringられませんが、1 文字をコピーするためだけに再帰呼び出しと同じくらいひどいものにするには、驚くほどひどい実装が必要になるでしょう。

別の可能性は、 のstd::deque<char>代わりにを使用することstringです。deque を使用すると、スペースを空けるために他のすべての文字を移動することなく、先頭に文字を挿入できます。これには 2 つの欠点があります。結果は (通常) メモリの連続したブロックではなく、通常は余分なレベルの間接化が発生するため、構築後のデータへのアクセスはわずかに遅くなります。

于 2013-10-14T15:52:51.177 に答える
0

ボトルネックは文字列の再割り当てです。したがって、最初にノードの数を数え、その後文字列を作成します。例えば

std::string::size_type n = 1;
for ( ; node->prev; node = node->prev ) ++n;
std::string s;
s.reserve( n );
for ( ; node->next; node = node->next ) s.push_back( node->data );
于 2013-10-14T16:18:00.583 に答える
0

個人的には、文字列のリンク リスト、または char 配列を作成し、各ノードを逆方向に埋めます。

struct StringNode
{
  char buffer [20];
  struct StringNode *next;
};

StringNode *node = new StringNode;
node->buffer [19] = '\0';
node->next = 0;
size_t output = 18;
size_t count = 1;

for (ptr = last item ; ptr ; ptr = ptr->prev)
{
  node->buffer [output] = ptr->character;
  ++count;
  if (output)
  {
    --output;
  }
  else
  {
    StringNode *newnode = new StringNode;
    newnode->buffer [19] = '\0';
    newnode->next = node;
    output = 18;
    node = newnode;
  }
}

string output (count); // preallocate enough storage for whole string and initialise to an empty string

while(node)
{
  output += &node->buffer [output+1];
  // or: cout << &node->buffer [output+1];
  StringNode *nextnode = node->next;
  delete node;
  node = nextnode;
  output = -1;
}
于 2013-10-14T15:59:40.370 に答える
0

ソリューションの非効率性は、再帰によるものです。リンク リストの場合は、文字列を設定し、単純な while ループを使用します。これにより、文字列ごとに 1 つの関数呼び出しのオーバーヘッドが発生しないため、パフォーマンスが向上します。

string makeString() {
  Node* p = l.end(); //l is the linked list. end is its tail node
  string s = "";
  while(p != NULL) {
    s = p.value() + s; //append the value to the string
    p = p.prev(); //advance p to the prev node
  }
  return s;
}

もちろん、パフォーマンスをさらに向上させるために、リンクされたデータ構造を使用しないことを検討します。これは、メモリ内の局所性を扱う非効率性につながる可能性があるためです。

于 2013-10-14T15:52:42.190 に答える