Немонолитные массивы в Haskell

Я принял ответ на вопрос ниже, но, похоже, я не понял, как работают массивы в haskell. Я думал, что они были просто усиленными списками. Помните об этом при чтении вопроса ниже.

Я обнаружил, что монолитные массивы в haskell довольно неэффективны при использовании их для больших массивов.

Мне не удалось найти немонолитную реализацию массивов в haskell. Мне нужно, чтобы O (1) время просматривало многомерный массив.

Есть ли реализация массивов, которые поддерживают это?

EDIT: Я, кажется, неправильно понял термин монолит. Проблема в том, что, похоже, массивы в haskell обрабатывают массив, подобный списку. Возможно, я ошибаюсь.

EDIT2: Краткий пример неэффективного кода:

fibArray n = a where
  bnds = (0,n)
  a = array bnds [ (i, f i) | i <- range bnds ]
  f 0 = 0
  f 1 = 1
  f i = a!(i-1) + a!(i-2)

это массив длины n+1, где i-е поле содержит i-е число фибоначчи. Но поскольку массивы в haskell имеют время поиска O (n), для вычисления требуется время O (n²).

Ответы

Ответ 1

Массивы имеют O (1) индексацию. Проблема в том, что каждый элемент вычисляется лениво. Так вот что происходит, когда вы запускаете это в ghci:

*Main> :set +s
*Main> let t = 100000
(0.00 secs, 556576 bytes)
*Main> let a = fibArray t
Loading package array-0.4.0.0 ... linking ... done.
(0.01 secs, 1033640 bytes)
*Main> a!t  -- result omitted
(1.51 secs, 570473504 bytes)
*Main> a!t  -- result omitted
(0.17 secs, 17954296 bytes)
*Main>

Обратите внимание, что поиск выполняется очень быстро, после он уже просматривается один раз. Функция array создает массив указателей на thunks, которые в конечном итоге будут вычислены для получения значения. В первый раз, когда вы оцениваете стоимость, вы оплачиваете эту стоимость. Вот первые несколько расширений thunk для оценки a!t:

a!t -> a!(t-1)+a!(t-2)-> a!(t-2)+a!(t-3)+a!(t-2) -> a!(t-3)+a!(t-4)+a!(t-3)+a!(t-2)

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

Я попытался скрыть значения в списке, переданном в array, но это, казалось, привело к бесконечному циклу.

Общим для этого является использование изменяемого массива, такого как STArray. Элементы могут обновляться, поскольку они доступны во время создания массива, а конечный результат заморожен и возвращен. В векторном пакете функции create и constructN предоставляют простые способы сделать это.

-- constructN :: Unbox a => Int -> (Vector a -> a) -> Vector a


import qualified Data.Vector.Unboxed as V
import Data.Int

fibVec :: Int -> V.Vector Int64
fibVec n = V.constructN (n+1) c
 where
  c v | V.length v == 0 = 0 
  c v | V.length v == 1 = 1 
  c v | V.length v == 2 = 1
  c v = let len = V.length v
        in v V.! (len-1) + v V.! (len-2)

НО, функция fibVec работает только с незанятыми векторами. Регулярные векторы (и массивы) недостаточно строгие, что приводит к той же проблеме, которую вы уже нашли. И, к сожалению, для Integer нет экземпляра Unboxed, поэтому, если вам нужны неограниченные целые типы (этот fibVec уже переполнен в этом тесте), вы застряли в создании изменяемого массива в IO или ST чтобы обеспечить необходимую строгость.

Ответ 2

Вы смешиваете связанные списки в Haskell с массивами.

Связанные списки - это типы данных, которые используют следующий синтаксис:

[1,2,3,5]

определяется как:

data [a] = [] | a : [a]

Это классические рекурсивные типы данных, поддерживающие индексирование O (n) и добавление O (1).

Если вы ищете многомерные данные с поиском O (1), вместо этого вы должны использовать истинную структуру массива или матрицы. Хорошими кандидатами являются:

  • Repa - быстрые, параллельные, многомерные массивы - (Tutorial)
  • Vector - Эффективная реализация массивов Int-indexed (как изменчивых, так и неизменяемых) с мощной схемой оптимизации цикла. (Tutorial)
  • HMatrix - Чисто функциональный интерфейс к базовой линейной алгебре и другим численным вычислениям, внутренне реализованный с использованием GSL, BLAS и LAPACK.

Ответ 3

Обращаясь конкретно к вашему примеру fibArray, попробуйте это и посмотрите, немного ли это ускорится:

-- gradually calculate m-th item in steps of k
--     to prevent Qaru , etc
gradualth m k arr                         
    | m <= v = pre `seq` arr!m   
  where                                   
    pre = foldl1 (\a b-> a `seq` arr!b) [u,u+k..m]
    (u,v) = bounds arr

Для меня, для let a=fibArray 50000, gradualth 50000 10 a запускается в промежутке времени 0,65, просто вызывая a!50000.