Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <oscar.j.benjamin@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.008
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'algorithm': 0.04; 'column': 0.07; 'grid': 0.09; 'subject:How': 0.10; 'cc:addr :python-list': 0.11; 'python': 0.11; 'dict': 0.16; 'dictionaries': 0.16; 'exists)': 0.16; 'iterating': 0.16; 'numpy': 0.16; 'subject:make': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'meant': 0.20; 'solution.': 0.20; 'cc:addr:python.org': 0.22; 'switched': 0.24; 'looks': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'tried': 0.27; 'array': 0.29; 'message-id:@mail.gmail.com': 0.30; 'easier': 0.31; 'keys': 0.31; 'lists': 0.32; 'stuff': 0.32; 'could': 0.34; 'but': 0.35; 'received:google.com': 0.35; 'version': 0.36; 'entry': 0.36; 'seconds': 0.37; 'implement': 0.38; 'even': 0.60; 'kind': 0.63; 'july': 0.63; 'improvement.': 0.68; 'subject:this': 0.83; 'occupied': 0.84; 'oscar': 0.84; '2013': 0.98
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=vuuXBSI9Vym34ctCsaChjxNaKY473cgxsKCHcgXuyio=; b=X/6phZN5wBp0H2EvreQvR8TB+aiZg2abCGxddLdIXxtfIX+J7hyRYqQI7xzzfNL0ue 81Wo3QCpK8ssGQr3Yx8TmIOn+sKnjsV+fgeg1K+LdYPytEM/kpx7t3ueWtFuuub7B4EO IjR4oE1VrK0x1Js3QDN6s7CP5h/M+ZbnV65krZ636/jIcw1xxCslczgZR3IPEA+H2rJx uv1oFOGmgT1DjY7EtIMHA9QRRDEC0BZe/09iOVes5rjCZzIbig/bbOVNB2MK/k+r7jxI no7Ys/UqBslvR9DnGkisZgfdCg6aTITaaDe2oiL7pgMR28t2/3syOz5s6/bjaNzurpce ozYg==
X-Received: by 10.220.191.5 with SMTP id dk5mr6786284vcb.47.1373031704661; Fri, 05 Jul 2013 06:41:44 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <b3nmtfFojnkU3@mid.dfncis.de>
References: <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Fri, 5 Jul 2013 14:41:23 +0100
Subject: Re: How to make this faster
To: Helmut Jarausch <jarausch@igpm.rwth-aachen.de>
Content-Type: text/plain; charset=ISO-8859-1
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://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: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.4296.1373031707.3114.python-list@python.org>
Lines: 26
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1373031707 news.xs4all.nl 15970 [2001:888:2000:d::a6]:48849
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:49983

On 5 July 2013 11:53, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
> I even tried to use dictionaries instead of Numpy arrays. This version is a bit
> slower then the lists of lists version (7.2 seconds instead of 6 second) but still
> much faster than the Numpy array solution.

When you switched to dictionaries did you take advantage of the
sparseness by iterating over dictionary keys instead of indices? This
is the kind of thing that I meant when I said that in Python it's
often easier to implement a better algorithm than in C. What I mean is
that if Grid is a dict so that Grid[(r, c)] is the entry at row r and
column c (if it exists) then you can change a loop like:

    for r in range(9):
        for c in range(9):
            if Grid[r, c] > 0: continue
            # do stuff

so that it looks like:

    for r, c in Grid:
        # do stuff

If the grid is sparsely occupied then this could be a significant improvement.


Oscar