3

Bigtable（db）に整数の大きなリストを保存する必要があります。効率を上げるために、2つの連続するアイテム間の差分としてそれらを保存しています。

例：

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

上記のリスト（実際には10万を超えるアイテムが含まれています）を次のように保存します

開始=1005
diff = [-1、-1、1、2]

私が管理できる最も近いものは、

ltp=[開始]
map（lambda x：ltp.append（ltp [-1] + x）、tick）

元のリストに戻すための効率的な方法を探しています。

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

他の回答者の何人かはあなたが求めたアルゴリズムの合理的な実装を持っていますが、あなたが本当に解決しようとしている問題が正確にはわかりません。

格納されている数値が非常に大きい場合（つまり、整数をオーバーフローしてbignumが必要な場合）を除いて、差分のリストは効率を上げません。整数は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が示唆しているように、リスト内包表記を使用します。一般的に、ループやマップ/ラムダよりも高速です（MarkLutzの著書LearningPythonによると）。

もっとFPっぽいソリューションを本当に使いたいのなら、適切な関数は「スキャン」ですが、Pythonには実装されていないので、自分で実装する必要があります（これは難しい作業ではありません）。

「スキャン」は基本的に削減ですが、リストを単一の値に削減する代わりに、各「反復」の結果を新しいリストに格納します。

あなたがそれを実装した場合、あなたは次のようなことをすることができます：

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

これがより効率的である理由はわかりませんが、forループが最高のパフォーマンスを発揮すると確信しています。

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

整数をdiffとして格納する理由はわかりませんが、rcoderは、整数自体を格納するよりも一般的に効率が悪い理由について良い答えを出しましたが、リスト全体にアクセスする必要がない場合は一度に、ジェネレータを使用する方がメモリ的に効率的です。これは「大きなリスト」であると言うので、リスト全体を一度に割り当てる代わりに、この方法で多くのメモリを節約できます。リストを元に戻すためのジェネレーターの理解は次のとおりです。

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

その後、リスト全体を一度にメモリに保存しなくても、他のリストと同じようにint_generatorを反復処理できます。ただし、ジェネレータを添え字またはスライスすることはできませんが、多くの便利な状況で使用できることに注意してください。

開始変数がグローバルである必要がないように、例をクリーンアップできます。mod_start関数に対してローカルにすることはできません。

編集：ジェネレーターを取得するためにジェネレーター内包表記を使用する必要はありません。THC4kのように、yield式でジェネレーター関数を使用することもできます。これにより、開始変数スコープの問題が回避され、おそらく少しクリーンになります。また、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 に答える