存储和操作数据的最佳数据结构?
我正在编写一个简单的 Java 程序,它将输入一个文本文件,其中包含一些代表 (nxn) 矩阵的数字,其中数字由空格分隔。例如:
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
然后我想将这些数字存储在一个数据结构中,然后我将使用该数据结构来操作数据(其中包括比较相邻数字以及根据特定规则删除某些数字。 如果删除某个数字,则该数字上方的所有其他数字都会减少空格量。 对于上面的例子,如果说我删除 8 和 9,那么结果将是:
() 2 3 ()
1 6 7 4
5 1 2 3
4 5 6 7
所以数字在它们的列中下降。 最后,给定的矩阵始终是方阵(因此始终为 nxn,其中 n 始终给定且始终为正),因此,数据结构必须灵活才能几乎接受任何 n 值。
我最初是在二维数组中实现它,但我想知道是否有人有更好的数据结构的想法,我可以使用它来提高效率(这将使我能够更快地访问数组中的所有相邻数字)矩阵(行和列)。 最终,mu 程序将根据规则自动检查相邻数字,我删除数字,重新格式化矩阵,然后继续,最后我希望能够创建一个人工智能,它将从矩阵中删除尽可能多的数字对于任何 nxn 矩阵,尽可能以最少的移动量。
I am writing a simple Java program that will input a text file which will have some numbers representing a (n x n) matrix where numbers are separated by spaces. for ex:
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
I then want to store these numbers in a data structure that I will then use to manipulate the data (which will include, comparing adjecent numbers and also deleting certain numbers based on specific rules.
If a number is deleted, all the other numbers above it fall down the amount of spaces.
For the example above, if say i delete 8 and 9, then the result would be:
() 2 3 ()
1 6 7 4
5 1 2 3
4 5 6 7
so the numbers fall down in their columns.
And lastly, the matrix given will always be square (so always n x n, where n will be always given and will always be positive), therefore, the data structure has to be flexible to virtually accept any n-value.
I was originally implementing it in a 2-d array, but I was wandering if someone had an idea of a better data structure that I could use in order to improve efficiency (something that will allow me to more quickly access all the adjacent numbers in the matrix (rows and columns).
Ultimately, mu program will automatically check adjacent numbers against the rules, I delete numbers, re-format the matrix, and keep going, and in the end i want to be able to create an AI that will remove as many numbers from the matrix as possible in the least amount of moves as possible, for any n x n matrix.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
在我看来,当你开始时就知道数组的长度,最好使用数组。简单的数据类型将更容易导航(直接访问)。然后,使用 LinkedLists,您将能够删除中间值,而无需重新排列矩阵内的数据。这将使您的“顶部”值为空。在你的例子中:
希望这有帮助。
In my opinion, you yo know the length of your array when you start, you are better off using an array. A simple dataType will be easier to navigate (direct access). Then again, using LinkedLists, you will be able to remove a middle value without having to re-arrange the data inside you matrix. This will leave you "top" value as null. in your example :
Hope this helps.
您可以使用大小为 n*n 的一维数组。
要访问坐标为
(i,j)
的元素,请使用myMatrix[i + j * n]
。要放置元素,请使用 System.arraycopy 来移动线条。使用特殊值(例如
Integer.MIN_VALUE
)作为()
孔的标记。我希望这将是最快且内存效率最高的解决方案。
You could use one dimensional array with the size
n*n
.To access element with coordinates
(i,j)
usemyMatrix[i + j * n]
. To fall elements useSystem.arraycopy
to move lines.Use special value (e.g.
Integer.MIN_VALUE
) as a mark for the()
hole.I expect it would be fastest and most memory efficient solution.
数组访问速度相当快。访问相邻元素很容易,因为您只需增加相关索引(认识边界)。您可以编写方法来封装那些经过充分测试的操作。虽然元素“掉落”可能会变得复杂,但如果您通过编写经过良好测试的方法将其模块化,那么应该不会太糟糕。
尽管如此,如果您不需要绝对的最佳速度,还有其他选择。
您可能还需要考虑修改的循环链表。在实现数独求解器时,我使用了此处概述的结构。查看图像,您会发现这将允许您根据需要修改二维数组,因为您所需要做的就是移动指针。
我将在这里发布描述数据结构的相关图片的屏幕截图,尽管如果有人警告我,如果我侵犯了作者的某种版权或其他权利,我将不胜感激,在这种情况下,我会将其删除...
Array access is pretty fast. Accessing adjacent elements is easy, as you just increment the relevant index(s) (being cognizant of boundaries). You could write methods to encapsulate those operations that are well tested. Having elements 'fall down' though might get complicated, but shouldn't be too bad if you modularize it out by writing well tested methods.
All that said, if you don't need the absolute best speed, there are other options.
You also might want to consider a modified circularly linked list. When implementing a sudoku solver, I used the structure outlined here. Looking at the image, you will see that this will allow you to modify your 2d array as you want, since all you need to do is move pointers around.
I'll post a screen shot of relevant picture describing the datastructure here, although I would appreciate it if someone will warn me if I am violating some sort of copy right or other rights of the author, in which case I'll take it down...
尝试使用 LinkedList 数组。
Try a Array of LinkedLists.
如果您希望数字自动下降,我建议您使用列表作为列。
If you want the numbers to auto-fall, I suggest you to use list for the coloumns.