Изменяемый массив / вектор произвольного доступа с высокой производительностью в haskell

Question

Эта тема на Haskell обсуждалась много раз (например, реализация mutable-array), но я до сих пор не уверен, что является лучшей практикой для случая, требующего частой модификации и произвольного доступа к массиву / вектору.

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

type Vect = [Int]

f :: Vect -> [[Int]] -> Vect
f x indsList = foldl g x indsList

-- g is just an example of random-access and modifications on the values.
g :: Vect -> [Int] -> Vect
g x inds = map h $ zip x [0..]
    where h (x, i) = if i `elem` inds then x !! i + 1 else x !! i

Структура данных хэша / карты (например, IntMap) может использоваться для эффективного большого количества случайных обращений, но массив / вектор должен это делать. Что еще более важно, большое количество модификаций все еще должно быть обращено изменяемой структурой, чтобы избежать репликации памяти. Есть ли в Haskell изменяемый массив случайных массивов / векторов? Если используются монады ST/IO, влияют ли такие элементы управления на производительность в моих настройках?

Answer 1

У Haskell есть эффективные изменяемые массивы.

• Есть STUArray, который имеет довольно сложный, но часто просто ненужный Ix -индексирование методологии с множеством проверок границ и небольшой специальной оптимизацией, что делает ее немного медленнее, чем теоретически возможно.

• Все Data.Vector не требуют больших накладных расходов, активно используют оптимизацию объединения потоков, предпочитают простой интерфейс типа "список". Это означает, что вы можете очень легко перенести свой пример непосредственно в неизменяемые векторы и, возможно, получить лучшую производительность, чем вы ожидаете:

  import Data.Vector.Unboxed as VU
  
  type Vect = VU.Vector Int
  
  f :: Vect -> [[Int]] -> Vect
  f x indsList = VU.foldl g x indsList
  
  
  g :: Vect -> [Int] -> Vect
  g x inds = VU.zipWith h x [0..]
      -- h is just an example of modifications on the values.
      where h x i
             | i`elem`inds   = x VU.! i + 1
             | otherwise     = x VU.! i
  

Да, вы, вероятно, хотите работать в ST монада для изменяемых обновлений. Не уверен, что вы подразумеваете под "влияют ли такие элементы управления на производительность": на самом деле нет никакого "элемента управления", которого также нет в императивных языках, когда компилятор оптимизировал проверенную безопасность типов. Какой GHC может сделать довольно хорошо; Вы можете получить довольно близко к производительности C с Data.Vector.Unboxed, Всегда есть некоторые неизбежные накладные расходы, но это в основном связано с проблемами сбора мусора и т. Д., Которые вы также получите в Java.

поскольку ST а также IO Будучи монадами, компилятор может на самом деле выполнять более высокоуровневую оптимизацию, которая была бы невозможна в императивном языке, хотя компилятор еще не так далеко.

Производительность, особенно операций с массивами, обсуждается во многих местах, например в RWH.

Answer 2

Иностранные UArrays от Yarr являются изменяемыми, произвольным доступом и максимально быстрыми. Также они "быстрые и грязные", то есть не навязывают замораживание / оттаивание для каждой операции мутации.

Недостаток: почти все операции "низкого уровня" находятся под IO,