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

И что, нельзя это запоминание реализовать в цикле?

нет. В итеративном цикле — нельзя. «Итеративный», это такой, где n+1 выражается *только* через n. А рекурсивный — через (в общем случае) — *всё*. В частности при обходе дерева твой путь зависит от того, где ты *уже* был. второй раз туда же ходить не нужно. Потому нужно на тех ходах ставить крестики. Тем и отличается рекурсия от итерации, в итерации ты просто последовательно перебираешь множество.

Конечно можно сделать в цикле, сделав эмуляцию стека возвратов например массивом. Для бинарного дерева глубиной h достаточно всего h бит.

Тем и отличается рекурсия от итерации, в итерации ты просто последовательно

А кто запрещает прыгнуть назад при переборе?

нет. В итеративном цикле — нельзя. «Итеративный», это такой, где n+1 выражается *только* через n. А рекурсивный — через (в общем случае) — *всё*. В частности при обходе дерева твой путь зависит от того, где ты *уже* был. второй раз туда же ходить не нужно. Потому нужно на тех ходах ставить крестики. Тем и отличается рекурсия от итерации, в итерации ты просто последовательно перебираешь множество.

Тогда ответь на следующие вопросы:

1) поиск в глубину итеративен или рекурсивен?

2) поиск в ширину итеративен или рекурсивен?

3) алгоритм Флойда-Уоршелла итеративен или рекурсивен?

К чему я это все спрашиваю? К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

Это собственно и подтверждает мою мысль.

в итерации ты просто последовательно перебираешь множество.

последовательный перебор множества ты тоже можешь представить «рекурсивной» записью.

(define tst (lambda(lst) (if (not (null? lst)) (do-staff))))

Не, если мы говорим о процессах, то тут несколько иная история. Процесс итеративен, если он зависит только от своего предыдущего состояния и рекурсивен, если от всех предыдущих. Грубо говоря. То, что ты предыдущие состояния запихаешь в свой стек ничего не поменяет - процесс останется рекурсивным.

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

Нет, не превратиться. Подумай о степени роста твоего «состояния».

Нет, не превратиться. Подумай о степени роста твоего «состояния».

Вы имеете в виду рост на реальной машине? Если не на машине а вообще - то процесс линейный и бесконечный, это даже не рост собственно, ну и что?

Нет, не превратиться. Подумай о степени роста твоего «состояния».

И что? Теперь любой прожорливый к памяти алгоритм будем называть от этого рекурсивным?

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

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

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

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

Я осмелюсь даже больше сказать: любые итеративные вычисления являются выражением рекурсии.

Рекурсивного алгоритма.

Совершенно верно.

Не, если мы говорим о процессах, то тут несколько иная история. Процесс итеративен, если он зависит только от своего предыдущего состояния и рекурсивен, если от всех предыдущих. Грубо говоря. То, что ты предыдущие состояния запихаешь в свой стек ничего не поменяет - процесс останется рекурсивным.

Итеративный процесс косвенно все равно зависит от всех предыдущих состояний, иначе как бы он пришел в данную точку. Неважно, сохранено ли каждое состояние в памяти или нет

Тем и отличается рекурсия от итерации, в итерации ты просто последовательно

А кто запрещает прыгнуть назад при переборе?

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

Да? А в двух счетчиках сколько хранится чисел? А в 100?

У тебя какое-то очень извращенное понятие об итерации.

Тогда ответь на следующие вопросы:

у тебя собеседование на носу что-ли? А я значит бесплатный репетитор для тебя?

К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

«итеративный» он будет лишь при наличии дополнительной памяти неизвестного объёма. Потому в кавычках. Без кавычек итеративен лишь алгоритм требующий O(1) памяти.

Естественно стек можно юзать какой угодно, не обязательно тот, что в CPU на esp.

у тебя собеседование на носу что-ли? А я значит бесплатный репетитор для тебя?

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

«итеративный» он будет лишь при наличии дополнительной памяти неизвестного объёма. Потому в кавычках. Без кавычек итеративен лишь алгоритм требующий O(1) памяти.

Вот тут уже хотя бы что-то стало проясняться.

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

в итерации ты просто последовательно перебираешь множество.

последовательный перебор множества ты тоже можешь представить «рекурсивной» записью.

конечно. Ибо итерация — частный случай рекурсии.

о чем вы тут вообще оба? Итерация - это тоже рекурсия.

Ты путаешь понятие рекурсивного алгоритма с понятием рекурсивного процесса. Тебе тут уже объяснили.

А в двух счетчиках сколько хранится чисел? А в 100?

в C счётчиках хранится O(C) === O(1) чисел.

У тебя какое-то очень извращенное понятие об итерации.

у Кнута и в SICP тоже самое. Но вы же не читали...

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

нет, неправильно. Конечно любой алгоритм можно переписать так, что-бы на n шагов он пожрал O(n!) памяти. Дурное дело не хитрое.

Ты путаешь понятие рекурсивного алгоритма с понятием рекурсивного процесса. Тебе тут уже объяснили.

О рекурсивных процессах, кажется, никто не говорил, нет?

нет, неправильно. Конечно любой алгоритм можно переписать так, что-бы на n шагов он пожрал O(n!) памяти. Дурное дело не хитрое.

Что и требовалось доказать =)

у Кнута и в SICP тоже самое. Но вы же не читали...

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

Как тебе тут уже писали, рекурсивный алгоритм может порождать как итерационный, так и рекурсивный процесс. А форма записи(цикл или рекурсивная функция) не важна.

нет, неправильно. Конечно любой алгоритм можно переписать так, что-бы на n шагов он пожрал O(n!) памяти. Дурное дело не хитрое.

Что и требовалось доказать

поймать меня хотел что-ли? Ну не получилось...

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

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

лениво искать.

вот вику почитай: http://ru.wikipedia.org/wiki/Итерация

поймать меня хотел что-ли? Ну не получилось...

Поймать?

Ты писал, что

В смысле? Всегда любую рекурсию можно переписать без оной.

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

А потом сам же пишешь, что можно.

Где там написано, что итерация не может выделять память?

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

А потом сам же пишешь, что можно.

рекурсия отличается от итерации тем, что для рекурсии нужна память, причём её количество может не ограничено расти. А вот для итерации память не нужна. Т.е. для второй и всех остальных нужно ровно столько же памяти, как и для первой.

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

Тут всё зависит от числа вариантов m и шагов n. Если m^n небольшое число, то нет никакой нужды в рекурсии, и можно просто перебрать. Но вот я сейчас перебираю 196627050475552913618075908526912116283103450944214766927315415537966391196809 вариантов — fail. Сейчас пойду спать, и если решения не найдётся, придётся применить рекурсию, вместо итерации. Проблема в том, что я не знаю, сколько есть решений, но очевидно, что в первом миллиарде вариантов решений нет(уже перебрал), потому придётся наверное применить рекурсию, что-бы более экономно выбирать варианты. Рекурсия более «умная», т.к. я могу отсекать те пути, по которым я уже прошёл. Думаю, затратив несколько гигабайт памяти и несколько часов, я смогу просмотреть всё пространство решений, на что в итеративном варианте не хватит не только моей жизни, но и жизни всей вселенной...

Где там написано, что итерация не может выделять память?

а зачем для итерации дополнительная память? Есть формула для вычисления след. числа, что ещё надо? Ну вот например для вычисления 5! вовсе не обязательно вычислять 5,4,3,2,1 и потом перемножать, можно сразу умножать, потому достаточно памяти всего на 2 числа. Но если ты обходишь дерево, тебе нужно по одному биту на каждый поворот(для бинарного дерева, для тернарного уже 2 бита, точнее log2(3)), а таких поворотов столько, сколько высота дерева, а высота вообще говоря неизвестна, и может быть какой угодно.

Кто тебе сказал, что каждая итерация должна вычислять число?

Кто тебе сказал, что каждая итерация должна вычислять число?

а что же она должна вычислять-то?

действие(изменение окружения) не есть число.

а зачем для итерации дополнительная память

То есть код

for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

не является итерацией? Ведь он выделяет память

У тебя не сама итерация выделяет память, а код внутри нее. В случае итерации шаги итерации независимы - можно их совершать один за другим и отбрасывать все, что было на предыдущих.В случае рекурсии так не получается. Не всегда по крайней мере.

а что же она должна вычислять-то?

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

У тебя не сама итерация выделяет память, а код внутри нее.

охлол. Этот код и есть итерация, если что.

Вот этот код, тогда тоже итерация? :

Number ack(m, n)
{
   vector<Number> s;
   while(m!=0 || s.length()>0) {
      if(n==0) m--;
      else {
         s.append(m);
         n = n--;
      }
      if(m==0 && s.length() > 0) {
         m=s.pop();
         m--;
         n = n++;
      }
   }
   return n+1;
}

действие(изменение окружения) не есть число.

а есть ещё что-то? Что-то кроме комбинации чисел? Может есть любовь, радость? Ты рассказывай, а то я же не в курсе.

не является итерацией?

это итерация к которой ты прилепил выделение памяти. Но оно тут не нужно, ибо очевидно, что алгоритму нужно seq.length() памяти, и внутри цикла это предопределённая константа. Т.е. выделение памяти является инвариантным для тела цикла.

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

Да, факториал выше не является истинной рекурсией. Но он являлся-бы, если-бы мне было нужно хранить не все числа, а только некоторые. Или все, но НУЖНО.

Он просто накапливает результат. Каждая итерация не зависит от следующих итераций. В рекурсивном же процессе у тебя будет «стек» промежуточных значений. И именно из них будет состоять память, про которую тебе тут говорят.

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

ну и где я говорил, что «не может быть графом, а только целое число от 3 до 7»?

Этот код и есть итерация, если что.

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

Это рекурсивный процесс.

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

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

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

n = 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))))

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

Это рекурсивный процесс.

В чём тогда отличие рекурсия и итерация (комментарий) от рекурсия и итерация (комментарий) ?

В обоих случаях есть главный цикл. В обоих случаях внутри цикла происходит работа с памятью. В обоих случаях можно заранее вычислить максимальный размер необходимого куска памяти.

Все уже говорилось. Читай SICP, может дойдет.

В том, что у тебя нет стека для промежуточных результатов. Может такое бытовое описание тебя устроит?

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

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

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

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

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

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

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

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

Почему res в

vector<Number> res;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

vector<Number> s;
while(m!=0 || s.length()>0) {
   if(n==0) m--;
   else {
      s.append(m);
      n = n--;
   }
   if(m==0 && s.length() > 0) {
      m=s.pop();
      m--;
      n = n++;
   }
}

считаешь?

В обоих случаях есть главный цикл. В обоих случаях внутри цикла происходит работа с памятью. В обоих случаях можно заранее вычислить максимальный размер необходимого куска памяти.

вопрос «можно/неможно» никого не волнует. В рекурсивном алгоритме память никто заранее не выделяет, она сама выделяется. В итеративном она выделяется один раз. Естественно, любой итеративный алгоритм ты при желании можешь переписать как рекурсивный, выделяя память в любых количествах. Т.к. рекурсия — более общий случай. Обратное неверно, т.к. обход дерева или скажем qsort невозможно переписать в итеративный вид без велосипедной эмуляции стека возвратов для хранения контекстов.

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

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

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

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

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

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

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

То есть

vector<Number> res;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

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

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

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

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

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

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

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

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

В твоем решении нет никаких промежуточных результатов, который ты хранишь в «стеке».

Что понимать под промежуточными результатами? Ну ладно...

vector<Number> res, s;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) {
      if(!found_sorted(s), seq[i])
        res.append(seq[i);
      insert_sorted(s, seq[i]);
   }
}

s определённо промежуточная и динамически выделяемая. Это делает эту функцию рекурсивной?

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

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

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

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

А по-моему, от твоего тугоумия. Не я-то код писал.

Ну и не важно, какой там код, хороший или плохой.

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

по моим понятиям это кривая итерация, записанная как рекурсия. В силу того, что рекурсия более проста и более понятна, такой вариант очень хорош, если конечно объём памяти и скорость не имеют значения.

Потому-что ИМХО если скорость/память не имеет значения, то самое важное — обеспечить максимально понятный код. Т.е. если алгоритм рекурсивный (от математиков), то его и надо записывать в виде рекурсии, как (define (factorial n)(if (= n 0) 1 (* n (factorial (- n 1))))), а не как-то иначе. потому-что преждевременная оптимизация == зло.

А если скорость/память значение имеет, то это совсем иная история.

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

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

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

Это делает эту функцию рекурсивной?

У тебя тут нет функции. А процесс рекурсивным будет тогда, когда ты будешь использовать «раскручивать» ранее накопленные промежуточные результаты. Посмотри на схемки рекурсивных и итеративных процессов в SICP'е.

А на википедии написано: факториал — произведение всех натуральных чисел от 1 до n включительно.

Так что надо

(define (factorial n)
  (for/fold ([res 1]) ([i (in-range 1 n)])
    (* res i)))

О по-моему, от твоего тугоумия. Не я-то код писал.

при чём тут я? Тугодумие у тебя, если ты берёшь как пример чужой код, который не понимаешь. Но для тех, кто в танке, поясню: да, это НЕ итеративный алгоритм, ибо тут нет единого куска памяти, в котором ты работаешь. На каждой итерации выделяется свой фрейм памяти. Т.ч. алгоритм строго говоря рекурсивный, и не оптимальный. Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Ну и не важно, какой там код, хороший или плохой.

«хорошесть» кода зависит от ЯП и от задачи. Это явно не чистая сишечка, а какой-нить пхп. Там такое можно и нужно. Бантик красив на маленькой девочке, а на моей башке будет выглядеть нелепо. Всё зависит от контекста.

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

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

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

когда ты будешь использовать «раскручивать» ранее накопленные промежуточные результаты.

То есть любой калькулятор, использующий стеки данных и операций для обработки скобок и порядка операций также является рекурсивным процессом? Несмотря на то, что машинный стек такой калькулятор использовать не может, так как ему надо два стека.

А ещё любая программа на FORTH'е...

А на википедии написано: факториал — произведение всех натуральных чисел от 1 до n включительно.

на самом деле у факториала есть несколько определений. Вот ещё одно:

n! <= (n-1)! * n; /n > 1/

n! <= 1; /n <= 1/

и это определение даёт более короткий, простой, и понятный код.Который не требует костылей типа for/fold и in-range.

Ты, баття, попой не верти, скажи прямо - ты все еще веришь, что стек «быстрее» произвольного массива?

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

внутри 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

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

и это определение даёт более короткий, простой, и понятный код.

Зависит от стандартной библиотеки.

Или хочешь сказать, что

(define (fact n) (if (> n 1) (* (fact (- n 1)) n) 1))

Читается проще, чем

(define (fact n) (apply * (range 1 n)))

(если уж мы не про производительность, а про читаемость)?

Т.ч. алгоритм строго говоря рекурсивный, и не оптимальный.

Вот она, квинтэссенция маразма - рекурсивный значит выделяющий память. Браво!

Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Твой уровень аргументации просто фееричен. Не важно, хороший это код или плохой, важен твой ответ на вопрос, рекурсивен ли он.

Нет, конечно. Это «руками» организованная рекурсия.

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

В первом случае необходимый кусок памяти, который надо выделить, никак не зависит от данных - надо выделить память для i и на этом все. Во втором случае для каждого набора данный нужно свое определенное количество памяти.

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

Рекурсивный алгоритм не просто работает со стеком - он работает со стеком вполне определенным образом. В частности рекурсивный алгоритм не имеет права выделять стекфреймы «по частям» или эмулировать подобное выделение «руками».

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

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

Сравните схемки:

рекурсивный процесс

итеративный процесс

Понимаете о какой памяти речь идет? О памяти, которую потребуется использовать для организации рекурсивного(линейно- в данном случае) или же итеративного процесса.

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

