Как растровый вектор trie быстрее обычного?

Ответ 1

растровые векторные попытки не строго быстрее, чем обычные векторы, по крайней мере, не во всем. Это зависит от того, какую операцию вы рассматриваете.

Обычные векторы быстрее, например, при доступе к элементу данных по конкретному индексу. Трудно побить прямой поиск по индексированным массивам. И с точки зрения местоположения в кешках большие массивы довольно хороши, если все, что вы делаете, последовательно перебирает их.

Однако растровое векторное trie будет намного быстрее для других операций (благодаря структурному разделению) - например, создание новой копии с одним измененным элементом без влияния на исходную структуру данных равно O (log32 n) по сравнению с O (n ) для традиционного вектора. Это огромная победа.

Здесь отличное видео, которое стоит посмотреть на эту тему, что включает в себя много мотивации, почему вы можете захотеть таких структур на вашем языке: Стойкие структуры данных и управляемые ссылки (разговор Рика Хики).

Ответ 2

В других ответах много хорошего, но благородный отвечает на ваш вопрос. PersistenVectors работают только для множества случайных поисков по индексу (когда массив большой). "Как это может быть?" вы можете спросить. "Нормальный плоский массив должен только перемещать указатель, PersistentVector должен пройти через несколько шагов".

Ответ - "Локальная кэш".

Кэш всегда получает диапазон из памяти. Если у вас большой массив, он не подходит к кешу. Поэтому, если вы хотите получить элемент x и item y, вам нужно перезагрузить весь кеш. Это потому, что массив всегда последователен в памяти.

Теперь с PVector, который отличается. Есть много маленьких массивов, плавающих вокруг, и JVM умен в этом и помещает их близко друг к другу в памяти. Поэтому для случайного доступа это быстро; если вы пропустите его последовательно, это будет намного медленнее.

Я должен сказать, что я не специалист по аппаратным средствам или как JVM обрабатывает местность кеша, и я никогда не сравнивал это сам; Я просто пересказываю вещи, которые я слышал от других людей.

Изменить: mikera тоже это упоминает.

Изменить 2: см. этот разговор о функциональных структурах данных, пропустите последнюю часть, если вас интересует только вектор. http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala

Ответ 3

Что вы подразумеваете под "простым вектором"? Просто плоский массив предметов? Это здорово, если вы никогда не обновляете его, но если вы когда-либо меняете 1-мерный элементный вектор, вам нужно много копировать; дерево существует, чтобы вы могли поделиться большей частью структуры.

Ответ 4

Краткое объяснение: он использует тот факт, что JVM так сильно оптимизирует структуру данных чтения/записи/копирования массива. Ключевым аспектом ИМО является то, что, если ваш вектор растет до определенного размера, управление индексами становится узким местом. Здесь идет очень умный алгоритм из сохраняющегося вектора в игру, на очень больших коллекциях он превосходит стандартный вариант. Таким образом, в основном это функциональная структура данных, которая работает только так хорошо, потому что она создана на небольших изменяемых высокоэффективных структурах данных JVM. Подробнее см. Здесь (в конце) http://topsy.com/vimeo.com/28760673

Ответ 5

Растровый векторный trie (также известный как постоянный вектор) представляет собой структуру данных, изобретенную Rich Hickey для Clojure, которая была реализована в Scala с 2010 года (v 2.8). Это его умная стратегия побитовой индексации, которая позволяет высокоэффективный доступ и модификацию больших наборов данных.

От Понимание Clojure Стойкие векторы:

Взаимосвязанные векторы и ArrayLists - это обычно массивы, которые растут и при необходимости сокращается. Это отлично работает, когда вы хотите изменчивости, но это большая проблема, когда вы хотите настойчивости. Вы медленно операции модификации, потому что вам придется скопировать весь массив все время, и он будет использовать много памяти. Было бы идеально как-то избегать избыточности, насколько это возможно, без потери производительность при поиске значений, а также быстрые операции. Что это то, что делает Clojure постоянный вектор, и это делается через сбалансированные упорядоченные деревья.

Идея заключается в реализации структуры, которая похожа на двоичную дерево. Единственное отличие состоит в том, что внутренние узлы в дереве ссылка на не более двух подузлов и не содержит никаких элементов самих себя. Листовые узлы содержат не более двух элементов. Элементы находятся в порядке, что означает, что первый элемент является первым элементом в самом левом листе, а последний элемент - самый правый элемент в самый правый лист. В настоящее время мы требуем, чтобы все листовые узлы находились на ту же глубину 2. В качестве примера рассмотрим дерево ниже: оно имеет целые числа от 0 до 8 в нем, где 0 - первый элемент, а 8 последний. Число 9 - размер вектора:

Если бы мы хотели добавить новый элемент в конец этого вектора, и мы были в изменчивом мире, мы вставляем 9 в самый правый лист node, например:

Но вот проблема: мы не можем этого сделать, если хотим быть настойчивыми. И это, очевидно, не сработает, если мы хотим обновить элемент! Нам нужно будет скопировать всю структуру или, по крайней мере, ее части.

Чтобы свести к минимуму копирование при сохранении полной сохранности, мы выполняем путь Копирование: мы копируем все узлы на пути до значения, о котором мы говорим обновлять или вставлять и заменять значение новым, когда мы внизу. Результат множественных вставок показан ниже. Вот, вектор с 7 элементами разделяет структуру с вектором с 10 элементы:

Розовые цветные узлы разделяются между векторами, тогда как коричневый и синий отделены друг от друга. Другие векторы, которые не визуализируются, могут также обменивайте узлы этими векторами.

Дополнительная информация

Кроме Понимание Clojure Persistent Vectors, идеи этой структуры данных и ее варианты использования также хорошо объяснил лекцию Дэвида Нолена 2014 года Неизбежность, интерактивность и JavaScript, из которых был сделан снимок экрана ниже. Или, если вы действительно хотите глубоко погрузиться в технические детали, см. Также Phil Bagwell Идеальные деревья хэшей, который был документ, на котором основывалась инициатива на основе Hickey Clojure.

Ответ 6

Судя по названию разговора, он говорит о векторах Scala, которые даже не близки к "наиболее локально упакованным данным": см. источник в https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src/library/scala/collection/immutable/Vector.scala.

Ваше определение относится только к Lisps (насколько я знаю).