Это не классический вопрос о "слиянии двух отсортированных" списков, который довольно тривиальный в линейном времени.
То, что я пытаюсь сделать, это объединить два списка пар (key, value), уже отсортированных по value, где в обоих списках есть объекты с тем же key: такие объекты должны иметь слияние value (добавлено), что может изменить порядок сортировки. Меня в первую очередь интересует, как сортировка может быть эффективно выполнена с использованием информации из уже отсортированных списков, поскольку сортировка является самой медленной частью этого алгоритма.
Возьмем конкретный пример. Представьте себе List объектов Student:
class Student {
final String name;
final int score;
...
}
Учитывая, что в качестве входных данных два List<Student> отсортированы по score, я хотел бы создать новый объединенный список студентов, где любой учащийся (идентифицированный Student.name), появляющийся в обоих списках, появляется один раз в конечном списке, с оценка, равная сумме их оценки в обоих списках. Исходные списки должны быть оставлены без изменений.
Например,
List 1:
{"bob", 20}
{"john", 15}
{"mark", 14}
List 2:
{"bill", 11}
{"mark", 9}
{"john", 1}
Result:
{"mark", 23}
{"bob", 20}
{"john", 16}
{"bill", 11}
Слияние (идентификация учеников, отображаемых в обоих списках) может быть выполнено в ожидаемое время O (1) с использованием любой структуры поиска/вставки O (1), такой как HashMap. Меня больше всего интересует шаг сортировки (хотя я не исключаю решения, которые объединяют и сортируют в одно и то же время).
Вопрос, однако, в том, как эффективно пересобирать такой список? Упорядочение существующих списков явно ограничивает конечную позицию элементов в объединенном списке. Например, если студент находится в позиции i в первом списке и j во втором, он должен появиться среди первых учеников i + j в объединенном списке простым аргументом, анализирующим максимальное количество студентов, которые могли бы имеют более высокий балл. Однако не сразу понятно, была ли эта информация полезной при сортировке списка.
Можно предположить, что во многих случаях учащиеся, которые высоко оценивают в одном списке, высоко оценивают друг друга. Алгоритм должен работать, если это не так, но он дает вам дополнительную информацию о дистрибутиве, которая может быть полезна, в дополнение к тому, что списки уже отсортированы.
Кажется, что этот тип операции был бы общим для любого типа распределенной реализации запросов + сортировки. Например, представьте себе "select state, count (*) group by state" тип проблемы запроса для распределенной системы (чтобы подсчитать количество записей в каждом состоянии) - естественно, вы получите отсортированный список (state, count ) возвращает объекты из каждого node, а затем вы хотите объединить и повторно сортировать их во время операции уменьшения. Кажется глупым отбросить всю работу, уже сделанную на распределенных узлах.
Количественные примечания
Меня интересует случай, когда списки, которые должны быть объединены и пересортированы, невелики: обычно около 256 записей. Диапазон баллов варьируется от 0 до 100 в некоторых случаях, до примерно 0 - 10 000 000 в других. Конечно, учитывая небольшое количество элементов, каждая операция будет быстрой в абсолютном времени, даже с наивными алгоритмами - но выполняется в миллиарды раз, она складывается.
Фактически, один из приведенных ниже ответов доказал, что вы не можете, в общем, сделать это лучше, чем простой способ для увеличения размеров списка (т.е. взяв n, чтобы быть объединенным размером списка), - но я на самом деле больше заинтересован в том, чтобы делать это много раз, для списков фиксированного размера, с хорошей эмпирической производительностью.
