英文:
How can I implement efficient way to search prefix in set of fixed length arrays of bytes?
问题
我有一个由固定长度的字节数组组成的大型集合，类似于：
type Fixed [64]byte
set := make([]Fixed, 10240)
大多数条目都有不同的5-7字节前缀。
我该如何实现一种高效的方法来根据给定的前缀在set中查找元素？例如：
set.Find([7]byte{ /*...*/ }) == /* 没有匹配 || 单个匹配 || 多个匹配 */
英文:
I have a large set of fixed length arrays of bytes, something like e.g.:
type Fixed [64]byte
set := make([]Fixed, 10240)
Most of this entries have distinct 5-7 byte prefix.
How I can implement efficient way to find elements of set based on given prefix? e.g.:
set.Find([7]byte{ /*...*/ }) == /* no hit || single hit || multiple hit */
答案1
得分: 1
看起来你需要一个字典树。
你可以将你的集合存储为一个字典树，给定一个前缀，你可以一直向下走到一个节点。然后你只需遍历以该节点为根的子树，就可以获取到所有的项。
英文:
Looks like you need a trie.
You can store your set as a trie and given a prefix you go all the way down and get to a node. Then you just traverse the subtree rooted at this node to get all your items.
答案2
得分: 0
如上所述，trie对你来说可能是一个不错的选择。
另外，你也可以使用哈希表，其中键将是前7-8个字节（可以使用长整型），访问时间为O(1)，我认为实现起来更简单。
英文:
As mention above trie can be good for you.
Also you can use hash table, the key will be the first 7-8 bytes (can use long for it), the access time is O(1) and I think is simpler to implement.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论