Исследование характеристик структуры данных Veсtor в языке программирования Scala

А.Н. Примушко
Национальный технический университет Украины «Киевский политехнический институт им. Игоря Сикорского»
(Украина, 03056, Киев, пр-т Победы, 37, e-mail: Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.)

È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 г. Область научных исследований – искусственный интеллект, машинное обучение, искусственные нейронные сети, программирование, системы навигации и ориентации.

Полный текст: PDF