Мне одному поведение search в sbcl кажется странным?
CL-USER> (defparameter *str* "kill him ")
*STR*
CL-USER> (dotimes (i 10) (setq *str* (concatenate 'string *str* *str*)))
NIL
CL-USER> *str*
"kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him kill him ну и так далее..."
CL-USER> (let* ((counter 0)
(search-result
(search "kill him " *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)
17400
9207
T
Кому лень читать код: здесь введен счетчик, который считает сколько раз search вызвала сравнение(т.е. функцию из :test). И с аргументом :FROM-END T она просматривает всю последовательность от начала до конца.
Я сначала подумал, что это в целях оптимизации, чтобы не гладить оперативку против шерсти. Но на больших последовательностях(как тут 8^10 символов) она ведет себя точно так же как на маленьких...
← Архив: Common Lisp
search in sbcl
oldlisper11.11.2010 01:35
oldlisper11.11.2010 03:47
Именно про возможность такого поведения написано примечание в стандарте:
The implementation may choose to search sequence-2 in any order; there is no guarantee on the number of times the test is made. For example, when start-end is true, the sequence might actually be searched from left to right instead of from right to left (but in either case would return the rightmost matching subsequence).
Конкретно в sbcl есть отдельные функции search для векторов и списков (почти одинаковые, обе просматривают последовательность всегда от начала), и общаяя функция для произвольной последовательности (sequence:search), последняя при :from-end t честно сканирует последовательность начиная с конца. Почему так сделано для списков понятно (их невозможно сканировать с конца), почему для векторов - не знаю, возможно, просто сделали как проще, а сильно оптимизировать тут не было желания/необходимости.
The implementation may choose to search sequence-2 in any order; there is no guarantee on the number of times the test is made. For example, when start-end is true, the sequence might actually be searched from left to right instead of from right to left (but in either case would return the rightmost matching subsequence).
Конкретно в sbcl есть отдельные функции search для векторов и списков (почти одинаковые, обе просматривают последовательность всегда от начала), и общаяя функция для произвольной последовательности (sequence:search), последняя при :from-end t честно сканирует последовательность начиная с конца. Почему так сделано для списков понятно (их невозможно сканировать с конца), почему для векторов - не знаю, возможно, просто сделали как проще, а сильно оптимизировать тут не было желания/необходимости.
oldlisper11.11.2010 04:30
Эм... а в стандарте разве прописано, что списки в коммон лисп реализуются обязательно в виде односвязанных списков? Как это "сильно оптимизировать тут не было желания/необходимости"? Оо Мы ведь о компиляторе говорим...
oldlisper11.11.2010 07:59
>Эм... а в стандарте разве прописано, что списки в коммон лисп реализуются обязательно в виде односвязанных списков?
Списков нет.
Списков нет.
oldlisper11.11.2010 08:01
Я имею ввиду, неужели так сложно было хоть откуда-нибудь узнать, какими основными свойствами обладает семейство языков "лисп"? Что такое cons-яйчейки, и списки, в частности.
oldlisper11.11.2010 09:06
В стандарте не прописано, но он не оставляет иных вариантов.
oldlisper11.11.2010 09:58
Нет, совсем не сложно, более того, я знаю. Это Вы поспешили сделать выводы восприняв то что я написал первым попавшимся способом. Cons ячейки - это интерфейс. Ничто не мешает на уровне компилятора/интерпретатора создать для них совершенно иное представление, например для более эффетивной реализации базовых функций для работы с ними. Хотя я пока еще только изучаю лисп, могу ошибаться...
oldlisper11.11.2010 10:02
Действительно, интересно.
Я не видел кода SBCL, и мог бы предположить, что имеет место избыточное параллельное вычисление. Однако, помусолив код, я вижу, что результаты всегда одинаковы, т.е. вычисление шло в одном потоке.
Так что, думаю, это ошибка (особенность?) реализации (при условии, что единственно верная реализация - однократный проход в правильном направлении с однократным вызовом теста).
P.S. Было бы очень интересно увидеть код функции search. У кого есть, дайте :)
Я не видел кода SBCL, и мог бы предположить, что имеет место избыточное параллельное вычисление. Однако, помусолив код, я вижу, что результаты всегда одинаковы, т.е. вычисление шло в одном потоке.
Так что, думаю, это ошибка (особенность?) реализации (при условии, что единственно верная реализация - однократный проход в правильном направлении с однократным вызовом теста).
P.S. Было бы очень интересно увидеть код функции search. У кого есть, дайте :)
oldlisper11.11.2010 10:09
Фактически, прописано:
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list
oldlisper11.11.2010 11:14
cons-яйчейки это вполне конкретные сущности, и из которых можно делать не только списки, причем.
Списков нет, еще раз.
Списков нет, еще раз.
oldlisper11.11.2010 11:22
В CLHS ясно прописано, что реализации могут просматривать последовательность с любого конца. Но при этом, естественно, возвращать всегда правильный результат(при :from-end, соответственно, самое последнее совпадение)
В сорцах SBCL ясно видно, что последовательности всегда просматриваются от начала.
http://sbcl.cvs.sourceforge.net/viewvc/sbcl/sbcl/src/code/seq.lisp?revision=1.90&view=markup&pathrev=HEAD
В сорцах SBCL ясно видно, что последовательности всегда просматриваются от начала.
http://sbcl.cvs.sourceforge.net/viewvc/sbcl/sbcl/src/code/seq.lisp?revision=1.90&view=markup&pathrev=HEAD
oldlisper11.11.2010 12:04
Функция :test вызывается для каждого элемента (символа) в случае, если предыдущий вызов был успешен.
CL-USER> (defparameter *str* "1234567890")
*STR*
CL-USER> (dotimes (i 16) (setq *str* (concatenate 'string *str* *str*)))
NIL
CL-USER> (length *str*)
655360
Вот подтверждение (да и по исходнику тоже видно):
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search "1" *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
655360
655350
T
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search "12" *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
720895
655350
T
CL-USER> (defvar *str-to-search-for* "123456789012345678901234567890")
*STR-TO-SEARCH-FOR*
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search *str-to-search-for* *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
2555817
655330
T
Вот фрагмент исходника, где видно, что unless будет лупить посимвольно, пока не успокоится:
(when (do ()
((funcall endp1 sequence1 state1 limit1 from-end1) t)
(let ((o1 (funcall key (funcall elt1 sequence1 state1)))
(o2 (funcall key (funcall elt2 sequence2 state2))))
(unless (funcall test o1 o2)
(return nil)))
(setq state1 (funcall step1 sequence1 state1 from-end1))
(setq state2 (funcall step2 sequence2 state2 from-end2)))
(return-from sequence:search s2))))
Поправьте меня, если я ошибаюсь.
CL-USER> (defparameter *str* "1234567890")
*STR*
CL-USER> (dotimes (i 16) (setq *str* (concatenate 'string *str* *str*)))
NIL
CL-USER> (length *str*)
655360
Вот подтверждение (да и по исходнику тоже видно):
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search "1" *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
655360
655350
T
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search "12" *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
720895
655350
T
CL-USER> (defvar *str-to-search-for* "123456789012345678901234567890")
*STR-TO-SEARCH-FOR*
CL-USER> ((lambda()(let* ((counter 0)
(search-result
(search *str-to-search-for* *str*
:FROM-END t
:test (lambda (x y) (incf counter) (char= x y)))))
(print counter)
(print search-result) T)))
2555817
655330
T
Вот фрагмент исходника, где видно, что unless будет лупить посимвольно, пока не успокоится:
(when (do ()
((funcall endp1 sequence1 state1 limit1 from-end1) t)
(let ((o1 (funcall key (funcall elt1 sequence1 state1)))
(o2 (funcall key (funcall elt2 sequence2 state2))))
(unless (funcall test o1 o2)
(return nil)))
(setq state1 (funcall step1 sequence1 state1 from-end1))
(setq state2 (funcall step2 sequence2 state2 from-end2)))
(return-from sequence:search s2))))
Поправьте меня, если я ошибаюсь.
oldlisper11.11.2010 12:38
Списки в SBCL односвязные. Да и в других реализациях, AFAIK. Сделав их двусвязными мы выиграем в сложности некоторых функций (например, last станет O(1)), но получим константный оверхед в некоторых других функциях (например push в конце концов должен будет обновить связь не только со вторым, но и с последним элементом) и общий прирост в количестве использованной памяти (будут хранятся указатели "предыдущий", помимо обычных "следующий").
На самом деле, то что объекты типа cons (+ nil = list) это "односвязный гетерогенный список" - традиция 50 лет. Соответсвенно, все алгоритмы были заточены имено на такой АТД. В принципе, может быть смысл сделать rings - "двусвязный замкнутый гетерогенный список", но отдельно и отдельно для него прорабатывать алгоритмы (можно даже поискать на cliki в библиотеках - может такой АТД уже делался). Конкретно для SBCL ring могут быть бинарно совместимы с cons, т.е. можно будет использовать функции вторых для первых, но так как сами эти АТД весьма разные - вряд ли это того стоит.
Note: "Кольца" во всех отношениях замкнутые алгебраические типы данных без частичных функций, в отличии от "списков". И вообще почетаются в концепциях Total Functional Programming ;)
На самом деле, то что объекты типа cons (+ nil = list) это "односвязный гетерогенный список" - традиция 50 лет. Соответсвенно, все алгоритмы были заточены имено на такой АТД. В принципе, может быть смысл сделать rings - "двусвязный замкнутый гетерогенный список", но отдельно и отдельно для него прорабатывать алгоритмы (можно даже поискать на cliki в библиотеках - может такой АТД уже делался). Конкретно для SBCL ring могут быть бинарно совместимы с cons, т.е. можно будет использовать функции вторых для первых, но так как сами эти АТД весьма разные - вряд ли это того стоит.
Note: "Кольца" во всех отношениях замкнутые алгебраические типы данных без частичных функций, в отличии от "списков". И вообще почетаются в концепциях Total Functional Programming ;)
oldlisper11.11.2010 12:59
> Кольца" во всех отношениях замкнутые алгебраические типы данных
Надо фильтр поставить, что бы всякие еретические слова (типа алгебраических типов данных) сразу резал ;)
Надо фильтр поставить, что бы всякие еретические слова (типа алгебраических типов данных) сразу резал ;)
oldlisper11.11.2010 13:00
> Вот фрагмент исходника, где видно, что unless будет лупить посимвольно, пока не успокоится
Это фрагмент из обобщённой реализации для произвольных (с возможностью добавления пользовательских) последовательностей (пакет sequence в sbcl). Она в случае :from-end t перебирает последовательность с конца (этим занимаются функции step1 и step2 из приведённого тобой фрагмента). Для векторов и списков используется отдельная оптимизированная реализация (см. (sb!xc:defmacro list-search ...) и (sb!xc:defmacro vector-search ...) в seq.lisp). Они всегда просматривают последовательность от начала.
Это фрагмент из обобщённой реализации для произвольных (с возможностью добавления пользовательских) последовательностей (пакет sequence в sbcl). Она в случае :from-end t перебирает последовательность с конца (этим занимаются функции step1 и step2 из приведённого тобой фрагмента). Для векторов и списков используется отдельная оптимизированная реализация (см. (sb!xc:defmacro list-search ...) и (sb!xc:defmacro vector-search ...) в seq.lisp). Они всегда просматривают последовательность от начала.
oldlisper11.11.2010 13:12
> Надо фильтр поставить, что бы всякие еретические слова (типа алгебраических типов данных) сразу резал ;)
Тогда придётся выражаться междометиями (ух! ах! типы данных). Я хотел сказать, что кольца во многих отношениях более выгодные типы данных, но и более "жирные" чем обычные списки.
Тогда придётся выражаться междометиями (ух! ах! типы данных). Я хотел сказать, что кольца во многих отношениях более выгодные типы данных, но и более "жирные" чем обычные списки.
oldlisper11.11.2010 13:45
> Я хотел сказать, что кольца во многих отношениях более выгодные типы данных,> но и более "жирные" чем обычные списки.
Видимо подобная логическая цепочка слишком сложна для меня.
Слушай, ты мне очень одного человека напоминаешь, мы с тобой случайно лично не знакомы?
Видимо подобная логическая цепочка слишком сложна для меня.
Слушай, ты мне очень одного человека напоминаешь, мы с тобой случайно лично не знакомы?
oldlisper11.11.2010 13:55
В двусвязных списках нельзя иметь общую структуру.
oldlisper11.11.2010 14:11
> Видимо подобная логическая цепочка слишком сложна для меня.
В смысле, чем двусвязный замкнутый список лучше чем односвязный линейный?
typedef struct LListNode {
/* node's elements */
struct LListNode *next;
} LList;
и
typedef struct DLListNode {
/* node's elements */
struct DLListNode *next, *prev; /* +1 sizeof(int) */
} DLList;
И какие алгоритмы и функции на втором будут проще выглядеть; а в случае соблюдения условия замкнутости - между левыми/правыми свёртками нет различия (собственно, о чём и вопрос треда).
Вот, но *не* то чтобы кольца были нужны *вместо* линейных списков, их можно прикладывать сами по себе :)
> Слушай, ты мне очень одного человека напоминаешь, мы с тобой случайно лично не знакомы?
Да не, мало ли похожих людей, архитипы всё-таки :) Лично не знакомы.
В смысле, чем двусвязный замкнутый список лучше чем односвязный линейный?
typedef struct LListNode {
/* node's elements */
struct LListNode *next;
} LList;
и
typedef struct DLListNode {
/* node's elements */
struct DLListNode *next, *prev; /* +1 sizeof(int) */
} DLList;
И какие алгоритмы и функции на втором будут проще выглядеть; а в случае соблюдения условия замкнутости - между левыми/правыми свёртками нет различия (собственно, о чём и вопрос треда).
Вот, но *не* то чтобы кольца были нужны *вместо* линейных списков, их можно прикладывать сами по себе :)
> Слушай, ты мне очень одного человека напоминаешь, мы с тобой случайно лично не знакомы?
Да не, мало ли похожих людей, архитипы всё-таки :) Лично не знакомы.
oldlisper11.11.2010 14:12
> общую структуру
Это как?
Это как?
oldlisper11.11.2010 14:18
oldlisper11.11.2010 14:36
А что за функция (previous :: list -> ?) ?
oldlisper11.11.2010 14:41
oldlisper11.11.2010 14:52
> одновременно является хвостом и первого, и второго списка
Почему? Например:
(let* ((a (list 1 2))
(b (cons 3 (rest a))))
(setf (cdr a) '(4))
(format t "a = ~A, b = ~A~%" a b))
;=>
a = (1 4), b = (3 2)
У первого обновилось, на втором не сказалось - это разные списки.
А previous должна иметь тип ring -> ring и иметь законное поведение.
Почему? Например:
(let* ((a (list 1 2))
(b (cons 3 (rest a))))
(setf (cdr a) '(4))
(format t "a = ~A, b = ~A~%" a b))
;=>
a = (1 4), b = (3 2)
У первого обновилось, на втором не сказалось - это разные списки.
А previous должна иметь тип ring -> ring и иметь законное поведение.
oldlisper11.11.2010 14:56
Может всё-таки возможны списки с общими элементами? Этакая лапша из списков, списки-нейросети, etc. :)
oldlisper11.11.2010 14:57
GC этого непереживёт.
oldlisper11.11.2010 15:04
oldlisper11.11.2010 15:08
oldlisper11.11.2010 15:17
Или ещё нагляднее:
CL-USER> (let* ((a (list 1 2))
(b (cons 3 (rest a))))
(format t "a = ~A, b = ~A~%" a b)
(setf (second a) 4)
(format t "a = ~A, b = ~A~%" a b))
a = (1 2), b = (3 2)
a = (1 4), b = (3 4)
NIL
С двусвязными списками/кольцами таких трюков не получится.
Это к тому, что заменить консы на двусвязные списки так прямо нельзя. Но никто не мешает их реализовать отдельно (на тех же структурах к примеру).
CL-USER> (let* ((a (list 1 2))
(b (cons 3 (rest a))))
(format t "a = ~A, b = ~A~%" a b)
(setf (second a) 4)
(format t "a = ~A, b = ~A~%" a b))
a = (1 2), b = (3 2)
a = (1 4), b = (3 4)
NIL
С двусвязными списками/кольцами таких трюков не получится.
Это к тому, что заменить консы на двусвязные списки так прямо нельзя. Но никто не мешает их реализовать отдельно (на тех же структурах к примеру).
oldlisper11.11.2010 17:19
Интересно, не знал про такие штуки. Вроде как, из-за мутабельности тут граф возникает, не дерево.
oldlisper11.11.2010 17:38
Железный человек - чисто наш препод по вышке, долго может так снисходительно (по-доброму) смотреть ;)
oldlisper11.11.2010 20:56
"Фактически, прописано:
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list "
Но опять же это интерфейс.
"Списки в SBCL односвязные. Да и в других реализациях, AFAIK. Сделав их двусвязными"...
Почему сразу двусвязаные списки? Мне кажется оптимальным представлением списков будет некий гибрид, линейная укладка в памяти всего, что можно так уложить. Причем с распознованием того, чем фактически эта списочная структура является(деревом или множеством, например) и видоизменением укладки в зависимости от этого. Так чтобы в реальный список структура вырождалась в самом худшем случае. Ну и, конечно, с прогнозированиеm и хешированием доступа.
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list "
Но опять же это интерфейс.
"Списки в SBCL односвязные. Да и в других реализациях, AFAIK. Сделав их двусвязными"...
Почему сразу двусвязаные списки? Мне кажется оптимальным представлением списков будет некий гибрид, линейная укладка в памяти всего, что можно так уложить. Причем с распознованием того, чем фактически эта списочная структура является(деревом или множеством, например) и видоизменением укладки в зависимости от этого. Так чтобы в реальный список структура вырождалась в самом худшем случае. Ну и, конечно, с прогнозированиеm и хешированием доступа.
oldlisper11.11.2010 21:12
Речь идет о технике CDR coding?
oldlisper11.11.2010 21:19
А в какой задаче надо представлять данные в таком виде? Можно пример?
oldlisper11.11.2010 21:48
"Речь идет о технике CDR coding?"
Ну если не считать, что я только сейчас узнал, что это такое... почти :)
Когда я учился на первом курсе универа мне постоянно нехватало каких-то возможностей в языкax, которы я знал. Про лисп я тогда только слышал и метопгрограммированием для меня была жалкая на него породия, то, что называют этим словом в С++. Ну и я, еще жутко наивный, решил написать небоьлшой язык для свих нужд! :) И откуда во мне было столько энтузиазма? :) Конечно это дело я забросил со временем... На самом деле просто возрасла моя квалификация и я уже не мог смотреть на код, который написал :) - в нем небыло ни одного паттерна, полиморфизма и вообще ничего, что свойственно хорошему коду... И вот до знакомства с lisp я все хотел его переписать :) Код и данные в моей задумке представлялись именно такой вот гибридной структурой. Более того я даже планировал ее перераспределение и дефрагментацию(во время сборки мусора) в зависимости от прогнозируемого времени существования. Фиксированные вектора, конечно, были быстрее нее, но списки(и деревья) она превосходила по всем пунктам, включая pop/push т.к. прогнозировала добавление элементов и в ряде случаев не нужно было выделять память. При этом она очень сильно сжимала данные(не нужно было хранить множество лишних указателей на следующий элемент), позволяла хеширование доступа, например, в предположение того, что доступ в абсолютном большинстве случаев последовательный. И к произвольному элементу доступ так же был значительно быстрее. По крайней мере общая производительность системы возрасла существенно при замене списочного представления кода и данных на это. Причем в ряде случаеев разговор идет о порядках, например, на аналогии лисповых map*, которым передавались небольшие(в плане времени выполнения) функции.
Ну если не считать, что я только сейчас узнал, что это такое... почти :)
Когда я учился на первом курсе универа мне постоянно нехватало каких-то возможностей в языкax, которы я знал. Про лисп я тогда только слышал и метопгрограммированием для меня была жалкая на него породия, то, что называют этим словом в С++. Ну и я, еще жутко наивный, решил написать небоьлшой язык для свих нужд! :) И откуда во мне было столько энтузиазма? :) Конечно это дело я забросил со временем... На самом деле просто возрасла моя квалификация и я уже не мог смотреть на код, который написал :) - в нем небыло ни одного паттерна, полиморфизма и вообще ничего, что свойственно хорошему коду... И вот до знакомства с lisp я все хотел его переписать :) Код и данные в моей задумке представлялись именно такой вот гибридной структурой. Более того я даже планировал ее перераспределение и дефрагментацию(во время сборки мусора) в зависимости от прогнозируемого времени существования. Фиксированные вектора, конечно, были быстрее нее, но списки(и деревья) она превосходила по всем пунктам, включая pop/push т.к. прогнозировала добавление элементов и в ряде случаев не нужно было выделять память. При этом она очень сильно сжимала данные(не нужно было хранить множество лишних указателей на следующий элемент), позволяла хеширование доступа, например, в предположение того, что доступ в абсолютном большинстве случаев последовательный. И к произвольному элементу доступ так же был значительно быстрее. По крайней мере общая производительность системы возрасла существенно при замене списочного представления кода и данных на это. Причем в ряде случаеев разговор идет о порядках, например, на аналогии лисповых map*, которым передавались небольшие(в плане времени выполнения) функции.
oldlisper11.11.2010 23:29
Если речь идёт о map*, то я не могу понять, как односвязный список реализованный через cons-ячейки, связывает руки в плане производительности. Если надо пройтись задом наперед, то (nreverse (my-map* (nreverse (...))), разве нет? Кстати, скорость вставки и удаления произвольного элемента в списке, например, при сортировке, не страдала при хранении замаскированными векторами/хэш-таблицами?
oldlisper12.11.2010 01:41
Я что то не очень понимаю о чем вы говорите. Список, если представлять его каноническим способом - это данные и ссылка на следующий элемент. Хаотичный доступ к памяти, который порождается подобной структурой данных, это оооочень медленно( http://www.ozon.ru/context/detail/id/1418882/ ).
"Кстати, скорость вставки и удаления произвольного элемента в списке, например, при сортировке, не страдала при хранении замаскированными векторами/хэш-таблицами? "
У меня она была значительно быстрей. Чтобы вставить что-либо в n-ую позицию в списке, нужно сначала до этого места добраться, сложность у этого алгоритма - N. А в моей реализации сложность значительно ниже. В худшем случае это был доступ к хешу и вычисление блока и смещения от него. В лучшем случае, если срабатывает "предсказание", то элемент получался сразу же.
Что касается непосредственно операции вставки, когда позиция уже известна, то списки быстрее, но не значительно т.к. двигались элементы в памяти только если этих передвижений требовалось немного. Иначе операция вставки была почти что эквивалента вставке в списке: блок памяти разбивался на две части и элемент оказывался между ними + дополнительно вносилась информация в хеш(формула использовала только сложение и умножение/деление на 2). Это все требует дополнительной памяти, но при этом значительно ее экономит.
Как я уже сказал я так же запланировал оптимизацию структур к которым происходит частый доступ(или которые долго существовали, я тогда так и не решил) во время сборки мусора(это должно было так же улучшить положение), но так эту часть и недоделал.
"Если речь идёт о map*, то я не могу понять, как односвязный список реализованный через cons-ячейки, связывает руки в плане производительности."
Он не связывает руки, но при небольших функциях, переданных map, переписав его можно получить приличный прирост производительности. А если говорить о (nreverse (my-map* (nreverse (...))), то прирост будет просто огромным. Тут при лучшей реализации одно прочтение задом наперед. А в случае с односвязаным списком две записи задом наперед(что хуже), одно прочтение задом на перед, и два прочтения в порядке возрастания адресов. И все это с "путешествиями" по ссылкам. Если конечно не рассмаривать это все исключительно с позиции асимптотического поведения... Ато будет что 2N, что N/2... :)
"Кстати, скорость вставки и удаления произвольного элемента в списке, например, при сортировке, не страдала при хранении замаскированными векторами/хэш-таблицами? "
У меня она была значительно быстрей. Чтобы вставить что-либо в n-ую позицию в списке, нужно сначала до этого места добраться, сложность у этого алгоритма - N. А в моей реализации сложность значительно ниже. В худшем случае это был доступ к хешу и вычисление блока и смещения от него. В лучшем случае, если срабатывает "предсказание", то элемент получался сразу же.
Что касается непосредственно операции вставки, когда позиция уже известна, то списки быстрее, но не значительно т.к. двигались элементы в памяти только если этих передвижений требовалось немного. Иначе операция вставки была почти что эквивалента вставке в списке: блок памяти разбивался на две части и элемент оказывался между ними + дополнительно вносилась информация в хеш(формула использовала только сложение и умножение/деление на 2). Это все требует дополнительной памяти, но при этом значительно ее экономит.
Как я уже сказал я так же запланировал оптимизацию структур к которым происходит частый доступ(или которые долго существовали, я тогда так и не решил) во время сборки мусора(это должно было так же улучшить положение), но так эту часть и недоделал.
"Если речь идёт о map*, то я не могу понять, как односвязный список реализованный через cons-ячейки, связывает руки в плане производительности."
Он не связывает руки, но при небольших функциях, переданных map, переписав его можно получить приличный прирост производительности. А если говорить о (nreverse (my-map* (nreverse (...))), то прирост будет просто огромным. Тут при лучшей реализации одно прочтение задом наперед. А в случае с односвязаным списком две записи задом наперед(что хуже), одно прочтение задом на перед, и два прочтения в порядке возрастания адресов. И все это с "путешествиями" по ссылкам. Если конечно не рассмаривать это все исключительно с позиции асимптотического поведения... Ато будет что 2N, что N/2... :)
oldlisper12.11.2010 01:46
Отправил второй раз с дополнительными пустыми строками, ато получилось совершенно нечитабельно :):
Я что то не очень понимаю о чем вы говорите. Список, если представлять его каноническим способом - это данные и ссылка на следующий элемент. Хаотичный доступ к памяти, который порождается подобной структурой данных, это оооочень медленно( http://www.ozon.ru/context/detail/id/1418882/ ).
"Кстати, скорость вставки и удаления произвольного элемента в списке, например, при сортировке, не страдала при хранении замаскированными векторами/хэш-таблицами? "
У меня она была значительно быстрей. Чтобы вставить что-либо в n-ую позицию в списке, нужно сначала до этого места добраться, сложность у этого алгоритма - N. А в моей реализации сложность значительно ниже. В худшем случае это был доступ к хешу и вычисление блока и смещения от него. В лучшем случае, если срабатывает "предсказание", то элемент получался сразу же.
Что касается непосредственно операции вставки, когда позиция уже известна, то списки быстрее, но не значительно т.к. двигались элементы в памяти только если этих передвижений требовалось немного. Иначе операция вставки была почти что эквивалента вставке в списке: блок памяти разбивался на две части и элемент оказывался между ними + дополнительно вносилась информация в хеш(формула использовала только сложение и умножение/деление на 2). Это все требует дополнительной памяти, но при этом значительно ее экономит.
Как я уже сказал я так же запланировал оптимизацию структур к которым происходит частый доступ(или которые долго существовали, я тогда так и не решил) во время сборки мусора, но так эту часть и недоделал.
"Если речь идёт о map*, то я не могу понять, как односвязный список реализованный через cons-ячейки, связывает руки в плане производительности."
Он не связывает руки, но при небольших функциях, переданных map, переписав его можно получить приличный прирост производительности. А если говорить о (nreverse (my-map* (nreverse (...))), то прирост будет просто огромным. Тут при лучшей реализации одно прочтение задом наперед. А в случае с односторонним списком две записи задом наперед(что хуже) + одно прочтение задом на перед + и два прочтения в порядке возрастания адресов. И все это с "путешествиями" по ссылкам. Если конечно не рассмаривать это все исключительно с позиции асимптотического поведения... Ато будет что 2N, что N/2... :)
Я что то не очень понимаю о чем вы говорите. Список, если представлять его каноническим способом - это данные и ссылка на следующий элемент. Хаотичный доступ к памяти, который порождается подобной структурой данных, это оооочень медленно( http://www.ozon.ru/context/detail/id/1418882/ ).
"Кстати, скорость вставки и удаления произвольного элемента в списке, например, при сортировке, не страдала при хранении замаскированными векторами/хэш-таблицами? "
У меня она была значительно быстрей. Чтобы вставить что-либо в n-ую позицию в списке, нужно сначала до этого места добраться, сложность у этого алгоритма - N. А в моей реализации сложность значительно ниже. В худшем случае это был доступ к хешу и вычисление блока и смещения от него. В лучшем случае, если срабатывает "предсказание", то элемент получался сразу же.
Что касается непосредственно операции вставки, когда позиция уже известна, то списки быстрее, но не значительно т.к. двигались элементы в памяти только если этих передвижений требовалось немного. Иначе операция вставки была почти что эквивалента вставке в списке: блок памяти разбивался на две части и элемент оказывался между ними + дополнительно вносилась информация в хеш(формула использовала только сложение и умножение/деление на 2). Это все требует дополнительной памяти, но при этом значительно ее экономит.
Как я уже сказал я так же запланировал оптимизацию структур к которым происходит частый доступ(или которые долго существовали, я тогда так и не решил) во время сборки мусора, но так эту часть и недоделал.
"Если речь идёт о map*, то я не могу понять, как односвязный список реализованный через cons-ячейки, связывает руки в плане производительности."
Он не связывает руки, но при небольших функциях, переданных map, переписав его можно получить приличный прирост производительности. А если говорить о (nreverse (my-map* (nreverse (...))), то прирост будет просто огромным. Тут при лучшей реализации одно прочтение задом наперед. А в случае с односторонним списком две записи задом наперед(что хуже) + одно прочтение задом на перед + и два прочтения в порядке возрастания адресов. И все это с "путешествиями" по ссылкам. Если конечно не рассмаривать это все исключительно с позиции асимптотического поведения... Ато будет что 2N, что N/2... :)
oldlisper12.11.2010 02:05
Licoris, у вас фундаментальные пробелы в теории (и в практике) Лиспа (причем не CL, а Лиспа в общем) :-)
List это list. Определение на него вам дали, как и на cons. И это не интерфейс который понимаем как поймется, это именно так как прописано в стандарте. И всем изветно, что list'ы "медленные" для досупа в определенных случаях (то что вы ссылаетесь как "сложность O(N)" если нужно 'добраться' до n-ого элемента в списке). Но "медленность" эта возникает из-за того, что используют list`ы для тех типов данных, для которых они не предназначены. Поэтому не нужно испольовать list'ы для данных, где их спользовать не нужно, даже если хочется. В CL ведь не зря ввели arrays, hash tables. Там "сложность O для доступа" совсем другая.
List это list. Определение на него вам дали, как и на cons. И это не интерфейс который понимаем как поймется, это именно так как прописано в стандарте. И всем изветно, что list'ы "медленные" для досупа в определенных случаях (то что вы ссылаетесь как "сложность O(N)" если нужно 'добраться' до n-ого элемента в списке). Но "медленность" эта возникает из-за того, что используют list`ы для тех типов данных, для которых они не предназначены. Поэтому не нужно испольовать list'ы для данных, где их спользовать не нужно, даже если хочется. В CL ведь не зря ввели arrays, hash tables. Там "сложность O для доступа" совсем другая.
oldlisper12.11.2010 02:50
"Licoris, у вас фундаментальные пробелы в теории (и в практике) Лиспа (причем не CL, а Лиспа в общем) :-)"
Очень даже может быть. :) Точнее у меня существенные проблемы с английским, поэтому стандарт я читаю очень выборочно.
Но, вообще говоря, я думал, что прочтения Practical Common Lips достаточно, чтобы хотя бы фундаментальных проблем небыло и из того определения, что "мне дали"(хотя это есть в PCL) т.е. что такое cons, что список - это набор конс ячеек и т.д. следует ничего о том, что должно скрываеться за функциями доступа к cons и функциями представляющими интерфейс списков/деревьев и т.д. И я если честно все равно не вижу причин, почему реализация не может сохранить весь этот интерфейс вплоть до самых низкоуровнеых car и cdr, но использовать хитрости для оптимизации производительности. Хотя я могу действительно чего то недопонимать - я часто сталкиваюсь в жизни с ситуациями, когда аналитических способностей моего мозга не хватает, кроме того я могу чего то еще не знать т.к. стандарт читал очень выборочно по вышеназванной причине.
Очень даже может быть. :) Точнее у меня существенные проблемы с английским, поэтому стандарт я читаю очень выборочно.
Но, вообще говоря, я думал, что прочтения Practical Common Lips достаточно, чтобы хотя бы фундаментальных проблем небыло и из того определения, что "мне дали"(хотя это есть в PCL) т.е. что такое cons, что список - это набор конс ячеек и т.д. следует ничего о том, что должно скрываеться за функциями доступа к cons и функциями представляющими интерфейс списков/деревьев и т.д. И я если честно все равно не вижу причин, почему реализация не может сохранить весь этот интерфейс вплоть до самых низкоуровнеых car и cdr, но использовать хитрости для оптимизации производительности. Хотя я могу действительно чего то недопонимать - я часто сталкиваюсь в жизни с ситуациями, когда аналитических способностей моего мозга не хватает, кроме того я могу чего то еще не знать т.к. стандарт читал очень выборочно по вышеназванной причине.
oldlisper12.11.2010 03:25
Да нету никакого "интерфейса деревьев/списков" у cons-яйчеек. У них есть только интерфейс cons-яйчеек. CAR и CDR.
oldlisper12.11.2010 03:47
В PCL есть глава 12, там есть "дзенский" диалог Мальчика с ложкой и Нео. Там суть "списков".
> почему реализация не может сохранить весь этот интерфейс вплоть до самых низкоуровнеых car и cdr, но использовать хитрости для оптимизации производительности.
Я все равно не очень понимаю, почему вы думаете что cons это интерфейс. И не понимаю ваших выше изложенных путей оптимизаций для lists, потому как то, что я читал выше у вас, что вы понимаете под оптимизацией для ваших задач, соптимизируется в конечном итоге в arrays, hash tables (которые уже есть в CL) под ваши задачи.
P.S. Английский все же выучить очень желательно. Это вообще самый первый язык который должен изучать программист.
> почему реализация не может сохранить весь этот интерфейс вплоть до самых низкоуровнеых car и cdr, но использовать хитрости для оптимизации производительности.
Я все равно не очень понимаю, почему вы думаете что cons это интерфейс. И не понимаю ваших выше изложенных путей оптимизаций для lists, потому как то, что я читал выше у вас, что вы понимаете под оптимизацией для ваших задач, соптимизируется в конечном итоге в arrays, hash tables (которые уже есть в CL) под ваши задачи.
P.S. Английский все же выучить очень желательно. Это вообще самый первый язык который должен изучать программист.
oldlisper12.11.2010 06:31
>не вижу причин, почему реализация не может сохранить весь этот интерфейс вплоть до самых низкоуровнеых car и cdr
Потому что временная сложность операций тоже является частью интерфейса (не знаю, прописанного в clhs или нет, но фактически все ожидают, что car, cdr, cons выполняются за O(1)).
Потому что временная сложность операций тоже является частью интерфейса (не знаю, прописанного в clhs или нет, но фактически все ожидают, что car, cdr, cons выполняются за O(1)).
oldlisper12.11.2010 10:45
> линейная укладка в памяти всего, что можно так уложить.
Т.е. с доступом к n-ому элементу за O(1), это основная цель? Но этим вы создадите массив, а не связный список. У Кнута в первом томе обо всех этих деталях хорошо написано - суть в том, что существуют разные структуры данных и для них одни и те же функции будут работать с разной сложностью. Например в том же STL (и в подобных библиотеках) есть разные типы данных и интерфейсы к ним, которые отличаются буквально в деталях (например хэш-таблицы у которых хэш-функции отличаются) и всё потому что универсальных структур не существует - мы можем выбрать массивы с быстрым доступом, но будем иметь меньше возможностей в динамическом их обновлении, а можем взять связные списки, у которых, например, length или nth имеют линейную сложность.
Я тут выше ошибся - всегда воспринимал списки как соответсвующий АТД, давно cons-ов не рисовал - сами списки, выходит, это просто один из способов использовать cons-ячейки (которые не интерфейс, а сама структура данных), их можно использовать и для представления замкнутых списков (вроде, '#1=(1 2 3 . #1#)) или даже графы (пример elyadow). Так или иначе в CL нет недостатка в различных АТД - есть cons-ячейки (и на их основе - списки, не двусвязные кольца и списки с общими структурами), есть массивы (adjustable и нет), хэш-таблицы (которые в SBCL как раз отличаются хорошей производительностью), и прочие прочие - нет проблем определить какой-нибудь АТД с помощью deftype/defstruct. Вот, и каждый АТД будет уместен для каких-то задач, а где-то - нет.
Т.е. с доступом к n-ому элементу за O(1), это основная цель? Но этим вы создадите массив, а не связный список. У Кнута в первом томе обо всех этих деталях хорошо написано - суть в том, что существуют разные структуры данных и для них одни и те же функции будут работать с разной сложностью. Например в том же STL (и в подобных библиотеках) есть разные типы данных и интерфейсы к ним, которые отличаются буквально в деталях (например хэш-таблицы у которых хэш-функции отличаются) и всё потому что универсальных структур не существует - мы можем выбрать массивы с быстрым доступом, но будем иметь меньше возможностей в динамическом их обновлении, а можем взять связные списки, у которых, например, length или nth имеют линейную сложность.
Я тут выше ошибся - всегда воспринимал списки как соответсвующий АТД, давно cons-ов не рисовал - сами списки, выходит, это просто один из способов использовать cons-ячейки (которые не интерфейс, а сама структура данных), их можно использовать и для представления замкнутых списков (вроде, '#1=(1 2 3 . #1#)) или даже графы (пример elyadow). Так или иначе в CL нет недостатка в различных АТД - есть cons-ячейки (и на их основе - списки, не двусвязные кольца и списки с общими структурами), есть массивы (adjustable и нет), хэш-таблицы (которые в SBCL как раз отличаются хорошей производительностью), и прочие прочие - нет проблем определить какой-нибудь АТД с помощью deftype/defstruct. Вот, и каждый АТД будет уместен для каких-то задач, а где-то - нет.
oldlisper12.11.2010 10:48
А вы можете в коде привести те типы данных о которых говорите как о лучших? А то многабукф, не очень понятно сразу :)
oldlisper12.11.2010 10:49
Насчёт английского я могу немного успокоить: учить весь язык, как это системно делается в школе-вузе, собственно, не надо. Хватит около 200 разговорных слов, массы спец-терминов (они кочуют и в русский, поэтому из считать смысла нет, они нужны в любом случае) и минимум грамматики, чтобы отличать вопросы от утверждений и разобрать границы предложений на запятых.
Так что, всё не так страшно. Мне кажется, работы на месяц. После этого можно читать тех.литературу.
Так что, всё не так страшно. Мне кажется, работы на месяц. После этого можно читать тех.литературу.
oldlisper12.11.2010 10:50
> Но, вообще говоря, я думал, что прочтения Practical Common Lips достаточно
Кстати, CLTL лучше подходит на роль всеобъемлющего руководста. А PCL - просто полезное чтение с упором на Practical.
Кстати, CLTL лучше подходит на роль всеобъемлющего руководста. А PCL - просто полезное чтение с упором на Practical.
oldlisper12.11.2010 11:55
CLTL2 не совместима со стандартом, 1 слишком старая.
Всеобъемлющее это CLHS
Всеобъемлющее это CLHS
oldlisper12.11.2010 12:03
> А PCL - просто полезное чтение с упором на Practical.
PCL достаточно для начала работы, а дальше лучше ориентироваться на исходники других проектов и учиться по ним.
PCL достаточно для начала работы, а дальше лучше ориентироваться на исходники других проектов и учиться по ним.
oldlisper12.11.2010 16:28
"Потому что временная сложность операций тоже является частью интерфейса (не знаю, прописанного в clhs или нет, но фактически все ожидают, что car, cdr, cons выполняются за O(1))."
Ну начнем с того, что в лиспе в любой момент может быть вызван сборщик мусора... И, собственно, это требование не нужно нарушать. Во всяком случае имеет место более точная формулоравка "О(CONST) в худшем случае".
<<В PCL есть глава 12, там есть "дзенский" диалог Мальчика с ложкой и Нео. Там суть "списков".>>
Ну, списки в лисп, как они представляются конс-ячейками - это идеальное олицетворение односвязанного списка, так что смысл этого для меня остался туманным еще во время первого прочтения(как впрочем и второго и третьего, а сейчас я, извините, читать не буду, т.к я просто помню).
"Я все равно не очень понимаю, почему вы думаете что cons это интерфейс."
Потому что это интерфейс, мы работаем с интерфейсом, детали реализации, вообще говоря, нас не интересуют. Мы просто ожидаем конкретного поведения... правильно? А как данные будут уложены в памяти, какие хитрости будут применены и т.д. - это все нас не волнует. Не это ли признаки интерфейса? Например, формально ведь могут быть реализованы потайные типы, видные только самой реализации, например cons внутри списка, cons внутри дерева, просто cons(doted list, кажется) и т.д.
"Т.е. с доступом к n-ому элементу за O(1), это основная цель?"
Неа :) Основная цель - это линейная укладка данных в памяти, это превращает список в вектор только в самом лучшем случае: когда список создан один раз и в него ничего не добавляется и ничего не удаляется. В самом худшем случае эта структура вырождается в список с тем же O(n). Линейная укладка в памяти всего, что МОЖНО так уложить мне нужна была потому как доступ к последовательностям чаще всего последовательный :) Хотя у меня была иная цель, когда я во всем этом ковырялся: меня как раз не устраивало это "либо-либо" я хотел создать просто универсальную структуру с максимально широким интерфейсом, чтобы она имела возможности и стека, и дега, и двусвязанного списка и деревьев и максимально заоптимизировать ее, так чтобы можно было всегда работать только с ней и с хеш таблицами. Я не понимал, почему списки(как у кнута или коремна) должны быть представленны именно так, почему они обязательно дожлны быть медленными - ведь можно сохранить полностью весь их интерфейс, так чтобы человек мог думать о них именно в кнутовсом или корменовсокм понимании, но целиком подменить реализацию на более "интеллектуальную" структуру. Но это, повторюсь, была моя цель именно тогда.
"А вы можете в коде привести те типы данных о которых говорите как о лучших? А то многабукф, не очень понятно сразу :)"
и опять неа :) того уродства, что было написано мной на первом курсе я не покажу, а переписывать слишком долго.
Что касается английского, то моя проблема не в том, что я не могу прочитать, а в том, что скорость чтения уменьшается на порядок(такими темпами гиперспецификация у меня займет пару месяцев) и чтобы это исправить надо заниматься ежедневно и систематично. Не говоря уже о том, что с гиперспецификации иногда встречаются такие обороты, что я обращался к человеку, который владеет разговорным английским и он не мог понять, что там написано.
Ну начнем с того, что в лиспе в любой момент может быть вызван сборщик мусора... И, собственно, это требование не нужно нарушать. Во всяком случае имеет место более точная формулоравка "О(CONST) в худшем случае".
<<В PCL есть глава 12, там есть "дзенский" диалог Мальчика с ложкой и Нео. Там суть "списков".>>
Ну, списки в лисп, как они представляются конс-ячейками - это идеальное олицетворение односвязанного списка, так что смысл этого для меня остался туманным еще во время первого прочтения(как впрочем и второго и третьего, а сейчас я, извините, читать не буду, т.к я просто помню).
"Я все равно не очень понимаю, почему вы думаете что cons это интерфейс."
Потому что это интерфейс, мы работаем с интерфейсом, детали реализации, вообще говоря, нас не интересуют. Мы просто ожидаем конкретного поведения... правильно? А как данные будут уложены в памяти, какие хитрости будут применены и т.д. - это все нас не волнует. Не это ли признаки интерфейса? Например, формально ведь могут быть реализованы потайные типы, видные только самой реализации, например cons внутри списка, cons внутри дерева, просто cons(doted list, кажется) и т.д.
"Т.е. с доступом к n-ому элементу за O(1), это основная цель?"
Неа :) Основная цель - это линейная укладка данных в памяти, это превращает список в вектор только в самом лучшем случае: когда список создан один раз и в него ничего не добавляется и ничего не удаляется. В самом худшем случае эта структура вырождается в список с тем же O(n). Линейная укладка в памяти всего, что МОЖНО так уложить мне нужна была потому как доступ к последовательностям чаще всего последовательный :) Хотя у меня была иная цель, когда я во всем этом ковырялся: меня как раз не устраивало это "либо-либо" я хотел создать просто универсальную структуру с максимально широким интерфейсом, чтобы она имела возможности и стека, и дега, и двусвязанного списка и деревьев и максимально заоптимизировать ее, так чтобы можно было всегда работать только с ней и с хеш таблицами. Я не понимал, почему списки(как у кнута или коремна) должны быть представленны именно так, почему они обязательно дожлны быть медленными - ведь можно сохранить полностью весь их интерфейс, так чтобы человек мог думать о них именно в кнутовсом или корменовсокм понимании, но целиком подменить реализацию на более "интеллектуальную" структуру. Но это, повторюсь, была моя цель именно тогда.
"А вы можете в коде привести те типы данных о которых говорите как о лучших? А то многабукф, не очень понятно сразу :)"
и опять неа :) того уродства, что было написано мной на первом курсе я не покажу, а переписывать слишком долго.
Что касается английского, то моя проблема не в том, что я не могу прочитать, а в том, что скорость чтения уменьшается на порядок(такими темпами гиперспецификация у меня займет пару месяцев) и чтобы это исправить надо заниматься ежедневно и систематично. Не говоря уже о том, что с гиперспецификации иногда встречаются такие обороты, что я обращался к человеку, который владеет разговорным английским и он не мог понять, что там написано.