search

sixty-north / segpy

A Python package for reading and writing SEG Y files.
Other
102 stars 54 forks source link

util.minmax() can be around 25% faster #8

Open abingham opened 10 years ago

abingham commented 10 years ago

Depending whether util.minmax() figures large in the runtime profile, it may be worth optimizing. The faster algorithm is to take two elements at a time from the input sequence. You first compare them to one another, then compare the smaller to the current minimum and the larger to the current maximum, updating the min/max as appropriate. This amortizes to 3 comparison per 2 input elements rather than the current 4 comparisons. However, it's a somewhat more complex algorithm, so it may not be worth the time.

rob-smallshire commented 10 years ago

I like that! Is that from TAOCP or somewhere?

abingham commented 10 years ago

I forget where I picked that up...the fruit of some CS course, probably.