rotolando intorno ai numeri di corsa

Question

Sono file generati con due cifre 00-99 e voglio conservare gli ultimi 50. L'algoritmo dovrebbe dirmi il numero del file corrente che sto per salvare e quale dei file precedenti da rimuovere.

Se lo riducono in una versione giocattolo con una cifra, ecco come voglio che si comportino.

.
1. Finché ci sono meno di 5 file, possiamo semplicemente aggiungere file. Questo è rappresentato nel primo blocco qui sotto.
2. Una volta ci sono 5 file precedenti, il più vecchio dovrebbe essere eliminato. Questo è banale fintanto che non abbiamo raggiunto il numero massimo, qui 9. Questo è rappresentato nel secondo blocco di seguito.
3. Una volta raggiunti i numeri più alti, la numerazione dovrebbe rotolare, e qui è dove le cose diventano ingannevoli. Vedi il terzo blocco qui sotto.

__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

.

Qualche pseudocodice per illustrare i miei progressi:

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

.

... ed è qui che sono bloccato. Ho sperimentato la sottraente 10 da ciascun elemento in prev.

Sono sicuro che è banale e che mi colterà quando meno mi aspetto. Ho anche una sensazione di fastidioso troverò un'espressione che generalizza entrambi i casi (con e senza max in prev).

Answer 1

Quello che hai cercato di implementare è una struttura di dati di dimensioni fisse di formazione first-in-first-out (FIFO), che è comunemente chiamata coda circolare , buffer circolare, buffer ciclico o buffer ad anello.

Oltre al requisito della coda circolare, si desidera che i numeri che rotolano attorno a un intervallo come da 0 a 99. Poiché tutti i numeri in uso sono contigui, è sufficiente utilizzare solo due numeri, il più piccolo e il più grande di loro per rappresentarli.

In effetti, dal momento che il numero di file è costante una volta che il numero massimo di file è stato raggiunto, è sufficiente se tenere traccia del conteggio dei numeri mai utilizzati. Quindi possiamo costruire un'implementazione speciale molto semplificata della coda circolare.

Allo stesso modo al tuo codice, dovremmo usare la tecnica del modulo. Ecco un'implementazione JavaScript semplice e completamente lavorativa. Entrambi ottengono operazioni di funzionamento e aggiornamento funzionano in $ 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.
    }

}

.

---

.

L'implementazione di cui sopra funziona per tutte le possibili limiti di coppie interi>= MASSIMEKET. In particolare, funziona anche se il limite è il maliuso.

Ecco un esempio di utilizzo:

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

È divertente come spiegare un problema ti fa approcciare in modo diverso (< Anatra di gomma , chiunque?).

Penso di essere riuscito a ciottore insieme il comportamento che sto cercando.L'idea è che se l'elenco contiene l'ultimo numero (I.E. n-1, qui 9), n viene aggiunto ad ogni numero maggiore di n/2.

Ora, JavaScript non è sicuramente la mia prima lingua, quindi per favore sii gentile e cerca di vedere l'idea piuttosto che il casino che è il mio JS ...

Gioca con esso qui o semplicemente prendi la vista qui sotto.Certo che sarei grato per una soluzione migliore.

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

Il comportamento della funzione Modulo in molti linguaggi di programmazione è un po 'eccentrico e potrebbe dipendere dal segno dell'argomento.Tuttavia, se si calcola $ a \ bmod B $ per Positive $ A, B $ , otterraiUna risposta nella gamma $ 0, \ Ldots, B-1 $ .

Ora supponiamo di voler calcolare una differenza $ xy \ pmod {b} $ , e il nostro obiettivo è ottenere una risposta nella gamma $ 0, \ Ldots, B-1 $ .Possiamo presumere che $ x, y $ sono nella stessa gamma.Se $ y> x $ , quindi $ x - y $ sarebbe negativo, e così potremmo ottenereuna risposta negativa.Per evitare che, possiamo calcolare $ x + (B-y) $ invece.Questo darà sempre la risposta corretta.