Поиск разницы между элементами большого списка

Question

Поиск разницы между элементами большого списка

Рейтинг: 4Ответов: 1Опубликовано: 22.03.2023

Коллеги, прошу совета. Дан список из float. Список может быть большой - миллионы элементов. Мы берем каждый элемент списка и проверяем каждый следующий элемент на разницу между ними. Как только абсолютное значение разницы равно или превышает заранее заданную величину мы заводим флаг в специально подготовленный список, который показывает - получили мы положительную или отрицательную разницу либо мы достигли конца списка, но условия не достигли.

Очевидное, но "тупое" решение данной задачи:

float_list = [1.0, 2.0, 3.0, 6.0, 3.0, 1.0]
flag_list = []
lim = 2 # значение 0 невозможно
for i in range(len(float_list)-1):
    for j in range(i+1, len(float_list)):
        if abs(float_list[j]-float_list[i]) >= lim:
            if float_list[j]-float_list[i] > 0:
                flag_list.append(1)
            else:
                flag_list.append(-1)
            break
    else:
        flag_list.append(0)
flag_list.append(0) # для последнего элемента условие никогда не выполнится
print(float_list)
print(flag_list)

Также я пытался применить map, также пытался конвертировать в pandas.Series и применять apply. Все это - очень долго.

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

UPD. Из комментариев стало понятно, что есть ряд неясных моментов. Проясняю:

Все входные данные положительные
Входные данные хаотичны и могут повторяться
Последовательность данных важна
Конечной целью задачи является - присвоить каждому из элементов списка флаг с соответствующим знаком - нашли мы ПОСЛЕ текущего элемента, другой элемент, который отличается на lim в большую или меньшую сторону.
Важно какая разница встретилась первой - положительная или отрицательная - в зависимости от знака первой разницы, соответствующей условию, мы выставляем положительный или отрицательный флаг.

Благодарю!

python python-3.x алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 5Принят

Проходим от начала и рассматриваем каждый элемент по очереди.

Далее описаны действия для каждого элемента E[i]:

добавляем элемент E[i] вместе с его индексом в дерево, которое хранит уже просмотренные элементы, для которых еще не найдены совпадения.
Находим в дереве все элементы, которые отстоят от текущего на eps или больше. Для каждого такого элемента E[j] в зависимости от того, в какую сторону он отстоит от текущего E[i], записываем результат и удаляем элемент E[j] из дерева.

Т.е. тут поиск идет не от элемента вперед по списку, а от элемента назад, и среди уже просмотренных элементов ищем есть ли такие, для которых текущий подходит по условию достаточной разности.

Итого каждый элемент добавим и удалим максимум один раз - сложность O(n*log(n))

from dataclasses import dataclass
from sortedcontainers import SortedList

l = [1, 2, 3, -2, 3, 0]
e = 2

@dataclass(frozen=True)
class ElementWithIndex:
    value: int
    index: int

unmatched = SortedList(key=lambda el: el.value)

f = [0] * len(l)

for i in range(len(l)):
    el = l[i]
    while unmatched and unmatched[0].value <= el - e:
        f[unmatched[0].index] = 1
        unmatched.pop(0)
    while unmatched and unmatched[-1].value >= el + e:
        f[unmatched[-1].index] = -1
        unmatched.pop(-1)

    unmatched.add(ElementWithIndex(value=el, index=i))

print(f"l={l}")
print(f"e={e}")
print(f"f={f}")

Поиск разницы между элементами большого списка

Ответы