?

Log in

No account? Create an account

Entries by category: it

спецолимпиадное

По мотивам поста Никиты про разницу в производительности "высокоуровнего/функционального" и "низкоуровнего/императивного" кода. Взял буквально его пример с созданием массива пар чисел. Его оригинал на кложе:
(concat
 (mapv
    (fn [y] [from-x y])
    (range from-y (quot to-y 2)))
  (mapv
    (fn [y] [to-x y])
    (range (quot to-y 2) to-y)))

Как быстро он работает - не представляю.

Попробовал обе версии - "функциональную" и "императивную" - записать на D в качестве эксперимента, посмотреть, насколько компилятор справляется это дело развернуть.
struct Point { int x, y; }

auto f(int from_y, int to_y, int from_x, int to_x) {
    return chain( iota(from_y, to_y/2).map!(y => Point(from_x, y)),
                  iota(to_y/2, to_y)  .map!(y => Point(to_x, y)) ).array;   
}

auto g(int from_y, int to_y, int from_x, int to_x) {
    auto res = new Point[to_y - from_y];
    foreach(y; from_y .. to_y)
        res[y - from_y] = Point(y < to_y / 2 ? from_x : to_x, y); 
    return res;
}

На 60 миллионах точек ( f(20_000_000, 80_000_000, 1, 2) ) "функциональный" у меня работает 167 мс, "императивный" - 146 мс, разница в пределах 15%. Терпимо.
(полный текст тут, компилятор - LDC)

Попробовал записать это дело на хаскеле, но в нем я нуб, не знаю, как правильно его готовить. Вот такой вариант
import qualified Data.Vector.Unboxed as V
type Point = (Int, Int)

f :: Int -> Int -> Int -> Int -> V.Vector Point
f from_y to_y from_x to_x =
    let a = V.generate (to_y `div` 2 - from_y) (\y -> (from_x, y+from_y))
        b = V.generate (to_y - to_y `div` 2)   (\y -> (to_x, y + to_y `div` 2))
    in V.concat [a, b]

на тех же исходных данных работает 1.33 сек, т.е. примерно на порядок медленнее. Другие варианты, что я пробовал, еще медленнее. Например, если data Point = P {-# UNPACK #-} !Int !Int, то оно уже не Unboxed, и если просто Data.Vector для них использовать, то время больше трех секунд уже.
Вопрос хаскелистам: как вы unboxed массив простых структур делаете?

Tags:

Полетал тут днем над центральными парками:

(HD, можно/нужно на весь экран открывать)




А вот простой способ отключить стабилизацию, и что тогда получается:
Read more...Collapse )

она сломалась

Вот, помнится, был я школьником средних классов, и был у меня дома компутер с 386 процессором и видеокартой EGA. А у соседей сверху был 486 с VGA. Какие там были игрушки! Какая графика! Жили там два брата, один лет на пять меня старше, второй года на четыре меня младше. Понятно, заведовал там всеми игрушками старший брат, а мы с младшим играли в то, что тот установит. Но иногда бывало так, что соберемся в какую-то игру поиграть, а ее больше нет. Младший тогда спрашивал у старшего: что с ней случилось? А тот отвечал: она сломалась. У младшего вопрос отпадал, он же знал на примере пластмассовых игрушек, что игрушки иногда ломаются. Я же тогда уже чуть побольше понимал и знал, что как же это: вот файлы игры, вот ее исполняемый файл, вот ДОС, в котором все живет, и если сам файлы удалять или менять не будешь, то программу можно запускать сколько угодно раз, она не изнашивается и не ломается, это ж числа, байты, не пластмасса какая. В этом и прелесть программ - полный детерминизм и воспроизводимость, один раз написал, и она работает сколько угодно, не ломается.

И вот прошли годы, появилась эта дурацкая тенденция переносить софт в веб. И вот ты пользуешься какой-то программой много месяцев подряд, все хорошо, а тут в один прекрасный день заходишь, а там все поменяли в худшую сторону. Или даже такое:
Fatal error: Uncaught exception 'PDOException' with message 'SQLSTATE[23000]: Integrity constraint violation: 1062 Duplicate entry '9dbbfc751b59adbb581f7460eb5263ab' for key 1' in /home/fth/public_html/_c/userUtils.php:114 Stack trace: #0 /home/fth/public_html/_c/userUtils.php(114): PDOStatement->execute(Array) #1 /home/fth/public_html/_c/doLogin.php(27): Guard->logUserIn(Object(User)) #2 {main} thrown in /home/fth/public_html/_c/userUtils.php on line 114

"Она сломалась".

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

Читаю статью про F# в очередном номере ПФП, а там стандартный набор бреда про сабж:
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.


По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.

2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.

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

Tags:

Делаем из мухи слона

Вчера давний друг, однокурсник, а ныне разработчик одной социальной сети, написал мне и другим нашим друзьям:

Я тут PHP-шников набираю, задаю всем одинаковое тестовое задание, чтобы присылали его вместе с резюме. Вот оно:

===============================================
Требуется написать программу, которая делает из "мухи" - "слона". Например:

муха -> мука -> рука -> руна -> ... -> слон

Т.е., меняя за 1 шаг по 1 букве, нужно из слова "муха" вывести слово "слон" и распечатать все шаги. Решите,
пожалуйста, задачу в этой постановке так, как сочтете нужным.
===============================================

Ощущение такое, что практически никто не может это нормально решить. Чего только не присылают...

Если у вас будет время, попробуйте, пожалуйста, решить данную задачку (на любом языке). А то я уже начинаю думать, может, я что-то не то спрашиваю...


А на днях я увидел упоминание этой задачки и там же вариант решения на PHP. Сначала не стал смотреть на решение и сделал свое, потом все же заглянул. И тогда я понял, что имел в виду автор письма.
Когда на работу устраиваются новички, это можно понять - с учетом низкого порога вхождения в РНР уровень среднего новичка там может быть сколь угодно низким. Но когда такие решения приходят от опытных вроде бы разработчиков, возникает ощущение, что все же РНР ест мозг.

Мой первый вариант на окамле получился довольно императивным, потом сделал более чистый, но все равно не без сайд эффектов. Подозреваю, что с помощью ленивости или CPS можно сотворить более красивое и чистое решение, однако быстро его придумать у меня не получилось...

Tags: