Разреженные массивы в Хаскеле?

Question

Существует ли какой-либо стандартный или «самый обычный» способ представления многомерных разреженных массивов в Haskell (без слишком большой потери производительности)?

Что-то вроде map > в C ++, например. Я гуглил и нашел только несколько старых научных работ и других людей, которые тоже просили об этом.

Спасибо!

Answer 1

Data.Map (Int,Int) MyClass - отличное предложение; попробуйте сначала.

Если у вас возникнут проблемы с космосом, попробуйте IntMap (IntMap MyClass). IntMap с (в модуле Data.IntMap) - Map с с Int с в качестве ключей; будучи специализированными, они более эффективны, чем общие карты. Это может иметь или не иметь существенного значения.

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

Answer 2

Как насчет Data.Map (Int,Int) MyClass?

Answer 3

Есть HsJudy , который, похоже, хорошо приспособлен для разреженных наборов ключей.

Связи Джуди (библиотека C, которая реализует быстрые разреженные динамические массивы) для Haskell, представляющего API, максимально соответствующие существующим интерфейсам библиотеки Haskell, таким как Data.Map и Data.Array.MArray. Эта привязка для библиотеки Judy включает в себя все ее четыре типа: отображение из слов в биты (Judy1), из слов в значения (JudyL), из строк в значения (JudyHS) и из массива байтов в значения (JudyHS).

Но я бы, вероятно, пошел с Data.Map.Map (Int, Int) MyClass, пока не столкнулся с проблемами масштабируемости или удобства использования.

Answer 4

Ничего не вижу, это бесплатно, но есть это:

Разреженные матричные представления на функциональном языке

и это:

Исследование разреженных матричных представлений для решения линейных систем на функциональном языке

Answer 5

Я нашел эту короткую суть , которая показывает хранилище сжатых строк для Haskell и соответствующее умножение матрицы на вектор:

import Data.Vector.Unboxed as U

-- | A compressed row storage (CRS) sparse matrix.
data CRS a = CRS {
      crsValues :: Vector a
    , colIndices :: Vector Int
    , rowIndices :: Vector Int
    } deriving (Show)

multiplyMV :: CRS Double -> Vector Double -> Vector Double
multiplyMV CRS{..} x = generate (U.length x) outer
  where outer i = U.sum . U.map inner $ U.enumFromN start (end-start)
          where inner j = (crsValues ! j) * (x ! (colIndices ! j))
                start   = rowIndices ! i
                end     = rowIndices ! (i+1)
                (!) a b = unsafeIndex a b