Алгоритмическая

[AndreyT]

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

Например, предоположим у нас есть упорядоченный массив M длины m и упорядоченный массив N длины n (n >= m). И пусть нам надо найти "места для вставки" всех элементов массива M в массив N. Фактически речь идет о классической задаче слияния двух упорядоченных массивов.

Традиционный лобовой алгоритм слияния, когда мы на каждой итерации сравниваем первые элементы еще не слитых частей массивов, соответствует банальному линейному поиску места для элементов массива M в массиве N и требует O(m+n) сравнений.

Можно предложить другой не менее очевидный способ поиска - просто по очереди берем элементы массива M и ищем их в "оставшейся" части массива N путем выполнения бинарного поиска. Это вариант потребует O(m log n) сравнений.

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

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

Предложите такой алгоритм.

(Банальный "лобовой" вариант с выбором одного из двух подходов в самом начале на основе значения n-m будем считать уже предложенным )

[venco]

Первый подход:
По возрастанию берём элемент из [M] и вставляем в [N] но не делением пополам, а с учётом его наиболее вероятного положения в [N]. Например первое сравнение делаем с N/2M-тым элементом из [N].
После того, как мы нашли место элемента в [N], продолжаем вставку, отбросив все элементы до вставленного, поскольку они явно меньше.
Оценить среднее число сравнений пока не могу.

Следующее улучшение:
первым вставляем средний элемент из [M].
Далее у нас получаются два под массива [N/2], и два подмассива [M/2]. По моим прикидкам среднее количество сравнений в этом варианте M*ln(4N/M)-2, что лучше чем M+N и M*ln(N) в большом диапазоне M.

[tengiz]

]становимся.на.первый.элемент.в.каждом.массиве

while.(есть.ещё.елементы.в.обоих.массивах)
{
....if.(значения.текущих.элементов.равны)
....{
........if.(известно.что.каждый.массив.представляет.собой.
................упорядоченный.набор.уникальных.значений)
............в.каждом.массиве.сдвигаемся.на.один.элемент
........else
............в.каждом.массиве.делаем.либо.двоичный.либо.
............интерполяционный.поиск.первого.элемента.значение.
............которого.не.равно.только.что.прочитанному
....}
....else
....{
........в.массиве.где.значение.элемента.оказалось.меньше,.делаем.либо.
........двоичный.либо.интерполяционный.поиск.первого.элемента.значение.
........которого.больше,.чем.текущий.элемент.другого.массива.

........if.(такой.элемент.найден)
............перемещаемся.на.его.позицию
........else
............конец
....}
}

[AndreyT]

tengiz-у:

Если все элементы массивов различны (а таковыми в общем случае следует считать "почти все" элементы), то на каждой итерации в предложенном алгоритме будет работать именно ветка

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

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

Интерполяционный поиск же является input-specific улучшением и в общем случае принципиального выигрыша не даст.

[olg2002]

Можно предложить другой не менее очевидный способ поиска - просто по очереди берем элементы массива M и ищем их в "оставшейся" части массива N путем выполнения бинарного поиска. Это вариант потребует O(m log n) сравнений.

Можно предложить третий не менее очевидный способ поиска:

просто по очереди берем элементы массива M и ищем их в "оставшейся" части массива N путем выполнения экспоненциального поиска.

[tengiz]

а это (в случае двоичного поиска) ни что иное, как один из алгоритмов в условии.

Да вроде бы нет - приведённый алгоритм отличается от двух исходных "переключеним" с одного массива на другой - в результате для распределений данных которые характеризуются наличием непрерывных участков которые будут сшиваться "целиком" имеет значительно лучшие характеристики чем N log M даже если N и M близки.

Кроме того, если не закладываться на специальные случаи распределения данных когда количество точек сшивки заметно меньше чем количество элементов в массивах (заметим, что распределение данных когда массивы сшиваются в основном через один элемент - на самом деле ещё более специальный случай), учитывая, что поиск имеет "массовый" характер, вполне можно усовершенствовать и поиск тоже - для чего можно держать (logM + logN) стек значений которые встретились при делении оставшейся части каждого массива, что может дать значительную экономию.

[AndreyT]

а это (в случае двоичного поиска) ни что иное, как один из алгоритмов в условии.

Да вроде бы нет - приведённый алгоритм отличается от двух исходных "переключеним" с одного массива на другой - в результате для распределений данных которые характеризуются наличием непрерывных участков которые будут сшиваться "целиком" имеет значительно лучшие характеристики чем N log M даже если N и M близки.

Да, но, во-первых, по-моему при использовании каких-то "эффективных" алгоритмов поиска (типа бинарного) имеет смысл применять этот эффективный алгоритм именно к более длинному массиву (чтобы "подавить логарифмом" бОльшую составляющую трудоемкости). Соответственно, какого-то революционного смысла в переключении я не вижу. Скорее даже наоборот. А даже если и говорить о переключении, то скорее в зависимости от остаточных длин массивов, а не от значений элементов массивов.

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

вполне можно усовершенствовать и поиск тоже - для чего можно держать (logM + logN) стек значений которые встретились при делении оставшейся части каждого массива, что может дать значительную экономию.

Хм... Звучит сложновато.

[tengiz]

вполне можно усовершенствовать и поиск тоже - для чего можно держать (logM + logN) стек значений которые встретились при делении оставшейся части каждого массива, что может дать значительную экономию.

Хм... Звучит сложновато.

Поиск в отсортированном массиве длины N, да ещё когда последовательность искомых значений M сама по себе тоже отсортирована - это специальный случай, когда суммарная сложность операции будет отнюдь не M log N - для чего значения полученные последовательным делением массива N пополам при двоичном поиске можно запоминать в стеке (при этом нужно запоминать только "правые" значения) с тем чтобы при поиске следующего значения поступившего из повледовательности M начинать двоичный поиск не в оставшейся части масива N, а в более коротком подмассиве, ограниченном началом оставшейся части массива N и первым значением на стеке, не превышающим искомое значение. При извлечении значений из стека, опять же, те значения, которые оказались меньше искомого просто выбрасываются.

Кобминация такого оптимизированного поиска с переключением описанным выше и есть предложенное решение.

[AndreyT]

вполне можно усовершенствовать и поиск тоже - для чего можно держать (logM + logN) стек значений которые встретились при делении оставшейся части каждого массива, что может дать значительную экономию.

Хм... Звучит сложновато.

Поиск в отсортированном массиве длины N, да ещё когда последовательность искомых значений M сама по себе тоже отсортирована - это специальный случай, когда суммарная сложность операции будет отнюдь не M log N - для чего значения полученные последовательным делением массива N пополам при двоичном поиске можно запоминать в стеке (при этом нужно запоминать только "правые" значения) с тем чтобы при поиске следующего значения поступившего из повледовательности M начинать двоичный поиск не в оставшейся части масива N, а в более коротком подмассиве ограниченном началом оставшейся части массива N и первым значением на стеке, не превышающим искомое значение элементом. При извлечении значений из стека, опять же, те значения, которые оказались меньше искомого просто выбрасываются.

Да, я прекрасно понимаю, что оценка m log n несколько завышена в том плане, что при вставке каждого элемента не надо просматривать весь массив N, а достаточно просмотреть только кусочек справа от места последней вставки. У меня нет более точной оценки, которая бы это учитывала, но тем не менее мне кажется, что в асимпоте оценка m log n является достаточно хорошей. В любом случае, несложно видеть, что для близких m и n алгоритм с бинарным поиском существенно проигрывает линейному поиску.

Что же касается стека запомненных значений - я не вижу в этом никакого улучшения. Очередной элемент из M все равно придется сравнивать с элементами этого стека. Разница тут только в том, что элементы стека располагаются в массиве в соостветствии с самым первым разбиением массива N, в то время как без стека мы бы выполняли переразбиение каждый раз по новой. Но количество требуемых сравнений от этого никак принципиально не поменяется.

Стоит заметить, что идея этой задачи созрела у меня "по мотивам" одной статьи, в которой приводился [почти] оптимальный алгоритм решения этой задачи, который все-таки использует практически лобовую смесь линейного и бинарного поисков. Все завязано на то, что именно заставляет линейный поиск работать оптимально в случае близких m и n, независимо от взаимного расположения значений элементов массива. Кстати, родственная идея прозвучала в ответе venco.

[olg2002]

Наверное, стоит уточнить, что когда в условии для двоичного поиска указывалось O(m log n), то имелось ввиду в худшем возможном случае, а никак не в среднем. Разумеется, если для очередного элемента из M мы определили позицию k в N, то все последующие элементы из M мы будем искать начиная с этой позиции, как минимум, а значит очередной двоичный поиск потребует log(N-k). Мне кажется, это то, что пытается сформулировать tengiz, правда, я не вижу, как может помочь сохранение промежуточных значений из N на стеке - сравнивать с ними все-равно придется, какая-разница из стека они или из оригинального массива.

Я к своему удивлению не смог найти ссылки на упомянутый мной экспоненциальный поиск как минимум в двух популярных источниках. В двух словах: поиск в массиве N очередного элемента из M начинается с текущей позиции k; на первом шаге проверяем элементы k, k+1, k+2, k+4, ..., k+2^i,... пока не обнаружим большее значение; на втором шаге - бинарный поиск в последнем отрезке k+2^(i-1)..k+2^i и перенос текущей позиции. Такой поиск всегда работает не хуже линейного слияния, очевидно лишен недостатка бинарного поиска в худшем случае, лишь немного уступая ему в среднем. По-моему, этот вариант удовлетворяет всем исходным требованиям для адаптивного алгоритма.

[tengiz]

При двоичном поиске после серии делений оставшейся части массива пополам оставляем на стеке значения в точках деления массива, причём не все встеченные значения, а только те, которые оказались больше значения которое мы искали. В результате на стеке остаётся сортированный по значениям набор пар [значение элемента, позиция в массиве] - оценка необходимого размера стека - log N. При поиске следующего значения вместо нормального двоичного поиска делаем "ускоренный" двухшаговый двойчный поиск - т.е. сначала ищем двоичным поиском диапазон на сортированном стеке (который на самом деле реализуется массивом с "подвижными" границами - поэтому поиск будет эффективным) куда попадает новое значение для поиска, для чего затратим в среднем log log N сравнений, а затем нормальный двоичный поиск в полученном диапазоне.

<added>
Хотя на самом деле действительно, сами значения на стеке хранить необязательно - так как их позиции всегда заранее известны, их просто можно извлекать из массива напрямую всего лишь правильно сгенерив последовательность индексов. Что касается "ускоренного" двоичного поиска - на самом деле он никакого выйгрыша для нормального двоичного поиска конечно не даёт (однако в случае интерполяционного поиска может оказаться быстрее для "хороших" распределений данных, так как в этом случае последовательность индексов заранее вычислить невозможно). Поэтому please disregard.

для olg2002 - насколько я понимаю, Ваш алгоритм с проходом по значениям с индексами k+1, k+2, k+4... чем-то похож на то, что я так коряво пытался изобразить в предыдущих сообщениях.
</added>

[AndreyT]

ОК, т.к. подобрались уже близко и подразумеваемый мною алгоритм не мой, а подсмотренный, я приведу его. Алгоритм совершенно прост:

Разбиваем массив N примерно на m частей одинаковой длины (примерно n/m элементов каждая). Берем очередной элемент из M. Сначала выполняем линейный поиск той части в N, в которую попадает этот очередной элемент. Затем в найденной части выполняем бинарный поиск конкретного места для вставки. И т.д. Все.

Такой алгоритм производит 2m + m log n/m сравнений.

В статье (страницы 4-5 по PDF) дается верхний предел количества сравнений как m(t+1) + floor(n/2^t), где t = floor(log2 n/m), т.е. длины сегментов, на которые разбивается N, приводятся к ближайшей меньшей степени двойки (длина сегмента равна 2^t). При этом утверждается, что mt + floor(n/2^t), это нижний предел количества сравнений, выполняемых любым алгоритмом слияния массивов (в общем случае, разумеется).

[venco]

Такой алгоритм производит 2m + m log n/m сравнений.

Получилось та же ассимптотика, что и у моего алгоритма (см. выше).
Причём это уже близко к теоретическому пределу (см. графики).
Напоминаю алгоритм:

Code: Select all

template<class InputIter, class OutputIter, class Compare>
OutputIter merge(InputIter begin1, InputIter end1, InputIter begin2, InputIter end2, OutputIter out, Compare comp)
{
  if ( end1-begin1 < end2-begin2 ) {
    swap(begin1, begin2);
    swap(end1, end2);
  }
  if ( begin2 == end2 )
    return copy(begin1, end1, out);
  InputIter mid2 = begin2+(end2-begin2)/2, mid1 = lower_bound(begin1, end1, *mid2, comp);
  out = merge(begin1, mid1, begin2, mid2, out, comp);
  *out++ = *mid2++;
  return merge(mid1, end1, mid2, end2, out, comp);
}

Эксперимент показывает, что количество сравнений не больше 112% от теоретического минимума.

[tengiz]

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

Оказалось, что в точности Ваша задача описана у Кнута в третьем томе на странице 202. Решение предлагаемое Кнутом - вариация алгоритма Hwang-Lin на который ссылаются в приведённой Вами статье, но с принципиальным отличием: распределение ролей последовательностей - "длинная/короткая" и глубина линейного поиска на первом шаге являются динамическими и делается на каждой итерации алгоритма. Т.е. во-первых, массивы могут поменяться местами, во-вторых, в действительности, первый шаг - это не линейный, а скорее экспоненциально-двоичный поиск (который, ясное дело, выродится в линейный, если распределение значений в обоих массивах равномерное, т.е. когда отношение длин "неслитых" частей массивов остаётся постоянным.)

[tengiz]

Кстати, вот интересная вариация исходной задачи - как слить две сортированные последовательности если их длины неизвестны (но предполагая, что каким-то образом обеспечивается эффективный индексный доступ к элементам последовательностей)?

[venco]

Кстати, вот интересная вариация исходной задачи - как слить две сортированные последовательности если их длины неизвестны (но предполагая, что каким-то образом обеспечивается эффективный индексный доступ к элементам последовательностей)?

Бинарным поиском за log(N)+log(M) находим длины, и сводим задачу к предыдущей.

[tengiz]

Кстати, вот интересная вариация исходной задачи - как слить две сортированные последовательности если их длины неизвестны (но предполагая, что каким-то образом обеспечивается эффективный индексный доступ к элементам последовательностей)?

Бинарным поиском за log(N)+log(M) находим длины, и сводим задачу к предыдущей.

А что если "длина неизвестна" реально означает просто непрерывные потоки данных которые нужно сливать "на ходу"? Как если бы данные читались с бесконечной магнитной летны при условии что есть разумно эффективные операции перемотки вперёд и назад но двоичный поиск длины никогда бы не закончился?

[venco]

Как если бы данные читались с бесконечной магнитной летны при условии что есть разумно эффективные операции перемотки вперёд и назад но двоичный поиск длины никогда бы не закончился?

Если есть эффективные операции перемотки вперёд и назад то двоичный поиск длины закончится:

Code: Select all

int length(sequence A)
{
  int min = 0, max = 1;
  while ( A.seek(max) ) { // log2(N) seeks
    min = max;
    max = max * 2;
  }
  while ( max - min > 1 ) { // log2(N) seeks
    int mid = (min+max)/2;
    if ( A.seek(mid) )
      min = mid;
    else
      max = mid;
  }
  return min;
}

[tengiz]

Если есть эффективные операции перемотки вперёд и назад то двоичный поиск длины закончится.

Давайте считать, что они "эффективные" - с точки зрения затраченных циклов CPU, а не физического времени, т.е. сравнения ключей в терминах циклов CPU всё равно дороже, чем любые перемотки. Но вне зависимости от этого считаем входные потоки бесконечными - они имеют начало, но не имеют конца. Другими словами seek "вперёд" никогда не возвращает FALSE, хотя может занять ненулевое физическое время пропорциональное растоянию на которое нужно будет перематывать, при этом CPU будет свободен.

[venco]

Так что минимизируем то?
И если seek() не возвращает FALSE, как мы узнаем что данных больше нет?

[tengiz]

Так что минимизируем то?
И если seek() не возвращает FALSE, как мы узнаем что данных больше нет?

Минимизируем CPU time. Данные никогда не кончаются.

[venco]

В этом случае простой merge sort подойдёт - сравниваем всегда первые элементы.