C++ - 用于大量可搜索数据的高效容器？

Question

我正在为一个College项目实现一个基于文本的Scrabble版本.

我的字典很大,重约400,000字(std::string).

如果我选择vector<string>(O(n)),那么在效率方面搜索有效的单词会很麻烦.有什么好的选择吗？请记住,我已入读大一新生.没什么太复杂了!

谢谢你的时间!

弗朗西斯科

Answer 1

如果您想要使用标准库中的某些内容,可以使用std::set该单词作为键.这会给你对数搜索时间.

由于您的字典可能是静态的(即创建一次而不是修改),您也可以使用a std::vector,对其进行排序std::sort,然后std::binary_search在排序后的矢量上使用以查找单词.这也会给出对数搜索时间,并且可能比a更节省空间set.

如果你想实现自己的数据结构,trie将是一个不错的选择.

Answer 2

std :: set对此很自然,因为它在使用向量时几乎需要0才能工作.即便如此,我会教你一些你通常不会学习的东西,直到你成为一名专业人士.不要过早优化.我在一台计算机上打赌,40K字符串向量中的线性字典查找需要0.001秒.

在一个集合中,它是O(log n)并且可能需要.00001秒.

任何不在STL中的东西都是浪费时间.不要花费10美元的工作来解决10美分的问题.

Answer 3

一个线索或基数树就会给你搜索时间和插入时间是在你所搜索的字符串的长度是线性的.

(请注意,您搜索的字符串长度中的线性是您可以使用任何搜索算法执行的最佳线性,因为比较或散列字符串在字符串的长度上是线性的 - 因此,运行时间的组成部分是线性的字符串的长度通常不在二进制搜索,二叉树或线性搜索的运行时间之外.)

如果您的库中没有这些解决方案,那么这些解决方案可能有些过分.

Answer 4

我做了一些分析并获得了以下结果(MSVS 2008,/ O2,发布版本,单独启动.exe).

编辑 - 现在我意识到我实际上已经完成了我的第一次测试,因为我没有拆分建筑和搜索测试.虽然它没有改变"赢家",但我做了一些新的测试.所以,这是我们拆分时的结果.

首先,如果几乎没有糟糕的搜索请求(400万次搜索尝试).

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (234 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (704 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (593 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (578 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (266 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (4484 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (5469 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (5485 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (1078 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1250 ms)
[----------] 11 tests from Containers (20516 ms total)

此分析表明您应该使用"普通"容器变体而不是"multi",您应该选择unordered_set.它非常适合构建时间和搜索操作时间.

以下是另一个案例的结果(猜测,这不是关于你的应用程序,只是为了它),当不良搜索量等于好搜索量(等于200万)时.获胜者保持不变.

另请注意,静态字典vector表现更好(虽然需要更多时间进行初始化)set,但是,如果必须添加元素,它会很糟糕.

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (235 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (718 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (578 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (579 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (265 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (3375 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (3656 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (3766 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (875 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1016 ms)
[----------] 11 tests from Containers (15438 ms total)

测试代码:

TEST(Containers, DictionaryPrepare) {
   EXPECT_FALSE(strings_initialized);
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      strings.push_back(generate_string());
   }
}

TEST(Containers, VectorPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      vec.push_back(strings[i]);
   }
   sort(vec.begin(), vec.end());
}

TEST(Containers, SetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      set.insert(strings[i]);
   }
}

TEST(Containers, MultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      multiset.insert(strings[i]);
   }
}

TEST(Containers, UnorderedSetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_set.insert(strings[i]);
   }
}

TEST(Containers, UnorderedMultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_multiset.insert(strings[i]);
   }
}

TEST(Containers, VectorSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, SetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, MultisetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      multiset.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedSet) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedMultiset) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_multiset.find(NONEXISTENT_ELEMENT);
   }
}