如何改进链表搜索。 C++

Question

我在 C++ 中有一个简单的方法，它在链表中搜索字符串。这很好用，但我需要让它更快。可能吗？也许我需要按字母顺序将项目插入列表？但我认为它不再有助于搜索列表。列表中有大约 300 000 个项目（单词）。

int GetItemPosition(const char* stringToFind)
{
    int i = 0;
    MyList* Tmp = FistListItem;
    while (Tmp){
        if (!strcmp(Tmp->Value, stringToFind))
        {
            return i;
        }
        Tmp = Tmp->NextItem;
        i++;
    }
    return -1;
}

方法 returns 如果找到项目则为位置编号，否则 returns -1。任何建议都会有所帮助。

感谢您的回答，我可以更改结构。我只有一个约束。代码必须实现以下接口：

int Count(void);
int AddItem(const char* StringValue, int WordOccurrence);
int GetItemPosition(const char* StringValue);
char* GetString(int Index);
int GetOccurrenceNum(int Index);
void SetInteger(int Index, int WordOccurrence);

那么您认为哪种结构最合适呢？

Answer 1

考虑使用数组或 std::vector 作为存储而不是链表，并使用二进制搜索来查找特定字符串，甚至更好，std::set，如果您不需要数字索引.如果由于某些原因无法使用其他容器，则没有太多可能 - 您可能希望通过将字符串的哈希与其一起存储在节点中来加快比较过程。

Answer 2

搜索链表是线性的，所以你需要从头开始一个一个地迭代，所以它是 O(n)。链表不是最好的，如果你要用它来搜索，你可以利用更合适的数据结构，比如二叉树。

对元素进行排序并没有多大帮助，因为无论如何您仍然需要迭代每个元素。

Wikipedia article 说：

In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "index" a linked list using a more efficient external data structure. For example, one can build a red-black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

因此，在第一种情况下，您可以通过将之前找到的项目移动到更靠近列表开头的位置来略微提高（通过统计假设）您的搜索性能。这假设以前找到的元素将被更频繁地搜索。

第二种方法需要使用其他数据结构。

如果使用链表不是硬性要求，请考虑使用哈希表、排序数组（随机访问）或平衡树。

Answer 3

我建议哈希。由于您已经有了自己的链表），您可以尝试与链表链接以解决冲突。

Answer 4

与其使用线性 linked 列表，不如使用二叉搜索树或 red/black 树。这些树旨在最大程度地减少查找项目的遍历。

您还可以存储 "short cut links"。例如，如果列表是字符串，您可以有一个 links 的数组，其中包含根据第一个字母开始搜索的位置。

例如，shortcut['B'] 将 return 指向第一个 link 的指针以开始搜索以 'B' 开头的字符串。

Answer 5

答案是不，不改变数据结构就无法改进搜索。

就目前而言，对列表进行排序不会让您更快地搜索任何随机项目。

它只会让您通过对第一个项目（最小或最大条目）进行测试来快速确定给定项目是否在列表中，并且此改进不太可能产生重大影响.

那么您能否编辑您的问题并向我们解释您的约束？

你能使用完全不同的数据结构，比如数组或树吗？（正如其他人所建议的）
如果不是，能否修改一下你的链表的链接方式？
否则，我们将不太可能帮助您...

Answer 6

最好的选择是使用更快的数据结构来存储字符串：

std::map - 幕后的红黑树。 search/insert/delete 操作的复杂度为 O(logn)。 Suitable 如果你想用字符串存储额外的值（例如 - positions）。
std::set - 基本上是同一棵树，但没有值。最适合只需要 contains 操作的情况。
std::unordered_map - 哈希 table。 O(1) 访问。
std::unordered_set - 哈希集。也是 O(1) 访问。

注意。 但是在所有这些情况下都有一个陷阱。复杂度仅基于 n（字符串计数）计算。实际上字符串比较不是免费的。因此，O(1) 变为 O(m)，O(logn) 变为 O(mlogn)（其中 m 是字符串的最大长度）。这在字符串相对较短的情况下无关紧要。但如果这不是真的，请考虑使用 Trie。实际上，trie 甚至可以比 hash table 更快——查询字符串的每个字符只被访问一次而不是多次。对于散列 table/set 它至少一次用于哈希计算，至少一次用于实际字符串比较（取决于冲突解决策略 - 不确定它是如何在 C++ 中实现的）。

如何改进链表搜索。 C++

How to improve linked list searching. C++

c++

performance

algorithm

search

linked-list