3

我需要在 Bigtable(db) 中存储大量整数。为了提高效率，我将它们存储为两个连续项目之间的差异。

例如：

original_list = [1005, 1004, 1003, 1004, 1006]

将上述列表（实际上包含超过 1000k 项）存储为

开始 = 1005
差异 = [-1, -1, 1, 2]

我能做到的最接近的是，

ltp = [开始]
地图（lambda x：ltp.append（ltp[-1] + x），打勾）

我正在寻找一种有效的方法将其转换回原始列表。

4

9 回答 9

7

对于如此大的数据结构，numpy 可以很好地工作。对于这个例子，它的速度提高了 200 倍以上（见下文），并且更容易编码，基本上只是

add.accumulate(diff)

numpy 和直接列表操作的比较：

import numpy as nx
import timeit

N = 10000

diff_nx = nx.zeros(N, dtype=nx.int)
diff_py = list(diff_nx)

start = 1005

def f0():
    orig = [start]
    for x in diff_py: 
        orig.append(orig[-1] + x)

def f1():
    diff_nx[0] = start
    nx.add.accumulate(diff_nx)

t = timeit.Timer("f0()", "from __main__ import f0, f1, diff_nx, diff_py, nx, start")
print t.timeit(number=1000)
t = timeit.Timer("f1()", "from __main__ import f0, f1, diff_nx, diff_py, nx, start")
print t.timeit(number=1000)

给

13.4044158459     # for list looping
0.0474112033844   # for numpy accumulate

但是，实际上，重用已建立的压缩算法似乎更好，就像可以使用PyTables轻松完成一样，而不是像您在这里所做的那样滚动您自己的算法。

另外，在这里，我建议您在数据中读取前置开始术语的空间，而不是使用前置术语重建列表，这样您就不必进行复制。

于 2009-09-01T16:41:17.617 回答
6

以下对我有用：

orig = [start]
for x in diff:
    orig.append(orig[-1] + x)

使用map将创建一个相同大小的新数组，用None. 我还发现一个简单的for循环更具可读性，并且在这种情况下尽可能快。

于 2009-09-01T16:35:21.450 回答
4

非常适合发电机：

def diff2abs( diffs, start ):
    yield start
    for diff in diffs:
        start += diff
        yield start

start = 1005
diffs = [-1, -1, 1, 2]
original_list = list( diff2abs( diffs, start ))
于 2009-09-01T16:41:40.063 回答
2

其他几位受访者对您要求的算法有合理的实现，但我不清楚您真正想要解决的问题到底是什么。

除非存储的数字非常大（即溢出整数并需要 bignums），否则您的差异列表不会为您带来任何效率——整数是 Python 运行时 POV 中的整数，因此您的示例“差异”列表of[-1, -1, 1, 2]将消耗与原始列表一样多的内存[1005, 1004, 1003, 1004, 1006]。

于 2009-09-01T16:41:09.787 回答
2 
class runningtotal:
    def __init__(self, start = 0):
        self.total = start
    def __call__(self, value):
        self.total += value
        return self.total

现在尝试：

>>> map(runningtotal(start), [0,]+diff)
[1005, 1004, 1003, 1004, 1006]
于 2009-09-01T16:41:43.077 回答
1

正如 mshsayem 建议的那样，使用列表推导 - 它们通常比 for 循环或 map/lambdas 更快（根据 Mark Lutz 的书 Learning Python）。

如果您真的想使用更类似于 FP 的解决方案，那么正确的功能将是“扫描”，[我相信]没有在 Python 中实现，因此您必须自己实现它（这不是一项艰巨的任务）。

“扫描”基本上是一个减少，但不是将列表减少为单个值，而是将每个“迭代”的结果存储在一个新列表中。

如果您实现了它，您可以执行以下操作：

scan(lambda x,y: x+y, [start]++diff)
于 2009-09-01T16:46:16.310 回答
0

我不知道您将整数存储为差异的原因 - rcoder 给出了一个很好的答案，说明为什么这通常不比存储整数本身更有效 - 但如果您不需要访问整个列表一次，使用生成器在内存方面更有效率。由于您说这是一个“大列表”，因此您可以通过这种方式节省大量内存，而不是一次分配整个列表。这是一个生成器理解，可以让您的列表恢复：

start = 1005
def mod_start(x):
    global start
    start += x
    return start
int_generator = (mod_start(i) for i in diffs)

然后，您可以像对任何列表一样迭代 int_generator，而无需一次将整个列表放在内存中。但是请注意，您不能对生成器进行下标或切片，但可以在许多有用的情况下使用它。

您可以清理示例，以便 start 变量不需要是全局的。它不能位于 mod_start 函数的本地。

编辑：您不必使用生成器理解来获取生成器。您还可以使用带有 yield 表达式的生成器函数，就像 THC4k 一样。这避免了开始变量范围的问题，并且可能更干净一些。您还可以随时从生成器中获取列表，方法是将其传递给 list() 内置函数。

于 2009-09-01T17:13:30.233 回答
0

对此性能没有评论，但您可以在此处使用 reduce。

start = 1005
diffs = [-1,-1,1,2]
reduce(lambda undiffed_list, diff: undiffed_list + [undiffed_list[-1] + diff],diffs,[start])

得到你想要的。

于 2011-07-04T19:31:30.170 回答
0

虽然我不明白为什么这应该更有效，但我很确定 for 循环将提供最佳性能：

l = [start]
for i in diff:
    l.append(l[-1] + i)
于 2009-09-01T16:35:16.490 回答