Python - 将列表转换为字典以降低复杂性
Python - convert list into dictionary in order to reduce complexity
假设我有一个大清单：
word_list = [elt.strip() for elt in open("bible_words.txt", "r").readlines()]
//complexity O(n) --> proporcional to list length "n"
我了解到 hash function 用于构建 dictionaries 可以使 lookup 更快，如下所示：
word_dict = dict((elt, 1) for elt in word_list)
// complexity O(l) ---> constant.
使用 word_list，是否有推荐的最有效的方法来降低我的代码的复杂性？
问题中的代码只做了一件事：将文件中的所有单词填充到列表中。其复杂度为 O(n)。
将相同的单词填充到任何其他类型的容器中仍然至少有 O(n) 的复杂度，因为它必须从文件中读取所有单词并将所有单词放入容器中.
dict 有什么不同？
找出某物是否在 list 中的复杂度为 O(n)，因为算法必须逐项遍历列表并检查它是否是要查找的项目。该项目可以在位置 0 找到，这很快，或者它可能是最后一个项目（或者根本不在列表中），这使得它 O(n).
在dict中，数据组织在"buckets"中。当 key:value 对保存到 dict 时，计算键的 hash 并且该数字用于标识 bucket 中的数据被储存了。之后在查找key的时候，再次计算hash(key)来标识bucket，然后只搜索那个bucket。每个 bucked 通常只有一对 key:value，因此可以在 O(1) 中完成搜索。
有关更多详细信息，请参阅 the article about DictionaryKeys on python.org。
set怎么样？
集合就像一本只有键没有值的字典。问题包含此代码：
word_dict = dict((elt, 1) for elt in word_list)
这显然是一个不需要值的字典，所以一个集合会更合适。
顺便说一句，不需要先创建一个列表 word_list 并将其转换为 set 或 dict。第一步可以跳过：
set_of_words = {elt.strip() for elt in open("bible_words.txt", "r").readlines()}
有什么缺点吗？
总是 ;)
一组没有重复。所以计算一个单词在集合中的次数永远不会 return 2. 如果需要，请不要使用集合。
一套未订购。无法检查哪个是集合中的第一个单词。如果需要，请不要使用集合。
保存到集合中的对象必须是可散列的，这意味着它们是不可变的。如果可以修改对象，那么它的 hash 就会改变，所以它会在错误的桶中并且搜索它会失败。无论如何，str、int、float 和 tuple 对象是不可变的，所以至少它们可以进入集合。
写入到集合可能比写入列表慢一点。仍然是 O(n)，但更慢的 O(n)，因为它必须计算散列并组织到桶中，而列表只是一个接一个地转储。请参阅下面的时间安排。
从集合中读取所有内容 也比从列表中读取所有内容 慢一些。
所有这些都适用于 dict 以及 set。
一些带计时的例子
写入列表与集合：
>>> timeit.timeit('[n for n in range(1000000)]', number=10)
0.7802875302271843
>>> timeit.timeit('{n for n in range(1000000)}', number=10)
1.025623542189976
读取列表与集合：
>>> timeit.timeit('989234 in values', setup='values=[n for n in range(1000000)]', number=10)
0.19846207875508526
>>> timeit.timeit('989234 in values', setup='values={n for n in range(1000000)}', number=10)
3.5699193290383846e-06
所以，写入一个集合似乎慢了大约 30%，但是当有数千个项目时，在集合中查找一个项目要快数千倍。
假设我有一个大清单：
word_list = [elt.strip() for elt in open("bible_words.txt", "r").readlines()]
//complexity O(n) --> proporcional to list length "n"
我了解到 hash function 用于构建 dictionaries 可以使 lookup 更快，如下所示：
word_dict = dict((elt, 1) for elt in word_list)
// complexity O(l) ---> constant.
使用 word_list，是否有推荐的最有效的方法来降低我的代码的复杂性？
问题中的代码只做了一件事：将文件中的所有单词填充到列表中。其复杂度为 O(n)。
将相同的单词填充到任何其他类型的容器中仍然至少有 O(n) 的复杂度，因为它必须从文件中读取所有单词并将所有单词放入容器中.
dict 有什么不同？
找出某物是否在 list 中的复杂度为 O(n)，因为算法必须逐项遍历列表并检查它是否是要查找的项目。该项目可以在位置 0 找到，这很快，或者它可能是最后一个项目（或者根本不在列表中），这使得它 O(n).
在dict中，数据组织在"buckets"中。当 key:value 对保存到 dict 时，计算键的 hash 并且该数字用于标识 bucket 中的数据被储存了。之后在查找key的时候，再次计算hash(key)来标识bucket，然后只搜索那个bucket。每个 bucked 通常只有一对 key:value，因此可以在 O(1) 中完成搜索。
有关更多详细信息，请参阅 the article about DictionaryKeys on python.org。
set怎么样？
集合就像一本只有键没有值的字典。问题包含此代码：
word_dict = dict((elt, 1) for elt in word_list)
这显然是一个不需要值的字典，所以一个集合会更合适。
顺便说一句，不需要先创建一个列表 word_list 并将其转换为 set 或 dict。第一步可以跳过：
set_of_words = {elt.strip() for elt in open("bible_words.txt", "r").readlines()}
有什么缺点吗？
总是 ;)
一组没有重复。所以计算一个单词在集合中的次数永远不会 return 2. 如果需要，请不要使用集合。
一套未订购。无法检查哪个是集合中的第一个单词。如果需要，请不要使用集合。
保存到集合中的对象必须是可散列的，这意味着它们是不可变的。如果可以修改对象，那么它的 hash 就会改变，所以它会在错误的桶中并且搜索它会失败。无论如何，
str、int、float和tuple对象是不可变的，所以至少它们可以进入集合。写入到集合可能比写入列表慢一点。仍然是 O(n)，但更慢的 O(n)，因为它必须计算散列并组织到桶中，而列表只是一个接一个地转储。请参阅下面的时间安排。
从集合中读取所有内容 也比从列表中读取所有内容 慢一些。
所有这些都适用于 dict 以及 set。
一些带计时的例子
写入列表与集合：
>>> timeit.timeit('[n for n in range(1000000)]', number=10)
0.7802875302271843
>>> timeit.timeit('{n for n in range(1000000)}', number=10)
1.025623542189976
读取列表与集合：
>>> timeit.timeit('989234 in values', setup='values=[n for n in range(1000000)]', number=10)
0.19846207875508526
>>> timeit.timeit('989234 in values', setup='values={n for n in range(1000000)}', number=10)
3.5699193290383846e-06
所以，写入一个集合似乎慢了大约 30%，但是当有数千个项目时，在集合中查找一个项目要快数千倍。