时间戳

首页 > 解决方案 > 空间复杂性——重新分配和返回参数，而不是创建新变量来返回

python - 空间复杂性——重新分配和返回参数，而不是创建新变量来返回

问题描述

我很好奇是否为了节省空间，您可以重新分配参数并返回它，而不是创建一个全新的字符串来返回。由于它在范围内是本地的，我认为它不应该影响任何东西，除了可能使它更难以调试。仅仅创建一个新变量并返回它是一种好的做法，甚至是一种标准吗？谢谢。

例如创建和返回 new_str：

def string_compression(string):
    new_str = ""

    dict = {}
    for char in string:
        if char not in dict:
            dict[char] = 1
        else:
            dict[char] += 1
    for key, value in dict.items():
        new_str += key + str(value)

    return new_str

与：（不创建或返回 new_str 变量）

def string_compression(string):
    dict = {}
    for char in string:
        if char not in dict:
            dict[char] = 1
        else:
            dict[char] += 1

    string = ""
    for key, value in dict.items():
        string += key + str(value)

    return string

标签： pythonpython-3.xalgorithm

解决方案

回答你的问题

在这两个代码片段中，您都在创建新字符串。您在第一个版本中为字符串指定不同的名称这一事实并不会使其效率高于或低于第二个版本。

关于命名变量的重要说明dict

该名称dict是用于字典内置类的 python 名称。如果您为自己的变量使用该名称，即使它是字典，也会遇到很多麻烦。您应该不惜一切代价避免为自己的变量使用内置名称。永远不要调用您的变量dict、list、str、sum或该列表中的任何名称：Python 内置函数。取而代之的是，您可以调用您的字典d，或者dictionary，或者更好的方法来解释该字典的用途；例如char_count或类似的东西。

关于字符串连接的重要说明

考虑以下代码片段：

s = ''
for n in range(1000000):
  s += str(n)

它通过连接用十进制写的数字来构建一个字符串：最后s是'01234567891011...999997999998999999'.

但它有效率吗？不，这不对。连接两个字符串s1并s2使用+or的时间复杂度与和+=中的字符总数成正比。在这里，我们连接与，然后与，然后与，然后与，然后与，等等。你看到发生了什么吗？这是画家施莱米尔的故事。复杂性是二次的而不是线性的。s1s2'''0''0''1''01''2''012''3''0123''4'

在 python 中连接两个以上字符串的一种更有效的方法是使用''.join(...). 所以我们应该写：

s = ''.join(str(n) for n in range(1000000)).

使用python模块collections

让我们看看这段代码片段：

    d = {}
    for char in string:
        if char not in d:
            d[char] = 1
        else:
            d[char] += 1

你猜怎么着？您不是第一个遇到需要这种逻辑的人。如果该值不在字典中，则添加它；否则，更新它。这样一个普通的操作只需四行代码！我们当然可以让它自动化一点吗？实际上是的，我们可以。dict我们可以使用 a来代替使用 a defaultdict。will的行为与defaultdictwill 完全相同dict，但它会在需要时为我们处理默认值：

from collections import defaultdict

d = defaultdict(int)
for char in string:
  d[char] += 1

如果d[char]在 需要时它不存在+=，defaultdict则将创建它并给它返回的值int()，即 0。一切都和以前一样；除了我们不必自己编写if/else逻辑。凉爽的！

...可是等等。为什么我们首先需要一本字典？计算字符串中字符出现的次数。这听起来像是一个普遍的问题。事实上，它是如此普遍，以至于有另一个子类比这个dict更适合defaultdict！它被调用Counter，它也在 module 中collections。您可以将上面的代码替换为：

from collections import Counter

d = Counter(string)

就是这样。是的。无需for-loop 手动填充字典。这一切都已经处理好了。

有用的阅读

文档

StackOverflow 问题

最终代码

from collections import Counter

def string_compression(s):
  char_counts = Counter(s)
  return ''.join('{}{}'.format(c,n) for c,n in char_counts.most_common())

print(string_compression('aaaabcbcbb'))
# a4b4c2

如果您想保持字符首次出现的顺序而不是按减少计数排序，您可以在代码中.most_common()替换为。.items()

推荐阅读