OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 21:37

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5
Автор Сообщение
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 21:46 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Alexey Veselovsky писал(а):
Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.


Я-то думал, и правда так. Проверил. Алексей, что-то Вы путаете.

Возможно и путаю. Во-первых я немного по другому заводил массив. Тип указателя был POINTER TO ARRAY OF INTEGER (т.е. открытый как бы массив). Ну и создавался новый массив просто:
NEW(Arr, 10000000);

Отслеживал изменения в таскмане виндовозном.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 21:49 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
У ББ замашки ОС, он может и хапнуть сразу с большим запасом (ну и не отдаёт). Чтобы отдавал, нужно Kernel.dllMem = TRUE. В линуксовой версии оно так и стоит, режима со страничным получением памяти от ОС нет, используется libc.malloc-free.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 21:57 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
У ББ замашки ОС, он может и хапнуть сразу с большим запасом (ну и не отдаёт). Чтобы отдавал, нужно Kernel.dllMem = TRUE. В линуксовой версии оно так и стоит, режима со страничным получением памяти от ОС нет, используется libc.malloc-free.


Да, похоже на то что он хапал лишку. Ибо, помню я странности что значение оверхэда у него плавало. То на 16 мег больше, то на 30 то вообще на 5...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 22:23 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Algo писал(а):
Получается, что программист должен
1) обязательно знать про указанную особенность компилятора
При чём здесь компилятор? Это такая же проблема, как и наивный алгоритм Фибоначчи с экспоненциальным временем работы. Думаете, обероны превратят тут постую рекурсию в составную? Да даже если бы могли -- не стали бы делать, ибо таков принцип оберонов: "Не будь умнее программиста"...

Algo писал(а):
Очень, очень просто!
Как не сделать ошибку? Просто нужно всё знать и понимать и не делать ошибок!

Прокол это, локальный, но прокол. И это надо признать.

