Растущие массивы в Хаскеле

Question

У меня есть следующий (обязательный) алгоритм, который я хочу реализовать в Haskell:

При заданной последовательности пар [(e0, s0), (e1, s1), (e2, s2) ,..., (en, sn)], где части "e" и "s" являются натуральными числами, которые не обязательно различаются, на каждом временном шаге один элемент этой последовательности выбирается случайным образом, скажем (ei, si), и основан нав значениях (ei, si) новый элемент создается и добавляется в последовательность.

Как я могу эффективно реализовать это в Haskell?Насколько мне известно, необходимость в произвольном доступе сделала бы это плохим для списков, в то время как необходимость добавления одного элемента за раз сделала бы его плохим для массивов.

Заранее спасибо.

Answer 1

Я предлагаю использовать Data.Set или Data.Sequence, в зависимости от того, для чего он вам нужен. Последний, в частности, предоставляет вам поиск по логарифмическому индексу (в отличие от линейного для списков) и добавление O (1) с обеих сторон.

Answer 2

"в то время как необходимость добавления одного элемента за раз могла бы ухудшить работу массивов" С алгоритмической точки зрения кажется, что вам нужен динамический массив (вектор, список массивов и т. Д.), Который амортизирует O (1) раз добавить элемент. Я не знаю, как она реализована на Haskell, и это не очень «функциональная» структура данных, но определенно возможно реализовать ее на Haskell в какой-то монаде состояния.

Answer 3

Если вам действительно нужно изменить размер при останове и начать, вы можете подумать об использовании пакета simple-веревка вместе с экземпляром StringLike для чего-то вроде Vector.В частности, это может соответствовать сценариям, когда вы начинаете с большого массива и заинтересованы в сравнительно небольших дополнениях.

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

Если вы можете построить свой массив за один раз и просто нуждаетесь в индексированииВы описываете, что-то вроде следующего может быть достаточно,

import Data.Array.IArray

test :: Array Int (Int,Int)
test = accumArray (flip const) (0,0) (0,20) [(i, f i) | i <- [0..19]]
  where f 0 = (1,0)
        f i = let (e,s) = test ! (i `div` 2) in (e*2,s+1)

Answer 4

Если вы знаете приблизительное количество элементов, которое вам понадобится, вы можете создать массив такого размера, который сначала будет «разреженным», а затем при необходимости вы можете поместить в него элементы.Для представления этого нового массива можно использовать что-то похожее на приведенное ниже:

data MyArray = MyArray (Array Int Int) Int

(где последние значения Int представляют количество элементов, используемых в массиве)

Answer 5

Делая заметку от ivanm, я думаю, что подходы - это путь для этого.

import Data.Set as Set
import System.Random (RandomGen, getStdGen)

startSet :: Set (Int, Int)
startSet = Set.fromList [(1,2), (3,4)] -- etc. Whatever the initial set is

-- grow the set by randomly producing "n" elements.
growSet :: (RandomGen g) => g -> Set (Int, Int) -> Int -> (Set (Int, Int), g)
growSet g s n | n <= 0    = (s, g)
              | otherwise = growSet g'' s' (n-1)
    where s' = Set.insert (x,y) s
          ((x,_), g')  = randElem s g
          ((_,y), g'') = randElem s g'

randElem :: (RandomGen g) => Set a -> g -> (a, g)
randElem = undefined

main = do
    g <- getStdGen
    let (grownSet,_) = growSet g startSet 2
    print $ grownSet -- or whatever you want to do with it

Это предполагает, что randElem - эффективный, определяемый метод для выбора случайного элемента из набора.(Я задал этот SO вопрос относительно эффективных реализаций такого метода).При написании этой реализации я понял, что она может не соответствовать вашим потребностям, поскольку Set s не может содержать повторяющиеся элементы, и мой алгоритм не может придать дополнительный вес парам, которые появляются в списке несколько раз.