рекурсия и итерация

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

Тогда можно и в обходе бинарного дерева сразу выделить кусок памяти размером log_2(N).

Тогда обход дерева станет итеративным?

Прочти уже SICP.

(define (factorial n)
   (if (= n 1)
       1
       (* n (factorial (- n 1)))))

vs

(define (factorial n)
   (fact-iter 1 1 n))

 (define (fact-iter product counter max-count)
   (if (> counter max-count)
       product
       (fact-iter (* counter product)
                  (+ counter 1)
                  max-count)))

Или же

(define (fib n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib (- n 1))
                  (fib (- n 2))))))

vs

(define (fib n)
   (fib-iter 1 0 n))

 (define (fib-iter a b count)
   (if (= count 0)
       b
       (fib-iter (+ a b) a (- count 1))))

Неужели непонятна разница? Развели тут...

Тогда можно и в обходе бинарного дерева сразу выделить кусок памяти размером log_2(N).

да, только не log2(N), а некое log2(N)<= h <= N.

Тогда обход дерева станет итеративным?

безусловно. Вот только нужно выделить либо N памяти, а это вполне может быть и 100Гб, либо обходить всё дерево перед каждым шагом, что-бы узнать текущее значение h. Естественно это можно, и не сложно, вот только работать оно будет медленнее простого списка, а памяти жрать будет больше.

Потому на практике такую итеративную замену никто не использует. А используют машинный стек + машинозависимые костыли для ограничения h + рекурсивный алгоритм обхода на аппаратном стеке.

Неужели непонятна разница? Развели тут...

ну ты правильно на SICP сослался, там есть хорошие и наглядные картинки как раз на эту тему. И объяснение вполне понятное. И ещё и по-русски. Что сразу на ЛОР тащить своё неосиляторство?

Потому на практике такую итеративную замену никто не использует. А используют машинный стек...

В компиляторе Scheme стек совсем не машинный.

Вот только нужно выделить либо N памяти, а это вполне может быть и 100Гб,

Если аналог стека требует 100Гб, то машинный стек гарантировано упадёт с stack overflow.

А аналог я и на файл могу отобразить при очень большом «стеке».

Потому на практике такую итеративную замену никто не использует. А используют машинный стек...

В компиляторе Scheme стек совсем не машинный.

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме? Или велосипедный qsort на схеме?

Если аналог стека требует 100Гб, то машинный стек гарантировано упадёт с stack overflow.

нет. Потому-что машинный стек не нужно _заранее_ выделять.

А аналог я и на файл могу отобразить при очень большом «стеке».

мне жаль твоих пользователей, которые плачут, когда твой 100Гб стек отображаются на их 64Гбый SSD. Особенно это печально, если из 100Гб нужно все 200 байт. Но ты же не думаешь, а «отображаешь»...

Потому-что машинный стек не нужно _заранее_ выделять.

Не понял. Это спасёт при выполнении

int rec_sum(list s)
{
   if(s.next == NULL) return s.data;
   return s.data + rec_sum(s.next, i+1);
}

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме?

Пишут, что здесь: http://www.getkahu.com/

Реализация Scheme под названием Racket

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме?

Пишут, что здесь: http://www.getkahu.com/ Реализация Scheme под названием Racket

покажи мне там скажем красно-чёрное дерево. Ну или qsort.

покажи мне там скажем красно-чёрное дерево

внутри http://pre.racket-lang.org/racket/collects/mred/private/wx/common/rbtree.rkt

Для пользователей: http://planet.racket-lang.org/package-source/krhari/pfds.plt/1/4/planet-docs/...

qsort

С учётом того, что списки там чаще, чем вектора, там сортировка слиянием.

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

внутри http://pre.racket-lang.org/racket/collects/mred/private/wx/common/rbtree.rkt

ну вот и сравни с любой сишной реализацией. Разница в скорости, как у ракеты «Союз» со светом. Да, ракета — быстрая. По сравнению с телегой.

С учётом того, что списки там чаще, чем вектора, там сортировка слиянием.

я знаю. Но многие задачи проще решаются «на месте», а не списком. Эта твоя ракета решает только половину задач? Ну ладно... Не обижайся только, что она никому не нужна.

ну вот и сравни с любой сишной реализацией. Разница в скорости, как у ракеты «Союз» со светом. Да, ракета — быстрая. По сравнению с телегой.

Не факт, на самом деле. Из-за сборщика мусора сишка как раз может оказаться тут телегой.

В сишке нет не то, что сборщика. В нем и памяти-то динамической нет - все библиотеками реализуется. Потому как сделаешь, так и будет.

В сишке нет не то, что сборщика.

Ну да, нету. В этом и проблема - сборщик мусора это ракета, а сишковский маллок - телега.

сишковский маллок - телега.

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

Не факт, на самом деле. Из-за сборщика мусора сишка как раз может оказаться тут телегой.

это если у тебя рукожопие.

Ну да, нету. В этом и проблема - сборщик мусора это ракета, а сишковский маллок - телега.

пиши свой СБИШ или возьми из ракеты. В чём проблема?

это если у тебя рукожопие.

Чтобы сишка не стала телегой придется реализовать тот же сборщик мусора.

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

Чтобы сишка не стала телегой придется реализовать тот же сборщик мусора.

лови:

uint8_t *pool = NULL;
uint8_t *pool_ptr = NULL;

void super_init()
{
  pool = malloc(1048576U*1048576U);
  pool_ptr = pool;
}

void *super_malloc(size_t s)
{
  uint8_t *r = pool_ptr;
  pool_ptr += s;
  return (void*)r;
}

void super_free(void*){}

узнай — какая проблема. А то если я скажу, опять начнёте матом ругаться.

Заебись, а когда память закончится, то что делать?