Похоже, вам нужно использовать алгоритм адаптивной сортировки .

«Алгоритм сортировки попадает в адаптивное семейство сортировки, если он использует существующий порядок во входе. Он извлекает выгоду из предвзятости во входной последовательности или ограниченного количества нарушений для различных определений мер беспорядка и сортируется быстрее. Адаптивная сортировка обычно выполняется путем изменения существующих алгоритмов сортировки ». - Статья Википедии, связанная выше.

Примеры включают сортировку вставки и Timsort; более подробно см. статью выше. Обратите внимание, что в Java 8 Arrays.sort(Object[])библиотечный метод использует модифицированный Timsort.

---

Я не знаю ни одного опубликованного алгоритма, который касается конкретных требований вашего примера, но вот идея:

1. Выполните классическое объединение на двух входных списках L1 и L2:

   • Когда вы объединяете пару объектов и меняете ключи, которые определяют порядок, поместите объединенный объект во временный список A.
   • В противном случае объекты будут помещены во временный список B ... который останется упорядоченным.

2. Сортировка временного списка A.

3. Списки слияния A и B.

При условии, что:

• длины исходных списков L1 и L2 являются M & N соответственно, и
• количество объединенных объектов, чьи ключи изменены, R (что меньше max (M, N)),

то общая сложность - O (M + N + RlogR). Если R мало относительно M + N, то это должно быть улучшением.

---

В вашем примере каждый случай, когда есть совпадение между элементами во входных списках , скорее всего, перемещает элемент в порядке. Если он перемещает элемент, он переместится на более поздний порядок (и никогда ранее). Таким образом, другая идея состоит в том, чтобы выполнить трехстороннее слияние между исходными 2 списками и очередью приоритетов. Когда вы получаете совпадение, вы объединяете счетчики и добавляете результат в очередь приоритетов.

Сложность похожа на предыдущую, но вы избегаете дополнительного прохода для объединения списков. А также RlogRстановится RlogAгде средний размер очереди приоритетов.

---

Имейте в виду, что меня особенно интересует случай, когда R приблизительно равен max (M, N), а также M == N.

(Вы не указали это в своем вопросе! И на самом деле для R не имеет значения> min (M, N)!)

В этом случае, возможно, просто используйте очередь приоритетов в качестве инкрементного сортировщика. Бросьте все объединенные записи и все записи, которые не могут быть объединены в очередь, и потяните наши записи, если у них есть ключ / счет, который меньше, чем текущие главы этих двух списков. Предполагая, что M и N - длины списка, а A - средний размер очереди приоритетов, тогда сложность max (M, N) * log A). Будет ли это улучшение простого повторного сортировки, будет зависеть от того, будет ли среднее значение A значительным (в терминах Big O) меньше, чем max (M, N). Это будет зависеть от входных данных ... и функции слияния.

---

Число (N) меняется, но типично 256-1000. Возможно, целых 10 000 человек.

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

---

Все это очень приблизительно, и мои математики в лучшем случае «отрывочны».

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

Похоже, вы хотите слияние O (n), как и при сортировке слияния. Думаю, у меня могут быть плохие новости. Я собираюсь (надеюсь) доказать, что вы не можете сделать лучше, чем O (nlog (n)) для обобщенной задачи: (поэтому, следовательно, вы должны просто использовать любой из оптимальных решений O (nlog (n)), представленных другими ). Во-первых, я начну с интуиции о том, почему это так, и тогда я напишу неофициальное доказательство.

Интуиция

Идея состоит в том, чтобы превратить проблему сортировки списка в вашу проблему и показать, что если вы можете решить свою проблему быстрее, чем O (nlog (n)), то я могу сортировать любой список быстрее, чем O (nlog (n)), который мы знаем, что это ложь. Мы просто будем работать с целыми числами, чтобы все было просто.