sicp я прочитал, дальше что?

Тут я вполне рекурсию вижу.

Вот тут не вижу:

while(..){
    void* x = malloc(100);
    ...
}

А emulek говорит, что она есть.

Есть тут рекурсия или нет, зависит от того, для чего ты используешь память. Просто для вычисления на итерации и перехода к следующей или же для самого процесса вычисления. Как-то так. ХЗ как уже формулировать.

То есть любой калькулятор, использующий стеки данных и операций для обработки скобок и порядка операций также является рекурсивным процессом?

естественно. Формула типа 2+2*2 является рекурсивной. Калькулятор тоже. Такое нельзя обработать итерацией, ибо нужно возвращаться, в данном случае нужно вернутся к сложению после умножения, что-бы получить правильный ответ 6.

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

ну тем более — ажно два машинных стека. К тому же, в ZX-Spectrum именно так калькулятор и был реализован (который в EEPROM с Basic) — два стека, один вверх рос, второй навстречу. В обычном, том, что по SP, хранились операторы вроде +,-,*,/, а во втором хранились числа. Обрабатывалось это всё рекурсивной функцией, какой-то INTxx, да, прерывание.

А ещё любая программа на FORTH'е...

да. И почти любая на сишечке (за исключением твоих хэлловорлдов конечно).

ты все еще веришь, что стек «быстрее» произвольного массива?

как он может быть не быстрее, если он железный, а массив == твой велосипед? Разве в твоём процессоре есть инструкция для записи в память по индексу с постдекриментом кроме push? А твои велосипеды в любом случае будут не быстрее.

И это несложно проверить при желании. Вот ты-бы чушь не порол, а взял-бы, и проверил. На своём процессоре.

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

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

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

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

Или хочешь сказать, что (define (fact n) (if (> n 1) (* (fact (- n 1)) n) 1)) Читается проще

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

Если для тебя не так, то поздравляю: у тебя lisp головного мозга.

да.

Нет. В форте совсем другая модель вычислений.

как он может быть не быстрее, если он железный, а массив == твой велосипед?

Стек - это обычная область памяти, такая же, как и массив. По-этому стек ничуть не быстрее массива

В смысле «другая»? Там стек же. Там действительно почти все процессы будут рекурсивными, разве нет?

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

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

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

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

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

как он может быть не быстрее, если он железный, а массив == твой велосипед?

Ну не быдло ли ты? Повторяю вопрос для недоумков: доступ к адресу по смещению от ESP чем-то отличается от доступа по, допустим, EAX?

Разве в твоём процессоре есть инструкция для записи в память по индексу с постдекриментом кроме push?

В моем процессоре, как и в любом, сделанном в последние 15 лет, push раскрывается в точно такую же последовательность uops, как и явный постдекремент регистра.

Вот ты-бы чушь не порол, а взял-бы, и проверил.

Ты, баття, редкостное ничтожество. Я удивляюсь, как ты до сих пор от стыда не повесился? Или тебе реально не стыдно быть настолько самоуверенной некомпетентной шлюхой?

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

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

Вот она, квинтэссенция маразма - рекурсивный значит выделяющий память. Браво!

если ты включишь голову, то поймёшь, что так и должно быть — рекурсивная функция, в отличие от итеративной, работает в персональном окружении(контексте), в этом и есть отличие. А как ты прыгаешь по коду — вопрос десятый, хоть call/ret, хоть loop. Да и ЯП тут не при чём.

Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Твой уровень аргументации просто фееричен. Не важно, хороший это код или плохой, важен твой ответ на вопрос, рекурсивен ли он.

тебе нечего возразить? Сливайся молча. Твоя фееричная демагогия никому не интересна. Как и твоё личное отношение лично ко мне.

sicp я прочитал, дальше что?

самое сложное: понять прочитанное.

А emulek говорит, что она есть.

здесь нет рекурсии. И здесь её нет:

void foo()
{
  foo();
}

Нет. В форте совсем другая модель вычислений.

The mistery of Yoda’s speech uncovered is: Just an old Forth programmer Yoda was

тоже самое, на самом деле. Такая модель очень часто используется внутри компиляторов и интерпретаторов. В железе её тоже часто реализуют. Просто очень непривычно выглядит первое время. Но привыкнуть несложно.

Стек - это обычная область памяти, такая же, как и массив. По-этому стек ничуть не быстрее массива

стек — обычная область памяти, согласен. Но для работы со стеком есть специальные команды и регистры. (sp,bp), позволяющие намного ускорить типичные операции стека(коих всего две — затолкать/вытолкать). Кроме того, есть специальная форма заталкивания/выталкивания регистра ip, которая не имеет аналога для простого массива. Потому сохранять можно не только данные, но и адреса кодов. Именно это и нужно при рекурсии, не просто вернуться, а запомнить _путь_, куда надо возвращаться. Велосипедить это всё указателями на функции или виртуальными функциями — жуткий геморрой и тормоза.

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

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

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

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

В моем процессоре, как и в любом, сделанном в последние 15 лет, push раскрывается в точно такую же последовательность uops, как и явный постдекремент регистра.

пруф будет?

тебе нечего возразить? Сливайся молча. Твоя фееричная демагогия никому не интересна. Как и твоё личное отношение лично ко мне.

Ты же понимаешь, что возразить-то нечего тебе. Ты же отвечаешь не по существу, а бросаешь комментарии по поводу качества кода. Это все равно что говорить, что доказательство в математике неправильное, потому что напечатано на плохой бумаге.

Ошибаешься, здесь рекурсия есть.

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

А брейнфак тогда еще проще, ок.

Ты же отвечаешь не по существу

ответ по существу ты очевидно не осилил. А он выше уже был.

бросаешь комментарии по поводу качества кода. Это все равно что говорить, что доказательство в математике неправильное, потому что напечатано на плохой бумаге.

твои алгоритмы не имеют смысла. В математике это как сокращение дроби на ноль — доказать можно всё что угодно. Но зачем?

Ошибаешься, здесь рекурсия есть.

в каком месте тут рекурсия, если это бесконечный цикл, в котором записывается одно и то же число в последовательные ячейки конечного массива. Тоже самое, что и твой цикл с malloc, только проще и короче.

твои алгоритмы не имеют смысла. В математике это как сокращение дроби на ноль — доказать можно всё что угодно. Но зачем?

Алгоритмы? Мои? Был только сишный код, не мой, который ты так и не можешь толком отнести ни к рекурсивному, ни к интеративному.

foo выражается через саму себя. Вот и рекурсия.

пруф будет?

Замени везде в коде хрень вроде pushl %edi на movl 0(%esp), %edi; addl $1, %esp, и убедись, что разницы в производительности нет.

И это я еще молчу о том, что никто тебе не запрещает использовать esp для своего массива, и игнорировать системный ABI с его стеком вообще.

то есть, movl %edi, 0(%esp)

Конечно проще, ибо смысл операций >,*,- мне знаком со школьной скамьи, а вот что значит операции apply и range я могу только догадываться.

А брейнфак тогда еще проще, ок.

в некотором смысле — проще. Хотя писать на нём и сложнее. Он слишком простой, и тривиальная конструкция там занимает слишком много букв. Можно придумать простой естественный язык, ароде русского мата, но ты устанешь объяснять на этом языке что угодно сложнее «fuck off».

Алгоритмы? Мои? Был только сишный код, не мой, который ты так и не можешь толком отнести ни к рекурсивному, ни к интеративному.

дык мы про код говорим? Тогда я не знаю, что такое «рекурсивный код». Я знаю, что такое «рекурсивный алгоритм».

с т.з. алгоритма нет никакой разницы, что через что выражается. С т.з. алгоритма там безусловный jmp, и запись одного и того же числа в ячейки [sp], [sp-1], [sp-2],... Т.к. число только записывается, и ничего более, то совершенно не важно, что это за число.

Замени везде в коде хрень вроде pushl %edi на movl 0(%esp), %edi; addl $1, %esp, и убедись, что разницы в производительности нет.

