c*********3
发帖数: 197 | 1 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
了。
插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
词。
第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
谢谢 |
g*****g
发帖数: 34805 | 2 要我说做个数据库，建个索引就行了。50万不是太多。
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
c*********3
发帖数: 197 | 3 考虑过这种可能。种种情况限制，不太可能用数据库。要不也不问了。数据库就简单多
了。谢谢 |
c*****t
发帖数: 1879 | 4 Both B trees and B+ trees are for databases, not for generic in-memory
access. They are also quite complex, so forget them.
BST should be faster (for in-memory data access) and simpler and there
are a lot of libraries supporting it.
50k isn't a lot of data, so you could even try simple array, or simple
sorted array with binary search.
You could also consider hash and trie, which could be even faster.
In most cases, pre-emptive optimization is a bad idea. You should just
pick a easy to implemen
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
r*********r
发帖数: 3195 | 5 use patricia trie
B+ tree is not the best choice |
s***e
发帖数: 122 | 6 C++的话用STL的map，Java的话用HashMap应该就够用了。
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
f*****Q
发帖数: 1912 | |
r*********r
发帖数: 3195 | 8 using SQLite is same as using a B tree. hehe |
f*****Q
发帖数: 1912 | |
c***c
发帖数: 21374 | 10 binary search tree就可以啦
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
|
|
c*********3
发帖数: 197 | 11 是用C++。最初实现是用STL map. 速度达不到要求。因为原来的代码不是我写的，刚刚
接手。看来我还是先看看原来的代码先。先谢谢了 |
t*******m
发帖数: 36 | 12 B+ tree主要用于database的index实现，主要是支持基于page I/O的树索引，这里不合
适。
你需要的是内存结构，但取决于你的需求。如果是普通查询，i.e., 输入一个词，返回
它的解释，用hash table: key 是词的string, value是解释，也是string. 50万个词
，每个词平均远低于10 byte (不考虑unicode), 共 5MB, 假定每个词的解释 1KB, 则
共 500MB, 全部load进内存没问题。
不要用C++ STL 的map, 那个不是hash table, 是 tree 结构，一般实现是 red-black
tree, 有很多 C++ STL extension, 如 SGI C++ STL 的 hash_map, 是hash table,
Linux GNU C++ 中也有。
如果你需要支持其他查询，如范围查询, 模糊查询，等， 你可以考虑其他结构，一般
是各种 tree
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
g*****e
发帖数: 87 | |
o****u
发帖数: 714 | 14 trie 确实是个好办法，自己写一个也不复杂。这是一种单词查找树，每个节点存一个
字母，从根节点下来到叶子，就是这个字符串。 在 bst 中, log2(500000)=19, 而在
trie中，每个单词的查询时间就是单词的长度，大部分单词少于19个字母。
hash table 更快，但是最好根据需要自己设计hash function, 这样控制得比较好。速度取决于 hash 的 collision.
【在 g*****e 的大作中提到】
: Trie is your best bet!
: http://en.wikipedia.org/wiki/Trie
|
d****h
发帖数: 58 | 15 如果是load in memory, Suffix tree 也是个不错的选择:
1.build time O(n) -> on-line structured
2.space O(n)
3. searching time O(m) -> m is the search query size |
s***e
发帖数: 122 | 16 以前还真不知道stl的map不是用的hash table，多谢提醒啊。
black
【在 t*******m 的大作中提到】
: B+ tree主要用于database的index实现，主要是支持基于page I/O的树索引，这里不合
: 适。
: 你需要的是内存结构，但取决于你的需求。如果是普通查询，i.e., 输入一个词，返回
: 它的解释，用hash table: key 是词的string, value是解释，也是string. 50万个词
: ，每个词平均远低于10 byte (不考虑unicode), 共 5MB, 假定每个词的解释 1KB, 则
: 共 500MB, 全部load进内存没问题。
: 不要用C++ STL 的map, 那个不是hash table, 是 tree 结构，一般实现是 red-black
: tree, 有很多 C++ STL extension, 如 SGI C++ STL 的 hash_map, 是hash table,
: Linux GNU C++ 中也有。
: 如果你需要支持其他查询，如范围查询, 模糊查询，等， 你可以考虑其他结构，一般
|
w***g
发帖数: 5958 | 17 如果程序运行中不需要增加单词，那么应该用perfect hash。
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
N**********d
发帖数: 9292 | 18 suffix tree?
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
x****u
发帖数: 44466 | 19 除了面试以外，你要是上来就想到设计个算法做，那是不专业的表现。
牛人会告诉你，用数据库或者用微型数据库。凡事都自己用个数据结构裸搞是软件品质
下降的万恶之源。
【在 c*********3 的大作中提到】
: 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
: 了。
: 插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
: 词。
: 第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
: 谢谢
|
c*********3
发帖数: 197 | 20 貌似有理。
请教一下什么是专业的表现？是CS专业吗？我都不是学这个。问个问题，那里有这么多
道理。知道就指点一下。
用数据结构和软件品质好像没有什么直接联系吧！ |
c*********3
发帖数: 197 | 21 貌似有理。
请教一下什么是专业的表现？是CS专业吗？我都不是学这个。问个问题，那里有这么多
道理。知道就指点一下。
用数据结构和软件品质好像没有什么直接联系吧！ |
