Исправление victor79, (текущая версия) :
Но он за это хочет чтобы было быстрее 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, :
Но он за это хочет чтобы было быстрее 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;
}