Точка безубыточности оптимизации: многократно повторяйте набор или конвертируйте в список в первую очередь?

Вот о чем я всегда задумывался. Я поставил вопрос для Python, но также приветствовал бы ответы, которые касаются стандартных библиотек в Java и C ++.

Предположим, у вас есть список Python, называемый «my_list», и вы хотите перебирать его уникальные элементы. Существует два естественных подхода:

#iterate over set for x in set(my_list): do_something(x) 

или

 #list to set to list for x in list(set(my_list)): do_something(x) 

Напряжение заключается в том, что итерация по списку быстрее, чем повторение по набору, но для преобразования набора в список требуется время. Я предполагаю, что ответ на этот вопрос будет зависеть от ряда факторов, таких как:

  • Сколько раз нам нужно повторять?
  • Насколько велик первоначальный список?
  • Сколько повторений в исходном списке мы должны ожидать?

Поэтому я предполагаю, что я искал эмпирическое правило формы «Если в списке есть x много элементов, каждый элемент повторяется не более, чем y раз, и вам нужно только повторить z раз, тогда вы должны перебирать множество, иначе вы должен преобразовать его в список ».

One Solution collect form web for “Точка безубыточности оптимизации: многократно повторяйте набор или конвертируйте в список в первую очередь?”

Я ищу эмпирическое правило …

Практическое правило

Вот лучшее правило для написания оптимального Python: используйте как можно меньше промежуточных шагов и избегайте материализации ненужных структур данных.

Применительно к этому вопросу: наборы являются итерабельными. Не конвертируйте их в другую структуру данных, чтобы перебирать их. Доверьте Python, чтобы узнать самый быстрый способ перебора множеств. Если бы быстрее преобразовать их в списки, Python сделает это.

При оптимизации:

Не пытайтесь преждевременно оптимизировать, добавляя сложность вашей программе. Если ваша программа занимает слишком много времени, профилируйте ее, а затем оптимизируйте узкие места. Если вы используете Python, вы, вероятно, больше озабочены временем разработки, чем тем, как долго ваша программа запускается.

демонстрация

В Python 2.7:

 import collections import timeit blackhole = collections.deque(maxlen=0).extend s = set(xrange(10000)) 

Мы видим, что при больших n проще:

 >>> timeit.timeit(lambda: blackhole(s)) 108.87403416633606 >>> timeit.timeit(lambda: blackhole(list(s))) 189.0135440826416 

И для меньшего n такое же соотношение:

 >>> s = set(xrange(10)) >>> timeit.timeit(lambda: blackhole(s)) 0.2969839572906494 >>> timeit.timeit(lambda: blackhole(list(s))) 0.630713939666748 

Да, списки повторяются быстрее, чем наборы (попробуйте на своем интерпретаторе Python):

 l = list(s) timeit.repeat(lambda: blackhole(l)) 

Но это не значит, что вы должны конвертировать множества в списки только для итерации.

Анализ безубыточности

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

Возможно, что, внося инвестиции в сложность и принимая на себя больший риск ошибок из большего количества строк кода, вы можете получить хороший выигрыш. Этот анализ продемонстрирует точку безубыточности в этом вопросе. Я не знаю, сколько еще производительности вам нужно будет заплатить за большие риски и время разработки, но это скажет вам, в какой момент вы можете начать платить по отношению к этим:

 import collections import timeit import pandas as pd BLACKHOLE = collections.deque(maxlen=0).extend SET = set(range(1000000)) def iterate(n, iterable): for _ in range(n): BLACKHOLE(iterable) def list_iterate(n, iterable): l = list(iterable) for _ in range(n): BLACKHOLE(l) columns = ('ConvertList', 'n', 'seconds') def main(): results = {c: [] for c in columns} for n in range(21): for fn in (iterate, list_iterate): time = min(timeit.repeat((lambda: fn(n, SET)), number=10)) results['ConvertList'].append(fn.__name__) results['n'].append(n) results['seconds'].append(time) df = pd.DataFrame(results) df2 = df.pivot('n', 'ConvertList') df2.plot() import pylab pylab.show() 

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

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

введите описание изображения здесь

Эти результаты были созданы с помощью Python 2.7 от Anaconda от терминала Ubuntu 14.04. Вы можете получать разные результаты с различными реализациями и версиями.


Обеспокоенность

Меня беспокоит то, что наборы изменяемы, а списки изменяемы. Набор запретит вам изменять его во время итерации по нему, но список, созданный из этого набора, не будет:

 >>> s = set('abc') >>> for e in s: ... s.add(e + e.upper()) ... Traceback (most recent call last): File "<stdin>", line 1, in <module> RuntimeError: Set changed size during iteration 

Если вы измените свой набор во время итерации по списку производных, вы не получите сообщение об ошибке, чтобы сообщить вам, что вы это сделали.

 >>> for e in list(s): ... s.add(e + e.upper()) 

Вот почему я также предложил вместо этого использовать фризонаты и кортежи. Это будет встроенная защита от семантически неправильного изменения ваших данных.

 >>> s = frozenset('abc') >>> t_s = tuple(s) >>> for e in t_s: ... s.add(e + e.upper()) ... Traceback (most recent call last): File "<stdin>", line 2, in <module> AttributeError: 'frozenset' object has no attribute 'add' 

В конце концов, вы должны доверять себе, чтобы получить правильный алгоритм. Часто мне говорят, что я дал хороший совет, когда предупреждаю новых пользователей Python об этих вещах. Они узнали, что это хороший совет, потому что они не слушали сначала, и обнаружили, что это создало ненужную сложность, сложности и возникающие проблемы. Но есть также такие вещи, как логическая правильность, что вы будете сами себя винить, если вы не поправляетесь. Минимизация вещей, которые могут пойти не так, – это преимущество, которое обычно стоит компромисс производительности. И снова, если производительность (а не правильность или скорость разработки) была главной проблемой при решении этого проекта, вы бы не использовали Python.

  • Ruby hash эквивалент Python dict setdefault
  • Как Python может иметь несколько ключей с одинаковым хэшем?
  • Предотвращение отправки нескольких форм в Django
  • Где я могу найти источник или алгоритм функции hash () Python?
  • Как определить __hash__, когда объект может быть равен различным типам объектов?
  • Проверьте, изменился ли огромный список в python
  • Хеширование кортежа в Python, вызывающее разные результаты в разных системах
  • Короткий алфавитно-цифровой хэш-код Python с минимальными коллизиями
  • Python - лучший язык программирования в мире.