Здравствуйте, Mr.Cat, Вы писали: G>>операция ++ дается почти бесплатно MC>А можно с этого места поподробнее?
Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Gaperton, Вы писали: G>>операция ++ дается почти бесплатно MC>А можно с этого места поподробнее?
Она "ленивая". Конкатенация списков не приводит к немедленной пробежке по списку, она откладывается на момент чтения этого списка. Ленивость превращает многие алгоритмы на списках, которые O(N^2) в строгом виде, в O(N). За подробностями лучше, например, к thesz. Мне думать очень лень о релятивистских эффектах ленивости, строго говоря, я в этом не специалист.
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Mr.Cat, Вы писали: G>>>операция ++ дается почти бесплатно MC>>А можно с этого места поподробнее?
MC>Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Mr.Cat, Вы писали: G>>>операция ++ дается почти бесплатно MC>>А можно с этого места поподробнее? MC>Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Что-то мне подсказывает, что это не так.
Забудем на время о rewrite rules и оптимизациях в компиляторе, рассмотрим только эффекты ленивого порядка вычислений на временную сложность.
Интуиция подсказывает, что сэкономить здесь можно только в том случае, если львиную долю вычислений делать не надо — например, генерируем огромный список и берем из него только первых 10 элементов. А сортировка требует вычисления результата конкатенации целиком.
Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.
По-моему выделенные слова противоположны друг другу, нет?
К>Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.
К>По-моему выделенные слова противоположны друг другу, нет?
Я спорил с утверждением "операция ++ дается почти бесплатно". Это не так. Выполнение фукнции (++) "размазано" во времени, но при условии потребления всего списка она выполняется полностью.
Здравствуйте, Gaperton, Вы писали:
G>Он проверяет другое — сложность операции конкатенации. Она все равно не получается O(N).
Я думаю, что получается. Это довольно просто проверить, надо всего-то поэкспериментировать с различными длинами списков и построить график, но мне лень .
Здравствуйте, palm mute, Вы писали:
К>>По-моему выделенные слова противоположны друг другу, нет?
PM>Я спорил с утверждением "операция ++ дается почти бесплатно". Это не так. Выполнение фукнции (++) "размазано" во времени, но при условии потребления всего списка она выполняется полностью.
Это не следует из проведенного эксперимента.
1) Надо исключить влияние времени генерации длинного списка.
2) Конкатенировать для чистоты лучше не пустой список, а тот же список многократно. Исключив фактор свопа — все должно гарантировано поместится в памяти. Для гарантии этого, каждый эксперимент должен повторяться многократно.
3) И потом посмотреть, будет ли у last выраженная квадратичная асимптотика, или ей можно пренебречь. Точек должно быть не меньше пяти.
4) И еще посмотреть, как будет себя вести first.
5) И делать все это не в консоли, а в ghc с включенными оптимизациями.
G>1) Надо исключить влияние времени генерации длинного списка.
Эта мысль мне сразу пришла в голову, вот результат:
Prelude> let appendEmpty xs = xs ++ []
Prelude> let xs = [1 .. 10000000]
Prelude> :s +s
Prelude> last xs
10000000
(1.95 secs, 402124972 bytes) -- вот здесь мы исключили влияние времени генерации
Prelude> last xs -- повторный замер показывает, что список уже сгенерирован
10000000
(0.08 secs, 0 bytes)
Prelude> last $ appendEmpty xs
10000000
(0.18 secs, 281025096 bytes)
Prelude> last $ appendEmpty $ appendEmpty xs
10000000
(0.32 secs, 561513668 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty xs
10000000
(0.45 secs, 842527844 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty $ appendEmpty xs
10000000
(0.60 secs, 1122493452 bytes)
Prelude>
G>2) Конкатенировать для чистоты лучше не пустой список, а тот же список многократно. Исключив фактор свопа — все должно гарантировано поместится в памяти. Для гарантии этого, каждый эксперимент должен повторяться многократно.
Для свопа тут маловато данных. Конкатенировать непустой список необязательно, достаточно показать линейную зависимость от длины первого слагаемого — это напрямую следует из реализации оператора (++). G>3) И потом посмотреть, будет ли у last выраженная квадратичная асимптотика, или ей можно пренебречь. Точек должно быть не меньше пяти. G>4) И еще посмотреть, как будет себя вести first.
Это все хорошие, годные предложения, но делать мне это точно лень.
G>5) И делать все это не в консоли, а в ghc с включенными оптимизациями.
В консоли ленивые вычисления никуда не деваются. А вот rewrite rules, deforestation и прочая магия не работают. Здесь оптимизации ни к чему, для чистоты эксперимента надо изолировать эффекты ленивости.
RD>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C. T>>Докажиземлюешь. RD>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности. RD>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Твой тезис, тебе и доказывать.
Или это не твой тезис?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, palm mute, Вы писали:
G>>Он проверяет другое — сложность операции конкатенации. Она все равно не получается O(N).
PM>Я думаю, что получается. Это довольно просто проверить, надо всего-то поэкспериментировать с различными длинами списков и построить график, но мне лень .
Ладно, тогда разберемся "аналитически". Ну, короче, как в принципе устроен ++? Ну, например, так. Я на Эрланге напишу, мне так проще, и в принципе один хрен.
%% Вот это - достаточно понятно.
concat( [], X ) -> X;
%% Как, собственно, и вот это
concat( [ H | T ], X ) ->
[ H | concat( T, X ) ].
Как у нас будет выполняться concat( A, B) в ленивом языке? Для простоты, пусть у нас ленивые только конструкторы списка, остальное неважно.
C = concat( A, B ) имеет сложность O(1)
Пробежка по результату приведет к дополнительному ленивому вызову concat, который будет возвращать копию элемента списка H для каждого элемента А, и будет стоить столько же для элементов B. То есть, пробежка по С будет чуть дороже, чем пробежка по А или Б. Однако, налицо неплохой потенциал для оптимизации в ghc — компилятор может избежать задействования хипа, если выведет last use для элементов C. Это уже кое-что, не так ли?
D = concat( concat( A, B ), B1 ) — само по себе тоже O(1), разумеется, это не интересно.
А пробежка по D... Два накладных вызова на len( A ), один — на len( A + B ) — len( A ), и ноль на len( B1 ). Та же картина по last use для ghc.
Итак, при наращивании глубины конкатенации по данной цепочке, имеем очень легкую, почти незаметную в сравнении со строгим случаем квадратичность (за счет отсутствия переливаний из памяти в память), которая будет почти незаметна на фоне обработки.
Смотрим второй вариант:
D = concat( B1, concat( A, B ) )
Имеем один накладной вызов при любой вложенности подобных операций конкатенации. То есть, квадратичности нет. Прикольно, не так ли?
Будем проверять теорию экспериментом?
Да, вариант с хвостовой рекурсией я не рассматривал, ибо интуиция мне подсказывает ее ненужность в "ленивом" случае.
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Gaperton, Вы писали:
G>>1) Надо исключить влияние времени генерации длинного списка. PM>Эта мысль мне сразу пришла в голову, вот результат:
Да, это напоминает линейную зависимость.
G>>5) И делать все это не в консоли, а в ghc с включенными оптимизациями. PM>В консоли ленивые вычисления никуда не деваются. А вот rewrite rules, deforestation и прочая магия не работают. Здесь оптимизации ни к чему, для чистоты эксперимента надо изолировать эффекты ленивости.
Ну, в реальности я думаю эта зависимость будет не так страшна и заметна. И должна сильно сгладится "магией" ghc. См. мой соседний пост тебе с "теорией".
И кстати, в случае, если мы берем первые несколько элементов, квадратичность точно не будет заметна из-за размазанности операции concat по всему списку. И будет строгий выигрышь.
RD>>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C. T>>>Докажиземлюешь. RD>>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности. RD>>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
T>Твой тезис, тебе и доказывать. T>Или это не твой тезис?
Мне достаточно наслаждаться жизнью. Доказывать кому-то что-то нужно Вам. А мне и так хорошо.
P.S. Это не тезис и я в отличии от некоторых никому и ничего не доказываю. Не напрягайтесь.
RD>Мне достаточно наслаждаться жизнью. Доказывать кому-то что-то нужно Вам. А мне и так хорошо. RD>P.S. Это не тезис и я в отличии от некоторых никому и ничего не доказываю. Не напрягайтесь.
Ну вот, например, более эффективная реализация. Нельзя сказать, что бы она была особо сложной для понимания.
qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' (x:xs) y = part xs [] [x] []
where
part [] l e g = qsort3' l (e ++ (qsort3' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| otherwise = part zs l (z:e) g
G>Да, вариант с хвостовой рекурсией я не рассматривал, ибо интуиция мне подсказывает ее ненужность в "ленивом" случае.
Хотя почему бы и нет. Конкатенация с хвостовой рекурсией, которая должна быть более оптимальна для строгих языков:
concat( A, B ) -> reverse_concat( reverse_concat( A, [] ), B ).
reverse_concat( [], B ) -> B;
reverse_concat( [ H | T ], B ) -> reverse_concat( T, [ H | B ] ).
Хм. Что тут будет в ленивом случае? По ходу дела, вообще ничего хорошего. Здесь нельзя получить первый элемент списка, не вычислив все. Не подвела меня интуиция .
Здравствуйте, Gaperton, Вы писали:
G>А пробежка по D... Два накладных вызова на len( A ), один — на len( A + B ) — len( A ), и ноль на len( B1 ). Та же картина по last use для ghc.
Здесь намудрил, это можно сказать проще. При пробежке по D будет 2 накладных вызова для элементов А, 1 элементов B, и ноль для элементов B1. Принцип понятен. Вызовы будут, будет также, вероятно, определен last use, и цепочка из 2-х вызовов для элементов A должна оказаться дешевле, чем сумма накладных расходов для чтения двух элементов B. Что и приведет к менее "квадратичной" асимптотике. Разумеется, если смотреть не в hugs а в ghc.
dmz>Ну вот, например, более эффективная реализация. Нельзя сказать, что бы она была особо сложной для понимания.
dmz>
dmz>qsort3 :: Ord a => [a] -> [a]
dmz>qsort3 x = qsort3' x []
dmz>qsort3' (x:xs) y = part xs [] [x] []
dmz> where
dmz> part [] l e g = qsort3' l (e ++ (qsort3' g y))
dmz> part (z:zs) l e g
dmz> | z > x = part zs l e (z:g)
dmz> | z < x = part zs (z:l) e g
dmz> | otherwise = part zs l (z:e) g
dmz>
Боюсь, что я не настолько силен в Haskell чтобы сходу понять. В частности, не ясно что происходит с "y" в qsort3'. Название "part" тоже ясности не добавляет.
Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".
