Сортировать набор чисел, когда отсортированный суперсет доступен

Question

• У меня есть набор A = {5,4,2,8}
• У меня есть набор B = {1,2,4,5,7,8,9}, которыйsorted
• A задано как подмножество B

Я хочу отсортировать A (возможно, используя B (или даже с некоторой разумной предварительной обработкой)). В общем, я хочу быть в состоянии отсортировать много таких произвольных «как» (все подмножества B) для данного B. Какое наилучшее время, когда это может быть достигнуто?

Два наивных решения приходят кразум.

• Сортировка A независимо (O (A log A))
• Сканирование B и выбор элементов, которые отображаются в A (O (B)).

Когда A маленький, первый явно лучше, когда A почти такой же большой, как B, второй лучше. Однако когда, скажем, в B есть что-то вроде 10 ^ 10 элементов, а в A есть 10 ^ 5, можем ли мы добиться большего успеха, чем любой из этих методов?

Answer 1

Кроме того, неясно, как ваше второе решение достигает O (| B |). Когда вы сканируете B , как вы "берете элементы, которые появляются в A "? Звучит так, будто где-то должен быть лог A .

Лучшее, что я могу внести - это автономный алгоритм, который сортирует множество A в O (| B | + L ), где L - сумма длин всех A . Под «оффлайн» я имею в виду, что вы можете заранее прочитать все A .

1. Предварительная обработка B и построить значения отображения хеш-таблицы в B на свои позиции. Для вашего примера хеш-таблица имеет вид (1 -> 1, 2 -> 2, 4 -> 3, 5 -> 4, 7 -> 5, 8 -> 6, 9 -> 7).
2. Сохраните связанный список для каждого элемента в B , изначально пустом.
3. Сканируйте все A . Если A_i [ j ] = k , тогда добавьте i в связанный список k . Мы можем быстро найти связанный список k (он же позиция k в B ), используя хэш-таблицу. В вашем примере предполагается, что A является первым вектором, который мы читаем из входных данных, а поскольку A _1 [4] = 8, мы добавляем 1 в связанный список 8 в B .
4. Очистка массивов A .
5. Сканирование B и вставка элементов в массивы A ,Например, если связанный список 8 содержит значения 1, 4 и 20, поместите значение 8 в 1-й, 4-й и 20-й массив.

На практике это нехватка памяти,Ваше ограничение 10 ^ 10 64-битного числа уже предполагает 80 ГБ доступной оперативной памяти. Хеш-таблица требует как минимум в три раза больше этой суммы. Хранение всех A в памяти и связанных списках также требует не менее 3 L 64-битных значений.

Я очень скептически отношусь к практическому онлайн-алгоритмусуществует, который хорошо использует B для обработки одного A за один раз. Даже если предположить, что вы можете искать позиции в B в O (1) (например, с помощью хеш-таблицы), это сужает область ваших элементов в A с 64 бит до 34 (10 ^ 10 округлено). Таким образом, сортировка с подсчетом все еще непригодна, так как последний шаг требует сканирования области из 10 ^ 10 значений для сортировки массива из 10 ^ 5 элементов. Оффлайн алгоритм по сути окупается за огромное сканирование, сортируя все массивы сразу.