Python：List vs Dict查找表
我有大约1000万的价值，我需要在某种types的查询表中，所以我想知道哪一个更有效的清单或字典 ？
我知道你可以为两者做这样的事情：
if something in dict_of_stuff: pass 和
if something in list_of_stuff: pass
我的想法是字典将更快，更高效。
谢谢你的帮助。
编辑1
关于我正在尝试做什么的更多信息。 欧拉问题92 。 我正在查找表，看是否计算出的值已经全部准备好了。
编辑2
查找效率。
编辑3
没有价值与价值相关…所以一套更好？
速度
列表中的查找是O（n），字典中的查找是O（1），关于数据结构中项目的数量。 如果您不需要关联值，请使用集合。
记忆
字典和集合都使用散列，并且它们使用的内存比仅用于对象存储的内存要多得多。 根据美国代码 AM Kuchling的说法，这个实现试图保持hash 2/3已满，所以你可能会浪费一些内存。
如果您没有即时添加新条目（根据您更新的问题，您可以添加新条目），则可能需要对列表进行sorting并使用二分查找。 这是O（log n），对于没有自然sorting的对象来说，对于string来说很可能会变慢。
字典是一个哈希表，所以它很快find密钥。 所以在字典和列表之间，字典会更快。 但是，如果你没有联系的价值，那么使用一套更好。 这是一个哈希表，没有“表”部分。
编辑：对于你的新问题，是的，一套会更好。 只需创build2个集合，一个序列以1结尾，另一个序列以89结尾。我已经成功地使用集合解决了这个问题。
set()正是你想要的。 O（1）查找，并小于字典。
我做了一些基准testing，事实certificate，字典比列表和更大的数据集设置更快，在Linux上的i7 CPU上运行python 2.7.3：
-
python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'10个循环，最好是每个循环3：64.2毫秒
-
python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'10000000循环，最好是3：每循环0.0759次
-
python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'1000000个循环，最好是每个循环的0.262个usec
正如你所看到的，字典比列表快得多，比集合快大约3倍。 但是，在某些应用程序中，您可能仍然希望select它的优点。 如果数据集非常小（<1000个元素），则performance得相当不错。
如果数据是唯一的set（）将是最有效的，但是双字典（这也需要唯一性，oops 🙂
你想要一个字典。
对于Python中的（未sorting的）列表，“in”操作需要O（n）时间—当你有大量的数据时不好。 字典，另一方面，是一个哈希表，所以你可以期望O（1）查找时间。
正如其他人所指出的，如果您只有键而不是键/值对，您可以select一组（特殊types的字典）。
有关：
- Python wiki ：关于Python容器操作时间复杂度的信息。
- SO ：Python容器的运行时间和内存的复杂性
你实际上并不需要在表中存储1000万个值，所以这两个方法都不是什么大不了的。
提示：想想在第一次平方运算之后你的结果有多大。 最大可能的结果将远远小于1000万…
