Thread overview | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
December 18, 2011 Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
This is bound to turn interesting: http://www.reddit.com/r/programming/comments/nddlj/extreme_cleverness_functional_data_structures_in/ Andrei |
December 18, 2011 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Le 18/12/2011 09:22, Andrei Alexandrescu a écrit :
> This is bound to turn interesting:
>
> http://www.reddit.com/r/programming/comments/nddlj/extreme_cleverness_functional_data_structures_in/
>
>
>
> Andrei
Interesting speach, but thoses datastructures are kind of trying dealing with a nail using a screwdriver. Problems solved here are not problem that nicely solve in functionnal, so why use functionnal ?
I did always think it is stupid to enforce a paradigm because it is supposed to be supperior, blablabla . . .
Java did it with OOP, and we end up with many stupid thing, static main within a class. OOP is working for some stuff, and not for others. Just as functionnal.
Secondly, I think this conf is going out of sanity during the butmap vector trie presentation (about 40 mins). Many claims not backed with facts, and messy explaination (the cache stuff doesn't exlain in any way how this datastruct can be faster than ArrayList, and I bet it isn't expect on a flawed benchmark). No idea why polymorphism is revealant here either - but this is most likely an error and not the word the speaker wanted to use.
Some argument are not convincing. OK, log32(n) is close to O(1) in many cases but it isn't O(1). Matter of fact.
It look like the author try to convince us that oranges can taste like banana, and show us many techniques to go in that direction, but this is useless as logn as we have banana available.
Thoses datastruct are interesting anyway on a research perspective.
|
December 18, 2011 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Andrei Alexandrescu:
> http://www.reddit.com/r/programming/comments/nddlj/extreme_cleverness_functional_data_structures_in/
You need to be registered to download the PDF slides :-(
Scala language seems rather compact and powerful to define such data structures. The function balance() at 24.21 to balance red-black trees using just pattern matching is quite nice, despite being a bit long.
But I don't know what those operators like +A >: <: mean.
Bye,
bearophile
|
December 18, 2011 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | On 12/18/2011 04:48 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> http://www.reddit.com/r/programming/comments/nddlj/extreme_cleverness_functional_data_structures_in/
>
> You need to be registered to download the PDF slides :-(
>
> Scala language seems rather compact and powerful to define such data structures. The function balance() at 24.21 to balance red-black trees using just pattern matching is quite nice, despite being a bit long.
>
> But I don't know what those operators like +A>:<: mean.
>
> Bye,
> bearophile
+A (-A) means A only occurs in covariant (contravariant) positions, the other two are used for constraints, where >: means supertype-of and <: means subtype-of.
|
December 20, 2011 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to deadalnix | On Sun, 18 Dec 2011 15:23:10 +0100, deadalnix wrote:
>
> Some argument are not convincing. OK, log32(n) is close to O(1) in many
> cases but it isn't O(1). Matter of fact.
>
Well, he talks about it, and we must admit that for the memory you *can* address, log32(n) is really, really fast. Matter of fact. :)
|
December 20, 2011 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dejan Lekic | On 12/20/11 4:44 AM, Dejan Lekic wrote:
> On Sun, 18 Dec 2011 15:23:10 +0100, deadalnix wrote:
>
>>
>> Some argument are not convincing. OK, log32(n) is close to O(1) in many
>> cases but it isn't O(1). Matter of fact.
>>
>
> Well, he talks about it, and we must admit that for the memory you *can*
> address, log32(n) is really, really fast. Matter of fact. :)
I agree. Well, anywhere between 1 and 7. I only have a bit of a problem with making a number between 1 and 7 equal to 1.
Andrei
|
January 11, 2012 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | == Extrait de l'article de « bearophile (bearophileHUGS@lycos.com) » > Andrei Alexandrescu: > > http://www.reddit.com/r/programming/comments/nddlj/extreme_cleverness_functional_data_structures_in/ > You need to be registered to download the PDF slides :-( I don't think from githup you can have them by clicking on the raw link: https://github.com/strangeloop/2011-slides/blob/master/Spiewak-FunctionalData.pdf https://github.com/strangeloop/2011-slides/ Regards, renoX |
January 11, 2012 Re: Bitmapped vector tries vs. arrays | ||||
---|---|---|---|---|
| ||||
Posted in reply to renoX | renoX:
> https://github.com/strangeloop/2011-slides/
Oh, very good, thank you.
Bye,
bearophile
|
Copyright © 1999-2021 by the D Language Foundation