• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

efficient algorithm?

 
Ranch Hand
Posts: 235
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If the n = 13,000,000,000, you will see huge speed difference.
 
Roseanne Zhang
Ranch Hand
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 235
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1953
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Thank you very much, Roseanne.
I will follow your link and try.
Simon
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic