Почему индексированная последовательность быстрее линейного индекса в Scala?

Question

В Scala есть два типа последовательностей (это можно сделать более общим; не указывать c - Scala).

1. Linear Sequence, where random access of elements involves traversal from one end to the element which is a slower process.
2. Indexed Sequence, where random access of elements is really quick.

Я хотел бы знать, почему доступ к элементам в индексированной последовательности происходит быстрее?

Это потому, что использование указателя в их базовой реализации? (адрес рассчитывается по: базовому адресу + (размер элемента * индекс элемента для извлечения))

Если это так, почему линейная последовательность не может быть реализована таким же образом? и мог быть сделан быстрее.

Answer 1

со страницы ScalaDocs : «Векторы реализуются с помощью сбалансированных по радиусу деревьев пальцев шириной 32». Array индексируется через адресную арифметику c, как вы описали. Оба предлагают очень быстрый выбор произвольного доступа (читай «индексация»).

A List, с другой стороны, выполняет медленный линейный поиск для каждого индексированного доступа. Так почему же списки так распространены в Scala коде?

Это потому, что произвольный доступ - не единственный способ доступа к элементам коллекции. Например, если вы хотите просто просмотреть последовательность, то List очень эффективен.

Я где-то читал, что Мартин Одерски однажды проводил эксперимент, в котором он заменял каждый List в коде компилятора на Vector. Результатом стал более медленный компилятор.

Answer 2

Если это правда, почему линейная последовательность не может быть реализована таким же образом? и могли бы быть сделаны быстрее.

Поскольку тогда это больше не будет линейной последовательностью, это будет индексированная последовательность с произвольным доступом.

Есть некоторые важные различия в Требования к памяти: массив требует единого, плоского, непрерывного куска памяти. Например, если вы хотите хранить 4 миллиарда хэшей SHA-1 в массиве, вам понадобится огромный, одиночный, плоский, непрерывный, неиспользуемый кусок из 128 гиоктетов. В то время как со списком, связанным по одной ссылке, вам понадобится 4 миллиарда маленьких кусочков по 40 октетов. Его гораздо проще найти, даже если он использует больше памяти (160 гиоктетов вместо 128 гиоктетов, то есть на 25% больше) из-за указателя next, который вы должны сохранить.