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

Question

任何人都好，谁回答了我的问题。我试图解决找到一定数量的独特单词的问题，这些单词将作为输入输入，第一个输入将是要输入的单词数量。像这样：5tracklostscalelosttable正确答案应该是：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()] = None

print(len(a))

此外，为了速度，如果您不需要使用input，您可能应该避免使用它并直接读取sys.stdin；input做了很多不必要的输出刷新和其他你在这里并不真正需要的工作。所以这样做可能会更快：

import itertools, sys

x = 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 zlib

a = 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.py

unique:  2

memory:  32

压缩：

> echo -e "3\naaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbb\naaaaaaaaaaaaaaaa" | python3 c.py

unique:  2

memory:  22

Answer 3

它给我带来了 2 个解决方案。第一个是使用 JSON 结构。JSON 结构使用唯一键，然后，您可以创建此结构，然后检查您有多少键。

代码看起来像这样

对于这两个例子，我假设你有一个包含所有单词的数组，这个数组将是 words_array

unique_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 value

print 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