Python: оптимизация цикла

Question

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

Я работаю над скриптом, который вычисляет radial distribution function между множеством N = 10000 (десять тысяч) точек в трехмерном поле с периодическими граничными условиями (PBC). В принципе, у меня есть файл из 10000 строк, выполненных так:

0.037827 0.127853 -0.481895 
12.056849 -12.100216 1.607448 
10.594823 1.937731 -9.527205 
-5.333775 -2.345856 -9.217283 
-5.772468 -10.625633 13.097802 
-5.290887 12.135528 -0.143371 
0.250986 7.155687 2.813220 

который представляет координаты N точек. Я должен вычислить расстояние между каждыми двумя точками (поэтому я должен рассмотреть все комбинации из 49995000 из 2 элементов), а затем выполнить некоторую операцию над ним.

Конечно, наиболее облагаемая налогом часть программы представляет собой цикл по комбинациям 49995000.

Моя текущая функция выглядит следующим образом:

g=[0 for i in range(Nbins)] 

for i in range(Nparticles): 
    for j in range(i+1,Nparticles): 

     #compute distance and apply PBC 
     dx=coors[i][0]-coors[j][0] 
     if(dx>halfSide): 
      dx-=boxSide 
     elif(dx<-halfSide): 
      dx+=boxSide 

     dy=coors[i][1]-coors[j][1] 
     if(dy>halfSide): 
      dy-=boxSide 
     elif(dy<-halfSide): 
      dy+=boxSide 

     dz=coors[i][2]-coors[j][2] 
     if(dz>halfSide): 
      dz-=boxSide 
     elif(dz<-halfSide): 
      dz+=boxSide 

     d2=dx**2+dy**2+dz**2 

     if(d2<(cutoff*boxSide)**2): 
      g[int(sqrt(d2)/dr)]+=2 

Примечание: coors вложенный массив, созданный с помощью loadtxt() на файл данных.

Я в основном переработаны функции, которые я использовал в другой программе, написанной на C.

Я не использую itertool.combinations(), потому что я заметил, что программа работает немного медленнее, если я использую его по какой-то причине (одна итерация около 111 с, пока он работает около 106 с этой реализацией).

Эта функция занимает около 106 с, что ужасно, учитывая, что мне приходится анализировать около 500 конфигурационных файлов.

Теперь, мой вопрос:: Есть ли общий способ сделать такие циклы быстрее работать с помощью Python? Я предполагаю, что соответствующий C-код будет быстрее, но я хотел бы придерживаться Python, потому что он намного проще в использовании.

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

PS Пожалуйста, постарайтесь как можно больше объяснить код в своих ответах (если вы напишите), потому что я новичок в Python.

Update

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

Я также хочу сказать, что с помощью Cython (я следил за этим tutorial) мне удалось немного ускорить все, как ожидалось (77 с, где до этого было 106).

Answer 1

Если память не является проблемой (и, вероятно, не указано, что фактический объем данных не будет отличаться от того, что вы делаете сейчас), вы можете использовать для выполнения математики для вас и поместить все в массив NxN (около 800 МБ при 8 байтах/float).

Учитывая операции код пытается сделать, я не думаю, что вам нужно любые петли вне numpy:

g = numpy.zeros((Nbins,)) 
coors = numpy.array(coors) 

#compute distance and apply PBC 
dx = numpy.subtract.outer(coors[:, 0], coors[:, 0]) 
dx[dx < -halfSide] += boxSide 
dx[dx > halfSide)] -= boxSide 
dy = numpy.subtract.outer(coors[:, 1], coors[:, 1]) 
dy[dy < -halfSide] += boxSide 
dy[dy > halfSide] -= boxSide 
dz = numpy.subtract.outer(coors[:, 2], coors[:, 2]) 
dz[dz < -halfSide] += boxSide 
dz[dz > halfSide] -= boxSide 

d2=dx**2 + dy**2 + dz**2 
# Avoid counting diagonal elements: inf would do as well as nan 
numpy.fill_diagonal(d2, numpy.nan) 

# This is the same length as the number of times the 
# if-statement in the loops would have triggered 
cond = numpy.sqrt(d2[d2 < (cutoff*boxSide)**2])/dr 
# See http://stackoverflow.com/a/24100418/2988730 
np.add.at(g, cond.astype(numpy.int_), 2) 

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

Библиотеки, такие как numpy и dynd, предоставляют операции, выполняющие петли, которые вы хотите «под капотом», обычно обходя бухгалтерию с реализацией C. Преимущество заключается в том, что вы можете выполнять бухгалтерию на уровне Python один раз для каждого огромного массива, а затем заниматься обработкой необработанных чисел вместо того, чтобы иметь дело с объектами оболочки Python (числа - это полномасштабные объекты на Python, нет примитивных типов).

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

Answer 2

У вас есть интересная проблема. Существуют некоторые общие рекомендации для высокопроизводительных Python; они предназначены для Python2, но в большинстве случаев они должны нести Python3.

• Профилируйте свой код. Использование% timeit и %% timeit на jupyter/ipython выполняется быстро и быстро для интерактивных сеансов, но cProfile и line_profiler ценны для поиска узких мест.
• Это ссылка на короткое эссе, которое охватывает основы документации Python, которые я нашел полезной: https://www.python.org/doc/essays/list2str
• Numpy - отличный пакет для векторизованных операций. Обратите внимание, что векторы numpy, как правило, работают медленнее, чем списки небольшого размера, но экономия памяти огромна. При выполнении многомерных массивов коэффициент усиления значительно превышает списки. Кроме того, если вы начнете наблюдать за промахами кеша и ошибками страниц с помощью чистого Python, то преимущество numpy будет еще больше.
• Недавно я использовал Cython с большим успехом, где numpy/scipy не совсем сократили его встроенными функциями.

• Ознакомьтесь с scipy, который имеет огромную библиотеку функций для научных вычислений. Есть много возможностей для изучения; например, функция scipy.spatial.pdist вычисляет быстрые парные расстояния nC2. В тестовом столбце ниже, 10k пунктов попарно расстояния завершены в 375 мс. 100 тыс. Элементов, вероятно, сломают мою машину, но без рефакторинга.

  import numpy as np 
  from scipy.spatial.distance import pdist 
  xyz_list = np.random.rand(10000, 3) 
  xyz_list 
  Out[2]: 
  array([[ 0.95763306, 0.47458207, 0.24051024], 
       [ 0.48429121, 0.12201472, 0.80701931], 
       [ 0.26035835, 0.76394588, 0.7832222 ], 
       ..., 
       [ 0.07835084, 0.8775841 , 0.20906537], 
       [ 0.73248369, 0.60908474, 0.57163023], 
       [ 0.68945879, 0.19393467, 0.23771904]]) 
  In [10]: %timeit xyz_pairwise = pdist(xyz_list) 
  1 loop, best of 3: 375 ms per loop 
  
  In [12]: xyz_pairwise = pdist(xyz_list) 
  In [13]: len(xyz_pairwise) 
  Out[13]: 49995000 
  

С Днем изучения!