Effizient zu Lambda der Nutzung Python, Karte

Question

Ich brauche eine große Liste von ganzen Zahlen in Bigtable zu speichern (db). Aus Gründen der Effizienz, sie als diff zwischen 2 aufeinander folgenden Artikeln Ich bin zu speichern.

für zB:

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

Das Speichern der obigen Liste (die eigentlich mehr als 1000k Elemente enthält) als

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

Die nächstgelegene ich verwalten könnte, ist,

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

Ich bin für einen effizienten Weg, um es zu konvertieren zurück in die ursprüngliche Liste.

Answer 1

Die folgenden Werke für mich:

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

map Verwendung wird ein neues Array der gleichen Größe erstellen, gefüllt mit None. Ich finde auch, eine einfache for Schleife besser lesbar, und in diesem Fall so schnell wie möglich zu erhalten.

Answer 2

Für solche großen Datenstrukturen numpy wird gut funktionieren. Für dieses Beispiel ist es über 200x schneller (siehe unten), und ein bisschen leichter zu kodieren, im Grunde nur

add.accumulate(diff)

Vergleich zwischen numpy und direkter Liste Manipulation:

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)

gibt

13.4044158459     # for list looping
0.0474112033844   # for numpy accumulate

Wirklich, obwohl, so scheint es besser, einen etablierten Komprimierungsalgorithmus wieder zu verwenden, wie leicht mit PyTables , anstatt Ihre eigenen rollen, wie es scheint, dass du hier tust.

Auch hier bin ich darauf hindeutet, dass Sie in den Daten mit Raum für die vorangestellter Start Begriff lesen, anstatt die Liste mit dem vorangestellten Begriff wieder aufzubauen, natürlich, so dass Sie die Kopie nicht zu tun.

Answer 3

Perfekt für Generatoren:

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

Einige der anderen Befragten begründete Implementierungen des Algorithmus Sie gefragt, aber ich bin nicht klar auf genau, welches Problem es ist, Sie wirklich zu lösen versuchen.

Es sei denn, die Zahlen gespeichert sind sehr groß (dh Überlauf eine ganze Zahl und erfordern bignums), die Liste der diffs werden Sie keine Effizienz gewinnen - eine ganze Zahl ist eine ganze Zahl aus dem Python-Laufzeit POV, so dass Ihr Beispiel " diff“Liste der [-1, -1, 1, 2] wird nur so viel Speicher wie die ursprüngliche Liste [1005, 1004, 1003, 1004, 1006] verbrauchen.

Answer 5

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

Jetzt versuchen:

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

Answer 6

Wie mshsayem vorgeschlagen, die Verwendung Listenkomprehensionen -. Sie sind in der Regel schneller als für Schleifen oder Karte / lambda (nach do Mark Lutz Buch Learning Python)

Wenn Sie wirklich eine mehr FP-ish-Lösung verwenden möchten, würde die ordnungsgemäße Funktion „Scan“ sein, wich [Ich glaube] ist in Python nicht implementiert, so würden Sie es selbst implementieren müssen (was nicht schwer ist Aufgabe).

„Scan“ ist im Grunde eines reduzieren, aber anstatt die Liste auf einen einzelnen Wert zu reduzieren, es speichert das Ergebnis jeder „Iteration“ in einer neuen Liste.

Wenn Sie es implementiert, können Sie etwas tun könnte, wie:

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

Answer 7

Obwohl ich nicht, warum dies effizienter sein sollte, ich bin ziemlich sicher, dass ein for-Schleife wird die beste Leistung geben:

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

Answer 8

Ich weiß nicht, über Ihre Argumentation für die ganzen Zahlen als diffs speichern - rcoder eine gute Antwort auf die Frage gab, warum dies in der Regel nicht effizienter als die ganzen Zahlen Speicherung selbst - aber wenn Sie benötigen keinen Zugang zu müssen die gesamte Liste auf einmal, es ist effizienter Speicher-weise für Sie einen Generator zu verwenden. Da Sie sagen, dass dies eine „große Liste“ können Sie auf diese Weise eine Menge Speicher speichern, statt die gesamte Liste auf einmal zuweisen. Hier ist ein Generator Verständnis Ihre Liste zurück zu bekommen:

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

Sie kann dann Iterierte über int_generator wie jede Liste, ohne sofort die gesamte Liste in Speichern. Beachten Sie jedoch, dass Sie nicht tief- oder in Scheiben schneiden, einen Generator, aber man kann es in vielen nützlichen Situationen verwenden.

Sie können das Beispiel aufzuzuräumen, so dass der Start Variable nicht global sein muss. Es kann einfach nicht auf die mod_start Funktion lokal sein.

Edit: Sie müssen nicht den Generator Verständnis verwenden, um einen Generator zu erhalten. Sie können auch eine Generatorfunktion mit dem Ertrag Ausdruck verwenden, wie THC4k tat. Das vermeidet den Start variable Umfang Problem und ist wahrscheinlich ein wenig saubere. Sie können auch eine Liste von einem Generator jederzeit erhalten, indem es in die Liste () integrierte Funktion übergeben.

Answer 9

Kein Kommentar über die Leistung dieses, aber Sie können hier verwenden reduzieren.

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

bekommt man, was Sie wollen.