Возврат значения из замыкания

При стандартизации CL этот вопрос очень долго обсуждался. Решение ИМХО идеально

это решение идеально только в том случае, если забиваем на железо. Т.е. нас не волнует, как там компилятор будет изворачиваться, и какие тормоза получаться в итоге. Ну как это у вас принято.

либо кто-то должен рассказать как сделать с одним for за O(n) по времени и O(1) по памяти.

неужели это как-то возможно? ИМХО никакой такой возможности быть не может.

неужели это как-то возможно?

Возможно, anonymous выше всё правильно сделал (под градусом же, чо), в частности, работоспособность его решения эквивалентна тому, что для любых n и k - (((n - (k + 1) % n) % n + 1) % n + k) % n + k == k (левая часть получается переводом координат ручки и петли туда-сюда).

Consы это не списки, списки можно представить consами, но не наоборот. Тип связного списка это L(a) = 1 + a * L(a), так что всегда будет только одна петля, consы - C = T * T, то есть совсем другая сущность.

Возможно, anonymous выше всё правильно сделал (под градусом же, чо)

вот мне что-то не сообразить, каким образом он этого добился...

Consы это не списки, списки можно представить consами, но не наоборот. Тип связного списка это L(a) = 1 + a * L(a), так что всегда будет только одна петля, consы - C = T * T, то есть совсем другая сущность.

как у вас всё сложно... Просто любой узел любого списка может указывать только на _один_ следующий узел. А если петель больше одной, то очевидно, что один(как минимум) узел должен указывать на больше одного «следующего». Именно потому петель может быть 1 максимум. Ну а вот Cons может указывать на два эл-та, и именно потому им можно делать не только списки.

PS: вот ещё вопрос - правда-ли, что в вашем LISPе всё в cons'ах? А как тогда мне сделать тривиальный массив со скоростью доступа O(1)? В SICP такого не нашёл. NoWay?

правда-ли, что в вашем LISPе всё в cons'ах?

Нет.

А как тогда мне сделать тривиальный массив со скоростью доступа O(1)? В SICP такого не нашёл. NoWay?

вот мне что-то не сообразить, каким образом он этого добился...

http://en.wikipedia.org/wiki/Cycle_detection

А как тогда мне сделать тривиальный массив со скоростью доступа O(1)?

http://www.schemers.org/Documents/Standards/R5RS/r5rs.pdf

http://www.lispworks.com/documentation/lw50/CLHS/Front/Contents.htm

http://en.wikipedia.org/wiki/Cycle_detection

это конечно весело, вот только сколько ждать окончания работы данного алгоритма? Я не сомневаюсь, что заяц нагонит черепаху, вот только боюсь худший случай тут и будет O(N*N), или нет?

http://www.schemers.org/Documents/Standards/R5RS/r5rs.pdf

http://www.lispworks.com/documentation/lw50/CLHS/Front/Contents.htm

ох уж эти лисперы... Даже нормальной документации не осилили. Единственное, что нашёл полезного, дык это /usr/doc/clisp-2.49/doc/LISP-tutorial.txt

Вот что у меня получилось:

[32]> (defun f (a c)
(if (>= c n)
a
(progn
(setf (aref a c) c)
(f a (+ c 1)))))
F
[33]> (setq n 5000)
5000
[34]> (f (make-array n) 0)

*** - Переполнение программного стека. СБРОС
[35]> 

ЗЫЖ или я неправильно готовлю массивы?

А что ты этим вообще хотел показать? Что при глубине рекурсии в 5000 вызовов стэку становится плохо?

вот ещё вопрос - правда-ли, что в вашем LISPе всё в cons'ах? А как тогда мне сделать тривиальный массив со скоростью доступа O(1)? В SICP такого не нашёл. NoWay?

А что тогда споришь о лиспе?

Я не сомневаюсь, что заяц нагонит черепаху, вот только боюсь худший случай тут и будет O(N*N), или нет?

