Как найти минимальную разницу между числами в массиве numpy

У меня есть массив numpy с образцами, которые являются результатом эксперимента. Все образцы являются целыми числами, но я не думаю, что это имеет значение. Некоторые значения появляются в массиве несколько раз, а некоторые — сотни раз — массивы могут содержать 10 000 выборок.

Хотя значения выглядят случайными, они имеют минимальный интервал. Я имею в виду, что никакие два значения не могут быть ближе друг к другу, чем, например, 27. Таким образом, вы можете увидеть 50 выборок со значением 999 027 где-то в массиве и вы можете увидеть 120 выборок из 999 054, но вы не увидите ни одной выборки из 999 036. значение в любом месте массива. Мне нужно проверить массив и установить, каков этот минимальный интервал, но очень быстро, если это возможно. Вы можете назвать это «ближайшим расстоянием выборки». Мне не нужно проверять каждый случай, поскольку вы можете себе представить, что просто проверка нескольких образцов, если они близки по значению, дает вам хорошее предположение о том, какова минимальная разница.

У кого-нибудь есть умный алгоритм (с использованием Python), который мог бы довольно быстро найти это ближайшее минимальное расстояние между любыми выборками? Как я уже сказал, массивы могут быть большими, и каждую секунду их нужно проверять многие десятки.

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


python numpy arrays spacing minimum
person Richard    schedule 06.03.2021    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Поскольку у вас есть массивы numpy, numpy должен ускорить это, хотя, вероятно, есть более эффективные реализации:

import numpy as np
from timeit import timeit

#Riccardo Bucco
def f1(lst):
    sorted_lst = sorted(set(lst))
    return min(n2 - n1 for n1, n2 in zip(sorted_lst, sorted_lst[1:]))

#numpy solution
def f2(arr):
    b = np.diff(np.sort(arr))
    return b[b>0].min()

ntime = 100 #number of test runs
nxd = 5000    #array length
nmax = 1000000

print(timeit(lambda: f1(np.random.randint(1, nmax, nxd)), number=ntime))
#0.347

print(timeit(lambda: f2(np.random.randint(1, nmax, nxd)), number=ntime))
#0.0327
    

ntime = 10 #number of test runs
nxd = 5000000    #array length
nmax = 100000000

print(timeit(lambda: f1(np.random.randint(1, nmax, nxd)), number=ntime))
#62.54

print(timeit(lambda: f2(np.random.randint(1, nmax, nxd)), number=ntime))
#5.46
person Mr. T    schedule 06.03.2021
comment
Ах, блестящая концепция Риккардо. Это отличный способ подумать о том, как получить ответ и минимизировать время обработки. Итак, логика состоит в том, чтобы отсортировать список по значению, а затем найти минимальную разницу между соседними отсортированными выборками. Приятно видеть, что numpy эффективно работает таким образом. Я не сказал, но выборки с большей вероятностью будут демонстрировать минимальный разрыв, когда они имеют более низкие значения, что упрощает использование выборки для ускорения этого. Спасибо. - person Richard; 06.03.2021
comment
Извините, я хотел поблагодарить мистера Т. и Риккардо за концепцию и исполнение - моя ошибка. Во всяком случае, мистер Т; Я использовал это сейчас в версии numpy, и она отлично работает, спасибо. Numpy действительно быстр по сравнению с тем, что я придумал. Кроме того, я думаю, что я также легко смогу ускорить его - например, не глядя на весь массив, а используя образец, вероятно, будет работать на практике для данных, которые у меня есть. Рекомендую этот подход для тех, у кого есть похожая проблема. - person Richard; 07.03.2021

arrow_upward
0
arrow_downward

Вы можете отсортировать уникальные элементы вашего массива, а затем найти кратчайшее расстояние между последовательными числами:

def find_min_distance(lst):
    sorted_lst = sorted(set(lst))
    return min(n2 - n1 for n1, n2 in zip(sorted_lst, sorted_lst[1:]))

Например:

>>> lst = [6, 8, 1, 4, 9, 4, 8]
>>> find_min_distance(lst)
1

Сложность этого подхода — O(nlogn), где n — количество элементов исходного массива. У вас не может быть лучшей сложности, если вы заранее не знаете диапазон, в который попадают ваши числа.

person Riccardo Bucco    schedule 06.03.2021