1

Suppose I have a doubly-linked list, with a byte associated with each element. Wikipedia has a good visual; pretend the numbers are hexadecimal numbers:

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

Now, the naïve ("immediately obvious") way to build a string from the list, given a pointer to the last node in the string (in this example, the 37 node), is:

using std::string;

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

The goal is the string "\0x12\0x99\0x37". However, this function requires lots of reallocations of the string being built and lots of function call overhead (it can't be tail-call optimized); doubtless there are other inefficiences that I'm not aware of.

Is there a better way? Of course, I'm not just looking to minimize theoretical time complexity; I'm really trying to find a method that will be fastest in practice.

4

6 回答 6

3

从 empty 开始std::string，回到列表的前面，然后遍历节点并push_back进入字符串。这需要线性时间，这对于这个问题是最佳的。

如果您预先知道列表有多长，则可以进行进一步优化。在这种情况下，您可以从适当长度的字符串开始，然后直接在其中插入字符。

于 2013-10-14T15:48:04.953 回答
2

有没有更好的办法？

当然。

  1. 找到列表的开头。在定位列表的开头时，计算节点总数（如果它尚不可用）并计算最终字符串的总字符串大小。
  2. 使用预分配所需大小的字符串std::string::reserve()
  3. 从第一个节点到最后一个节点遍历列表，将数据添加到先前预分配字符串的末尾。你可以使用std::string::append()它。
于 2013-10-14T19:41:53.370 回答
1

考虑到手头的限制（你基本上被困在反向遍历列表），最好也反向构建字符串，然后在添加所有字符后，反转字符串。

你现在做事的方式是二次复杂度——每次插入另一个字符时，将该字符放入一个字符串中，将所有现有字符复制到新字符串中，因此每次插入都是线性的并且 N 次插入大约为 O(N 2 )。[注意：实际上，我误读了代码——它很糟糕，但没那么糟糕] 就像现在一样，我们可以期望每个字符至少被复制两次——一次到堆栈，一次到目标字符串。如果您从内存带宽的角度考虑，效率低下可能最为明显。至少，每次调用都必须读取一个指针，将当前字符写入堆栈并写入一个返回地址，所有这些都是为了将​​一个字节从链表复制到目标字符串。假设一个 64 位的实现，我们在读取和写入指针（和其他开销）与复制我们真正关心的数据方面的比率约为 18:1。

通过反向构建字符串，然后将其反转，您可以在字符串的末尾添加新字符，您可以期望它很快发生。然后你只做一次所有额外的移动，而不是为你添加的每个角色做一次。

如果您使用的是std::vector<char>，则可以明确说明在字符串末尾添加一个字符是摊销常数复杂性。由于std::string我们（我记得）没有得到复杂性保证，但是要让它像复制一个字符的递归调用一样糟糕，需要一个非常糟糕的实现。

另一种可能性是使用 astd::deque<char>而不是 a string。使用双端队列，您可以在前面插入字符，而无需移动所有其他字符以腾出空间。这确实有两个缺点：结果（通常）不是连续的内存块，并且您通常会获得额外的间接级别，因此在构建数据后访问数据会稍微慢一些。

于 2013-10-14T15:52:51.177 回答
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 循环。这将带来更好的性能，因为每个字符串不会有一个函数调用的开销。

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 回答
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 回答