@StadardOil, lo so che non mi leggi MA ogni tanto anche tu c'azzecchi qualcosa
a) inverto l'ordine: calcolo la distanza, controllo che non sia uguale ed eventualmente la inserisco nel vettore
b) tengo il vettore ordinato, cosa che mi permetterà di cercare la prossima distanza calcolata con una ricerca dicotomica invece che con un semplice scorrimento, al prezzo di un continuo "riordinamento parziale" del vettore ho un forte alleggerimento della ricerca
c) quando cerco una distanza, se non la trovo sono almeno già nel punto del vettore dove devo inserirla, questo ammetto sia un po' una banalità, discende del punto b), ma io sono dell'idea che "tutto fa brodo",
ma quella che spero essere la vera differenza è un'altra
d) pre-ordino il vettore dei punti (ok, ok, i vettori delle due coordinate, ma io ragiono come se fosse un singolo vettore di punti)
perché ne effettuo un pre-ordinamento?
e) ho pensato che la distanza tra due punti è "non maggiore" della somma delle distanze dei due punti dall'origine degli assi
da questo discende che il valore massimo delle distanze è tanto più basso tanto i punti sono vicini all'origine degli assi
da questo discende che la probabilità di trovare distanze basse è tra i punti vicini all'origine... da adesso li chiamo punti "bassi"
se i punti sono distribuiti casualmente la probabilità di avere "doppioni" di distanze (credo, non ho una dimostrazione formale di questo) scende con l'aumentare della distanza dall'origine degli assi (in soldoni: è più facile trovare doppioni se i numeri sono piccoli)
e quindi io testo per primi i punti bassi, sperando che mi vada bene
ultimo (ma poi magari ne trovo ancora) trucco:
f) tengo traccia del massimo (e magari del minimo) valore finora trovato, con un semplice test "prima" di cominciare la ricerca nell'array so già se per caso ho sforato il massimo, e siccome mi aspetto che i valori (dopo aver pre-ordinato i punti) mi si presentino tendenzialmente in salita (dai punti bassi ai punti alti), spero di poter abbastanza spesso, evitare proprio la ricerca nell'array e limitarmi ad aggiungere in fondo
a) giusto,
b) corretto, MA non consideri il COSTO dell'inserimento: devi spostare un blocco di dati si una cella verso il basso. Fare una copia NON COSTA ZERO, anzi, se vogliamo, COSTA DI PIU' di un semplice confronto, perche' il confronto e' tra valori che probabilmente sono gia' nei registri della CPU, mentre SICURAMENTE leggere una cella di memoria e riscriverla costa moooolti piu' cicli di clock
c) perfetto
d) non serve perche' d.1) non esiste il concetto di ordine TOTALE in 2 o piu' dimensioni, d.2) da nessuna parte c'e' scritto che i punti piu' vicini debbano essere necessariamente vicini allo zero
e) quasi: e.1) stai enunciando, in modo poco ortodosso,la priprieta' "triangolare" di una distanza, in cui i punti sono A, B, e O (origine)
e.2) TUTTO questo ragionamenti non ha senso. Ad esempio (1000,3000) e (1000, 3001) sono molto vicini tra loro ma sono MOLTO DISTANTI dall'origine. OVVIAMENTE le speranze vengono SEMPRE disattese: Lege di Murphy
Ed ora la svista:
f) l'autore sta cercando DUE DISTANZE UGUALI, NON due punti vicini!