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

Groups > comp.lang.python > #101402 > unrolled thread

Re: How to remove item from heap efficiently?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: How to remove item from heap efficiently? "Sven R. Kunze" <srkunze@mail.de> - 2016-01-08 17:45 +0100
    Re: How to remove item from heap efficiently? Paul Rubin <no.email@nospam.invalid> - 2016-01-09 10:32 -0800
      Re: How to remove item from heap efficiently? "Sven R. Kunze" <srkunze@mail.de> - 2016-01-10 19:50 +0100
      Re: How to remove item from heap efficiently? srinivas devaki <mr.eightnoteight@gmail.com> - 2016-01-12 08:38 +0530
        Re: How to remove item from heap efficiently? Paul Rubin <no.email@nospam.invalid> - 2016-01-11 19:16 -0800

#101402 — Re: How to remove item from heap efficiently?

Thanks for your suggestion.

On 08.01.2016 14:21, srinivas devaki wrote:
> You can create a single heap with primary key as timestamp and
> secondary key as priority, i.e by creating a tuple
> insert the elements into the heap as
> (timestamp, priority)
I think I cannot use that because I need the list sorted by both criteria.
> If there is any underlying meaning for creating 2 heaps. please mention.

I use two heaps because I need to insert arbitrary items fast and remove 
the ones fast which are too old (timestamp) or are next in order (priority).

Basically a task scheduler where tasks can be thrown away once they are 
too long in the queue.

> On Fri, Jan 8, 2016 at 4:22 AM, Sven R. Kunze <srkunze@mail.de> wrote:
>> Hi everybody,
>>
>> suppose, I need items sorted by two criteria (say timestamp and priority).
>> For that purpose, I use two heaps (heapq module):
>>
>> heapA # items sorted by timestamp
>> heapB # items sorted by priority
>>
>> Now my actual problem. When popping an item of heapA (that's the oldest
>> item), I need to remove the very same item from heapB, regardlessly where it
>> is in heapB. And vice versa.
>>
>> Is there a datastructure or a simple trick to achieve that in an efficient
>> matter?
>>
>> Best,
>> Sven
>> --
>> https://mail.python.org/mailman/listinfo/python-list

[toc] | [next] | [standalone]

#101411

"Sven R. Kunze" <srkunze@mail.de> writes:
> Basically a task scheduler where tasks can be thrown away once they
> are too long in the queue.

I don't think there's a real nice way to do this with heapq.  The
computer-sciencey way would involve separate balanced tree structures
for the two sorting keys (think of a database table with indexes on two
different columns).

You could look up "timing wheels" for a simpler practical approach that
the Linux kernel scheduler used to use (I think it changed a few years
ago).

[toc] | [prev] | [next] | [standalone]

#101446

On 09.01.2016 19:32, Paul Rubin wrote:
> "Sven R. Kunze" <srkunze@mail.de> writes:
>> Basically a task scheduler where tasks can be thrown away once they
>> are too long in the queue.
> I don't think there's a real nice way to do this with heapq.  The
> computer-sciencey way would involve separate balanced tree structures
> for the two sorting keys (think of a database table with indexes on two
> different columns).

Others suggested using an additional dict where to store the indexes of 
the items. Then, when removing an item, I just need to query the dict.

Best,
Sven

[toc] | [prev] | [next] | [standalone]

#101513

On Jan 10, 2016 12:05 AM, "Paul Rubin" <no.email@nospam.invalid> wrote:
>
> You could look up "timing wheels" for a simpler practical approach that
> the Linux kernel scheduler used to use (I think it changed a few years
> ago).

this is not related to OP's topic

I googled about "timing wheels" and "Linux kernel scheduler", I couldn't
find any learning resources or at least the resources that I can
understand. Could you please point me to some learning resources for a
beginner.

[toc] | [prev] | [next] | [standalone]

#101514

srinivas devaki <mr.eightnoteight@gmail.com> writes:
> I googled about "timing wheels" and "Linux kernel scheduler"

Sorry, correct term was "timer wheel" rather than "timing wheel".

http://www.elinux.org/Kernel_Timer_Systems has some links.

The Erlang BEAM internal scheduler works the same way, iirc.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web