Предположим , у вас есть какая - то странная последовательность для сортировки: X = 1, 3, 2, -10, 5, 4, 7, 25. Теперь я создам два списка Dec и Inc., с которых я начинаю 1 = 1 + 0(т.е. x_1 = x_1 + 0). Затем после этого, если x_{i-1} -> x_iэто увеличение, я вычитаю 1 из моего значения в Dec и вычисляю необходимое значение в Inc для суммирования x_i. Если x_{i-1} -> x_iэто уменьшение, то я добавляю 1 к моему значению в Inc и вычисляю необходимое значение в Dec для суммирования x_i. Мы применяем этот алгоритм к последовательности в следующей таблице:

idx   x     Dec    Inc      
----------------------
 1 |  1  =  1   +  0
 2 |  3  =  0   +  3
 3 |  2  =  -2  +  4
 4 | -10 =  -15 +  5
 5 |  5  =  -16 +  21
 6 |  4  =  -18 +  22
 7 |  7  =  -19 +  23
 8 |  25 =  -20 +  45

Обратите внимание, что я могу преобразовать из сортировки в вашу проблему в O (n) - note: reverse Inc в O (n) раз, чтобы получить две уменьшающиеся последовательности. Затем мы можем ввести вашу проблему

A = {(1, 1), (2, 0), (3, -2), (4, -15), (5, -16), (6, -18), (7, -19), (8, -20)}
B = {(8, 45), (7, 23), (6, 22), (5, 21), (4, 5), (3, 4), (2, 3), (1, 0)}

Теперь, если вы можете комбинировать A и B в отсортированном порядке по сумме их значений (второй элемент в упорядоченных парах) и получить что-то вроде

