hat-trie 0.3

hat-trie

Python (2.x和3.x) 的HAT-Trie结构。

此软件包是hat-trie C库的Python包装器。

安装

pip install hat-trie

使用

创建一个新的trie

>>> from hat_trie import Trie
>>> trie = Trie()

变量 trie 是一个类似于字典的对象，支持Unicode键，可以以任何Python对象作为值。对于共享前缀的键，它通常比Python字典使用更少的内存。

还有一个 hat_trie.IntTrie，它只支持正整数作为值。当您不需要任意对象作为值时，它可以更有效。例如，如果您需要存储浮点值，那么将它们存储在数组（无论是numpy还是stdlib的 array.array）中，并使用IntTrie值作为索引，可能比直接在 hat_trie.Trie 中存储Python浮点对象更节省内存。

另一种存储浮点值的方法是使用 hat_trie.FloatTrie()。在这种情况下，精度限制为float32。

当前实现的方法包括

• __getitem__()

• __setitem__()

• __contains__()

• __len__()

• get()

• setdefault()

• keys()

• iterkeys()

其他方法尚未实现 - 欢迎贡献！

性能

性能是在100k个独特的Unicode单词（英语和俄语）作为键，以及‘1’数字作为值的情况下，针对 hat_trie.Trie 与Python的dict进行比较的。

Python 3.3 的基准测试结果（Intel i5 1.8GHz，"1.000M ops/sec" 等于 "1,000,000 次操作/秒"）

dict __getitem__ (hits)      6.874M ops/sec
trie __getitem__ (hits)      3.754M ops/sec
dict __contains__ (hits)     7.035M ops/sec
trie __contains__ (hits)     3.772M ops/sec
dict __contains__ (misses)   5.356M ops/sec
trie __contains__ (misses)   3.364M ops/sec
dict __len__                 785958.286 ops/sec
trie __len__                 574164.704 ops/sec
dict __setitem__ (updates)   6.830M ops/sec
trie __setitem__ (updates)   3.472M ops/sec
dict __setitem__ (inserts)   6.774M ops/sec
trie __setitem__ (inserts)   2.460M ops/sec
dict setdefault (updates)    3.522M ops/sec
trie setdefault (updates)    2.680M ops/sec
dict setdefault (inserts)    4.062M ops/sec
trie setdefault (inserts)    1.866M ops/sec
dict keys()                  189.564 ops/sec
trie keys()                  16.067 ops/sec

HAT-Trie 在所有支持的运算上比 datrie 快约 1.5 倍；它还支持快速插入，而 datrie 不支持。另一方面，datrie 有更多功能（例如，更好的迭代支持和更丰富的 API）；datrie 还更节省内存。

如果您需要一个内存高效的数据结构，并且不需要插入操作，那么 marisa-trie 或 DAWG 应该更适用。

贡献

开发在 github 上进行

• https://github.com/kmike/hat-trie

请随意提交想法、错误、pull request 或常规补丁。

请勿提交生成的 C 文件更改；我将自己重新构建它们。

$ ./update_c.sh
$ tox

$ tox -c bench.ini

许可证

许可协议为 MIT 许可。