Shuffle di una coda

di
mark22
il
6 risposte
M
mark22
Pochi posts
Iscritto da
ott, 2017
Messaggi:
29

Shuffle di una coda

Salve a tutti,
sto implementando una coda e vorrei scrivere un metodo che la disordina.
Vorrei chiedervi quale potrebbe essere un algoritmo efficiente per disordinarla?

Altra domanda: come potrei far si che io possa utilizzare metodi di "Collections" per esempio: Collections.sort,Collections.shuffle... però con liste, code ecc. scritte da me?
Grazie in anticipo!

6 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Shuffle di una coda

    mark22 ha scritto:

    sto implementando una coda e vorrei scrivere un metodo che la disordina.
    Vorrei chiedervi quale potrebbe essere un algoritmo efficiente per disordinarla?
    Dipende .... come è fatta la struttura della coda? Array? Lista linkata di tuoi nodi? Altro?

    mark22 ha scritto:

    Altra domanda: come potrei far si che io possa utilizzare metodi di "Collections" per esempio: Collections.sort,Collections.shuffle... però con liste, code ecc. scritte da me?
    Quei metodi si aspettano un java.util.List. La tua coda "dovrebbe" implementare List ... cosa che per una coda avrebbe poco senso.
  • M
    mark22
    Pochi posts
    Iscritto da
    ott, 2017
    Messaggi:
    29

    Re: Shuffle di una coda

    andbin ha scritto:

    mark22 ha scritto:

    sto implementando una coda e vorrei scrivere un metodo che la disordina.
    Vorrei chiedervi quale potrebbe essere un algoritmo efficiente per disordinarla?
    Dipende .... come è fatta la struttura della coda? Array? Lista linkata di tuoi nodi? Altro?
    lista linkata di miei nodi

    mark22 ha scritto:

    Altra domanda: come potrei far si che io possa utilizzare metodi di "Collections" per esempio: Collections.sort,Collections.shuffle... però con liste, code ecc. scritte da me?
    Quei metodi si aspettano un java.util.List. La tua coda "dovrebbe" implementare List ... cosa che per una coda avrebbe poco senso.
    E quindi per implementare una coda dovrei fare "implements Queue"?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Shuffle di una coda

    mark22 ha scritto:

    E quindi per implementare una coda dovrei fare "implements Queue"?
    Se vuoi fare una coda per motivi "didattici", può anche non avere nulla a che fare con classi/interfacce delle collection standard di Java (al massimo potresti renderla implements Iterable, cioè che si possa iterare con il iterator() esplicitamente o tramite for-each).

    Se invece vuoi implementare java.util.Queue, allora sei obbligato ad implementare tutti i metodi di Queue più quelli di Collection (supertipo di Queue) e con i significati indicati nella documentazione, chiaramente. E se non hai avuto una richiesta esplicita in tal senso, sinceramente non te lo consiglio.

    Se vuoi fare una coda "da zero", come ho detto prima hai principalmente due approcci per la sua struttura dati interna: a) array di dimensione prefissata, b) lista linkata di tuoi nodi.
    Poi bisogna anche vedere se vuoi fare una coda per trattare solo un tipo ben specifico (es. int o String) oppure se vuoi renderla "generica" (nel senso dei generics introdotti in Java 5).
  • M
    mark22
    Pochi posts
    Iscritto da
    ott, 2017
    Messaggi:
    29

    Re: Shuffle di una coda

    andbin ha scritto:

    Dipende .... come è fatta la struttura della coda? Array? Lista linkata di tuoi nodi? Altro?
    Scusami mi son dimenticato di risponderti a questa domanda,
    è fatta da una lista linkata di nodi, generica

    andbin ha scritto:

    mark22 ha scritto:

    E quindi per implementare una coda dovrei fare "implements Queue"?
    Se vuoi fare una coda per motivi "didattici", può anche non avere nulla a che fare con classi/interfacce delle collection standard di Java (al massimo potresti renderla implements Iterable, cioè che si possa iterare con il iterator() esplicitamente o tramite for-each).
    Si la sto facendo per motivi didattici
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Shuffle di una coda

    mark22 ha scritto:

    è fatta da una lista linkata di nodi, generica
    L'approccio tipico del shuffle è il seguente, dati n elementi con indici logici da 0 a n-1:

    - nell'elemento a indice n-1 (l'ultimo) si mette il valore preso all'indice "casuale" tra 0 e n-1 (entrambi inclusi)
    - nell'elemento a indice n-2 si mette il valore preso all'indice "casuale" tra 0 e n-2 (entrambi inclusi)
    ecc...

    In questo modo è possibile che un valore resti allo stesso posto. Se si vuole evitarlo, basta scalare ancora di 1 il limite superiore dell'estrazione casuale.

    Ora, una lista linkata non è molto appropriata per questo. Le soluzioni sono due:
    a) soluzione molto inefficiente: se hai dei get() e set() a indice (anche privati, non esposti) puoi fare quella logica. Ovviamente diventa "pesante" perché per ogni get o set di un elemento richiede di scorrere la lista fino a quel indice.
    b) creare un array temporaneo con i valori dei nodi, applicare lo shuffle all'array e poi risettare i valori nei nodi (nota: NON serve toccare il "next" dei nodi)


    Nota: la soluzione b) è quella che usa internamente lo shuffle() di java.util.Collections quando la lista che riceve NON implementa RandomAccess.
  • M
    mark22
    Pochi posts
    Iscritto da
    ott, 2017
    Messaggi:
    29

    Re: Shuffle di una coda

    Perfetto grazie tante!
Devi accedere o registrarti per scrivere nel forum
6 risposte