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

Question

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

например:

 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

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

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

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

Answer 2

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

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

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

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

Если сохраняемые числа не очень велики (т. е. не переполняют целое число и не требуют больших чисел), ваш список различий не принесет вам никакой эффективности - целое число является целым числом из POV среды выполнения Python, поэтому ваш пример списка «diff» из [-1, -1, 1, 2] будет занимать столько же памяти, сколько исходный список [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

Теперь попробуйте:

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

Вы можете очистить пример, чтобы стартовая переменная не была глобальной.Он просто не может быть локальным для функции mod_start.

Редактировать: Вам не нужно использовать понимание генератора, чтобы получить генератор.Вы также можете использовать функцию-генератор с выражением доходности, как это сделал THC4k.Это позволяет избежать проблемы с областью начальной переменной и, вероятно, немного чище.Вы также можете в любой момент получить список из генератора, передав его встроенной функции list().

Answer 9

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

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

дает вам то, что вы хотите.