на что мне менять call/ret?

то есть, movl %edi, 0(%esp)

это по любому длиннее(особенно с учётом inc/dec), а значит не влезет в кеш. Уже получишь тормоза, чисто из-за раздутого кода.

Ну как нет, если рекурсия по определению - код который вызывает себя.

Можно придумать простой естественный язык, ароде русского мата, но ты устанешь объяснять на этом языке что угодно сложнее «fuck off».

Это не правда, ты значит не русский. Русским матом тривиально объясняется все. И ничего кроме него не нужно. А причина здесь одна: всегда есть контекст употребления слов. В этом и беда ваших строго типизированных языков, что вы шага не можете сделать без пояснения что-есть что.

А если с выводом типа?

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

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

на что мне менять call/ret?

Посмотри, как это сделано в ARM, где никаких call и ret нет в принципе.

нет.

там фишка в ныне ставшим модном «рефакторинге»

ну и уберфича - управление потоком управления через манипуляции со стеком возврата ( а уж переустнаовка 2 стеков (данных,адрессов) даём многозадачность)

уберфича в том что командной можно расширить язык до любой конструкции управления ибо команда может произвольно манипулировать стеком возвратов.

в компиляторах/интерпретаторах редко когда прямо манипулируют со стеком возвратов

Это не правда, ты значит не русский. Русским матом тривиально объясняется все. И ничего кроме него не нужно.

ТОЛЬКО русским матом ты не сможешь почти ничего КОНКРЕТНОГО объяснить. Кроме эмоций. Да, иногда этого достаточно. Но в этом случае можно и промолчать. Чё пи**ть попусту?

Алгоритмы — сплошная конкретика, и ты слишком много сил потратишь для изготовления конкретного float'а на BF'е. Попробуй, если не веришь. Нет, я знаю, что это возможно, и это не сложно. Но очень долго.

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

всё зависит от задачи. Иногда без этого никак, иногда это только мешает.

Ну как нет, если рекурсия по определению - код который вызывает себя.

ок. Это будем считать рекурсией кода. А моё определение (которое я выдрал из SICP) — определение рекурсивного алгоритма.

Так без вопросов?

Повторюсь (а то аноны опять своим срачем половину постов убили): я считаю рекурсивным такой алгоритм, который выполняет итерации в своём контексте. Т.е. рекурсия — это развитие и обобщение итераций, мы не просто повторно используем алгоритм, а используем его как-то по новому. К примеру, при обходе дерева, ключевое значение имеет то, _какую_ ветвь мы обошли, левую, или правую. Если обход центрирован, то после левой надо обходить корень, а потом правую ветвь, а если ветка правая, то мы эти ветки и этот корень уже обошли, и надо валить отсюда вверх. Т.е. алгоритм зависит от данных. А при чистой итерации алгоритм не зависит, просто числа меняются.

Это все соплями по говну рассусоливание.

Ты как, успокоился?

Если да, то похмелись, и попытайся понять: Изначально я говорил про автоматические переменные в сишечке. Компилятор вовсе не обязательно их пихает в стек. В современных CPU amd64 и регистров полно, а регистры понятно быстрее(глупо с этим спорить, да). Туда и пихает.

Т.е. автоматические переменные в сишечке пихаются в регистры и/или в стек, в зависимости от того, что быстрее(в целевом CPU). Есть два следствия:

1. т.к. основные переменные критичные по времени лежат в регистре/стеке, то вся программа работает обычно в разы быстрее. Доступ к регистром в разы быстрее. Доступ к стеку несколько быстрее потому, что он всегда в кеше, но важно то, что освобождение/выделение памяти стека практически мгновенно, по сравнению с любым GC.

2. п1 это хорошо, но что плохо, эти переменные не разруливаются GC. Невозможно вернуть в пул то, чего там никогда не было. А регистров/стека там никогда не было. Потому в сишке нельзя сделать «полноценный» GC. Это плата за наличие быстрых переменных, которые в регистрах и/или в самой быстрой памяти (в стеке, для некоторых CPU).

Ты не обязан платить такую цену, если хочешь, делай ВСЕ свои переменные своим аллокатором. И они будут убираться твоим любимым GC. Как в любимой яве/пхп/сишарп.

На хрена вывод типа, если есть контекст.

ИМХО это фильтрует огромное количество глупых ошибок/опечаток. А в каком-нить пыхпыхе оно само всё сконвертит куда угодно, и потом будешь удивляться, как сумма 3х лестниц с 2я дорогами даёт 17 облаков и 3х лошадок. В сишечке нельзя складывать лестницы с дорогами в любом контексте.

В сишечке нельзя складывать лестницы с дорогами в любом контексте.

4.2. Кастуешь их обоих к голубям и складываешь.

В сишечке нельзя складывать лестницы с дорогами в любом контексте.

2+2.0 - сложение целого с вещественным. И не надо подводить под одно понятие динамическую и слабую типизацию. Сильная типизация в динамических языках как раз и нужна, чтобы не складывать 3 лестницы с 2я дорогами.

тоже самое, на самом деле.

Нет не то же самое. Ты просто не знаешь форта.

Но для работы со стеком есть специальные команды и регистры. (sp,bp), позволяющие намного ускорить типичные операции стека

Нет. Всмысле команды есть - но ничего они не ускорят, тем более «намного».

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

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

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

Доступ к стеку несколько быстрее потому, что он всегда в кеше, но важно то, что освобождение/выделение памяти стека практически мгновенно, по сравнению с любым GC.

Память в стеке выделяется точно так же, как в перемещающем GC.

п1 это хорошо, но что плохо, эти переменные не разруливаются GC. Невозможно вернуть в пул то, чего там никогда не было. А регистров/стека там никогда не было. Потому в сишке нельзя сделать «полноценный» GC. Это плата за наличие быстрых переменных, которые в регистрах и/или в самой быстрой памяти (в стеке, для некоторых CPU).

Ты ведь просто не понимаешь как работают сборщики мусора, да? Им совершенно похер где у тебя что лежит - в регистрах, на стеке, в хипе.

А ты забываешь про jit, который сам по себе не бесплатен и оправдывает себя не всегда. И да, llvm, пара плагинчиков для clang'а и соответствующий рантайм и будет у тебя ЛЮБОЙ GC. Вот только невостребован он в С и даже в С++, там немного другой подход к разработке - в Си в каждом проекте свой подход, в С++ - тоже, хотя и большинству проектов хватает подсчета ссылок(иногда вместе с детектором циклов) - shared_ptr и weak_ptr, в отличие от сборщиков, это позволяет хотя бы ресурсы различные вовремя отдавать и без всяких костыликов вроде finally.

А ты забываешь про jit

Джит никак не связан со сборщиком мусора.

И да, llvm, пара плагинчиков для clang'а и соответствующий рантайм и будет у тебя ЛЮБОЙ GC.

Не будет.

4.2. Кастуешь их обоих к голубям и складываешь.

для быдлокодера любой ЯП годен

2+2.0 - сложение целого с вещественным.

и что тут такого страшного? Это сложение вещественного и вещественного.

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

типизация в сишечке не слабая, целое число без потерь преобразуется в вещественное. Целое — частный случай вещественного.

Сильная типизация в динамических языках как раз и нужна, чтобы не складывать 3 лестницы с 2я дорогами.

угу, потому-что если дорога выглядит как лестница, крякает как лестница, то это лестница. Т.ч. пишем к дороге метод view() и kru(), как в лестнице, и она становится лестницей. С которой мы и складываем другие лестницы, получая облака и крякающих лошадок.

А потом все рассказываем, какое C/C++ говно, потому-что там так нельзя. А типизация слабая, ибо число 2 является вещественным в контексте вещественных чисел. А почему не так-то? Разве теперь множество вещественных чисел уже не включает целые?

Разве теперь множество вещественных чисел уже не включает целые?

