Home arrow static arrow Java Programming [Archive] - Will this method improve enumeration speed of all the elements in a Hashtab
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Will this method improve enumeration speed of all the elements in a Hashtab
This topic has 16 replies on 2 pages.    1 | 2 | Next »

Posts:536
Registered: 6/29/03
Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 6:37 AM



 
Hello everyone:

I have learned that a trick can be used to enumerate all the elements in a Hashtable, which is said to be more efficient. I just want to know whether it is true (more efficient) and if so, why this method is more efficient. The method is illustrated below.

Sample Code

//prepare work begin
Hashtable table = new Hashtable();
TreeSet set = new TreeSet();
//for each item in "table", put its key value in "set"
//prepare work end

//enumeration method
Iterator i = set.iterator();
while (i.hasNext()) {
String key = (String) i.next();
AuthEntry entry = (AuthEntry) table.get(key);
//do operations with "entry"
}

Thanks in advance,
George

 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 7:04 AM (reply 1 of 16)



 
Hi,

I don't see why it would be faster than iterating over the iterator given by table.values().iterator().
The code you sent still calls a get() for each key.

/Kaj
 

Posts:24,036
Registered: 2/3/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 7:21 AM (reply 2 of 16)



 
I have learned that a trick can be used to enumerate
all the elements in a Hashtable, which is said to be
more efficient. I just want to know whether it is true
(more efficient) and if so, why this method is more
efficient.

Have you tested it (I'm guessing not, since you're asking the question)? If not, and you're curious, why not?
 

Posts:24,036
Registered: 2/3/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 7:23 AM (reply 3 of 16)



 
P.S. Don't bother "optimizing" this until you know it's an issue. You stand a good chance of slowing your application down (e.g., copying all keys into a TreeSet, etc.).
 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 7:41 AM (reply 4 of 16)



 
yawmark, he isn't copying them into the TreeSet. He adds the key to the set when he adds the entry to the hashtable.

/Kaj
 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:00 AM (reply 5 of 16)



 
Yes, yawmark buddy, I have never tested it. I am just wondering its performance. Any suggestions?
 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:04 AM (reply 6 of 16)



 
Thanks, kajbj buddy!

Your reply puzzles me a bit, what means "The code you sent still calls a get() for each key." in your reply? Can you provide more detailed explanations?

Best regards,
George

 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:05 AM (reply 7 of 16)



 
Yes, you are correct, kajbj buddy! The program runs in this way.

Geroge
 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:07 AM (reply 8 of 16)



 
Will indexing by TreeSet faster than "table.values().iterator()", yawmark buddy?

George

 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:18 AM (reply 9 of 16)



 
Hi,

In your post you had the code:

while (i.hasNext()) {    String key = (String) i.next();    AuthEntry entry = (AuthEntry) table.get(key);    //do operations with "entry"}


There you can see that you are iterating over all keys (that you have in the TreeSet). And for each key you call table.get(key). That is what might cost. The hashtable have to get the hashvalue for the key, look it up in the table, and then return the value.

That is why I think this will run faster:
Iterator i = table.values().iterator();while (i.hasNext()) {    AuthEntry entry = (AuthEntry)i.next();    //do operations with "entry"}


/Kaj
 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:20 AM (reply 10 of 16)



 
Hi, there is no such thing as indexing the TreeSet, and you would still have to call get on the table.

/Kaj
 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:33 AM (reply 11 of 16)



 
Thanks for your kindly reply, kajbj buddy!

I have got your idea. Your method will enumerate the values directly and my method will enumerate values by keys, while the keys are stored in another container, TreeSet. Am I correct?

IMHO, I think to identify which way is better has two solutions. One is prove through theory, for example, Java specifications and implementations and another one is through experiments. How do you think of it? And any suggestions dealing with how to identify which way is faster?

Have a nice weekend,
George

 

Posts:536
Registered: 6/29/03
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:34 AM (reply 12 of 16)



 
Yes, I agree. I mean index values by keys stored in a TreeSet, kajbj buddy!

George

 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:42 AM (reply 13 of 16)



 
Hi,

I usually think about it first. Which one of two methods should have the lower overheads? In this case you have two options. Access the values using the keys, or accessing the values directly. Logically it would be faster to access the keys directly. Usually you have to have a basic understanding of how things are implemented as well (i.e. how is a hashtable/hashmap implemented). After you have come up with a solution that you think is good, just make a test, and time it.

long beginTime = System.currentTimeMillis();
//perform your tests
long endTime = System.currentTimeMillis();
System.out.println("It took " + (endTime - beginTime) + " ms to complete the test");

Then you have to run your tests a couple of times, since the test results can vary. Take the mean execution time as the result.

If it is in a larger system, or you want to know more of what is going on, run it in a profiler.

/Kaj
 

Posts:18,384
Registered: 21.03.00
Re: Will this method improve enumeration speed of all the elements in a Hashtab  
Jul 17, 2004 8:43 AM (reply 14 of 16)



 
Hmmm the absolut fastest way would be to have the values backed up in a list, and then iterate over it (instead of backing up the keys in a set).

/Kaj
 
This topic has 16 replies on 2 pages.    1 | 2 | Next »