rodando por números corriendo

Question

Estoy numerando archivos generados con dos dígitos del 00 al 99 y quiero conservar los últimos 50.El algoritmo debería decirme el número del archivo actual que estoy a punto de guardar y cuál de los archivos anteriores debo eliminar.

Si lo reduzco a una versión de juguete con un dígito, así es como quiero que se comporte.

1. Siempre que haya menos de 5 archivos, simplemente podemos agregar archivos.Esto está representado en el primer bloque a continuación.
2. Una vez que haya 5 archivos anteriores, se debe eliminar el más antiguo.Esto es trivial mientras no hayamos alcanzado el número máximo, aquí 9.Esto está representado en el segundo bloque a continuación.
3. Una vez que se han alcanzado los números más altos, la numeración debería continuar, y aquí es donde las cosas se ponen complicadas.Vea el tercer bloque a continuación.

__prev__    __curr__   __drop__  
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

0 1 2 3 4      5          0 
1 2 3 4 5      6          1
2 3 4 5 6      7          2
3 4 5 6 7      8          3
4 5 6 7 8      9          4

5 6 7 8 9      0          5
6 7 8 9 0      1          6
7 8 9 0 1      2          7
8 9 0 1 2      3          8
9 0 1 2 3      4          9

Algún pseudocódigo para ilustrar mi progreso:

if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

...y aquí es donde estoy estancado.He experimentado restando 10 de cada elemento en prev.

Estoy seguro de que es trivial y que me llegará cuando menos lo espere.También tengo la sensación de que encontraré una expresión que generalice ambos casos (con y sin max en prev).

Answer 1

Lo que ha estado tratando de implementar es una estructura de datos de tamaño fijo primero en primer puesto (FIFO), que comúnmente se llama una cola circular , tampón circular, tampón cíclico o tampón de anillo.

Además del requisito de la cola circular, desea que los números rodan alrededor de un intervalo, como de 0 a 99. Dado que todos los números en uso son contiguos, es suficiente usar solo dos números, los más pequeños de ellos y El más grande de ellos para representarlos.

De hecho, dado que la cantidad de archivos es una constante una vez que se ha alcanzado el número máximo de archivos, es suficiente si hacemos un seguimiento del recuento de todos los números que se han usado. Así que podemos construir una implementación especial muy simplificada de la cola circular.

De manera similar a su código, deberíamos usar la técnica de Modulo. Aquí hay una implementación de JavaScript simple y completamente trabajadora. Tanto la operación y la operación de actualización se ejecutan en $ o (1) $ .

// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

---

La implementación anterior funciona para todos los pares de enteros posibles Límite>= MAXIMIENTE LOYPT. En particular, funciona incluso si el límite es máximo LOTPTT.

Aquí hay un uso de muestra:

function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());

Answer 2

Es curioso cómo explicar un problema te hace abordarlo de manera diferente (pato de goma, ¿alguien?).

Creo que logré improvisar el comportamiento que estoy buscando.La idea es que si la lista contiene el último número (es decir, n-1, aquí 9), n se suma a cada número mayor que n/2.

Ahora bien, Javascript definitivamente no es mi primer idioma, así que sea amable e intente ver la idea en lugar del desorden que es mi js...

Juega con él aquí. o simplemente disfrute de la vista a continuación.Por supuesto que estaría agradecido por una mejor solución.

function roll(n) {
  const half = n/2 ;
  const last = n-1 ;
  var iter = half * 3 ;
  var prev = [] ;
  var curr = null ;
  var drop = n ;
  var temp ;

  while(iter--) {
    console.log(prev) ;
    curr = prev.length ;
    if (curr < half) {
      prev = update(prev,curr,drop) ;
      continue ;
    }
    temp = [].concat(prev) ;
    if (temp.includes(last)) {
      for (var t=0 ; t<temp.length ; t++) {
        if (temp[t] < half)
          temp[t] += n ;
      }
    }
    drop = Math.min.apply(null, temp) % n ;
    curr = Math.max.apply(null, temp) + 1 ;
    curr %= n ;
    prev = update(prev,curr,drop) ;
  }
}

function update(p,c,d) {
  for (var i=0 ; i<p.length ; i++) {
    if (p[i] == d)
      p.splice(i,1) ;
  } 
  p.push(c) ;
  return p ;
}

roll(10) ;

Answer 3

El comportamiento de la función Modulo en muchos lenguajes de programación es un poco peculiar, y podría depender del signo del argumento.Sin embargo, si calcula $ a \ bmod b $ para positivo $ a, b $ , obtendrásUna respuesta en el rango $ 0, \ ldots, b-1 $ .

Supongamos que queremos calcular una diferencia $ xy \ pmod {b} $ , y nuestro objetivo es obtener una respuesta en el rango $ 0, \ LDOTS, B-1 $ .Podemos asumir que $ x, y $ están en el mismo rango.Si $ y> x $ , luego $ x - y $ sería negativo, y así podríamos obtenerUna respuesta negativa.Para evitar que, podemos calcular $ x + (b-y) $ en su lugar.Esto siempre dará la respuesta correcta.