Warm tip: This article is reproduced from serverfault.com, please click
grid java multidimensional-array row

Efficient way of linking grid tiles while creating distinct edges in Java

发布于 2020-12-04 17:42:28

There is a grid.

static Double [][] myTiles = new Double[row][column];

The goal is to connect each tile with an adjacent tile. Compare a value between the pair, construct a link between tiles to create the minimum spanning tree for a given grid.

Below is my initial approach to this issue:

Nine ( 9 ) groups of tiles are identified.

This is a picture of a grid of cells that are separated into nine distinct areas.

These groups have the same logic and the same availability of adjacent squares.

For each cell in my grid I decided to check a cell above, below, to the left and to the right. Certain cells cannot perform all checks when located on an edge of the grid. Below is the movement representation for each type of a tile.

A grid with the move availability for each tile.

My current solution is a nested for-loop with the below if-else statements:

            if ( row == 0 && column == 0)   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 && ( column > 0 && column < myTiles.length ) )   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 && column == myTiles.length )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 && row < myTilese[row].length ) && column == 0 )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length && column == 0 )  {
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length && ( column > 0 && column < myTiles.length ) )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == myTilese[row].length &&  column == myTiles.length )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 &&  row < myTilese[row].length ) && column == myTiles.length )  {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}
            
            else    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}

The above logic creates at least two links and at most four. That's a lot of diplicates to sort when it comes to building a minimum spanning tree.

Is there an eloquent way of representing the above if-else block?

Questioner
Ivan
Viewed
0
分享
Ivan 2020-12-08 15:50:03

The most efficient way is to limit amount of links created per tile.

To make the logic produce less duplicates it is helpfull to escape the nesting-loops solution, and instead implement two separate for loops.

First step: Iterate through each tile, of each row column by column and make one link east or left until the edge is detected. When the edge is detected, skip the pointer one row down.

The second step: Iterate through each tile, of each column row by row and make one link south or down until the edge is detected. When the edge is detected, skip the pointer one column right.

A divided grid with traces of links connecting rows and columns.

This logic covers all the tiles, prevents IndexOutOfBoundsChecks, and reduces amount of duplicate links created.

        for ( tileColumn = 0; tileColumn < 74; tileColumn ++ )  {
            myEdge = new GraphEdge<String>();
            
            mySortingQueue.offer(createEdgeEast(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileColumn == 73 && tileRow < 34 ) {   
                tileColumn = 0;
                tileRow++;  }
        }   /*  End of the column for loop  */
        
        tileRow = ZERO;
        tileColumn = ZERO;
        
        for ( tileRow = 0; tileRow < 34; tileRow++ )    {
            myEdge = new GraphEdge<String>();
            mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileRow == 33 && tileColumn < 74)  {   
                tileRow = 0;
                tileColumn++;   }
        }   // End of the row for loop

热门帖子

1
[内购终身版限时免费][macOS] Barbee - 拯救你的菜单栏空间（刘海屏快来！
2
关于出镜旅游
3
原来凤凰系统已经倒闭 2 年多了
4
B 站必火推广好假啊
5
Apple TV 经常自动开机
6
推特尼日尼亚去也涨价了,羊毛没了
7
求推荐 3k 左右的烘干机
8
真搞笑， homepod 在 windows 上延迟比在 mac 上还小。。
9
[疑难杂症] 安卓面具求助，拯救楼主的 3000 软 QAQ
10
收个路由器，稳定的。

热门github

1
Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information
2
A Windows and Office activator using HWID / Ohook / KMS38 / Online KMS activation methods, with a focus on open-source code and fewer antivirus detections.
3
Get up and running with Llama 2, Mistral, Gemma, and other large language models.
4
该项目可以让你通过订阅的方式使用Cloudflare WARP+，自动获取流量。This project enables you to use Cloudflare WARP+ through subscription, automatically acquiring traffic.
5
Multi functional app to find duplicates, empty folders, similar images etc.
6
Xray panel supporting multi-protocol multi-user expire day & traffic & ip limit (Vmess & Vless & Trojan & ShadowSocks & Wireguard)
7
The Free Software Media System
8
lightweight, standalone C++ inference engine for Google's Gemma models.
9
📚 Freely available programming books
10
A collective list of free APIs
11
1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java
12
🎓 Path to a free self-taught education in Computer Science!
13
Curso para aprender el lenguaje de programación Python desde cero y para principiantes. 75 clases, 37 horas en vídeo, código, proyectos y grupo de chat. Fundamentos, frontend, backend, testing, IA...
14
This repository contains System Design resources which are useful while preparing for interviews and learning Distributed Systems
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.