Как стать автором
Обновить

Ленивые вычисления в с++0x, тест новых фич

C++ *
Всем привет. А особенно тем, кто пишет на плюсах и интересуется грядущими изменениями языка.
Для исследования фич нового стандарта С++ я сделал забавную штуку — функцию для превращения простого функтора в ленивый. Т.е. вычисляемый не более одного раза, и только при первом обращении.
Для использования вам понадобится простой функтор, без аргументов, возвращающий значение.
Применяете к нему calc_once(some_func) — и он становится ленивым.

auto my_func = calc_once([]{ return SomeHugeCalculation(); });
if ((my_func() && some_case) || (!my_func() && some_other_case))
{
}


* This source code was highlighted with Source Code Highlighter.


Под хабракатом код, там и auto, и decltype, и лямбды.

UPD. Спасибо за карму. Перенес в блог С++.

Читать дальше →
Всего голосов 39: ↑34 и ↓5 +29
Просмотры 3.9K
Комментарии 29

Куча Хаскеля

Haskell *
Перевод

Куча Хаскеля — довольно странное место. Она не похожа на кучу в традиционном языке со строгими вычислениями...

… которая представляет из себя кучу мусора из старых добрых простых данных!
Читать дальше →
Всего голосов 62: ↑54 и ↓8 +46
Просмотры 1.6K
Комментарии 34

Вычисление в куче Хаскеля

Haskell *
Перевод
Начало серии Куча Хаскеля

Дух новогодних подарков

Сегодня в статье мы кратко рассмотрим, что происходит, когда вы в куче Хаскеля открываете подарок с духом внутри. Почти во всём, что есть в куче, кроме констант и того, что уже вычислено, сидит дух. Весь вопрос в том, что станет делать дух в подарке.
Читать дальше →
Всего голосов 36: ↑29 и ↓7 +22
Просмотры 1.2K
Комментарии 13

IO работает с кучей Хаскеля

Haskell *
Перевод
Начало серии Куча Хаскеля
В этой статье мы сосредоточимся на вас. Вы всё крутитесь около кучи Хаскеля и норовите открыть подарок. В конце концов, подарки сами по себе не открываются.
Читать дальше →
Всего голосов 32: ↑25 и ↓7 +18
Просмотры 1.1K
Комментарии 3

Streams.js: отложенные (ленивые) вычисления в Javascript

JavaScript *
Javascript-библиотека stream.js вводит «новую»1 структуру числовых данных: поток (stream). Это контейнер, который похож на массив (array) и связный список (linked list), но содержит неограниченное количество элементов, реализованное методом отложенных вычислений.

var s = Stream.range( 10, 20 );  
s.print(); // prints the numbers from 10 to 20

Для аргумента Stream.range( low, high ) можно указать только начальную границу диапазона Stream.range( low ), тогда поток будет состоять из неограниченного количества натуральных чисел. По умолчанию Stream.range() начинается с 1.
Читать дальше →
Всего голосов 41: ↑35 и ↓6 +29
Просмотры 4.9K
Комментарии 11

Динамическое программирование и ленивые вычисления

Haskell *
Динамическое программирование является довольно важным подходом в решении многих сложных задач, основанным на разбиении задачи на подзадачи и решении этих подзадач единожды, даже если они являются частью нескольких других подзадач. Перед людьми, которые только начинают овладевать функциональным программированием часто возникает вопрос: «как избежать повторного решения подзадач, если не использовать переменные для сохранения результатов?». В этом вопросе одна особенность функционального программирования — отсутствие переменных — мешает кешировать результаты решения подзадач, но другая особенность поможет — ленивые вычисления.
Читать дальше →
Всего голосов 26: ↑26 и ↓0 +26
Просмотры 4.6K
Комментарии 14

Ленивые вычисления

Haskell *
Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.

В этой статье я постараюсь объяснить: что такое ленивые вычисления, для чего они могут применяться и как избежать потери производительности при их использовании.
Читать дальше →
Всего голосов 36: ↑35 и ↓1 +34
Просмотры 15K
Комментарии 36

Ленивый hGetContents. Баг или фича? (Haskell)

Haskell *
Меня давно беспокоит одна тема. Вот решил высказаться и услышать, что думают люди по этому поводу. Речь пойдет о функции hGetContents. Если вы когда-нибудь работали с файлами, то вы знаете, что эта функция возвращает содержимое файла (потока). Вот типичный пример использования этой функции.
import System.IO

main = do 
	file <- openFile "1.txt" ReadMode
	content <- hGetContents file
	print content
	hClose file
-- результат: выводит содержимое файла на экран

Читать дальше →
Всего голосов 10: ↑7 и ↓3 +4
Просмотры 3.2K
Комментарии 20

Принципы быстрого Хаскеля под GHC

