Why is my Time algorithm so slow - Can anyone tell me why?

[Dave Milne]

FWIW, I did, it didn't.

Hi Jon,

If you read my previous email it will shed some light on the matter at

hand.

 

[Roy Gourgi]

That may well be the intention, but it's not what actually happens, as

far as I can tell. If you make the program dump out any times when it's
checking {2,3,4} just with the lp1/lp2/lp3, lp2/lp3/lp4 combinations,
you'll see it does it several times.

Yes but not in any particular row. For example if you have the 6 numbers
2,3,4,5,6,7 then it only checks the 2,3,4 one time. I told you this is a
watered down version of my program.

So, one more time: what is this actually trying to do? Without
understanding the code in depth (which is tricky, due to the way it's
written) it's very hard to do anything other the kind of refactoring
which Markus performed.

It is tryiing to see if all the any one of the 3 number point are contained
in all the possible combinations ranging from 1 to 49.

Hope this helps
Roy

Believe it or not, in most combinatorial problems there is some
*unavoidable
redundancy* as most combinatorial covering designs are not perfect (i.e.
they contain some unavoidable redundancy). There are instances of perfect
combinatorial designs such as this design C(22,6,3)=77 and when they are
perfect they are call t-designs. But most designs do not fall under this
perfect category and they are thus much harder to find than their
counterparts.

If you are interested I can shed some more light, but it gets more
complex.

Let's see how much progress we make elsewhere first... I can't remember
much of the combinatorics I did from university, unfortunately. (I
can't even remember how much we did.)

No, I am not counting the instances of a particular combination such as
2,3,4 because if you look at the code carefully, any combination is never
checked more than once in any of the 6 columns in the gaSeconds. That is
why
as I mentioned in my other posts, the way the search is conducted is of
the
essence. If 3 points such as 2,3,4 appear in any one of 6 numbers, it
would
be better if they appear in the first 3 of the 6 because that would speed
up
the search. Do you follow?

That may well be the intention, but it's not what actually happens, as
far as I can tell. If you make the program dump out any times when it's
checking {2,3,4} just with the lp1/lp2/lp3, lp2/lp3/lp4 combinations,
you'll see it does it several times.

However, it looks like the code doesn't actually do what I thought it
did - a brute force search for all x/y/z such that 0 < x < y < z < 50
and gaSumWorkDays[gaSeconds[x,1]+gaSeconds[y,2]+gaSeconds[z,3]]<=0
finds plenty.

So, one more time: what is this actually trying to do? Without
understanding the code in depth (which is tricky, due to the way it's
written) it's very hard to do anything other the kind of refactoring
which Markus performed.

First of all, I don't think that C++ supports jagged arrays (correct me
if I
am wrong).

I wouldn't like to say for sure, to be honest. I'm not sure what you
*do* get in C++ - it's been a while. I *suspect* that C++ doesn't
actually support *rectangular* arrays directly - you have to create a
one-dimensional array with a size of the product of the individual rank
lengths.

Furthermore, as I reiterated a few times, my knowledge in
programming is not as extensive as yours and I thought jagged arrays are
to
be used only when the arrays are not rectangular and in my case they
always
are.

No - rectangular arrays are definitely more memory efficient, but
slower in .NET.

I was not aware that jagged arrays would speed up the search process
(one of the new things that I learnt).

But when I told you that originally, you said that you *couldn't* use
jagged arrays. Is that actually the case (and in which case, why?) or
not?

In my original program I use 3 one
dimensional arrays (i.e. gaSeconds1,gaSeconds2,gaSeconds3) which I guess
is
analogous to a jagged array.

Yes, pretty much.

I think it may even be faster than a jagged
array as you are only accessing a one dimension array at a time (correct
me
if I am wrong) but I was too lazy to try to see which one is faster.
Also,
to me it seems more natural and intuitive to have several one dimensional
arrays, but this might just be a matter of preference. BTW do you know
which
would be faster a jagged array, or multiple one dimensional arrays?

I don't know which would be faster, to be honest - you'd need to
benchmark it. Of course, doing that is *much* easier if you refactor
the test bit into a separate method, which is almost certain to be
inlined anyway. Just an example of why it's important to code in a
maintainable way rather than assuming that anything which is
understandable won't perform.

 

[Roy Gourgi]

Very good, you hit the nail right on the button. Impressive. Now was that
not FUN!!!
Well believe it or not, combinatorics is used in many applications, even for
debugging software. So yes indirectly there could be a connection. Covering
designs are templates and they could be used in any application.

Roy

So, one more time: what is this actually trying to do? Without
understanding the code in depth (which is tricky, due to the way it's
written) it's very hard to do anything other the kind of refactoring
which Markus performed.

<snip>

OK,
I got tired of trying to extract deeply held secrets from Roy, so I did
some digging.
It turns out that Roy loves the lottery (or at least the a mathematics
surrounding it)

The 163 rows of data in the TimeSchedule Array were 163 lottery tickets.
This particular lottery has 49 numbers and you choose 6 of them.

The idea of the game is to find the minimum number of lottery tickets that
you would need to buy in order to ensure that you were guaranteed to
always match a minimum of 3 numbers on at least 1 ticket. Of course the
same logic could be applied for 4 or 5 number matches, or other lotteries,
or other variations.

So the short description of his watered down program would be as follows.
Given a set of N lottery tickets (163) in this case, with certain
numbers on each ticket (TimeSchedule Array)
Verify that we have a covering() - for any valid lottery number(the 6
loops) verify that at least 1 of our tickets matches 3 of the numbers.

That's it!!
No state secrets!!
No concept to vast for our tiny minds!!!

Now most likely his REAL program has algorithms for attempting to generate
minimal coverings for certain problems.
He then needs to verify that his solution is a covering (minimal is much
tougher)

Apparently Roy wanted us off the scent given the names he chose for is
variables.
TimeSchedule ---> LotteryTickets
kNoWeeks=49; ---> How many numbers in the lottery
kNoDays=163; ---> How many tickets
kNoSeconds=18424; ---> 49 choose 3 = (49*48*47)/(3*2*1)
gaWorkDays= new int [7]; ---> Numbers on a given ticket

I would be curious to hear from Roy if there is ANY connection to the
variable names.

For more info look here:
http://pages.infinit.net/royng/index.htm

or Google for - combinatorial covering designs

Bill

 

