2

我正在尝试编写一些代码来计算 2 的幂，但将它们存储在以 10 的幂作为键的字典中，例如，2^9 将存储为

{0:2, 1:1, 2:5}

你有 5*10^2 + 1*10^1 + 2*10^0。

所以目前，我有类似的东西

def foo():
    result={0:2}
    for i in range(2,10):
        for p in result.keys():
            result[p]*=2
        for p in result.keys():
            if result[p] / 10 != 0:
                result.setdefault(p+1,result[p]/10)
                result[p] = result[p] % 10

问题是

result.setdefault(p+1,result[p]/10)

它会覆盖result[p+1]. 我知道可以只检查字典，然后在需要时“初始化”新密钥，但是有没有更优雅的方法可以即时完成？我可以将结果初始化为足够长，但由于我不一定知道“足够长”有多长，所以在我看来，动态扩展它更有意义。

基本上我想要一些类似的东西

for p in result.keys():
    if result[p] / 10 != 0:
        if result[p+1] exists:
            result[p+1]+=result[p]/10
        else:
            create result[p+1] and set its value to result[p]/10

任何帮助深表感谢！

4

2 回答 2

2

所以，你每次通过主循环所做的是：将每个数字加倍，然后将额外的十位带到下一个数字。问题是，对于最高数字，下一个数字不存在。

所以这是一个解决方案——尽管它不适用于除 2 之外的任何幂，原因我将在下面讨论。

def foo():
    result={0:2}
    for i in range(2,10):
        for p in result.keys():
            result[p]*=2
        for p in result.keys()[:]:
            if result[p] / 10 != 0:
                result[p+1] = result.get(p+1, 0) + result[p] / 10
                result[p] = result[p] % 10

您的原始代码有两个关键更改。

首先，我们必须添加[:]到 second 的末尾result.keys()，以便在循环之前迭代字典的一组键的副本，而不是它的当前键。原因是如果最后一位数字大于 5，我们将在字典中添加一个新键，并且在迭代它时不允许这样做。（为什么？有几个原因，但最简单的一个是字典是任意顺序的，每次添加一个键，整个顺序都会改变。这在以后也很重要。）

其次，您最初的问题是：您如何避免必须检查if p+1 in result以决定是存储r_p还是添加r_p到现有值？

当您处理计数时，您使用collection.Counter，它类似于 a dict，只是它只存储整数，并且任何缺少的键的值都为 0。否则，您通常使用collection.defaultdict，它类似于 a dict，除了您可以指定一个默认值所有丢失的钥匙都有。使用 aCounter或defaultdict，您只需要result[p+1] += result[p]/10.

但我使用了另一种选择： 上的get方法dict，它允许您指定默认值。我稍后会解释为什么，但请记住，一般来说，当你发现自己伸手去拿 时get，你可能想要一个defaultdictorCounter代替。

所以，现在它可以运行并工作，对于 2 的幂。但它不适用于其他幂，原因有两个：

首先，我们以随机顺序进行进位。对于 2 的幂，您最多可以携带 1，并且 1 不会影响下一个数字是否携带。（8 不会携带，8+1 也不会，现在有办法得到 9。）但对于任何其他力量，这不是真的。

在简单的测试中，你可能不会注意到这一点，因为它恰好发生在（至少在 CPython 2.7 和 3.2 中）当你从一个空开始dict并添加少量小键（实际上，具有小散列值的键，但ints 以排序顺序散列到自己），并且不删除任何内容，dict通常会按顺序迭代（和打印）。但总的来说，顺序是不可预测的，你不能依赖它。

该问题的解决方案是使用collections.OrderedDict，它按照添加顺序对键进行迭代。这就是为什么我不想使用defaultdictor Counter: 因为如果你必须切换到OrderedDict，你唯一的选择是get.

其次，一旦您的指数超过 10，您可能需要进位 100。这意味着您必须进位 10，这将导致下一个数字即使是 0 也会进位。这意味着我们不能只复制密钥进步。例如，假设我们正在计算 75 的幂。从 开始{0:5, 1:7}。将每个数字乘以 75 即可{0:375, 1:525}。现在携带 37: {0:5, 1:562}。现在携带 56: {0:5, 1:2, 2:56}。因为我们只是迭代原始密钥的副本——也就是说——[0, 1]我们没有机会携带 5。

我会把它留给你来解决这个问题。

但是，您可能要考虑的一件事是创建一个新字典，而不是修改旧字典。然后你就可以解决所有这些问题。（作为一般规则，使用纯函数而不是改变状态会解决很多问题，但当然是以额外复制为代价的。）

def double(d):
    result = Counter()
    for p in d:
        result[p] += d[p] % 10
        result[p+1] += d[p] / 10
    return result

digits={0:2}
for i in range(2,10):
    for p in digits:
        digits[p]*=2
    digits = double(digits)
于 2012-09-29T06:22:24.940 回答
1

您可以使用以下in语法检查密钥是否存在：

for p in result.keys()[:]:
    r_p = result[p] / 10

    if r_p != 0:
        if p + 1 in result:
            result[p + 1] += r_p
        else:
            result[p + 1] = r_p

或者，您可以使用Counter，它会自动执行此操作：

from collections import Counter

result = Counter()

for p in result.keys()[:]:
    r_p = result[p] / 10

    if r_p != 0:
        result[p + 1] += r_p

另外，你的情况有点奇怪。result[p] / 10 == 0仅result[p] < 10在 Python 2 或result[p] == 0Python 3 上。

于 2012-09-29T04:22:47.630 回答