在Python中，我们有没有办法找到用户输入的乱七八糟的单词，exists给出一个没有排列代码的列表，让它变得更快？

Question

假设我有一个唯一的300k+项目列表：

mylist = ["door", "mango", "rose", "orange", "car", "knowledge", "flower", ...., 300k+ items]

userinput = input()

现在，如果用户输入混杂的单词"knowledge“。例如："dngwekleo"，程序应该检查mylist中的输入词，并打印"knowledge“作为输出。

我的代码工作正常，直到输入单词的长度为7，我已经使用排列代码进行输入，然后匹配排列== mylist中的每个单词。但是一旦输入词的输入长度超过8-10，它就会产生太多的排列，然后python就会花费太多的时间(10分钟，20分钟，30分钟)来获得输出。

请帮我解决这个问题，以便更快地得到答案，比如10-15秒，从20天开始尝试。

Answer 1

首先，您可以通过创建一个查找来实现，该查找具有按字符排序的键&保留具有原始字符串的值。

例如：{deegklnow : knowledge}

my_list = ["door", "mango", "rose", "orange", "car", "knowledge", "flower"]

lookup = {"".join(sorted(x)): x for x in my_list}

print(lookup.get("".join(sorted("dngwekleo"))))
print(lookup.get("".join(sorted("eosr"))))
print(lookup.get("".join(sorted("rca"))))

knowledge
rose
car

Answer 2

您可以计算原始列表和输入中每个单词的字母数。如果计数匹配，则一个单词是另一个单词的排列。

from collections import Counter
# Pre-calculate the dictionaries
counts = [Counter(word) for word in mylist]

userinput = input()
count = Counter(userinput)
if count in counts:
    # Found it!

对于大型列表，您可以通过为每个单词计算一组冻结的字母-计数对来减少查找时间：

counts = {frozenset(Counter(word).items()) for word in mylist}
count = frozenset(Counter(userinput).items())
if count in counts: ...

Answer 3

编辑经过思考后，我认为DYZ的答案可能会更快。

注意：我假设在输入单词集上做一些预计算是可以接受的，而且只有在那之后的查找时间才是真正重要的。

要扩展DYZ的概念：

• 统计每个字母的出现次数
• 使用该计数更新散列值
• 对列表中的每个输入单词执行此操作，以获得包含key: hash，value: word (或单词列表，例如"cart“和"trac”将导致相同的字符数)的字典。
• 然后还对用户输入进行散列，并在字典中进行查找

<>F211

散列函数的示例实现：

import hashlib
import string

def get_char_count_hash(input_string):
    char_count_hash = hashlib.sha256()

    for char in string.ascii_lowercase:
        char_count = input_string.count(char)
        char_count_hash.update(str(char_count))

    return char_count_hash.hexdigest()

注意:您可以通过稍微优化散列函数来减少预计算时间。