Не включает и никогда не включало. Целые числа - это классы эквивалентностей пар натуральных, вещественные числа - классы эквивалентностей фундаментальных последовательностей пар классов эквивалентностей троек натуральных.

Всмысле команды есть - но ничего они не ускорят, тем более «намного».

тогда представь мне аналоги команд push/pop и call/ret, и я проверю скорость работы твоих аналогов. Ну например для x86, 32 бита.

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

лови:

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*){}

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

Память в стеке выделяется точно так же, как в перемещающем GC.

а затраты времени на перемещение в перемещающем GC ты конечно не считаешь, да? Он у тебя с помощью магии перемещает? REP MOVS для дебилов, да?

Ты ведь просто не понимаешь как работают сборщики мусора, да? Им совершенно похер где у тебя что лежит - в регистрах, на стеке, в хипе.

не понимаю. Объясни. Желательно с примером.

Не включает и никогда не включало. Целые числа - это классы эквивалентностей пар натуральных, вещественные числа - классы эквивалентностей фундаментальных последовательностей пар классов эквивалентностей троек натуральных.

у вас на Марсе другая арифметика? Перевод на земной язык будет?

И да, как вы там на Марсе обходитесь без единицы в своих вещественных числах? Соотношение e^{i \pi} + 1 = 0 не работает?

Не включает и никогда не включало.

Первый курс, теория чисел. Enjoy.

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

При чем тут перемещение, если речь велась о выделении памяти?

Что тебе объяснить? иди и прочитай любой алгоритм сборки.

у вас на Марсе другая арифметика?

При чем тут Марс?

Перевод на земной язык будет?

Оно и было на земном, русском языке. Классическое определение целых и вещественных чисел. Обычно это все на первом курсе матфака проходят.

И да, как вы там на Марсе обходитесь без единицы в своих вещественных числах?

Там есть единица. Эта последовательность, эквивалентная 1, 1, 1, ...

Соотношение e^{i \pi} + 1 = 0 не работает?

Это соотношение как раз и задается в вещественных. Точнее - в комплексных. Единица и ноль тут комплексные, а никакие целые.

Ебанашка, ты зачем же пытаешься говорить о том, в чем не смыслишь? Теория чисел занимается целыми числами. И, да, это один из самых сложных разделов математики, на первом курсе его никто не проходит, потому что нужна нехуевая база из алгебры, топологии, матана, функана, комплексного анализа и т.д. чтобы просто понимать о чем идет речь.

Теория чисел занимается целыми числами.

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

Определения целых/рациональных/вещественных обычно проходят на первой-второй лекции матана. Но ты этих определений не знаешь.

как и основы теории чисел.

основы теории чисел, которые можно проходить на первом курсе, имеют примерно такое же отношение к теории чисел как арифметика к гомологической алгебре.

Определения целых/рациональных/вещественных обычно проходят на первой-второй лекции матана.

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

основы теории чисел, которые можно проходить на первом курсе, имеют примерно такое же отношение к теории чисел как арифметика к гомологической алгебре.

Нет.

При чем тут перемещение, если речь велась о выделении памяти?

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

эти посты писали разные люди, или один идиот?

Нахрена вам вообще это красование знанием терминов математики. Лари Уолл, гуманитарий, спроектировал ЯП, Джордж Буш джуниор с ай кью меньше средней домохозяйки стал президентом. А вам что поанонировать на терминологию хочется? Какой толк от ваших матанов, если в жизни другие вещи рулят? Задротство?

Какой толк от ваших матанов, если в жизни другие вещи рулят?

Криптография, например.

Ну и чо криптграфия? Чо криптографы короли мира чтоли? Если бы математика давала ощутимый профит, математики были бы особой кастой брахманов давно уже. А жизнь этого не подтверждает какбэ. Зато подтверждает, что чем математик умней, чем больше шансов закончить в дурдоме.

Это соотношение как раз и задается в вещественных. Точнее - в комплексных. Единица и ноль тут комплексные, а никакие целые.

вот в этом и фишка. На самом деле, int и float — это никакие не вещественные и не целые числа. Это просто модели представления ЧИСЕЛ(вообще) внутри компьютера. Int НЕ эквивалентно целым, а float НЕ эквивалентно вещественным. Мало того, эквивалентного множества нет, и быть не может. Хотя-бы потому, что любое счётное множество бесконечно, и любое множество в компьютере конечно, и стало быть счётным в математическом смысле быть НЕ может.

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

Если тебе интересно продолжить своё образование, то знай: множество int полностью и однозначно преобразуется в множество double, т.к. в большинстве архитектур на сегодня множество int имеет 4294967296 элементов, и в множестве double КАЖДОМУ из этих эл-тов можно найти ОДНОЗНАЧНОЕ отображение. В силу того, что мантисса double является КОНЕЧНЫМ(sic!) множеством из 4503599627370496 эл-тов. Кроме мантиссы есть конечно ещё и 11 бит порядка, но в данном случае он не имеет значения, т.к. его величина однозначно следует из исходного целого числа, и составляет целую часть логарифма по осн. 2 из данного числа(с учётом смещения).

Таким образом, множество int полностью и однозначно отображается в множество double. И потому, преобразование int->double имеет смысл, и правомерно.

Ты же пытаешься подменить числа int какими-то «целыми числами», которые ты изучал на единственном известном тебе первом курсе какого-то заборостроительного института(ты его хоть закончил?)

Лари Уолл, гуманитарий, спроектировал ЯП

который никому не нужен, и в сраном говне.

Джордж Буш джуниор с ай кью меньше средней домохозяйки стал президентом.

страны, которая просрала все свои ништяки, и никому не нужна, и в сраном говне.

Какой толк от ваших матанов, если в жизни другие вещи рулят?

просрать то, что тебе досталось бесплатно?

Если бы математика давала ощутимый профит, математики были бы особой кастой брахманов давно уже. А жизнь этого не подтверждает какбэ.

подтверждает. Миром правят математики. КаГБэ.

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

тебе это не грозит.

который никому не нужен, и в сраном говне.

Извини меня, всему свое время, посмотрим как сраный пистон/пых продержит монополию в вебе 10 лет. Уже в начале слили

росрать то, что тебе досталось бесплатно?

Бесплатно ничего не бывает - ты теряшь время и силы. И кормишь дядей профессоров. Без таких дурачков они были бы не нужны.

страны, которая просрала все свои ништяки, и никому не нужна, и в сраном говне.

Ага, толстожопый нигер сейчас поперхнулся гамбургером, на который ты ему заработал. А на оборуну за год они тратят столько же сколько мы за 10. Путин лает из-за кустов, а караван идет на восток.

Извини меня, всему свое время, посмотрим как сраный пистон/пых продержит монополию в вебе 10 лет. Уже в начале слили

ты не с тем споришь. Я разве защищал когда-то пых/пистон? Наоборот, я всегда считал эти ЯП чем-то вроде sed, годных разве на то, что-бы написать какую-то поделку на злобу дня. Если мне заплатят денег за замену в тексте слово xyz на zyx, я напишу sed 's/xyz/zyx/g'. Если мне заплатят денег за какую-то хоумпагу, я возьму php, и сделаю это. Говно.

Люди хотят срать.

Тебе жалко? Принцессы тоже какают, относись к этому философски.

Бесплатно ничего не бывает - ты теряшь время и силы. И кормишь дядей профессоров. Без таких дурачков они были бы не нужны.

Это ты правильно сказал. Но нужны были-бы МЫ? А профессорские детки === глупые тупые дойные коровы, которых надо доить, и на которых надо ездить. Потому-что безмозглая скотина. За-то с жирным мясом.

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

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

не. Мой толстожопый о таком не думает, и ЛОР не читает. AFAIK он ваще читать не умеет. Думает, что ему все должны. Да и пусть думает, я не против.

Теперь ты в правильном ключе рассуждаешь

дык я всегда так рассуждал. Не вижу смысла делать из этого тайну.

Некоторые обиженные на это обижаются, но это не моя проблема. Некоторые неудобства только. Не вижу смысла меняться.

