Оптимизация обнаружения короткого замыкания в большой атомной ячейке: стремление улучшить время выполнения ⇐ JAVA

[Anonymous]

Контекст: Я работаю над проблемой моделирования, включающей матрицу размера n x n, представляющую атомы. Каждый атом может быть как проводником, так и нет. Моделирование включает в себя преобразование непроводящих атомов в проводящие и определение того, создает ли это «короткое замыкание», определяемое как соединение проводящих атомов сверху вниз матрицы.

Проблема: Существующий алгоритм обнаружения замыканий неэффективен для больших матриц (например, 2000x2000). Мне нужно оптимизировать его, чтобы сократить время выполнения, в идеале до O(logn) или лучше.

Фактический код ячейки:

публичный класс CeldaAvanzada реализует Celda { частный DisjointSet disjointSet; частный интервал n; частная логическая кортосхема; частное логическое значение[][] esConductor; частный int LastI, LastJ; частный int[] transmutadosSuperior; частный int[] transmutadosInferior; частный int contadorSuperior ; частный int contadorInferior; public void Inicializar(int n) { это.n = n; disjointSet = новый DisjointSet(n * n); esConductor = новое логическое значение[n][n]; кортосхема = ложь; transmutadosSuperior = новый int[n]; // Максимальное увеличение числа столбцов transmutadosInferior = новый int [n]; контадорСупериор = 0; контадоринфериор = 0; } public void RayoCosmico(int i, int j) { if (!esConductor[j]) { esConductor[j]=истина; если (я == 0) { transmutadosSuperior[contadorSuperior++] = j; } иначе, если (я == n - 1) { transmutadosInferior[contadorInferior++] = j; } последний я = я; последнийJ=j; uniteAdjacentAtoms (я, j); } } общедоступное логическое значение Cortocircuito() { возвратная кортосхема;

Private void uniteAdjacentAtoms(int i, int j) { int index = getKey(i, j); int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; for (int k = 0; k < dx.length; k++) { int ni = я + dx[k]; int nj = j + dy[k]; if (ni >= 0 && ni < n && nj >= 0 && nj < n && esConductor[ni][nj]) { disjointSet.union(index, getKey(ni, nj)); } } actizarBanderasDeConexion (индекс);

private void actuizarBanderasDeConexion(int indice) { логическое conexionSuperior = ложь; // Проверяем, что необходимо извлечь корзину если (contadorSuperior > 0) { for (int k = 0; k 0) { for (int l = 0; l < contadorInferior; l++) { int indiceInferior = getKey(n - 1, transmutadosInferior[l]); если (disjointSet.isConnected(indice, indiceInferior)) { кортосхема = правда; перерыв; // Выход на связь с соединением } } }

private int getKey(int i, int j) { вернуть я * п + j; } @Override публичная строка toString() { StringBuilder sb = новый StringBuilder(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == LastI && j == LastJ) { sb.append("*"); // Маркамос el último átomo afectado } еще { sb.append(esConductor[j] ? "X" : "."); // X пара проводников, . без проводников } } sb.append("\n"); } вернуть sb.toString(); } Реализация непересекающихся множеств

класс DisjointSet { частный int[] родительский; частный int[] ранг; public DisjointSet (размер int) { родитель = новый int[размер]; ранг = новый int[размер]; for (int я = 0; я