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

Groups > comp.lang.python > #102527

Re: _siftup and _siftdown implementation

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From srinivas devaki <mr.eightnoteight@gmail.com>
Newsgroups comp.lang.python
Subject Re: _siftup and _siftdown implementation
Date Fri, 5 Feb 2016 21:15:33 +0530
Lines 24
Message-ID <mailman.12.1454687182.19407.python-list@python.org> (permalink)
References <mailman.72.1454619005.30993.python-list@python.org> <56b3e902$0$1613$c3e8da3$5496439d@news.astraweb.com> <CACs7g=C-MEHLWYZWJPiiJfxoFHE3y3UcEL2Q7kE=HLNbGQkV+g@mail.gmail.com> <56B4B4D5.20804@mail.de>
Mime-Version 1.0
Content-Type text/plain; charset=UTF-8
X-Trace news.uni-berlin.de X1keg/zFroO6ME8RL+DJ1w0RdCyJKO23D1azjrv2V+tQ==
Return-Path <mr.eightnoteight@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.002
X-Spam-Evidence '*H*': 1.00; '*S*': 0.00; 'received:209.85.223': 0.03; 'root': 0.04; 'cc:addr:python-list': 0.09; 'inserted': 0.09; 'logic': 0.09; 'oh,': 0.09; 'variance': 0.09; '+91': 0.15; '2016': 0.16; 'heapq': 0.16; 'popping': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'sound,': 0.16; 'wrote:': 0.16; 'obviously': 0.16; 'element': 0.18; 'merge': 0.18; 'student': 0.20; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'junior': 0.22; 'subject:skip:i 10': 0.22; 'feb': 0.23; 'elements': 0.23; 'header :In-Reply-To:1': 0.24; 'module': 0.25; 'fri,': 0.27; 'message- id:@mail.gmail.com': 0.27; 'operations,': 0.27; 'small,': 0.27; 'request,': 0.29; 'operations': 0.31; 'says': 0.32; 'gets': 0.35; 'received:google.com': 0.35; 'could': 0.35; "isn't": 0.35; 'but': 0.36; 'received:209.85': 0.36; 'indian': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'doing': 0.38; "won't": 0.38; 'received:209': 0.38; 'sure': 0.39; 'some': 0.40; 'school': 0.62; 'back': 0.62; 'here.': 0.62; 'more': 0.63; 'different': 0.63; 'our': 0.64; '(3rd': 0.84; 'ph:': 0.84
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=1450bSdNQlHWdDTlbEYg7CsSndAFyAVzy+SyRR58lqA=; b=0rU9pumdu3XMaD36d9Aa2tRex+iuBtxOtDm2ZPw0CsERQye2wxG6visf71LNXjf28u eNAcyCE54jPPSiGhbKuOyGRr1TfBEgLfynmb89AmdKI01lIu1zPA2cCtB5vebKQv4Kgl 1jU6sWe9hu0OMB4KVeEzifGvu/Rooe4v+JwQq9RIkitPFQ6ACcaHkeUXFAEZkayvwoHq ccurHAtybm4x7Dc3M9JuAhWxo0KzhuEgEAFGoyd3ZqA4A+7095G4bLsBtFndOctVjf2L 5Ebt8c4a44U0eP9njcK87o4+OENz4ILXJxcxQaGTe02651hOdUUqDCU6l/DiZuGLPUDo VOOA==
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:from:date :message-id:subject:to:cc:content-type; bh=1450bSdNQlHWdDTlbEYg7CsSndAFyAVzy+SyRR58lqA=; b=hovSY5p9eaZFThI2IN3k6lEYeRyLVvXs4vaMm8/jR7FjUhe9RMj8rLQYyOPXTlyLh9 kVy1BUXHh/CjCN8IQIsxcmsVzIzS1FTXGY4sxuCUsRMmd3Y4EnSk5ccx5moS2FBkaYlQ xhWnCQ0rX2E+K3x57g2UKdsmnrqUIA7zay7k1RIhw5clJx+xVKGOMKDo8KaWxyXTj8Jo mgvoiUa+T5LTkLF4gu2Jer/TX0UjM1MpyP+MsjbxR7MxxvI8c9mbVkKQaOW/jPkIjmja yPCtNmuJruRBpXtI0aT4NPqmYurHVzzzy7YYXtgwZDzphtZ8trVrxBNfjxkysknidGO3 W+uQ==
X-Gm-Message-State AG10YORont+CQdItlkng9PZ6T3FAj+xt+6RYgpNbISzKJkf1lVrzSwx6zM1UDuT0UmWxphPAlec+sMJzoiXSXg==
X-Received by 10.107.135.30 with SMTP id j30mr18063648iod.103.1454687173314; Fri, 05 Feb 2016 07:46:13 -0800 (PST)
In-Reply-To <56B4B4D5.20804@mail.de>
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.21rc2
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>
Xref csiph.com comp.lang.python:102527

Show key headers only | View raw

On Fri, Feb 5, 2016 at 8:12 PM, Sven R. Kunze <srkunze@mail.de> wrote:
> On 05.02.2016 02:26, srinivas devaki wrote:
> What do you think about our use-case?
>
Oh, the logic is sound, every element that we have inserted has to be popped,
We are spending some *extra* time in rearranging the elements only to be
sure that we won't be spending more than this *extra* time when doing other
operations, and our use-case isn't much different either, If by rearranging the
elements in the heap(*subheap*) gets optimal for other operations like
popping the
root element(heap[0]) then obviously it is optimal for popping other elements
(children of heap[0]).


PS: @sven But don't yet merge the pull request, I could be wrong.
as the heapq module already says that the variance is very small,
let me write some tests(on more than 10**3 elements) and then get back here.
-- 
Regards
Srinivas Devaki
Junior (3rd yr) student at Indian School of Mines,(IIT Dhanbad)
Computer Science and Engineering Department
ph: +91 9491 383 249
telegram_id: @eightnoteight

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

Thread

_siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 02:20 +0530
  Re: _siftup and _siftdown implementation Steven D'Aprano <steve@pearwood.info> - 2016-02-05 11:12 +1100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 01:21 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 06:56 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:42 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:48 -0200
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:55 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:59 -0200
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 21:15 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:27 +0100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:35 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 23:12 +0530
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-06 20:16 +0530

csiph-web