data structure like skips list in Erlang

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

data structure like skips list in Erlang

Benoit Chesneau-2
Hi all,

I’m looking for a datastructure like a skiplist to maintain an ordered set of Key/Values. It has to have the following properties:

* allows custom compare function to order the data in a specific order
* allows the user to iterate forward (next) and backward (prev) the data

Has someone already written a lib that offers such datastructure? Or maybe we can add a `prev(Key) function to gb_tree? Any idea i welcome :)

- benoit
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Dmitry Kolesnikov-2
Hello,

It looks like you are looking for data structure called zipper. I’ve not used any of these but there is at least two versions of zippers for Erlang.


- Dmitry


On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:

Hi all,

I’m looking for a datastructure like a skiplist to maintain an ordered set of Key/Values. It has to have the following properties:

* allows custom compare function to order the data in a specific order
* allows the user to iterate forward (next) and backward (prev) the data

Has someone already written a lib that offers such datastructure? Or maybe we can add a `prev(Key) function to gb_tree? Any idea i welcome :)

- benoit
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Benoit Chesneau-2
hmm i forgot to mention i need to also lookup for the data so not sure if a zipper is designed for it. 

 I will have a loom kn the libs anyway, thanks for the links :)

- benoît

On 8 Oct 2017, at 19:33, Dmitry Kolesnikov <[hidden email]> wrote:

Hello,

It looks like you are looking for data structure called zipper. I’ve not used any of these but there is at least two versions of zippers for Erlang.


- Dmitry


On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:

Hi all,

I’m looking for a datastructure like a skiplist to maintain an ordered set of Key/Values. It has to have the following properties:

* allows custom compare function to order the data in a specific order
* allows the user to iterate forward (next) and backward (prev) the data

Has someone already written a lib that offers such datastructure? Or maybe we can add a `prev(Key) function to gb_tree? Any idea i welcome :)

- benoit
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Billy Svensson
I've needed this in the past too. Couldn't find any lib that could do
it so I just ported the floor and ceiling methods of the TreeMap class
in Java to an Erlang module that operated on a gb_tree.
It's a bit ugly though since you have to work on the "hidden" data
structure of the gb_trees module, so would be great if this could be a
part of the standard module instead.

Not sure I still have that code, but could try to find it if you want.
You would probably need to test it a bit better though since I only
used it for a small hobby project.

On Sun, Oct 8, 2017 at 8:21 PM, Benoit Chesneau <[hidden email]> wrote:

> hmm i forgot to mention i need to also lookup for the data so not sure if a
> zipper is designed for it.
>
>  I will have a loom kn the libs anyway, thanks for the links :)
>
> - benoît
>
> On 8 Oct 2017, at 19:33, Dmitry Kolesnikov <[hidden email]> wrote:
>
> Hello,
>
> It looks like you are looking for data structure called zipper. I’ve not
> used any of these but there is at least two versions of zippers for Erlang.
>
> https://github.com/ferd/zippers
> https://github.com/inaka/zipper
>
> - Dmitry
>
>
> On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:
>
> Hi all,
>
> I’m looking for a datastructure like a skiplist to maintain an ordered set
> of Key/Values. It has to have the following properties:
>
> * allows custom compare function to order the data in a specific order
> * allows the user to iterate forward (next) and backward (prev) the data
>
> Has someone already written a lib that offers such datastructure? Or maybe
> we can add a `prev(Key) function to gb_tree? Any idea i welcome :)
>
> - benoit
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Benoit Chesneau-2
I’m didn’t find anything that fit my need. There are some btree libs but that doesn’t fit my needs. Also a tree is not that fast for memory imo. I’m thinking to build a red-black tree lib that support iterations for it. Red-black trees look simple enough to be build as a pure functional data structure. Still contemplating though.

Benoit

