Подтвердить что ты не робот

Как работает Scala Vector?

Я прочитал эту страницу о временной сложности коллекций Scala. Как сказано, Vector сложность eC для всех операций.

Мне стало интересно, что это за Vector. Я прочитал документ , и он говорит:

Поскольку векторы достигают хорошего баланса между быстрыми случайными выборами и быстрыми случайными функциональными обновлениями, они в настоящее время являются реализация по умолчанию неизменяемых индексированных последовательностей. Это подтверждается немного endian бит-отображенный вектор trie с коэффициентом разветвления 32. Местность очень хорошая, но не смежная, что хорошо для большие последовательности.

Как и все остальное о Scala, оно довольно расплывчато. Как работает Vector?

4b9b3361

ОТВЕТЫ

Ответ 1

Ключевое слово здесь Trie. Вектор реализуется как структурная структура Trie. См. http://en.wikipedia.org/wiki/Trie.

Точнее, это "бит-отображенный векторный trie". Я только что нашел достаточно подробное описание структуры (наряду с реализацией - по-видимому, в Rust):

https://bitbucket.org/astrieanna/bitmapped-vector-trie

Наиболее релевантная выдержка:

Разорванное векторное Trie - это в основном 32-дерево. Уровень 1 представляет собой массив размером 32, любого типа данных. Уровень 2 - это массив из 32 уровней 1. и так далее, пока: Уровень 7 не является массивом из 2 уровней 6.

ОБНОВЛЕНИЕ: В ответ на комментарий Lai Yu-Hsuan о сложности:

Я должен буду предположить, что вы имели в виду "глубину" здесь: -D. В легенде для "eC" говорится: "Операция занимает эффективное постоянное время, но это может зависеть от некоторых допущений, таких как максимальная длина вектора или распределение хэш-ключей".

Если вы хотите рассмотреть наихудший случай и учитывая, что существует верхняя граница максимального размера вектора, то да, действительно, мы можем сказать, что сложность постоянна. Скажем, что максимальный размер равен 2 ^ 32, то это означает, что наихудший случай - это 7 операций в лучшем случае, в любом случае. Опять же, мы всегда можем рассмотреть наихудший случай для любого типа коллекции, найти верхнюю границу и сказать, что это постоянная сложность, но для списка на примере это будет означать константу в 4 миллиарда, что не совсем практично.

Но вектор противоположный, 7 операций более чем практичны, и именно так мы можем позволить себе постоянно учитывать его сложность.

Еще один способ взглянуть на это: мы не говорим о log (2, N), но log (32, N). Если вы попытаетесь построить, вы увидите, что это практически горизонтальная линия. Таким образом, прагматично говоря, вы никогда не сможете увидеть значительное увеличение времени обработки по мере роста коллекции. Да, это еще не очень постоянное (поэтому оно отмечено как "eC", а не только "C" ), и вы сможете увидеть разницу вокруг коротких векторов (но опять же, очень маленькая разница, потому что число операций растет настолько медленно).

Ответ 2

Другие ответы re 'Trie' хороши. Но, как близкое приближение, просто для быстрого понимания:

  • Вектор внутренне использует древовидную структуру - не двоичное дерево, а 32-арное дерево
  • Каждый '32 -way node 'использует Array [32] и может хранить либо 0-32 ссылки на дочерние узлы, либо 0-32 части данных
  • Дерево структурировано таким образом, чтобы его можно было сбалансировать определенным образом - это уровни "n" глубоко, но уровни с 1 по n-1 являются "уровнями только для индекса" (100% дочерние ссылки, без данных), а уровень n содержит все данные (100% данных, никаких дочерних ссылок). Поэтому, если число элементов данных равно "d", тогда n = log-base-32 (d) округлено вверх

Почему это? Простой: для производительности.

Вместо того, чтобы делать тысячи/миллионы/gazillions распределения памяти для каждого отдельного элемента данных, память выделяется в 32 элементарных фрагментах. Вместо того, чтобы прокладывать мили глубоко, чтобы найти ваши данные, структура довольно мелкая - это очень широкое, короткое дерево. Например. 5 уровней могут содержать 32 элемента данных 5 элементов (для 4-байтовых элементов = 132 ГБ, т.е. Довольно большой), и каждый доступ к данным будет искать и проходить через 5 узлов из корня (тогда как большой массив будет использовать один доступ к данным). Вектор не проактивно выделяет память для всех уровней n (данных), - он выделяет в 32 элементарных фрагментах по мере необходимости. Это дает производительность чтения, несколько похожую на огромный массив, имея функциональные характеристики (мощность и гибкость и эффективность памяти), несколько похожие на двоичное дерево.

:)