4

I've building a tree pagination in JSF1.2 and Richfaces 3.3.2, because I have a lot of tree nodes (something like 80k), and it's slow..

So, as first attempt, I create a HashMap with the page and the list of nodes of the page.

But, the performance isn't good enough...

So I was wondering if is something faster than a HashMap, maybe a List of Lists or something.

Someone have some experience with this? What can I do?

Thanks in advance.

EDIT.

The big problem is that I have to validate permissions of users in the childnodes of the tree. I knew that this is the big problem: this validation is slow, because I have to go inside the nodes, I don't have a good way to know if the user have permission in a 10th level node without iterate all of them. Plus to this, the same three has used in more places... The basic reason for why I was doing this pagination, is that the client side will be much slow, because of the structure generated by richfaces, a lot of tr's and td's, the browser just going crazy with this. So, unfortunatelly, I have to load all the nodes, and paginate just client side, and I need to know what of them is faster to iterate...

Sorry my bad english.

caarlos0
  • 20,020
  • 27
  • 85
  • 160
  • maybe duplicat to http://stackoverflow.com/questions/1518103/hashmap-vs-arraylist-performance-am-i-correct – Sam Mar 14 '12 at 12:38
  • 10
    This is not a problem of which collection you use; it's wrong to load all the data in one collection, the whole idea behind a paginator is to only load the relevant subset of the data that you need at that time. – Viruzzo Mar 14 '12 at 12:38
  • That depends on how you use those collections and what is slow. Can you provide some more details on how you'd implement that pagination. Also, did you profile your code? If so what was the slow part, accessing/filling the structure, loading the data or the expressions on the page? – Thomas Mar 14 '12 at 12:40
  • 2
    `List` and `Map` are collections with different goals, I think this comparison is wrong. – Sam Mar 14 '12 at 12:45
  • For the edit: your model is clearly wrong if you have to check permissions for an element by checking all of its children... You should go back and redesign the system so that it works in an efficient way, instead of trying to patch it in the view. – Viruzzo Mar 14 '12 at 14:52
  • hmm, I understand... what can you suggest me about how to do permission validation... – caarlos0 Mar 14 '12 at 16:31

4 Answers4

10

A hash map is the fastest data structure if you want to get all nodes for a page. The list of nodes can be fetched in constant time (O(1)) while with lists the time is O(n) (n=number of pages, faster on sorted lists but never getting near O(1))

What operations on your datastructure are too slow. That's what you have to analyse before you start optimization.

Andreas Dolk
  • 113,398
  • 19
  • 180
  • 268
2

It's probably more due to the fact that JSF is a performance pig than a data structure choice. The one attempt I've seen to create a JSF app could be timed with a sundial.

You're making a mistake by guessing about solutions without more knowledge about the root cause. I'd recommend that you profile your app to see where the time is being spent.

duffymo
  • 305,152
  • 44
  • 369
  • 561
  • +1: If you haven't measured the performance of your application, you are just guessing. I would bet you would find that HashMap doesn't even show up in your profile results. ;) – Peter Lawrey Mar 14 '12 at 12:47
2

The data structure to use always depends on how you need to store the data and how you need to access it. HashMap<K, V> is supposed to have constant time complexity in accessing the value, provided the key. When you call get(key), the hashCode() for key is computed and it's used to retrieve the related value. Unless you've got different keys that have the same hashcode (in which case you may have been doing something wrong, as while is not mandatory different objects should have different hash codes, at least in the majority of cases), this is usually fast.

Searching an element in a plain list requires scanning of the list, which will (almost) always be slower than computing an hashcode.

If you need to associate values with keys, a Map is the way. And HashMap should be fast enough.

I don't know too much about JSF, but I think - if the data structure and access pattern is the one that a Map is designed for - the problem is not the HashMap itself.

manub
  • 3,990
  • 2
  • 24
  • 33
-2

I would solve this with a javascript/ajax calls method that fetches childnodes.

heldt
  • 4,166
  • 7
  • 39
  • 67