Нужен быстрый способ подсчета и суммирования итерации за один проход

Ответ 1

Спасибо за все замечательные ответы, но я решил использовать мою оригинальную функцию count_and_sum, называемую следующим образом:

>>> cc, cs = count_and_sum(c.width for c in cols if not c.hide) 

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

Ответ 2

Использование комплексных чисел

z = [1, 2, 4, 5, 6]
y = sum(x + 1j for x in z)
sum_z, count_z = y.real, int(y.imag)
print sum_z, count_z
18.0 5

Ответ 3

Я не знаю о скорости, но это довольно красиво:

>>> from itertools import accumulate
>>> it = range(10)
>>> max(enumerate(accumulate(it), 1))
(10, 45)

Ответ 4

Адаптация ответа DSM. используя deque(... maxlen=1), чтобы сохранить использование памяти.

import itertools 
from collections import deque 
deque(enumerate(itertools.accumulate(x), 1), maxlen=1)

код времени в ipython:

import itertools , random
from collections import deque 

def count_and_sum(iter):
     count = sum = 0
     for item in iter:
         count += 1
         sum += item
     return count, sum

X = [random.randint(0, 10) for _ in range(10**7)]
%timeit count_and_sum(X)
%timeit deque(enumerate(itertools.accumulate(X), 1), maxlen=1)
%timeit (max(enumerate(itertools.accumulate(X), 1)))

: теперь быстрее, чем метод OP

1 loops, best of 3: 1.08 s per loop
1 loops, best of 3: 659 ms per loop
1 loops, best of 3: 1.19 s per loop

Ответ 5

Вот некоторые данные синхронизации, которые могут представлять интерес:

import timeit

setup = '''
import random, functools, itertools, collections

x = [random.randint(0, 10) for _ in range(10**5)]

def count_and_sum(it):
    c, s = 0, 0
    for i in it:
        c += 1
        s += i
    return c, s

def two_pass(it):
    return sum(i for i in it), sum(True for i in it)

def functional(it):
    return functools.reduce(lambda pair, x: (pair[0]+1, pair[1]+x), it, [0, 0])

def accumulator(it):
    return max(enumerate(itertools.accumulate(it), 1))

def complex(it):
    cpx = sum(x + 1j for x in it)
    return cpx.real, int(cpx.imag)

def dequed(it):
    return collections.deque(enumerate(itertools.accumulate(it), 1), maxlen=1)

'''

number = 100
for stmt in ['count_and_sum(x)',
             'two_pass(x)',
             'functional(x)',
             'accumulator(x)',
             'complex(x)',
             'dequed(x)']:
    print('{:.4}'.format(timeit.timeit(stmt=stmt, setup=setup, number=number)))

Результат:

3.404 # OP one-pass method
3.833 # OP two-pass method
8.405 # Timothy Shields fold method
3.892 # DSM accumulate-based method
4.946 # 1_CR complex-number method
2.002 # M4rtini deque-based modification of DSM method

Учитывая эти результаты, я не совсем уверен, как OP видит 100-кратное замедление с помощью однопроходного метода. Даже если данные выглядят радикально отличными от списка случайных целых чисел, этого просто не должно быть.

Кроме того, решение M4rtini выглядит как явный победитель.

