LINUX.ORG.RU

Нужен оптимальный алгоритм объединения двух упорядоченных массивов.

 ,


0

1

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

Упорядочены по доп.ключу, а не непосредственно по значению, т.е. прилагается функция сравнения.

Массивы равнозначны, и можно объединять в любой, или можно даже создать новый, если время на выделение памяти незначительно по сравнению с приростом скорости алгоритма.

Конечно, про это пишут везде и много, но везде повторяется примитивный вариант параллельного обхода. Так же как и в классическом std::merge.

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

От которого количества имеет смысл вставлять по штучно, а не прогонкой объединения? И т.д.

В общем нюансов много, есть ли готовое, желательно на C++?

-----------------
Если более предметно, то имеется два массива, упорядоченных по Key:

using Key = ...;
using Aggr = int; // может быть любой складывамый класс
std::vector<pair<Key,Aggr>> ar1 = ...;
std::vector<pair<Key,Aggr>> ar2 = ...;

И из этих двух нужно сделать один объединением, а для случаев когда Key совпадают, то Aggr сложить для результатного массива.

===============================================
UPD: добавил описание результата изысканий: пост

тогда проще поиском по сортированному массиву найти позицию

Если это именно массивы, то тебе всё равно придётся аллоцировать новый массив на n+m элементов и копировать туда. Т.е. всё равно 1 проход будет. Тогда какая разница? А если это «типа массивы» но на самом деле списки, то тогда «найти позицию» будет дорогой операцией..

no-such-file ★★★★★ ()

Упорядочены по доп.ключу, а не непосредственно по значению, т.е. прилагается функция сравнения.

Судя по описанию, это похоже на flat_map

annulen ★★★★★ ()
Ответ на: комментарий от no-such-file

Если это именно массивы, то тебе всё равно придётся аллоцировать новый массив на n+m элементов и копировать туда

Для каких-то случаев да, но для каких-то хватит уже заразервированной памяти. Я думаю, если учесть побольше нюансов, то это даст прирост ~50% времени.

victor79 ()
Ответ на: комментарий от victor79

но для каких-то хватит уже заразервированной памяти

Зарезервированной где? В середину ты всё равно не вставишь без копирования половины массива. Вставил 2 элемента - считай что весь массив скопировал. Возможны какие-то нанооптимизации, типа проверить что первое число второго массива меньше последнего у первого и тогда можно тупо дописать второй в конец первого. Но то такое.

no-such-file ★★★★★ ()

В таком случае, не эффективно например

Сколько элементов в массивах? Если 100, то об эффективности думать не надо. O(n^2) и вперёд.

ox55ff ★★★★ ()
Ответ на: комментарий от ox55ff

Сколько элементов в массивах? Если 100, то об эффективности думать не надо.

от одного до ~150. В теории может быть и 10тыс, но пока это не нужно.

victor79 ()
Ответ на: комментарий от no-such-file

В середину ты всё равно не вставишь без копирования половины массива. Вставил 2 элемента - считай что весь массив скопировал.

Имено, что лишь половину - 50% времени. При правильной вставке двух элементов будет почто так же. Вот и думаю, то ли самому продумать эту штуку, либо есть готовое.

У меня алгоритм на таких объединениях работает несколько минут или даже десятков, а оптимизация этого момента это улучшит. Суммарно конечно даст не 50%, но хоть что-нибудь будет.

victor79 ()
Последнее исправление: victor79 (всего исправлений: 3)
Ответ на: комментарий от Siborgium

Есть: не страдать х**ней и воспользоваться std::map

Я после того как слез с мап на упорядоченный вектор, производительность выросла в ~1.5 раз. И на обходах, и на вставках - на всем.

Мап лучше, когда размеры от 1000, а на 100 вектора существенно быстрей, несмотря на то, что вставка двигает половину значений. Плюс куча бонусов при инициализации из уже упорядоченных данных.

victor79 ()
Последнее исправление: victor79 (всего исправлений: 2)

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

