[Tutor] Efficiency and speed

[Stefan Behnel]

James Reynolds, 19.03.2010 17:41:
> I've still been working towards learning the language, albeit slowly and
> I've been working on a project that is somewhat intense on the numerical
> calculation end of things.
>
> Running 10,000 trials takes about 1.5 seconds and running 100,000 trials
> takes 11 seconds. Running a million trials takes about 81 seconds or so. I
> don't think 1M trials is needed for accuracy, but 100K probably is.
>
> I've made a few other optimizations today that I won't be able to test until
> I get home, but I was wondering if any of you could give some general
> pointers on how to make python run a little more quickly.
>
> There are two major pieces of code that seem slow, so I'll share the first
> with you. This section takes up about 1/3 of the time used when running all
> trials, where trials is 10K or larger.
>
> This section doesn't actually do any math, all it's doing is returning the
> "bin" that the randomly generated number falls in.
>
> The second section, the one that is taking up most of the time, does the
> math.
>
> The list nx1 is about 220 floating point numbers long.
>
>
>
>> sample = random.sample(range(int(self.nx1[b])), trials) # a list of sample
>> values based on nx1
>
> countlist = []
>
> self.nx1.append(0) #puts a zero on the end of nx1. This is for the case
>> where one of the random values lies past the minimum number (it scales from
>> 10M down to almost 0, but not exactly 0) Antyhing past this dates yields a
>> 0.
>
> for s in self.mcrange_gen(sample):
>
>           countlist.append(s-1) # This appends the bin number (the number
>> returned previously minus one) to make slices of the premium streams.
>
>
> and here is the generator section:
>
> def mcrange_gen(self, sample):#, lensample):
>
>      lensample = len(sample) # this section is just for speed. All of these
>> are renames from the globals to bring calc times down at the expense of
>> memory. I haven't tested these yet.
>
>      nx2 = self.nx1
>
>      nx2_append = nx2.append
>
>      nx2_sort = nx2.sort
>
>      nx2_reverse = nx2.reverse
>
>      nx2_index = nx2.index
>
>      nx2_remove = nx2.remove
>
>      for s in range(lensample):
>
>          q = sample[s] #takes the next randomly generated number from the
>> sample list
>
>          nx2_append(q) # and appends it to nx list.
>
>          nx2_sort() # and sorts it in place
>
>          nx2_reverse() # reverses the list, because this was the original
>> order
>
>          i = nx2_index(q) #get the index of that element
>
>          nx2_remove(q) # and remove the element.
>
>          yield i # send the position of that element back to the main
>> program.

This certainly falls into the bin of the most inefficient algorithms I've 
ever seen. Even walking through the samples one by one to find the target 
bin would be faster than the above.

Could you try to describe in a couple of words what this algorithm is 
supposed to do? That will almost certainly make it clear how you should 
write it instead.

Stefan