Ожидаемое время сортировки с помощью внешнего алгоритма сортировки

Question

Кто-нибудь знает, что будет минимальным ожидаемым временем (в секундах?) Сортировки, скажем, бинарным файлом в 64 МБ из 32-битных целых чисел, что означает сортировку 16777216 значений в порядке возрастания, без использования каких-либо внутренние алгоритмы сортировки или структуры данных, которые могут запускать «исключения из памяти»? Просто распределение данных в двух вспомогательных файлах, а затем их объединение вместе для создания окончательной упорядоченной последовательности - вот как работает прямая внешняя сортировка слияния с k повторений.

Некоторые дополнительные предположения об алгоритме заключаются в том, что он написан на Java, он использует буферизованные считыватели и писатели, и он работает на двухъядерной машине Windows с 5 ГБ памяти, а остальное зависит от того, как алгоритм работает в теории.

Я знаю, что вопрос немного странный, но какое-то минимальное время можно оценить, надеюсь? Если вам нужна дополнительная информация, спросите.

ThankS!

Answer 1

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

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

Во втором проходе используется объединение k-way для объединения временных файлов в один отсортированный выходной файл. Опять же, каждый элемент снова читается один раз с диска и записывается один раз на диск.

Если входной файл уже отсортирован, а алгоритм сортировки блоков хорошо реализован, тогда время сортировки отдельных блоков почти ничего. То же самое с слиянием: уже отсортированный файл является наилучшим вариантом для слияния k-way.

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

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

По моему опыту, хорошая оценка времени, необходимого для слияния k блоков (т.второй проход) довольно близко к однако времени требуется, чтобы скопировать файл ввода раза лога (журнал (количество блоков)):

время слияния = (время копирования) * (войти (журнал (количество блоков)))

Скажем, у меня есть 1 ГБ файл, и я использую блоки 64 МБ. Таким образом, есть 16 блоков для слияния. Я уже решил, что для копирования гигабайта требуется одна минута. Таким образом, хорошая оценка времени, необходимого для слияния, составляет один минутный лог (журнал (16)). log(log(16)) равно 2, поэтому для объединения 16 входных файлов требуется примерно в два раза больше, чтобы просто скопировать один файл с комбинированным размером.

Когда вы все это вместе, вы в конечном итоге следующим для оценки времени, необходимого, чтобы сделать ваш типичный внешний вид размера файла S используя размер блока B

• Время скопировать (прочитать и записать) файл размером S; плюс
• Время сортировки S/B блоки; плюс
• Время копирования (чтение и запись) файл размером S, раз войти (журнал (S/B))

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

Answer 2

Вы должны подумать об использовании ObjectInputStream. Было бы намного проще и быстрее, и потому, что Integer реализует Serializable, это делает его намного проще. См.:

long howLong(String path) throws IOException, ClassCastException{ 
    long start = System.currentTimeMillis(); 
    ObjectInputStream ois = new ObjectInputStream(new FileInputStream(new File(path))); 

    List<Integer> allInts = new ArrayList<>(); 
    while(ois.ready()){ 
     allInts.add((Integer)ois.readObject()); 
    } 
    ois.close(); 
    sortList(allInts); 

    ObjectOuputStream oos = new ObjectOutputStream(new FileOutputStream(newFile(path))); 

    for(Integer i:allInts){ 
     oos.writeObject(i); 
    } 
    oos.close(); 
    long end = System.currentTimeMillis();  

    //returns how long the alg took 
    return (end-start)/1000; 
} 

private <E extends Comparable<E>> void sortList(List<E> l){ 
    boolean sorted; 
    while(!sorted){ 
     soreted=true; 
     for(int i=0,n=l.size()-1;i<n;i++){ 

      if(arr1[i].compareTo(arr1[i+1])>0){ 
       E tmp = l.get(i); 
       l.get(i) = l.get(i+1); 
       l.get(i+1) = tmp; 

       sorted = false; 
      } 
     } 

    } 


} 

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