python-3.x 高效搜索多个列表中的冲突

eqfvzcg8  于 2022-12-24  发布在  Python
关注(0)|答案(1)|浏览(111)

我有一个多个列表的形式的数据:(有一个简单的例子,事实上,行向量的维度要大得多)

  • 列表1:[num1][[1,0,0,1,0], [0,0,1,0,1], [0,1,0,1,0], ...]
  • 列表2:[num2][[0,0,0,1,0], [1,0,0,1,0], [0,0,1,0,0], ...]

...

  • 列表n:[numn][[1,1,0,1,0], [1,0,0,1,1], [0,0,1,0,1], ...]

每个列表都标有自己的编号[num](编号不重复)。
主要问题是:如何有效地从它们和这样的向量中找出所有行向量相同的表的个数?
详情如下:
例如,行向量[1,0,0,1,0]出现在列表1和列表2中,因此我应该返回[1,0,0,1,0] : [num1], [num2]
首先想到的是哈希表。我认为由于数据量大,最好使用哈希表,但我对哈希表的了解相当肤浅,而且在这种情况下,我无法在脑海中构建一个清晰的算法。有人能告诉我应该注意什么,应该考虑哪些模块吗?也许还有其他有效的方法?

ivqmmu1c

ivqmmu1c1#

深入研究哈希表之类的东西超出了常规问题的范围,但可以说Python中的sets有哈希表作为后盾,检查集合成员关系几乎是即时的,而且比搜索列表要高效得多。
如果向量列表中的顺序无关紧要,那么你应该把它们看作无序集合(集合)。集合需要包含不可变的东西,所以你不能把列表放入集合,但是你可以放入元组。所以,如果你把数据重组为元组集合,你就处于良好的状态。
你有许多“案例”的事情,你可能会这样做,下面是一些例子。

data = { 1:  {(1, 0, 0), (1, 1, 0)},
         2:  {(0, 0, 0), (1, 0, 0)},
         3:  {(1, 0, 0), (1, 0, 1), (1, 1, 0)}}

# find common vectors in 2 sets
def common_vecs(a, b):
    return a.intersection(b)

# find all the common vectors in a group of sets
def all_common_vecs(grps):
    return set.intersection(*grps)

# find which sets contain a specific vector
def find(vec, data):
    result = set()
    for idx, grp in data.items():
        if vec in grp:
            result.add(idx)
    return result

print(common_vecs(data[1], data[3]))

print(all_common_vecs(data.values()))

print(find((1,0,1), data))
输出:
{(1, 0, 0), (1, 1, 0)}
{(1, 0, 0)}
{3}

相关问题