0

假设我有独特的 300k+ 项目列表：

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

userinput = input()

现在，如果用户输入了“知识”的混乱词。例如。“dngwekleo”，程序应检查 mylist 中的输入单词并打印“knowledge”作为输出。

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

请帮助我解决这个问题，以便在 10-15 秒内更快地得到答案，尝试 20 天。

4

3 回答 3

2

只是为了启动，您可以通过使用按字符排序的键创建查找来接近，并使用原始字符串保留值。
例如：{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
于 2020-06-08T08:12:43.260 回答
1

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

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: ...
于 2020-06-08T07:52:37.850 回答
0

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

注意：我假设对输入词集进行一些预计算是可以接受的，并且只有之后的查找时间才真正重要。

扩展DYZ的想法：

  • 计算每个字母出现的次数
  • 使用该计数来更新哈希值
  • 对列表中的每个输入单词执行此操作，以获得一个带有 key: hash, value: word 的字典（或单词列表，例如“cart”和“trac”会导致相同的字符数）
  • 然后还散列用户输入并在字典中进行查找

哈希函数的示例实现：

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()

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

于 2020-06-08T08:37:42.880 回答