Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Chris Angelico <rosuav@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: how to convert code that uses cmp to python3
Date: Sun, 10 Apr 2016 01:31:30 +1000
Lines: 24
Message-ID: <mailman.123.1460215898.2253.python-list@python.org>
References: <57064D0D.1030701@rece.vub.ac.be> <CAPTjJmrGiQS9uhFU-+TQ4nUWQ2p4gmJoQitMotS0Ob--qm1iWg@mail.gmail.com> <5706C961.2000009@rece.vub.ac.be> <CAPTjJmrbL870mV1kU8nHar=bPyKZRmhKP-8iUs_tpYVo5vhhOA@mail.gmail.com> <57075F43.7060004@rece.vub.ac.be> <85fuuw5ypl.fsf@benfinney.id.au> <5707B2CE.1010407@rece.vub.ac.be> <CAPTjJmrMv5O5vwrbfHJJCdiHi87naPOanhPmk4Ba_SLRgu1m4Q@mail.gmail.com> <5707BE18.1050805@rece.vub.ac.be> <CAPTjJmoMuqwg0Q_fp=qitC3wWkXYHtdqBNVGzO+3ToAmsgit8Q@mail.gmail.com> <5708C8B0.6050904@rece.vub.ac.be> <85twjb3su5.fsf@benfinney.id.au> <570910E2.3030400@rece.vub.ac.be> <CAPTjJmqeWACzrzka+5kQxO9Co42k7jRJzG_+cCqHkYO2OtQtMw@mail.gmail.com> <57091EA8.4080803@rece.vub.ac.be> <CAPTjJmrS=HW2fhDgZw22n5kcS4c+=b71rV50DkPPkKRdRW+QqA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
X-Trace: news.uni-berlin.de yRK/OKvh7MAdn3w7en6ubQ0vnNjRxAmCGplXTbxxR3GA==
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.010
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'received:209.85.223': 0.03; 'mentioned,': 0.07; 'so?': 0.07; 'subject:code': 0.07; 'cc:addr:python-list': 0.09; 'dict': 0.09; '2016': 0.16; 'ah,': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'lookups': 0.16; 'naive': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:python3': 0.16; 'wrote:': 0.16; 'tree': 0.18; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'do.': 0.22; 'keys': 0.22; 'am,': 0.23; 'header:In-Reply-To:1': 0.24; "doesn't": 0.26; 'chris': 0.26; 'message-id:@mail.gmail.com': 0.27; 'branches': 0.29; 'comparison': 0.29; 'subject:that': 0.29; 'probably': 0.31; "can't": 0.32; 'common': 0.33; 'values.': 0.33; 'case,': 0.34; 'structure': 0.34; 'received:google.com': 0.35; 'received:209.85': 0.36; '(and': 0.36; 'subject:: ': 0.37; 'received:209': 0.38; 'end': 0.39; 'data': 0.39; 'easily': 0.39; 'takes': 0.39; 'still': 0.40; 'your': 0.60; 'provide': 0.61; 'matter': 0.63; 'between': 0.65; 'account': 0.66; 'fact,': 0.67; 'angelico:': 0.84; 'answer,': 0.84; 'chrisa': 0.84; 'pardon': 0.84; 'schreef': 0.84; 'to:none': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc; bh=S5lT3kHVz/EmQcoD3VV5cdKoWUnAjk7wLOwEjVPo/Tc=; b=JfzryPN5u0ICQyAcKDgKhGsaWvkMaGQCxWfmQ3UpsTVk1ryTqapWjK/l7CkbiMbYdR w/cqEutWvnUDq+xXY4RZ6DB4S78dYRH/aO1Njec3AimW2BSFbACUTMaCALOC29/oGhub qRDGWBPuTsroGf20mulPF1bFVK44oKGpnTj8Cl5/jvp7idgFRh5OsyMwiWiVJ1CFUevB 0F++i4z5THUTI2jvgPxZZhQzdNgC+glUMzq2BfYqkWYFKB9ZFUacukPFnGwA7kx3QtA5 VXIraNomiAPdz2Q3MQfSG+Ei3DUAcMsOGHHIVntfh7sN097s5/CQny+yOFqD7JYF+DkL xieQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:cc; bh=S5lT3kHVz/EmQcoD3VV5cdKoWUnAjk7wLOwEjVPo/Tc=; b=bjEzkkGleoHtleT706BUCqo22bSjesiaBfz2tEYmw66jpYe8eV9WVmhEbC/hEMnv49 gLeQYxqON4CyJBACO5kVGCydled2LjWGTpF85e9rfYBHawr0ZI+P+uRM4cEffG4OJnSy fpR0qIp2bi9SnJhv3qCqzCfwgkTwvf4xdkuBIFgJPeodDtdR2u4Jhg5QRLYTZln0pm9k HRF51JhCTNzAXsZWpsAFUA/QYH+scJWD2Kc/iSUGQHoRK7/b/Yva6ZajTBimnR+vXxn7 +YbzjuB0LqI0SuCGO0frKHFT+zgSqBqpv/V2vE+9pbfcjQhCQlkEXVWJvIRRd6FqCimU OpDw==
X-Gm-Message-State: AD7BkJKYTwpqVWv20nxjIkqsxGCa6W0HBRFGk4qG5yLaIL7CLkeb4Cg4ROnyY1ZBSQJmeTthK/qIPSwBzxy8eQ==
X-Received: by 10.107.18.147 with SMTP id 19mr13894032ios.157.1460215890697; Sat, 09 Apr 2016 08:31:30 -0700 (PDT)
In-Reply-To: <57091EA8.4080803@rece.vub.ac.be>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.21
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <CAPTjJmrS=HW2fhDgZw22n5kcS4c+=b71rV50DkPPkKRdRW+QqA@mail.gmail.com>
X-Mailman-Original-References: <57064D0D.1030701@rece.vub.ac.be> <CAPTjJmrGiQS9uhFU-+TQ4nUWQ2p4gmJoQitMotS0Ob--qm1iWg@mail.gmail.com> <5706C961.2000009@rece.vub.ac.be> <CAPTjJmrbL870mV1kU8nHar=bPyKZRmhKP-8iUs_tpYVo5vhhOA@mail.gmail.com> <57075F43.7060004@rece.vub.ac.be> <85fuuw5ypl.fsf@benfinney.id.au> <5707B2CE.1010407@rece.vub.ac.be> <CAPTjJmrMv5O5vwrbfHJJCdiHi87naPOanhPmk4Ba_SLRgu1m4Q@mail.gmail.com> <5707BE18.1050805@rece.vub.ac.be> <CAPTjJmoMuqwg0Q_fp=qitC3wWkXYHtdqBNVGzO+3ToAmsgit8Q@mail.gmail.com> <5708C8B0.6050904@rece.vub.ac.be> <85twjb3su5.fsf@benfinney.id.au> <570910E2.3030400@rece.vub.ac.be> <CAPTjJmqeWACzrzka+5kQxO9Co42k7jRJzG_+cCqHkYO2OtQtMw@mail.gmail.com> <57091EA8.4080803@rece.vub.ac.be>
Xref: csiph.com comp.lang.python:106738

On Sun, Apr 10, 2016 at 1:24 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> Op 09-04-16 om 16:41 schreef Chris Angelico:
>
>>
>> In this case, you're likely to end up with large branches of your tree
>> that have the same prefix. (And if you don't, your iterations are all
>> going to end early anyway, so the comparison is cheap.) A data
>> structure that takes this into account will out-perform the naive
>> comparison model every time. In fact, a simple dict will probably
>> out-perform your tree;
>
> So? I need a structure that can easily give me an answer to the
> following: Given key1 and key2 what are the the keys between them
> with their corresponding values. As long as a dict can't provide
> me with that answer, it doesn't matter that it will out perform
> lookups in my trees.

Ah, okay. You can probably still take advantage of the other thing I
mentioned, which was structuring your tree such that it's aware of the
common prefixes, even if you can't go for O(1) hashing. That would
drastically reduce the number of comparisons you have to do.

ChrisA