Он не думает и не читает. Ему это нахненужно. Он просто занял деньжонок у всего мира и никогда не отдаст.

Он не думает и не читает. Ему это нахненужно. Он просто занял деньжонок у всего мира и никогда не отдаст.

не всё так просто — он должен. Мне — отдаёт. Куда денется с подводной лодки? В этом мире делить на ноль умею только я.

Ну ладно, лично тебе отдаст, остальных поимеет.

А определения дают даже в сельской школе.

Для нормального определения вещественных чисел нужно определение предела, е-д формализм. То есть первый семестр матана. На первых лекциях дают обычно через канторовские сечения, чтобы не ждать (до полей частных на алгебре разве что к концу семестра доберутся, да и вещественными числами алгебра не занимается). Если школа без матуклона то таких определений, конечно, не будет, как и нормальных определений целых/рациональных как классов эквивалентностей на парах.

Нет.

Да. И, еще раз, хватит говорить о том, в чем не разбираешься.

Так что будет с твоим гениальным «сборщиком» когда кончится память?

Мало того, эквивалентного множества нет, и быть не может.

Почему же? Может. Классы вычетов - вполне себе int. Если подумать, то можно и для флоатов найти модель. Хотя я уверен, что уже подумали, так что надо только погуглить.

Таким образом, все твои отсылки к множествам чисел оставь при себе.

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

Таким образом, множество int полностью и однозначно отображается в множество double.

Произвольные отображения между множествами обычно никому не интересны. Интересны отображения, сохранающие определенную структуру. Какую структуру сохраняет описанная тобой хуита?

типизация в сишечке не слабая

Наличие автоматических кастов типов целых чисел и автоматических кастов типов указателей — это черты слабой типизации.

целое число без потерь преобразуется в вещественное

36028801313931392 не представимо в IEEE754-double без потери точности.

не всё так просто — он должен. Мне — отдаёт.

Хоть в рот моча - все божья роса, ага.

у него 32-битный int, там такого числа нет.

Ах да, и вообще double — это вообще не вещественные числа. Это такое множество целых чисел, которое компьютер обрабатывает так, как будто бы они отображаются на определённые вещественные, а потом обратно.

как будто бы они отображаются на определённые вещественные

На рациональные.

или, если еще более точно - на диапазоны рациональных.

Да, my bad.

Это сложение вещественного и вещественного

Не гони!

int a = 2;
double b = 2.0;
double c = a + b;

Целое — частный случай вещественного

Опять гонишь! Сравни результат с сишечке 1/2 и 1.0/2.0. Если целое - частный случай вещественного, то результат должен быть один и тот же, а это не так.

Так что будет с твоим гениальным «сборщиком» когда кончится память?

тоже, что и с твоим.

Почему же? Может. Классы вычетов - вполне себе int.

не поле.

Если подумать, то можно и для флоатов найти модель. Хотя я уверен, что уже подумали, так что надо только погуглить

дык и погугли.

Таким образом, все твои отсылки к множествам чисел оставь при себе.

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

вообще-то тут про действия над double+int в языке C, неуч.

Какую структуру сохраняет описанная тобой

без ненормативной лексики ты не можешь? Ты пьян? Иди, проспись.

Какой очаровательный ослик у тебя на аватарке. Кажется, такой беззащитной грусти не видел даже никогда.

Наличие автоматических кастов типов целых чисел и автоматических кастов типов указателей — это черты слабой типизации.

и что?

36028801313931392 не представимо в IEEE754-double без потери точности.

я знаю.

Ах да, и вообще double — это вообще не вещественные числа.

угу. А int — это НЕ целые числа. Потому-что множество целых чисел бесконечно, а множество int — таки конечно.

Надеюсь, так тебе понятнее, что это сложение целого и вещественного. Здесь используется _неявное_ приведение типов.

это СЛОЖЕНИЕ double и double. Данный факт никак не противоречит тому, что ПЕРЕД этим происходит преобразование int --> double.

Джит никак не связан со сборщиком мусора.

Как это не связан, если карту корневых ссылок строит именно он?

Не будет.

Почему?

тут кричали, что у них GC — «только инкремент». Это довольно грустно, что в их коде — всё работает, а вот в моём — почему-то нет. Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается? И как он выделяет регистровую память?

А то мне — ещё грустнее, чем этому ослику...

это СЛОЖЕНИЕ double и double.

С точки зрения программы - да. Но я человек, я вижу сложение целого и вещественного. Программа пишется для людей, ведь так? Меньше неявных преобразований, как сейчас, больше контроля.

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

так. Потому я и пишу:

double x;
int y;
double z = x + (double)y;

Как пишут разные быдлокодеры — меня не волнует.

С нормальным сборщиком мусора память от реконструкции дерева не закончится. А у тебя закончится.

не поле.

Не поле. И что дальше?

вообще-то тут про действия над double+int в языке C

еще раз, для особо одаренных - я отвечал на твой пост, где ты говорил про целые и вещественные числа. Об интах и флоатах не было никакого разговора.

Как это не связан, если карту корневых ссылок строит именно он?

А кто строит карту корневых ссылок в языке со сборкой, но без джита (интерпретируемых или компилируемых в машкод)?

Почему?

потому что не будет.

Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается?

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

А ты забываешь про jit, который сам по себе не бесплатен и оправдывает себя не всегда.

Какое отношение JIT имеет к GC? У всяких там какамлов с какашкелями JIT-ов нет, а GC есть.

И да, llvm, пара плагинчиков для clang'а и соответствующий рантайм и будет у тебя ЛЮБОЙ GC.

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

Вот только невостребован он в С и даже в С++, там немного другой подход к разработке

Там языки убогие настолько, что задача полного анализа pointer aliasing становится неразрешимой, и от GC будет мало пользы.

а затраты времени на перемещение в перемещающем GC ты конечно не считаешь, да? Он у тебя с помощью магии перемещает?

Выигрыш от компактификации многократно перевешивает накладные расходы на перемещение.

http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora086.html

нормального определения
канторовские сечения

Лол.

Да.

Нет.

И, еще раз, хватит говорить о том, в чем не разбираешься.

У меня для тебя плохие новости. То, что ты умеешь гуглить — не значит, что ты в чем-то разбираешься. Это значит лишь то, что ты умеешь гуглить.

С нормальным сборщиком мусора память от реконструкции дерева не закончится. А у тебя закончится.

тогда не говори, что «только инкремент». Пойми — либо крестик, либо трусы. Чудес не бывает в этом мире. Да, у меня рухнет этот код. У тебя — зависнет. Я такое наблюдал неоднократно. Бороться с нехваткой мозгов можно только покупкой новых мозгов. Повторяю — чудес не бывает. Кнут ещё в семидесятых это всё доказал, и у него есть пруфы, со строгим матаном. Ищи ошибку, если такой умный. Я верю Кнуту, а не тебе.

Не поле. И что дальше?

Всё. В не поле не определено умножение и деление. Оно не нужно на практике. В вычетах определено лишь сложение. (да и то со многими оговорками)

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

еще раз, для особо одаренных - я отвечал на твой пост, где ты говорил про целые и вещественные числа. Об интах и флоатах не было никакого разговора.

ОК. В таком случае, ты зря потратил своё время, доказывая мне очевидное. Меня не волнуют счётные множества ни целые, ни вещественные. Ибо в моей практике их нет. В последний раз они мне много лет назад были нужны, когда я учился. Я давно и успешно забыл эту ненужность.

В следующий раз помни, что _я_ пишу исключительно про множества, которые можно *посчитать*. А чего нет, того нельзя считать. Как этих твоих «целых чисел».

Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается?

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

за сигаретами сбегаешь? Пока твой GC всё повесил? Помни, что память *одна* в большинстве случаев, и ВСЁ ждёт, пока эта память занята. Например твоим GC. Намного лучше(дешевле!) повесить пару ядер на вычисление оптимального выделенного блока, чем вешать ВСЁ. Потому сишный malloc(3) предпочтителен в 95% случаев. А если ты не в состоянии сделать free(3) в нужный момент — вон из профессии. Никакая прокладка типа allways jit'а тебя не спасёт от течки. Смирись с этим.

