[Tutor] Efficiency and speed

[Luke Paireepinart]

On Fri, Mar 19, 2010 at 3:17 PM, James Reynolds <eire1130 at gmail.com> wrote:

> Here's another idea I had. I thought this would be slower than then the
> previous algorithm because it has another for loop and another while loop. I
> read that the overhead of such loops is high, so I have been trying to avoid
> using them where possible.
>
>     def mcrange_gen(self, sample):
>         nx2 = self.nx1
>         for q in sample:
>             for a in nx2:
>                 while a > q:
>                      pass
>             yield a
>             break
>
> One thing to consider is whether you need to run this simulation online or
offline.
That is, whether you can reorder your sample space.

IFF you can reorder your sample space, then this algorithm can be extremely
simplified / sped up,
because then you can sort both the sample space and the binning list in
numerical order
Then you simply do a single pass through each list and only spend O(n+m)
time to categorize your entire sample space.
Sort of how a "merge" step of "merge sort" works, except rather than
emitting the sort order you would just be emitting
tuples with the sample value and its corresponding bin index.

If this doesn't make sense let me know.
If you are able to run the sim offline and reorder your sample space,
and I'm not just being dumb & misunderstanding what you're trying to do
(which is entirely possible),
try it this way.  If you have problems with my explanation, let me know and
I'll try to explain it better.

HTH,
-Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20100319/f5c96037/attachment.html>