Provides fast:
- concatenation (++)
- patching
- random element insertion/removal
resolvers += "abzu" at "http://dl.bintray.com/content/abzu/maven"
libraryDependencies += "fi.rbvector" %% "rbvector" % "1.0.0"
Requires Scala 2.10 or 2.11.
Nothing special, a drop in replacement for standard library Vector.
Two convenience methods for random element removal and insertion are provided: inserted and removed. (Method names where inspired by existing updated method).
scala> import rbvector.Vector
import rbvector.Vector
// alias for patch(2, Vector(3), 0)
scala> Vector(1, 2, 4).inserted(2, 3)
res0: rbvector.Vector[Int] = Vector(1, 2, 3, 4)
// alias for patch(1, Vector(), 1)
scala> res0.removed(1)
res1: rbvector.Vector[Int] = Vector(1, 3, 4)In a nut shell, you want to use this if you need to
- concatenate vectors [1]
- use patch method
- do random element insertion/removal
- have a truly general purpose IndexedSeq
The last point is bit subjective. Where standard Vector performs in O(log_32 n) rbvector has O(log_2 n). One way to illustrate this:
- log_2 (2^31 - 1) ~= 31.0
- log_32 (2^31 - 1) ~= 6.2
That is, you can expect standard Vector to be slightly faster in many operations. Standard Vector also benfits being based on arrays whereas rbvector is based on red-black trees. But then again, standard Vector ++ and patch methods have complexity of O(n + m) where as rbvector has O(log(n + m)).
Some examples assuming one million element Vector(s):
- rbvector ++ is 25000 times faster than standard Vector
- standard Vector head() is 6.6 times faster and take() is 7.7 times faster
See the benchmark results for details.
[1] Scala 2.11 Vector ++ has been optimized to perform slightly better, especially when one of the collections is small.
Most of the code is directly taken from Scala standard library classes (scala.collection.immutable.RedBlackTree, scala.collection.immutable.TreeMap and scala.collection.immutable.Vector).
RRBVector provided also some inspiration: https://github.com/TiarkRompf/rrbtrees
Apache License, Version 2.0