Пусть наше n ─ длина списка и n = i + j, где i ─ длина хвоста ручки, а j ─ размер петли, на ручке будет особая арифметика H[i, j] ⊂ ℕ, на петле ─ L[j] ≅ ℤ/jℤ ⊂ ℕ, то есть обычная арифметика по модулю j, они связаны как x ∈ L[j] ⇒ H[i, j](x + i) ∈ H[i, j] и x ∈ H[i, j] ∧ x ≥ i ⇒ x - i ∈ L[j], где ∀ (x ∈ ℕ)(x ≥ i) H[i, j](x) = L[j](x - i) + i ∈ H[i, j] и ∀ (x ∈ ℕ) L[j](x) = x mod j ∈ L[j].

Теперь, за

T₁ = i

итераций у нас будет

H[i, j](i) = i ∈ H[i, j]
           ~ 0 ∈ L[j]

H[i, j](2 × i + 1) = L[j](i + 1) + i ∈ H[i, j]
                   ~ L[j](i + 1) ∈ L[j]

Дальше, нагоним мы за

T₂ = j - L[j](i + 1)
T₂ ≤ j

итераций в точке

L[j](j - L[j](i + 1)) + i ∈ H[i, j]
~
L[j](j - L[j](i + 1)) ∈ L[j]

Дальше, от этой точки дойдём до узла

L[j](L[j](L[j](j - L[j](i + 1)) + 1) + i) + i ∈ H[i, j] = i ∈ H[i, j]
~
L[j](L[j](L[j](j - L[j](i + 1)) + 1) + i) ∈ L[j] = 0 ∈ L[j]

за

T₃ = i

итераций.

Итого

T = T₁ + T₂ + T₃ = 2 × i + j - L[j](i + 1)

T < 2 × n

O(n)

или я неправильно готовлю массивы?

Вот это неправильно:

clisp

Ну и лучше писать как-то так (declaim и declare ─ только если оно действительно нужно):

(declaim (optimize (speed 3) (debug 0) (safety 0)))

(defparameter *my-array-size* 100000000)
(declaim (type fixnum *my-array-size*))

(defun init-my-array/tail-rec (array &optional (index 0))
  (declare (type fixnum index)
           (type (array fixnum) array))
  (if (>= index *my-array-size*)
      array
      (progn
        (setf (aref array index) index)
        (init-my-array/tail-rec array (1+ index)))))

(time
 (progn
   (init-my-array/tail-rec (make-array *my-array-size* :element-type 'fixnum))
   (values)))

Evaluation took:
  1.189 seconds of real time
  1.177820 seconds of total run time (0.990849 user, 0.186971 system)
  99.07% CPU
  2,371,490,234 processor cycles
  800,000,016 bytes consed

Ещё лучше не писать на CL так как пишут в SICP, то есть свободно использовать императивные конструкции вместо рекурсии ─ do, loop, iterate:

(sb-ext:gc :full t)

(defun init-my-array (array)
  (declare (type (array fixnum) array))
  (loop :for index :from 0 :to *my-array-size*
        :do (setf (aref array index) index)))

(time
 (progn
   (init-my-array (make-array *my-array-size* :element-type 'fixnum))
   (values)))

Evaluation took:
  1.094 seconds of real time
  1.082835 seconds of total run time (0.889864 user, 0.192971 system)
  98.99% CPU
  2,182,572,412 processor cycles
  800,000,016 bytes consed

И после этого кто-то будет утверждать, что алкоголь безусловно вреден=)

(declare (type (array fixnum) array))

(declare (type simple-vector array)) - вот так в три раза быстрее.

Да там просто все... Списки же. Что же с тобой будет при взгляде на алгоритмы на графах ;) ?

ИМХО, но если тебе нужны нормальные кастомные структуры данных и алгоритмы, то ничего лучше С(++) сейчас просто нет. Ассемблер все таки тяжеловат в современном мире. Но вот если у тебя типовая задача, вписывающаяся в типовые концепции, с уже миллион раз сделанными реализациями, то бери какой-нибудь питон и не мучайся. Ну или всякие Java, если больше нравится...

Нет в x86 никаких «операций со стеком». Ты опять за свой тупизм взялся, недоучка. Адресация относительно ESP ничем внутренне не отличается от адресации со сдвигом от любого другого регистра.

А что ты этим вообще хотел показать? Что при глубине рекурсии в 5000 вызовов стэку становится плохо?

ага. По моему это смешно.

(dotimes

это не сахар?

T = T₁ + T₂ + T₃ = 2 × i + j - L[j](i + 1)

спасибо.

Ну и лучше писать как-то так

ну алгоритмически я так и написал. А типы это хорошо, буду знать...

Ещё лучше не писать на CL так как пишут в SICP, то есть свободно использовать императивные конструкции вместо рекурсии ─ do, loop, iterate:

do/loop я и в сишечке могу. Не интересно.

Да, для tagbody+go. Тебе уже говорили.

T = T₁ + T₂ + T₃ = 2 × i + j - (i + 1) % j

Ещё забыл про крайний случай когда j - (i + 1) % j = 0 (mod j), в этом случае T = i.

Три утверждения которые нужно доказать чтобы поверить в подобный результат:

• Заяц догонит черепаху внутри петли.
• Он догонит её всегда во время самого первого прохода черепахи по петле.
• Наконец, точка (x) в которой он её догонит в арифметике ручки связана с узлом (i) соотношением x + i + 1 ≡ i (H[i, j]), то есть независимо от длины петли (j).

loop я и в сишечке могу

loop который из CL?

Не интересно.

А смысл тогда? Писать не идиоматичный код на языке $lang_name? Если говорит про SICP, то её смысл в том, чтобы высветить студенту некоторые идеи, чтобы он потом имел о них представление, но писать мог на чём угодно, оставив лисп и SICP в стороне, там лисп просто потому что он наиболее хорошо иллюстрирует эти самые идеи по сравнению, например, с си - в си за деревьями можно леса не разглядеть. Причём, к тем же идеям можно прийти и без SICP, и иначе. Например, переосмысление SICP в терминах какого-нибудь ML это вообще грех, избиение младенцев и перманентный фейспалм :)

Да, для tagbody+go. Тебе уже говорили.

мне лисп интересен исключительно как bnrainfuck, на котором ВСЁ можно делать одними функциями.

Ещё забыл про крайний случай когда j - (i + 1) % j = 0 (mod j), в этом случае T = i.

это уже не существенно.

loop который из CL?

угу. Но вроде это простая хвостовая рекурсия. Разве нет?

А смысл тогда? Писать не идиоматичный код на языке $lang_name?

смысл что-бы идиоматичный.

например, с си - в си за деревьями можно леса не разглядеть.

можно. Как и в CL, в котором как ваши говорят «программист знает, как сделать всё что угодно, но никогда не знает, сколько это стоит». ИМХО результат работы программы сильно зависит от того, как правильно распарсит компилятор весь этот сахар. Оно вам-то, опытным лисперам хорошо, а мне вот не сообразить, как это всё будет работать. Особенно за сахаром. Тот-же loop превращается сначала и рекурсию, а потом опять в цикл - голову можно сломать с непривычки. Причём в самой простой программе. В сишечке всё проще, там рекурсия это не комильфо, а вот цикл так циклом и остаётся. Ну и нет проблемы Over9000 уровней контекста. Их всего два: внутри функции, и снаружи. Сложно заблудиться.

А что там за идеи в sicp'е? ИМХО, но это курс не для программистов, а для тех, кому нужно получить примерное представление о программировании. Что полезного может извлечь программист из этого курса? Ни алгоритмов, ни структур данных, ни проектирования ПО, хз о чем вообще этот ваш sicp.

Но вроде это простая хвостовая рекурсия. Разве нет?

Тот-же loop превращается сначала и рекурсию, а потом опять в цикл - голову можно сломать с непривычки

Это SICP так влияет на мозги? :)

В качестве BF с ХР лучше уж тогда Haskell брать, в CL рекурсия встречается не чаще чем во всех остальных императивных языках. В tagbody/go/do/dotimes/dolist/loop/iterate нет никакой рекурсии. А loop и iterate это вообще сложные DSLи, можно сказать, они делают множественный unfold/fold последовательностей разных типов, но это будет слишком упрощённо.

Что полезного может извлечь программист из этого курса?

то, что

1. функция - полезная вещь. (примеры присутствуют)

2. списки - полезная вещь. (примеры присутствуют)

3. иногда списков не хватает, можно юзать деревья (примеров нет)

4. всё остальное - не нужно. п1 и п2 достаточно для чего угодно

5. нудятина про «что угодно» из п4.

Ну после того, как gcc наконец научился ХР, то SICP можно рекомендовать к прочтению обычному программисту (с опытом не менее 10 лет). ИМХО.

Ни алгоритмов, ни структур данных, ни проектирования ПО

это всё не нужно.

Это SICP так влияет на мозги? :)

