Quicksort: краткость записи vs производительность кода - Философия программирования

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

A>Какие препятствия для сохранения иммутабельности на уровне языка?
A>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).

Такие фокусы умеет делать Clean (http://wiki.clean.cs.ru.nl/Clean). Там чистота реализуется как раз на уникальных типах http://en.wikipedia.org/wiki/Uniqueness_type

Вот тут
http://www.rsdn.ru/forum/decl/1128992.hot.aspx
http://www.rsdn.ru/forum/philosophy/1128398.1.aspx

Gaperton неплохо все разъясняет.

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

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

PC_>>Спасибо, но это не Квик сорт. Это его пародия.
PC_>>Алгоритм Квик сорт включает перемещение элементов на "одном участке" памяти.
PC_>>Тоесть не требует дополнительных ресурсов памяти.

PC_>>Тоесть банально этот код не решает поставленную задачу. Точка.

KV>Предлагаю со столь смелым заявлением отправляться сразу сюда: http://rsdn.ru/forum/decl/, а я пока за попкорном сбегаю. Троеточие...

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

1. Может ли?
2. Если да, то как? Интересует последовательность преобразований, алгоритм работы оптимизирующего компилятора в данном конкретном случае (общие стространичные статьи по устройству оптимизатора, например, в хаскеле на данный момент не интересуют).
Хотелось бы увидеть не эвристический алгоритм.
3. Хотелось бы увидеть код на высокоуровневом языке программирования и листинг машинного или байт кода.

Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).

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

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

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

A>Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).

Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.

P>А "хвост разворачивать обратно" -- это как?

добавить в этот код — reverse правой части (перед вторым quicksort — сделать inplace-reverse(pivotNewIndex+1, right))

procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

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

Ф>С таким подходом у нас скоро появятся программы, для которых не хватит никакого кол-ва памяти.
Ф>Ничего бесплатного не бывает. Если на PC потерю 1 — 2 Гб можно не заметить, то на (например) карманном гаджете этого объёма может не найтись.

Правильно понимаю, на карманном гаджете ты собрался запускать высоконагруженый сервер ?

Ф>Оптимизировал софтину, которая обрабатывала текстовые отчёты XML-подобного формата (самопальный формат). На очередном отчёте софтине просто не хватило памяти.
Ф>Софтина на каждый уровень вложенности открывала тот же самый файл, читала его целико в память (в свой буфер).

Какое это имеет отношение к immutable ?

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

P>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort,
это никак не видно из кода на наскеле. это просто так получается из за особеностей реализации

    [y|y->xs,y<=x]

P> а классический inplace qsort на C -- не stable.

т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный?
и при этом не потерял простоты описания?

... << RSDN@Home 1.2.0 alpha 4 rev. 1227>>

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

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

P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort,
C>это никак не видно из кода на наскеле. это просто так получается из за особеностей реализации

Очень даже видно, особенно если прочитать статью на википедии, где ровно то же написано псевдокодом. Ну, еще, правда, надо знать что list comprehensions сохраняют порядок.

C>т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный?
C>и при этом не потерял простоты описания?

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

P>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable.

inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n

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

DG>inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n

А "хвост разворачивать обратно" -- это как?

P>А так можно думать как короче записать классический partition.

да можно не записывать короче, можно оставить partition.
достаточно зафиксировать как делается partition по бинарному условию на той же самой памяти

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

C>т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный?
C>и при этом не потерял простоты описания?

Хаскельный код сортирует список, а не массив, и всегда просматривает этот список в одном направлении.

Конкретно этот алгоритм легко выраждается в O(n^2), если список изначально отсортирован.

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

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

P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.

Pzz>Казалось бы, из любой нестабильной сортировки легко получить стабильную, если модифицировать функцию сравнения таким образом, чтобы при равенстве аргументов она учитывала их взаимное расположение и считала, что тот, который идет раньше — он меньше (если мы сортируем по возрастанию).

А наоборот?

Мозгом-то много что много из чего можно получить, а оптимизация должна сохранять смысл кода, что при переходе stable->unstable очевидно невозможно

Хотя алгоритм, такое делающий, был бы очень интересен.

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

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

A>1. Может ли?
A>2. Если да, то как? Интересует последовательность преобразований, алгоритм работы оптимизирующего компилятора в данном конкретном случае (общие стространичные статьи по устройству оптимизатора, например, в хаскеле на данный момент не интересуют).
A>Хотелось бы увидеть не эвристический алгоритм.
A>3. Хотелось бы увидеть код на высокоуровневом языке программирования и листинг машинного или байт кода.

A>Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).

Как уже сказали, алгоритмы разные и не получится.
Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.

Здравствуйте, pierre, Вы писали:
P>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.

Здравствуйте, FR, Вы писали:
FR>Как уже сказали, алгоритмы разные и не получится.
FR>Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.

Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си.
Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.

def quicksort(l)
{
    | [] => [];
    | x :: xs  => quicksort( $[ y | y in xs, y <= x ] ) + [x] + quicksort( $[y | y in xs, y > x] );
}

