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>
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

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