А.Н. Примушко
Èlektron. model. 2019, 41(6):107-114
https://doi.org/10.15407/emodel.41.06.107
АНОТАЦІЯ
Подано огляд принципів і підходів, які дозволяють ознайомитися зі структурою даних Vector у мові програмування Scala. Розглянуто префіксне дерево як структура даних, що лежить в основі структури Vector. Проаналізовано поняття ефективно константного часу виконання операцій над структурою Vector. Наведено реальні дані про ефективність структури Vector.
КЛЮЧОВІ СЛОВА:
вектор, префіксне дерево, складність алгоритму, асимптотична складність, пам’ять.
СПИСОК ЛІТЕРАТУРИ
1. Wikipedia. Префиксное дерево. [Электронный ресурс] Режим доступа: https:// en.wikipedia.org/wiki/Tri. Дата обращения: 27.10.19.
2. Wikipedia. Двоичное дерево поиска. [Электронный ресурс] Режим доступа: https://en.wikipedia.org/wiki/Binary_search_tree. Дата обращения: 27.10.19.
3. Wikipedia. Базисное дерево. [Электронный ресурс] Режим доступа: https://en.wikipedia.org/wiki/Radix_tree. Дата обращения: 27.10.19.
4. Haoyi's Programming. How does a Scala Vector work? [Электронный ресурс] Режим доступа: http://www.lihaoyi.com/post/ScalaVectoroperationsarent EffectivelyConstant-time.html#how-does-a-scala-vector-work. Дата обращения: 27.10.19.
5. Scala-lang. Concrete immutable collection classes. [Электронный ресурс] Режим доступа: https://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes. html#vectors. Дата обращения: 27.10.19.
6. 47deg. Adventures with Scala Collections. [Электронный ресурс] Режим доступа: https://www.47deg.com/blog/adventures-with-scala-collections/#vector-law-abiding-16. Дата обращения: 27.10.19.
7. Wikipedia. Bio O notation. [Электронный ресурс] Режим доступа: https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant. Дата обращения: 27.10.19.
8. Haoyi's Programming. Scala collections benchmarking. [Электронный ресурс] Режим доступа: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#vectors-are-ok. Дата обращения: 27.10.19.
9. Scala-lang. Performance characteristics. [Электронный ресурс] Режим доступа: https:// docs.scala-lang.org/overviews/collections/performance-characteristics.html. Дата обраще-ния: 27.10.19.
10. Github: Benchmarks. [Электронный ресурс] Режим доступа: https://japgolly.github.io/ scalajs-benchmark/res/scala213-full.html. Дата обращения: 27.10.19.
ПРИМУШКО Арсентий Николаевич, магистр Национального технического университета Украины «Киевский политехнический институт им. Игоря Сикорского», бакалаврат которого окончил в 2019 г. Область научных исследований – искусственный интеллект, машинное обучение, искусственные нейронные сети, программирование, системы навигации и ориентации.