Эффективный способ использования лямбда-карты Python

Question

Мне нужно хранить большой список целых чисел в Bigtable (дБ). Для эффективности я храню их в виде различий между двумя последовательными элементами.

например:

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

Сохранение приведенного выше списка (который на самом деле содержит более 1000 тыс. Элементов) как

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

Самое близкое, на что я способен, это

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

Я ищу эффективный способ преобразовать его обратно в исходный список.

Answer 1

Для таких больших структур данных numpy будет хорошо работать. В этом примере это более чем в 200 раз быстрее (см. Ниже) и немного проще для кодирования, в основном просто

add.accumulate(diff)

Сравнение между обработкой списка и прямым списком:

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 , вместо того, чтобы бросать свои собственные, как кажется, что вы делаете здесь.

Кроме того, здесь я предлагаю вам прочитать в данных с местом для предварительно начального термина, а не перестраивать список с предварительно определенным термином, разумеется, так что вам не нужно делать копию.

Answer 2

У меня работает следующее:

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

Использование map создаст новый массив того же размера, заполненный None. Я также нахожу простой цикл for более читабельным, и в этом случае настолько быстрым, насколько это возможно.

Answer 3

Идеально подходит для генераторов:

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

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]

Answer 5

Несколько других респондентов имеют разумные реализации запрашиваемого вами алгоритма, но мне неясно, какую именно проблему вы действительно пытаетесь решить.

Если числа, которые хранятся, не очень велики (т. Е. Переполняются целые числа и требуют больших чисел), ваш список различий не принесет вам никакой эффективности - целое число - это целое число из POV времени выполнения Python, поэтому ваш пример " diff "список [-1, -1, 1, 2] будет занимать столько же памяти, сколько исходный список [1005, 1004, 1003, 1004, 1006].

Answer 6

Как предложил mshsayem, используйте списочные выражения - они, как правило, быстрее, чем для циклов или карты / лямбды (в соответствии с книгой Марка Лутца «Learning Python»).

Если вы действительно хотите использовать более FP-ишное решение, правильной функцией будет «сканирование», которое [я считаю] не реализовано в Python, поэтому вам придется реализовать его самостоятельно (что не сложно задача).

«Сканирование» - это, по сути, сокращение, но вместо сокращения списка до одного значения он сохраняет результат каждой «итерации» в новом списке.

Если вы реализовали это, вы можете сделать что-то вроде:

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

Answer 7

Нет комментариев по поводу производительности, но вы можете использовать уменьшить здесь.

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

получает то, что вы хотите.

Answer 8

Я не знаю, как вы рассуждали о сохранении целых чисел в виде различий - 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 ().

Answer 9

Хотя я не понимаю, почему это должно быть более эффективным, я уверен, что цикл for даст лучшую производительность:

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