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?