dict理解效率低吗…有没有更快的方法来比较两个dict中的键和值？

Question

我试图解决一个问题，其中两个字符串作为参数给出，任务是确定第一个字符串是否包含生成第二个字符串所需的所有元素。我认为我有一个相当简单的解决方案，通过从两个字符串创建字典，其中键是字符串中的字符，值是它们各自的出现次数。代码如下：

    def scramble(s1, s2):
        s1dict = {x: s1.count(x) for x in s1}
        s2dict = {y: s2.count(y) for y in s2}
        s3dict = {k:s2dict[k] for k in s2dict and s1dict[k] >= s2dict[k]}
        return s3dict == s2dict

当我尝试将解决方案提交到web质询解释器时，它会说我的代码超时了。我知道对于大型字符串，这个解决方案会导致大量的迭代…我可以采取什么方法来提高效率？你知道吗

Answer 1

正如其他人所说，词典理解并不是天生的低效。如果你想加快你的解决方案，你应该看看你的算法。你知道吗

s1dict = {x: s1.count(x) for x in s1}是获取s1中所有字符计数的低效方法。如果s1是长度N，那么它将在s1中迭代N次，使其成为O（N^2）。如果你要自己实现这个逻辑，它会像这样：

s1dict = {}
for char1 in s1:
    for char2 in s1:
        if char2 == char1:
            s1dict[char1] = s1dict.get(char1, 0) + 1

有一种方法可以在O（N）时间内得到计数。你知道吗

s1dict = {}
for char in s1:
    s1dict[char] = s1dict.get(char, 0) + 1

或者，您可以使用collections.Counter为您执行此操作：s1dict = collections.Counter(s1)。你知道吗

你计算s3dict的方法实际上是无效的。我也不认为字典理解是比较这两本字典的最好方法。您可以使用字典理解（all({k: s1dict.get(k, 0) >= v for k, v in s2dict.items()})），但为什么不编写一个简单的循环呢？你知道吗

for key, value in s2dict.items():
    if s1dict.get(key, 0) < value:
        return False
return True