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.
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 ]
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.
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?
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.
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
Post by:autobot
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