façon efficace d'utiliser lambda, carte de python

Question

Je dois stocker une grande liste d'entiers dans BigTable (db). Pour plus d'efficacité, je suis les stocker sous forme diff entre 2 points consécutifs.

pour par exemple:

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

Stockage de la liste ci-dessus (qui contient en fait plus de 1000k articles) comme

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

Le plus proche que je pouvais gérer est,

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

Je cherche un moyen efficace de le reconvertir en liste originale.

Answer 1

Les oeuvres suivantes pour moi:

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

L'utilisation map va créer un nouveau tableau de la même taille, rempli de None. Je trouve aussi simple boucle de for plus lisible, et dans ce cas aussi vite que vous pouvez obtenir.

Answer 2

Pour ces grandes structures de données numpy va bien travailler. Pour cet exemple, il est sur 200x plus rapide (voir ci-dessous), et un peu plus facile à coder, fondamentalement juste

add.accumulate(diff)

Comparaison entre les numpy et la manipulation de la liste directe:

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)

donne

13.4044158459     # for list looping
0.0474112033844   # for numpy accumulate

Vraiment, cependant, il semble préférable de réutiliser un algorithme de compression mis en place, comme peut facilement être fait avec PyTables , plutôt que de rouler votre propre comme il semble que vous faites ici.

En outre, ici, je suggère que vous avez lu dans les données avec salle pour la durée de démarrage Prepended, plutôt que de reconstruire la liste avec le terme Prepended, bien sûr, vous ne devez pas faire la copie.

Answer 3

Parfait pour les générateurs:

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

Plusieurs des autres répondants ont mises en œuvre raisonnables de l'algorithme que vous avez demandé, mais je ne suis pas clair sur exactement ce problème, il est vous vraiment essayer de résoudre.

A moins que les numéros étant stockés sont très grandes (par exemple, un débordement entier et nécessitent bignums), votre liste de diffs ne vous gagnez une efficacité - un entier est un entier de l'exécution Python POV, de sorte que votre exemple " diff » liste des [-1, -1, 1, 2] consommera tout autant que la mémoire [1005, 1004, 1003, 1004, 1006] de liste originale.

Answer 5

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

Maintenant, essayez:

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

Answer 6

mshsayem suggéré, utiliser la liste compréhensions - ils sont généralement plus rapides que pour les boucles ou une carte / lambdas (selon le livre de faire Mark Lutz Learning Python)

.

Si vous voulez vraiment utiliser une solution plus FP-ish, la fonction appropriée serait « scan », Wich [je crois] n'est pas implémenté en Python afin que vous auriez à mettre en œuvre vous-même (ce qui est un disque tâche).

« scan » est essentiellement une réduire, mais au lieu de réduire la liste à une valeur unique, il stocke le résultat de chaque « itération » dans une nouvelle liste.

Si vous avez implémenté, vous pouvez faire quelque chose comme:

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

Answer 7

Bien que je ne comprends pas pourquoi cela devrait être plus efficace, je suis assez sûr une boucle donnera les meilleures performances:

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

Answer 8

Je ne sais pas au sujet de votre raisonnement pour stocker les entiers comme diffs - rcoder a donné une bonne réponse sur les raisons de ce qui est généralement plus efficace que le stockage des entiers eux-mêmes - mais si vous n'avez pas besoin d'avoir accès à la liste entière à la fois, il est plus efficace sage mémoire pour vous d'utiliser un générateur. Puisque vous dites que cela est une « grande liste, » vous pouvez économiser beaucoup de mémoire de cette façon, au lieu d'attribuer à la fois la liste complète. Voici une compréhension du générateur pour obtenir votre liste de retour:

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

Vous pouvez ensuite itérer sur int_generator comme vous le feriez une liste, sans avoir la liste entière en mémoire à la fois. Notez toutefois que vous ne pouvez pas couper ou un indice générateur, mais vous pouvez l'utiliser dans de nombreuses situations utiles.

Vous pouvez nettoyer l'exemple de sorte que la variable de démarrage n'a pas besoin d'être globale. Il peut tout simplement pas être local à la fonction mod_start.

Modifier Vous ne devez pas utiliser la compréhension du générateur pour obtenir un générateur. Vous pouvez également utiliser une fonction de générateur avec l'expression de rendement, comme l'a fait THC4k. Cela évite le problème de démarrage de portée variable et est probablement un peu plus propre. Vous pouvez également obtenir une liste à partir d'un générateur à tout moment en passant à la liste () fonction intégrée.

Answer 9

Aucun commentaire sur la performance de cela, mais vous pouvez utiliser réduire ici.

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

obtient ce que vous voulez.