• Post Reply Bookmark Topic Watch Topic
  • New Topic

Best Sorting objects method  RSS feed

 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi @ll,

I am searching information about sorting objects in Java.

I need to sort object in an Array using minimum resources.

They are sorted by attribute counting. For example;



It should be done for 1 million objects. I dont want to use quickSort(), because it uses memory.

Could someone, give some tips or link with info about this specifics cases, please?

Regards, ISaac


 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Google in-place sort. They use a constant amount of memory, but in general are not as fast. Also consider whether the sort needs to be stable.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isaac Ferguson wrote:I need to sort object in an Array using minimum resources.

It should be done for 1 million objects. I dont want to use quickSort(), because it uses memory.

What resource CAN you use more of?  there's always a trade-off between memory, speed, disk, complexity, and probably some others i'm not thinking of. the art is always figuring out which is most important to you. If you are on a mobile device, memory might be more important (although becoming less so all the time).  If you have a missile guidance system, speed would be most important.

so without knowing what your all your constraints are, it's kind of hard to give suggestions.
 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am studying how to design it, maybe with this info we can comment it;

It is a module which will be connected to an open source social network. The will be in a different server that the social network irself.

It is a distributed app(REST, Java,  TDD). I would like to do it mainly for tablets, Ipads, phones, ...mobile devices.

The only functionality of the code is to tidyUp objects, in base of an attribute called counter. It should be able to hold 500.000 users simultaneously, from several different countries.

Every object has a path to one external image, and one external file with text....

Of course speed is very important else the user will get bored, and memory because it will be used mainly in mobile devices ....

Is this info useful for suggestions?
 
Paul Clapham
Sheriff
Posts: 22835
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isaac Ferguson wrote:The only functionality of the code is to tidyUp objects, in base of an attribute called counter. It should be able to hold 500.000 users simultaneously, from several different countries.

Every object has a path to one external image, and one external file with text....

Of course speed is very important else the user will get bored, and memory because it will be used mainly in mobile devices ....


There's something I don't quite understand here. Your application is going to hold information about 500,000 users, but it's going to run on a mobile device? Earlier you said "It is a module... will be in a different server than the social network". Do you really intend for that server to run on a mobile device? Or is the plan for mobile devices to connect to that server? That would make more sense to me... and if it's only the server which contains that large amount of information, then you don't need to worry so much about memory constraints. In fact you probably wouldn't need to sort the data, or even keep it all in memory for that matter.
 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The module runs in the cloud, it is a REST service.

Even when it is not a problem with the server, I want to make the best possible code ever, it is also a personal challenge to it as fast and compact as posible. It helps me to program better...

In fact you probably wouldn't need to sort the data, or even keep it all in memory for that matter.


Why? Is it automatic?? ;)

I need to code for dityUp the one with the higher couter to the one with the minimum one.
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why do you want half a million users in memory?

There is no point.
 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A DB can be also an option
 
Paul Clapham
Sheriff
Posts: 22835
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isaac Ferguson wrote:A DB can be also an option


Agreed. Putting the users into a List is technically an option, too, just not a good option. So if you're looking for an exercise in writing code for sorting a list, then carry on. But if you're actually designing this server, then I think (my opinion here) that you're going way off course. Optimizing a sort algorithm is one of the last things you should be doing, and it's only when you find that (a) you need to sort a list, and (b) it's taking too much time or memory, that you should be trying to improve the performance of that sort.
 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When the objects are in a DB, it use to take plenty of time.

a) I need to sort a list b) I am afraid that the DB option could not be efficient enough. I need to desing the system to be sure that later on it causes not performances problems

Any suggestion, please?
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are heading down the path of premature optimization. A good design involves knowing when existing solutions are a good fit and when they're not. You haven't stated the requirements for response time and you haven't gathered any performance results to know if the requirement cannot be met by existing solutions (e.g. database).
 
Isaac Ferguson
Ranch Hand
Posts: 1063
3
Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok so I carry on with my DB solution, and I will check and optimize later...

Cheers, Isaac
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isaac Ferguson wrote:Ok so I carry on with my DB solution, and I will check and optimize later...

Sounds like possibly the way to go at the moment.

One thing (in fact, possibly the MOST important thing) about Object-Oriented programming is not to re-invent the wheel. And writing a custom sort from scratch is a classic case in point.

The writers of the existing sort routines in Java - not to mention databases, which were created for precisely this kind of problem - have probably forgotten more about the mechanics of sorting large volumes of data than you (or I) will ever know, so unless this is simply a mental exercise, use existing code.

Mobile devices obviously have constraints; although in these days of quad-core tablets, and smartphones with gigabytes of memory, they're nowhere near as strict as they used to be.
However, holding half a million user objects on every client is a pretty sure way to slow it down, whether you actually sort them or not - so thinking about where you keep stuff is likely to solve far more throughput issues than writing the most efficient, tailored sort that has ever been.

OTOH, if this is a web-based app, the biggest constraint on it is likely to be network bandwith, so anything you can do to keep that to a minimum is likely to make your users happy.

HIH

Winston
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isaac Ferguson wrote:it is also a personal challenge to it as fast and compact as possible.

But these two conditions are often at direct odds with each other.  If you want to make it faster, you often put more stuff in memory.  If you want to reduce memory, you need more disk I/O or network data transmission, both of which would slow things down.

The best tip i'd give you would be to WRITE DOWN what your specs are.  and by "specs", I mean "specific items".  Phrases like "as fast as possible" is vague and not helpful. There are always ways to make things go faster (including buying better hardware).  But having a spec like "response is retured in under 1.3 seconds" - that IS a spec. Saying "total peak memory footprint is under 500MB" IS a spec.
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The points I have not seen raised (sorry if I missed it) are:

1. How much does this list change and how long would a sorted list be valid?

2. What changes the list and how many items are changed at one time?

Bill
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i would also add

3) is the list already mostly sorted, or is it closer to being random?
 
Paul Clapham
Sheriff
Posts: 22835
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The question which comes before that is: Why are these users being kept in a List anyway?

I wouldn't be surprised if it's necessary to find a user's information when you're given a user number. And if that's the case then the natural thing to do would be to use a Map. Using a List would be, um, not optimal. You'd have to make sure that the List was always sorted, so that you could use a binary search. And even then a binary search in a large list is slower -- O(log n) -- than accessing a map via a key -- O(1). Not to mention that adding a new user could require resorting the List.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!