1

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

Пример: в дереве 1, 5, 6, 7.56, 100 и на входе 8, то результат (7.56, 100)

Или тут лучше подходит другая структура данных? (Необходима максимальная скорость)

UPD: На словах придумал, но реализацию еще нет. Назовем искомое значение v. Начинаем искать v. Если последнее значение меньше v(нода1), то необходимо найти ноду с минимальным значением которое будет больше ноды1 (нода2). Если последнее значение больше v(нода2), то необходимо найти ноду с максимальным значением которое будет меньше ноды2 (нода1). Если в дереве найдена нода со значением v, то сообщаем об исключении. Если какого-то значения из пары нет, то заменить его на null в ответе, к примеру (null,null) или (3,null).

14
  • 1
    эти значения на числовой прямой статичные? Или обновляются? Если обновляются, то как часто?
    – tym32167
    15 авг 2020 в 22:33
  • Если вы хотите найти элементы, соседние с заданным, чем вам обычный сортированный массив не угодил?
    – tym32167
    15 авг 2020 в 22:36
  • 1
    Вставка/удаление в сортированный массив займет линейное время. Если у вас есть вставки/удаления, то тогда дерево будет лучше.
    – tym32167
    15 авг 2020 в 22:42
  • 1
    Ещё вопрос - сколько данных то вообще и как часто к ним идёт обращение? Если данных очень много, я бы в SQL таблицу записал, сделал индекс по этому полю - и пусть база думает.
    – CrazyElf
    16 авг 2020 в 7:14
  • 1
    Для начала попробуйте на данных реального для вашей задачи размера тривиальный отсортированный массив и бинарный поиск.
    – avp
    16 авг 2020 в 10:19

2 ответа 2

2

Возможно, B+-дерево будет лучше просто бинарного дерева, исходя из использования кэша процессора. И возможно, даже лучше бинарного поиска в большом массиве.

Куча (heap) расположена в линейном/виртуальном адресном пространстве. Физически данные могут находиться в кэше процессора (доступно очень быстро), оперативной памяти (нормально), выгружены в своп (медленно).

При обращении к виртуальному адресу данные переносятся большими кусками (страница памяти (см. TLB) и блок кэша (cache-line)) из медленных подсистем в быстрые.

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

Если половинным делением искать в большом массиве, то первые несколько делений возможны обращения к новым участкам памяти. С B+-деревом, у которого один узел влезает в единицу кэширования, и в одном узле много ссылок на детей, сначала будет поиск внутри массива детей, а только потом -- к новому узлу;

В листьях дерева -- сортированные массивы.


Критика реализации векторов в scala, не про поиск, а вообще:

... cache-locality, where the 32-way branching ... faster than working with binary trees ...

https://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#vectors-are-ok

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


В абстрактах пары статей (не вчитывался) говорится:

Effect of Node Size on the Performance of Cache-Conscious B+-trees:

in modern processors, the over-all performance of an index structure depends on the number of cache misses, the instructions that are executed, the number of mispredicted conditional branches, and the number of TLB misses.

http://pages.cs.wisc.edu/~jignesh/publ/cci.pdf

Making B+-Trees Cache Conscious in Main Memory:

Cache Sensitive SearchTrees (CSS-Trees) perform lookups much faster than binary search

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.444.6716&rep=rep1&type=pdf


А возможно, есть и какая-то совсем специализированная структура.

В общем, пробовать надо.

3
  • 1
    А можно ссылку на "...использования кэша процессора", "... первые несколько делений возможны обращения к новым страницам памяти"? Не очень понимаю как это работает. К примеру делаю реализацию на c# и знаю что есть кучи и стек.
    – John
    15 авг 2020 в 23:15
  • развернул объяснения и ссылки 16 авг 2020 в 1:08
  • 1
    В самом деле, CSB+ деревья выглядят симпатично. Как вы правильно заметили, пробовать надо, подбирать оптимальный размер узлов индекса и данных и метод поиска (последовательный (не стоит забывать о cache lines prefetch) или бинарный) в узлах
    – avp
    16 авг 2020 в 9:49
0

1-й способ

Сбалансированное бинарное дерево поиска.

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

Пусть X - узел дерева, который содержит найденное "входящее числовое значение".

Что же до поиска предшественника, то эта задача несильно сложнее:

  • если у найденного элемента есть левое поддерево, то предшественник является его максимальным элементом; другими словами, берём левого сына и в цикле проходим по иерархии узлов вниз, на каждом уровне выбирая правого сына, пока не упрёмся в листовой узел:
t = X->Left_Child;
while ( t->Right_Child != null )
{
    t = t->Right_Child;
}
return t->Value;
  • в противном случае (т.е. левое поддерево пустое) поднимаемся по иерархии вверх, пока не найдётся узел с ключом меньшим, чем значение X:
t = X->Parent;
while ( t->Value > X->Value )
{
    t = t->Parent;
}
return t->Value;

Асимптотика алгоритма:

  • построение дерева из n входных элементов: O(n*log(n))
  • поиск X: O(log(n))
  • поиск предшественника: O(log(n))