да. Заметно?

В качестве BF с ХР лучше уж тогда Haskell брать, в CL рекурсия встречается не чаще чем во всех остальных императивных языках. В tagbody/go/do/dotimes/dolist/loop/iterate нет никакой рекурсии. А loop и iterate это вообще сложные DSLи, можно сказать, они делают множественный unfold/fold последовательностей разных типов, но это будет слишком упрощённо.

жуть какая...

1. Да. Причем тут SICP?

2. Да. Причем тут SICP?

3. Да. Причем тут SICP?

4. Ложь или троллинг. Это как целые числа представлять Zero и Succ. Можно, но к программированию никакого отношения не имеет. Разве что в compile-time для зависимых типов и т.п., но это совсем другая история...

5. =) Да я читал SICP(лет 7 назад). На какое-то время даже заразился схемой(а потом и другими лиспами), но потом понял, что лисп действительно хорош только как язык конфигурации и/или управления. Как в emacs'е, autocad'е и т.п. Примерно в таком виде и использую в реальной разработке. Жаль только, что guile - тормоз еще тот.

CL никогда не нравился... В планах пристальный взгляд на clojure.

это всё не нужно.

Я боюсь представить себе программиста, которому это все не нужно. Что тогда остается от программирования?

Заметно?

Ну да, «все циклы рекурсией», «все данные cons-ами» и «ОО и модульность на мутабельных замыканиях и символах» это всё идеи которые из SICP особенно не вытаскиваются, они там просто как упрощения, в том же CL есть свои нормальные нативные циклы, разные типы данных и свой CLOS. Про всё остальное (если я не упустил ещё какую-нибудь идею фикс) можно почитать и будет уже более универсально - expression orientation, first-class / higher-order функции, термы как деревья, обработка символьных данных (AST, их преобразования и трансляции, CAS и разные DSL как примеры), порядки вычисления, бутстрап, потоки и ленивые данные, недетерминированное и логическое программирование, эмуляция разной схемотехники и ISA, компиляция, рантайм, GC и про что там ещё пишут.

Непонятно к чему у вас эти зайцы, формулы и т.д.

Флойд ищет длину цикла за линейное время, если известна длина цикла, то его начало ищется за линейное время, O(n) + O(n) = O(n).

Тот-же loop превращается сначала и рекурсию

Не превращается

1. Да. Причем тут SICP?

2. Да. Причем тут SICP?

3. Да. Причем тут SICP?

4. Ложь или троллинг. Это как целые числа представлять Zero и Succ. Можно, но к программированию никакого отношения не имеет. Разве что в compile-time для зависимых типов и т.п., но это совсем другая история...

пункт 4 прямо следует из п1, п2, и п3. Особенно для начинающего быдлокодера. Т.е. создателей SICP кроме функций и списков ничего и не волнует больше. А это подход BrainFuck'а, в котором всего 8 операторов, и можно писать что угодно. Можно, но зачем так извращаться?

Я боюсь представить себе программиста, которому это все не нужно. Что тогда остается от программирования?

И кроме ФП много разного и интересного.

