You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@struts.apache.org by Ashish Kulkarni <as...@gmail.com> on 2007/08/10 04:16:09 UTC
[OT] Question about performance with last array
Hi
I have a program which creates permutations for 10 letters, so the values i
get is 10 ^10 which is more then 3 million
Now i have to go through all 3 million records and do some calculations to
determine the best possible combination .
Any ideas what i should use, LinkedList, ArrayList, HashMap,
what would be the best way performance wise
should i use primitive or objects for calculations.
Any suggestions on approaching this problem.
Ashish
Re: [OT] Question about performance with last array
Posted by Dave Newton <ne...@yahoo.com>.
--- Ashish Kulkarni wrote:
> i have to find the shortest distance to travel, but
> this is not as simple as travel sales man problem
> because A-B is not as same as B-C
That *is* the traveling salesman problem.
There are many homework and algorithm sites that can
help you, and googling for various Java performance
search terms should give you much more information
than you'll want.
d.
____________________________________________________________________________________
Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us. http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@struts.apache.org
For additional commands, e-mail: user-help@struts.apache.org
Re: [OT] Question about performance with last array
Posted by Ashish Kulkarni <as...@gmail.com>.
Hi
This is what i have to do,
suppose have 3 points A-B-C then
i have to find the shortest distance to travel, but this is not as simple as
travel sales man problem because
A-B is not as same as B-C
So suppose i have
A-B is 2
A-C is 1
B-A is 3
B-C is 2
C-A is 4
C-B is 3
then i have find what is the best of A-B-C or A-C-B or some thing else,
any ideas?
On 8/10/07, Antonio Petrelli <an...@gmail.com> wrote:
>
> 2007/8/10, Ashish Kulkarni <as...@gmail.com>:
> > Hi
> > I have a program which creates permutations for 10 letters, so the
> values i
> > get is 10 ^10 which is more then 3 million
>
> Do you mean permutations (the same letters ordered in different ways)
> or dispositions with repetition (the 10-letter group can be taken from
> the 26 letters of the alphabet, can be repeated and can stay in any
> order)?
> Permutations: 10! possibilities
> Dispositions with repetition: 26^10
>
> > Now i have to go through all 3 million records and do some calculations
> to
> > determine the best possible combination .
> >
> > Any ideas what i should use, LinkedList, ArrayList, HashMap,
> > what would be the best way performance wise
> >
> > should i use primitive or objects for calculations.
> > Any suggestions on approaching this problem.
>
> IMHO it's better not to do it! :-) AFAICT, either way you are using
> permutations or dispositions with repetition, it is a O(e^n) problem,
> i.e. exponential complexity.
> I think that you need to change the problem, or solve it in another
> way, to go down to polynomial complexity.
> The answer, then, is that the complexity does not depend on the
> array-like structure you are using.
>
> Just my 0.02 euros.
> Antonio
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@struts.apache.org
> For additional commands, e-mail: user-help@struts.apache.org
>
>
Re: [OT] Question about performance with last array
Posted by Antonio Petrelli <an...@gmail.com>.
2007/8/10, Ashish Kulkarni <as...@gmail.com>:
> Hi
> I have a program which creates permutations for 10 letters, so the values i
> get is 10 ^10 which is more then 3 million
Do you mean permutations (the same letters ordered in different ways)
or dispositions with repetition (the 10-letter group can be taken from
the 26 letters of the alphabet, can be repeated and can stay in any
order)?
Permutations: 10! possibilities
Dispositions with repetition: 26^10
> Now i have to go through all 3 million records and do some calculations to
> determine the best possible combination .
>
> Any ideas what i should use, LinkedList, ArrayList, HashMap,
> what would be the best way performance wise
>
> should i use primitive or objects for calculations.
> Any suggestions on approaching this problem.
IMHO it's better not to do it! :-) AFAICT, either way you are using
permutations or dispositions with repetition, it is a O(e^n) problem,
i.e. exponential complexity.
I think that you need to change the problem, or solve it in another
way, to go down to polynomial complexity.
The answer, then, is that the complexity does not depend on the
array-like structure you are using.
Just my 0.02 euros.
Antonio
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@struts.apache.org
For additional commands, e-mail: user-help@struts.apache.org