LINUX.ORG.RU

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

 


0

1

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

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

но у меня возник вопрос, а если бы значения не выходили за предел Int64 или Double, какое было бы соотношение производительности хаскеля и си_шарпа. и несмотря на переполнение, я решил потестить прогу для Int64, и видимо в силу каких-то оптимизаций, сборщик мусора перестал очищать память от прошлых элементов, и мне не хватает оперативы.

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


Код покажи.

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

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

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

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

kyz
() автор топика
Ответ на: комментарий от Begemoth

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

вот код: [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

kyz
() автор топика
Ответ на: комментарий от Begemoth

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

вот код:

 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) 
упражнение 3_56

kyz
() автор топика
Ответ на: комментарий от kyz

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

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

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

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

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

kyz
() автор топика
Ответ на: комментарий от Norgat

протестил эф-шарп на ленивых_списках. показует херовую производительность даже на примитивных типах(если туда добавить БигИнт, то никогда не посчитает 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


kyz
() автор топика
Ответ на: комментарий от Norgat

ок.

кину 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)
        } 

kyz
() автор топика

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

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

Norgat ★★★★★
()
Ответ на: комментарий от kyz

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

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

Shimuuar
()
Ответ на: комментарий от Shimuuar

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

kyz
() автор топика
Ответ на: комментарий от anonymous

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

kyz
() автор топика
Ответ на: комментарий от Waterlaz

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

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

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

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

kyz
() автор топика
Ответ на: комментарий от anonymous

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

KyZ

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

kyz
() автор топика
Ответ на: комментарий от anonymous

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

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

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

kyz
() автор топика
Ответ на: комментарий от kyz

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

kyz
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.