Здравствуйте, Cyberax, Вы писали:

C>Легкость копирования — приятный побочный продукт.

Побочный продукт чего?

prVovik пишет:

> C>Легкость копирования — приятный побочный продукт.
> Побочный продукт чего?

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

--
С уважением,
Alex Besogonov (alexy@izh.com)

Здравствуйте, Cyberax, Вы писали:

>> C>Легкость копирования — приятный побочный продукт.

C>Иммутабельности данных, которая введена была для сохранения ссылочной
C>целостности.

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

То, что в ФЯ копирование отложено по времени до момента модификации, еще не означает, что его (копирования) не происходит

prVovik пишет:

> C>Иммутабельности данных, которая введена была для сохранения ссылочной
> C>целостности.
> Не, ты хоть убей, но я не понимаю, как иммутабельность может ускорить
> процесс *копирования*. Заметь, я имею ввиду *именно копирование*, а не
> создание новой ссылки.

В том-то все и дело, что часто копирование с изменением как раз к
созданию новой ссылки и сводится. Например, для связного списка.

> То, что в ФЯ копирование отложено по времени до момента модификации,
> еще не означает, что его (копирования) не происходит

А иногда его не происходит вообще.

--
С уважением,
Alex Besogonov (alexy@izh.com)

Здравствуйте, prVovik, Вы писали:

C>>В ФЯ изменение — это нежелательная операция, а в некоторых ФЯ вообще
C>>запрещенная.
V>В том то и дело. Поэтому изменения должны быть копирующими

Не обязательно. Это уже смотря как реализовать контейнер. Если старое состояние не используется после получения нового (а в ФЯ это как раз легко отслеживается), то копирование можно реализовать изменением.

Здравствуйте, prVovik, Вы писали:

V>Здравствуйте, Cyberax, Вы писали:

C>>Копирование данных в ФЯ — дешовая операция, так как реального
C>>копирования не происходит. Все данные же неизменяемые, так что просто
C>>копируются указатели на них.

V>Если копирование бесплатно, то изменение дорого.

Докажи.

Здравствуйте, mihoshi, Вы писали:

M>Не обязательно. Это уже смотря как реализовать контейнер. Если старое состояние не используется после получения нового (а в ФЯ это как раз легко отслеживается), то копирование можно реализовать изменением.
И если нет других ссылок.
А если ты вклинился, не читя, о чем шел разговор, то я напомню:

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

То есть, если мы сначала быстро "скопируем данные" (создадаи новую ссылку), то потом будем долго эти данные изменять. Именно об этом я и говорил.

prVovik пишет:

> M>Не обязательно. Это уже смотря как реализовать контейнер. Если
> старое состояние не используется после получения нового (а в ФЯ это
> как раз легко отслеживается), то копирование можно реализовать изменением.
> И если нет других ссылок.

А их обычно не бывает. Вообще, полное копирование данных в ФЯ обычно
происходит не чаще, чем в обычных языках.

> А если ты вклинился, не читя, о чем шел разговор, то я напомню:
> Копирование данных в ФЯ — дешовая операция, так как реального
> копирования не происходит. Все данные же неизменяемые, так что просто
> *копируются указатели на них.*
> То есть, если мы сначала быстро "скопируем данные" (создадаи новую
> ссылку), то потом будем долго эти данные изменять. Именно об этом я и
> говорил.

Не обязательно, при изменяющем копировании возможны варианты:
1. Изменить данные и ничего не копировать
2. Передавать измененные данные _параллельно_ с исходными (естественно,
совершенно прозрачно для программиста).
3. Использовать структуры, в которых изменяющее копирование — дешовая
операция (связные списки, например).
4. Просто скопировать.

Вариант 4 реально почти всегда оптимизируется в предидущие случаи.

--
С уважением,
Alex Besogonov (alexy@izh.com)

prVovik пишет:
> То есть, если мы сначала быстро "скопируем данные" (создадаи новую
> ссылку), то потом будем долго эти данные изменять. Именно об этом я и
> говорил.

Долго это сколько? Существуют специализированные
структуры данных.

Например, binary random-access list в котором cons, head, and tail —
O(1) в большинстве случаев и O(log n) в худшем; lookup и update занимают
O(log n). А в неком Segmented Binomial Random-Access Lists cons, head,
and tail занимают O(1) в худшем случае; lookup и update занимают O(log n).