А ничего что нужно всё равно либо передвигать все элементы после, либо реаллоцировать массив и копировать все элементы? В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.

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

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.

вставка одного в упорядоченный будет O(log(N) + аллокация)

можно модифицировать исходный массив

Можно. Это возвращаемый результат из рекурсии, в рекурсию же, и дальше рекурсивно складывается, удаляя уже сложенное.

в значительном проценте случаев все ключи меньшего массива уже есть в большем

Верно, нюансов достаточно.

victor79 ()
Последнее исправление: victor79 (всего исправлений: 3)
Ответ на: комментарий от victor79

Это получится обычный insert, о чем тут спорить?

О том что ты ничего не понимаешь. Нужно сдвигать все элементы после места вставки. Никаким logN там и не пахнет.

За logN ты лишь найдёшь место вставки. Дальше O(N) на саму вставку. Учи матчасть.

У массива никогда не было logN на вставки. logN у деревьев…

fsb4000 ★★★★★ ()
Последнее исправление: fsb4000 (всего исправлений: 1)

Нужен оптимальный алгоритм объединения двух упорядоченных массивов.

Тему не читал, но это же буквально сортировка слиянием

Crocodoom ★★★★ ()
Ответ на: комментарий от no-such-file

В середину ты всё равно не вставишь без копирования половины массива. Вставил 2 элемента - считай что весь массив скопировал.

+100500.

fsb4000 ★★★★★ ()
Ответ на: комментарий от victor79

вставка одного в упорядоченный будет O(log(N) + аллокация)

Двойка, вставка в упорядоченный массив будет O(N).

slovazap ★★★★★ ()

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

neon1ks ★★ ()
Ответ на: комментарий от slovazap

У ТС два упорядочённых массива объединяются в один упорядоченный, я правильно понял? И чем это тогда отличается от сути алгоритма сортировки слиянием?

На всякий случай, сортировка слиянием это

sort(xs) ~> merge(sort(xs[:len/2]), sort(xs[len/2:]))

Где главное правильно написать функцию merge + тривиально замкнуть рекурсию

Crocodoom ★★★★ ()
Последнее исправление: Crocodoom (всего исправлений: 2)
Ответ на: комментарий от slovazap

Там от классической сортировки слиянием отличие в том, что два массива уже отсортированы и запускается только финальная стадия. При этом слитый массив оказывается отсортирован. И это самый простой способ избежать дубликатов - чего ТС и хочет собственно.

Это алгоритм имени кого то, я забыл.

AntonI ★★ ()

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

Можно свелосипедить это на std::map вместо std::vector

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

Можно подумать над специфической структурой данных учитывающей что есть непрерывные куски массивов.

AntonI ★★ ()
Ответ на: комментарий от AntonI

Да-да, я уже про это два раза сказал - отличие от сортировки в том что там нет сортировки. Там есть только слияние. Неприятно видеть коллег которые так шаблонно мыслят - заучили когда-то что есть сортировка слиянием, и теперь лезут сортировать ей уже сортированное, и не могут предположить что слияние бывает вполне себе обособлено.

Это алгоритм имени кого то, я забыл

Мля, это цикл и два итератора и сравнение, это алгоритм имени никого, такая элементарщина не может носить чьё-то имя в принципе.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

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

«Где главное правильно написать функцию merge + тривиально замкнуть рекурсию»(c) @Crocodoom == «Там есть только слияние.»(c) Вы

такая элементарщина не может носить чьё-то имя в принципе.

Очень много элементарщины носит чье то имя.

AntonI ★★ ()
Ответ на: комментарий от AntonI

Все фигня. В любом случае данные надо копировать в новый вектор, так что получаем сложность O(N1+N2) и ничего лучше не сделать.

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

Так что не надо усложнять простые вещи;-)

AntonI ★★ ()
Ответ на: комментарий от victor79

Я думаю, если учесть побольше нюансов, то это даст прирост ~50%

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

tz4678 ★★ ()
Ответ на: комментарий от slovazap

