Innanzitutto, questa domanda non riguarda realmente ricerca binaria poiché né abbiamo dati ordinati , né alcun dato ordinabile. : -)
W.r.t l'affermazione "unsortable" vedi sotto; ma penso che il termine titolo "unsortable" sia importante qui, perché, afaikt, qualsiasi ordinamento richiederebbe la visita di tutti i "nodi", che è esattamente quello che voglio evitare.
Domanda : Fornisci i termini per l'algoritmo / approccio di ricerca algoritmico riportato di seguito .
Introduzione a lungo termine con l'esempio : Quello che ho è, in sostanza, un elenco di nomi e ho bisogno di trovare tutti i nomi "validi". Tuttavia, per determinare i nomi validi, devo interrogare un sistema di terze parti, che, in termini di questo problema semplificato, ha solo una funzione di interfaccia:
// remote 3rd party interface
// return true if all names in the given list are valid
// [names] may be a list of 1 - n strings
bool has_invalid_names(List names)
Quindi, data la mia lista l := [a, b, c, ...] , ho bisogno di raccogliere tutti i nomi validi, ovvero has_invalid_names([i]) == false .
La cosa più semplice è ovviamente fare una ricerca lineare , ma ciò significa chiamare all_names_are_valid(i) n volte, il che può diventare proibitivo, poiché ogni chiamata remota ha un po 'di overhead.
Dato che ci aspettiamo solo un pochino nomi non validi nella lista iniziale, noi intuitivamente abbiamo avuto l'idea di tagliare l'elenco a metà e cercare oltre questi:
a) Split list in halve
b) for each half, check if any names are invalid
c) rinse and repeat for all slices that show "invalid"
until you're down to calls with just single names
Che crea solo un albero di fette dell'elenco iniziale
[a, b, c, d, e, f, g*, h]
/\
[a, b, c, d] [e, f, g*, h]
/\ /\
[a, b] [c, d] [e, f] [g*, h]
/\ /\ /\ /\
[a][b] [c][d] [e][f] [g*][h]
Se il numero di nomi non validi è piccolo, devono essere esplorati solo pochissimi percorsi lungo quest'albero, essenzialmente richiedendo solo le chiamate vicino a log2(n) , dove il caso peggiore, in cui tutti i nomi non sono validi, sarebbe 2*n-1 .
In questo esempio precedente, supponendo di provare le sotto-liste da sinistra a destra, dovremmo chiamare la funzione remota 6 volte per trovare il g* "non valido". Per n maggiori, i risparmi sarebbero più significativi, a patto che solo pochi articoli non siano validi.
Quindi, ho una soluzione a questo problema, ma che cos'è questa roba chiamata ?
- Esiste un nome specifico per che suddivide un set di dati in un albero di sezioni ?
-
Che cosa potrebbe essere chiamato l'algoritmo di ricerca / parti di esso?
Sembra una specie di unsorted ricerca per albero binario , dove un predicato viene applicato a ogni nodo per decidere quali sotto-alberi seguire, ma sono davvero debole sull'intero algoritmo e amp; dati strutture zoo. : -)
Meccanicamente, sembra più nella direzione di ciò che mappa, filtro (, riduzione) raggiungere, con una funzione mappa più complessa.
In altre parole: se vuoi risolvere questo problema, quali librerie, algoritmi esistenti e strutture dati useresti? - > Nota: l'intera domanda è stata scatenata dal fatto che sono pigro e non voglio codificare tutto ciò che affetta, tree'ing e possibilmente ricorsero me stesso, ma la Wide Net non mi ha indulgere con nulla di prefabbricato. : -)