查找列表中的列表的高效方法？

Question

我正在持续创建一个基于500列的大小为10的随机生成列表New_X。

每次我创建一个新列表时，它必须是独一无二的，并且我的函数NewList只有在New_X还没有被创建并附加到List_Of_Xs中时才返回。

def NewList(Old_List):

end = True
while end == True:

    """ Here is code that generates my new sorted list, it is a combination of elements 
        from Old_List and the other remaining columns,
        but the details aren't necessary for this question. """ 

    end = (List_Of_Xs == np.array([New_X])).all(axis=1).any()

List_Of_Xs.append(New_X)
return New_X

我的问题是，这一行代码end = (List_Of_Xs == np.array([New_X])).all(axis=1).any()是否是查找List_Of_Xs的有效方式？

我的List_Of_Xs可能会增长到超过100,000个列表的长度，所以我不确定这是否有效。

任何帮助都将不胜感激！

- Garrett Miller

---

那么，List_Of_Xs是一个包含10个元素的列表吗？这些元素是整数吗？这些整数有上下限吗？ - Divakar

我会把New_X 设为元组，并检查它是否在集合Set_of_Xs中。尤其是对于仅由10个元素组成的小列表，这样做比进行数组比较更快。 - hpaulj

List_of_Xs==np.array([New_X]) 不仅将 New_X 转换为数组，而且每次都会对 List_of_Xs 进行转换。从列表的列表中创建数组不是一个时间上不重要的任务。 - hpaulj

Answer 1

所以让我搞清楚，因为代码似乎不完整： 1. 你有一个旧列表，每次迭代都在不断增长 2. 你计算一个列表 3. 你将其与旧列表中的每个列表进行比较，看是否应该中断循环？

一种选择是将列表存储在集合中，而不是列表的列表中。将元素与列表的所有元素进行比较将是每次迭代的O(n)操作。使用集合应该是O(1)平均值...尽管你可能会在每次迭代直到最后都得到O(n)。

其他想法是计算每个元素的md5并比较它们，这样你就不必比较完整的列表。

- Michael Stratton

---

旧列表在每次迭代中不会不断增长。每个旧列表都存储在一个X列表中，每个新列表都与X列表进行比较，如果新列表尚未在X列表中，则退出循环。 - Garrett Miller

Answer 2

正如我在评论中观察到的那样，数组比较可能会非常慢，尤其是在列表变得很大时。它必须每次创建数组，这需要时间。

以下是一个集合实现：

创建一个包含10个元素的列表的函数：

def foo(N=10):
    return np.random.randint(0,10,N).tolist()

生成列表并打印唯一的函数

def foo1(m=10):
    Set_of_Xs = set()
    while len(Set_of_Xs)<m:
        NewX = foo(10)
        tx = tuple(NewX)
        if not tx in Set_of_Xs:
            print(NewX)
            Set_of_Xs.add(tx)
    return Set_of_Xs

示例运行。按照原样写的话，无法显示是否有重复项。

In [214]: foo1(5)
[9, 4, 3, 0, 9, 4, 9, 5, 6, 3]
[1, 8, 0, 3, 0, 0, 4, 0, 0, 5]
[6, 7, 2, 0, 6, 9, 0, 7, 0, 8]
[9, 5, 6, 3, 3, 5, 6, 9, 6, 9]
[9, 2, 6, 0, 2, 7, 2, 0, 0, 4]
Out[214]: 
{(1, 8, 0, 3, 0, 0, 4, 0, 0, 5),
 (6, 7, 2, 0, 6, 9, 0, 7, 0, 8),
 (9, 2, 6, 0, 2, 7, 2, 0, 0, 4),
 (9, 4, 3, 0, 9, 4, 9, 5, 6, 3),
 (9, 5, 6, 3, 3, 5, 6, 9, 6, 9)}

- hpaulj

---

谢谢，这样做会更快，因为我的 Set_of_Xs 变得相当大。你认为如果我的函数 NewX 以元组形式创建它们会更容易吗？ - Garrett Miller

将列表转换为元组（或反向转换）并不是什么大问题。只是因为“set”需要一个元组（因为它是不可变的）。 - hpaulj