Чтобы уточнить, эти результаты приведены в CPython 3.2.3. Для сравнения с PyPy3 см. ответ James_pic, который показывает некоторые серьезные выгоды от компиляции JIT для некоторых методов (также упоминается в a комментарий от M4rtini.

Ответ 6

В качестве ответа на вопрос senshin следует отметить, что различия в производительности в значительной степени обусловлены причудами в реализации CPython, которые делают некоторые методы медленнее, чем другие (например, циклы for относительно медленны в CPython). Я подумал, что было бы интересно попробовать один и тот же тест в PyPy (используя PyPy3 2.1 beta), который имеет разные характеристики производительности. В PyPy результаты:

0.6227 # OP one-pass method
0.8714 # OP two-pass method
1.033 # Timothy Shields fold method
6.354 # DSM accumulate-based method
1.287 # 1_CR complex-number method
3.857 # M4rtini deque-based modification of DSM method

В этом случае метод однопроходного OP быстрее. Это имеет смысл, поскольку это, возможно, самый простой (по крайней мере, с точки зрения компилятора), и PyPy может устранить многие из накладных расходов путем встраивания вызовов методов, которые CPython не может.

Для сравнения, CPython 3.3.2 на моем компьютере дает следующее:

1.651 # OP one-pass method
1.825 # OP two-pass method
3.258 # Timothy Shields fold method
1.684 # DSM accumulate-based method
3.072 # 1_CR complex-number method
1.191 # M4rtini deque-based modification of DSM method

Ответ 7

Вы можете сохранить счет внутри суммы с помощью трюков, подобных этому

>>> from itertools import count
>>> cnt = count()
>>> sum((next(cnt), x)[1] for x in range(10) if x%2)
25
>>> next(cnt)
5

Но, вероятно, будет более читаемым просто использовать цикл for

Ответ 8

Вы можете использовать это:

from itertools import count

lst = range(10)
c = count(1)
tot = sum(next(c) and x for x in lst if x % 2)
n = next(c)-1
print(n, tot)

# 5 25

Это своего рода взлом, но он отлично работает.

Ответ 9

Я не знаю, что синтаксис Python отключен, но вы можете использовать сгиб. Что-то вроде этого:

(count, total) = fold((0, 0), lambda pair, x: (pair[0] + 1, pair[1] + x))

Идея состоит в том, чтобы использовать семя (0,0), а затем на каждом шаге добавить 1 к первому компоненту и текущему числу ко второму компоненту.

Для сравнения вы можете реализовать sum как сгиб следующим образом:

total = fold(0, lambda t, x: t + x)

Ответ 10

1_CR комплексное решение - симпатичное, но слишком хакерское. Причина, по которой он работает, состоит в том, что комплексное число является 2-кортежем, который суммируется по-разному. То же самое относится к массивам numpy, и я думаю, что это немного чище, чтобы использовать их:

import numpy as np
z = [1, 2, 4, 5, 6]
y = sum(np.array([x, 1]) for x in z)
sum_z, count_z = y[0], y[1]
print sum_z, count_z
18 5

Ответ 11

Что-то еще нужно учитывать: если можно определить минимально возможный счет, мы можем позволить эффективному встроенному sum выполнить часть работы:

from itertools import islice

def count_and_sum(iterable):
    # insert favorite implementation here

def count_and_sum_with_min_count(iterable, min_count):
    iterator = iter(iterable)
    slice_sum = sum(islice(iterator, None, min_count))
    rest_count, rest_sum = count_and_sum(iterator)
    return min_count + rest_count, slice_sum + rest_sum

Например, используя метод deque с последовательностью из 10000000 элементов и min_count 5000000, результаты синхронизации:

count_and_sum: 1.03
count_and_sum_with_min_count: 0.63

Ответ 12

Как насчет этого? Кажется, что это работает.

from functools import reduce

class Column:
    def __init__(self, width, hide):
        self.width = width
        self.hide = hide

lst = [Column(10, False), Column(100, False), Column(1000, True), Column(10000, False)]

print(reduce(lambda acc, col: Column(col.width + acc.width, False) if not col.hide else acc, lst, Column(0, False)).width)

Ответ 13

Вам может понадобиться только сумма и счет сегодня, но кто знает, что вам нужно завтра!

Здесь легко расширяемое решение:

def fold_parallel(itr, **fs):
    res = {
        k: zero for k, (zero, f) in fs.items()
    }

    for x in itr:
        for k, (_, f) in fs.items():
            res[k] = f(res[k], x)

    return res

from operator import add

print(fold_parallel([1, 2, 3],
    count = (0, lambda a, b: a + 1),
    sum = (0, add),
))
# {'count': 3, 'sum': 6}