Я всё же доведу мысль до конца. Раз искомый ТС алгоритм слияния - основная часть алгоритма сортировки слиянием, то можно погуглить популярные реализации merge sort, и оттуда спизвдохновиться

Crocodoom ★★★★ ()
Ответ на: комментарий от victor79

от одного до ~150.

У меня алгоритм на таких объединениях работает несколько минут или даже десятков

Как, чёрт побери, ты тратишь несколько десятков минут на мерж сортированных массивов?!

ya-betmen ★★★★★ ()

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

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

Если не создавать (предположим, есть массив a длины N+M с заполненными M записями и массив b длины N, результат в массиве a), тогда можно перемещаться на следующий поиском.

i1 = позиция b[0] в a
перебираем k позиций из b, которые меньше a[i1+1]
i2 = позиция b[k] в a[i1+1:]
сдвигаем a[i1:] на k, вставляем найденный диапазон b[:k]
вставляем b[:k] в a[i2+k:] по этому же алгоритму

P.S. Алгоритм примерный, могут быть ошибки на плюс-минус один по позиции и не упомянуты проверки на конец массива.

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от victor79

У меня алгоритм на таких объединениях работает несколько минут или даже десятков

На десяти тысячах элементов??? Ты точно std::merge используешь, а не какой-то поломанный велосипед?

monk ★★★★★ ()

Извини, конечно, ТС, может я чего-то не понимаю, но лучше параллельного обхода тут ничего не придумаешь. Вставка или сортировка в готовый массив тебе ничего лучше O(n) не дадут.

untitl3d ()

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

Любые попытки применить параллельные обходы сортированных массивов только ухудшали результат. И как объединение в новый вектор, и как попытка вставки в текущей же после прохода, оба варианта показывали результат хуже.

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

В среднем код такой:

template <class K, class D>
void Aggr<K,D>::appendAsInsert_withInsertAfter(const Aggr& o, bool asMove) {
    // asMove - два варианта в одном, const Aggr& и Aggr&&
    
    // сортированные данные хранятся в
    // mapData, это что-то вроде flat_map<K,D> из boost
    //   содержит сортированные по ключу складываеммые данные

    // накопление позиций, которых нет в текущем объекте,
    //   но есть в добавляемом - что бы потом сразу все добавить.
    MyList<PairForInsert> listForInsert;

    Node* preFindPos = begin();

    for (const auto &ndSrc: o.mapData) {
        const auto& [key,valueSrc] = ndSrc;

        // поиск по сортированному массиву от предыдущей позиции
        //  использование предыдущей позиции улучшает совсем на немного
        auto [exists,ndDest] = mapData.findInsPos(key, preFindPos);
        preFindPos = ndDest;

        if (!exists)
            // позиция не нашлась, будет добавлена после цикла
            listForInsert += PairForInsert(ndDest, &ndSrc);

        else if (!asMove)
            ndDest->second += valueSrc;
        else
            ndDest->second += std::move(const_cast<D&>(valueSrc));
    }

    // добавление отсутствующих здесь, но присутствующих в добавляемом
    // сразу за один проход.
    // Если выделенный резерв текущего объекта позволяет,
    // то добавляемое совмещается проходом в обратном порядке.
    // Если не позволяет, то выделяется новый буфер, и в него
    // складывается проходом он начала.
    mapData.unsafe_insertListPointers(listForInsert, asMove);
}
Ну а дальше, этот метод вызывается из операторов сложения с соответствующим флагом asMove.

Случаи сложений с пустыми объектами отсеюиваются до этой функции как простые копирования или перемещения объектов.

Случай когда добавляемый больше исходного, и добавляемый типа &&, то они меняются местами.

victor79 ()
Последнее исправление: victor79 (всего исправлений: 2)
Ответ на: комментарий от no-such-file

Зарезервированной где? В середину ты всё равно не вставишь без копирования половины массива. Вставил 2 элемента - считай что весь массив скопировал.

Слить два массива без выделения дополнительно памяти можно, но за O(n log n), как это делается в четно-нечетной сортировке слиянием Бэтчера.

