Здравствуйте, samius, Вы писали:
S>Здравствуйте, Aleх, Вы писали:
A>>Здравствуйте, samius, Вы писали:
S>>>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.
A>>Какие препятствия для сохранения иммутабельности на уровне языка? A>>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается). S>А если нужны, то что сортировать не надо? В иммутабельных языках довольно сильный реюз данных. Ждать пока данные освободятся для сортировки нет смысла.
Инплейс сортировкой не надо.
A>>Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте). S>Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило.
Да, нет на уровне языка. Но тот же список, например, может быть вполне представлен физически массивом, если под списком обязательно не подразумевать физический список (как на Си), а только интерфейс списка.
A>>Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом. S>Представь что ты сортируешь деревья по их размеру. После сортировки новые деревья должны вырасти?
Что значит вырасти? Деревья по структуре остануться теми же, только могут быть расположены в других адресах памяти, что будет незаметно из программы.
A>>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте". S>А не будет дороже, чем отсортировать иммутабельной сортировкой?
Возможно. Но ведь зачастую в программе одновременно не нужны отсортированные данные и исходные неотсортированные.
Re[7]: Quicksort: краткость записи vs производительность код
Здравствуйте, Aleх, Вы писали:
A>Здравствуйте, samius, Вы писали:
A>>>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается). S>>А если нужны, то что сортировать не надо? В иммутабельных языках довольно сильный реюз данных. Ждать пока данные освободятся для сортировки нет смысла. A>Инплейс сортировкой не надо.
Вот и не сортируются
S>>Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило. A>Да, нет на уровне языка. Но тот же список, например, может быть вполне представлен физически массивом, если под списком обязательно не подразумевать физический список (как на Си), а только интерфейс списка.
Представим список деревьев в физическом массиве. Ты предлагаешь перемешать деревья незаметно для кода, вызывающего сортировку. В случае если программа ссылается на те деревья, то незаметно перемешать их не выйдет.
A>>>Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом. S>>Представь что ты сортируешь деревья по их размеру. После сортировки новые деревья должны вырасти? A>Что значит вырасти? Деревья по структуре остануться теми же, только могут быть расположены в других адресах памяти, что будет незаметно из программы.
Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя.
A>>>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте". S>>А не будет дороже, чем отсортировать иммутабельной сортировкой? A>Возможно. Но ведь зачастую в программе одновременно не нужны отсортированные данные и исходные неотсортированные.
А кто будет разбираться, нужны или нет в конкретном случае?
Re[2]: Quicksort: краткость записи vs производительность код
N>На одном из проектов я сейчас наблюдаю 3-кратное ускорение при переписывании кода с C++ на C# и переходе к immutable структурам данных (к сожалению, не могу сейчас написать детали).
А можно еще привести данные об изменении потребности в памяти ? immutable — оно же не бесплатно.
With best regards
Pavel Dvorkin
Re[8]: Quicksort: краткость записи vs производительность код
Здравствуйте, samius, Вы писали:
S>Представим список деревьев в физическом массиве. Ты предлагаешь перемешать деревья незаметно для кода, вызывающего сортировку. В случае если программа ссылается на те деревья, то незаметно перемешать их не выйдет.
Если ссылается на отдельные деревья, то не выйдет. Если для дальнейшей работы программы нужна только отсорированная совокупность деревьев, то вполне.
К тому же программа теоретически может быть преобразована во время компиляции так, что в списке будут храниться ссылки/указатели на деревья.
S>Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя.
Что значит во время сортировки? Во время сортировки выполняется сортировка, или имеются ввиду многопоточные приложения? Это отдельный вопрос.
S>А кто будет разбираться, нужны или нет в конкретном случае?
Оптимизатор. http://en.wikipedia.org/wiki/Alias_analysis
Re[9]: Quicksort: краткость записи vs производительность код
Здравствуйте, Aleх, Вы писали:
A>Здравствуйте, samius, Вы писали:
S>>Представим список деревьев в физическом массиве. Ты предлагаешь перемешать деревья незаметно для кода, вызывающего сортировку. В случае если программа ссылается на те деревья, то незаметно перемешать их не выйдет. A>Если ссылается на отдельные деревья, то не выйдет. Если для дальнейшей работы программы нужна только отсорированная совокупность деревьев, то вполне. A>К тому же программа теоретически может быть преобразована во время компиляции так, что в списке будут храниться ссылки/указатели на деревья.
Ты предлагаешь создать вспомогательный невидимый массив со ссылками на данные, отсортировать его по месту, а потом по этому массиву создать уже упорядоченный функциональный список?
Да, это будет работать. Проблема лишь в том, что это должно работать в ядре языка, если сам язык не позволяет работать с массивовм напрямую. А все алгоритмы в ядро языка не воткнуть.
S>>Как это может быть не заметно, если программа использует эти деревья? Они же не взялись изниоткуда. Они были созданы неким процессом. Ожидать того что этот процесс "забудет" о всех структурах данных на время сортировки нельзя. A>Что значит во время сортировки? Во время сортировки выполняется сортировка, или имеются ввиду многопоточные приложения? Это отдельный вопрос.
Нет, не многопоточные. Речь была о том, что если сортируются сами данные а не ссылки, то ссылки будут ссылаться на другие данные после сортировки, что ломает иммутабельность.
S>>А кто будет разбираться, нужны или нет в конкретном случае? A>Оптимизатор. http://en.wikipedia.org/wiki/Alias_analysis
Это штука времени компиляции. В рантайме она не ответит на вопрос используемости данных.
Re[5]: Quicksort: краткость записи vs производительность код
Здравствуйте, Aleх, Вы писали:
A>Какие препятствия для сохранения иммутабельности на уровне языка? A>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).
Здравствуйте, 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>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 }
Re[3]: Quicksort: краткость записи vs производительность код
Здравствуйте, Pavel Dvorkin, Вы писали:
N>>На одном из проектов я сейчас наблюдаю 3-кратное ускорение при переписывании кода с C++ на C# и переходе к immutable структурам данных (к сожалению, не могу сейчас написать детали).
PD>А можно еще привести данные об изменении потребности в памяти ? immutable — оно же не бесплатно.
Бесплатно, потому что память нынче бесплатная.
Re[4]: Quicksort: краткость записи vs производительность код
Здравствуйте, Ikemefula, Вы писали:
PD>>А можно еще привести данные об изменении потребности в памяти ? immutable — оно же не бесплатно.
I>Бесплатно, потому что память нынче бесплатная.
С таким подходом у нас скоро появятся программы, для которых не хватит никакого кол-ва памяти.
Ничего бесплатного не бывает. Если на PC потерю 1 — 2 Гб можно не заметить, то на (например) карманном гаджете этого объёма может не найтись.
На сервере может не найтись например 10 Гб. Из личного опыта:
Оптимизировал софтину, которая обрабатывала текстовые отчёты XML-подобного формата (самопальный формат). На очередном отчёте софтине просто не хватило памяти.
Софтина на каждый уровень вложенности открывала тот же самый файл, читала его целико в память (в свой буфер).
Всё сказанное выше — личное мнение, если не указано обратное.
Re[5]: Quicksort: краткость записи vs производительность код
Здравствуйте, Фанатик, Вы писали:
Ф>С таким подходом у нас скоро появятся программы, для которых не хватит никакого кол-ва памяти. Ф>Ничего бесплатного не бывает. Если на PC потерю 1 — 2 Гб можно не заметить, то на (например) карманном гаджете этого объёма может не найтись.
Правильно понимаю, на карманном гаджете ты собрался запускать высоконагруженый сервер ?
Ф>Оптимизировал софтину, которая обрабатывала текстовые отчёты XML-подобного формата (самопальный формат). На очередном отчёте софтине просто не хватило памяти. Ф>Софтина на каждый уровень вложенности открывала тот же самый файл, читала его целико в память (в свой буфер).
Какое это имеет отношение к immutable ?
Re[6]: Quicksort: краткость записи vs производительность код
Здравствуйте, Ikemefula, Вы писали:
Ф>>Оптимизировал софтину, которая обрабатывала текстовые отчёты XML-подобного формата (самопальный формат). На очередном отчёте софтине просто не хватило памяти. Ф>>Софтина на каждый уровень вложенности открывала тот же самый файл, читала его целико в память (в свой буфер).
I>Какое это имеет отношение к immutable ?
Это имеет отношение к бесплатности памяти. И является ярчайшим примером наплевательского отношения к вычислительным ресурсам.
Всё сказанное выше — личное мнение, если не указано обратное.
