5

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.

Improve this question
6
  • maybe duplicat to stackoverflow.com/questions/1518103/… Commented Mar 14, 2012 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. Commented Mar 14, 2012 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? Commented Mar 14, 2012 at 12:40
  • 2
    List and Map are collections with different goals, I think this comparison is wrong. Commented Mar 14, 2012 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. Commented Mar 14, 2012 at 14:52

4 Answers 4

Reset to default
11

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

1 Comment

+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. ;)
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.

Improve this answer

Comments

-2

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.