kb
24.07.2012 07:51
Кстати, может я и дебил, но совершенно не понимаю, каким образом к функциональному программированию (да да, тому самому, в котором нету присваивания) прикрепить алгоритм hash-table. В смысле, получается, либо нужен новый тип данных, который как список, только с быстрой операцией "сдвиг на n элементов", либо как-то еще, даже не знаю.
Ну и не могу представить, как можно оптимизировать создание / редактирования всяких там деревьев или списков эффективно. В смысле, функциональный стиль предполагает, что ты будешь каждый раз "строить дерево заново" (при добавлении элемента, например). Никто не может дать ссылку на то, есть ли для таких случаев оптимизации в функциональных языках?
Recommended by:
@ulidtko
25 comments
recommend
bookmark
subscribe
Не понял твоего непонимания касательно hash-table, can you elaborate on that? Про оптимизации для структур ничего не знаю, но есть «Purely Functional Data Structures» Chris Okasaki — возможно, найдёшь ответы там.
читай Окасаки. смотри исходники на Hackage
Ты можешь заюзать часть из предыдущего дерева, например. И ваще, в ФП своя атмосфера^WW свои структуры данных, погугли по finger tree.
Ну, мой узкий мозг пытается реализовать алгоритм hash-table (с его O(1)-сложностью) при помощи структуры данных "пара" и понимает, что добиться этого невозможно, т.к. по сути эффективность hash-table строится на том, что ОС умеет эффективно читать кусочек памяти по заданному сдвигу. Потому фантазия предложила либо специальную пару, у которой будет гарантия единичной сложности взятия n-го элемента, либо же структуру данных "массив", но в структуре данных "массив" не знаю как его перестраивать.
p.s.: всё, что здесь посоветовали сейчас окину взглядом, спасибо.
хеш-таблица классическая (вёдра, в которых список ключ*значение) — да, только копированием всех вёдер делается.
Чистого O(1) не получится, так как нормальная хеш-таблица ресайзит вёдра, чтобы не превращаться в "список". Будет как минимум O(количество_вёдер), если вёдра в типа-массиве, или O(log(количество_вёдер)), если в дереве.
Но вообще хеш-таблица и не обещает O(1) — есть же коллизии в общем случае.
но тут как сказать, "копированием вёдер". Копирования не происходит, обычно просто создаётся другая структура данных, содержащая указатели на старые значения.
конечно, кроме того значения, которое таки надо изменить.
клёво я сам с собой говорю!
ну проблема не в копировании, фиг с ним. проблема в доступе к n-ному элементу.
Блин, ну спасибо. Теперь придётся выбирать, читать дальше SICP главу про concurrency, или бросать его, учить хаскель и читать Окасаки :(
Да, просто у меня все деревья имеют логарифмическую сложность. Короче буду копать Окасаки, видимо, т.к. проще пути понять как это, "дерево с линейной сложностью" не нашёл.
можно реализовать чисто-функциональные массивы, они потребуют поддержки компилятора (т.е. на классических около-фп типах не получится), они могут дать O(1) доступ к элементу по индексу. Правда вот, изменения в чистом фп не будет, будет "создать новый массив на основании старого, но по такому-то индексу будет такой-то элемент".
схему всяко нужно бросать. Книжка SICP хороша, но чисто в плане посмотреть, как-чо.
ну, я понимаю, что при модификации, можно сделать оптимизацию, просто соорудив алгоритм, который максимально быстро отсекает куски, которые останутся неизменными, видимо вышеупомянутый алгоритм так и делает. а вот меня больше интересует эта самая "поддержка компилятора" именно для эффективного доступа.
Чо, нирикаминдуешь? Я уже несколько лет вынашиваю планы по осиливанию схемы просто.
Да там (в SICP), в общем-то, большинство примеров реализовывать в коде либо не нужно, либо невозможно. И благодаря тупости схемы, очень отлично и так читаются (и в голове составляются). Так что за схему я не боюсь.
нельзя просто так взять и отсечь неизменные куски из массива, сохранив O(1) доступ.
А поддержка компилятора — ну, фактически, копирование всего массива, при копировании один элемент заменяется другим. Копируется императивным кодом, конечно.
Или что-то другое интересно?
sicp хорош для почитать, а схема — ну посмотри на её типы, это же ёбаный стыд кококой-то! После х-я тебя как из ушата окатит. Так гадко станет. И обидно.
Если хочешь поломать моск, схему стоит поковырять для изучения continuations. Штука интересная, хоть и редко нужная лично мне (но, может, задачи такие; или просто предпочитаю без "гибкости неописуемой").
я имею в виду некую аналогию (list), только гарантирующую доступ по O(1) для некоторой функции (n-th-elem <n>). например, пусть он называется (arr <size>). оптимизации перестраивания будут аналогичны оптимизациям над списком. то есть полная аналогия, за исключением гарантии скорости доступа к n-ному элементу.
короче, как я и предполагал, есть в схеме структура данных "вектор", являющаяся массивом с эффективным random-access. правда она там mutable, потому без всяких там оптимизаций по перестраиванию и прочему, но уже хоть что-то)
не выйдет фокус. Дело в том, чисто-функциональные структуры могут присутствовать в памяти в куче экземпляров (до, после изменения, после нескольких изменений), и структура, которая обеспечивает это и даёт O(1), это только массив с копированием, насколько мне известно. А копирование — O(n).
ну, насколько я себе представляю, идея оптимизации состоит в том, что в любой момент программа работает только с одной версией твоего массива, а потому "копирование" можно делать только заменой изменяемых элементов, а потому, если твоя функция генерирует из массива A конкатенацию массивов A[0:10] + ["foo"] + A[12:последний] — можно ничего не копировать, а заменить 11й элемент.
возможно, конечно, сделать нечто подобное слишком сложно.
Далекто не факт.
diff arrays
> So if a diff array is used in a single-threaded style, i.e. after // application the old version is no longer used, a'!'i takes O(1) time and a // d takes O(length d). Accessing elements of older versions gradually becomes slower.
Снова на уровне интуиции я угадал. Спасибо.
просто миру нужен функциональный компьютер