5 ms·
Fast immutable vectors in C#
- Bognar 12y agoComparisons with ImmutableList<T> from Microsoft aren't necessarily valid, since ImmutableList<T> supports insertion and removal at arbitrary points. The implementation in the article is optimized for adding at the end.
- DenisM 12y agoThat's why there are two separate methods on this class - Add (at the end) and Set (anywhere). Both outperform the corresponding ImmutableList<T>, according to the article.
- danbruc 12y agoBut Set can just overwrites the specified element while Insert will insert the element at the specified position by pushing the element and all following elements out of the way.
- SideburnsOfDoom 12y ago> But Set can just overwrites the specified element Kind of: Set returns a new Vector with a changed state (the specified element overwritten). But yes, this implement is very sparse: there's no way to add and remove elements in the middle, no way to even tell how many elements are in the list: https://news.ycombinator.com/item?id=8592178 https://news.ycombinator.com/item?id=8592178 Perhaps omitting them hides some different optimisation choices (i.e. they would be more expensive) Maybe it's just a proof of concept?
- Bognar 12y agoSet is the corollary to SetItem on ImmutableList<T>, not Insert.
- Ono-Sendai 12y agoI have something similar in C++, works pretty well.
- _random_ 12y ago"If there’s interest in a full featured production quality version, I may implement that." That would be great.
- 0xffff2 12y agoFast immutable collections are easy when your collections aren't actually immutable. http://www.reddit.com/r/programming/comments/2lyf8f/fast_immutable_vectors_in_c_10x_faster_and_90/clzloli http://www.reddit.com/r/programming/comments/2lyf8f/fast_imm...
- corysama 12y agoFix commited: http://www.reddit.com/r/programming/comments/2lyf8f/fast_immutable_vectors_in_c_10x_faster_and_90/clzpuwv http://www.reddit.com/r/programming/comments/2lyf8f/fast_imm...
- SideburnsOfDoom 12y agoHm.. am I missing something? there's no Count property on the Vector interface. If Lookup and Set take an index (int i), and you can't tell how many items there are in the vector, what happens when you specify an index way past the end to one of those?
- alkonaut 12y agoThat is really odd (unless I'm also missing something). It should be trivial to implement a count.
- SideburnsOfDoom 12y agoIt should be trivial. The only reasonable explanation that I can think of is that it was't needed for a Proof of Concept.
- joosters 12y agoBut... this isn't actually a vector. It stands to reason that if you use a different data structure then you will get different timing properties, but you are not comparing like-for-like.
- alkonaut 12y agoWhat is a vector? There is nothing that says a vector has to be a sequentially stored array. If you agree that the interface is a vector interface, then it "is" a vector.
- joosters 12y agoThat's pretty much the definition of it. It's what just about every language out there calls a vector. If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector...
- alkonaut 12y agoA "list" can be a linked list, an array based list and so on. Would a data structure stored in an array but not supporting the correct interface be a "vector" because the secret implementation is an array?
- zamalek 12y agoQueues and stacks are typically implemented using arrays. Should a queue or stack that uses a linked list (which is how you make them lock-free, or one way to make them immutable) be called something else then?
- SideburnsOfDoom 12y ago> If you want a blackbox object that has Lookup(), Add() and Set() but with no guarantees about the underlying algorithm, you should probably avoid calling it a vector. "Vector" here is an interface. The equivalent, e.g. "interface ILinkedListVector" is considered bad practice, i.e. you do want an interface to be a back box and not leak implementation details. if it has the right operations, "Vector" (actually more like "IVector<T>") is an acceptable interface name.