Check positions of an array and replace them with the optimal algorithm

Question

Check positions of an array and replace them with the optimal algorithm

Navigation

#1 by (0 votes)
#2 by (0 votes)

0

Good evening,

The problem with the next piece of code is that I need to save the positions of all the repeated values that are found, for example:

Using the FIFO algorithm

marcos = [4,1,2] cadena = [5,1,2,3,4,5]

The first one that enters is the first to go out therefore, and l 5 replaces the 4 , but when a value is repeated it should not be replaced since said value is already in the array marcos . Following the logic of the algorithm this should jump the repeated values that this case would be 1,2 and continue [5,3,4] and therefore the 5 would not be replaced either.

Then in my array of "repeated" should be saved [1,2] which are the corresponding positions of the elements that are repeated in the array frames.

for(var i = 0; i < marcos.length; i++){
        if(marcos[i] == cadena[i]){
            var repetido = cadena.indexOf(cadena[i]);
            array.push(repetido);
            cadena.splice(repetido , 1);
        }

        if(array.length > 0){
            //aca iria el 
            marcos.splice(array[i] , 1 , cadena[i])
           //y luego se elimina el elemento del array para eguir con el proceso de forma normal
        }else{
            marcos.splice(i, 1, cadena[i]);
        }

    }

Making use of the optimal algorithm

The difference between this and the FIFO is that it replaces the farthest value.

marcos [1,2,3]      cadena [5 , 4 , 3 , 2 , 1]

then the farthest value in this case would be one and you would have to replace 5 with 1 obtaining this result: [5,2,3] cadena [4 , 3 , 2 , 1] to then repeat the procedure, but in this case the value 5 will not return to then use the result would be: [4,2,3]

Could someone give me a hand with the logic of these problems?

Thank you very much.

javascript jquery array

asked by Elio 01.12.2016 в 05:24

source

2 answers

Data structure in java or xml file with xpath? How to make git ignore files (configure .gitignore) [closed]

score 0 · Answer 1

int v = 4;

int[] cadena = new int[v];

for(int i=0; i=v; v--){

 for(int j=0; j<=v; j++){

  System.out.print(cadena[j]);

 }

}

I'm not sure what you really want, but in principle this is showing you the chain until it ceases to exist.

score 0 · Answer 2

I know that what you were needing is not exactly this, but ... below I leave an implementation of the Optimal Algorithm .

Every detail of the process is documented throughout the script

function algoritmoOptimo (marcos, paginas) {
  var memoriaLlena = false,
    i = 0,
    valor,
    enMemoria,
    actual,
    anterior,
    candidato,
    candidatos,
    fallos = 0,
    mapaMemoria = {},
    log;

  // LOGs
  document.getElementById('marcos').innerHTML = JSON.stringify(marcos);
  document.getElementById('paginas').innerHTML = JSON.stringify(paginas);
  log = logTiemposHeaders();

  // Inicio de proceso
  paginas.forEach(function(proceso, idx) {

    // Comprobamos que todos los marcos esten llenos
    if (!memoriaLlena) {
      for (; i < marcos.length; i++) {
        valor = marcos[i];

        // Si el marco esta vacio
        if (valor === null) {
          escribirMarco(i, proceso, idx);
          i++;
          return;
        }
      }

      // Si todos los marcos ya esta llenos
      memoriaLlena = i === marcos.length;
    }

    enMemoria = false;
    candidatos = [];
    actual = 0;
    anterior = 0;

    for (i = 0; i < marcos.length; i++) {
      valor = marcos[i];

      // Si ya esta en el marco
      if (valor === proceso) {
        enMemoria = true;
        break;
      }

      // Obtenemos la distancia del proceso en el marco en las paginas restantes
      actual = paginas.indexOf(valor, idx + 1);

      // Si no esta las paginas restantes
      if (actual === -1) {
        actual = paginas.length;

        // Es candidato a fifo
        candidatos.push(i);
      }

      // Si la distancia del proceso en el marco actual en las paginas restantes
      // es mayor o igual a la del proceso anterior 
      if (actual >= anterior) {
        anterior = actual;
        candidato = i;
      }
    }

    // Si ya estaba en memoria
    if (enMemoria) {
      log += logTiempos(idx);
      return;
    }

    // Si hay uno o mas candidatos, es porque hay uno o mas procesos
    // que no se encuentra en las paginas
    if (candidatos.length) {
      anterior = -1;
      actual = 0;
      
      // Para cada uno de los candidatos
      candidatos.forEach(function(posicion) {
        actual = mapaMemoria[posicion];
        // Buscamos aquel que lleva mas tiempo en memoria
        if (actual > anterior) {
          anterior = actual;
          candidato = posicion;
        }
      });
    }
    
    //
    escribirMarco(candidato, proceso, idx);
  });
  
  // LOGs
  document.getElementById('tiempos').innerHTML = log;
  var frecuencia = Number(Number(fallos / paginas.length).toFixed(2));
  document.getElementById('frecuencia').innerHTML = frecuencia;
  document.getElementById('rendimiento').innerHTML = parseInt((1 - frecuencia) * 100, 10) + '%';

  return;

  // ------------------
  // Metodos privados

  function escribirMarco(posicion, proceso, tiempo) {
    // Escribimos el proces en el marco indicado
    marcos[posicion] = proceso;
    // Hubo acceso a disco 
    fallos++;

    marcos.forEach(function(proceso, idx) {
      // Si no esta seteado el contador en el mapa de memoria para la poscion de marco
      if (mapaMemoria[idx] === undefined) {
        mapaMemoria[idx] = 0;
      }
      // Si el contador en el mapa de memoria es igual al que a que acabamos de escribir
      // lo igualamos a 0, en caso contrario lo incrementamos 
      mapaMemoria[idx] = idx === posicion ? 0 : mapaMemoria[idx] + 1;
    });
    
    // Log para generar la tabla de tiempos
    log += logTiempos(tiempo, true);
  }

  function logTiemposHeaders() {
    var html = '<tr><th>Tiempos</th>';

    marcos.forEach(function(proceso, idx) {
      html += '<th> Marco ' + (idx + 1) + '</th>';
    });
    html += '<th>Fallos</th></tr>';
    return html;
  }

  function logTiempos(tiempo, fallo) {
    var html = '<tr><td>Tiempo ' + (tiempo + 1) + '</td>';

    marcos.forEach(function(proceso) {
      html += '<td>' + (proceso === null ? '-' : proceso) + '</td>';
    });
    html += '<td>' + (fallo ? 'X' : '-') + '</td></tr>';
    return html;
  }
}


//
algoritmoOptimo([null,null,null], [4,1,2,5,1,2,3,4,5]);

Marcos:
<span id="marcos"></span><br/>
Paginas:
<span id="paginas"></span><br/>
Tiempos:
<table border="1" cellpadding="2" cellspacing="0" style="text-align:center; display: inline-block; vertical-align: top">
  <tbody id="tiempos"></tbody>
</table><br/>
Frecuencia de Fallos:
<span id="frecuencia"></span><br/>
Rendimiento del algoritmo:
<span id="rendimiento"></span>