用python搜索列表的最快方法

Question

当您执行类似于"test" in a的操作时，其中a是列表，python是对列表执行顺序搜索，还是创建哈希表表示来优化查找？在应用程序中，我需要这个，因为我将在列表上做很多查找，所以最好是做一些像b = set(a)然后"test" in b这样的事情吗？还要注意，我将拥有的值列表不会有重复的数据，而且我实际上并不关心它的顺序；我只需要能够检查值的存在性。

Answer 1

带有列表的"test" in a将执行线性搜索。动态设置哈希表要比线性搜索昂贵得多。"test" in b另一方面，将执行一个amoirtised O（1）散列查找。

在你描述的例子中，似乎没有理由在集合上使用列表。

Answer 2

Also note that the list of values I'll have won't have duplicate data and I don't actually care about the order it's in; I just need to be able to check for the existence of a value.

不要使用列表，而是使用^{}。它完全具有您想要的属性，包括一个快速的in测试。

我见过20倍或更高的速度在一些地方（主要是大量的数字运算），其中一个列表被更改为一套。

Answer 3

我想最好还是按规定执行。我知道集合有O（1）个查找时间。我认为列表需要O（n）查找时间。但即使列表也是O（1）查找，切换到集合也不会有任何损失。

此外，集合不允许重复值。这也会使程序的内存效率稍微提高一些