Waterlaz ★★★★★ ()
Ответ на: комментарий от Waterlaz

Слить два массива без выделения дополнительно памяти можно, но за O(n log n)

ЛОЛ, тут массивы уже отсортированы и сливаются за O(n), можешь забрать свои позорные n log n обратно. Гражданин хочет ещё быстрее, типа за log n.

no-such-file ★★★★★ ()
Последнее исправление: no-such-file (всего исправлений: 2)
Ответ на: комментарий от no-such-file

ЛОЛ, тут массивы уже отсортированы и сливаются за O(n), можешь забрать свои позорные n log n обратно. Гражданин хочет ещё быстрее, типа за log n.

Так я и предлагаю сливать in-place отсортированные массивы. Гугли «четно-нечетная сортировка слиянием Бэтчера». Она делает слияние отсортированных массивов за O(n log n), а весь массив сортирует за O(n log^2 n). Может показаться, что это не очень хорошо, но там есть другие хорошие свойства (реализуемость как сортирующая сеть например)

Waterlaz ★★★★★ ()
Ответ на: комментарий от no-such-file

Но он за это хочет чтобы было быстрее O(n).

При слиянии классическим merge там O(n1+n2-X), где X это количество одинаковых ключей. Плюс время сдвигов или переаллокаций.

Но вопрос в том, что если n2 == 1, то зачем проходить O(n1+n2-X)? Можно найти позицию вставки/сложения за O(log n1).

Но на самом деле, обвес всякими проверками это все утяжеляет, и для случаев если списки менее ~30, нарисованный мной вариант в среднем лучше или равный по производительности.

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

Aggr calcNextLevel(level) {

    Aggr result; // <- объект накопления по упорядоченным ключам
    for (auto& nextLevel: listNextLevel)
        result += calcNextLevel(nextLevel) // рекурсия
    
    ... разные вычисления с result ...

    return result;
}

victor79 ()
Последнее исправление: victor79 (всего исправлений: 1)
Ответ на: комментарий от victor79

При слиянии классическим merge там O(n1+n2-X), где X это количество одинаковых ключей.

Открою секрет. O(n1 + n2 - X) = O(n1 + n2)

Waterlaz ★★★★★ ()
Ответ на: комментарий от Waterlaz

Открою секрет. O(n1 + n2 - X) = O(n1 + n2)

Вот если бы еще объяснил. А то по мне это как если сказать, что n1+n2-X = n1+n2; это только для случаев X==0.

victor79 ()
Ответ на: комментарий от victor79

Ну, Запись f(n) = O(g(n)) означает, что существуют такие c и m, что f(n) < c*g(n) для всех n>m.

Отсюда интересные свойства типа O(n1+n2) = O(max(n1, n2)). Ну а в нашем случае max(n1, n2) <= n1+n2-X <= n1+n2 <= 2*max(n1, n2). Поэтому O(n1 + n2 - X) и O(n1 + n2) значат одно и то же.

Waterlaz ★★★★★ ()
Ответ на: комментарий от Waterlaz

Запись f(n) = O(g(n)) означает, что существуют такие c и m, что f(n) < c*g(n) для всех n>m

Уточните, где здесь m? Может не аккуратно написали, и я поэтому не понимаю как такое равенство О(n1+n2) == О(max(n1, n2)) может быть? Если О это функция, то это эквивалентно f(n1+n2) == f(max(n1, n2)), что ложно.

victor79 ()
Ответ на: комментарий от Waterlaz

И в любом случае, какую бы ты софистику не написал бы, от этого цикл из n1+n2-x тактов не выполнится за max(n1,n2) тактов, за исключением случая, если x равен одному из n1 || n2.

victor79 ()
Последнее исправление: victor79 (всего исправлений: 1)

Это последний проход сортировки merge sort – объединение двух уже отсортированных массивов. Смотри на wiki MergeSort

unanimous ★★★★★ ()
Ограничение на отправку комментариев: только для зарегистрированных пользователей