Traversal di grandi grafici con OOP

1

Sto cercando di risolvere il problema di un problema algoritmico. Ho una matrice 2000x2000. Voglio rappresentarlo come grafico e attraversarlo con BFS / DFS. Ho limiti di tempo per l'esecuzione dell'app (2 secondi). La creazione di vertici semplici ha richiesto più di 2 secondi! Pensaci: avrò bisogno di creare una matrice di Adjacency + eseguire BFS / DFS + fare una certa logica di business in modo che il tempo aumenti di più! Ecco il mio tentativo di creare i vertici del grafico:

Map<Integer, Vertex> allVertices = new HashMap<>();

final long b = System.currentTimeMillis();
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        final int id = i * m + j + 1;
        Vertex v = allVertices.get(id);
        if (v == null)
        {
            v = new Vertex(id);
            allVertices.put(id, v);
        }
    }
}
final long a = System.currentTimeMillis();
final long d = a - b;
System.out.println(String.format("took <%s> ms", d));

class Vertex
{
    Color color;
    final int id;

    public Vertex(final int id)
    {
        this.id = id;
    }   
}

Mi chiedo se questa pratica comune usi OOP per rappresentare i vertici di un grande grafico o devo usare solo gli array?

    
posta Michael Z 05.03.2015 - 11:40
fonte

2 risposte

1

Prima di tutto, quando crei la tua mappa iniziale, puoi essere sicuro che ogni vertice non sia già presente in esso. Stai perdendo un sacco di tempo per verificarlo.

In secondo luogo, negli algoritmi contesti con quel gran numero di input e vincoli di tempo relativamente piccoli, la soluzione migliore di solito richiede solo di memorizzare una riga di input alla volta, più una sorta di risultato cumulativo intorno la dimensione di una riga. Dovresti cercare prima quei tipi di soluzioni.

    
risposta data 05.03.2015 - 14:35
fonte
0

Solo perché vuoi fare cose OO non significa che devi creare il grafico fatto di nodi e vertici. È assolutamente bene catturare il grafico completo in un singolo oggetto e creare un'interfaccia OO bella e ben contrattata sopra.

Un'idea classica che ho usato è il concetto di un cursore che funziona sopra un grafico. Quel cursore conosce la rappresentazione interna e può sedersi sopra i nodi e viaggiare lungo i vertici verso altri nodi, o potrebbe sedersi anche sui vertici - è tutta una questione di scelta progettuale.

La cosa bella di questa interfaccia è che rimane ragionevolmente efficiente, anche se ti stai nascondendo all'utente se l'implementazione interna del grafico utilizza la matrice di adiacenza o gli elenchi di adiacenza.

    
risposta data 03.07.2015 - 22:39
fonte

Leggi altre domande sui tag