Come si chiama un iteratore che restituisce i fratelli corrente, precedente e successivo di ciascun nodo di un elenco? [chiuso]

3

Come si chiama un iteratore che ha dato una lista [a, b, c] , restituisce un oggetto della forma { prev, curr, next } per ogni iterazione?

ad es. (? === undefined )

{ prev: ?, curr: a, next: b }
{ prev: a, curr: b, next: c }
{ prev: b, curr: c, next: ? }

Ho pensato tuples , ma sono abituato a pensare che una tupla sia di solito un elenco di 2 voci quindi sono indeciso.

EDIT: Triples could work, but I was also wondering if there is any mention of this type of structures in the literature. I am familiar with linked lists, but this is different.

EDIT 2: Here is the generator implementation in JavaScript.

  /**
    @syntax
    Parsec.prototype.tuples([a, b, c])
      { prev: ?, curr: a, next: b }
      { prev: a, curr: b, next: c }
      { prev: b, curr: c, next: ? }
    @param {Array|String} list List to iterate.
    @param {Object} [last] Define to use as the last value.
    @param {Object} [prev] Define to use as the first prev value.
    @param {Object} [curr] Define to use as the first curr value.
  */
  function* tuples(list, last, prev, curr) {
    for (let next of list) {
      if (curr !== undefined) yield { prev, curr, next /* add last here? */}
      prev = curr
      curr = next
    }
    yield { prev, curr, last }
  }
    
posta Jorge Bucaran 12.05.2015 - 08:10
fonte

4 risposte

18

Oltre a triple (che significa solo "abbiamo tre valori") e nodo (che è stato suggerito da manlio ), posso suggerire le seguenti alternative:

Finestra scorrevole

Sembra che tu abbia sempre una finestra con tre elementi consecutivi nell'elenco. Questo è il nome più appropriato secondo la tua situazione.

Quella struttura non consente di navigare facilmente nell'elenco in termini di prev , next puntatori, tuttavia (forse è intenzionale). Se vuoi navigare nella struttura dei dati, dovresti chiamarlo node (come nelle liste a doppio collegamento, come dice manlio) o un cursore , che è un nome leggermente migliore che trasmette le capacità iterative dell'oggetto.

cursore

Gli iteratori in Ada sono basati su un cosiddetto tipo Cursor , che incapsula la posizione di un iteratore all'interno di una struttura, insieme alle operazioni Next e Previous .

Vedi ad esempio Gem # 127 oppure Motivazione per Ada 2005 .

Zipper

La tua domanda mi ha originariamente ricordato Chiusure lampo che sono costrutti trovati di solito con strutture dati puramente funzionali. Permettono di scorrere su una struttura mantenendo un contesto sufficiente per spostarsi.

Ad esempio, una lista lampo dovrebbe contenere l'elenco invertito degli elementi precedenti (prefisso), elemento corrente e la solita lista di coda:

(Prefix,Current,Tail)

È facile costruire una cerniera per il prossimo elemento in tempo costante:

(cons(Current,Prefix),head(Tail),tail(Tail))

Oppure, una cerniera per l'elemento precedente in tempo costante:

(tail(Prefix),head(Prefix),cons(Current,Tail))

Ovviamente, il costo di questo approccio è che stai manipolando due liste invece di una (durante la vita dell'iteratore / zipper). Contrariamente agli elenchi collegati doppiamente, non è necessario modificare le strutture dei dati.

La tua struttura è chiaramente non una cerniera, ma ha condiviso abbastanza somiglianze con loro che ho pensato che sarebbe stato interessante scrivere su di loro.

    
risposta data 12.05.2015 - 09:45
fonte
9

In Scala, questa è chiamata finestra scorrevole :

Seq(1, 2, 3, 4, 5).sliding(2).foreach(println)
// List(1, 2)
// List(2, 3)
// List(3, 4)
// List(4, 5)

Al contrario di raggruppato quando gli elementi non si sovrappongono:

Seq(1, 2, 3, 4, 5).grouped(2).foreach(println)
// List(1, 2)
// List(3, 4)
// List(5)

In Ruby, si chiama contro :

[1, 2, 3, 4, 5].each_cons(2).to_a
# => [[1, 2], [2, 3], [3, 4], [4, 5]]

e l'altro è chiamato slice :

[1, 2, 3, 4, 5].each_slice(2).to_a
# => [[1, 2], [3, 4], [5]]

Nota: nel tuo caso, la finestra inizia prima del primo elemento e finisce dopo l'ultimo, mentre in Ruby e Scala inizia a il primo elemento e finisce all'ultimo, ma questo è solo un Scelta arbitraria del design dell'API e probabilmente non dovrebbe influire sul nome.

Penso che "cons" (per "consecutivi") sia una scelta sfortunata di nome, perché si scontra con il termine ben definito "contro" per "costruire", come in Lisp e in altri linguaggi funzionali. Mi piace molto "sliding window" o "sliding view".

    
risposta data 12.05.2015 - 10:01
fonte
5

Una tupla è una sequenza finita (lista ordinata) di elementi. È vero in matematica, database relazionali e in molte lingue (ad es. C ++ , Prolog, Python ...).

Quindi tuple potrebbe essere un buon nome.

node è un'alternativa poiché un oggetto della forma {prev, curr, next} ricorda di un nodo di una lista doppiamente collegata.

    
risposta data 12.05.2015 - 09:54
fonte
-3

Questa sembra una domanda di teoria su algoritmi e strutture dati.
Per quanto riguarda la struttura dati, se si desidera restituire i tre risultati contemporaneamente, ovviamente è necessario inserirli in una singola infrastruttura e, naturalmente, ciò renderebbe una tripla. Senza una data sintassi è difficile dare una risposta e la domanda sembra non correttamente affermata, sento che la domanda è anche come calcolare il precedente e il successivo, e per questo vorrei dire qualcosa del tipo:

curry = this;
prev = this;
next = this;
prev —-;
next++;

if(pre <0) prev = undefined;
if (next >= length) next = undefined;

Per quanto riguarda il nome di questo tipo di itertor, come avresti già fatto, lo chiamerei triple o triplet, in quanto ha bisogno di memorizzare 3 valori.

    
risposta data 12.05.2015 - 08:50
fonte

Leggi altre domande sui tag