Более быстрый способ найти следующее наибольшее значение в массиве

Question

Я пытаюсь улучшить время выполнения моего кода данных. Правильно ли мое мнение?

У меня есть следующий код, чтобы найти первое значение в столбце 1, которое больше value и имеет более высокий индекс, чем оно (index_value=n)

new_index=(df[n:,1] > value).argmax()

Мой вопрос таков: аргумент argmax () создаст полный список с Trues и False тогда, и только тогда он найдет первый случай и вернет мой ожидаемый индекс.

Есть ли способ улучшить этот код? т.е. прекратить создание списка после того, как найден первый True.

Answer 1

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

# Proposed solutions
import numpy as np
from numba import njit

# @piRSquared's soln
@njit
def find_first_gt(a, n, value):
    while a[n] <= value:
        n += 1
    return n

# @Ehsan's soln
def numpy_argmax(a, n , value):
    return np.argmax(a[n:] > value)

Использование пакета benchit (несколько инструментов для сравнения, собранные вместе; отказ от ответственности: я его автор) для сравнения предлагаемых решений.

Время и ускорения -

# Benchmark
a = np.arange(1000_000)
n = 0

import benchit
funcs = [find_first_gt, numpy_argmax]
vs = np.linspace(0, len(a)-1, num=20, endpoint=True).astype(int)
inputs = [(a,0,v) for v in vs]
t = benchit.timings(funcs, inputs, multivar=True, input_name='Position of value')
t.plot(logy=False, logx=False, savepath='plot.png')
t.speedups(ref_func_by_index=1).plot('Speedup_with_numba.png')

Если вас интересуют точные цифры ускорения -

In [12]: t.speedups(ref_func_by_index=1)
Out[12]: 
Functions          find_first_gt  Ref:numpy_argmax
Position of value                                 
0                    2103.548010               1.0
52631                  22.053699               1.0
105263                 11.109615               1.0
157894                  7.541725               1.0
210526                  5.640514               1.0
263157                  4.407300               1.0
315789                  3.642989               1.0
368420                  3.028726               1.0
421052                  2.543713               1.0
473683                  2.201336               1.0
526315                  1.931540               1.0
578946                  1.692138               1.0
631578                  1.536912               1.0
684209                  1.455065               1.0
736841                  1.357728               1.0
789472                  1.248716               1.0
842104                  1.176199               1.0
894735                  1.062174               1.0
947367                  1.043791               1.0
999999                  0.983419               1.0

Вывод: почти во всех условиях numba делает хорошую работу, если только вы не знаете, что value находится в самом дальнем конце или в тупике. схемы кеширования не устраивают вас.

Answer 2

IIU C и заимствование @ по предложению Дивакара

from numba import njit

@njit
def find_first_gt(a, n, value):
    while a[n] <= value:
        n += 1
    return n

find_first_gt(df[1].to_numpy(), n, value)

---

При наивном тесте мы находим, что в то время как l oop порядка двух всего лишь numpy.

a = np.arange(1_000_000)
n = 0
value = 999_998

%timeit np.argmax(a > value)
%timeit find_first_gt(a, n, value)

322 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
620 µs ± 66.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Однако этот тест явно проверяет, когда индекс является предпоследней позицией. В среднем индекс будет посередине. Итак, давайте проверим все значения в массиве.

def test_numpy(a, n):
    for value in a[::1000]:
        np.argmax(a > value)

def test_find_first(a, n):
    for value in a[::1000]:
        find_first_gt(a, n, value)

a = np.arange(1_000_000)
n = 0

%timeit test_numpy(a, n)
%timeit test_find_first(a, n)

300 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
276 ms ± 1.36 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

В котором мы находим, что средние результаты примерно одинаковы.

Answer 3

Если вы преобразуете фрейм данных в numpy:

Используйте np.argmax(df[n:,1] > value). Он останавливается на первом значении. Это значительно быстрее, чем (df[n:,1] > value).argmax(), когда первое вхождение намного ближе к n по сравнению с размером поискового массива. Однако, когда первое вхождение становится ближе к концу массива, оба метода должны go проходить через большую часть массива.

Чтобы преобразовать столбец по номеру индекса в массив numpy:

np.argmax(df.iloc[:, 1].to_numpy()[n:] > value)

ОБНОВЛЕНИЕ: время сравнения:
Поиск элемента 999,998 в np.arange(1,000,000)

np.argmax(df[n:,1] > value)    time = 0.0008049319999998694
(df[n:,1] > value).argmax()    time = 0.0013422100000000103
Using numba while loop         time = 0.14520884199999995

РЕДАКТИРОВАТЬ: Пожалуйста, проверьте @ piRSquared ответ для сравнения времени. Представления numpy v. Numba кажутся сопоставимыми в этом ответе. Я не уверен, почему он отличается при двух настройках.