Domanda sull'algoritmo di ricerca

Question

Domanda sull'algoritmo di ricerca

#1 da (0 voti)
#2 da (0 voti)

0

Ho bisogno di recuperare cinque stelle da un gruppo di stelle in modo da poterle nascondere girando la loro bandiera visibile su "false".

Conosco il valore di coordinate x, y di ogni stella che sto cercando. Il mio algoritmo apre una transazione e recupera un gruppo di stelle i cui valori x, y rientrano nelle estensioni delle cinque stelle che sto cercando.

Questo è più veloce dell'apertura di cinque transazioni separate e guardando individualmente una posizione x, y di ciascuna stella.

Con il gruppo di stelle sotto quello che voglio fare è confrontare il valore x, y di ogni stella per trovare una corrispondenza con quella delle cinque che sto cercando.

Gruppo di oltre 400 stelle da cercare

    *********************************************
    *********************************************
    *********************************************
    *********************************************
    *********************************************
    *********************************************
    *********************************************
    *********************************************
    *********************************************

Il mio pensiero su questo è che ho due scelte per iterare attraverso la collezione:

(1) Posso scorrere le oltre 400 stelle una alla volta, prendere i valori x, y di ciascuna e quindi scorrere tra i cinque gruppi di coordinate per vedere se corrisponde a una delle il cinque che sto cercando.

(2) Posso scorrere le "cinque stelle per trovare" una alla volta e quindi scorrere la collezione di oltre 400 stelle cercando una corrispondenza

NB:

La collezione di stelle ha oltre 400 stelle che rientrano nelle estensioni.

La proprietà "visibile" funziona solo per gli elementi nella raccolta di stelle.

La raccolta stars_to_find ha le coordinate delle cinque stelle che sto cercando.

Frammenti di codice

(1)

foreach (Star star in stars)
{
    foreach (Star star_to_find in stars_to_find)
    {
        if (star.Coordinates.Equals(star_to_find.Coordinates))
        {
            star.Visible = false;
        }
    }
}

(2)

foreach (Star star_to_find in stars_to_find)
{
    foreach (Star star in stars)
    {
        if (star.Coordinates.Equals(star_to_find.Coordinates))
        {
            star.Visible = false;
        }
    }
}

Il metodo di ricerca è, (1) o (2), più veloce dell'altro? Esiste un algoritmo di ricerca diverso che potrebbe funzionare meglio?

algorithms search

posta scott_f 03.11.2015 - 00:25

fonte

2 risposte

0

In generale, quando devi cercare una raccolta per elementi che rientrano in un intervallo di coordinate 2D, probabilmente dovresti usare un quadtree (o un octree per le coordinate 3d).

risposta data 03.11.2015 - 03:43

fonte

Leggi altre domande sui tag algorithms search

Cosa succede al superhandler con variabili di istanza Qual è il valore nel nascondere i dettagli attraverso le astrazioni? Non c'è valore nella trasparenza?

score 0 · Accepted Answer

Come regola generale, metti la raccolta che è più facile da tracciare sul ciclo più interno. Le tue 5 stelle da trovare sarebbero solo un semplice array, quindi inseriscile nel ciclo interno.

Tuttavia è molto più efficiente se non hai bisogno di un ciclo in primo luogo o ridurre il numero di iterazioni del ciclo.

Ad esempio potresti mantenere le stelle in una matrice% co_de nidificata (array di matrici) in modo che tu possa fare Star[][] e ottenere direttamente la stella che ti serve.

Se hai bisogno di qualcosa di meno denso allora puoi usare una hashmap e usare la chiave Coordinates. In entrambi i casi l'algoritmo finale si riduce a:

foreach (Star star_to_find in stars_to_find)
{
    stars.get(star_to_find.Coordinates).Visible = false;
}