Либо, как заметил DarkGray

inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n

Тогда алгоритмы тоже будут одинаковы.

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

A>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си.
A>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.

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

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

A>Здравствуйте, pierre, Вы писали:
P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.

A>Здравствуйте, FR, Вы писали:
FR>>Как уже сказали, алгоритмы разные и не получится.
FR>>Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.

A>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си.
A>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.
A>

A>def quicksort(l)
A>{
A>    | [] => [];
A>    | x :: xs  => quicksort( $[ y | y in xs, y <= x ] ) + [x] + quicksort( $[y | y in xs, y > x] );
A>}
A>

A>Либо, как заметил DarkGray
A>

A>inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n

A>Тогда алгоритмы тоже будут одинаковы.

Более простая задача:
Как следующий код преобразовать в код на С++, данный ниже:

def partition(l)
{
    | [] => [];
    | x :: xs  => $[ y | y in xs, y <= x ] + [x] + $[y | y in xs, y > x]; //где $[...] не сохраняет последовательность 
}

void partition(int a[], int p, int r) 
{
  int x = a[p];
  int j = p;
  for (int i = p + 1; i < r; i++) 
  {
    if (x > a[i]) 
    {
      j = j + 1;
      swap(a[j], a[i]);
    }
  }
  a[p] = a[j];
  a[j] = x;
}

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

S>Здравствуйте, Aleх, Вы писали:

A>>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си.
A>>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.

S>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.

Какие препятствия для сохранения иммутабельности на уровне языка?
Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается). Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте). Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом.

В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".

S>С другой стороны, сборщик мусора из дотнета умеет двигать объекты прозрачным для программы образом. Т.е. программа не узнает о том что они передвинулись. Но и сортировку таким образом не сделать, т.к. ее результаты тоже будут невидны.

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

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

Но можно посмотреть и с другой стороны: на своем любимом декларативно-функциональном языке ты можешь написать программу, которая не будет сортировать сама, а сгенерирует оптимальный императивный код.

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

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

D>вопрос очень правильный, и, как я понимаю, вопросами эффективной компиляции такого кода много занимаются.

D>Но можно посмотреть и с другой стороны: на своем любимом декларативно-функциональном языке ты можешь написать программу, которая не будет сортировать сама, а сгенерирует оптимальный императивный код.

Можно раскрыть мысль? Чтобы сгенерировать оптимальный код нужно ведь очень много вещей учитывать, то есть внешней программой это делать будет не удобно.
К тому же я как раз и создал тему, потому что мне интересно, существует ли такой неэвристический алгоритм (даже не алгоритм а метод), который мог бы сгенерировать оптимальную программу сортировки.

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

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

S>>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.

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

A>Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте).
Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило.

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

A>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".
А не будет дороже, чем отсортировать иммутабельной сортировкой?

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

S>Здравствуйте, Aleх, Вы писали:

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

S>>>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.

A>>Какие препятствия для сохранения иммутабельности на уровне языка?
A>>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).
S>А если нужны, то что сортировать не надо? В иммутабельных языках довольно сильный реюз данных. Ждать пока данные освободятся для сортировки нет смысла.
Инплейс сортировкой не надо.

A>>Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте).
S>Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило.
Да, нет на уровне языка. Но тот же список, например, может быть вполне представлен физически массивом, если под списком обязательно не подразумевать физический список (как на Си), а только интерфейс списка.

A>>Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом.
S>Представь что ты сортируешь деревья по их размеру. После сортировки новые деревья должны вырасти?
Что значит вырасти? Деревья по структуре остануться теми же, только могут быть расположены в других адресах памяти, что будет незаметно из программы.

A>>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".
S>А не будет дороже, чем отсортировать иммутабельной сортировкой?
Возможно. Но ведь зачастую в программе одновременно не нужны отсортированные данные и исходные неотсортированные.

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

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

A>>>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).
S>>А если нужны, то что сортировать не надо? В иммутабельных языках довольно сильный реюз данных. Ждать пока данные освободятся для сортировки нет смысла.
A>Инплейс сортировкой не надо.
Вот и не сортируются

S>>Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило.
A>Да, нет на уровне языка. Но тот же список, например, может быть вполне представлен физически массивом, если под списком обязательно не подразумевать физический список (как на Си), а только интерфейс списка.
Представим список деревьев в физическом массиве. Ты предлагаешь перемешать деревья незаметно для кода, вызывающего сортировку. В случае если программа ссылается на те деревья, то незаметно перемешать их не выйдет.

A>>>Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом.
S>>Представь что ты сортируешь деревья по их размеру. После сортировки новые деревья должны вырасти?
A>Что значит вырасти? Деревья по структуре остануться теми же, только могут быть расположены в других адресах памяти, что будет незаметно из программы.
Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя.

A>>>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".
S>>А не будет дороже, чем отсортировать иммутабельной сортировкой?
A>Возможно. Но ведь зачастую в программе одновременно не нужны отсортированные данные и исходные неотсортированные.
А кто будет разбираться, нужны или нет в конкретном случае?

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

N>На одном из проектов я сейчас наблюдаю 3-кратное ускорение при переписывании кода с C++ на C# и переходе к immutable структурам данных (к сожалению, не могу сейчас написать детали).

А можно еще привести данные об изменении потребности в памяти ? immutable — оно же не бесплатно.

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

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

S>Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя.
Что значит во время сортировки? Во время сортировки выполняется сортировка, или имеются ввиду многопоточные приложения? Это отдельный вопрос.

S>А кто будет разбираться, нужны или нет в конкретном случае?
Оптимизатор. http://en.wikipedia.org/wiki/Alias_analysis

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

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

S>>Представим список деревьев в физическом массиве. Ты предлагаешь перемешать деревья незаметно для кода, вызывающего сортировку. В случае если программа ссылается на те деревья, то незаметно перемешать их не выйдет.
A>Если ссылается на отдельные деревья, то не выйдет. Если для дальнейшей работы программы нужна только отсорированная совокупность деревьев, то вполне.
A>К тому же программа теоретически может быть преобразована во время компиляции так, что в списке будут храниться ссылки/указатели на деревья.
Ты предлагаешь создать вспомогательный невидимый массив со ссылками на данные, отсортировать его по месту, а потом по этому массиву создать уже упорядоченный функциональный список?
Да, это будет работать. Проблема лишь в том, что это должно работать в ядре языка, если сам язык не позволяет работать с массивовм напрямую. А все алгоритмы в ядро языка не воткнуть.

S>>Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя.
A>Что значит во время сортировки? Во время сортировки выполняется сортировка, или имеются ввиду многопоточные приложения? Это отдельный вопрос.
Нет, не многопоточные. Речь была о том, что если сортируются сами данные а не ссылки, то ссылки будут ссылаться на другие данные после сортировки, что ломает иммутабельность.

S>>А кто будет разбираться, нужны или нет в конкретном случае?
A>Оптимизатор. http://en.wikipedia.org/wiki/Alias_analysis
Это штука времени компиляции. В рантайме она не ответит на вопрос используемости данных.

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

FR>Здравствуйте, Aleх, Вы писали:

A>>Какие препятствия для сохранения иммутабельности на уровне языка?
A>>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).

FR>Такие фокусы умеет делать Clean (http://wiki.clean.cs.ru.nl/Clean). Там чистота реализуется как раз на уникальных типах http://en.wikipedia.org/wiki/Uniqueness_type

FR>Вот тут
FR>http://www.rsdn.ru/forum/decl/1128992.hot.aspx
FR>http://www.rsdn.ru/forum/philosophy/1128398.1.aspx

FR>Gaperton неплохо все разъясняет.
Идея понятна, но возникает несколько вопросов.
Поскольку та тема уже закрыта, спрошу здесь:

transform:: !*{.a} !Int !Int (.a->.a) -> *{.a}
transform arr fr to fun
| fr < to # ( x, arr) = arr![ fr ]
          = transform { arr & [ fr ] = fun x } (fr + 1) to fun             
          = arr

// это уникальный массив массивов с элементами Color.
// модификаторы "*" и "." задают уникальность объекта — компилятор будет следить за тем,
// чтобы на него оставалась только одна ссылка, и если что — даст по рукам.
// Такие объекты называются single threaded и компилятор умеет их изменять деструктивно.

Чем отличается точка от звездочки?
И что означают эти два выражения?

( x, arr) = arr![ fr ] 
{ arr & [ fr ] = fun x }

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

PD>>А можно еще привести данные об изменении потребности в памяти ? immutable — оно же не бесплатно.

I>Бесплатно, потому что память нынче бесплатная.

С таким подходом у нас скоро появятся программы, для которых не хватит никакого кол-ва памяти.
Ничего бесплатного не бывает. Если на PC потерю 1 — 2 Гб можно не заметить, то на (например) карманном гаджете этого объёма может не найтись.
На сервере может не найтись например 10 Гб. Из личного опыта:
Оптимизировал софтину, которая обрабатывала текстовые отчёты XML-подобного формата (самопальный формат). На очередном отчёте софтине просто не хватило памяти.
Софтина на каждый уровень вложенности открывала тот же самый файл, читала его целико в память (в свой буфер).

От:	Ikemefula	http://blogs.rsdn.org/ikemefula
Дата:	23.12.10 20:33
Оценка:

	От:	FR
	Дата:	23.12.10 17:15
	Оценка:	20 (2)

	От:	Aleх
	Дата:	22.12.10 15:44
	Оценка:	3 (1)

	От:	pierre
	Дата:	22.12.10 17:09
	Оценка:	2 (1)

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	22.12.10 17:45
Оценка:	1 (1)

От:	Pzz	https://github.com/alexpevzner
Дата:	22.12.10 17:46
Оценка:

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	22.12.10 18:32
Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	23.12.10 14:39
Оценка:

От:	Фанатик	http://vk.com/id10256428
Дата:	23.12.10 20:47
Оценка: