Любопытный вопрос: Какой алгоритм реализует STL set_intersect? - PullRequest
Новая
       19

Любопытный вопрос: Какой алгоритм реализует STL set_intersect?

2 голосов
/ 27 октября 2010

Я потратил значительное количество времени на кодирование алгоритма быстрого пересечения Baeza-Yates для одного из моих приложений. Хотя я немного превзошел STL set_intersect, тот факт, что мне потребовалось отсортировать результирующий набор, удалялся всякий раз, когда я получал реализацию собственного алгоритма после сортировки выходных данных. Учитывая, что STL set_intersect выполняет это хорошо, кто-нибудь может указать мне на алгоритм, который он на самом деле реализует? Или он реализует тот же алгоритм Баеза-Йейтса, но только гораздо более эффективным способом?

Баеза-Йейтс: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

Ответы [ 3 ]

3 голосов
/ 27 октября 2010

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

2 голосов
/ 27 октября 2010

По крайней мере, в тех реализациях, на которые я смотрел, реализация довольно проста - что-то в этом общем порядке: 

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

Конечно, я просто набираю это сверху моегоhead - он, вероятно, даже не будет компилироваться и, конечно, не будет педантично правильным (например, вероятно, следует использовать функцию сравнения вместо непосредственного использования operator< и иметь другой параметр шаблона, чтобы start1 / end1 отличалсявведите с начала2 / конца2).

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

0 голосов
/ 28 октября 2010

Интересно. Таким образом, количество сравнений в вашем алгоритме линейно масштабируется с количеством элементов в обоих наборах. Алгоритм Baeza-Yates работает примерно так (обратите внимание, что предполагается, что оба входных набора отсортированы):

1) Найдите медиану множества A (здесь A - меньшее множество) 2) Поиск медианы A в B. Если найден, добавить к результату иначе, вставной ранг медианы в B известен. 3) Разделите множество A относительно его медианы на две части, и установите B относительно его ранга вставки на две части, и повторите процедуру рекурсивно для обеих частей. Этот шаг работает, потому что все элементы, меньшие медианы в A, будут пересекаться только с этими элементами до ранга вставки медианы A в B.

Поскольку вы можете использовать двоичный поиск, чтобы найти медиану A в B, ясно, что число сравнений в этом алгоритме меньше, чем упомянутое вами. Фактически, в «лучшем» случае число сравнений равно O (log (m) * log (n)), где m и n - размеры наборов, а в худшем случае число сравнений равно O (m + n). Как же я испортил реализацию так плохо? (

...