[haskell] расход памяти.

Код покажи.

при этом функциональное решение на хаскеле рвало в хвост и гриву императивное решение, где юзался BigInteger.

А не пробовал ручками заленивить на C# последовательность? Или LINQ использовать?

Указал бы какое упраднение из скипа и привёл бы свой код.

пробовал. сначала на Эф-шарпе заюзал Seq. - жукткий тормоз. догадался закешировать - немного помоголов, но не айс.

и только потом нашел в книге, что существует понятие LazyList в F#-пе, скачал либу PowerPack и это помогло.

но шарп сливает не из-за императивности(тут наоборот нет лишних аллокаций) а из-за BigInteger-а(а тут уже аллокации появляются)

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

вот код: [code] module Main (main) where

import System.Environment

merge [] s2 = s2 merge s1 [] = s1 merge (s1:s1s) (s2:s2s) | s1 < s2 = s1 : (merge s1s (s2:s2s))                   | s1 > s2 = s2 : (merge (s1:s1s) s2s)                   | otherwise = s1 : (merge s1s s2s)

scaleStreams scale = map $ (*) scale       

getNum n = s_3_56!!n    where s_3_56 = 1:(merge (scaleStreams 2 s_3_56)           (merge (scaleStreams 3 s_3_56)        (scaleStreams 5 s_3_56 )))

main = do    snum:_ <- getArgs    putStrLn $ show $ getNum (read snum) [/code] упражнение 3_56

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

вот код:

 module Main (main) where

import System.Environment

merge [] s2 = s2 merge s1 [] = s1 merge (s1:s1s) (s2:s2s) | s1 < s2 = s1 : (merge s1s (s2:s2s))                   | s1 > s2 = s2 : (merge (s1:s1s) s2s)                   | otherwise = s1 : (merge s1s s2s)

scaleStreams scale = map $ (*) scale       

getNum n = s_3_56!!n    where s_3_56 = 1:(merge (scaleStreams 2 s_3_56)           (merge (scaleStreams 3 s_3_56)        (scaleStreams 5 s_3_56 )))

main = do    snum:_ <- getArgs    putStrLn $ show $ getNum (read snum) 

че-то с форматированием не то :)))))

скопируйте код в редактора для читабельности.

но меня не данная задача интересует, а почему сборщик мусора не чистит элементы, когда я указываю примитивный тип.

> но шарп сливает не из-за императивности(тут наоборот нет лишних аллокаций) а из-за BigInteger-а(а тут уже аллокации появляются)

Постановку задачи приведи и то, что ты хочешь получить.

я же номер упражнения привел. и повторю, мне сейчас пох на си_шарп и его БигИнт. мне интересно как работать с большими списками Int64 в Хаскеле.

на си_шарп забейте. да и на задачу. это не главное.

> на си_шарп забейте. да и на задачу. это не главное.

Меня интересует то, что на F# это тормозило, сейчас гляну что там. Можешь свой F# код кинуь?

тебе самую быструю версию? ее я на биг_интах не тестил. тормозила версия на Seq и Cached Seq. меньше тормозит на ленивых_списках, но я его на большие выборки не тестил, мне нужно найти 100_000_000-е число, а я подозреваю что и в эф-шарпе сборщик мусора не сприваться. хоят надо проверить.

з.ы. у меня очень мало оперативки.

на хаскеле влазит 10_000_000-й список (примитивных типов), а произвольной длины вроде 1000_000, но уже не помню.

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

Кидай все версии.

протестил эф-шарп на ленивых_списках. показует херовую производительность даже на примитивных типах(если туда добавить БигИнт, то никогда не посчитает 100_000_000-й элемент)

я вон на инте не могу дождаться 10_000_000-го.

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

вот код:

let rec lazy_merge s1 s2 =
    match (s1, s2) with
    | (LazyList.Nil, _) -> s2
    | (_, LazyList.Nil) -> s1
    | (LazyList.Cons(h1,t1),
       LazyList.Cons(h2,t2)) -> if      h1 < h2 then LazyList.consDelayed h1 (fun () -> (lazy_merge t1 s2))
                                else if h1 > h2 then LazyList.consDelayed h2 (fun () -> (lazy_merge s1 t2))
                                else                 LazyList.consDelayed h1 (fun () -> (lazy_merge t1 t2)) 

