File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes efficient algorithm? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "efficient algorithm?" Watch "efficient algorithm?" New topic
Author

efficient algorithm?

Simon Xu
Ranch Hand

Joined: Aug 16, 2000
Posts: 235
hi,
I have two arrays contain a group of integer. I want to find if they have the same groups of number or not, although the order is different. Is there faster algorithm than nested for loops?
Thanks
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
1) first thing, compare length, if not equal, gone!
2) make copy of each, O(n )
3) sort both copy, O(n * lg n)
4) compare each pair O(n)
Over all O(n * lg n)
better than nested loop, which is O(n*n)
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
If the n = 13,000,000,000, you will see huge speed difference.
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
Use your calculator to do the comparison calculation, you will get a good understanding of computer algorithms.
Of course, if n = 130, the nested loop algorithm is simple and better. Since the time saving on computing does not worth the programming effort and the overhead of the complicated algorithms.
Thanks!
Roseanne
Join our SCJD Study Group at http://www.developergroup.org/
[This message has been edited by Roseanne Zhang (edited September 08, 2001).]
Simon Xu
Ranch Hand

Joined: Aug 16, 2000
Posts: 235
Roseanne
Thanks for your prompt response.
But how about not integer value, such as String, Char.
In fact, I have two arrays (or vector) which store two methods' parameters. I would like to compare if these two are the same, although the parameter order could be different.
Please reply,
Simon
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
Define a java.util.Comparator for the object you want to compare, then the algorithm would be the same.
If speed is your major concern, do not use Vector, use array instead, according to some research, Vector is at least 3 times slower than straight array for some obscure reason.
Roseanne
Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953
Here is an example of how to use Comarator:
http://www.geocities.com/developergrp/presentations/SortBy.htm
[This message has been edited by Roseanne Zhang (edited September 08, 2001).]
Simon Xu
Ranch Hand

Joined: Aug 16, 2000
Posts: 235

Thank you very much, Roseanne.
I will follow your link and try.
Simon
Peter den Haan
author
Ranch Hand

Joined: Apr 20, 2000
Posts: 3252
Originally posted by Roseanne Zhang:
If speed is your major concern, do not use Vector, use array instead, according to some research, Vector is at least 3 times slower than straight array for some obscure reason.

The reason is that the old-style Vector (and Hashtable) are completely synchronized and threadsafe. An ArrayList should be faster as it is not synchronized. Of course going to the bare metal of an array is faster still...
- Peter
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: efficient algorithm?
 
Similar Threads
need help for critical path analysis in java
Credit card validation algorithm
WA #1.....word association
Assignment Java-3 (Leap) Algorithm Logic
Unique 8-length chars algorithm