Высокая производительность *Haskell *Компиляторы *
Tutorial
GHC (Glasgow Haskell Compiler) — стандартный компилятор Хаскеля. GHC — один из самых крутых компиляторов в мире, но к сожалению без дополнительных телодвижений скомпилированные им программы по скорости больше напоминают интерпретируемые, т. е. работают очень медленно. Однако если раскрыть весь потенциал компилятора, Хаскель приближается по производительности к аналогичному коду на C.

В этой статье я обобщаю опыт выжимания максимума из GHC при создании dataflow-фреймворка Yarr.
Читать дальше →
Всего голосов 27: ↑26 и ↓1 +25
Просмотры 9.6K
Комментарии 21

Как работают ленивые вычисления

Программирование *Haskell *
Перевод
Tutorial
Маленькая Лямбда решила, что уборку в комнате можно отложить и на потом.

Ленивые вычисления — часто используемая методика при исполнении компьютером программ на Haskell. Они делают наш код проще и модульнее, но могут вызвать и замешательство, особенно когда речь заходит об использовании памяти, становясь для новичков распространённой ловушкой. Например, безобидно выглядящее выражение
foldl (+) 0 [1..10^8]
потребует для своего вычисления гигабайты памяти.

В этом руководстве я хочу объяснить, как работают ленивые вычисления и что они означают для времени выполнения и объёма памяти, затрачиваемыми программами на Haskell. Я начну рассказ с основ редукции графов, а после перейду к обсуждению строгой левой свёртки — простейшего примера для понимания и ликвидации утечек памяти.

Тема ленивых вычислений рассматривалась во многих учебниках (например, в книге Саймона Томпсона «Haskell — The Craft of Functional Programming»), но информацию о них, кажется, всё ещё проблематично найти в сети. Надеюсь, моё руководство посодействует решению этой проблемы.

Ленивые вычисления — это компромисс. С одной стороны, они помогают нам сделать код более модульным. С другой стороны, бывает невозможно до конца разобраться, как происходит вычисление в конкретной программе — всегда существуют небольшие отличия между реальностью и тем, что вы о ней думаете. В конце статьи я дам рекомендации, как поступать в ситуациях такого рода. Итак, приступим!

Читать дальше →
Всего голосов 51: ↑49 и ↓2 +47
Просмотры 40K
Комментарии 6

Ленивый список в C++

Ненормальное программирование *C++ *

В Scala есть интересная коллекция — Stream. Контейнер, который представляет собой список, элементы которого вычисляются (и сохраняются после этого) при первом обращении:

The class Stream implements lazy lists where elements are only evaluated when they are needed.

Мне захотелось реализовать нечто подобное на C++.
Что из этого получилось...
Всего голосов 24: ↑24 и ↓0 +24
Просмотры 24K
Комментарии 9

Пишем Java Stream API на коленке за пару минут

Программирование *Java *
Из песочницы
Stream API — замечательная вещь быстро завоевавшая популярность у джава программистов. Лаконичные однострочники обрабатывающие коллекции данных посредством цепочек простых операций map, filter, forEach, collect оказались очень удобны. Операции над парами ключ-значение, конечно, тоже не помешали бы, но увы.

В целом примерно понятно как это всё устроено, но все же зачастую ответ на вопрос «А как бы это написал я?» здорово помогает понять внутренние механизмы той или иной технологии. Так получилось, что внезапно для себя я ответил на этот вопрос применительно к Stream API, историей изобретения этого велосипеда и спешу с вами поделиться.
Читать дальше →
Всего голосов 24: ↑21 и ↓3 +18
Просмотры 20K
Комментарии 12

PostgreSQL Antipatterns: вредные JOIN и OR

Блог компании Тензор PostgreSQL *SQL *Администрирование баз данных *
Бойтесь операций, buffers приносящих…
На примере небольшого запроса рассмотрим некоторые универсальные подходы к оптимизации запросов на PostgreSQL. Пользоваться ими или нет — выбирать вам, но знать о них стоит.
Читать дальше →
Всего голосов 20: ↑20 и ↓0 +20
Просмотры 15K
Комментарии 22

Перемещение — прошлый век! Альтернативы std::move в «C++ будущего»

Программирование *C++ *

Каждый раз, когда мы пишем класс, управляющий ресурсами, мы задумываемся о том, что, скорее всего, для него придётся писать move-конструктор и move-присваивание. Ведь иначе объекты такого типа становятся неуклюжими, как std::mutex, ими тяжело пользоваться на практике: ни вернуть из функции, ни передать в функцию по значению, ни положить в вектор — а если положить его в другой класс как один из членов, то тот класс также «заболевает».


Положим, мы преодолели свою лень (хотя в Rust таких проблем нет!) и садимся писать move-операции для нашего класса. Проблема в том, что move-семантика в C++ имеет фундаментальное ограничение: каждый владеющий ресурсами тип с move-операциями должен иметь пустое состояние, то есть состояние с украденными ресурсами. Его нужно описывать в документации и предоставлять ему поддержку, то есть тратить время и силы на то, что нам не нужно.


