5

Hace poco estuve un tiempo tratando de implementar el algoritmo llamado Shortest Seek Time First (SSTF) a base de simulación, sin embargo me estoy quedando sin tiempo y no logro descubrir como implementar bien el algoritmo, ya que lo tengo logrado a medias, el algoritmo parte de algo llamado cilindros donde un cilindro simula ser las regiones por donde se va a mover la aguja del disco duro, en pocas palabras, por donde va a pasar primero la aguja del disco duro.

El algoritmo SSTF funciona con base a la menor distancia que hay que recorrer de un cilindro a otro, es decir, el orden es por menor distancia que hay que recorrer para llegar de un cilindro a otro, yo tengo hecho lo siguiente:

const timeList = new Array(4);

timeList[0] = {name: 'Open paint', time: 1000, cilinder: 83};
timeList[1] = {name: 'Open word', time: 2000, cilinder: 90};
timeList[2] = {name: 'Open photoshop', time: 4000, cilinder: 43};
timeList[3] = {name: 'Open gimpp', time: 3000, cilinder: 87};

function orderByLessCilinderDistance(processList){

    let procList = new Array(...processList);

    outer: for(let i = 0; i < procList.length - 1; i++){
        for(let j = i + 1; j < procList.length; j++){
            if(i > 0){
                if(Math.abs(procList[i].cilinder - procList[j].cilinder) > Math.abs(procList[i - 1].cilinder - procList[i].cilinder)){
                    const swap = procList[i];
                    procList[i] = procList[j];
                    procList[j] = swap;
                }
            }else{
                continue outer;
            }
        }
    }

    return procList

}

console.log(orderByLessCilinderDistance(timeList));

Donde casí lo tengo hecho, es decir lo que me retorna la función orderByLessCilinderDistance es:

[
  {
    "name": "Open paint",
    "time": 1000,
    "cilinder": 83
  },
  {
    "name": "Open gimpp",
    "time": 3000,
    "cilinder": 87
  },
  {
    "name": "Open photoshop",
    "time": 4000,
    "cilinder": 43
  },
  {
    "name": "Open word",
    "time": 2000,
    "cilinder": 90
  }
]

Lo cuál si es correcto, excepto los ultimos dos, debido a que el orden deberia ser así:

cilinder: 83,
cilinder: 87,
cilinder: 90,
cilinder: 43

Debido a que según este orden de 83 a 87 hay solo 4, de 87 a 90 hay solo 3, de 90 a 43 esta la distancia mas larga, (los primeros dos son correctos debido a que si en vez de poner 87 de primero, pusiera 90, entonces la distancia ya no sería 4 en el primero, sería 7, lo cuál es erroneo para el algoritmo).

Que cambios o arreglos puedo hacer a mi código para obtener el resultado que deseo?, ya intente un sort personalizado, pero igual me lo ordenaba de menor a mayor o de mayor a menor, pero no este orden que quiero.

Tener en cuenta que el primer elemento siempre será el primero, osea el primero es el punto de partida y siempre va a estar en el mismo sitio, los otros deberán ordenarse de acuerdo a la distancia minima o recorrido mas corto entre estos y el primero ya sea que el numero sea mayor al cilindro o sea menor, lo que cuenta es ordenar de acuerdo a las distancias que hay entre un cilindro y el otro partiendo del primer elemento y que el primero siempre sea el primero.

1 respuesta 1

1

La razon por la que falla es porque realmente nunca estas calculando la distancia que hay del punto de inicio con respecto a todos los demas

Si prestas atención, siempre estas intercambiando si la distancia de i-j > i-(i-1).

Solución:

Lo que deberías hacer es primero calcular la distancia a todos y luego intercambiar con el que este más cerca.

let timeList = [{
  name: 'Open paint',
  time: 1000,
  cilinder: 83
}, {
  name: 'Open word',
  time: 2000,
  cilinder: 90
}, {
  name: 'Open photoshop',
  time: 4000,
  cilinder: 43
}, {
  name: 'Open gimpp',
  time: 3000,
  cilinder: 87
}];

function orderByLessCilinderDistance(processList) {

  let list = [...processList];
  let i = 1; // salteamos el 0
  for (i; i < list.length; i++) {

    // Buscamos el que este a menor distancia del anterior
    let idx = 0;
    let minDistance = Infinity;
    for (let j = i; j < list.length; j++) {

      let distance = Math.abs(list[i - 1].cilinder - list[j].cilinder);
      if (distance < minDistance) {
        minDistance = distance;
        idx = j;
      }
    }

    // Intercambiamos
    if (idx != i) {
      let node = list[idx];
      list[idx] = list[i];
      list[i] = node;
    }
  }
  return list;

}

console.log(orderByLessCilinderDistance(timeList));

1
  • 1
    Muchas gracias Marcos funciona a la perfección!, se me fueron las pinzas al olvidarme que podia declarar los objetos dentro del array así como lo hiciste en tu respuesta, funciona perfectamente!
    – Layer
    Commented el 24 abr. 2020 a las 20:42

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.