Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.005 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'algorithm': 0.04; 'that?': 0.05; 'cache': 0.07; 'nested': 0.07; 'subset': 0.09; 'cc:addr :python-list': 0.11; '23,': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'looping': 0.16; 'nodes': 0.16; 'nodes.': 0.16; 'part-way': 0.16; 'rough': 0.16; 'wrote:': 0.18; 'written,': 0.19; 'cc:addr:python.org': 0.22; 'comparing': 0.24; 'cc:2**0': 0.24; 'references': 0.26; 'header:In-Reply-To:1': 0.27; 'point': 0.28; 'am,': 0.29; 'label': 0.30; 'message- id:@mail.gmail.com': 0.30; 'code': 0.31; 'another.': 0.31; 'node': 0.31; 'sep': 0.31; 'another': 0.32; 'maybe': 0.34; 'definition': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'doing': 0.36; 'checks': 0.38; 'issue': 0.38; 'how': 0.40; "you're": 0.61; 'taking': 0.65; 'manner': 0.72; 'other.': 0.75; 'checks.': 0.84; 'cuts': 0.84; 'to:none': 0.92 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 :content-type:content-transfer-encoding; bh=cucXOJ9M9oAFUKnece5m0C2TwW6pELc6HVObU6rHc0I=; b=usFCyfsPNhxzkTDO1QgbDRjFJe5duJP0PSUDSyCUzOCy+UDKqMBaNFLyr/KydY0huJ pocUqP/obYPeuPbdXF/U6jADRK3iJyeJ/1joQZHTbAb26CdBscQ9AkM8WDurMZJRbCAE fRN43Vpz6tKYTPTRSEV8O05/IyzYmgBh+Iiu2dfjwEtbfdmZz91cJxtGAVEsM5o+vwlw Z9/32dnHU/dWEqK9h/qnOeBaKcMtvtklC3dPnF8aM1fPKAgLHn1aBGPVEdEope79sw6N 69mDEng+ytD5HzkFrFB5WRO9W0rF1MBIV44v5OeekdH/fOw61zj/N4NUfExCxsaEuIPM mxYw== MIME-Version: 1.0 X-Received: by 10.42.231.9 with SMTP id jo9mr17797325icb.12.1411407916866; Mon, 22 Sep 2014 10:45:16 -0700 (PDT) In-Reply-To: <0be2cb54-4520-4379-a9bb-279cfe134d19@googlegroups.com> References: <521ef86a-df52-4a49-8562-6312273a8c07@googlegroups.com> <0be2cb54-4520-4379-a9bb-279cfe134d19@googlegroups.com> Date: Tue, 23 Sep 2014 03:45:16 +1000 Subject: Re: Comparison From: Chris Angelico Cc: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 20 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1411407926 news.xs4all.nl 2918 [2001:888:2000:d::a6]:56904 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:78170 On Tue, Sep 23, 2014 at 3:38 AM, LJ wrote: > At some point in my algorithm I am looping through some subset of nodes a= nd through the labels in each node and I perform some "joining" checks with= the labels of each node in another subset of nodes. To clarify I check for= a feasibility condition in a pairwise manner for every label in one node a= nd every label of another. This nested loop is taking time. > Okay, that's where the issue is - you're doing a cross-match, that's going to be comparing every label against every other. You might be able to cache some references to part-way into the tree, depending on how your code is written, but ultimately, you still need to do all of those checks. What's the definition of feasibility? Can you optimize that? Maybe there's a way to do a rough check that cuts down the number you have to do the exact check on. ChrisA