Are min() and max() thread-safe?

Paul McGuire ptmcg at austin.rr.com
Thu Sep 17 11:01:05 CEST 2009


On Sep 16, 11:33 pm, Steven D'Aprano
<ste... at 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



More information about the Python-list mailing list