给定 5 mb 内存和 5 秒时间的限制，如何在中找到一定数量的唯一单词？

Question

任何人都好，谁回答了我的问题。我试图解决找到一定数量的独特单词的问题，这些单词将作为输入输入，第一个输入将是要输入的单词数量。像这样：

5

track

lost

scale

lost

table

正确答案应该是：4

我已经尝试在 Python 中解决这个问题，如下所示：

a=set()

x = int(input())

a.add(x)

for i in range(x):

    y = input()

    a.add(y)

print(len(a)-1)

它似乎工作得很好，只是在内存方面效率不高（它超出了内存限制，在高输入下）。有没有更有效的方法来解决这个问题？

Answer 1

由于您使用的是 Python 3.6+，因此可以节省廉价内存：使用dict，而不是set. 尽管需要为每个元素存储一个值，dict但即使在旧版本的 Python 中，s 也经常使用更少的内存（它们针对不同的事物进行了优化；set倾向于过度分配桶以降低桶冲突的风险，但这会花费更多内存） ; 在 3.6+ 中，他们转向更紧凑的dict设计，只要唯一数据不是很大，就可以节省更多（set当唯一项目的数量超过2**15/32768 时，s 可以再次开始赢得某些大小，因为紧凑性收益下降在那一点上戏剧性地）。因此，要更改它，只需执行以下操作：a = {}x = int(input())for _ in range(x):    a[input()] = Noneprint(len(a))此外，为了速度，如果您不需要使用input，您可能应该避免使用它并直接读取sys.stdin；input做了很多不必要的输出刷新和其他你在这里并不真正需要的工作。所以这样做可能会更快：import itertools, sysx = int(input())a = dict.fromkeys(itertools.islice(sys.stdin.buffer, x))print(len(a))它只是直接拉动线条而无需修改，并将它们直接推入dictC 级以获得额外的速度。更改sys.stdin以sys.stdin.buffer避免在所有解码串，并在包装map(str.rstrip, ...)或map(bytes.rstrip, ...)用于sys.stdin.buffer去除换行符（如果最后一行可能无法在新行结束了，这是必要的正确性，我想这样可以节省内存微不足道的金额）。如果输入可能很大（更高的五位数唯一输入），那么dict可能无济于事，所以坚持使用set，但您仍然可以使用sys.stdin优化，导致最终形式如下：x = int(input())a = set(itertools.islice(map(bytes.rstrip, sys.stdin.buffer), x))print(len(a))

Answer 2

根据数据的预期性质：对于字典单词，尤其是相似的单词，请使用 trie对于长文本，使用无损压缩zlib压缩示例：import zliba = set()x = int(input())for _ in range(x):    a.add(zlib.compress(input().encode()))    #a.add(input())print("unique: ", len(a))print("memory: ", sum(len(b) for b in a))未压缩：> echo -e "3\naaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbb\naaaaaaaaaaaaaaaa" | python3 c.pyunique:  2memory:  32压缩：> echo -e "3\naaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbb\naaaaaaaaaaaaaaaa" | python3 c.pyunique:  2memory:  22

Answer 3

它给我带来了 2 个解决方案。第一个是使用 JSON 结构。JSON 结构使用唯一键，然后，您可以创建此结构，然后检查您有多少键。代码看起来像这样对于这两个例子，我假设你有一个包含所有单词的数组，这个数组将是 words_arrayunique_words = {}for word in words_array:  unique_words[word.lower().strip()] = 1   # this  one could be any value  # i just need to create the key valueprint len(unique_words)我使用lower并strip确保这个词是独一无二的，无论单词中的大写还是空格。另一种方法是如果单词已存在则检查数组，此方法有效但效率较低unique_words = []for word in words_array:  w = word.lower().strip()  if not w in unique_words:    unique_words.append(w)print len(unique_words)如果您正在寻找内存效率，我会建议其他替代方案，例如使用 C