Forums Register Login

Meaningful 2D array sort?

+Pie Number of slices to send: Send
Is there any meaninful way to sort/search a 2D array. For instance if I have a 2D int[][] with values:

1 5 3
2 4 8
6 9 7

Is there a meaninful way to sort this to

1 2 3
4 5 6
7 8 9

so that if I do a search for 5, I can use a binary search algorithm (either a custom one or one provided by the standard library) to optimize the search speed.
+Pie Number of slices to send: Send
One way would be to place all of the integers from the 2D array into a 1D array, sort it, and then put the numbers back into the 2D array.
+Pie Number of slices to send: Send
Keith,
Thanks for the reply. Of course you're right. For any real world problem this is what I would do. Really, what happened was that I read at another site that it was twice as expensive to access a 2D array than a 1D array. I decided to test this assertion out and tried to implement the following code:

Obviously this code will not compile bc the Arrays.sort(int[]) method will not sort a 2D array. In this case converting the 2D array to a 1D array nullifies the test I was trying to conduct. So.. my original question stands, is there any other way?
One afterthought: is there a better/more accurate of generating the time stamp than calling the

method?

[ January 22, 2006: Message edited by: Garrett Rowe ]
[ January 22, 2006: Message edited by: Garrett Rowe ]
+Pie Number of slices to send: Send
Technically, Java does not have 2D arrays. Really you are using an array of arrays here. This might be why people claim that 2D arrays are slow.

Interestingly, you CAN use the another version of the sort() method: Arrays.sort(Object[], Comparator). Since arrays are Objects in their own right this method will work. However, you will then have to define what it means for one array to be "less than", "greater than", and "equal to" another.

Layne
+Pie Number of slices to send: Send
Layne

It is possible to do this, however I really would have to implement my own sort() implementation then. For instance if I start out with my original [3][3] array:
1 5 3
2 4 8
6 9 7
I could call the Arrays.sort() method to each "row" and get the result
1 3 5
2 4 8
6 7 9
But then I can't think of a meaningful way to define a Comparator to give me anyting other than what I already have.

Can anyone think of another way to test the 2D array accessor speed other than the one I have already outlined?
+Pie Number of slices to send: Send
 

Originally posted by Garrett Rowe:
Layne

It is possible to do this, however I really would have to implement my own sort() implementation then. For instance if I start out with my original [3][3] array:
1 5 3
2 4 8
6 9 7
I could call the Arrays.sort() method to each "row" and get the result
1 3 5
2 4 8
6 7 9
But then I can't think of a meaningful way to define a Comparator to give me anyting other than what I already have.


I wasn't considering sorting indivdual rows. That may or may not be part of the problem depending on how you define "sorting a 2D array". What if you start with the 3x3 array that you gave but with the 2nd and 3rd rows switched:

1 5 3
6 9 7
2 4 8

Then if you want to sort each row, you will get

1 3 5
6 7 9
2 4 8

I would imagine that you want to sort the rows from here to get the result you gave above:

1 3 5
2 4 8
6 7 9

You could define a Comparator that would give this sort order. If you are using Java 1.5, you will probably define a Comparator<int[]>. Of course, this depends on how you define when one array is "less than" another.


Can anyone think of another way to test the 2D array accessor speed other than the one I have already outlined?



Well, it depends on exactly what you want to test. If you are just testing the access of an element in the array, I can think of a lot easier tests. To access setting the value, you can do something like

Similar methods could be created to test accessing an element of the 2D array and for setting and accessing elements in 2D arrays. In fact, I think that these are much better tests since you don't have the overhead of the sorting algorithm. You are ONLY testing how the array is accessed.

Layne
+Pie Number of slices to send: Send
Ok, so implementing Layne's suggestion I implemented the following test.


Based on this test on my laptop, there is about a 33% difference between accessing an element in a 2D array and a 1D array.
+Pie Number of slices to send: Send
The clock time is not necessarily an accurate measurement of how long an operation takes. This is because the system could be doing other things, especially in this age of multi-tasking operating systems. Unfortunately, this is about the best empirical method availble for measuring such things. It might be interesting to run this program multiple times and taking the average and standard deviation for the sample.

Also, you might want to test getting array elements (i.e. value = array[x][y]). I wonder if there is much of a difference between setting and gettign an element.

Layne
I didn't do it. You can't prove it. Nobody saw me. The sheep are lying! This tiny ad is my witness!
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 1501 times.
Similar Threads
Random Numbers II
What is Object[][]
Two dimensional data structures?
Sudoku
Binary search slower or faster than sequential search
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 15:10:37.