On Sep 16, 11:33 pm, Steven D'Aprano
<ste...@remove.this.cybersource.com.au> wrote:
> I have two threads, one running min() and the other running max() over
> the same list. I'm getting some mysterious results which I'm having
> trouble debugging. Are min() and max() thread-safe, or am I doing
> something fundamentally silly by having them walk over the same list
> simultaneously?
>
If you are calculating both min and max of a sequence, here is an
algorithm that can cut your comparisons by 25% - for objects with rich/
time-consuming comparisons, that can really add up.
import sys
if sys.version[0] == 2:
range = xrange
def minmax(seq):
if not seq:
return None, None
min_ = seq[0]
max_ = seq[0]
seqlen = len(seq)
start = seqlen % 2
for i in range(start,seqlen,2):
a,b = seq[i],seq[i+1]
if a > b:
a,b = b,a
if a < min_:
min_ = a
if b > max_:
max_ = b
return min_,max_
With this test code, I verified that the comparison count drops from
2*len to 1.5*len:
if __name__ == "__main__":
import sys
if sys.version[0] == 2:
range = xrange
import random
def minmax_bf(seq):
# brute force, just call min and max on sequence
return min(seq),max(seq)
testseq = [random.random() for i in range(1000000)]
print minmax_bf(testseq)
print minmax(testseq)
class ComparisonCounter(object):
tally = 0
def __init__(self,obj):
self.obj = obj
def __cmp__(self,other):
ComparisonCounter.tally += 1
return cmp(self.obj,other.obj)
def __getattr__(self,attr):
return getattr(self.obj, attr)
def __str__(self):
return str(self.obj)
def __repr__(self):
return repr(self.obj)
testseq = [ComparisonCounter(random.random()) for i in range
(10001)]
print minmax_bf(testseq)
print ComparisonCounter.tally
ComparisonCounter.tally = 0
print minmax(testseq)
print ComparisonCounter.tally
Plus, now that you are finding both min and max in a single pass
through the sequence, you can wrap this in a lock to make sure of the
atomicity of your results.
(Just for grins, I also tried sorting the list and returning elements
0 and -1 for min and max - I got numbers of comparisons in the range
of 12X to 15X the length of the sequence.)
-- Paul
--
http://mail.python.org/mailman/listinfo/python-list
