Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# efficient algorithm?

Simon Xu
Ranch Hand
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
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
Posts: 1953
If the n = 13,000,000,000, you will see huge speed difference.

Roseanne Zhang
Ranch Hand
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
[This message has been edited by Roseanne Zhang (edited September 08, 2001).]

Simon Xu
Ranch Hand
Posts: 235
Roseanne
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.
Simon

Roseanne Zhang
Ranch Hand
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
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
Posts: 235

Thank you very much, Roseanne.
Simon

Peter den Haan
author
Ranch Hand
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