--
Andrei N.Sobchuck
JabberID: andreis@jabber.ru. ICQ UIN: 46466235.

Здравствуйте, alexeiz, Вы писали:

A>"Cyberax" <37054@users.rsdn.ru> wrote in message
A>news:1068127@news.rsdn.ru
>> alexeiz пишет:
>>

>> Наоборот как раз бывает. Оптимизированная реализация алогритмов на С
>> выглядят ужасно.

A>Вопрос в том, чем будет эта реализация на ФЯ, если на C она ужасна.

A>Конечно, если хочешь показать, что на OCaml'е можно лучше написать, пожалуйста. Возьми любую (не совсем тривиальную) задачу с этого сайта и вперед. Только не забудь привести свой код. Посмотрим, как красиво он будет выглядеть.

Ты что же, любезный, свою тормозную (в 10 раз медленнее чем на С++) прогу на OCaml выложить-то не хочешь? А? Не стесняйся, тут все свои. Ты бы вместо того, чтобы рассуждать об ужасном виде и типичности стиля для языка OCaml, а также его тормознутости, дал бы посмотреть свою прогу тем, кто знает язык хорошо.

Программа на OCaml просто не может отстать в десять раз от варианта на С, если специально не приложить руки. Тем более на известной задаче рассчета простых чисел. Такой проигрыш показывают туповатые компиляторы динамически типизированных языков вроде питона, уважаемый. Это постараться надо. Выложи программку, а? А мы посмотрим, насколько тут OCaml виноват, и насколько ужасен будет оптимизированный вариант.

А то вы все говорите, говорите...

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>prVovik пишет:
>> То есть, если мы сначала быстро "скопируем данные" (создадаи новую
>> ссылку), то потом будем долго эти данные изменять. Именно об этом я и
>> говорил.

ANS>Долго это сколько? Существуют специализированные
ANS>структуры данных.

ANS>Например, binary random-access list в котором cons, head, and tail —
ANS>O(1) в большинстве случаев и O(log n) в худшем; lookup и update занимают
ANS>O(log n). А в неком Segmented Binomial Random-Access Lists cons, head,
ANS>and tail занимают O(1) в худшем случае; lookup и update занимают O(log n).

Замечательно, но я не об этом.
Если на некоторый объект существуют ссылки, и мы пытаемся этот объект менять, то придерживаясь ф. стиля мы вынуждены создать его копию, время создания которой O(n).

Да короче, не важно это... Честно говоря, плевать я хотел на производительность (в разумных пределах), особенно в последнее время

Здравствуйте, prVovik, Вы писали:

V>Замечательно, но я не об этом.
V>Если на некоторый объект существуют ссылки, и мы пытаемся этот объект менять, то придерживаясь ф. стиля мы вынуждены создать его копию, время создания которой O(n).

У Окасаки есть чисто функциональная реализация очереди. Очередь — вполне себе объект. На который может быть много-много ссылок. Должен, зараза копироваться. И ведь копируется, поганка, при каждой вставке и забирании элемента. И время копирования — О(1). Чудо. Вот такой Окасаки фокусник. А ты, батенька, не прав.

1) Не вынуждены. Если объект single-threaded (на него одна ссылка), то он может и будет изменен деструктивно, не принося в жертву функциональный стиль. Применение монад и уникальных типов позволяет гарантировать сингл-тредность (компайлер по рукам тебе даст, если что. Так что не надо про внешние ссылки).
2) Ты увидишь в функциональных программах очень немного длинных массивов и жирных структур. Функциональные программеры в курсе того, что их копирование дорого, и так любят списки в том числе и потому, что для его элементов копирование практически не проигрывает деструктивному изменению. При специально заточенном аллокаторе, конечно (а он такой).

Очередь Окасаки построена на паре однонаправленных списков, и, как я и говорил, имеет среднюю сложность операций O(1). Все "сложные" и "большие" структуры данных Окасаки изменяют не более log(n) своих элементов, остальное очень аккуратно разделяется между разными (!) версиями объекта. Так что функциональные программеры выкрутились — "время копирования сложного объекта" — не О(N), а log(N), и даже иногда О(1) .

V>Да короче, не важно это... Честно говоря, плевать я хотел на производительность (в разумных пределах), особенно в последнее время
V>
Ну и молодец

Здравствуйте, Gaperton, Вы писали:

G>Очередь Окасаки построена на паре однонаправленных списков, и, как я и говорил, имеет среднюю сложность операций O(1). Все "сложные" и "большие" структуры данных Окасаки изменяют не более log(n) своих элементов, остальное очень аккуратно разделяется между разными (!) версиями объекта. Так что функциональные программеры выкрутились — "время копирования сложного объекта" — не О(N), а log(N), и даже иногда О(1) .
Ну чтож, отлично

Здравствуйте, Cyberax, Вы писали:


C>Копирование данных в ФЯ — дешовая операция, так как реального
C>копирования не происходит. Все данные же неизменяемые, так что просто
C>копируются указатели на них.

Это сказка. Указатели — это те же данные. Так что непроизводительные затраты все равно есть.

Если мой алгоритм порождает новый список, то все равно прийдется создать этот список.

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

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

Здравствуйте, Cyberax, Вы писали:

C>В ФЯ изменение — это нежелательная операция, а в некоторых ФЯ вообще
C>запрещенная.

Вот это и есть догма. Из-за этого ориентация на не эффективные во многих случаях связанные списки. Да и порой ракообразный синтаксис.

Ну, не привыкли обычные люди добавлять что-то в начало списка. Понятно, что можно объяснить, что это из соображений эффективности делается, но это уже ломка сознания. А стало быть проблемы в изучении.

А главное, что совсем не это делает ФЯ мощным средсвом борьбы со сложностью.

Здравствуйте, Cyberax, Вы писали:

C>Не поэтому, а для того, чтобы сохранялась ссылочная целостность.
C>Легкость копирования — приятный побочный продукт.

А кто-нибудь в этом мире доказал, что сама по себе "прозрачность" ссылок дает подавляющее приемущество?

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

Мне кажется — это догма рожденная от непонимания того, что же дает ФЯ те самые приемущества.

Когда пропагандисты ФЯ рекламируют их достоинства, то все время приводятся примеры максимально краткой записи. Не спорю — это действительно впечатляет. Но вот дальнейший вывод, что все это благодаря прозрачности ссылок — это просто обман.

Эти приемущества являются всеголишь следствием грамотного использования функциональной декомпозиции (встроенной в функции вроде map() или в разные лист-копрехеншоны). Такие же фичи можно использовать и в ИЯ получая точно такие же приемущества. При этом можно без зазрения совести заниматься модификацией данных по месту и т.п.

Здравствуйте, Cyberax, Вы писали:

C>В том-то все и дело, что часто копирование с изменением как раз к
C>созданию новой ссылки и сводится. Например, для связного списка.

А ты не подумал, что сама возня со списком и трата лишней памяти под его структуру занимают время и ресурсы?

C>А иногда его не происходит вообще.

Очень редко. Настолько редко, чтобы не возводить это в ранг правила.

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Долго это сколько? Существуют специализированные
ANS>структуры данных.

ANS>Например, binary random-access list в котором cons, head, and tail —
ANS>O(1) в большинстве случаев и O(log n) в худшем; lookup и update занимают
ANS>O(log n). А в неком Segmented Binomial Random-Access Lists cons, head,
ANS>and tail занимают O(1) в худшем случае; lookup и update занимают O(log n).

Здорово. А есть такая структура данных — массив. Доступ к любому элменту и его модификация всегда O(1). Как ты думашь кто победит в соревновании на скорость доступа и на минимальность потребления памяти?

И вот встает вопрос, а ради чего ломаются копья? Неспорю неизменяемые типы иногда полезны. Но далеко не всегда. ООП основанный на незименяемых структурах адных — это дурь полнейшая. В ООП объеты на то и объекты чтобы хранить состояние. Так зачем это эиулировать?

Здравствуйте, mihoshi, Вы писали:

M>Докажи.

Сперва докажи бесплатность копирования. Мне этот тезис предсавляется натянутым.

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

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Не происходит.

Просходит, происходит. Просто формулы обман. Там не "O(1)", а "n * O(1)" да еще и абсолютная стоимость "O(1)" разная.

Попробуй написать на ИЯ пргркмму которая будет манипулировать ссылками и сравни ее с программой манипулирующей значениями. ФЯ ничего другого придумать не сможет. Ну, если только переписывать код на массивы в императивном стиле, что слишком сложно.

В общем, хотелось бы увидить реальные тесты, а не теоритические изыски. А то по теории все сортировки имеющие логарифмическое время равны. Но на практике почему-то возникает огромная разница.