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

Question

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

Скажите вектор длины 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) может быть использована для эффективного большого количества случайных-доступов , но array/vector должен делать это тоже. Что еще более важно, большое количество изменений по-прежнему необходимо устранить изменчивой структурой, чтобы избежать репликации памяти. Есть ли в Хаскелле изменяемый массив случайных ассесов или вектор? Если используются монады 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 являются монадами, на самом деле компилятор может сделать некоторые более высокоуровневые оптимизации, которые не были бы возможны на императивном языке, хотя компиляторы еще не так далеко.

Характеристики, особенно операции с массивами, обсуждаются во многих местах, например in RWH.

Answer 2

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

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