6 ms·
Another useful datatype is a rope[0]. It is useful for using immutable/shared pieces that can build up to other longer compositions. In particular, an operation
by karmakaze 3y ago
Another useful datatype is a rope[0]. It is useful for using immutable/shared pieces that can build up to other longer compositions. In particular, an operation such as concatenation can be O(1) since that's matches the representation of a rope.
[0] https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure)
- jcparkyn 3y agoAlso worth noting that just about every javascript engine uses ropes internally to represent strings (most of the time). https://docs.google.com/document/d/1o-MJPAddpfBfDZCkIHNKbMiM86iDFld7idGbNQLuKIQ/preview#heading=h.6kknmf22ixwc https://docs.google.com/document/d/1o-MJPAddpfBfDZCkIHNKbMiM...
- codethief 3y ago> most of the time Looking at the reference[0] given at the very end of the document, wouldn't the word "sometimes" be more appropriate? [0]: https://mrale.ph/blog/2016/11/23/making-less-dart-faster.html https://mrale.ph/blog/2016/11/23/making-less-dart-faster.htm...
- jcparkyn 3y agoInteresting, seems like things are more complicated than I thought.
- shirleyquirk 3y agoThe Nim compiler used ropes internally for years, until recently[0] because removing them reduced memory consumption and decreased compile times, so ymmv [0]https://github.com/nim-lang/Nim/pull/20433 https://github.com/nim-lang/Nim/pull/20433
- dietr1ch 3y agoThis is a big tell that maybe we don't want to know exactly the type, but to have way to let the compiler/benchmarks to pick the best performing data structure for the task at hand, but I think that on most programming languages neither the language nor the tooling help you too much here.* *Saying this mostly with the intent of being proved wrong ;) kxcd://386
- sakex 3y agoA company had me implement that in Rust during an interview. It was pretty hard