Быстрый способ сортировки действительно большой вектор

Question

У меня есть действительно большой вектор, который хранит 100000 различных значений, от 0 до 50000. Они представляют собой цилиндры на жестком диске, и я хочу сортировать этот вектор по трем различным алгоритмам используется для планирования диска. До сих пор я считывал эти 100 000 значений из файла, сохранял их в векторе, а затем сортировал их по желаемому алгоритму (FCFS, SCAN, SSTF). Проблема в том, что это занимает слишком много времени, потому что я делаю это в наименее творческом пути возможным:

public static Vector<Integer> sortSSTF(Vector<Integer> array){ 

    Vector<Integer> positions = new Vector<Integer>(array); 

    Vector<Integer> return_array = new Vector<Integer>(); 

    int current_pos = 0,minimum,final_pos; 

    while(positions.size() > 0){ 
     minimum = 999999; 
     final_pos = current_pos; 

     for(int i=0 ; i < positions.size() ; i++){ 
      //do some math 
     } 
    } 
    return_array.add(final_pos); 
    current_pos = final_pos; 
    positions.removeElement(final_pos); 
    } 
return return_array; 
} 

Моей функция принимает вектор в качестве параметра, делает копию, делает некоторую математику, чтобы найти нужный элемент из скопированного массива и хранить его в другом массиве, то должен быть упорядочен в соответствии с выбранным алгоритмом. Но в массиве с N элементами он принимает N! итераций для завершения, что слишком много, так как код должен делать это как минимум 10 раз.

Вопрос в том, как я могу сделать эту сортировку более эффективной?

Answer 1

Java уже имеет встроенные методы для сортировки List очень быстро; см. Collections.sort.

Vector является старым и несет штраф за исполнение из-за его накладных расходов на синхронизацию. Используйте вместо этого реализацию List (например, ArrayList).

Это говорит о том, что, основываясь на содержании вашего вопроса, похоже, что вместо этого вы испытываете трудности с внедрением алгоритма Shortest Seek Time First.

См. Соответствующий вопрос Shortest seek time first algorithm using Comparator.

Я не думаю, что вы можете реализовать алгоритм SSTF или SCAN, если вы не поставили текущую позицию головы в качестве аргумента в свой метод сортировки. Если предположить, что начальное значение current_postion всегда 0 будет просто дать вам список отсортирован в порядке возрастания, в этом случае ваш метод будет выглядеть следующим образом:

public static List<Integer> sortSSTF(List<Integer> cylinders) { 
    List<Integer> result = new ArrayList<Integer>(cylinders); 
    Collections.sort(result); 
    return result; 
} 

Но это не обязательно будет правильным Кратчайший время поиска Первый если вам когда-либо понадобится метод current_pos > 0. Ваш алгоритм будет, вероятно, искать что-то вроде этого:

1. Collections.sort(positions);
2. найти индексы в положениях, которые содержат позиции nextLowest и nextHighest относительно current_pos (или currentPos, если следующие Java именования)
3. какой бы ни положение ближе, удалите это положение с positions и добавьте его в return_array (если было nextLowest, а также декремент nextLowestIndex.Если было nextHighest, приращение nextHighestIndex)
4. повторите шаг 3 до тех пор, пока не будут опущены
5. return return_array.

Конечно, вам также необходимо будет проверить на nextLowestIndex < 0 и nextHighestIndex >= positions.size() на шаге 3.

Обратите внимание, что вам не нужен цикл for внутри цикла while, но вы должны использовать этот цикл на шаге 2, прежде чем вводить цикл while.