Какой подход лучше рассчитать длину итератора?

Question

В чем разница между len(list(iterator)) и sum(1 for _ in iterator)? Впоследствии, какой из них лучше всего использовать для вычисления длины итератора?

Answer 1

Первый использует пространство O (n), потому что он должен построить список. Второй использует пространство O (1), потому что ему не нужно запоминать элемент после обновления промежуточной суммы.

Ни один из них не очень полезен, поскольку вы отбросили каждый элемент из оригинала итератор, не глядя ни на один из них. Остается узнать, как долго итератор был . Предполагая, что вас это устраивает, пробел O (1) лучше, чем O (n).

Answer 2

Хотя я не могу спорить с logi c Чепнера, быстрый тест, кажется, дает противоположный вывод, по крайней мере, с точки зрения времени.

import time

def option1(a):
    return len(list(a))

def option2(b):
    return sum(1 for _ in b)

start = time.time()
for i in range(20000):
    a0 = range(1, 10000)
    a = option1(map(lambda x: x + 1, a0))
end = time.time()
print("Option 1:", end - start, "seconds")

start = time.time()
for i in range(20000):
    a0 = range(1, 10000)
    a = option2(map(lambda x: x + 1, a0))
end = time.time()
print("Option 2:", end - start, "seconds")

Результат:

Option 1: 14.580924987792969 seconds
Option 2: 19.70468544960022 seconds

Итак, по крайней мере, с точки зрения времени, второй вариант на 35% медленнее (когда я увеличиваю длину итераций, первый вариант, кажется, масштабируется немного хуже, но не намного). Также стоит отметить, что прямое императивное решение без генераторов и промежуточных списков, то есть

def option3(c):
    i = 0
    for _ in c:
        i += 1
    return i

, работает лишь немного лучше, чем вариант 2, давая 18,61347 секунд на тех же входах, что и в приведенном выше коде.

Таким образом, похоже, что форсирование списка на самом деле несколько быстрее, если у вас есть место для создания промежуточного списка. Я протестировал его с итерациями до 50 000 элементов, и он по-прежнему превосходит решение на основе генератора.