let lazy_scaleStreams scale = LazyList.map <| (*) scale

let getNum n=
    let rec lazy_series = 
                   LazyList.consDelayed 1
                                        (fun () -> (lazy_scaleStreams 2 lazy_series)
                                                        |> lazy_merge (lazy_scaleStreams 3 lazy_series)
                                                        |> lazy_merge (lazy_scaleStreams 5 lazy_series))
    lazy_series
        |>LazyList.skip n
        |> LazyList.head

ок.

кину c кешом. кеширование сам убереш и убедишься что еще в разы хуже станет.

let rec merge s1 s2 =
    match (s1, s2) with
    | ([], _)          -> s2
    | (_, [])          -> s1
    | (h1::t1, h2::t2) -> if      h1 < h2 then h1 :: (merge t1 s2)
                          else if h1 > h2 then h2 :: (merge s1 t2)
                          else                 h1 :: (merge t1 t2)

let rec seq_merge s1 s2 = Seq.cache <|
    if Seq.isEmpty s1 
        then s2
    else if Seq.isEmpty s2 
        then s1
    else   
        let h1 = Seq.head   s1
        let t1 = Seq.skip 1 s1
        let h2 = Seq.head   s2
        let t2 = Seq.skip 1 s2
        seq {
                if      h1 < h2 then yield  h1
                                     yield! (seq_merge t1 s2)
                else if h1 > h2 then yield  h2 
                                     yield! (seq_merge s1 t2)
                else                 yield  h1
                                     yield! (seq_merge t1 t2)
            }

let scaleStreams scale stream = Seq.map ((*) scale) stream

let rec series = Seq.cache <|
    seq {
            yield 1
            yield! scaleStreams 2 series
                      |> seq_merge (scaleStreams 3 series)
                      |> seq_merge (scaleStreams 5 series)
        } 

дак че, нету на лоре хаскелистов? а кто тогда вечно лисперов троллит?

> дак че, нету на лоре хаскелистов? а кто тогда вечно лисперов троллит?

Зануду жди, но он обычно вечером появляется.

а какой у него ник? а то я не местный.

http://www.linux.org.ru/people/sanuda/profile

спасибо

что-то я не понял вопроса

Во-первых, что Int, что Int64, что Integer представлены в памяти одинаково — указателями на объект в куче. Так что разницы толком и нет.

Во-вторых, программа что с Int64, что с Integer потребляет больше памяти. С Int64 она просто делает это быстрее, ибо арифметика быстрее.

задай этот вопрос на stackoverflow, там Дон Стюарт быстро тебе ответит

окэй, почему с Integer - ответ находит, памяти не ест. с инт64 - работает быстрее, но памяти для 100_000_000-го элемента у меня не хватает.

мне очень стыдно, но у меня очень плохой аглицкий :(((((( если кто поможет - полюс в карму :)))))

>что-то я не понял вопроса

когда я ищу n-й элемент послдеовательности типа Integer, то сборщик мусора подчищает памяить и ее хватает.

когда я запускаю этот же код, но специализировал тип как Int64, то сборщик мусора не собирает ненужные элементы и памяти не хватает.

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

Ест он с Integer память. Я в top смотрю и вижу как память разрастается. Сделай heap profiling.

http://book.realworldhaskell.org/read/profiling-and-optimization.html

оне ее подчищает и программа рабоате в рамках 400-600 метров, а если ставлю Int64, съедает больше гектара и виснит.

KyZ

>задай этот вопрос на stackoverflow, там Дон Стюарт быстро тебе ответит

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

на сто процентов не уверен, но похоже на правду. а как вы думаете?

Int64 ест в два раза больше, чем Int32.

600 Мб × 2 = (больше гектара и виснет)

да, проблема была из-за переполнения. а я тупица и не догадался.

а причем здесь Int32? я юзал Integer - произвольной длинны. но уже балгодаря челу со стек_оверфлов броблема найдена. я заблуждался что это из-за оптимизаций.

ну с проблемой мы разобрались.

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

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

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

а посоветуйте быструю библиотеку для длинной арифметики для сей. думаю сейчас прожку написать что-бы хацкель сделала.