OberonCore
https://forum.oberoncore.ru/

Haskell подсчитать длину списка.
https://forum.oberoncore.ru/viewtopic.php?f=72&t=1707		 Страница 4 из 5
Автор:  Algo [ Среда, 08 Июль, 2009 15:47 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
Ну, этта... Я не знаю какую чёрную магию использует gcc и msvc, но в плюсах std::vector<int> vec(10000000) -- отжирает ровно 38 мегабайт ОЗУ, как ему и положено.

Если мне неизменяют мои слабые познания С++, внутреннее представление std::vector<...> - массив, а не список, от сюда и результат.
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 15:51 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Algo писал(а):
Alexey Veselovsky писал(а):
Ну, этта... Я не знаю какую чёрную магию использует gcc и msvc, но в плюсах std::vector<int> vec(10000000) -- отжирает ровно 38 мегабайт ОЗУ, как ему и положено.

Если мне неизменяют мои слабые познания С++, внутреннее представление std::vector<...> - массив, а не список, от сюда и результат.


Дык про массивы и шла речь:
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...
Автор:  Geniepro [ Среда, 08 Июль, 2009 17:46 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
В ghc видимо аналогично. И тут всплывает целесообразность использования в качестве внутренней структуры данных для последовательностей, именно списков...

Ну опять же, как я Вам уже отмечал, никто Вас не вынуждает ограничиваться только списками...
Код:
import Data.Array.Unboxed

arr :: UArray Int Int
arr = listArray (1, 10000000) [1..]

main = do
    print $ arr ! 9999999

    putChar =<< getChar
82 МБ в памяти. Тип Int на самом деле, похоже хранится как указатель на значение в куче, поэтому массив занимает не 40 МБт, а 80...
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 17:52 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
ну, ёлки палки, список, который [] -- встроен в язык. им удобней всего пользоваться. Причем я уверен что по сути списком оно не обязано быть ни разу. Покурю доки, попробую обосновать.
Автор:  Geniepro [ Среда, 08 Июль, 2009 18:04 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
Вот моё:
Что-то я недопонял -- Ваш список не содержит в себе значения, а только ссылку на следующий элемент -- почему на него тратится столько же памяти, как и на мой?
Автор:  Geniepro [ Среда, 08 Июль, 2009 18:07 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...
Речь, вероятно, о том, что при огромных массивах всё равно будут промахи в кеше и переключения контекстов всяких в ОС...
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 18:12 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Alexey Veselovsky писал(а):
Вот моё:
Что-то я недопонял -- Ваш список не содержит в себе значения, а только ссылку на следующий элемент -- почему на него тратится столько же памяти, как и на мой?

Аа! Это видимо потому же почему и в плюсах -- стандартный аллокатор аллоцирует минимум 8 байт под элемент. Т.о. у нас получается место зарезервировано для себя и ещё для вон того парня, которого на самом деле нет.

Возможно в BB используется ещё более крупный кусок по умолчанию. Mожно поэкспериментировать ;-)
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 18:12 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...
Речь, вероятно, о том, что при огромных массивах всё равно будут промахи в кеше и переключения контекстов всяких в ОС...


А толку? Это же ж не влияет на размер массива. А про быстродействие тут никто и не говорил. Только про размер. Про память.
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 18:36 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Geniepro писал(а):
Вот ещё бы заставить его реально создавать в памяти список, а то он его оптимизирует и память вообще от размера списка не зависит.

Наврал. Список в памяти создаётся, на 100 млн эл-тов тратится 100 МБт ОЗУ. Что-то маловато, наверное всё-таки что-то там оптимизируется...


Кстати, а попробуйте забить оный список случайными числами. Посмотрим, сумеет ли он это оптимизировать/пожать.
Автор:  Algo [ Среда, 08 Июль, 2009 18:36 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
Дык про массивы и шла речь:
Илья Ермаков писал(а):
А касательно массивов здоровых - всё равно задействуются служебные структуры и потери по страницам у ОС...

В основном то речь шла о списках, элементы которых отностительно небольшие.
Служебная информация в этом случае составляет большой процент.
С большими массивами такого быть не должно.
Посмотрел на результат распределения 10 млн. integer в D7. Ни каких сюрпризов.
Поискал в сети, похоже, что служебная информация занимает 4 байта, плюс, блоки выравниваются на границу 4 байта.
Ни каких увеличений в разы.
Скорее уж это не магия С++ или D7, а особенности BB.
Автор:  Algo [ Среда, 08 Июль, 2009 18:52 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Algo писал(а):
В императиве обсуждать было бы просто не чего.
А по-вашему в императиве нет проблем? Ну-ну... :lol:

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

Да я и не собираюсь так уж экстраполировать. Но всё равно, ситуация показательная:
1. Пример ТРИВИАЛЬНЫЙ.
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.

Вывод: это острый камушек в огород ФП.
А на "кривую рожу" императива "пенять" не надо, ибо известно, что импратив - зло, но придёт светлое царствие ФП, простое и безпроблемное :)
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 20:20 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Как интересно... Программа собранная jhc банально зацикливается при попытке вывести last. Причем похоже вне зависимости от размеров списка.
Автор:  Geniepro [ Среда, 08 Июль, 2009 20:35 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Algo писал(а):
...
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.
Ну есть и более простая форма, и вообще нужно изучать стандартную библиотеку -- со стандартной функицией length никаких проблем нет! :lol:
Автор:  Geniepro [ Среда, 08 Июль, 2009 20:39 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
Как интересно... Программа собранная jhc банально зацикливается при попытке вывести last. Причем похоже вне зависимости от размеров списка.

Как так? даже для списка из нескольких элементов?
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 20:42 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Alexey Veselovsky писал(а):
Как интересно... Программа собранная jhc банально зацикливается при попытке вывести last. Причем похоже вне зависимости от размеров списка.

Как так? даже для списка из нескольких элементов?


Даже для списка из двух элементов заданых явно. Т.е. [1,2]
Для списка из одного элемента проблем нет ;-)
Видать что-то они там совсем жестко наоптимизировали. Надыть будет багрепорт накатать.
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 20:52 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Сейчас попробую UHC собрать и потестить на этих задачках.
Автор:  Alexey Veselovsky [ Среда, 08 Июль, 2009 21:11 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Гм. Что-то не собирается UHC...
Завтра накатаю жалобу разработчикам ;-)
Автор:  Geniepro [ Среда, 08 Июль, 2009 21:17 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Ужасно, ужасно всё это. Я вот попробовал на интерпретаторе YHC -- 100 тыс элементов проканало, на миллионе интерпретатор упал -- памяти, говорит, не хватает, нужно 32 кБт, а доступно только 30. И это на двух гигах ОЗУ... :lol:
Автор:  Algo [ Среда, 08 Июль, 2009 21:37 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Geniepro писал(а):
Algo писал(а):
...
2. Первое, интуитивное его решение на MAINSTREAM компиляторе не слабо засветившегося ФП языка, выдаёт ошибку.
3. Для ликвидации ошибки требуется глубокие знания языка и модификация решения в МЕНЕЕ простую форму.
Ну есть и более простая форма, и вообще нужно изучать стандартную библиотеку -- со стандартной функицией length никаких проблем нет! :lol:

Получается, что программист должен
1) обязательно знать про указанную особенность компилятора
2) знать про хвостовую рекурсию и форсирование вычислений
3) знать стандартную библиотеку
4) в случае аналогичного, но сложного примера "увидеть" потенциальную проблему.

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

Прокол это, локальный, но прокол. И это надо признать.
Автор:  Илья Ермаков [ Среда, 08 Июль, 2009 21:42 ]
Заголовок сообщения:  Re: Haskell подсчитать длину списка.
Alexey Veselovsky писал(а):
Создание массива INTEGER'ов на 10 млн. элементов хавает 57 мегабайт.


Я-то думал, и правда так. Проверил. Алексей, что-то Вы путаете.
Вложение:
bbmem.PNG
bbmem.PNG [ 50.17 КБ | Просмотров: 6884 ]
Страница 4 из 5 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/