[Jon Skeet [C# MVP]]

Believe it or not, in most combinatorial problems there is some *unavoidable
redundancy* as most combinatorial covering designs are not perfect (i.e.
they contain some unavoidable redundancy). There are instances of perfect
combinatorial designs such as this design C(22,6,3)=77 and when they are
perfect they are call t-designs. But most designs do not fall under this
perfect category and they are thus much harder to find than their
counterparts.

If you are interested I can shed some more light, but it gets more complex.

Let's see how much progress we make elsewhere first... I can't remember
much of the combinatorics I did from university, unfortunately. (I
can't even remember how much we did.)

No, I am not counting the instances of a particular combination such as
2,3,4 because if you look at the code carefully, any combination is never
checked more than once in any of the 6 columns in the gaSeconds. That is why
as I mentioned in my other posts, the way the search is conducted is of the
essence. If 3 points such as 2,3,4 appear in any one of 6 numbers, it would
be better if they appear in the first 3 of the 6 because that would speed up
the search. Do you follow?

That may well be the intention, but it's not what actually happens, as
far as I can tell. If you make the program dump out any times when it's
checking {2,3,4} just with the lp1/lp2/lp3, lp2/lp3/lp4 combinations,
you'll see it does it several times.

However, it looks like the code doesn't actually do what I thought it
did - a brute force search for all x/y/z such that 0 < x < y < z < 50
and gaSumWorkDays[gaSeconds[x,1]+gaSeconds[y,2]+gaSeconds[z,3]]<=0
finds plenty.

So, one more time: what is this actually trying to do? Without
understanding the code in depth (which is tricky, due to the way it's
written) it's very hard to do anything other the kind of refactoring
which Markus performed.

First of all, I don't think that C++ supports jagged arrays (correct me if I
am wrong).

I wouldn't like to say for sure, to be honest. I'm not sure what you
*do* get in C++ - it's been a while. I *suspect* that C++ doesn't
actually support *rectangular* arrays directly - you have to create a
one-dimensional array with a size of the product of the individual rank
lengths.

Furthermore, as I reiterated a few times, my knowledge in
programming is not as extensive as yours and I thought jagged arrays are to
be used only when the arrays are not rectangular and in my case they always
are.

No - rectangular arrays are definitely more memory efficient, but
slower in .NET.

I was not aware that jagged arrays would speed up the search process
(one of the new things that I learnt).

But when I told you that originally, you said that you *couldn't* use
jagged arrays. Is that actually the case (and in which case, why?) or
not?

In my original program I use 3 one
dimensional arrays (i.e. gaSeconds1,gaSeconds2,gaSeconds3) which I guess is
analogous to a jagged array.

Yes, pretty much.

I think it may even be faster than a jagged
array as you are only accessing a one dimension array at a time (correct me
if I am wrong) but I was too lazy to try to see which one is faster. Also,
to me it seems more natural and intuitive to have several one dimensional
arrays, but this might just be a matter of preference. BTW do you know which
would be faster a jagged array, or multiple one dimensional arrays?

I don't know which would be faster, to be honest - you'd need to
benchmark it. Of course, doing that is *much* easier if you refactor
the test bit into a separate method, which is almost certain to be
inlined anyway. Just an example of why it's important to code in a
maintainable way rather than assuming that anything which is
understandable won't perform.

 

[Jon Skeet [C# MVP]]

Yes but not in any particular row. For example if you have the 6 numbers
2,3,4,5,6,7 then it only checks the 2,3,4 one time. I told you this is a
watered down version of my program.

Yes, which is part of the problem - you've never actually told us what
it's meant to do.

It is tryiing to see if all the any one of the 3 number point are contained
in all the possible combinations ranging from 1 to 49.

Please try explaining that in more straightforward terms. As far as I
can tell, it attempts to find whether it can find any *6* numbers where
the condition (the sum etc) is true for *all* combinations of 3 numbers
within those 6.

If you only look for 3 at a time, there are plenty of examples for
which the condition holds - but there are no 6 numbers where it holds
for all combinations of three of those numbers.

I can't help but feel there must be a more efficient way of looking -
for instance, if you find that the condition doesn't hold for
(30,31,32) when those are the later three numbers, then there's no
point in looking through them at all for *any* earlier set of numbers -
the sort of optimisation you've got for skipping past early
combinations. I'll have to have a think about how to use that - but I
can only do so if you can confirm that the program is trying to do what
I think it is.

In the meantime, I'll attempt to convert it into a more readable form
which lends itself to optimisation.

 

[Bill Butler]

So, one more time: what is this actually trying to do? Without
understanding the code in depth (which is tricky, due to the way it's
written) it's very hard to do anything other the kind of refactoring
which Markus performed.

<snip>

OK,
I got tired of trying to extract deeply held secrets from Roy, so I did some digging.
It turns out that Roy loves the lottery (or at least the a mathematics surrounding it)

The 163 rows of data in the TimeSchedule Array were 163 lottery tickets.
This particular lottery has 49 numbers and you choose 6 of them.

The idea of the game is to find the minimum number of lottery tickets that you would need to buy in
order to ensure that you were guaranteed to always match a minimum of 3 numbers on at least 1
ticket. Of course the same logic could be applied for 4 or 5 number matches, or other lotteries, or
other variations.

So the short description of his watered down program would be as follows.
Given a set of N lottery tickets (163) in this case, with certain numbers on each ticket
(TimeSchedule Array)
Verify that we have a covering() - for any valid lottery number(the 6 loops) verify that at
least 1 of our tickets matches 3 of the numbers.

That's it!!
No state secrets!!
No concept to vast for our tiny minds!!!

Now most likely his REAL program has algorithms for attempting to generate minimal coverings for
certain problems.
He then needs to verify that his solution is a covering (minimal is much tougher)

Apparently Roy wanted us off the scent given the names he chose for is variables.
TimeSchedule ---> LotteryTickets
kNoWeeks=49; ---> How many numbers in the lottery
kNoDays=163; ---> How many tickets
kNoSeconds=18424; ---> 49 choose 3 = (49*48*47)/(3*2*1)
gaWorkDays= new int [7]; ---> Numbers on a given ticket

I would be curious to hear from Roy if there is ANY connection to the variable names.

For more info look here:
http://pages.infinit.net/royng/index.htm

or Google for - combinatorial covering designs

Bill

 

[Jon Skeet [C# MVP]]

Apparently Roy wanted us off the scent given the names he chose for is variables.
TimeSchedule ---> LotteryTickets
kNoWeeks=49; ---> How many numbers in the lottery
kNoDays=163; ---> How many tickets
kNoSeconds=18424; ---> 49 choose 3 = (49*48*47)/(3*2*1)
gaWorkDays= new int [7]; ---> Numbers on a given ticket

I would be curious to hear from Roy if there is ANY connection to the variable names.

Thanks for doing the research, Bill. I suspect this will be my last
post to this thread, as I'm not much of a fan of helping people who
effectively lie about what their code is for in the first place.

If Roy had been honest in the first place, I'd have been much more
interested in helping...

 

[Roy Gourgi]

Hi,

I did not lie. All I asked for was for some help which I did receive from
Markus. He did not ask any questions and he solved my problem. What is the
big deal?

Thanks anyways

Roy

Apparently Roy wanted us off the scent given the names he chose for is
variables.
TimeSchedule ---> LotteryTickets
kNoWeeks=49; ---> How many numbers in the
lottery
kNoDays=163; ---> How many tickets
kNoSeconds=18424; ---> 49 choose 3 = (49*48*47)/(3*2*1)
gaWorkDays= new int [7]; ---> Numbers on a given ticket

I would be curious to hear from Roy if there is ANY connection to the
variable names.

Thanks for doing the research, Bill. I suspect this will be my last
post to this thread, as I'm not much of a fan of helping people who
effectively lie about what their code is for in the first place.

If Roy had been honest in the first place, I'd have been much more
interested in helping...

 

[Jon Skeet [C# MVP]]

I did not lie. All I asked for was for some help which I did receive from
Markus. He did not ask any questions and he solved my problem. What is the
big deal?

"I have the same time scheduling program written in C++ and
it is 5 times faster than my version in C#."

This is now clearly *not* a time scheduling program, but you changed
your variable names etc to pretend it was.

You've been secretive and dishonest. I suspect I'm not the only one who
dislikes being treated this way.

(By the way, others helped you as well - you just chose to ignore their
help, like my very first post which suggested using jagged arrays...)