Войти
ФлеймФорумПрограммирование

Функциональщина, односвязные списки: обратный обход (2 стр)

Страницы: 1 2 3 Следующая »
#15
11:37, 27 апр 2010

innuendo
> в основе функциональных языков лежит список
неважно что положено людьми в основу. можно было и двусвязный положить. или массив.
если абстракция не выдерживает требований практики - она останется теоретизированием :-|

#16
11:46, 27 апр 2010

ffinder
> т.е. зачем создавать промежуточный перевернутый список, когда нужно не
> создавать? а если список к тому же еще и длинный?

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

Неизменяемые структуры данных тоже полезны, им тоже есть применение.

#17
11:58, 27 апр 2010

ffinder
> если абстракция не выдерживает требований практики - она останется
> теоретизированием :-|

про хаскель не много знаю, а на lisp много чего написано

#18
13:11, 27 апр 2010

chiaroscuro
> Можно и не создавать, но для этого нужна поддержка изменяемых данных в языке
ну зачем здесь изменяемые данные?
например дано: ListNum
надо получить: ListEven и ListOdd, данные должны быть в прямом порядке (не в перевернутом).
зачем что-то изменять? просто читаем поэлементно начиная с конца, не генерируя перевернутый список.

Поинт не в mutable vs immutable, а в структурах данных пригодных для эффективных вычислений.

#19
13:18, 27 апр 2010

Zefick
> Си вроде не функциональный язык.
Если в функциях Си использовать один return, то Си самый функциональный из всех. (лиспа и хаскелла)

ffinder
> Причем он за собой тянет алгоритмически жуткие решения в ситуациях, когда надо
> эти списки переворачивать/обходить в обратном порядке.
> Это вообще нормально? [b]Как с этим люди живут в реальных условиях?[/b]
На функциональных языках еще ничего не написано(кроме емакса)

#20
13:24, 27 апр 2010

Poki, как я рад что ты пишешь в моей теме :-)))
(а в руках табличка с надписью "САРКАЗМ" !!!)

#21
13:28, 27 апр 2010

Pokimon
> На функциональных языках еще ничего не написано(кроме емакса)
кончай трендеть

#22
16:46, 27 апр 2010

Ну и зачем делать двусвязный (или даже односвязный) список чаров? Для расширения кругозора хочу пример реальный из жизни, где кроме связного списка чаров ну больше вообще никак

#23
16:49, 27 апр 2010

d.m.k
> Для расширения кругозора хочу пример реальный из жизни, где кроме связного списка чаров ну больше вообще никак
Имеем граф из 200 вершин. Стримом нам идёт список рёбер, рёбра существенно кратные. Мы хотим на лету строить полный список соседей.

#24
17:43, 27 апр 2010

Suslik
Ну в таком случае оверхед оправдан от дополнения элементов prev/next полями?

#25
18:03, 27 апр 2010

d.m.k
Конечно, не оправдан. У меня был менее клинический случай, список интов, а не чаров, но добавить связь в ещё одном направлении было бы непозволительно, просто памяти не хватило б.

ПС хотя мне и не надо было как попало его обходить, прямого порядка обхода вполне достаточно.

#26
18:07, 27 апр 2010

Suslik
А чем вывозит тогда связной список? Скоростью вставки, удаления или и того и другого. Можно в таком случае попробовать замудрить компромиссное решение - связной список небольших "пулов", которые работают как массивы (т.е. внутри пула обычная вставка/удаление со сдвигом, но т.к. в пуле не очень много элементов, то это не будет сильно снижать профит, а памяти можно сэкономить.

#27
18:11, 27 апр 2010

d.m.k
> А чем вывозит тогда связной список? Скоростью вставки, удаления или и того и
> другого. Можно в таком случае попробовать замудрить компромиссное решение -
> связной список небольших "пулов"
Я делал пул нодов списка. Память выделяется не для одного нового элемента, а, скажем, для 10Mb нодов и участки памяти под ноды выдаются, пока не кончится. Потом выделяется ещё кусок и так далее. Так не будет полупустых болтающихся пулов, из-за пустоты в которых, кстати, оверхед будет едва ли меньше, чем от ссылки в лишнем направлении.

#28
18:29, 27 апр 2010

ffinder
> т.е. зачем создавать промежуточный перевернутый список, когда нужно не
> создавать? а если список к тому же еще и длинный?
Да у тебя изначально подход императивный, ты думаешь о списке как об объекте, который надо менять.
А функциональный подход - это построение метода трансформации одного объекта в другой.

> неважно что положено людьми в основу. можно было и двусвязный положить. или массив.
> если абстракция не выдерживает требований практики - она останется теоретизированием :-|
Угу, практики у тебя нет, поэтому теоретизируешь о неизвестном:)

#29
19:08, 27 апр 2010

DROnik
> Да у тебя изначально подход императивный, ты думаешь о списке как об объекте,
> который надо менять.
ни разу не думаю. с чего ты взял это вообще?
DROnik
> А функциональный подход - это построение метода трансформации одного объекта в
> другой.
именно, вопрос только во времени этой трансформации.
согласись, что алгоритм со сложностью O(N) всухую сливает алгоритму с O(0).

Страницы: 1 2 3 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.