Сортировка 1 трлн целых чисел

Question

Учитывая набор из 1 триллиона целых чисел на жестком диске, найдите самый маленький из них 1 миллион. Вы можете разместить в памяти не более 1 миллиона целых чисел за раз.

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

Есть ли более оптимальный подход, который мне не хватает?

Answer 1

Вы можете сделать это эффективно в O (n log m), используя heap .(n = все числа, m = размер набора чисел, которые вы хотите найти).

Пройдите триллион чисел по одному за раз.Для каждого нового номера выполните одно из следующих действий.

1. Если в куче <1 миллион узлов, вставьте новый номер в кучу. </li>
2. Если в куче ровно 1 миллион узлов иверхний узел> больше, чем новый номер, затем извлеките верхний узел из кучи и вставьте узел с новым номером.
3. Если ни 1, ни 2 не являются истинными, бросьте номер.

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

Вставка и удаление из кучи - это O (log m).Один проход через кучу - это n.Итак, алгоритм n * log (m)

Answer 2

Насколько велики целые числа?Если бы они были просто 32-битными значениями, я просто создал бы массив из 4 миллиардов 64-битных счетчиков на диске, и, обнаружив на входе x, увеличил счетчик в позиции x.В общем случае этот подход чрезвычайно дорог в пространстве, но пропорционально он является низким, когда диапазон возможных значений элементов намного меньше количества сортируемых элементов, и, что лучше всего, это O(n) во времени.

Answer 3

Решение в скале, но не для 1 триллиона элементов.С указателем на файл вместо списка или несколькими небольшими списками это можно сделать следующим образом:

def top (n: Int, li: List [Int]) : List[Int] = {

  def updateSofar (sofar: List [Int], el: Int) : List [Int] = {
    // println (el + " - " + sofar)
    if (el < sofar.head) 
      (el :: sofar.tail).sortWith (_ > _) 
    else sofar
  }

  /* better readable:
    val sofar = li.take (n).sortWith (_ > _)
    val rest = li.drop (n)
    (sofar /: rest) (updateSofar (_, _)) */    
  (li.take (n). sortWith (_ > _) /: li.drop (n)) (updateSofar (_, _)) 
}

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

Answer 4

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

Все, что вам нужно сделать, это:

1. Найти миллионное наименьшее число, разделив диск несколько раз на все более мелкие разделы.Это занимает время O (n).

2. Возьмите его и другие 999 999 целых чисел, которые разобрал раздел, и поместите их в ОЗУ.Вы закончили.

Наименьший миллион целых чисел не будет отсортирован, но он будет наименьшим миллионом.

Если затем вы хотите отсортировать наименьший миллион, онзаймет время O (m log m), где в этом случае «m» - это миллион.

Пространство без затрат, время O (n), работает с нецелыми значениями.Наслаждаться.:)