Здравствуйте, Mazay, Вы писали:
G>>>>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди. G>>>>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.
К>>Эээ, никаких указателей нет, всё что ты можешь со списком по сути — взять голову и/или передвинуться на след. элемент списка.
M>А как в него помещаются элементы? К голове подклеиваются?
Да, именно так. Список однонаправленный, ты можешь подклеивать элементы к голове. При этом, указатель на старый список остается — и у тебя два списка, новый и старый. Все чисто функциональные структуры данных обладают свойством "транзакционности" — а именно, у тебя остается и структура до модификации, и после модификации. Пример со списками.
Есть пустой список. Обозначим его [].
Ты добавил к нему 1. У тебя список [1].
Добавил к голове 2. Получилось [2, 1 ]. Ты запомнил этот список — назовем его А.
Теперь, ты добавляешь к А 3, потом 4. У тебя получается ДВА разных списка, [3,2,1] и [4,2,1], при этом, оба этих списка _разделяют_ общий хвост А. Понятно? Это надо понять.
В обычных языках основная структура данных, на которой строится все — массив, и основной тип их обработки — цикл. В функциональных языках — это список, и основной тип обработки — рекурсия. Ты должен уметь играючи обращаться со списками, если хочешь понять ФЯ и то, как устроены структуры данных Окасаки.
Re[7]: Манипулирование большими структурами данных
Здравствуйте, Mazay, Вы писали:
M>Хм. Может я неправильно понимаю абстракцию списка или задачу? Что значит "средневзвешенная сложность ... равна O(1)" ? Взвешенная по чему? Множитель сложности же игнорируется, как её вообще можно взешивать? Или это подразумевает, что время на get/put может в разных случаях значительно отличаться, но всё ранвно не зависит от N?
Это значит вот что. Ты делаешь 1000 вставок и забираний. И _среднее_ время на каждую из этих операций у тебя примерно одинаково и не зависит
1) От порядка этих вставок и забираний, раз.
2) От того, 1000 их, 10000, или 100000, два.
M> "обход списка через рекурсию" — это O(N) или O(N^2) ?
О(N). Тебе надо ознакомится поближе как минимум с одним ФЯ. Рекомендую Erlang, как самый простой в мире язык вообще, и ФЯ в частности.
Re[2]: Манипулирование большими структурами данных
Здравствуйте, Gaperton, Вы писали:
M>>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?
G>Второй ответ — состоит в оптимизации с single threaded object. Если у тебя есть объект, на который только одна ссылка, то его можно безопасно модифицировать. В Хаскеле это делается посредством монад. Обрати внимание на STAray.
нет в хаскеле такого. а ST — это обычная монада IO с ограниченным подмножеством операций. втч STArray = IOArray
G>Кроме того, есть прием программирования, суть которого — отложить фактическое изменение объекта на потом, чтобы провести все изменения кучей (bulk update), отложив их. Это также выправляет асимптотику.
ээээ, единственное что мне приодит на ум похожего — это подход к обработке структуры данных целиком. скажем, вместо использования хеша для группировки и схожей обработки каких-то данных мы используем сортировку и раюиваем на группы
G>И кроме того, коль скоро у нас все копируется, сам процесс детального проектирования в ФЯ другой. В обычном языке ты озабочен выбором долгоживущей структуры данных, которая обеспечит тебе все сценарии. В ФЯ ты думаешь не так. Коль скоро у тебя все копируется, ты раскладываешь алгоритм на стадии, и выбираешь для каждой стадии наиболее оптимальное представление данных. Таким образом, у тебя нет единой долгоживущей структуры, и ты концентрируешься на алгоритмах, а не структурах данных.
слвершенно верно.
Люди, я люблю вас! Будьте бдительны!!!
Re[10]: Манипулирование большими структурами данных
Здравствуйте, Курилка, Вы писали:
К>Нет, каждый вызов есть переход на 1 шаг, т.к. шагов N, то и сложность O(N) К>Я могу код привести, но если ты с не с одним языком не знаком, то хз на чём К>Ну вот допустим на чём-то сиподобном:
К>
К>A last(List list) { // (1)
К> (Head, Rest) = list.cut_head(); // тут мы список "делим" на "голову" и остаток, в ФП это делается обычно при помощи pattern matching
К> if(Rest.is_empty()) {
К> return Head; // последняя "голова" и есть последний элемент списка
К> } else {
К> return last(Rest);
К> }
К>}
К>
В строчке (1) я вижу передачу параметра по значению. Для списка в N элементов это означает КОПИРОВАНИЕ N элементов. Это при наивной реализации. А если у нас там O(N), значит фактически там передаётся указатель на голову списка, так?
К>В общем — попробуй пописать на каком-нибудь функциональном языке, а то я так совсем элементарные вещи объясняю, лучше их по туториалам смотреть.
Года назад я ковырял Erlang. В своё удовольствие написал многопоточный порт-сканер, сниффер, общалку с реалтековскими свитчами. Всё чуть больше одного экрана кода. Очень круто. Недавно прочитал здешний туториал по Хаскелю и несколько статей с www.ocaml-tutorial.org/ Короче как в ФП предлагается работать со списками я представляю. Неясно другое — сколько это всё стоит.
Главное гармония ...
Re[11]: Манипулирование большими структурами данных
Ой. Очепятка:
M>В строчке (1) я вижу передачу параметра по значению. Для списка в N элементов это означает КОПИРОВАНИЕ N элементов. Это при наивной реализации. А если у нас там O(1), значит фактически там передаётся указатель на голову списка, так?
Здравствуйте, Mazay, Вы писали:
M>Но возникает вопрос — как быть с большими структурами данных? Если мне нужно поменять единственный элемент в большом массиве даных, то неужели мне придётся копировать все элементы, которые остались неизменными?
Я не хочу концентрироваться на списках, лучше посмотреть на хэши (они же словари, они же map...), потому что они более "концептуальны" и желательно их видеть реализованными напрямую в среде.;) Если мы представим себе объект типа hash и представим для него операции типа:
то можно сделать и внутреннее представление newhash как список "модификаций" по сравнению с предыдущим состоянием и ссылку на это предыдущее состояние (как обычная ссылка на неизменяемый объект. Если после этого постановить, что внутреннее представление может меняться при сохранении внешне видимого содержания — мы даём достаточно возможностей среде оптимизировать работу с таким хэшом (оптимизация, вероятно, должна идти в сторону, что при превышении какого-то "порога" доступа к старому содержанию оно таки копируется в новое полностью).
Erlang'овский dict реализует именно эту парадигму, судя по сигнатурам:
с поправкой на стиль (я бы сделал таки множественную добавку в append, а чтобы сигнатура функции сохранялась — сделать кортеж из добавляемых пар значений). Вот насколько эффективно оно сделано — вопрос уже реализации.
И вообще, stdlib в OTP симпатичная — от тупой работы с перебором списка там можно благополучно уйти, сохраняя с одной стороны грамотный функциональный стиль;), а с другой стороны — пользуясь всем богатством придуманных структур данных.
Я с вопросом "а как быть с большой структурой?" столкнулся в софтсвиче в задаче "распарсить дерево раутинга". Там, во-первых, строить связи в дереве — тот ещё цирк. Но у одного раута дохрена атрибутов — сейчас около 40, и дальше предполагается только рост этого богатства. (Конечно, в типичном случае 90% из них имеют дефолтные значения... от этого не легче). И надо итерировать по групповым роутам за дефолтными значениями, в результате получалась или рекурсивная функция на 40+ аргументов (врагу не пожелаешь такое сопровождать), или то же в виде record (не сильно лучше). Через dict — вполне вменяемо и читабельно...
M> (Вообще, доступ к элементам в середине списков в ФЯ выглядит жутковато — судя по коду, приводимому в разных туториалах, требуется перелопатить пол-массива, чтоб добраться до нужного элемента. Я конечно понимаю, что компилятор сможет оптимизировать такой элеметарный случай, но где проходит граница той сложности, при которой компилятор перестанет вмешиваться?)
Ну вот, мне кажется, не надо всё на списках строить. Оно, конечно, неумирающая классика. Но сейчас ФЯ, у которого списки — единственный строительный элемент, выглядит примерно как настоящая машина Тьюринга в железе по сравнению с современным процессором. Построить машину Тьюринга в железе — хорошее развлечение на пенсии, но мне лично ленту жалко.;)
M>В качестве примера можно привести игру Конвея — Жизнь. Погуглив я нашёл пример её реализации, в которой основной цикл выглядел как вот такая функция: M>
M>evaluate w :: World -> World
M>
M>Где World — это тип, включающий в себя описание всей среды Жизни, в том числе большущий двумерный массив с клеточками. Получается, что на каждом шаге происходит копирование всего содержимого этой матрицы.
Случай сильно специфический, всё-таки. В реальном случае (а не когда мы рассматриваем "навигационные огни", "флайер" или столь же мелкие специфические объекты в маленьком кусочке огромного пустого поля) на поле меняют состояние очень много клеток (а пересчитываются — так совсем все). Тут как раз не копирование, а создание наново. Оно должно и отрабатываться соответственно — поодиночке вычисляются новые значения, затем группируются в строки и матрицы. Тут как раз списки хорошо пойдут.
M>В качестве второго примера можно рассмотреть реализацию быстрой сортировки, про которую говорил Gaperton в Q&A
Вариант quicksort на C использует чрезвычайно эффективную технику, изобретенную Хоаром, где массив сортируется на месте, без использования дополнительной памяти. В результате, quicksort на С выполняется быстрее. В противоположность ему, программа на Haskell выделяет «за сценой» достаточно много памяти, и, соответственно, выполняется медленнее.
Так конечно, алгоритм должен быть для такого случая другой. Скорее всего, даже не хоаровская "обменная сортировка с разделением" (она же "быстрая"). "Быстрая" сильно зависит от ряда факторов: обмен местами дёшев; сравнение ещё дешевле; выполняется последовательно одним процессором (иначе бы, например, имело смысл подумать про сортировку Бэтчера); не нужна устойчивость порядка записей с равными ключами... все эти условия в каком-то случае нарушаются, и становится ясно, что quicksort — не панацея.
Я подозреваю (но это навскидку, даже не прицеливаясь), что для среды, ориентированной на списки, сортировка должна быть родственна известным группам алгоритмов "внешней" и "распределяющей" сортировки. Но никак не перестановкой на месте, уж конечно.
M>Хотя пример с Жизнью, мне кажется более общим. M>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?
Ну вот я, кажется, вполне на него ответил;) И начинать надо с определения, какой именно ФЯ — а то для LISP, ML, Erlang и Haskell ответы будут совершенно разными.
The God is real, unless declared integer.
Re[11]: Манипулирование большими структурами данных
Здравствуйте, Mazay, Вы писали:
M>Здравствуйте, Курилка, Вы писали:
К>>Нет, каждый вызов есть переход на 1 шаг, т.к. шагов N, то и сложность O(N) К>>Я могу код привести, но если ты с не с одним языком не знаком, то хз на чём К>>Ну вот допустим на чём-то сиподобном:
К>>
К>>A last(List list) { // (1)
К>> (Head, Rest) = list.cut_head(); // тут мы список "делим" на "голову" и остаток, в ФП это делается обычно при помощи pattern matching
К>> if(Rest.is_empty()) {
К>> return Head; // последняя "голова" и есть последний элемент списка
К>> } else {
К>> return last(Rest);
К>> }
К>>}
К>>
M>В строчке (1) я вижу передачу параметра по значению. Для списка в N элементов это означает КОПИРОВАНИЕ N элементов. Это при наивной реализации. А если у нас там O(N), значит фактически там передаётся указатель на голову списка, так?
Откуда ты вдруг взял передачу по значению? Реально передаются указатели (если язык не совсем дурацкий), но это от тебя скрыто в реализации языка.
Про O(1) — это было для искомой реализации queue, я показал реализацию last для обычного списка, не путай.
К>>В общем — попробуй пописать на каком-нибудь функциональном языке, а то я так совсем элементарные вещи объясняю, лучше их по туториалам смотреть. M>Года назад я ковырял Erlang. В своё удовольствие написал многопоточный порт-сканер, сниффер, общалку с реалтековскими свитчами. Всё чуть больше одного экрана кода. Очень круто. Недавно прочитал здешний туториал по Хаскелю и несколько статей с www.ocaml-tutorial.org/ Короче как в ФП предлагается работать со списками я представляю. Неясно другое — сколько это всё стоит.
Ну возьми тупо померяй или в том же гугле поищи, ну или глянь на не очень любимом тут Language Shootout.
Re[11]: Манипулирование большими структурами данных
Здравствуйте, Mazay, Вы писали:
M>Недавно прочитал здешний туториал по Хаскелю и несколько статей с www.ocaml-tutorial.org/ Короче как в ФП предлагается работать со списками я представляю. Неясно другое — сколько это всё стоит.
Здравствуйте, netch80, Вы писали:
N>Erlang'овский dict реализует именно эту парадигму, судя по сигнатурам:
N>append(Key, Value, Dict1) -> Dict2 N>erase(Key, Dict1) -> Dict2 N>filter(Pred, Dict1) -> Dict2
Эрланговский dict имеет две реализации — первая из которых — линейный список пар ключ-значение, со временем доступа О(N). А второе — сбалансированные деревья, с временем доступа O(log2(N)). Накакой парадигмы "хэша" они не реализуют, это простой map.
Re[3]: Манипулирование большими структурами данных
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, netch80, Вы писали:
N>>Erlang'овский dict реализует именно эту парадигму, судя по сигнатурам:
N>>append(Key, Value, Dict1) -> Dict2 N>>erase(Key, Dict1) -> Dict2 N>>filter(Pred, Dict1) -> Dict2
G>Эрланговский dict имеет две реализации — первая из которых — линейный список пар ключ-значение, со временем доступа О(N). А второе — сбалансированные деревья, с временем доступа O(log2(N)).
Ну вот дешевле чем O(N) уже хорошо (а при каком N реализация на деревьях становится выгоднее?)
G> Накакой парадигмы "хэша" они не реализуют, это простой map.
По крайней мере в моём окружении привычно по-русски эту структуру данных называть "хэш" (видимо, вслед за Perl'ом). Если будет какое-то другое слово без посторонней нагрузки — хорошо бы. А то map даже нормально не переведёшь (а дословно — будет слишком близко к картографии), у словаря своя смысловая нагрузка...
The God is real, unless declared integer.
Re: [F#] Манипулирование большими структурами данных
#light
let a = [1 .. 50]
let rec skipFirstAux i n h t =
if i = n
then (h,t)
else match t with
| [] -> (h,t)
| th::tt -> skipFirstAux (i+1) (n) (h @ [th]) (tt)
// пропускает с списке первых n элеметнов и возвращает кортеж с двумя списками (пропущенные элементы, оставшиеся)
let skipFirst n l = skipFirstAux 0 n [] l
// обновить в списке первый элемент, возвращает измененный список
// f - функция принимает старое значение и возвращает новое
// l - список
let updateFirst f l =
match l with
| [] -> []
| h::t -> (f h) :: t
// обновляем элемент в списке, возвращает измененный список
// n - индекс
// f - функция принимает старое значение и возвращает новое
// l - список
let updateElement n f l =
if n < List.length l
then
let (h,t) = l |> skipFirst n
let ut = t |> updateFirst f
h @ ut
else l
let na = a |> updateElement 49 (fun v -> v * 1000)
print_any na
Хотелось бы, чтобы более опытные коллеги оценили, правильно ли я понял идею.
У меня еще такой вопрос. Оптимизирует ли компилятор обращение к конкретному элементу до O(1)? Или сложность алгоритма так и будет O(N)?
Здравствуйте, Mazay, Вы писали:
M>В качестве примера можно привести игру Конвея — Жизнь. Погуглив я нашёл пример её реализации, в которой основной цикл выглядел как вот такая функция: M>
M>evaluate w :: World -> World
M>
M>Где World — это тип, включающий в себя описание всей среды Жизни, в том числе большущий двумерный массив с клеточками. Получается, что на каждом шаге происходит копирование всего содержимого этой матрицы.
Как раз в игре "жизнь" по-любому придется копировать все поле.
Re[4]: Манипулирование большими структурами данных
Здравствуйте, netch80, Вы писали:
G>>Эрланговский dict имеет две реализации — первая из которых — линейный список пар ключ-значение, со временем доступа О(N). А второе — сбалансированные деревья, с временем доступа O(log2(N)).
N>Ну вот дешевле чем O(N) уже хорошо (а при каком N реализация на деревьях становится выгоднее?)
Не знаю, вероятно речь идет о десятках элементов.
G>> Накакой парадигмы "хэша" они не реализуют, это простой map.
N>По крайней мере в моём окружении привычно по-русски эту структуру данных называть "хэш" (видимо, вслед за Perl'ом). Если будет какое-то другое слово без посторонней нагрузки — хорошо бы. А то map даже нормально не переведёшь (а дословно — будет слишком близко к картографии), у словаря своя смысловая нагрузка...
"ассоциативный массив", или "ассоциативный контейнер". Или просто map. Хэш несет в себе слишком большой дополнительный смысл.
Дело в том, что хеш-таблицы в Эрланге тоже есть, и они дают O(1). Но они "деструктивные", а не функциональные.
Первая из них — словарь процесса, это самое быстрое "деструктивное" хранилище.
Вторая — таблица ets, которая тяжелее, потому что в отличии от словаря процесса всегда копирует данные как при вставках, так и при чтениях (это не касается длинных binaries, которые живут в разделяемом хипе и на них считаются ссылки. Таблица ets существует также в двух вариантах — как сбалансированное дерево и как хэш-таблица. Основное отличие ее от словаря процесса — к ets можно обращаться из нескольких процессов. Это разделяемая ассоциативная память. Почему там все и копируется.
Re[2]: Манипулирование большими структурами данных
Здравствуйте, Gaperton, Вы писали:
M>>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных? G>Краткий ответ — применяются другие структуры данных, построенные не на базе массивов, а на базе списков. Кроме того, ленивые вычисления позволяют в ряде случаев улучшить асимптотику. Смотри список публикаций Криса Окасаки, а также его диссертацию Purely Functional Data Structures.
G>http://www.eecs.usma.edu/webs/people/okasaki/pubs.html
А есть альтернативы Окасаки? Что-нибудь попроще в описании, на пальцах так сказать, применяемый язык, в принципе, не важен. (вон монадных туториалов как грязи, а как структуры — так сразу Окасаки ...)
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
M>>>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?
G>>Второй ответ — состоит в оптимизации с single threaded object. Если у тебя есть объект, на который только одна ссылка, то его можно безопасно модифицировать. В Хаскеле это делается посредством монад. Обрати внимание на STAray.
BZ>нет в хаскеле такого. а ST — это обычная монада IO с ограниченным подмножеством операций. втч STArray = IOArray
Что значит "нет", когда "да". Я практически цитирую сейчас статью Вадлера. STArray и IOArray модифицируются деструктивно, потому что на них гарантируется одна ссылка. Для того, чтобы гарантировать single threadness, применяются монады.
G>>Кроме того, есть прием программирования, суть которого — отложить фактическое изменение объекта на потом, чтобы провести все изменения кучей (bulk update), отложив их. Это также выправляет асимптотику.
BZ>ээээ, единственное что мне приодит на ум похожего — это подход к обработке структуры данных целиком. скажем, вместо использования хеша для группировки и схожей обработки каких-то данных мы используем сортировку и раюиваем на группы
Пример. Ты пробегаешься по массиву, и удваиваешь каждый элемент, который больше пятерки. Если изменять массив на каждой итерации (не прибегая к single-threaded оптимизациям), словишь в худшем случае квадрат. Однако, ты можешь не модифицировать массив, а накопить изменения к нему в списке пар "индекс-значение", после чего, по выходу из цикла (это хвостовая рекурсия — неважно), ты модифицируешь массив одним вызовом updateArray. Все. Асимптотика у тебя сохранилась O(N), при этом, никаких злых фокусов ты не делал.
Собственно, таким образом можно работать со многими структурами, в основе которых лежат массивы. Иногда помогает. Например, если у тебя B-Tree в памяти, и у тебя много последовательных (по возрастанию ключа) модификаций, этот прием тоже сильно поможет.
Re[2]: [F#] Манипулирование большими структурами данных
Я неверное погорячился, написав свой велосипед.
Так будет покороче:
#light
let a = [1 .. 50]
// обновляем элемент в списке, возвращает измененный список
// n - индекс
// f - функция принимает старое значение и возвращает новое
// l - список
let updateElement n f l = l |> List.mapi (fun i v -> if i = n then f v else v)
let na = a |> updateElement 49 (fun v -> v * 1000)
print_any na
Но опять же, получается перебор всего списка..
Re[4]: Манипулирование большими структурами данных
Здравствуйте, Gaperton, Вы писали:
G>>>Второй ответ — состоит в оптимизации с single threaded object. Если у тебя есть объект, на который только одна ссылка, то его можно безопасно модифицировать. В Хаскеле это делается посредством монад. Обрати внимание на STAray.
BZ>>нет в хаскеле такого. а ST — это обычная монада IO с ограниченным подмножеством операций. втч STArray = IOArray
G>Что значит "нет", когда "да". Я практически цитирую сейчас статью Вадлера. STArray и IOArray модифицируются деструктивно, потому что на них гарантируется одна ссылка. Для того, чтобы гарантировать single threadness, применяются монады.
с точки зрения теории — наверно именно так (как и для монад ST/IO вообще), поскольку хаскел у нас чистый ФП. а практичсекая реализация — это просто мутабельный массив. ссылок можешь иметь сколько угодно:
do x <- newArray (0,2) 0
let y=x
writeArray x 0 1
readArray y 0 >>= print
Люди, я люблю вас! Будьте бдительны!!!
Re[8]: Манипулирование большими структурами данных
M>Хотя пример с Жизнью, мне кажется более общим. M>Итак, попробую сформулировать вопрос коротко — Как в функциональных языках делать небольшие изменения больших структур данных?
Сделай дерево, сделай его широким, получишь малое время доступа и малое время перестроения.
Жизнь никто на массивах не делает, если он, конечно, в своем уме.
Ее делают на наборах Set Coords2D (бинарное дерево живых клеток.
Даже на языках, где обновление больших объемов памяти очень эффективно, например, на C/C++.
Что еще? Сортировка?
Так при ленивом quicksort легко быстро получить M первых элементов, и сложность, AFAIK, будет меньше O(NlogN). То есть, "выделение памяти за сценой" оборачивается снижением сложности получения решения. С энергичной быстрой сортировкой такой финт ушами не пройдет.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[11]: Манипулирование большими структурами данных
К>> (Head, Rest) = list.cut_head(); // тут мы список "делим" на "голову" и остаток, в ФП это делается обычно при помощи pattern matching
К>> if(Rest.is_empty()) {
К>> return Head; // последняя "голова" и есть последний элемент списка
К>> } else {
К>> return last(Rest);
К>> }
К>>}
К>>
M>В строчке (1) я вижу передачу параметра по значению. Для списка в N элементов это означает КОПИРОВАНИЕ N элементов. Это при наивной реализации. А если у нас там O(N), значит фактически там передаётся указатель на голову списка, так?
Не надо наивных реализаций, компиляторы неплохо оптимизируют, вот например если переписать код выше на Ocaml:
let rec last l = match l with
| [] -> invalid_arg "error"
| [e] -> e
| h::t -> last t;;
Printf.printf "%d\n" (last [0; 1; 2; 3; 4]);;
превращается в
PUBLIC _camlLast000__last_58
_camlLast000__last_58:
L102:
cmp eax, 1
je L100
mov ebx, DWORD PTR [eax+4]
cmp ebx, 1
je L101
mov eax, ebx
jmp L102
L101:
mov eax, DWORD PTR [eax]
ret
L100:
mov eax, OFFSET _camlLast000__4
jmp _camlPervasives__invalid_arg_40
живых клеток.
