• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

Best Sorting objects method

 
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • 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


 
Saloon Keeper
Posts: 12251
259
  • 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.
 
lowercase baba
Posts: 12893
63
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.
 
Angus Ferguson
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • 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?
 
Marshal
Posts: 25798
69
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.
 
Angus Ferguson
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • 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: 12251
259
  • 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.
 
Angus Ferguson
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A DB can be also an option
 
Paul Clapham
Marshal
Posts: 25798
69
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.
 
Angus Ferguson
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • 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?
 
Bartender
Posts: 7290
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java 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).
 
Angus Ferguson
Ranch Hand
Posts: 1402
3
Netbeans IDE Spring Java
  • 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
 
Bartender
Posts: 10777
71
Hibernate Eclipse IDE 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
Posts: 12893
63
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.
 
Author and all-around good cowpoke
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
Posts: 12893
63
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
Marshal
Posts: 25798
69
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.
 
    Bookmark Topic Watch Topic
  • New Topic