Флойд ищет длину цикла за линейное время, если известна длина цикла, то его начало ищется за линейное время, O(n) + O(n) = O(n).

facepalm

там кубическая сложность по времени и квадратичная сложность по размеру памяти. Но это в общем виде. В нашем частном случае можно просто хранить ВСЕ пройденные узлы, и проверять, попадаем-ли мы в узел, в котором были. Сложность O(N^2) по времени, и O(N) по памяти.

Не превращается

ну вот, и тут меня развели... А я, наивный читатель SICP, думал что у вас так принято...

Ась? Флойд в чистом виде не ищет точку цикла. Он просто определяет, есть ли петля. И делает это за линейное время и константную память. Для определения длины ручки и цикла и нужны «формулы», благодаря которым мы так же можем обойтись константной памятью и линейным временем для поиска точки цикла.

Чего? Откуда там кубическая сложность по времени и квадратичная по памяти? По списку идем линейно(даже если смотреть реально на число проходов, оно никогда не дайдет даже до квадратичной), а память лишнию при этом вообще не выделяем, ее размер для алгоритма не зависит от длины списка.

Чего? Откуда там кубическая сложность по времени и квадратичная по памяти?

ну я думал вы про этот алгоритм: http://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла

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

просто в нашем частном случае список строго линейный, каждый узел имеет ровно одного потомка. Потому память нам нужна только для хранения значений узлов. Если какой-то узел равен текущему, то мы нашли узловую точку. Памяти нам понадобится N, и если эта память - список, то для проверки каждого текущего узла нам понадобится ещё O(N). В итоге, нам понадобится O(N^2) шагов.

Я так и не понял, чем не устраивает реализация анонимуса, которая имеет линейное время и константную память.

Я так и не понял, чем не устраивает реализация анонимуса, которая имеет линейное время и константную память.

которая с зайцами? всем устраивает.

http://stackoverflow.com/questions/4659929/how-to-use-utf-8-in-resource-prope...

Тебе следовало заинтересоваться не лиспом, а лямбда-исчислением в таком случае.

ну вот, и тут меня развели... А я, наивный читатель SICP, думал что у вас так принято...

Ты сам себя развел.

Тебе следовало заинтересоваться не лиспом, а лямбда-исчислением в таком случае.

лямбда-исчисление само по себе == не нужный никому матан. А вот LISP - он вроде иногда даже на практике применяется. Даже в SICP вроде как «жизненные» примеры, хотя ИМХО их ещё на сишечку нужно переписать, а так - только прототипы идеи.

Так перепиши. Я когда читал почти все перевел на С++(на чистом С тяжеловато, все таки)

потом попробую. ИМХО на сишечку смысла нет - передача сообщений ИМХО в C это изначально быдлокод.

там кубическая сложность по времени и квадратичная сложность по размеру памяти.

Флойд работает за линейное время и O(1) по памяти. Я неебу откуда ты взял куб и квадрат.

нашем частном случае можно просто хранить ВСЕ пройденные узлы, и проверять, попадаем-ли мы в узел, в котором были. Сложность O(N^2) по времени, и O(N) по памяти.

Не надо хранить и проверять ничего. Почитай описание алгоритма, позорник.

у вот, и тут меня развели... А я, наивный читатель SICP, думал что у вас так принято...

В SICP про Scheme, а loop - в CL. Это два разных языка, которые имеют намного меньше общего, чем сишка и джава, например.

Ась? Флойд в чистом виде не ищет точку цикла. Он просто определяет, есть ли петля. И делает это за линейное время и константную память.

Точку цикла - не ищет. А вот _длину_ цикла - вполне. И если длина цикла известна, то точка цикла определяется элементарно за те же O(n) по времени и O(1) по памяти (пускаем двух зайцев с лагом в длину цикла, когда попадет на одинаковое значение - это и есть наш цикл).

Бред. Что про SICP, что про явно преувеличенное различие между Scheme и Common Lisp. Незнающие люди прочитают, да еще поверят анониму.