Ускорьте вложенные циклы Python с помощью условных операторов

Я конвертирую код из MATLAB в python, чтобы ускорить выполнение простых операций. Я написал функцию, которая содержит вложенные циклы и условный оператор; цель цикла - вернуть список индексов для ближайших элементов в массиве x по сравнению с массивом y. Я сравниваю в порядке 1e5 элементов, выполнение которых занимает около 30 секунд. Любая помощь в ускорении этого процесса будет принята с благодарностью! У меня был частичный успех с использованием автоматического компилятора numba-pro:

@autojit()
def find_nearest(x,y,idx):
    idx_old = 0
    rng1 = range(y.shape[0])
    rng2 = range(x.shape[0])
    for i in rng1:
        prev = abs(x[idx_old]-y[i])
        for j in rng2:
            if abs(x[j]-y[i]) < prev:
                prev = abs(x[j]-y[i])
                idx_old = j
        idx[i] = idx_old
    return idx

Извините за то, что я такой нуб, я новичок в python!


numpy python-2.7 conditional-statements performance numba
person Chris Church    schedule 20.05.2015    source источник
comment
Не могли бы вы обновить свой сценарий, включив в него примеры входных данных для find_nearest, просто так?   -  person JoshAdel    schedule 20.05.2015
comment
Например, x = np.array([1.1,2.3,5.9,8.5]), y = np.array([0.2, 5.5, 12]) и idx = np.zeros(np.shape(y)) должны возвращать idx = [0,2,3] (индексы ближайших элементов в x к элементам в y. В MATLAB я использую knnsearch для выполнения этого, и в моем большом наборе данных это занимает примерно 2,5 с, тогда как моя реализация занимает около 30 с , Входные массивы не обязательно должны быть отсортированы в каком-либо определенном порядке. Спасибо за внимание!   -  person Chris Church    schedule 21.05.2015
comment
Я попытался использовать реализацию k-ближайших соседей sci-kitlearn, однако она возвращает функцию, обученную на наборе данных; и обучение на моем полном наборе данных просто невозможно. Мой поисковый домен содержит 1023848 элементов, и я пытаюсь найти в нем 12325 ближайших элементов.   -  person Chris Church    schedule 21.05.2015

Ответы (2)


arrow_upward
4
arrow_downward

В вашем коде Numba нет ничего плохого, за исключением того, что алгоритм не настолько эффективен, насколько это возможно. Гораздо лучше отсортировать массив x и выполнить двоичный поиск, очень похожий на этот ответ, а также этот ответ:

def find_nearest(x, y):
    indices = np.argsort(x)

    loc = np.searchsorted(x[indices], y)
    right = indices.take(loc, mode='clip')
    left = indices.take(loc-1, mode='clip')

    return np.where(abs(y-x[left]) < abs(y-x[right]), left, right)

На моем ПК это примерно в 80 раз быстрее, чем даже подход KDTree для x и y, имеющих 106 и 105 элементов соответственно. Около двух третей времени тратится на argsort-обработку массива, поэтому я не думаю, что вы можете много выиграть с помощью Numba.

person Community    schedule 23.05.2015
comment
Большое спасибо за Ваш ответ; Я смог реализовать ваш код. В моем наборе данных он работал примерно в 270 раз быстрее (находя около 1e4 индексов в наборе около 1e6 элементов). Не могли бы вы предложить учебник/статью/веб-страницу, которая показалась вам полезной при обучении реализации более эффективного кода на Python? Я рассмотрел аналогичные ответы, которые вы предложили. Всегда ли операции с индексами намного быстрее? - person Chris Church; 25.05.2015
comment
@Chris Я научился кодировать более эффективный Python, в основном следуя тегу [Numpy] на этом сайте и экспериментируя / методом проб и ошибок. Не могли бы вы объяснить немного подробнее, что вы имеете в виду под «Всегда ли индексированные операции намного быстрее?» - person ; 25.05.2015
comment
Под индексированными операциями я подразумеваю функции, которые возвращают логические/индексные массивы для дальнейших операций по строке. Первоначально я пытался превратить мою функцию find_nearest в одну строку матричных и векторных операций; Однако я столкнулся с MemoryError при попытке запустить его на наборах данных значительного размера. - person Chris Church; 25.05.2015
comment
@ Крис А, понятно. Нет, речь идет не об операциях индексации и матричных/векторных операциях. Ваш исходный алгоритм имеет сложность O(m*n), где m и n — длины x и y. Вероятно, вы также создавали массив размером m*n (очень большой). С моим кодом сложность составляет O ((m+n)log(m)) и дополнительное использование памяти в порядке O (m+n) (я думаю ... не уверен насчет сортировки). - person ; 26.05.2015

arrow_upward
1
arrow_downward

Я нашел временное решение своей проблемы. Внедрив kdtree из scipy.spatial, я смог сократить время выполнения с 32 до чуть менее 10 с. Это все еще в четыре раза медленнее, чем алгоритм knnsearch MATLAB; и понимание того, как ускорить циклы с помощью условных операторов, по-прежнему важно. Но на данный момент эта пересмотренная реализация работает быстрее:

from scipy import spatial
from numpy import matrix

tree = spatial.KDTree(matrix(x).T)
(_, idxx) = tree.query(matrix(y).T)

Массивы x и y были в плоском формате 1d; дерево требовало, чтобы запросы были в форме вектора-столбца.

Мы будем очень признательны за любые предложения по улучшению времени выполнения оригинальной реализации!

person Chris Church    schedule 21.05.2015