 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 04/08/2011 09:03 AM, Invisible wrote:
>
> OK, the down-side: Sequential access. You can only access lists
> sequentially. Obtaining the Nth element is a linear-time operation, and
> any attempt at parallel processing is fairly doomed from the start.
>
Have you considered a skip list structure?
(http://en.wikipedia.org/wiki/Skip_list)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> OK, the down-side: Sequential access. You can only access lists
>> sequentially. Obtaining the Nth element is a linear-time operation, and
>> any attempt at parallel processing is fairly doomed from the start.
>>
> Have you considered a skip list structure?
> (http://en.wikipedia.org/wiki/Skip_list)
No - mainly because I've never heard of it. ;-)
However, according to Wikipedia, it does everything in logarithmic time.
Well, so does a tree [assuming you can keep it balanced]. Haskell
already has a bazillion different tree implementations [although I don't
recall seeing a mutable one recently].
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 04/08/2011 02:09 PM, Invisible wrote:
> No - mainly because I've never heard of it. ;-)
>
> However, according to Wikipedia, it does everything in logarithmic time.
> Well, so does a tree [assuming you can keep it balanced]. Haskell
> already has a bazillion different tree implementations [although I don't
> recall seeing a mutable one recently].
Skip lists structure is claimed to be so simple,
that it could be easily implemented within an hour
without a textbook (http://goo.gl/yDqKJ).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 4/8/2011 6:09, Invisible wrote:
> However, according to Wikipedia, it does everything in logarithmic time.
It moves forward and back in linear time. It moves far forward in
logarithmic time if you make it tall enough. It's like an unholy union of
tree and list that automatically keeps itself balanced. It's worth reading
about, because it's interesting and easy to understand.
The nice thing is a skip graph, which is as efficient as a skip list except
you can make it distributed like a DHT.
--
Darren New, San Diego CA, USA (PST)
"Coding without comments is like
driving without turn signals."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> Yesterday I was working on a small Haskell library for working with
> mutable double-linked lists. Man, it's been such a long time since I
> worked with this data structure, I'd forgotten how great it is!
then why not using a LISt Processing language? ;)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/04/2011 03:40 AM, nemesis wrote:
> Invisible<voi### [at] devnull> wrote:
>> Yesterday I was working on a small Haskell library for working with
>> mutable double-linked lists. Man, it's been such a long time since I
>> worked with this data structure, I'd forgotten how great it is!
>
> then why not using a LISt Processing language? ;)
Because I prefer working with a system that offers static type
guarantees? And thread safety? And sane syntax? And...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/04/2011 03:40 AM, nemesis wrote:
> Invisible<voi### [at] devnull> wrote:
>> Yesterday I was working on a small Haskell library for working with
>> mutable double-linked lists. Man, it's been such a long time since I
>> worked with this data structure, I'd forgotten how great it is!
>
> then why not using a LISt Processing language? ;)
Also, as a mere technicality... Aren't lists in Lisp *single* linked
rather than *double* linked?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> It's worth
> reading about, because it's interesting and easy to understand.
By contrast, I didn't bother reading much further because it appears to
be very complex and difficult to understand.
> The nice thing is a skip graph, which is as efficient as a skip list
> except you can make it distributed like a DHT.
What's a DHT when it's at home?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 4/12/2011 3:50, Invisible wrote:
>> It's worth
>> reading about, because it's interesting and easy to understand.
>
> By contrast, I didn't bother reading much further because it appears to be
> very complex and difficult to understand.
Well, come on. Look at the pictures and you can understand what's going on. :-)
>> The nice thing is a skip graph, which is as efficient as a skip list
>> except you can make it distributed like a DHT.
>
> What's a DHT when it's at home?
a Hash Table that's not Distributed?
--
Darren New, San Diego CA, USA (PST)
"Coding without comments is like
driving without turn signals."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible escreveu:
> On 09/04/2011 03:40 AM, nemesis wrote:
>> Invisible<voi### [at] devnull> wrote:
>>> Yesterday I was working on a small Haskell library for working with
>>> mutable double-linked lists. Man, it's been such a long time since I
>>> worked with this data structure, I'd forgotten how great it is!
>>
>> then why not using a LISt Processing language? ;)
>
> Also, as a mere technicality... Aren't lists in Lisp *single* linked
> rather than *double* linked?
yep.
--
a game sig: http://tinyurl.com/d3rxz9
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
