Instance Indexing

Algoritmi, discussioni sulle possibili implementazioni, matematica, fisica e tutti gli argomenti correlati alla programmazione
Rispondi
Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Instance Indexing

Messaggio da Barnack »

Salve a tutti. Nel mio esperimento mplayer ho notato la necessità di creare un sistema di indexing interno per scambiare i dati di precise istanze tra un'istanza del gioco ed un'altra (scusate il gioco di parole :asd: )
In alcuni video (non solo riguardanti il multiplayer) ho visto utilizzare le ds_map per questo scopo. Il che avrebbe moooolto senso se le mappe (o dizionari) fossero implementate nella maniera ottimale, ovvero con tempo di accesso O(1).
Tuttavia per sbaglio ho aperto la documentazione di gm ed ho trovato una frase orribile:
Maps are not sorted in any (recognisable) way, meaning that to find a certain key you may have to iterate through the whole thing (which is very slow).
... momento di silenzio...
E io ero del tipo "WTF???"
Cioè sul serio, se proprio non utilizzi l'implementazione ottimale almeno usa una sorted_list così impieghi al più O(log(n))!!!
Spoiler
Scusate, mi sentivo obbligato :asd:
https://www.youtube.com/watch?v=alY0yxlEOJ8
Immagino il sorrisetto del mio prof di algoritmi se leggesse questo post... vabbè. Adesso so cosa aggiungerò alla mia libreria "coding utilities", ovvero una "ds_at_least_decent_map()"

Comunque torniamo a noi. Vista questa porkata che da gm non mi aspettavo di vedere (o forse si) ho pensato ad un sistema di indexing alternativo. L'idea più banale è quella di fare lo stesso implementandosi una mappa decente con tempo di accesso O(1). Poi però mi sono detto che mi piace fare il precisino, e i <3 ottimizzazioni marginali, quindi perché ignorare il peso dei fattori moltiplicativi? Credo sia abbastanza intuitivo che l'accesso all'i-esimo indice di un array sia ben più rapido dell'accesso ad un valore in una mappa/dizionario.

Ecco il sistema che ho pensato: (vado con pseudo codice mezzo c++esco meticciato a gml)
NOTE:
l'id custom è indicato con _id
Spoiler

Codice: Seleziona tutto

array/list <instance_id> indexes
int current_id = 0
queue <int> unused_ids
Spoiler

Codice: Seleziona tutto

var inst = instance_create(/*qualsiasi istanza da creare*/)
var n=0
if unused_ids.empty()
	{n = current_id++}
else
	{n = unused_ids.dequeue()}
inst._id = n
indexes[n] = inst.id
Spoiler

Codice: Seleziona tutto

var inst = /*id istanza da distruggere*/
var n = inst._id
indexes[n] = noone
unused_ids.enqueue(n)
with(inst){instance_destroy()}
Spiegazione:
C'è un array per l'accesso alle istanze a partire dall'_id (che è esattamente l'indice nel detto array)
C'è una coda vuota che conterrà gli id già predisposti nell'array ma non utilizzati.
C'è un intero che indica il corrente valore massimo.
Quando si aggiungono istanze, finché la coda è vuota si utilizzerà il massimo come nuovo id e si incrementerà il massimo.
Quando si rimuove un'istanza il suo indice nell'array indicherà noone e l'indice stesso verrà enqueuato nella coda.
Se aggiungo un'istanza e la coda non è più vuota significa che ci sono "buchi" nell'array e quindi è più conveniente riempire quei buchi piuttosto che ingigantirlo. Prendo quindi l'indice inutilizzato e piazzo lì l'istanza.
In teoria in un ambiente dinamico con molte cose che si creano e si distruggono spesso (tipo proiettili just to say) dopo una rapida crescita iniziale dell'array, la dimensione dovrebbe rimanere sempre stabile, e non costantemente crescente. :sisisi:
NOTA: si funzionerebbe esattamente uguale con uno stack, ho usato una coda per sanità mentale mia. In realtà il risultato in termini di efficienza dovrebbe essere esattamente identico.