Какое отношение JIT имеет к GC?

именно эта прокладка впитывает то, что из тебя вытекает. Только благодаря ей твой GC имеет нужную информацию о переменных в периметре GC. В сишечке такой прокладки нет, потому надёжное и быстрое определение утечек невозможно.

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

GC *всегда* непереносим. Ибо прибит гвоздями к машине(возможно — к виртуальной).

Там языки убогие настолько, что задача полного анализа pointer aliasing становится неразрешимой

это не баг, а фича. Не надо обсираться на каждом шагу, и всё будет хорошо. А если течка у тебя регулярная, то смирись, что ты — баба.

Выигрыш от компактификации многократно перевешивает накладные расходы на перемещение.

сиё есть бред и мечта. Доказательство опубликовано Кнутом более 30 лет назад.

http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora086.html

это я читал. Что дальше?

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

Если у тебя нет виртуальной машины с поддержкой GC, результат в любом случае непереносим.

Там языки убогие настолько, что задача полного анализа pointer aliasing становится неразрешимой, и от GC будет мало пользы.

В проектах, использующих эти языки, скорее всего нет потребности в полном анализе. И от GC для указанных явно объектов толк быть вполне может.

Доказательство опубликовано Кнутом более 30 лет назад.

Я думаю, что тогда были совсем другие сборщики.

Я думаю, что тогда были совсем другие сборщики.

математика тогда тоже была совсем другой? Ну тогда извини...

Hint: матан «исправляется» только магией. А делить на ноль умеет только Б-г.

Алгоритмы сборки стали другими.

алгоритмы НЕ стали «другими». Они только развиваются и улучшаются. Причём почти всегда в сторону специализации. Т.е. старый алгоритм затачивают под новый случай. Но принципиально в них ничего не меняется.

Если у тебя нет виртуальной машины с поддержкой GC, результат в любом случае непереносим.

а с wm тоже будет не переносим. Точнее, тебе придётся эту твою wm везде таскать для «переносимости». Т.е. это конечно ххорошо, если тебе её по любому надо таскать, как например в javascript, и мирится с её overhead'ом.

тогда не говори, что «только инкремент».

Хорошо, не только. Но этим «не только» можно полностью пренебречь. То есть 99.9% времени будет занимать именно инкремент.

Да, у меня рухнет этот код. У тебя — зависнет.

С чего же он зависнет? Ничего подобного.

Всё. В не поле не определено умножение и деление.

В кольце определено и сложение и умножение. Кольцо - не поле.

Оно не нужно на практике.

Конечно нужно. Вот твой int - как раз пример полезного кольца.

В вычетах определено лишь сложение. (да и то со многими оговорками)

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

Доопределение например до поля Галуа приводит к чудовищному удорожанию операций

А зачем?

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

На полях Галуа основан матаппарат самокорректирующихся кодов. Без них не будет работать цифровая связь и твои инторнеты.

ОК. В таком случае, ты зря потратил своё время, доказывая мне очевидное.

Чего же ты спорить начал, ебанашка?

Пока твой GC всё повесил?

С чего он что-то повесит? В случае малого дерева сборка будет быстрее, чем вызов одного маллока. Ты когда вызываешь маллок идешь за сигаретами?

Помни, что память *одна* в большинстве случаев, и ВСЁ ждёт, пока эта память занята.

Открой для себя конкурентные инкрементальные сборщики.

Потому сишный malloc(3) предпочтителен в 95% случаев. А если ты не в состоянии сделать free(3) в нужный момент — вон из профессии.

К сожалению, маллок/фри - это медленно, сильно медленно. Зачем делать программу, которая будет работать медленнее в тысячи или даже миллионы раз?

Только благодаря ей твой GC имеет нужную информацию о переменных в периметре GC.

Нет, не благодаря ей. Есть куча языков без джита, но с ГЦ.

сиё есть бред и мечта.

Только выигрыш в сотни тысяч раз перед дефолтными аллокаторами доказан практикой.

Доказательство опубликовано Кнутом более 30 лет назад.

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

Hint: матан «исправляется» только магией.

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

Причём почти всегда в сторону специализации.

Exactly! Так вот функциональные языки - это как раз тот частный случай, на котором фри-маллошное говно тормозит, а сборщики - летают. Конкретнее - происходит интенсивное выделение маленьких короткоживущих объектов, при этом общее потребление памяти сравнительно мало.

В таком случае если выделять память аллокаторами «влоб» - это будет тормозить, очень, очень силньо тормозить. В сишка обычно проблема решается за счет предварительного выделения памяти, выделения блоками и т.д. - но для функциональных кейзов эти способы неприменимы. И сборщик тут - это как раз оптимальный алгоритм выделения памяти для данного кейза.

Хорошо, не только. Но этим «не только» можно полностью пренебречь. То есть 99.9% времени будет занимать именно инкремент.

ага. В синтетических тестах, где для массива в 1000 эл-тов имеется 64Гб RAM. На боевом сервере это всё начинает тупить и тормозить, хотя там тоже 64Гб, но массивов там 100500, и размером они по 100500.

С чего же он зависнет? Ничего подобного.

так и будет, когда твой перемещающий GC начнёт _перемещать_. Включи голову и осознай, что для этого нужно ВСЁ останавливать.

ИЧСХ, если у тебя этот твой GC будет НЕ работать 99.9% времени, то когда он таки включится, работы накопится в тысячу раз БОЛЬШЕ, чем если-бы он работал на каждой аллокации. Но ты же 999 аллокаций делал только инкремент. А теперь — страдай и жди.

Повторяю: чудес не бывает, если ты отложил работу, то ты НЕ СДЕЛАЛ работу. Так вот, GC именно ОТКЛАДЫВАЕТ работу по наведению порядка.

В кольце определено и сложение и умножение. Кольцо - не поле.

может ты самостоятельно освежишь свои знания?

Сложение определено безо всяких оговорок.

6часов + 6часов == сколько часов?

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

3часа*4часа == сколько часов? А сколько 6часов*6часов?

Доопределение например до поля Галуа приводит к чудовищному удорожанию операций

А зачем?

затем, что оно(умножение/деление) _неоднозначное_. Даже если делитель не равен нулю. Т.е. если в целых/вещественных «делить на ноль нельзя», то в вычетах делить ВООБЩЕ нельзя, кроме некоторых специальных случаев (например можно умножать и делить на 1).

Доопределение до поля Галуа снимает проблему неоднозначности, но возникает проблема дебиловрядовых программистов, которые стройными рядами уходят в лечебницы для психов. Ибо понять 2*2==1 они почему-то не могут.

На полях Галуа основан матаппарат самокорректирующихся кодов. Без них не будет работать цифровая связь и твои инторнеты.

я в курсе. А работать будет, просто медленнее.

В случае малого дерева сборка будет быстрее, чем вызов одного маллока.

докажи это странное заключение.

Открой для себя конкурентные инкрементальные сборщики.

они освобождают какую-то другую память?

К сожалению, маллок/фри - это медленно, сильно медленно.

это пока сборка не запустилась, а откладывается. Да, тогда malloc медленный. Вот только работа GC всё равно только ОТКЛАДЫВАЕТСЯ.

Нет, не благодаря ей. Есть куча языков без джита, но с ГЦ.

ага: bash, php...

может ты самостоятельно освежишь свои знания?

Ага, замечательно. Быстро мне определение кольца - только без подсказок из гугла!

6часов + 6часов == сколько часов?

Я не знаю, какая мат. структура у тебя на часах. может Z_12, может Z_24, может N, может что еще изощреннее. Я мысли читать не умею.

затем, что оно(умножение/деление) _неоднозначное_.

Ну ради бога. Все равно все пользуются интами и довольны. Умножение и деление кстати вполне однозначны, только деление не всюду определено (только если делитель с модулем взаимно просты).

