Как получить статистику в постоянной памяти

Question

У меня есть функция, которая создает случайные числовые результаты.Я знаю, что результатом будет целое число в (малом, a - b около 50) диапазоне a, b .Я хочу создать функцию, которая выполняет вышеупомянутую функцию, скажем, 1000000 раз и вычисляет, как часто появляется каждый результат.(Функция использует генератор случайных чисел для получения результата.) Проблема в том, что я не знаю, как сделать это в постоянной памяти без жесткого кодирования длины диапазона.Мой (плохой) подход такой:

values :: [Int]
values = doFunctionNtimes myRandom 1000000
results = map (\x ->length . filter (x==) $ values) [a..b]

У кого-нибудь есть идея сделать это?

Редактировать:

Мне кажется, я неправильно объяснил проблему, извините за это,У меня есть функция, которая - в зависимости от случайного поколения - выдает небольшое значение типа int.Чтобы составить статистику, я хочу знать, как часто появляются результаты.Поскольку я хочу сделать статистику, скажем, 1000000 попыток, мне нужна постоянная память в течение количества попыток.

Answer 1

import qualified Data.Map as Map
import Data.List (foldl')          -- ' (to fix SO syntax highlighting)

histogram :: (Ord a) => [a] -> Map.Map a Int
histogram = foldl' (\m x -> Map.insertWith' (+) x 1 m) Map.empty

Объяснение того, почему это работает и почему оно превосходит решение Трэвиса Брауна, довольно техническое, и для полного понимания потребуется некоторое терпение.

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

(4, 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)

Очень неэффективное представление числа 19. Только когда вы попросите этот элемент на карте, будет вычислена гигантская сумма. Эти "thunks" (выражения отложенной оценки) будут расти линейно с размером входных данных.

Чтобы предотвратить это, мы используем insertWith', который применяет функцию строго , то есть он оценивает результат перед тем, как поместить его на карту. Итак, если вы вставите 4 в карту выше, он оценит Thunk и вы получите хорошую приборку:

(4, 20)

И еще один оценит это перед добавлением, так что вы получите:

(4, 21)

Так что теперь, по крайней мере, значения карты являются постоянным пространством.

Последнее, что нам нужно сделать, это изменить правый сгиб на левый, потому что Map.insert строг в своем втором аргументе. Следующее демонстрирует значение правой складки.

iw x m = Map.insertWith' (+) x 1 m    -- '

foldr iw Map.empty [1,2,1,3,2,1]
    = iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 Map.empty)))))

Использование iw в качестве простого сокращения. Map.insert строгость второго аргумента означает, что вам нужно оценить карту, в которую вы вставляете, прежде чем вставка сможет выполнить какую-либо работу. Я буду использовать обозначение { k1 -> v1, k2 -> v2, ... } как сокращение для карт. Ваша последовательность оценки выглядит следующим образом:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldr iw {} [1,2,1,3,2,1]
iw 1 (foldr iw {} [2,1,3,2,1])
iw 1 (iw 2 (foldr iw {} [1,3,2,1]))
iw 1 (iw 2 (iw 1 (foldr iw {} [3,2,1])))
iw 1 (iw 2 (iw 1 (iw 3 (foldr iw {} [2,1]))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (foldr iw {} [1])))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 (foldr iw {} []))))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 {}))))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 {1 -> 1}))))
iw 1 (iw 2 (iw 1 (iw 3 {1 -> 1, 2 -> 1})))
iw 1 (iw 2 (iw 1 {1 -> 1, 2 -> 1, 3 -> 1}))
iw 1 (iw 2 {1 -> 2, 2 -> 1, 3 -> 1})
iw 1 {1 -> 2, 2 -> 2, 3 -> 1}
{1 -> 3, 2 -> 2, 3 -> 1}

Итак, если у вас есть массив из 1 000 000 элементов, нам нужно пройти весь процесс до 1 000 000 элементов, чтобы начать вставку, поэтому нам нужно сохранить в памяти предыдущие 999 999 элементов, чтобы мы знали, что делать дальше. Левый сгиб решает это:

-- definition of left fold
foldl' f z xs = go z xs             -- '
    where 
    go accum [] = z
    go accum (x:xs) = accum `seq` go (f accum x) xs

foldl' (flip iw) Map.empty [1,2,1,3,2,1]  -- needed to flip arg order to appease foldl'
go {} [1,2,1,3,2,1]
go (iw 1 {}) [2,1,3,2,1]
go (iw 2 {1 -> 1}) [1,3,2,1]
go (iw 1 {1 -> 1, 2 -> 1}) [3,2,1]
go (iw 3 {1 -> 2, 2 -> 1}) [2,1]
go (iw 2 {1 -> 2, 2 -> 1, 3 -> 1}) [1]
go (iw 1 {1 -> 2, 2 -> 2, 3 -> 1}) []
iw 1 {1 -> 2, 2 -> 2, 3 -> 1}
{1 -> 3, 2 -> 2, 3 -> 1}

Теперь мы можем видеть, что, наконец, если количество записей на карте ограничено, то это выполняется в постоянном пространстве и линейном времени.

Answer 2

Способ, которым я обычно решаю эту проблему, состоит в том, чтобы отслеживать количество на карте.Data.IntMap работает в этом случае:

import qualified Data.IntMap as I

results :: [Int] -> I.IntMap Int
results = foldr (\x -> I.insertWith (+) x 1) I.empty

В этот момент вы можете запросить конечные точки диапазона (I.findMin и I.findMax) или посмотреть счетчик на определенное значение в O (войти n).Кроме того, очень просто поместить все в массив для более быстрого поиска.

---

ОБНОВЛЕНИЕ: См. ответ luqui , где приведена гораздо лучшая версия этого кода.

Answer 3

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

Answer 4

Как уже упоминал Джоуни, постоянная память невозможна, но этот скетч-минус напоминает бомбу!(хотя я не слышал об этом раньше).Но я думаю, что вы, возможно, спросили, это возможность хранить это в одном массиве и обновлять только каждую частоту.Это можно сделать в haskell с изменяемыми массивами.Вот пример:

main = do gen <- newStdGen
          n <- liftM (read . head) getArgs
          arr  <- (newArray (a,b) 0) :: IO (IOUArray Int Int)
          replicateM_ n $ do 
               result <- myRand
               x <- readArray arr result
               writeArray arr result (x+1)
          (getAssocs arr :: IO [(Int,Int)]) >>= print

Запустив программу с + RTS -s и введя 1000000, мы получим вывод

787,874,256 bytes allocated in the heap
         364,536 bytes copied during GC
           5,984 bytes maximum residency (1 sample(s))
          17,928 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

...
  Total time    0.29s  (  0.30s elapsed)
...
  %GC time       0.3%  (2.1% elapsed)