aspose file tools*
The moose likes Performance and the fly likes Design question for sorting array or treeset? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Design question for sorting array or treeset?" Watch "Design question for sorting array or treeset?" New topic
Author

Design question for sorting array or treeset?

Mohamed Farouk
Ranch Hand

Joined: Jun 08, 2005
Posts: 249
Hello Friends

I have to design a interface method which accepts an primitive [] array and perform a sort and return back an primitive [] array for a LOW LATENCY(high performance) requirement and will be called by many threads at the same time. The interface can be modified If i can justify that a different option (Se instead of int[])is better for performance.

Question:

1. I am not sure whether it is better to use (for sorting) [b]primitive array or some kind of LinkedList or TreeSet?[/b] If primitive array if so What is the reason to use primitive array instead of tree set?

2. If the method is read only (all sorting is done local to the method) and there is no instance variable in the class?, Do I need to worry about synchronisation?

3. What is the best method to sort ? Arrays.sort?, Collections.sort or anything else (Quick Sort?) which will render efficient sorting in Java 6 or Java 7 given this low latency requirement and maximum efficiency
Any response is greatly appreciated
Regards

Mohamed

SCJP, SCWCD, SCBCD, SCEA 5
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11499
    
  16

You seem to be asking for a magic bullet. There is no such thing. IF there was a "best method to sort", then that would be the only one anyone ever used. The problem is that with all CS questions, the answer is "it depends".

How much data do you have to sort? Is it mostly sorted already? Does it have to be a stable sort?

Even the term "maximum efficiency" doesn't mean anything. There are almost always tradeoff between speed, memory, complexity, and probably a few other variables. On a device with limited memory, you can't write something that would make 20 copies of a huge array, even if it would be fast because you don't HAVE that much memory.

I think you need better specs before you attempt to answer any of the questions you are asking.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Mohamed Farouk
Ranch Hand

Joined: Jun 08, 2005
Posts: 249
How much data do you have to sort? Is it mostly sorted already? Does it have to be a stable sort?


How much data do you have to sort? - 50 elements max,
Is it mostly sorted already? - no
Does it have to be a stable sort? Not sure what you mean by that.


All i want to find out is which is better (relative) way to sort given that a interface has int[]. Will it be less powerful to use some form of sorted list or set ?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
If the things you're sorting are primitives like int, I would use an array to store them. Chances are that it won't really make much difference anyway, but if there is a difference, the array should be faster. For the implementation, it will be hard for you to do much better than the implementation in Arrays.sort(), which will be a QuickSort for primitive arrays. It's possible for some situations you might do better with a radix sort. But don't count on it; the sort in Arrays is very good.

Ultimately, for performance questions like this, if you really need to know the difference, the best way is to try it both ways, and measure which one is faster. Very often, you end up discovering there is no significant difference.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11499
    
  16

If you only have 50 elements, I doubt it makes much difference at all which sort you use.

a stable sort is one that preserves the order of equal elements before and after the sort. say you spread out 52 playing cards in a random order, and you are going to sort them by rank only (ignoring the suit). further, assume that the 5's are in order of 5h, 5s, 5c, 5d (although they are not necesarily next to each other - there could be plenty of cards between each pair).

A stable sort guarantees that when the sorting is done, you still have the cards in that order: 5h, 5s, 5c, 5d.

An unstable sort makes no such guarantee (although the elements MAY be in the same order). You could end up with them in this order: 5d, 5c, 5s, 5h

If you are only sorting ints, then it doesn't really matter, since you can't tell one "5" from another.
Mohamed Farouk
Ranch Hand

Joined: Jun 08, 2005
Posts: 249
Thanks both for your help

What I inferred and learnt here is
1. What is stable sort
2. According to my requirement stable sort will not make any difference
3. Arrays sort is faster than Collections.sort

Thanks for all your help
I will post my synchronization related question next
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Design question for sorting array or treeset?