Ora, la big question è: cosa c'è che non va? Me lo sento, deve esserci un lato negativo in tutto questo cui non ho pensato :asd:

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Avatar utente
cp94
Moderatore
Messaggi: 2789
Iscritto il: 04/07/2009, 19:18
Specialità: ddd
Località: Brescia
Contatta:

Re: Instance Indexing

Messaggio da cp94 »

Ho alcuni dubbi a riguardo, te li elenco:
- Perchè generi una coda vuota contenente degli _id non utilizzati quando poi dici che i valori degli _id saranno incrementali? Non faresti prima ad avere un contatore che si incrementa senza dover controllare se ci sono degli _id non utilizzati?
- Piuttosto che inserire tutti gli _id in un array e dover iterare ogni volta questa lista per vedere se ci sono posizioni vuote ti consiglierei di creare una lista collegata (tipo una ds_list) ed effettuare la pulizia dei buchi al momento di rimozione dell'elemento. Vi saranno degli indici non più utilizzati, ma le nuove istanze verranno messe sempre in cima alla lista con un _id incrementato.
- Se usi una coda ed hai migliaia di istanze che si creano e distruggono in maniera frequente potresti avere dei rallentamenti, soprattutto nella rimozione perchè dovresti iterare la lista alla ricerca dell'_id. Io proverei ad implementare una mappa 6-dimensionale dove ogni dimensione contiene la cifra di posto i dell'_id (se l'_id è formato da 6 cifre). Ogni cella conterrà il dato (la cifra) e un puntatore alla cella della prossima cifra. Non son sicuro sul come si potrebbe fare in GM ma dettagli :mrgreen:
Games you should check out
Naemo
E T U S
Overgravity
Inside the Code

Immagine

Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Instance Indexing

Messaggio da Barnack »

Da quello che hai scritto mi sembra di essermi spiegato male :asd:
cp94 ha scritto:Ho alcuni dubbi a riguardo, te li elenco:
- Perchè generi una coda vuota contenente degli _id non utilizzati quando poi dici che i valori degli _id saranno incrementali? Non faresti prima ad avere un contatore che si incrementa senza dover controllare se ci sono degli _id non utilizzati?
Il contatore c'è, ma gli _id non sono sempre incrementali, non l'ho mai detto. Finché non ci sono id vuoti, allora si incrementa l'id, altrimenti si assegna quello inutilizzato.
CFR:

Codice: Seleziona tutto

if unused_ids.empty()
	{n = current_id++}
else
	{n = unused_ids.dequeue()}
inst._id = n
- Piuttosto che inserire tutti gli _id in un array e dover iterare ogni volta questa lista per vedere se ci sono posizioni vuote
Infatti non itero mai per vedere se ci sono posizioni vuote. Ho fatto la coda apposta XD
ti consiglierei di creare una lista collegata (tipo una ds_list) ed effettuare la pulizia dei buchi al momento di rimozione dell'elemento. Vi saranno degli indici non più utilizzati, ma le nuove istanze verranno messe sempre in cima alla lista con un _id incrementato.
Facendo tutto con una linked list si perdono i vantaggi dell'accesso diretto all' _id-esimo elemento dell'array del sistema che ho proposto e ti troveresti a dover iterare tutta la lista quando cerchi un id...
- Se usi una coda ed hai migliaia di istanze che si creano e distruggono in maniera frequente potresti avere dei rallentamenti, soprattutto nella rimozione perchè dovresti iterare la lista alla ricerca dell'_id. Io proverei ad implementare una mappa 6-dimensionale dove ogni dimensione contiene la cifra di posto i dell'_id (se l'_id è formato da 6 cifre). Ogni cella conterrà il dato (la cifra) e un puntatore alla cella della prossima cifra. Non son sicuro sul come si potrebbe fare in GM ma dettagli :mrgreen:
No non hai capito. Tu stai parlando come se l'_id fosse un numero a caso incrementale. Invece quello che faccio è usare come _id l'indice stesso della posizione nell'array. Non ci sarà mai bisogno di iterare proprio un bel niente, si fa tutto ad accesso diretto (come ho detto, tempo O(1) )

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Instance Indexing

Messaggio da Barnack »

Barnack ha scritto:Da quello che hai scritto mi sembra di essermi spiegato male :asd:
cp94 ha scritto:Ho alcuni dubbi a riguardo, te li elenco:
- Perchè generi una coda vuota contenente degli _id non utilizzati quando poi dici che i valori degli _id saranno incrementali? Non faresti prima ad avere un contatore che si incrementa senza dover controllare se ci sono degli _id non utilizzati?
Il contatore c'è, ma gli _id non sono sempre incrementali, non l'ho mai detto. Finché non ci sono id vuoti, allora si incrementa l'id, altrimenti si assegna quello inutilizzato.
CFR:

Codice: Seleziona tutto

if unused_ids.empty()
	{n = current_id++}
else
	{n = unused_ids.dequeue()}
inst._id = n
- Piuttosto che inserire tutti gli _id in un array e dover iterare ogni volta questa lista per vedere se ci sono posizioni vuote
Infatti non itero mai per vedere se ci sono posizioni vuote. Ho fatto la coda apposta XD
ti consiglierei di creare una lista collegata (tipo una ds_list) ed effettuare la pulizia dei buchi al momento di rimozione dell'elemento. Vi saranno degli indici non più utilizzati, ma le nuove istanze verranno messe sempre in cima alla lista con un _id incrementato.
Facendo tutto con una linked list si perdono i vantaggi dell'accesso diretto all' _id-esimo elemento dell'array del sistema che ho proposto e ti troveresti a dover iterare tutta la lista quando cerchi un id...
- Se usi una coda ed hai migliaia di istanze che si creano e distruggono in maniera frequente potresti avere dei rallentamenti, soprattutto nella rimozione perchè dovresti iterare la lista alla ricerca dell'_id. Io proverei ad implementare una mappa 6-dimensionale dove ogni dimensione contiene la cifra di posto i dell'_id (se l'_id è formato da 6 cifre). Ogni cella conterrà il dato (la cifra) e un puntatore alla cella della prossima cifra. Non son sicuro sul come si potrebbe fare in GM ma dettagli :mrgreen:
No non hai capito. Tu stai parlando come se l'_id fosse un numero a caso incrementale. Invece quello che faccio è usare come _id l'indice stesso della posizione nell'array. Non ci sarà mai bisogno di iterare proprio un bel niente, si fa tutto ad accesso diretto (come ho detto, tempo O(1) )
Cito me stesso:
Spoiler

Codice: Seleziona tutto

var inst = /*id istanza da distruggere*/
var n = inst._id
indexes[n] = noone
unused_ids.enqueue(n)
with(inst){instance_destroy()}
Io qui non vedo alcuna iterazione. Vengono fatte 3 cose dirette: accesso ad un array, aggiunta in una coda, distruzione istanza.

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Jak
Admin
Messaggi: 12355
Iscritto il: 19/08/2009, 16:20
Specialità: Programmazione 3D
Uso: GM:Studio 2
Contatta:

Re: Instance Indexing

Messaggio da Jak »

Maaaaaa, hai fatto dei test o sei andato ad intuito su quella frase?
Il manuale parla espressamente di CHIAVI e non di VALORI. Cercare un valore tramite chiave è veloce, è il contrario che è difficile (cosa che è sempre stata poichè va contro le regole di una map)
Per l'ordine dei valori hanno semplicemente voluto (ulteriormente) pensare alle prestazioni su un'utilizzo comune.
Cercare un valore tramite key è veloce, scorrere l'intera map come fosse una lista è lento (ed incoerente causa ordine casuale)
Se, e solo se, ti serve fare entrambi a quel punto puoi facilmente farti una sorta di "maplist" come avevo fatto io per la gestione delle risorse in Lizard con risultati piuttosto buoni.
Time to feel, time to believe
Dare to see what may come of our future
Lift your head, broaden your gaze
Speak your mind and your thoughts they will follow you

Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Instance Indexing

Messaggio da Barnack »

Ho testato
Spoiler

Codice: Seleziona tutto

var m = 0
do
    {
    m = get_integer("MAX: ", 0)
    var map = ds_map_create()
    var arr;
    var time = 0;
    var dtime = 0
    
    // MAP POP
    for(var i=0; i<m; i++)
        {ds_map_add(map, i, "val"+string(i))}
    // ARR POP
    for(var i=0; i<m; i++)
        {arr[i] = "val"+string(i)}
    
    // MAP FINDS
    var finds=0;
    var item;
    for(var i=0; i<m; i++)
        {
        time = current_time
        item = ds_map_find_value(map, i)
        dtime = current_time-time
        finds+=dtime
        }
    dtime /= m
    show_debug_message("Map average find time: "+string(dtime))
    
    // ARR FINDS
    var finds=0;
    for(var i=0; i<m; i++)
        {
        time = current_time
        item = arr[i]
        dtime = current_time-time
        finds+=dtime
        }
    dtime /= m
    show_debug_message("Map average find time: "+string(dtime))
    }
until(m<0)
Ed il tempo impiegato è lo stesso... ma... 0??????? Ok che sono entrambi metodi veloci ma impiegarci 0 assoluto mi sembra eccessivo :hum: Qualcuno con un pc un po' vecchio può testare lo stesso codice?

EDIT:
Dato che gm limita a 32'000 elementi è anche difficile fare un test complesso. L'ultima volta che ho testato due cose a confronto in c++ l'ho fatto con 100'000/500'000 elementi.


Comunque, messa a parte l'efficienza delle ds_map, qualcuno trova falle nel sistema che ho proposto?^^

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Instance Indexing

Messaggio da Barnack »

Xeryan ha scritto:Non usare current_time ma get_timer() che è 'preciso' fino al milionesimo di secondo
Ottengo comunque bellissimi zeri e neanche mezza cifra diversa da 0 xD

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Jak
Admin
Messaggi: 12355
Iscritto il: 19/08/2009, 16:20
Specialità: Programmazione 3D
Uso: GM:Studio 2
Contatta:

Re: Instance Indexing

Messaggio da Jak »

Di solito il contatore si mette fuori dal ciclo e non dentro per evitare problemi di precisione. Stessa cosa per la funzione string() che se non sbaglio ha un limite standard sul numero di cifre decimali (ma potrei sbagliarmi) quindi usa string_format
Time to feel, time to believe
Dare to see what may come of our future
Lift your head, broaden your gaze
Speak your mind and your thoughts they will follow you

Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Instance Indexing

Messaggio da Barnack »

Vabbè 5 messaggi senza parlare del punto del topic. Comunque non mi serve vedere i numeri: l'accesso all'i-esimo elemento di un array è semplicemente la lettura di un indirizzo più un numero (somma, memorizzazione), mentre in una mappa vengono eseguite più operazioni per trovare un dato valore. E come ho già detto per fare un test significativo si dovrebbero usare dimensioni maggiori di quelle che gm mette a disposizione. Finché la differenza è in millimicronano-secondi può essere dovuta tanto all'efficienza reale, quanto a fortuna/sfortuna nella cache, quanto alla gestione del multitasking del sistema operativo, quanto a cosa hai mangiato ieri a cena :asd:
A parte questo che a prescindere non era il motivo del topic, ci sono modi più efficienti (parlando di memoria sia di tempi) per fare un'indicizzazione o quello che ho proposto va bene?

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti