Caccia all'errore (mio)

[Barnack]

Salve a tutti.
Per varie ragioni stavo implementando gli insiemi in gamemaker (non possono esserci elementi doppi).
Appena finite le funzioni essenziali mi sono accorto di un errore che non capisco.
Premessa = gli elementi vengono inseriti in maniera ordinata.
Ora, la funzione aggiunngi per prima cosa controlla se un elemento è già presente, e lo fa tramite ricerca dicotomica (che è il codice buggato), la quale A VOLTE FUNZIONE E A VOLTE NO SENZA APPARENTE RAGIONE.

Vi posto qui il codice della ricerca:

Spoiler

Codice: Seleziona tutto

/// ds_find_sub(id, value, ll, rr)
if argument2 = argument3
    {if argument0.items[argument2] = argument1 return(argument0.items[argument2])}
else
if argument2 < argument3
    {
    var mm = floor((argument2+argument3)/2)
    var val = argument0.items[mm]
    if val = argument1
        {return(mm)}
    else
        {
        if val < argument1
            {
            return(ds_find_sub(argument0, argument1, mm-1, argument3))
            }
        else
            {
            return(ds_find_sub(argument0, argument1, argument2, mm+1))
            }
        }
    }
return(-1)

Quando chiamo su un insieme vuoto aggiungi(i) da 5 a 1, appena deve aggiungere il 3 mi dice "malformed variable" con items_n, che è l'intero contenente il numero attuale di elementi. Le uniche operazioni eseguite su items_n sono ++ e --.
Oltre a ciò, il nel codice dell'aggiunta, dopo aver chiamato questa ricerca, la variabile dell'elemento da aggiungere che viene passata alla ricerca come argomento, diventa 0.

Esempio
add(3)
// argument0 è 3
if not find(3)
{
//e qui argument0 diventa inspiegabilmente 0
}

[Cash]

Domanda molto stupida: l'insieme quando gli aggiungi elementi è ordinato?

[Barnack]

Premessa = gli elementi vengono inseriti in maniera ordinata.

Anche se l'errore si verifica in nell'aggiunta, quando questa va a buon fine l'insieme è ordinato. Nella fase "controlla se l'elemento è già presente" in qualche modo l'argument0 di aggiungi si trasforma dopo la chiamata di cerca

[Barnack]

quello che non capisco è come possa un argomento di una funzione cambiare dopo che viene chiamata una sottofunzione. Le variabili sono passate per valore, non dovrebbe succedere, solo gli array vengono passati per riferimento...

[Tizzio]

Per maggiori prestazioni potresti usare le ds_map usando il valore stesso come key
All'aggiunta controlli se non esiste

[boxbuilder]

Anch'io faccio una domanda stupida:

Sei sicuro di passare solo numeri alla funzione?

[Barnack]

Funzione aggiungi

Codice: Seleziona tutto

show_debug_message("=============")
show_debug_message("Adding begin: "+string(argument1)) //(1)

if not ds_set_empty(argument0)
    {
    if not ds_set_find(argument0, argument1)
        {
        var i=ds_set_size(argument0)-1
        for(; i>=0 and argument0.items[i]>argument1; i--)
            {
            argument0.items[i+1]=argument0.items[i]
            }
        i++
        show_debug_message("Adding at: "+string(i))
        show_debug_message("Adding : "+string(argument1)) //(2)
        argument0.items[i] = argument1
        show_debug_message(argument0.items[i])
        argument0.items_n++
        }
    }
else
    {
    argument0.items[0] = argument1
    argument0.items_n++
    }
show_debug_message("Adding end")
ds_set_print(argument0)
show_message("Pause")

Tra i punti 1 e 2 argument1 diventa dal valore passato (1) a 0 (2) in alcuni casi non meglio definiti. ds_set_find è il codice della ricerca che ho già postato

[boxbuilder]

Barnack , l'ultimo script che hai postato è un po' complesso e non l'ho molto capito,
comunque se pensi che il bug sia nella ricerca binaria ti consiglio innanzitutto di lasciar perdere la funzione ricorsiva che hai scritto e di usarne una un po' più semplice, tipo questa fatta al volo:

Codice: Seleziona tutto

///ds_find_sub(vect, value)
var vect = agument0;
var value = agument1;

var dim = array_length_1d(vect);

var l, r, m;
l = 0;
r = dim-1;

while(l<=r){
  m = floor((l+r)/2);
  if(vect[m] == value){
    return m
  } else if(vect[m]<value){
    l = m+1;
  } else {
    r = m-1;
  }
}

return -1;

se ti piace l'idea di passare i confini della ricerca come parametro puoi utilizzarne due opzionali:

Codice: Seleziona tutto

if(argument_count == 4){
	l = argument[2];
	r = argument[3];
} else if (argument_count == 3){
	l = argument[2];
}

[Barnack]

Non ho la più pallida idea del perché ma riscrivendola da capo in forma ciclica anziché ricorsiva funziona senza problemi...
Ora resta da capire come facevano gli argomenti della funzione superiore a cambiare, se è un bug di gm sulla ricorsione, o se ho scritto minchiate io...
@boxbuilder, il secondo codice è per l'inserimento, non fa altro che sporstare da i a i+1 tutti gli elementi dall'ultimo verso il primo finché non ne trova uno minore dell'elemento da aggiungere. Infine piazza in quella posizione il nuovo elemento. Una spece di pseudo-insertion_sort più efficiente e fatto apposta per il caso in cui c'è un solo elemento disordinato, appunto quello da aggiungere.
L'aggiunta in ordine non sempre è migliore, ma preferisco distribuire un po' di carico di lavoro piuttosto che avere le aggiunte immediate ed eseguire poi un algoritmo di sorting per una lista completamente disordinata u.u