Maneira eficiente de usar python lambda, mapa de

Question

Eu preciso para armazenar uma lista grande de números inteiros no Bigtable(db).Para a eficiência estou armazenando-os como de comparação entre os 2 itens consecutivos.

por exemplo:

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

Armazenar a lista acima(que, na verdade, contém mais de 1000k itens) como

start = 1005
diff = [-1, -1, 1, 2]

O mais próximo que eu poderia gerir é,

ltp = [start]
map(lambda x: ltp.append(ltp[-1] + x), tick)

Estou a procura de uma maneira eficiente para convertê-lo de volta na lista original.

Answer 1

O seguinte funciona para mim:

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

Usando map criará uma nova matriz do mesmo tamanho, cheia de None. Eu também acho um simples for Loop mais legível e, neste caso, o mais rápido possível.

Answer 2

Para estruturas de dados tão grandes, Numpy funcionará bem. Para este exemplo, é Mais de 200x mais rápido (veja abaixo), e um pouco mais fácil de codificar, basicamente apenas

add.accumulate(diff)

Comparação entre manipulação de listas Numpy e direta:

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)

dá

13.4044158459     # for list looping
0.0474112033844   # for numpy accumulate

Realmente, porém, parece melhor reutilizar um algoritmo de compressão estabelecido, como pode ser feito facilmente com Pytables, em vez de rolar o seu próprio como parece que você está fazendo aqui.

Além disso, aqui, estou sugerindo que você leia os dados com espaço para o termo de início pré -preso, em vez de reconstruir a lista com o termo precendido, é claro, para que você não precise fazer a cópia.

Answer 3

Perfeito para geradores:

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 ))

Answer 4

Vários outros entrevistados têm razoável implementações do algoritmo de você pediu, mas eu sou claro sobre exatamente o que o problema é que você está realmente tentando resolver.

A menos que os números que estão sendo armazenados são muito grandes (por exemplo, estouro de um número inteiro e exigir bignums), sua lista de difs não ganhar a qualquer eficiência -- um número inteiro é um número inteiro de o tempo de execução do Python POV, para que o seu exemplo de "diff" lista de [-1, -1, 1, 2] irá consumir mais memória do que a lista original [1005, 1004, 1003, 1004, 1006].

Answer 5

class runningtotal:
    def __init__(self, start = 0):
        self.total = start
    def __call__(self, value):
        self.total += value
        return self.total

Agora tente:

>>> map(runningtotal(start), [0,]+diff)
[1005, 1004, 1003, 1004, 1006]

Answer 6

Como o MSHSAYEM sugeriu, use as compreensões da lista - elas geralmente são mais rápidas do que para loops ou mapa/lambdas (de acordo com o livro de Mark Lutz, Learning Python).

Se você realmente deseja usar uma solução mais FP-ish, a função adequada seria "Scan", o que [eu acredito] não é implementado no Python, então você precisará implementá-lo (o que não é uma tarefa difícil).

"Scan" é basicamente uma redução, mas, em vez de reduzir a lista para um único valor, ele armazena o resultado de cada "iteração" em uma nova lista.

Se você o implementou, poderá fazer algo como:

scan(lambda x,y: x+y, [start]++diff)

Answer 7

Embora eu não entendi por que isso deve ser mais eficiente, tenho certeza de que um loop para dar o melhor desempenho:

l = [start]
for i in diff:
    l.append(l[-1] + i)

Answer 8

Não sei sobre o seu raciocínio para armazenar os números inteiros como diferenças - o Rcoder deu uma boa resposta sobre por que isso geralmente não é mais eficiente do que armazenar os números inteiros - mas se você não precisar ter acesso a toda a lista Ao mesmo tempo, é mais eficiente em termos de memória para você usar um gerador. Como você diz que esta é uma "grande lista", você pode economizar muita memória dessa maneira, em vez de alocar a lista inteira de uma só vez. Aqui está uma compreensão do gerador para recuperar sua lista:

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

Você pode iterar sobre o Int_Generator como faria com qualquer lista, sem ter a lista inteira na memória de uma só vez. Observe, no entanto, que você não pode subscrever ou cortar um gerador, mas pode usá -lo em muitas situações úteis.

Você pode limpar o exemplo para que a variável inicial não precise ser global. Simplesmente não pode ser local para a função mod_start.

Editar: Você não precisa usar a compreensão do gerador para obter um gerador. Você também pode usar uma função de gerador com a expressão de rendimento, como o THC4K. Isso evita o problema do escopo variável inicial e provavelmente é um pouco mais limpo. Você também pode obter uma lista de um gerador a qualquer momento, passando-o para a função interna da lista ().

Answer 9

Sem comentários sobre o desempenho disso, mas você pode usar o Reduce aqui.

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

pega o que você quer.