c++ - 磁盘调度程序 SCAN 算法错误

Question

我有一个文件，其中有第一行，我想做扫描算法(电梯)来计算总距离。

队列大小为 32，总数据行为 35691

左端为0

右端是59999

ex:

queue size is 3

start from 0

left end is 0

right end is 255

all request:30, 150, 30, 10, 70

1.
head:0
quene:30, 150, 30
distance:0
2.
head:30
quene:150, 30, 10
distance:30
3.
head:30
quene:150, 10, 70
distance:30
4.
head:70
quene:150, 10
distance:70
5.
head:150
quene:10
distance:150
6.
head:10
quene:
distance:500(150 to right end 255 and come back to 10 --> 150 + (255 - 150) * 2 + (150 - 10))

我做的是下面的代码，我用multi set来存储，

the first stage I fill up the queue

the second stage I insert the next element first

if the direction is right now

to see whether there is element next to the current, if not, change the direction, else keep right moving.

if the direction is left now

do the same thing above but go to left 

the third stage I will calculate the remaining element in the queue.

我遇到的问题是我计算的距离

second stage is larger the result

，所以它可能有问题。而且我认为我认为是对的我想不通

哪里出错了

最终结果应该是33055962。

还有代码:

#include <iostream>
#include <fstream>
#include <string>
#include <set>
const int dataSize = 35691;
const int queueSize = 32;
const int minNumber = 0;
const int maxNumber = 59999;
using namespace std;

int number = minNumber;
int direction = 1;// right
int distanceSum = 0;
multiset<int> myset;
multiset<int>::iterator it;
multiset<int>::iterator temp;
multiset<int>::iterator next;
void print(void);

int main(int argc, char const *argv[]){
    ifstream myfile("sort");
    if (myfile.is_open()){
// ===============================initialization===============================
        for(int i = 0; i < queueSize; i ++){
            myfile >> number;
            myset.insert(number);           
        }
        it = myset.begin();
        int last = minNumber;
        int current = *it;
// ===============================middle stage===============================
        for(int i = 0; i < dataSize - queueSize; i ++){
            myfile >> number;
            myset.insert(number);
            current = *it;
            if(direction == 1){// right
                next = it;
                next ++;
                if(next == myset.end()){// right most
                    direction = 0;// change direction
                    distanceSum += ((maxNumber - current) * 2 + (current - last));
                    temp = it;
                    it --;
                    myset.erase(temp);
                    last = current;
                }
                else{
                    distanceSum += (current - last);
                    temp = it;
                    it ++;
                    myset.erase(temp);
                    last = current;
                }
            }
            else if(direction == 0){// left
                if(it == myset.begin()){// left most
                    direction = 1;// change direction
                    distanceSum += ((current - minNumber) * 2 + (last - current));
                    temp = it;
                    it ++;
                    myset.erase(temp);
                    last = current;
                }
                else{
                    distanceSum += (last - current);
                    temp = it;
                    it --;
                    myset.erase(temp);
                    last = current;
                }
            }       
        }
// ===============================remaining===============================
        // for(int i = 0; i < queueSize; i ++){
        //  current = *it;
        //  if(direction == 1){// right
        //      next = it;
        //      next ++;
        //      if(next == myset.end()){
        //          direction = 0;
        //          if(myset.size() == 1)distanceSum += (current - last);
        //          else distanceSum += ((maxNumber - current) * 2 + (current - last));
        //          temp = it;
        //          it --;
        //          myset.erase(temp);
        //          last = current;
        //      }
        //      else{
        //          distanceSum += (current - last);
        //          temp = it;
        //          it ++;
        //          myset.erase(temp);
        //          last = current;
        //      }
        //  }
        //  else if(direction == 0){

        //      if(it == myset.begin()){
        //          direction = 1;
        //          if(myset.size() == 1)distanceSum += (last - current);
        //          else distanceSum += ((current - minNumber) * 2 + (last - current));
        //          temp = it;
        //          it ++;
        //          myset.erase(temp);
        //          last = current;
        //      }
        //      else{
        //          distanceSum += (last - current);
        //          temp = it;
        //          it --;
        //          myset.erase(temp);
        //          last = current;
        //      }
        //  }       
        // }
        myfile.close();
    }
    else cout << "Unable to open file";
    print();
    cout << "distanceSum is :" << distanceSum << endl;
    return 0;
}
void print(){
    cout << "value:" << endl;
    for(multiset<int>::iterator it = myset.begin(); it != myset.end(); it ++){
        cout << *it << "\t"; 
    }
    cout << endl;
    cout << "current point to:" << *it << endl;
    cout << "total size is:" << myset.size() << endl;
    cout << "current distance:" << distanceSum << endl;
}

和测试数据:

https://drive.google.com/file/d/0ByMlz1Uisc9ONWJIdFFXaGdpSXM/edit?usp=sharing

你应该将它保存为文件名'sort'

Answer 1

我已经读了你的算法三遍了，我唯一能找到的错误是当你读到相同的值时。考虑一下，

• 你在位置 300 向左移动。

• 您将新元素插入队列中，位置也是“300”。

  Now in the multiset implementation according to this SO answer
  (http://stackoverflow.com/q/2643473) depending on the implementation
  the value can either go right to your present value(C++ 0x) or can go
  anywhere(C++03). 
  

• 因此，如果您位于位置 300 并假设新值插入到多重集中当前值的右侧。

• 您检查左侧并移动到较小的元素，或者如果您位于最左侧的位置，则在向下移动到位置 0 后开始向右扫描。而您应该首先访问位置 300 中的值，这是新的队列。

当您在右侧并且在当前值的左侧插入相同的值时，将发生相同类型的错误。

这是使用 3 的队列大小的说明。
考虑您的多集队列具有值 (300,700,900) 和方向 = 0，即左侧。右边带星号的数字表示迭代器所在的位置。让我们假设此时 totalSweepDistance=0。

• 您当前的队列 (300*, 700, 900)，totalSweepDistance=0，方向 =0
• 你读取了 300 并将其插入到队列中 (300*, 300, 700, 900)，totalSweepDistance=0, direction =0
• 您检查队列的开头并返回 true。你把移动的扫掠距离加到0，方向向右，然后到300，扫掠距离=600
• 你当前队列(300*, 700, 900)，totalSweepDistance=600 direction =1
• 您读取了一个低于 300 的新值，理想情况下，如果您没有改变方向并执行不需要增加扫描量的右扫描，则该值会在左侧扫描中读取。

解决方案

一个可能的解决方案是，当您向队列中插入一个与当前值相同的新值时。向左移动时检查当前位置右侧的一个位置，向右移动时检查当前位置左侧的一个位置以插入相同的值。