Пытаюсь решить задачу. Есть матрица 2000x2000. Хочу представить ее ввиде графа и обходить с BFS/DFS. Есть лимит на время выполнения (2s). Простое создание вершин занимает более 2s! Но мне еще нужно создать Adjacency matrix + пройтись BFS/DFS + какая-то логика решения так что время еще будет увеличено! Вот так создаю вершины:
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;
}
}Нормально ли это использовать ООП для представления больших графов или нужны исключительно массивы?
Для плотных графов используй матрицу смежности (boolean[][] для невзвешенных графов или int[][] для взвешенных), для разреженных — списки смежности (List<Integer>[] или List<Edge>[], где Edge — пара (конец ребра, вес))
Спасибо! А как к матрицам применять обход BFS/DFS? Хранить еще массив такой же размерности с цветами? А если еще какое-то свойство нужно для вершины — то заводить еще массив? Для разреженных — смотря какого размера, если использовать Edje то опять можно попасть на OutOfMemeory или сильно снизить скорость создавая объекты. Так ведь?
Зачем вообще в явном виде хранить граф, если у нас матрица?.. Казалось бы,
dfs(int x, int y)и вперёдНо ведь нужно из матрицы полноценный граф соорудить сперва? В матрице только информация о связях (это не матрица смежности еще)
Ну можно написать что-то в духе
Или предполагается, что в матрице соединены произвольные клетки, а не соседние?
В задачах по программированию ребер в разреженном графе обычно максимум 500 тысяч, а чаще всего 100-200 тысяч, такое количество объектов не сильно снизит скорость.
Также, если сильно напрягают коллекции чисел, их можно избежать (github link)
Хм... может я не верно придумал мат модель для решения... В матрице 2000х2000 каждая ячейка — это вершина графа, которая может иметь до 4-х ребер (соединена серху, снизу, слева, справа). Т.е. по сути у меня 4*10^6 вершин и максимум (примерно) 2*4*10^6 ребер. Это явно больше чем 500 000 :) Тут матрица связности не нужна, т.к. граф разрежжен, а список смежности будет состоять из 4 миллионов вершин! Может это плохая идея рассматривать матрицу как граф???
Клетчатый лабиринт лучше всего не пытаться явно представить в виде графа, а обходить его, как выше написал adamant
Во-первых, в конструктор HashMap можно передавать capacity, иначе время на инициализацию будет не O(n), а O(n*logn)
Во-вторых, непонятно зачем тут HashMap, если все id будут иметь индексы от 0 до (n*m-1)... во всяком случае если делать
int id = i * m + j;(непонятно зачем тут +1)ОК, спасибо за совет! Но тут скорей проблема не в инициализации, а в самом подходе: надо ООП или нет. (а +1 в id _ это так, для веселости ;) )
Нельзя сказать универсальное правило. Иногда использовать ООП нормально, иногда нет. При больших ограничениях злоупортеблять ооп конечно вредно, в вашем случае я думаю Vertex это норм, а Color лишнее... color в этой задаче думаю можно представить как int.
Замедляет ещё использование обёрток типа Integer, когда можно воспрользоваться int. Про ненужность HashMap я к тому, что можно использовать Vertex[], тогда код будет работать намного быстрее.
В обоих случаях O(n), просто константы разные.
Создаётся хэш таблица с маленьким initial capacity. Потом всякий раз, когда количество элементов мало (стандартное пороговое значение это 3/4 capacity), размер таблицы увеличивается в 2 раза.... уууупс и где-то тут я понял что нужно 2n операций. Действительно, моя ошибка.
судя по попыткам, вы используете
new Scanner(System.in)иSystem.out.print()для ввода/вывода. Это очень медленно. Большинство местных джавистов пишет свои классы для этих целей, см. например yaal by Egor