C = {(8, 25), (7, 7), (5, 5), (6, 4), (2, 3), (3, 2), (1, 1), (4, -10)

то вы по существу сделали argsort (сортировать по индексу) начальной последовательности x_i. Поэтому, если вы решите свою проблему быстрее, чем O (nlog (n)), я могу сортировать быстрее, чем O (nlog (n)), сначала решая проблему, а затем преобразовывая решение в мою проблему сортировки списка. В частности, я бы сортировал со сложностью O (n) + O (сложность для решения вашей проблемы)

Заявление должно быть доказано

Пусть ваши два списка ключевых значений

A = [(ka_i, va_i) | i = 1..n]
B = [(kb_i, vb_i) | i = 1..m] 

сортируются в порядке убывания стоимости. Вы не можете найти объединенный список

C = [(ka_i, va_i + va_j) | ka_i = kb_j]

быстрее, чем O (nlog (n)).

Доказательство

Единственное предположение, которое дает это доказательство, заключается в том, что вы не можете сортировать список быстрее, чем время O (nlog (n)), и это доказательство будет продолжено путем предоставления сокращения, которое выполняется в O (n) времени, от сортировки любого произвольного списка до вашей проблемы.

В сущности, мы покажем, что если мы решим вашу проблему быстрее, чем O (nlog (n)), мы также можем отсортировать любой произвольный список быстрее, чем O (nlog (n)). И мы уже знаем, что сортировать список невозможно быстрее, чем nlog (n), поэтому ваше желаемое решение также должно быть невозможным.

Детали доказательства

Для простоты мы будем сортировать список целых чисел. Пусть S = x_1, x_2, ..., x_n- любая последовательность целых чисел. Теперь мы построим два списка: Dec и Inc.

У нас есть три ограничения:

1. Inc строго возрастает
2. Dec строго снижается
3. На итерации i алгоритма, Inc[j] + Dec[j] = x_j for all j = 1..i-1

Поскольку их имена подразумевают, Dec будет строго снижаться, а Inc будет строго возрастать. Мы будем поддерживать инвариант, которыйx_i = Dec[i] + Inc[i] for i = 1..n

Вот сокращение:

# (Assume 1-indexed lists)
1. Initialize Inc = [x_1] and Dec = [0]
2. For i = 2..n:
    a. if x[i] > x[i-1] then
          Dec.append(Dec[i-1] - 1)
          Inc.append(x_i - Dec[i])
       else   # We must have x[i] <= x[i-1]
          Inc.append(Inc[i-1] + 1)
          Dec.append(x_i - Inc[i])

3. Create list A and B:
    A = [(i, Dec[i]) | i = 1..n]
    B = [(i, Inc[i]) | i = 1..n]
4. B = reverse(B) # Reverse B because B was in increasing order and we
                  # need both lists to be in decreasing order
5. A and B are inputs to your algorithm.
  If your algorithm can combine A and B into sorted order,
  then we have also sorted S (via argsort on the keys).

Вероятно, вы тоже голодны за доказательство того, что мой ad hoc метод выбора увеличения Inc на 1 или уменьшение Dec на 1 работает. Ну вот неофициальное «доказательство» (вы можете его формализовать, используя индукцию):

Случай x_ {i}> x_ {i-1}

Напомним, что в этом случае мы выбираем декремент Dec на 1. Нам дано это, Dec_{i-1} + Inc_{i-1} = x_{i-1}и мы это знаем (Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}. Мы также можем сказать это x_{i} > x_{i-1}.

Так как x_{i} > x_{i-1}мы должны иметь x_{i} >= x_{i-1} + 1. Поэтому x_{i} >= (Dec_{i-1} - 1) + (Inc_{i+1} + 1). Поэтому, если мы уменьшаем Dec на 1, мы будем вынуждены добавить не менее 1 к Inc, поэтому Inc остается строго возрастающим.

Случай x_ {i}? X_ {я-1}

Напомним, что в этом случае мы выбираем инкремент Inc на 1. Нам дано это, x_{i} <= x_{i-1}и мы это знаем Dec_{i-1} + Inc_{i-1} = x_{i-1}. Мы также можем сказать это, (Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}и, поскольку x_{i} <= x_{i-1}это должно быть так (Dec_{i-1} - 1) + (Inc_{i+1} + 1) <= x_{i}. Поэтому, если мы добавим 1 к Inc, мы уверены, что мы должны вычесть по крайней мере 1 с декабря.

Вывод

Ваша проблема не может быть выполнена быстрее, чем O (nlog (n)). Вам лучше просто объединиться в HashMap, а затем отсортировать его элементы в O (nlog (n)), потому что невозможно найти более быстрое решение.

Не стесняйтесь комментировать, однако, если вы обнаружите проблему с сокращением или имеете вопросы. Я почти уверен, что это правильно. Конечно, если я ошибаюсь в том, что сортировка не быстрее O (nlog (n)), все это доказательство разваливается, но в последний раз я проверял, что кто-то уже доказал, что O (nlog (n)) - самая быстрая сложность сортировки , Комментарий, если вы предпочитаете формальное сокращение. Сейчас мне стало поздно, и я пропустил некоторые «формализации», но я могу изменить их, когда у меня появится шанс.

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

Также: см. Этот пост, если вы хотите объяснить привязку O (nlog (n)) к сортировке. Каковы правила для «? (N log n) барьера» для сортировки алгоритмов?

(Отклонение для первого слияния, а затем повторного сортировки). Мой первый удар будет состоять в том, чтобы объявить отсортированные входные списки (полустатические) очереди приоритетов и действовать в два этапа. Чтобы избежать двусмысленности в терминах слияния , я буду называть создание / изменение объекта для представления значений «общих объектов» comb / combination ; чтобы уменьшить беспорядок, я буду обозначать приоритетную очередь PQ.

1. идентифицировать объекты, которые появляются в обеих / более одной «входной очереди»
   (в качестве второстепенного интереса здесь)
   • (возможно, недействительность позиции в любом списке),
   • поместите их в другой (динамический) PQ (если необходимо)
   • удалить из / invalidate в очереди (вводах), где они больше не будут.
2. Слияние PQ обычным способом

Это должно работать в линейном времени в числе n объектов, плюс O (c log c) для c "обычных" объектов, где объединенный объект будет несовместим вместо любого объединенного объекта. (ожидаемое постоянное время, чтобы (идентифицировать и) объединить один (набор общих) объектов ( см. примечание о ожидаемом O (1) в вопросе))
Затем, боюсь, что неправильно адресовано главное:

Есть ли способ извлечь выгоду из заключительного ключа, чтобы быть (линейной, монотонной)
комбинацией, по крайней мере, одной упорядоченной последовательности и «других значений»?
(С большим количеством общих записей - все думают ).

Если комбинация уменьшает приоритет монотонно (в примере добавление (положительных) значений оценки увеличивает приоритет), обойтись без фазы объединения и объединить объекты при слиянии PQ, что потенциально уменьшает память и время.
В противном случае выберите один PQ для извлечения объектов (уменьшая приоритет), чтобы потенциально объединиться с другими объектами.
«Наихудший случай» может показаться приоритетом комбинированных объектов, не показывающих корреляции: я боюсь, что ответ
вообще нет . (см . ответ пользователя2570465 для явного аргумента)
(как указывает BeeOnRope , выбранные объекты (последовательность), которые доминируют в комбинации (невыгодный выбор), могут фактически превратиться в хороший случай, если это можно обнаружить и использовать.)
Затем снова ( линейная, монотонная) комбинация может искажать распределение ключей даже без (положительной) корреляции (предполагается в вопросе): обязательно используйте (динамическую) реализацию PQ, где вставка в порядке - лучший случай, а не худший:
Во-первых, возьмите неявную кучу в массиве (дочерние элементы из индекса i находятся в 2i и 2i + 1 (или 2i + 1 & 2i + 2 ", не теряя при этом элемент 0", но немного больше манипуляции с индексами):
просто добавьте предметы (с распределением перекос в уменьшении приоритета ) до конца: ожидается , количество обменов с родителем ниже 1 (будет почти 1 без перекоса).

1. Ведите карту, которая отображает что-то уникальное для фактической информации Студента.

   Map<String, Student> scores = new HashMap<>();
   

2. Перебирайте все списки и помещайте их в карту баллов

   for (Student s : list1) {
       if (scores.containsKey(s.name)) {
           scores.put(s.name, s.score + scores.get(s.name));
       } else {
           scores.put(s.name, s.score); 
       } 
   }
   

3. Сортировка entrySet с использованием потоков Java 8

   scores.entrySet()
     .stream()
     .sorted((s1, s2) -> (s2.getValue().score - s1.getValue().score)
     .map(s1 -> s1.getValue())
     .collect(Collectos.toList());
   

Это все еще O(N Log N)

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

Мне кажется, что любое решение должно вообще относиться к категории сложности O (n * log (n)) (с n = длина (L1) + длина (L2), или n = max (длина (L1), длина ( L2))).

Моим основным алгоритмом было бы следующее

  Let's use two intermediate structures:
  - a TreeSet R, which guarantees ordering by rank, 
  - an HashMap M, which guarantees constant time insertion and retrieve 
  Call R's size n

  1 for each student in each list
      1.1 find the student in M by name (O(1)).
      1.2 if the student is found          
         1.2.1 find the student in R by its rank (O(log(n)).  
         1.2.2 remove the student from R (O(log(n))
         1.2.3 update the student rank 
      1.3 else 
        1.3.1. put the student in M O(1)
      1.4 put the student in R (O(log(n))
  2 At the end (if needed) transform the TreeSet in a list

Общая сложность O - это O (n * log (n)),

Предполагая, что L1 является самым длинным из 2 списков, небольшая оптимизация будет избегать поиска ученика при обходе L1, в этом случае сложность O будет одинаковой, но вы будете иметь меньше операций в абсолютном. Лучший случай - конечно, когда Len (L1) >> Len (L2).

Могут быть более сложные решения или лучшие структуры данных для сокращения числа операций, но я не думаю, что может быть более сложная O-сложность, так как в основном у вас есть 2 возможности

1 - упорядочивание списка результатов, поэтому списки сканирования, поиск совпадений и повторное вычисление позиции каждый раз

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

Обе возможности обычно вычисляются в O (n * log (n))