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

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

Требуется реализовать функцию, которая принимает на вход массив из N элементов (тип не важен) и массив из M функций, которые могут быть вычислены от этих элементов и возвращают целочисленные значения. Реализуемая функция должна возвращать массив индексов элементов (из входного массива) в отсортированном массиве, никакого реального перемещением элементов с места на место не требуется. Сортировка идет по множеству ключей, которыми являются целочисленные значения, возвращаемые из соответствующих функций. Если для двух различных элементов первые ключи (то есть значения возвращаемые первой функцией) совпадают, то их порядок определяется по вторым ключам (значениям возвращаемым второй функцией), и.т.д. Дважды вычислять одну и ту же функцию от одного и того же элемента нет смысла. Также нет смысла производить вычисления, которые не необходимы для сортировки (фактически только первая функция будет вычисляться для всех элементов в любом случае). Плюс ко всему, память не резиновая, ее расход нужно по возможности сократить.

Я прихожу к выводу, что в худшем случае расход памяти составит O(N*M), что мне очень не нравится. Кто считает, что можно обойтись меньшими объемами, будет очень интересно услышать идеи. Также мне не нравится необходимость частых вызовов на динамическое выделение памяти.

На счет самого алгоритма: у меня в голове крутятся какие-то идеи насчет построения бинарных деревьев на каждом уровне сортировки, затем финальный проход по горизонтали сквозь весь "лес" для формирования выходного массива индексов. Но поиск/вставка в б-деревья требуют O(log N), а мне нужно O(1), как для линейных массивов. Но с линейными массивами я не смогу сэкономить память и получу N*M по объему даже для лучшего случая, а я уверен, что можно обойтись гораздо меньшими объемами за исключением худшего случая.
Возможно, я все усложняю, и существует какой-то простой и очевидный алгоритм.

Уважаемые коллеги, поделитесь своими соображениями по сабжу.

P.S.: ЯП в тегах условные.
  • Вопрос задан
  • 652 просмотра
Пригласить эксперта
Ответы на вопрос 2
AtomKrieg
@AtomKrieg
Давай я поищу в Google за тебя
Есть предложение кэшировать значения функций вычисления ключа в какой-нибудь HashMap<Pair<N,M>, key_value>. Должно сработать если функции дольше вычислять чем возится с кэшем.
Примерный код:
https://gist.github.com/AtomKrieg/6fb6d3d8ae80842e...
Ответ написан
@bizon2000
Java-программист
Я думаю, что соответствующий алгоритм на псевдокоде можно изобразить как-то так:

Создадим массив из N элементов типа Node и проинициализируем его:
class Node {
    int group;
    int key;
    int index;
}

Node[N] nodes;

for (int i = 0; i < N; i++) {
    nodes[i].group = 0;
    nodes[i].index = i;
}


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

Теперь будем сортировать этот массив в цикле по функциям, в каждой итерации мы будем ужесточать порядок в группах, которые содержат более одного элемента, т.е., еще не отсортированы:
for (int j = 0; j < M; j++) {
    // для каждой группы, содержащей более одного элемента
        // вычисляем значение ключа в каждом элементе этой группы
        // сортируем на месте элементы этой группы по этому ключу
        // разбиваем группу на подгруппы с одинаковым значением ключа, присваиваем подгруппам уникальные номера
    // если все группы содержат ровно по одному элементу, то досрочный выход из цикла
}


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

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

После завершения цикла все элементы в массиве nodes отсортированы, для ссылки на элементы исходного массива используется значение поля index.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Wunder Fund Москва
от 120 000 до 150 000 ₽
АКМЭ сервис Санкт-Петербург
от 120 000 ₽
Eltex Новосибирск
от 80 000 ₽
28 мая 2020, в 22:27
5000 руб./за проект
28 мая 2020, в 21:46
20000 руб./за проект
28 мая 2020, в 21:42
10000 руб./за проект