Да, верно, это же и у оберонщиков любимая тема -- правильное проектирование спасёт мир!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Среда, 08 Июль, 2009 22:28 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Господа, прошу не превращать тему в холивор на общие темы "ни о чем". Думаю у меня ещё найдется достаточно глупых технических вопросов по хаскелю. Хотелось бы это всё собрать в более-менее одной теме или группе тем.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Четверг, 09 Июль, 2009 09:14 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Целые числа Int в GHC хранять в себе не только само число, но и доп. служебную информацию (ну как в той же яве информация об объекте). Однако есть unboxed-типы, например Int#, которые не содержат такой информации. Однако такие типы нельзя использовать совместно с полиморфными типами вроде списков. Там же на ru_lambde посоветовали попробовать так:
Код:
{-# LANGUAGE MagicHash #-}

module Main where

import qualified Prelude as P
import Prelude (undefined, seq, print, ($), (+))
import GHC.Prim
import GHC.Types
import Data.List (foldl')

data IntList = Nil | Cons Int# !IntList

fromList = foldl' (\xs (I# x) -> Cons x xs) Nil

foldl _ a Nil = a
foldl f a (Cons x xs) = let a' = f a x in seq a' $ foldl f a' xs

length = foldl (\r _ -> r+1) 0
last   = foldl (\_ x -> I# x) undefined

xs :: IntList
xs = fromList [1..10000000]

main = do
    print $ length xs
    print $ last   xs
Объём занимаемой программой памяти уменьшился до 182 МБт (т.е. на стандартный boxed-тип Int приходилось как минимум по 8 байт доп. информации на каждое число), но, правда, время работы программы увеличилось в несколько раз...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Четверг, 09 Июль, 2009 09:25 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Кстати, а попробуйте забить оный список случайными числами. Посмотрим, сумеет ли он это оптимизировать/пожать.
Таки попробовал:
Код:
module Lists

import StdInt, StdEnum, MersenneTwister
   
xs :: [Int]
xs = take 100000000 (genRandInt 12345)

take :: !Int [a] -> [a]
take 0 _      = []
take _ []     = []
take n [x:xs] = [x : take (n-1) xs]

length2 :: [a] -> Int
length2 xs = len xs 0
  where
    len :: [a] !Int -> Int
    len []     n = n
    len [_:ys] n = len ys (n+1)

last :: [a] -> a
last [x]    = x
last [x:xs] = last xs

Start::(Int, Int)
Start = (length2 xs, last xs)
Опять на 100 млн чисел было потрачено 100 МБт. Непонятно...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Четверг, 09 Июль, 2009 10:27 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Geniepro писал(а):
Опять на 100 млн чисел было потрачено 100 МБт. Непонятно...

Ну вот, я же в настройках проекта указал минимальный размер кучи 100 МБт. :lol:
Указал кучу от 1 Мбт и стек 100 кБт -- программа отработала в полутора мегабайтах...
Но тут уже какая-то непонятность -- что мешало кешировать список? Зачем его вычислять два раза?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Четверг, 09 Июль, 2009 10:47 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Думаю у меня ещё найдется достаточно глупых технических вопросов по хаскелю.
Кстати, а вы таки поройтесь в этом Clean, его компилятор выдаёт довольно вразумительный ассемблерный листинг.
Код:
fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)
Код:
s2
   eqI_b 1 0
   jmp_true case.1
   eqI_b 2 0
   jmp_true case.2
   jmp case.3
case.1
   pop_b 1
   pushI 1
.d 0 1 i
   rtn
case.2
   pop_b 1
   pushI 1
.d 0 1 i
   rtn
case.3
   pushI 2
   push_b 1
   subI
.d 0 1 i
   jsr s2
.o 0 1 i
   pushI 1
   push_b 2
   subI
.d 0 1 i
   jsr s2
.o 0 1 i
   update_b 1 2
   updatepop_b 0 1
   addI
.d 0 1 i
   rtn
Если я не ошибаюсь, это стековая машина типа CLR или JVM...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Пятница, 10 Июль, 2009 19:39 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
та-акс, появился ещё один вопрос. не очень приятный ;-)
Код:
lst = [1..]
main = print $ length lst


Вообще говоря лично я ожидал что мне вернут или _|_, или кинут исключением, или вообще какой-нибудь инфинум вернут (что было бы лучше всего), однако вместо этого программа просто тупо зациклилась.

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

А то как бы декларируется что хаскель умеет работать с бесконечными циклами, однако вон оно что выходит... Неприятно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Пятница, 10 Июль, 2009 22:29 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Вообще говоря лично я ожидал что мне вернут или _|_, или кинут исключением, или вообще какой-нибудь инфинум вернут (что было бы лучше всего), однако вместо этого программа просто тупо зациклилась.

Хаскелл -- это не теорем-прувер, так что заказали Вы ему программу -- вот он и пытался её выполнить.
Кстати, в ряде случаев GHC обнаруживает зацикливание:
Код:
a = b :: Int
b = a

main = do
    print a
Но, похоже, на бесконечные списки это не распространяется...

Alexey Veselovsky писал(а):
Вопрос -- есть ряд алгоритмов которым бесконечные списки явно противопоказаны, можно ли как-то сказать чтобы нам слали лишь конечные списки? Ну, или на худой конец, как-то эти самые бесконечные списки обнаруживать?
Тут уже требуется тотальное ФП, в котором все функции являются полностью определёнными. Хаскелл не относится к тотальным ФЯ.
viewtopic.php?p=31188#p31188
Там все данные (data) являются конечными, а коданные (codata) -- потенциально бесконечными. Данные и коданные имеют разные типы, так что компилятор может проследить за правильностью их использования.
Так же есть рекурсии (которые всегда конечны) и корекурсии (потенциально бесконечные).
Почитайте статью Тёрнера "Total Functional Programming"


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB