高效搜索一长串列表

Question

我有一长串六面体点坐标，例如：

[[0,    57,  2948,    56,   449, 14953, 15002,  5446],
[  449, 14953, 15002,  5446,   450, 14954, 15003,  5495],
[  450, 14954, 15003,  5495,   451, 14955, 15004,  5544],
[  451, 14955, 15004,  5544,   452, 14956, 15005,  5593],
[  452, 14956, 15005,  5593,   453, 14957, 15006,  5642],
....]

每一行定义一个六面体单元格，通过迭代每个单元格，我提取单元格的定义面（6 个面），并将每个面添加到列表 processed_faces

这一切都很好，但是因为一些单元格共享同一张脸，我需要一种方法来检查当前的脸是否已经被处理过（之后还需要进行连通性计算，所以没有办法这个）。

 for cell_id, cell in enumerate(cells):
        faces = get_faces(cell)
        for face in faces:
            # have we met `face` before?
            if not self.face_exists(face):
                self.add_face(face)

            # link the face to the cell who shares it
            self.link_face_to_cell(face, cell_id)

我的代码的瓶颈是face_exists()，为此我尝试了两种不同的方法：

对每个处理过的人脸进行排序，将其转换为元组（可哈希），将元组添加到元组列表中，然后通过 tuple(sorted(face)) in faces 简单检查人脸是否存在。但这太慢了。

实现一个 trie 数据结构，效果很好（比方法 1 快 100 倍左右），但我对性能不满意

class TrieNode:
    __slots__ = ['index', 'is_end', 'children']
    def __init__(self, index: int):
        self.index = index
        self.is_end = False
        self.children = {}


class Trie:
    __slots__ = ['root']
    def __init__(self):
        self.root = TrieNode(-1)

    def insert(self, face: List[int]):
        node = self.root

        for point in face:
            if point in node.children:
                node = node.children[point]
            else:
                new_node = TrieNode(point)
                node.children[point] = new_node
                node = new_node

        node.is_end = True


    def search(self, face: List[int]) -> bool:
        node =self.root

        for point in face:
            if point in node.children:
                node = node.children[point]
                continue
            else:
                return False

        if node.is_end:
            return True

        return False

抱歉问了这么长的问题，总而言之，我正在寻找两件事：

网格存储的另一种数据结构，满足我的快速搜索需求。或者：
如果 trie 适合我的应用程序，是否有 python 库（希望有 C 后端）允许存储数字列表，因为我遇到的库主要是为字符串设计的。

Answer 1

可能的 drop-in 解决方案之一是使用 set/frozenset 来存储人脸。集合具有出色的查找性能，并且在这里使用起来很简单。

高效搜索一长串列表

Efficiently search a long list of lists

python

performance

search

data-structures