efficient algorithm?

[Simon Xu]

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]

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]

If the n = 13,000,000,000, you will see huge speed difference.

[Roseanne Zhang]

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]

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]

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]

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]

Thank you very much, Roseanne.
I will follow your link and try.
Simon

[Peter den Haan]

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