то в вычетах делить ВООБЩЕ нельзя, кроме некоторых специальных случаев (например можно умножать и делить на 1).

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

я в курсе. А работать будет, просто медленнее.

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

Только выигрыш в сотни тысяч раз перед дефолтными аллокаторами доказан практикой.

тут главное, что-бы сборка не включилась во время теста.

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

область применимости описана — когда памяти не хватает, и приходится запускать GC (или когда maloc(3) уже не справляется, и тратит слишком много времени на поиск)

А когда памяти как грязи — мой super_malloc работает ничуть не хуже, и не медленнее. Особенно в 64х битах и со свопом (куда и будет складываться автоматически ненужный мусор)

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

а те теоремы тоже устарели? Сумма квадратов катетов уже не равна квадрату гипотенузы? Да? Ну дай пруф на ютуб, я посмотрю ролик с доказательством, и пойду топится.

но для функциональных кейзов эти способы неприменимы. И сборщик тут - это как раз оптимальный алгоритм выделения памяти для данного кейза.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

докажи это странное заключение.

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

они освобождают какую-то другую память?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это пока сборка не запустилась, а откладывается. Да, тогда malloc медленный. Вот только работа GC всё равно только ОТКЛАДЫВАЕТСЯ.

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

С аллокаторами все наоборот - их стоимость практически не растет с ростом потребностей в памяти, но линейна по вызываемым маллок/фри.

В ФП языках мы имеем как раз первый случай - и там GC резко выигрывают. Еще раз, фактически, алгоритм GC - это алгоритм оптимального аллокатора для подобной ситуации.

Повторяю: чудес не бывает, если ты отложил работу, то ты НЕ СДЕЛАЛ работу. Так вот, GC именно ОТКЛАДЫВАЕТ работу по наведению порядка.

Да нет, GC совершает ДРУГУЮ работу. Это другой алгоритм. И сложность у GC и у аллокаторов разная (зависит от разных параметров).

так и будет, когда твой перемещающий GC начнёт _перемещать_. Включи голову и осознай, что для этого нужно ВСЁ останавливать.

Еще раз - читай про конкурентные сборщики.

тут главное, что-бы сборка не включилась во время теста.

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

область применимости описана — когда памяти не хватает, и приходится запускать GC (или когда maloc(3) уже не справляется, и тратит слишком много времени на поиск)

Это зависит от того, чем забита память. Если данные достижимы - то времени потратится много, а если нихуя достижимых нет - то и времени нихуя затрачено не будет. Т.к. недостижимые данные в процессе сборки вообще никак не участвуют. Сборщик их не обходит, не помечает, не перемещает. Ничего с ними не делает - его для них вообще нет.

а те теоремы тоже устарели?

Теоремы не устарели. Я говорил о методах доказательства.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

Не является. Как и стратегия дефолтных аллокаторов. Вообще говоря для каждой задачи есть определенный оптимальный способ использования памяти. И вероятность того, что он совпадет с оптимальным для данной архитектуры - около нуля (если только это не специализированный заточенный под узкую задачу девайс).

Ага, замечательно. Быстро мне определение кольца - только без подсказок из гугла!

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

Я не знаю, какая мат. структура у тебя на часах. может Z_12, может Z_24, может N, может что еще изощреннее. Я мысли читать не умею.

ты часов не видел? 12 цифр. И да, с 24ю только хуже, ибо неоднозначностей только больше. Т.ч. считай как попроще, с 12.

Ну ради бога. Все равно все пользуются интами и довольны. Умножение и деление кстати вполне однозначны, только деление не всюду определено (только если делитель с модулем взаимно просты).

да потому-что int'ы это НЕ вычеты. Твоя изначальная предпосылка ложна. Они «вычеты» исключительно по сложению, а по умножению/делению — это конечная подобласть таки области целых. Т.е. результат умножения/деления int эквивалентен умножению/делению целых, если нет переполнения. А если есть — UB для сишечки.

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

ты ошибаешься. Всё намного хуже, если модуль — не целая степень простого числа. Проблема в том, что по модулю 12, 2*6==6*6==3*4==...==0; И ты не можешь разделить даже ноль на что угодно.

А если модуль — целая степень простого числа, то всё только хуже. Вот тебе таблица умножения по модулю 3

0*2=0
1*2=2
2*2=1

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

ОК, а что такого тормозного нужно сделать моему malloc'у? Выиграть партию в преферанс?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это как, если у тебя скажем массив, с которым ты СЕЙЧАС работаешь наполовину в одном месте, а на другую половину — в другом?

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

и избавить меня от повторения очевидных вещей.

Но ты же этих вещей не знаешь. Или не помнишь. Значит - надо повторить. А ну быстро в гугл иди!

ты часов не видел? 12 цифр. И да, с 24ю только хуже, ибо неоднозначностей только больше. Т.ч. считай как попроще, с 12.

Замечательно, 6+6=0. Дальше что?

да потому-что int'ы это НЕ вычеты.

Нет, это именно что вычеты.

Они «вычеты» исключительно по сложению, а по умножению/делению — это конечная подобласть таки области целых.

По умножению они тоже точно такие же вычеты, т.к. умножение нельзя определить иначе, не нарушив дистрибутивность, то есть тогда у тебя в интах будет ситуация, при которой a+a!=2a. Ну а операции деления, как противоположной умножению на интах просто не определено, есть только целочисленное деление с вариациями.

Т.е. результат умножения/деления int эквивалентен умножению/делению целых, если нет переполнения. А если есть — UB для сишечки.

Хохо, так ты не только начальной алгебры, но и сишки не знаешь? ub - только в случае знаковых, а вот беззнаковые как раз обязаны modulo 2^n - то есть вести себя как классы вычетов при сложении и умножении.

ты ошибаешься. Всё намного хуже, если модуль — не целая степень простого числа.

Это ты сам хуйню придумал.

Проблема в том, что по модулю 12, 2*6==6*6==3*4==...==0; И ты не можешь разделить даже ноль на что угодно.

Деление - это, по определению, умножение на обратный элемент, а не то, что ты придумал. 0/5 = 0*5^-1, например, то есть ноль, по определению нуля. У пятерки в Z_12 обратный есть (как и у любого числа взаимно простого с 12), по-этому все что угодно в этом кольце можно делить на пятерку.

Таблица умножения по модулю 7

Кольцо классов вычетов по модулю 7 является полем, да будет тебе известно (поле Галуа GF(7)). В нем можно умножать что угодно на что угодно и делить что угодно на что угодно (кроме нуля, конечно).

ну, например, в этом поле 5*6=2, 3*4=5, 6*4=3. Таблицу целиком мне лениво писать.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

Тот маллок, который подходит, у меня уже есть - и это GC. О чем я и говорю. Если хочешь оптимального маллока для этой задачи - придется реализовать полноценный GC.

ОК, а что такого тормозного нужно сделать моему malloc'у?

В общем случае - это системный вызов, которому надо сделать очень много.

это как

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

Есть мнение, что ты сам эти алгоритмы не знаешь. Ибо не смотря на название, они не делают то, что говоришь ты. И еще, современные GC плохо работают тогда, когда мало мусора и много объектов, которые реально нужны. Особенно это все проявляется, когда речь идет хотя бы о нескольких десятках гигобайт. В то время как кастомные аллокаторы на C++ показывают себя очень хорошо. Поэтому, повторюсь, не существует оптимальных алгоритмов на все случаи жизни. Опциональный(полностью) сборщик в C++ может быть полезен, возможно, что он таки появится рано или поздно в стандарте.

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

нет, спасибо. Но меня никто не просит писать helloworld'ы, задача которых — напечатать helloworld и завершиться.

И злится не нужно. Пиши пожалуйста по-русски. Со своими друзьями будешь так общаться. Не нужно тут всем доказывать, что у тебя друзья такие тупые, что кроме ненормативной лексики ничего больше не разумеют.

Теоремы не устарели. Я говорил о методах доказательства.

а я говорил о _доказанных_ теоремах.