A.N. Prymushko
Èlektron. model. 2019, 41(6):107-114
https://doi.org/10.15407/emodel.41.06.107
ABSTRACT
This article provides an overview of the principles and approaches that allow you to become familiar with such a data structure in the Scala programming language as Vector. The prefix tree is considered as the data structure underlying Vector. Understands the concept of effectively constant execution time on Vector. Real data on the effectiveness of Vector are presented.
KEYWORDS
Vector, prefix tree, algorithm complexity, asymptotic complexity, memory.
REFERENCES
1. “Trie”. Аvailable at: https://en.wikipedia.org/wiki/Tri. Accessed October 27, 2019.
2. Binary search tree. https://en.wikipedia.org/wiki/Binary_search_tree. Accessed October 27, 2019.
3. “Radix tree”, available at: https://en.wikipedia.org/wiki/Radix_tree. Accessed October 27, 2019.
4. “How does a Scala Vector work?”. Available at: http://www.lihaoyi.com/post/ ScalaVectoroperationsarentEffectivelyConstanttime.html#how-does-a-scala-vector-work. Accessed October 27, 2019.
5. “Concrete immutable collection classes”. Available at: https://docs.scala-lang.org/ overviews/ collections/concrete-immutable-collection-classes.html#vectors. Accessed October 27, 2019.
6. “Adventures with Scala Collections” Available at: https://www.47deg.com/blog/ adven-tures-with-scala-collections/#vector-law-abiding-16. Accessed October 27, 2019.
7. “Bio O notation”. Available at: https://en.wikipedia.org/wiki/Big_O_notation#Multiplica-tion_by_a_constant. Accessed October 27, 2019.
8. “Scala collections benchmarking”http://www.lihaoyi.com/post/BenchmarkingScala Col-lections.html#vectors-are-ok. Accessed October 27, 2019.
9. “Performance characteristics”. Available at: https://docs.scala-lang.org/overviews/ collec-tions/performance-characteristics.html. Accessed October 27, 2019.
10. “Benchmarks”. Available at: https://japgolly.github.io/scalajs-benchmark/res/scala213- full. html. Accessed October 27, 2019.
2. Binary search tree. https://en.wikipedia.org/wiki/Binary_search_tree. Accessed October 27, 2019.
3. “Radix tree”, available at: https://en.wikipedia.org/wiki/Radix_tree. Accessed October 27, 2019.
4. “How does a Scala Vector work?”. Available at: http://www.lihaoyi.com/post/ ScalaVectoroperationsarentEffectivelyConstanttime.html#how-does-a-scala-vector-work. Accessed October 27, 2019.
5. “Concrete immutable collection classes”. Available at: https://docs.scala-lang.org/ overviews/ collections/concrete-immutable-collection-classes.html#vectors. Accessed October 27, 2019.
6. “Adventures with Scala Collections” Available at: https://www.47deg.com/blog/ adven-tures-with-scala-collections/#vector-law-abiding-16. Accessed October 27, 2019.
7. “Bio O notation”. Available at: https://en.wikipedia.org/wiki/Big_O_notation#Multiplica-tion_by_a_constant. Accessed October 27, 2019.
8. “Scala collections benchmarking”http://www.lihaoyi.com/post/BenchmarkingScala Col-lections.html#vectors-are-ok. Accessed October 27, 2019.
9. “Performance characteristics”. Available at: https://docs.scala-lang.org/overviews/ collec-tions/performance-characteristics.html. Accessed October 27, 2019.
10. “Benchmarks”. Available at: https://japgolly.github.io/scalajs-benchmark/res/scala213- full. html. Accessed October 27, 2019.