Это довольно концептуальный вопрос, но я надеялся получить хороший совет по этому вопросу. Я занимаюсь программированием с массивами ( NumPy ); Мне часто приходится сопоставлять элементы в двух или более массивах разных размеров, и первое, на что я обращаюсь - это цикл for или, что еще хуже, вложенный цикл for. Я хочу как можно больше избегать циклов for, потому что они медленные (по крайней мере, в Python).
Я знаю, что для многих вещей с NumPy есть предопределенные команды, которые мне просто нужно исследовать, но есть ли у вас (как у более опытных программистов) общий мыслительный процесс, который приходит на ум, когда вам приходится что-то повторять?
Поэтому у меня часто бывает что-то подобное, что ужасно, и я хочу этого избежать:
small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])
for i in range(len(small_array)):
for p in range(len(big_array)):
if small_array[i] == big_array[p]:
print "This item is matched: ", small_array[i]
Я знаю, что для достижения этой цели, в частности, существует множество различных способов, но меня интересует общий метод мышления, если он существует.
I want to avoid for-loops as much as possible because they are slow (at least in Python).
Похоже, вы решаете не ту проблему здесь. Если вам нужно перебрать что-то, вам нужно перебрать что-то; Вы получите аналогичный удар по производительности независимо от того, какую конструкцию Python вы используете. Если ваш код медленный, это не потому, что у вас естьfor
циклы; это потому, что вы выполняете ненужную работу или работу на стороне Python, что может быть сделано на стороне C. В вашем примере вы делаете дополнительную работу; Вы могли бы сделать это с одним циклом вместо двух.Ответы:
Это общая концептуальная трудность при обучении эффективному использованию NumPy . Обычно обработка данных в Python лучше всего выражается в терминах итераторов , чтобы сохранить низкое использование памяти, чтобы максимизировать возможности параллелизма с системой ввода / вывода, а также обеспечить повторное использование и комбинацию частей алгоритмов.
Но NumPy переворачивает все это наизнанку: наилучший подход состоит в том, чтобы выразить алгоритм в виде последовательности операций с целым массивом , чтобы минимизировать количество времени, затрачиваемого на медленный интерпретатор Python, и максимизировать количество времени, затрачиваемого на процедуры быстрой компиляции NumPy.
Вот общий подход, который я использую:
Сохраняйте исходную версию функции (которая, как вы уверены, является правильной), чтобы вы могли проверить ее на соответствие улучшенным версиям как на правильность, так и на скорость.
Работа изнутри: то есть начните с самого внутреннего цикла и посмотрите, можно ли векторизовать; затем, когда вы это сделаете, выйдите на один уровень и продолжайте.
Потратьте много времени на чтение документации NumPy . Там много функций и операций, и они не всегда блестяще названы, поэтому стоит их узнать. В частности, если вы обнаружите, что думаете: «Если бы существовала функция, которая выполняла то-то и то-то», тогда стоит потратить десять минут на ее поиск. Обычно это где-то там.
Там нет замены для практики, поэтому я собираюсь дать вам несколько примеров проблем. Цель каждой проблемы - переписать функцию так, чтобы она была полностью векторизована : то есть, чтобы она состояла из последовательности операций NumPy над целыми массивами, без собственных циклов Python (без операторов
for
илиwhile
операторов, без итераторов или пониманий).Проблема 1
Проблема 2
Проблема 3
Спойлеры ниже. Вы получите гораздо лучшие результаты, если сами попробуете, прежде чем смотреть на мои решения!
Ответ 1
Ответ 2
Ответ 3
источник
list
Чтобы ускорить процесс, вы должны прочитать свои структуры данных и использовать те, которые вам подходят.
Для нетривиальных размеров малого массива и большого массива (скажем, small = 100 элементов и big = 10.000 элементов) один из способов сделать это - отсортировать небольшой массив, затем выполнить итерацию по большому массиву и использовать двоичный поиск для поиска подходящих элементов. в небольшом массиве.
Это сделало бы максимальную сложность по времени O (N log N) (а для маленьких маленьких массивов и очень больших больших массивов это ближе к O (N)), где ваше решение с вложенным циклом равно O (N ^ 2)
Тем не мение. какие структуры данных являются наиболее эффективными, в значительной степени зависит от актуальной проблемы.
источник
Вы можете использовать словарь, чтобы значительно оптимизировать производительность
Это еще один пример:
источник