Looking for a datastructure

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

Kees Bleijenberg-2
My program uses a very long list of (index,count) items. Index and count are
Int's.
The program updates the count values a lot. Therefor it uses the index as a
key to update the belonging count value.
After updating, the program needs the (index,count) pair with the least
count value in the list.
What is an approriate (fast) datastructure? My first idea was to use a heap.
Problem with the heap is that I can't update the count value by its index
fast.
Any ideas?

Kees
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110715/755c0228/attachment-0001.htm>

Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

Ertugrul Söylemez
"Kees Bleijenberg" <k.bleijenberg at inter.nl.net> wrote:

> My program uses a very long list of (index,count) items. Index and count are
> Int's.
> The program updates the count values a lot. Therefor it uses the index as a
> key to update the belonging count value.
> After updating, the program needs the (index,count) pair with the least
> count value in the list.
> What is an approriate (fast) datastructure? My first idea was to use a heap.
> Problem with the heap is that I can't update the count value by its index
> fast.
> Any ideas?

Try Data.IntMap and Data.Map.  I think they have different asymptotics,
but they both do exactly what you want, so try both.  Because of the
purity I would estimate the total query time to O(log n) and the total
update time to O((log n)^2).


Greets,
Ertugrul


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/




Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

Chaddaï Fouché
In reply to this post by Kees Bleijenberg-2
On Fri, Jul 15, 2011 at 11:42 AM, Kees Bleijenberg
<k.bleijenberg at inter.nl.net> wrote:

> My program uses?a very long list of (index,count) items. Index and
> count?are?Int's.
> The program?updates the count values a lot. Therefor?it uses?the index as a
> key to?update the belonging count value.
> After updating, the program needs the (index,count) pair with the least
> count value in the list.
> What is an approriate (fast)?datastructure? My first idea was to use a heap.
> Problem?with the?heap is that I can't update the count value by its index
> fast.
> Any ideas?

Do you need to be able to "remove" the pair that has the least count cheaply ?

--
Jeda?


Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

Kees Bleijenberg-2
Jeda?,


On Fri, Jul 15, 2011 at 11:42 AM, Kees Bleijenberg
<k.bleijenberg at inter.nl.net> wrote:
> My program uses?a very long list of (index,count) items. Index and
> count?are?Int's.
> The program?updates the count values a lot. Therefor?it uses?the index
> as a key to?update the belonging count value.
> After updating, the program needs the (index,count) pair with the
> least count value in the list.
> What is an approriate (fast)?datastructure? My first idea was to use a
heap.
> Problem?with the?heap is that I can't update the count value by its
> index fast.
> Any ideas?

Do you need to be able to "remove" the pair that has the least count cheaply
?

Yes, that would be nice. But as an alternative I can give give it a very,
very high count.
I need an index to access the elements (just like a map) and the map should
stay sorted on another 'field' then the key (or at least it should act as a
heap for that 'non-key field').

Kees



Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

David Place

On Jul 15, 2011, at 8:30 AM, Kees Bleijenberg wrote:

> I need an index to access the elements (just like a map) and the map should
> stay sorted on another 'field' then the key (or at least it should act as a
> heap for that 'non-key field').
>
> Kees


Hi, Kees.

Have you looked into fingertrees?  They give an enormously powerful way to express incremental computations over trees with big O logarithmic complexity.  

> http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

____________________
David Place  
Owner, Panpipes Ho! LLC
http://panpipesho.com
d at vidplace.com





Reply | Threaded
Open this post in threaded view
|

Looking for a datastructure

David Place
In reply to this post by Kees Bleijenberg-2
On Jul 15, 2011, at 8:30 AM, Kees Bleijenberg wrote:

>  need an index to access the elements (just like a map) and the map should
> stay sorted on another 'field' then the key (or at least it should act as a
> heap for that 'non-key field').

More on fingertrees.  In fact, i think this module in the fingertree package does exactly what you need.

> http://hackage.haskell.org/packages/archive/fingertree/0.0.1.0/doc/html/Data-PriorityQueue-FingerTree.html

____________________
David Place  
Owner, Panpipes Ho! LLC
http://panpipesho.com
d at vidplace.com