java - 对大 vector 进行排序的快速方法

Question

我有一个非常大的 vector ，可以存储 100000 个不同的值，范围从 0 到 50000。 它们代表硬盘上的柱面，我想根据用于磁盘调度的三种不同算法对这个 vector 进行排序。 到目前为止，我从文件中读取了这 100000 个值，将它们存储到一个 vector 中，然后根据所需的算法(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;
}

我的函数将一个 vector 作为参数，对其进行复制，进行一些数学运算以从复制的数组中找到所需的元素并将其存储在另一个数组中，该数组应根据所选算法进行排序。一个有 N 个元素的数组，它占用了 N!迭代来完成，这太多了，因为代码应该至少执行 10 次。

我的问题是，如何才能使这种排序更加高效？

Answer 1

Java 已经有内置的方法来对 List 进行排序很快；参见Collections.sort .

Vector已过时，并且由于其同步开销而导致性能损失。使用List改为实现(例如 ArrayList )。

也就是说，根据您问题的内容，听起来您在实现最短寻道时间优先算法方面遇到了困难。

查看相关问题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 中。

请注意，您不需要在 while 循环内使用 for 循环，但您可以在进入 while 循环之前在步骤 2 中使用该循环。