Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #44122

Re: List Count

Path csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!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.062
X-Spam-Evidence '*H*': 0.89; '*S*': 0.01; 'seemed': 0.09; 'cc:addr :python-list': 0.11; 'missed': 0.12; 'benjamin': 0.16; 'bisect': 0.16; 'interval.': 0.16; 'wrote:': 0.18; 'looked': 0.18; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'message- id:@mail.gmail.com': 0.30; '(which': 0.31; 'but': 0.35; 'received:google.com': 0.35; 'subject:List': 0.36; 'wrong': 0.37; 'list': 0.37; 'depends': 0.38; 'within': 0.65; 'here': 0.66; 'obvious': 0.74; 'oscar': 0.84; '2013': 0.98
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=9B6/0E5PgeNN11kC07QEWM7tRtGeSjJTbYd7FNms6JQ=; b=nJj7zGXCHp1k0iyXrGLvdqAxgK0i+mRp29VRoE/IMYVGMo7Po3jbtvIMifnSHY0zrh wTSsOUZlgXShodX6BoNEexCqWvFaXcOTQYFka5HDQPLylQuCSGiKl/aaP+tQxgF6KlVA M/wjHlJ2DP8qzzaiWsF3yNivkEnUvBAq1BCd4H0yQo/F8EAY6RvXF477Qu0+zrafCEox 8b0e3AjiTCoWp+nT+gSVz/4gonPZSXzJZU32cQ5w6RgchroIoqRWqGoj7nNSapEMn9bm LwPBvgkGz10dGLiVTbUV2Ip5uIaLR3KB4KwQxCb8EiQmPC2cUbtsFdDgMB6k+E6SJh9+ TS1A==
X-Received by 10.52.73.42 with SMTP id i10mr1086439vdv.50.1366672025027; Mon, 22 Apr 2013 16:07:05 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <_umdnUiJWp9yN-jMnZ2dnUVZ7o-dnZ2d@brightview.co.uk>
References <sridnffI6YhxuOjMnZ2dnUVZ7tSdnZ2d@brightview.co.uk> <5175377f$0$29977$c3e8da3$5496439d@news.astraweb.com> <517545F7.5090209@nowhere.org> <mailman.927.1366644147.3114.python-list@python.org> <51755C38.4000204@nowhere.org> <mailman.929.1366646795.3114.python-list@python.org> <51756769.20206@nowhere.org> <mailman.936.1366661918.3114.python-list@python.org> <_umdnUiJWp9yN-jMnZ2dnUVZ7o-dnZ2d@brightview.co.uk>
From Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date Tue, 23 Apr 2013 00:06:44 +0100
Subject Re: List Count
To Blind Anagram <blindanagram@nowhere.org>
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.940.1366672027.3114.python-list@python.org> (permalink)
Lines 22
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1366672027 news.xs4all.nl 2296 [2001:888:2000:d::a6]:39109
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:44122

Show key headers only | View raw

On 22 April 2013 22:25, Blind Anagram <blindanagram@nowhere.org> wrote:
> On 22/04/2013 21:18, Oscar Benjamin wrote:
>> On 22 April 2013 17:38, Blind Anagram <blindanagram@nowhere.org> wrote:
>
> I also wondered whether I had missed any obvious way of avoiding the
> slicing cost (intellectually it seemed wrong to me to have to copy the
> list in order to count items within it).
 [snip]
>
> I have looked at solutions based on listing primes and here I have found
> that they are very much slower than my existing solution when the sieve
> is not large (which is the majority use case).

What matters is not so much the size of the sieve but the size of the
interval you want to query. You say that slicing cost is somehow
significant which suggests to me that it's not a small interval. An
approach using a sorted list of primes and bisect would have a cost
that is independent of the size of the interval (and depends only
logarithmically on the size of the sieve).


Oscar

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 12:58 +0100
  Re: List Count Dave Angel <davea@davea.name> - 2013-04-22 08:51 -0400
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 14:03 +0100
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 14:03 +0100
  Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 13:13 +0000
    Re: List Count Skip Montanaro <skip@pobox.com> - 2013-04-22 08:57 -0500
    Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 15:15 +0100
      Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 16:14 +0100
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 16:50 +0100
          Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 17:06 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 17:38 +0100
              Re: List Count Skip Montanaro <skip@pobox.com> - 2013-04-22 12:48 -0500
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 20:22 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 21:18 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 22:25 +0100
                Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 00:06 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 07:45 +0100
                Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 23:28 +0000
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:00 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-22 22:03 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 22:32 +0100
                Re: List Count Dave Angel <davea@davea.name> - 2013-04-22 21:47 -0400
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:02 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 17:38 +0100
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-22 16:50 +0100
      Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-22 23:01 +0000
        Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 08:05 +0100
          Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 12:08 +0100
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 12:45 +0100
              Re: List Count Terry Jan Reedy <tjreedy@udel.edu> - 2013-04-23 15:01 -0400
          Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-23 14:49 +0000
            Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 17:57 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 18:45 +0100
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 19:30 +0100
                Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 20:16 +0100
              Re: List Count Terry Jan Reedy <tjreedy@udel.edu> - 2013-04-23 16:00 -0400
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-23 21:41 +0100
              Re: List Count Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-04-23 21:38 +0100
              Re: List Count Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-24 01:59 +0000
                Re: List Count Blind Anagram <blindanagram@nowhere.org> - 2013-04-24 10:01 +0100
  Re: List Count Peter Otten <__peter__@web.de> - 2013-04-22 15:22 +0200
  Re: List Count 88888 Dihedral <dihedral88888@googlemail.com> - 2013-04-22 06:36 -0700

csiph-web