Для абстрактных типов данных пустое состояние обычно бессмысленно — если у объекта украли его ресурсы, то он не сможет выполнять свои обычные функции. Но мы вынуждены это делать, чтобы реализовать move-семантику. Для некоторых типов пустое состояние недопустимо: open_file (в противовес теоретическому file), not_null_unique_ptr<T> (в противовес unique_ptr<T>).


Говоря словами Arthur O'Dwyer, мы заказывали телепорт, а нам дали «вас клонируют и убивают первоначальную копию». Чтобы вернуть себе телепорт, проходите под кат!

Читать дальше →
Всего голосов 24: ↑22 и ↓2 +20
Просмотры 15K
Комментарии 174

Долой циклы, или Неленивая композиция алгоритмов в C++

Программирование *C++ *Функциональное программирование *
"Кто ни разу не ошибался в индексировании цикла, пусть первый бросит в деструкторе исключение."

— Древняя мудрость

Циклы ужасны. Циклы сложно читать — вместо того, чтобы сразу понять намерение автора, приходится сначала вникать в код, чтобы понять, что именно он делает. В цикле легко ошибиться с индексированием и переопределить индекс цикла во вложенном цикле. Циклы сложно поддерживать, исправлять в случае ошибок, сложно вносить текущие изменения, и т.д. и т.п.


В конце концов, это просто некрасиво.


Человечество издревле пытается упростить написание циклов. Вначале программисты подметили часто повторяющиеся циклы и выделили их в отдельные функции. Затем они придумали ленивые итераторы, а потом и диапазоны. И каждая из этих идей была прорывом. Но, несмотря на это, идеал до сих пор не достигнут, и люди продолжают искать способы улучшить свой код.


Данная работа ставит своей целью пролить свет на отнюдь не новую, но пока что не слишком распространённую идею, которая вполне способна произвести очередной прорыв в области написания программ на языке C++.


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

Читать дальше →
Всего голосов 24: ↑23 и ↓1 +22
Просмотры 16K
Комментарии 47

Ленивые итераторы и диапазоны в C++

Программирование *C++ *Алгоритмы *

Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.


Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.


Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator).

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

Читать дальше →
Всего голосов 10: ↑10 и ↓0 +10
Просмотры 5.3K
Комментарии 0

Ленивые операции над множествами в C++

Программирование *C++ *Алгоритмы *

В C++ нет понятия "множество". Есть std::set, но это всё-таки конкретный контейнер. Есть функции для работы с упорядоченными диапазонами: merge, inplace_merge, includes, set_difference, set_intersection, set_symmetric_difference, set_union, но это алгоритмы, они не ленивые, и при вызове сразу вычисляют результат. К тому же они предназначены для работы строго с двумя диапазонами.


Что же делать, если, во-первых, диапазонов много (больше двух), а во-вторых, мы хотим вычислять результат не сразу, а по необходимости?


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


В публикации Ленивые итераторы и диапазоны в C++ я разбирал, что такое ленивые диапазоны.
Читать дальше →
Всего голосов 7: ↑7 и ↓0 +7
Просмотры 8.3K
Комментарии 4

Самую холодную капельку во Вселенной уронили с высокой колокольни

Блог компании RUVDS.com Julia *Научно-популярное Физика Квантовые технологии

И остались довольны результатом. Теперь хотят отправить ее на орбиту Земли.

Сегодня мы попробуем разобраться в физике пятого состояния материи и выясним, зачем ее сбрасывать с башни.
Читать дальше →
Всего голосов 117: ↑115 и ↓2 +113
Просмотры 42K
Комментарии 38

Ленивые диапазоны и стирание типов

Программирование *C++ *

В публикации Ленивые операции над множествами в C++ я показал, как можно проектировать ленивые операции над несколькими диапазонами. Теперь я хочу подробнее рассказать о важном решении, делающем такие операции удобными в использовании.


Один из основных моментов в интерфейсе ленивых операций над диапазонами — это возможность следующей записи


burst::merge(std::tie(range1, range2, ...));

То есть возможность работать с произвольным набором исходных диапазонов.


В коде это будет выглядеть как-то так:


const auto odd = std::vector{1, 3, 5, 7};
const auto even = std::list{0, 2, 4, 6, 8};

const auto merged_range = burst::merge(std::tie(odd, even));

const auto expected = {0, 1, 2, 3, 4, 5, 6, 7, 8};
assert(merged_range == expected);

Почему же это так важно, и что стоит за этой записью?


Ответ на вопрос "почему это важно" понятен. Во-первых, это красиво. Кроме того, удобно.
А вот что за этим стоит — и есть суть данной публикации.

Читать дальше →
Всего голосов 11: ↑11 и ↓0 +11
Просмотры 3.7K
Комментарии 8