> On 9 Oct 2017, at 09:52, Billy Svensson <[hidden email]> wrote:
>
> I've needed this in the past too. Couldn't find any lib that could do
> it so I just ported the floor and ceiling methods of the TreeMap class
> in Java to an Erlang module that operated on a gb_tree.
> It's a bit ugly though since you have to work on the "hidden" data
> structure of the gb_trees module, so would be great if this could be a
> part of the standard module instead.
>
> Not sure I still have that code, but could try to find it if you want.
> You would probably need to test it a bit better though since I only
> used it for a small hobby project.
>
> On Sun, Oct 8, 2017 at 8:21 PM, Benoit Chesneau <[hidden email]> wrote:
>> hmm i forgot to mention i need to also lookup for the data so not sure if a
>> zipper is designed for it.
>>
>> I will have a loom kn the libs anyway, thanks for the links :)
>>
>> - benoît
>>
>> On 8 Oct 2017, at 19:33, Dmitry Kolesnikov <[hidden email]> wrote:
>>
>> Hello,
>>
>> It looks like you are looking for data structure called zipper. I’ve not
>> used any of these but there is at least two versions of zippers for Erlang.
>>
>> https://github.com/ferd/zippers
>> https://github.com/inaka/zipper
>>
>> - Dmitry
>>
>>
>> On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:
>>
>> Hi all,
>>
>> I’m looking for a datastructure like a skiplist to maintain an ordered set
>> of Key/Values. It has to have the following properties:
>>
>> * allows custom compare function to order the data in a specific order
>> * allows the user to iterate forward (next) and backward (prev) the data
>>
>> Has someone already written a lib that offers such datastructure? Or maybe
>> we can add a `prev(Key) function to gb_tree? Any idea i welcome :)
>>
>> - benoit
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Frank Muller
Benoit,

It’s called “Judy Array” and Erlang bindings do exist:

You can search for next/previous elements and do stuffs no other hashing libs support.

/Frank

I’m didn’t find anything that fit my need. There are some btree libs but that doesn’t fit my needs. Also a tree is not that fast for memory imo. I’m thinking to build a red-black tree lib that support iterations for it. Red-black trees look simple enough to be build as a pure functional data structure. Still contemplating though.

Benoit

> On 9 Oct 2017, at 09:52, Billy Svensson <[hidden email]> wrote:
>
> I've needed this in the past too. Couldn't find any lib that could do
> it so I just ported the floor and ceiling methods of the TreeMap class
> in Java to an Erlang module that operated on a gb_tree.
> It's a bit ugly though since you have to work on the "hidden" data
> structure of the gb_trees module, so would be great if this could be a
> part of the standard module instead.
>
> Not sure I still have that code, but could try to find it if you want.
> You would probably need to test it a bit better though since I only
> used it for a small hobby project.
>
> On Sun, Oct 8, 2017 at 8:21 PM, Benoit Chesneau <[hidden email]> wrote:
>> hmm i forgot to mention i need to also lookup for the data so not sure if a
>> zipper is designed for it.
>>
>> I will have a loom kn the libs anyway, thanks for the links :)
>>
>> - benoît
>>
>> On 8 Oct 2017, at 19:33, Dmitry Kolesnikov <[hidden email]> wrote:
>>
>> Hello,
>>
>> It looks like you are looking for data structure called zipper. I’ve not
>> used any of these but there is at least two versions of zippers for Erlang.
>>
>> https://github.com/ferd/zippers
>> https://github.com/inaka/zipper
>>
>> - Dmitry
>>
>>
>> On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:
>>
>> Hi all,
>>
>> I’m looking for a datastructure like a skiplist to maintain an ordered set
>> of Key/Values. It has to have the following properties:
>>
>> * allows custom compare function to order the data in a specific order
>> * allows the user to iterate forward (next) and backward (prev) the data
>>
>> Has someone already written a lib that offers such datastructure? Or maybe
>> we can add a `prev(Key) function to gb_tree? Any idea i welcome :)
>>
>> - benoit
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: data structure like skips list in Erlang

Vans S
Either im completely missing the point or this has been in core erlang for a long time.

ets ordered_set.

> * allows custom compare function to order the data in a specific order

Setup a key tuple instead of custom compare function.  If you need to sort by values pull those out into the key tuple.

> * allows the user to iterate forward (next) and backward (prev) the data>

ets:next|prev

> Has someone already written a lib that offers such datastructure? Or maybe we can add a `prev(Key) function to gb_tree? Any idea i welcome :)

Only part that this does not fit is the requirement for a custom compare function.  If the custom compare is very complex, itl be very expensive regardless and wont scale.  If the custom compare is simple, a tuple key should replace it.


On Monday, October 9, 2017 6:24 AM, Frank Muller <[hidden email]> wrote:


Benoit,

It’s called “Judy Array” and Erlang bindings do exist:

You can search for next/previous elements and do stuffs no other hashing libs support.

/Frank

I’m didn’t find anything that fit my need. There are some btree libs but that doesn’t fit my needs. Also a tree is not that fast for memory imo. I’m thinking to build a red-black tree lib that support iterations for it. Red-black trees look simple enough to be build as a pure functional data structure. Still contemplating though.

Benoit

> On 9 Oct 2017, at 09:52, Billy Svensson <[hidden email]> wrote:
>
> I've needed this in the past too. Couldn't find any lib that could do
> it so I just ported the floor and ceiling methods of the TreeMap class
> in Java to an Erlang module that operated on a gb_tree.
> It's a bit ugly though since you have to work on the "hidden" data
> structure of the gb_trees module, so would be great if this could be a
> part of the standard module instead.
>
> Not sure I still have that code, but could try to find it if you want.
> You would probably need to test it a bit better though since I only
> used it for a small hobby project.
>
> On Sun, Oct 8, 2017 at 8:21 PM, Benoit Chesneau <[hidden email]> wrote:
>> hmm i forgot to mention i need to also lookup for the data so not sure if a
>> zipper is designed for it.
>>
>> I will have a loom kn the libs anyway, thanks for the links :)
>>
>> - benoît
>>
>> On 8 Oct 2017, at 19:33, Dmitry Kolesnikov <[hidden email]> wrote:
>>
>> Hello,
>>
>> It looks like you are looking for data structure called zipper. I’ve not
>> used any of these but there is at least two versions of zippers for Erlang.
>>
>> https://github.com/ferd/zippers
>> https://github.com/inaka/zipper
>>
>> - Dmitry
>>
>>
>> On 8 Oct 2017, at 20.14, Benoit Chesneau <[hidden email]> wrote:
>>
>> Hi all,
>>
>> I’m looking for a datastructure like a skiplist to maintain an ordered set
>> of Key/Values. It has to have the following properties:
>>
>> * allows custom compare function to order the data in a specific order
>> * allows the user to iterate forward (next) and backward (prev) the data
>>
>> Has someone already written a lib that offers such datastructure? Or maybe
>> we can add a `prev(Key) function to gb_tree? Any idea i welcome :)
>>
>> - benoit
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions