Python - Наиболее эффективный способ сортировки массива для поиска в нем

Question

У меня есть очень большой Numpy массив, который выглядит следующим образом (первые 5 статей):

[[ 1. 0.01 0.02 0.6 0.01 0.5 0.01 0.5 0.5 0.5 ] 
[ 0.5 0.01 0.01 0.6 0.01 0.5 0.5 0.5 0.5 0.6 ] 
[ 0.6 0.01 0.5 0.5 0.5 0.5 0.7 0.01 0.01 0. ] 
[ 0.01 0.5 0.8 0.02 0.02 0.81 0.01 0.77 0.02 0.01] 
[ 0.5 0.02 0.5 0. 0.5 0.5 0.01 0.6 0.01 0. ]] 

Я поиск этого массива для конкретных последовательностей, также 10 значений. Итак, я сохраняю входящие последовательности после специального правила, просто 0 1 2 3 ... и тот же я ищу этот массив. Это мой метод поиска (silo_arrays [] [] является массивом выше, array_pattern [] является 1D Numpy 10 значений длиной массива, для которого я искать silo_arrays):

new_pattern=True 
    for z in range(0, self.silo_arrays_c): 
    eq_rate = 0 
    for y in range(0, self.length): 
     if(self.silo_arrays[z][y] != array_pattern[y]): 
      break 
     else: 
      eq_rate += 1 

    if(eq_rate == self.length): 
    new_pattern = False 
    break 

Это занимает около 0.006257s, если это silo_arrays - это что-то вроде 1585 записей. Есть ли идеи о том, как ускорить этот поиск от Сортировка или Изменения в конструкции? Спасибо за поддержку :)

Answer 1

Когда речь идет о данных-оптимизации вы часто дело с компромиссами, а не общим ускорением.

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

Одним из популярных алгоритмов является реализация двоичного поиска. В случае, если вы не знакомы с понятием:

Учитывая упорядоченный числовой список L и численный v, вы должны проверить, если v in L. Вы можете сделать это, разделив список пополам, а затем сравните среднее значение этих двух интервалов с вашим значением. v. Предполагая, что в порядке возрастания вы выберете интервал I на основе следующих правил: if v < L[middleindex]: I = lower_half else I = upper_half Затем вы продолжите поиск, повторяя. Таким образом вы сократите пространство поиска до минимума.

Чтобы использовать Binary Search в вашем проекте, вам необходимо отсортировать массивы при их вставке в массив. Значения для сравнения будут вашими элементами массивов в порядке убывания. Таким образом, вы, скорее всего, увеличите скорость поиска.

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

Отказ от форматирования, я нахожусь на мобильном телефоне.