1

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

我的问题是，我怎样才能使这种排序更有效率？

4

1 回答 1

2

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但是，如果您第一次输入该方法时有可能，那不一定是正确的 Shortest Seek Time First 排序。你的算法可能看起来像这样：

  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.

当然，您还需要在步骤 3中检查nextLowestIndex < 0和。nextHighestIndex >= positions.size()

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

于 2013-05-15T18:32:32.633 回答