Суммируем, меньшие оценки поглощаем большими, и получаем итоговую оценку:

O(n*log(n))

2-й способ

Бинарный поиск по отсортированному массиву.

Пусть A - отсортированный массив, где храним входные данные.

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

Пусть i - это индекс "входящего числового значения", найденный бинарным поиском.

Тогда (i-1) будет индексом предшественника, а значение предшественника - A[i-1].

Асимптотика алгоритма:

  • сортировка на основе сравнений: O(n*log(n))
  • бинарный поиск: O(log(n))
  • вычисление предшественника: O(1)

Суммируем, меньшие оценки поглощаем большими, и получаем итоговую оценку:

O(n*log(n))

Оптимизация

Можно ли достичь лучшего по скорости?

Да, можно! Только есть ограничения:

  • входные данные должны быть в относительно узком диапазоне значений, например числа от 1 до 10000
  • данные должны быть распределены относительно равномерно по оси между минимальным и максимальным значениями
  • во 2-м способе сортировку на основе сравнения заменяем - будем использовать сортировку на основе значений ключей (примеры: сортировка подсчётом и корзинная сортировка) с линейной асимптотикой O(n)

В этом случае асимптотика алгоритма "поджимается":

  • сортировка на основе значений: O(n)
  • бинарный поиск: O(log(n))
  • вычисление предшественника: O(1)

Суммируем, меньшие оценки поглощаем большими, и получаем итоговую оценку:

O(n)

3-й способ

Можно ли добиться ещё более быстрого результата?

И да и нет :)

"Нет" - потому, что не можем опуститься ниже оценки O(n) - т.к. нужно прочитать входные данные целиком.

"Да" - потому, что в оценке O(n) можем уменьшить скрытый константный множитель!

Как это сделать? Ну, раз мы уже упомянули корзинную сортировку, давайте попробуем проэксплуатировать её основную идею в своих целях.

Итак, корзинная сортировка делит числовую ось на интервалы, и для каждого интервала создаёт "корзину", в которой складываются все значения, попадающие на этот интервал. Если набор корзин реализовать массивом списков, а размер каждой корзины задать константой c, то сортировка становится до неприличия простой:

A = new int[n];  // входные данные
B = new List<int>[max(A)/c];  // набор корзин

// 1-й проход - читаем входные данные
for (i = 0; i < n; i++)
    B[A[i]/c].add(A[i]);
    
// 2-й проход - сортируем внутренности каждой корзины
for (i = 0; i < max(A)/c; i++)
    B[i].sort();

// 3-й проход (необязательный) - переписываем числа из набора корзин обратно в линейный массив A[]

А теперь подумаем - нужно ли нам сортировать сразу все корзины?

Правильный ответ - "конечно, нет!" :)

Составляем итоговый план алгоритма:

  • раскладываем числа по корзинам
  • определяем корзину, где лежит искомое число X; это просто - значение X делим на значение c (размер корзины); пусть индекс корзины с числом X равен i
  • сортируем i-ю корзину (при константном размере корзины её сортировка любым алгоритмом принимается за O(1)!)
  • бинарным (или даже линейным) поиском определяем в корзине позицию числа X; пусть его индекс внутри корзины будет j (поиск внутри корзины в любом случае будет быстрее сортировки этой корзины, так что асимптотику тоже принимаем за O(1)!)
  • если j > 0, то в качестве ответа возвращаем значение корзины с индексом (j-1) и завершаем выполнение
  • (если j = 0) идём влево от i-й корзины, пока не найдём непустую; ищем в непустой корзине максимальный по значению элемент и возвращаем его в качестве ответа (и опять, по тем же соображениям, асимптотика этого шага принимается за O(1)!)

Асимптотика алгоритма:

  • раскладывание по корзинам: O(n)
  • определение корзины с элементом X: O(1)
  • сортировка корзины с элементом X: O(1)
  • поиск ближайшей слева непустой корзины: O(n) (в худшем случае проверим на [пусто/непусто] все корзины, число которых линейно)
  • вычисление максимального элемента корзины: O(1)

Суммируем, меньшие оценки поглощаем большими, и получаем итоговую оценку:

O(n)

P.S.:

Вообще-то, оценка асимптотической сложности для алгоритмов подсчётной и корзинной сортировки не совсем O(n), а скорее O(r), где r - диапазон значений входных данных, т.е. r = max(A) - min(A). Но во многих случаях (зависящих от входных данных) можно считать оценки O(n) и O(r) эквивалентными.

Кроме того, оценки O(n) для "оптимизированного" 2-го способа (равно, как и для 3-го) являются оптимистичными, для усреднённого случая. Однако, возможны и худшие случаи входных данных , когда алгоритм будет отрабатывать за время похуже линейного.

Впрочем, это бывает и с некоторыми известными алгоритмами - так, неаккуратно реализованный QuickSort может деградировать с O(n*log(n)) до O(n^2) при особых входных данных.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.