Рекурсия и стек

#javascript #рекурсия #стек

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

function power (base, exponent){
   if (exponent == 0)
       return 1;
   else
       return base * power(base, exponent -1);
}

console.log(power(2, 3));


Можете ли объяснить по шагам как тут всё устроено? 
    

Ответы

Ответ 1

Вызываем функцию с параметрами (2,3), т.е. функция имеет данный вид: 



function power (2, 3){
   if (3 == 0)
       return 1;
   else
       return 2 * power(2, 3 - 1);
}




Далее функция(назовем ее внешняя) вызывает сама себя и создает новый уровень вложенности(
назовем клон 1 ),  (PS внешняя не может завершиться пока не завершатся все внутренние(клоны))
далее клон 1 вызывает сам себя и создает новый уровень вложенности( назовем клон 2 ),
далее клон 2 вызывает сам себя и создает новый уровень вложенности( назовем клон 3 ),
далее на клоне 3 срабатывает условие if, значит return 1 и клон 3 возвращает единицу
клону 2.
На клоне 2 срабатывает условие else т.е. 2 * 1( единицу вернул клон 3) , и результат(двойка)
возвращается  клону 1
На клоне 1 срабатывает условие else т.е. 2 * 2( двойку вернул клон 2 ), и результат(четверку)
возвращает внешней функции
На внешней функции срабатывает условие else т.е. 2 * 4( четверку вернул клон 1 ),
и возвращает результат(восьмерку ) в консоль.

Нарисовал схему работы данной функции:


Ответ 2

function power (base, exponent){
   //Посчитаем силу базы (хз что это, но надо так надо :)

   //Если экспонента точно равна нулю, то мы знаем ответ!
   if (exponent == 0) {
       return 1; //и он равен нулю
   }
   else { //Но если экспонента нулю не равна, то ответ мы не знаем

       //Попробуем уменьшить экспоненту на 1 и посчитать снова
       exponent = exponent - 1;

       //результатом работы функции будет число, умноженное на результат работы ЭТОЙ
же функции, но с экспонентой, уменьшенной на 1
       return base * power(base, exponent);
   }

   //Если придет значение экспоненты меньше нуля, то все, браузеру хана :)
}

Не удается создать стек в теле класса

#cpp #классы #стек

Хочу создать стек с элементами класса Disk в классе Pole, но получаю ошибку: синтаксическая
ошибка: отсутствие ";" перед "<"

Pole.h

#pragma once
#include 
#include "Disk.h"


class Pole
{
private:
    char num;

    stack  pole; //здесь ошибка

public:
    Pole();

    ~Pole();

    void Number(int n);

    int Get_Number();

};

    

Ответы

Ответ 1

stack у вас указывает на ::stack.
Не знаю, где конкретно он у вас определён, но похоже, что определён, и не имеет шаблонной
формы(иначе была бы другая ошибка).  

Варианты решения:  


Указать namespace: std::stack  
Импортировать namespace полностью: using namespace std; 
Импортировать из namespace нужный символ: using std::stack;

Рекурсия и стек

#javascript #рекурсия #стек

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

function power (base, exponent){
   if (exponent == 0)
       return 1;
   else
       return base * power(base, exponent -1);
}

console.log(power(2, 3));


Можете ли объяснить по шагам как тут всё устроено? 
    

Ответы

Ответ 1

Вызываем функцию с параметрами (2,3), т.е. функция имеет данный вид: 



function power (2, 3){
   if (3 == 0)
       return 1;
   else
       return 2 * power(2, 3 - 1);
}




Далее функция(назовем ее внешняя) вызывает сама себя и создает новый уровень вложенности(
назовем клон 1 ),  (PS внешняя не может завершиться пока не завершатся все внутренние(клоны))
далее клон 1 вызывает сам себя и создает новый уровень вложенности( назовем клон 2 ),
далее клон 2 вызывает сам себя и создает новый уровень вложенности( назовем клон 3 ),
далее на клоне 3 срабатывает условие if, значит return 1 и клон 3 возвращает единицу
клону 2.
На клоне 2 срабатывает условие else т.е. 2 * 1( единицу вернул клон 3) , и результат(двойка)
возвращается  клону 1
На клоне 1 срабатывает условие else т.е. 2 * 2( двойку вернул клон 2 ), и результат(четверку)
возвращает внешней функции
На внешней функции срабатывает условие else т.е. 2 * 4( четверку вернул клон 1 ),
и возвращает результат(восьмерку ) в консоль.

Нарисовал схему работы данной функции:


Ответ 2

function power (base, exponent){
   //Посчитаем силу базы (хз что это, но надо так надо :)

   //Если экспонента точно равна нулю, то мы знаем ответ!
   if (exponent == 0) {
       return 1; //и он равен нулю
   }
   else { //Но если экспонента нулю не равна, то ответ мы не знаем

       //Попробуем уменьшить экспоненту на 1 и посчитать снова
       exponent = exponent - 1;

       //результатом работы функции будет число, умноженное на результат работы ЭТОЙ
же функции, но с экспонентой, уменьшенной на 1
       return base * power(base, exponent);
   }

   //Если придет значение экспоненты меньше нуля, то все, браузеру хана :)
}

Не удается создать стек в теле класса

#cpp #классы #стек

Хочу создать стек с элементами класса Disk в классе Pole, но получаю ошибку: синтаксическая
ошибка: отсутствие ";" перед "<"

Pole.h

#pragma once
#include 
#include "Disk.h"


class Pole
{
private:
    char num;

    stack  pole; //здесь ошибка

public:
    Pole();

    ~Pole();

    void Number(int n);

    int Get_Number();

};

    

Ответы

Ответ 1

stack у вас указывает на ::stack.
Не знаю, где конкретно он у вас определён, но похоже, что определён, и не имеет шаблонной
формы(иначе была бы другая ошибка).  

Варианты решения:  


Указать namespace: std::stack  
Импортировать namespace полностью: using namespace std; 
Импортировать из namespace нужный символ: using std::stack;

Правильная скобочная последовательность стек python [дубликат]

#python #стек

        
             
                
                    
                        
                            На этот вопрос уже даны ответы здесь:
                            
                        
                    
                
                        
                            Проверить правильно ли вложены скобки 〈 ( { [ ] } ) 〉в
тексте
                                
                                    (2 ответа)
                                
                        
                                Закрыт 2 года назад.
            
                    
Всем привет, кто может помочь с реализацией проверки на правильность скобочной последовательности
через стек на Python.
Суть проверки я знаю, и просто через условия реализовала, но со стеком не могу понять,
помогите пожалуйста.

def brackets_check(s):
meetings = 0
for c in s:
    if c == '(':
        meetings += 1
    elif c == ')':
        meetings -= 1
        if meetings < 0:
            return False

return meetings == 0

    

Ответы

Ответ 1

А мне понравился этот простой и хитрый алгоритм -- главное чтобы строка в нем не
имела символом, кроме ()[]{}, там даже объяснять ничего не нужно:

def is_correct_brackets(text):
    while '()' in text or '[]' in text or '{}' in text:
        text = text.replace('()', '')
        text = text.replace('[]', '')
        text = text.replace('{}', '')

    # Возвращаем True, если text с пустой строкой
    return not text


print(is_correct_brackets('(((())))'))  # True
print(is_correct_brackets('(((())'))  # False
print(is_correct_brackets('())))'))  # False
print(is_correct_brackets('((((){}[]{}[])))'))  # True
print(is_correct_brackets('(){}[]{}[])))'))  # False
print(is_correct_brackets('(){}[]{}[]'))  # True


Ответ 2

На самом деле, всё очень просто.

Вы идёте от начала строки. Каждый раз, когда встречаете открывающую скобку - кладёте
её в стек. Каждый раз, когда встречаете закрывающую - убираете из стека ранее положенную
скобку.

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

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

Определение объектов в C++

#cpp #классы #объекты #стек

Добрый день, интересует такой вопрос, по поводу определения объектов в С++. Насколько
я знаю объекты можно определять, как в стеке так и в куче. Знаю, что в стеке доступ
к объектам будет быстрее, но если нужно будет запрашивать большое количество памяти,
то нужно будет определять его в куче. Это в принципе все, что я знаю об этом. Хотелось
бы услышать внятный ответ, когда и в каких ситуациях предпочтительнее тот или иной способ.
    

Ответы

Ответ 1

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


Введем для этого пояснения такое понятие, как время жизни объекта (object lifetime).
Будем считать, что объект начинает жизнь тогда, когда под 
него выделилась память и завершилась его инициализация. Всякие отводы, тонкости и
закавыки рассматривать не будем.

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

Итак, для начала рассмотрим коротенько четыре "времени хранения" (storage duration).

Статическое время хранения (static storage duration) - всё статическое живет от момента
создания до самого конца программы.

Потоковое время хранения (thread storage duration) - всё потоковое живет от момента
создания до конца потока в котором создано.

Автоматическое время хранения (automatic storage duration) - всё автоматическое живет
от момента создания до конца блока в котором оно было создано.

Динамическое время хранения (dynamic storage duration) - всё динамическое живет от
момента создания до того момента, пока его явно не прихлопнут.

Соответственно уже отсюда можно сделать вывод что нам необходимо.

A. Если объект должен жить всю программу (ну, почти), то варианта два:


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


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

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


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


D. Если нам необходимо, чтобы объект, созданный в блоке жил до самого конца программы
(или потока),то вариант у нас один:


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


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


Динамический объект.



Теперь по каждому пункту отдельно.

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

B. см. предыдущий пункт.

C. Автоматический или динамический?
Объекты маленькие, их количество известно и они точно влезут в стек (без фанатизма)?
Если да то использовать автоматические объекты или динамические
зависит от хотелок разработчика и здравого смысла.
Если не нужна динамика, то нафиг заниматься ручной работой?
Но если очень хочется, то можно хоть каждый int делать динамическим.
Если же объекты тяжелые и не хочется на них тратить стек,
или же нам неизвестно конечное количество одновременно 
живущих элементов, то тут только динамические объекты прокатят.
Вариант "создам здоровый массив на все случаи жизни"
здесь не прокатит, т.к. выше оговорено, что конечное количество одновременно 
живущих объектов неизвестно и, соответственно, оно всегда будет равно sizeof(mySuperArray)/sizeof(*mySuperArray) + 1.

D. Всё как и прежде - смотрим на потребности в каждом потоке.

E. Без вариантов.

В программах, чаще всего, встречается смесь из всего высказанного выше в разных пропорциях
и сочетаниях.

Вот такая абсолютно бесполезная портянка, т.к. она всё равно не покрывает всего и
вся и не является истиной в последней инстанции.


Ответ 2

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

Доступ быстрее в стеке не будет, так как память физически та же самая, что и для
объектов в куче. Другое дело, что данные могут быть в кэше, где скорость доступа выше,
но это характерно для любых данных, независимо от места их объявления. В давние времена
пытались оптимизировать добавляя ключевое слово register к объявляемой переменной.
Сейчас это уже не актуально. Более того, начиная с c++17 это слово зарезервировано
и не используется.


Ответ 3

Таки да (!), доступ к объектам в куче будет медленнее. Так как в случае создания
объектов в куче еще добавляется время, необходимое для выделение и освобождение памяти
в куче. Если объект в программе один и создается этот объект один раз, то различие
невелико. А если в куче приходится во время работы создавать и удалять МНОГО объектов,
то время на выделение объекта в куче становится существенным (по сравнению с временем
на выделение объекта в стеке). В стеке память под объекты в большинстве современных
архитектур выделяются одной машинной командой. А чтобы выделить память под объекты
в куче, надо выполнить целую подпрограмму.

UPD1:


  так а почему именно доступ(!) будет медленнее? Я бы понял
  создание/удаление объекта. Но доступ то...


Если надо в программе ПОСТОЯННО создавать и удалять объекты, то время ДОСТУПА  включает
и время на создание/удаление объекта. ИБО очевидно, что не создав объект, доступа к
нему не получишь. Собственно же ДОСТУП, конечно, в СОВРЕМЕННЫХ архитектурах персоналок
и мобильников не отличается по времени. Однако были и есть архитектуры (например приснопамятная
однокристалка от Интел пятьдесят первой серии) в которых даже и собственно ДОСТУП к
памяти значительно отличается по времени от ДОСТУПА к стеку.

UPD2:

Опа-на. Пока я отвечал, комментарий на который я отвечал куда-то делся. :-) Чудны
дела Твои Господи. :-)

Переполнение системного стека (не структуры данных)

#стек

Как стек знает, что он переполнен?
Когда программа проверяет, не переполнен ли стек?
Что происходит при переполнении стека?
    

Ответы

Ответ 1

Как стек знает, что он переполнен?


Об этом знает операционная система. Она, в свою очередь, узнаёт об этом при попытке
программы прочитать из или записать в страницу-«ловушку» сразу под стеком. «Ловушка»
здесь — это невыделенная страница, к слову зарезервированная и потому никому не выделяемая
даже случайно.


  Когда программа проверяет, не переполнен ли стек?


Например, для Windows: программа может обработать SEH.


  Что происходит при переполнении стека?


Например, для Windows: операционная система генерирует исключение  EXCEPTION_STACK_OVERFLOW
(определено в winnt.h). Если программа не обработает полученное исключение, а попытается
использовать память за выделенным диапазоном - возникнет исключение "нарушение доступа".
А вот в этом случае операционная система прибъет не только поток, который попытался
воспользоваться большем чем ему доступно памятью стека потока, но и завершит аварийно
весь процесс.

ADD: Про *nix системы надо почитать, пока освежил знания по Рихтеру)


Ответ 2

Железный стек процессора (в x86) - это два регистра: ESP и SS.

SS - это адрес сегмента стека (адрес самого стека в памяти)
ESP - это указатель на текущее положение последнего элемента в стеке.

В самом начале он выставляется на конец стека. И при помещении новых элементов -
он уменьшается.

т.е. стек в памяти выглядит так

другие данные][ пустое место в стеке            | занятое место в стеке ][другие данные
              ^--- расстояние = значению ESP ---^


по мере заполнения картина меняется на 

другие данные][ |              занятое место в стеке                    ][другие данные
              ^^


и в конце концов ESP достигает значения 0 и уходит в минус. 

процессор оказывается в ситуации


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


Может только упасть. Процессор кидает ошибку Stack-Segment Fault, его ловит операционка. 

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

Теоретически корректно побороть Stack Overflow может рантайм с автоматическим управлением
памяти (вроде .NET) - тем, что он может спрятать разработчика детали реализации, и
запретить захватывать указатели на объекты в стеке. Это уберет последнее ограничение
в списке, и позволит переместить стек в другую область памяти, выделив под него побольше
места.

На практике ни один фрейморк так не делает из соображений простоты и производительности
и красоты. Stack Overflow - это почти всегда ошибка разработчика. Лучше (и проще!)
упасть, и заставить его исправить ошибку, чем скрывать ее путем скрытого перемещения
больших объемов памяти.



Стоит отметить, что описание выше значительно упрощено - примерно до уровня x86 protected
mode времен 486/Pentium. На самом деле современные операционные системы выделяют физическую
память страницами + используют флаги защиты на страницах для обнаружения переполнения
стека. Подробно (с картинками) об этом можно почитать у Рихтера, в книге "Создание
эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows", главе
"Стек потока".



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


Ответ 3

Как стек знает что он переполнен?


никак. Он не умеет думать.


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


а программа этого не делает. Это задача операционной системы. Она выделяет приложению
немного памяти под стек (обычно 1 мегабайт, и это можно настраивать). Как только приложение
начинает писать в много данных в стек и выходит за пределы выделенного места - операционная
система прибивает приложение.

Но в целом, приложение может знать, сколько места под стек ему выделено и сколько
стека по факту уже занято. И если занятно больше какого-то объёма (допустим 95%), записать
в лог/написать письмо.


  Что происходит при переполнении стека?


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


Ответ 4

Как стек знает, что он переполнен?


По мере заполнения указатель стека уменьшается. А он, к слову сказать, беззнаковый.
Когда он достигнет нуля, очередная попытка что-то в него поместить вызовет ошибку переполнения
(ну на самом дел заёма). Вот тебе и сигнал.


  Когда программа проверяет, не переполнен ли стек?


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


  Что происходит при переполнении стека?


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

Что такое стеки и очереди? [закрыт]

#cpp #очередь #стек

        
             
                
                    
                        
                            Закрыт. Данный вопрос необходимо конкретизировать. Ответы
на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы он был сосредоточен только на одной проблеме, отредактировав его.
                        
                        Закрыт 9 месяцев назад.
                                                                                
           
                
        
Учусь на втором курсе, программирование, C++. Расскажите, пожалуйста, о стеках. Как
пишется программа?
    

Ответы

Ответ 1

Стек - структура данных с доступом к элементам по принципу LIFO (Last In First Out
- Последний пришел - первый вышел). Данные добавляются в начало (конец, кому как удобно),
оттуда же и извлекаются. Для реализации данной структуры достаточно иметь лишь две
функции и указатель на верхушку:
push(item); //добавляет данные в стек
pop(); //извлекает последний элемент

Очередь - структура данных с доступом к элементам по принципу FIFO (First In First
Out - Первый пришел - Первый вышел). Данные добавляются в конец, а извлекаются из начала.
Для быстрого добавления и извлечения данных понадобится два указателя, один на начало,
очереди, второй на ее конец. Для работы с очередью используются функции:
enqueue(item); //добавляет новый элемент в очередь
dequeue(); //извлекает элемент из очереди

Для работы с указателями в C++ вам необходимо ознакомиться, например, с данной статьей
(одна из первых в поиске).
Затем, вам необходимо создать элемент данных вашего стека (очереди). Например:
struct data {
    int p;
    int c;
}

После этого обзавестись ячейкой стека. Например:
struct element {
 data element_data;
 element *next; //указатель на следующий элемент
}

Указатель на следующий элемент необходим дабы наши данные в стеке (очереди) имели
некоторую последовательность и были как-то связаны между собой.
После этого пишете необходимые функции, обзаводитесь указателями на начало (и конец,
при необходимости). Например для push():
//somewhere in the code
element *top; //инициализируется в NULL
//...
void push(data newData) {
 //создаем нашу структуру element и указатель на нее
 element *newElement = new element();
 //element_data = newData
 element->element_data = newData;
 //next = top - здесь мы и задаем связку между двумя элементами стека
 element->next = top;
 //top = указателю на нашу структуру
 top = newElement;
}

Все остальное по аналогии. На C++ давненько я не кодил (проверить негде), поэтому
прошу заранее прощения всех гуру, поправьте если где напортачил.


Ответ 2

Я бы описал стэк как упаковку с коллекцией монеток, уложеных в стопочку. С 1 до 10.
Что бы получить доступ к 5, нужно снять 10, потом 9, 8, 7, 6 и только потом получим
5-ю. Ну это лично моё ИМХО, когда то мне было проще запомнить так. В остальном остаются
только технические вопросы, и я не могу не согласится с Dex'ом...

Ошибка со стеком: Thread stack overrun

#стек #sql

update `t_map_atms` set phone='3e43' WHERE id=37

Для проверки дала такой вот простенький запрос.
Вышло:

#1436 - Thread stack overrun: 8240 bytes used of a 131072 byte stack, and 128000
bytes needed. Use 'mysqld --thread_stack=#' to specify a bigger stack.

Гуглила. Нашла вариант, как исправитья: в файле my.cnf надо одну строчку привести к виду
 thread_stack = 256K

такого файла не нашла, нашла только my.ini. Подобной строки нет, сама вставила (для
эксперемента), но не работает. 
Что мне делать?    

Ответы

Ответ 1

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

Как удалить произвольный элемента стека Forth

#стек #forth

Как удалить произвольный элемент из стека данных в языке Форт?
    

Ответы

Ответ 1

N ROLL DROP


где N — номер элемента от вершины стека начиная с 0.

Например, фраза 4 3 2 1 0  3 ROLL DROP оставит на стеке 4 2 1 0.

Такой вариант слова ROLL закреплен в спецификации начиная с Forth-83.

Зачем выделять память для переменных в стеке?

#cpp #стек

В теме еще разбираюсь плохо так что прошу строго не судить.

Насколько я понял, стек в основном нужен для правильного последовательного распределения
выполнения функций в программе. Его вместимость ограничена и он может быть переполнен
тем самым вызвав ошибку. Ввиду этого у меня возник вопрос: Почему бы чтобы уменьшить
заполненность стека по дефолту не кидать все переменные в кучу?

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

Ответы

Ответ 1

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

Если у вас локальные переменные суммарно хранят большой объем данных (от сотни килобайт
и выше), то имеет смысл выделять область в куче, и хранить указатель на нее в стеке.

Почему такой механизм не применяется по умолчанию - потому что это медленнее и в
99% случаев не нужно.

разница между flush() и ob_flush()

#php #потоки_данных #стек

Прошу вас, объясните наконец, ЧТО именно делают эти функции (объясните просто, я
новичок) и какая между ними разница.
Не понимаю, хоть убей, на форумах всех используют терминологию, котораял ишь путает
тех, кто столкнулся с ними впервые. И что ещё за верхнии и нижнее слои стека буферов?
Что за стек буферов? Что за слои? Если кто-то это доступно объяснит - это мне очень
поможет. Заранее огромное спасибо
    

Ответы

Ответ 1

Если в простых терминах пояснять, то когда вызывается echo/print, то данные идут
на вывод (например браузер). Чтобы при многочисленных echo не гонять по байту существует
выходной буфер, куда накапливаются выходные данные до какого то объема и при переполнении
данные отправляются на выход. Потом снова происходит накопление данных. flush принудительно
выбрасывает содержимое буфера в поток вывода.

Например, есть у вас долгая задача, где нужно постоянно досылать в браузер результаты
и вы используете echo "информация". Но они накапливаются в буфере и браузер ничего
не получит пока буфер не переполнится. flush после echo принудительно отправляет данные. 
Также буфер можно отключить, а в режиме cli его вообще нет.

ob_* позволяет же инициализировать свои вложенные буферы, наслаивая их друг на друга.
И при очищении данные такого буфера будут попадать в нижележащий вплоть до дефолтного.
А можно вообще не делать flush, а просто забрать накопленный результат из буфера
и уничтожить его.

ob_start открывает новый буфер и все последующие print/echo будут попадать в него.
В любой момент вы можете открыть новый буфер, а можете закрыть и сбросить данный на
буфер открытый ранее.
То есть это выглядит как слоенный пирог (стек) буферов, где данные пишутся в верхний
буфер и только когда все буферы будут сброшены на нижележащие вплоть до дефолтного,
только тогда данные уйдут не вывод.

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

то есть flush сбрасывает системный буфер на вывод, а ob_flush сбрасывает последний
открытый буфер через ob_start в нижележащий буфер (ob_* или системный)


Ответ 2

Ответ прост потому как ob_flush очищает и выводит буфер созданыый ob_start - 'output
buffer start' а flush очищает буфер вывода скрипта который и отправляет его вывод в
браузер обычно это происходит по окончанию выполнения скрипта.

Представление кучи и стека

#память #стек

Как физически выглядят куча и стек в оперативной памяти?    

Ответы

Ответ 1

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


Ответ 2

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

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

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

Вот пример организации сегментной памяти.



Суть в том, что адресное представление в "виртуальной памяти" отличается от физической.
Но для процесса(программы) это не важно, т.к. распределением памяти(выделением/освобождением)
для занимается не она. Этим занимаются различные механизмы ОС и MMU

Для более глубинного понимания, вам нужно ознакомиться с понятием "виртуальная память",
а также со способами её организации "Сегментная адресация памяти","Страничная память"

Это кратко и немного по поводу представления виртуальной памяти в физическую.

По поводу устройства памяти внутри процесса:



Снова вкратце, процесс думает, что ему выделяется цельное пространство, в котором
уже размещаются области - "код","стек", "куча".
Стек заполняется и растет при вызове новых методов в свободную область в сторону
УМЕНЬШЕНИЯ адресов. Куча растет наоборот в сторону УВЕЛИЧЕНИЯ адресов. За тем, чтобы
памяти хватило снова-таки следит ОС.

Что хранится в блоке CODE, а также о много другом вы можете узнать из рекоммендованных
мной материалов в этой ответе.

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


Азы устройства памяти 
Известная статья "Что каждый программист должен знать о памяти" 
Организация виртуальной памяти. Таблицы страниц и прочее. 
Преобразование логического адреса в линейный. 
Устройство MMU 
Элемент списка


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


Ответ 3

Лучше сказать так. Типичными операциями при работе с памятью являются её выделение/освобождение
и чтение/запись. Операции выделения и освобождения памяти работают в куче медленнее.
Доступ к данным (чтение/запись) происходит практически с одинаковой скоростью. Практически
- потому что в стеке типичным является доступ к значениям напрямую, а в куче - через
указатель. Напрямую на самом деле тоже означает что-нибудь в духе ptr [esp+10h], т.е.
чтобы получить данные, процессору нужно прибавить некоторое число к значению регистра
esp и обратиться к памяти по этому адресу. Если (типичная ситуация) указатель на фрагмент
памяти в куче лежит на стеке, то возникает два уровня косвенности - сначала надо получить
значение указателя через "ptr [esp+10h]", а потом прочитать значение по этому адресу.
Если же мы, например, заводим указатель на данные, лежащие в стеке, то разницы в
скорости доступа не будет абсолютно никакой.

Правильная скобочная последовательность стек python [дубликат]

На данный вопрос уже ответили: Проверить правильно ли вложены скобки 〈 ( { [ ] } ) 〉в тексте 2 ответа Всем привет, кто может помочь с реализацией проверки на правильность скобочной последовательности через стек на Python. Суть проверки я знаю, и просто через условия реализовала, но со стеком не могу понять, помогите пожалуйста.
def brackets_check(s): meetings = 0 for c in s: if c == '(': meetings += 1 elif c == ')': meetings -= 1 if meetings < 0: return False
return meetings == 0

Ответ

А мне понравился этот простой и хитрый алгоритм -- главное чтобы строка в нем не имела символом, кроме ()[]{}, там даже объяснять ничего не нужно:
def is_correct_brackets(text): while '()' in text or '[]' in text or '{}' in text: text = text.replace('()', '') text = text.replace('[]', '') text = text.replace('{}', '')
# Возвращаем True, если text с пустой строкой return not text
print(is_correct_brackets('(((())))')) # True print(is_correct_brackets('(((())')) # False print(is_correct_brackets('())))')) # False print(is_correct_brackets('((((){}[]{}[])))')) # True print(is_correct_brackets('(){}[]{}[])))')) # False print(is_correct_brackets('(){}[]{}[]')) # True

Определение объектов в C++

Добрый день, интересует такой вопрос, по поводу определения объектов в С++. Насколько я знаю объекты можно определять, как в стеке так и в куче. Знаю, что в стеке доступ к объектам будет быстрее, но если нужно будет запрашивать большое количество памяти, то нужно будет определять его в куче. Это в принципе все, что я знаю об этом. Хотелось бы услышать внятный ответ, когда и в каких ситуациях предпочтительнее тот или иной способ.

Ответ

Это в принципе все, что я знаю об этом. Хотелось бы услышать внятный ответ, когда и в каких ситуациях предпочтительнее тот или иной способ.
Введем для этого пояснения такое понятие, как время жизни объекта (object lifetime). Будем считать, что объект начинает жизнь тогда, когда под него выделилась память и завершилась его инициализация. Всякие отводы, тонкости и закавыки рассматривать не будем.
Объект умирает, когда память им занимаемая была освобождена или деструктор (если он есть и не тривиальный) объекта был вызван.
Итак, для начала рассмотрим коротенько четыре "времени хранения" (storage duration).
Статическое время хранения (static storage duration) - всё статическое живет от момента создания до самого конца программы.
Потоковое время хранения (thread storage duration) - всё потоковое живет от момента создания до конца потока в котором создано.
Автоматическое время хранения (automatic storage duration) - всё автоматическое живет от момента создания до конца блока в котором оно было создано.
Динамическое время хранения (dynamic storage duration) - всё динамическое живет от момента создания до того момента, пока его явно не прихлопнут.
Соответственно уже отсюда можно сделать вывод что нам необходимо.
A. Если объект должен жить всю программу (ну, почти), то варианта два:
Использовать объект с потоковым временем хранения, ежели у нас имеется один, живущий всю программу поток. Использовать объект с статическим временем хранения. Еще вариант, использовать динамический объект, но для его корректного уничтожения придется либо в какой-то из функций его явно уничтожить, что как бы уже подразумевает, что объект живет меньше чем статические объекты, либо же в деструкторе одного из статических объектов уничтожить и наш динамический объект, только вот получается, что нам для этого нужен статический объект, так что такой вариант не рассматриваем. Вариант не уничтожать его совсем - система прихлопнет память, рассматривать не будем, т.к. для объектов не будет вызван деструктор, а мы рассматриваем общее для всех объектов, а не отдельных их "видов". Так что для "чистоты эксперимента" подобные варианты мы не рассматриваем. Также выбросим из повествования временные объекты.
B. С потоковыми объектами, практически также, как и со статическими, только в масштабах потока, так что расписывать не буду, ибо и так ясно.
C. Если нам нужен объект, который должен быть уничтожен после выхода из блока, в котором создался, то варианта два:
Использовать автоматический объект. Использовать динамический объект, но при этом придется вручную его создавать и уничтожать.
D. Если нам необходимо, чтобы объект, созданный в блоке жил до самого конца программы (или потока),то вариант у нас один:
Сделать его статическим объектом, ну или потоковым, если речь о потоке. С динамическим объектом та же фигня, что и в прошлый раз - до конца такое не доживет, либо уничтожится не правильно (в общем случае).
E. Если нам необходимо, чтобы объект жил после выхода из блока в котором создан, но мы не знаем до какого времени он нам понадобится и, жить ему всю программу не нужно, то здесь вариант тоже один:
Динамический объект.
Теперь по каждому пункту отдельно.
A. Потоковый или статический? А смотрим на программу. У нас планируется всего один поток? Если да, то нефиг пытать потоковый класс памяти. Если же потоков может быть несколько, то у каждого потока должна быть своя такая переменная? Если да, то потоковый берем, если нет - статический.
B. см. предыдущий пункт.
C. Автоматический или динамический? Объекты маленькие, их количество известно и они точно влезут в стек (без фанатизма)? Если да то использовать автоматические объекты или динамические зависит от хотелок разработчика и здравого смысла. Если не нужна динамика, то нафиг заниматься ручной работой? Но если очень хочется, то можно хоть каждый int делать динамическим. Если же объекты тяжелые и не хочется на них тратить стек, или же нам неизвестно конечное количество одновременно живущих элементов, то тут только динамические объекты прокатят. Вариант "создам здоровый массив на все случаи жизни" здесь не прокатит, т.к. выше оговорено, что конечное количество одновременно живущих объектов неизвестно и, соответственно, оно всегда будет равно sizeof(mySuperArray)/sizeof(*mySuperArray) + 1
D. Всё как и прежде - смотрим на потребности в каждом потоке.
E. Без вариантов.
В программах, чаще всего, встречается смесь из всего высказанного выше в разных пропорциях и сочетаниях.
Вот такая абсолютно бесполезная портянка, т.к. она всё равно не покрывает всего и вся и не является истиной в последней инстанции.

Ошибка со стеком: Thread stack overrun

update `t_map_atms` set phone='3e43' WHERE id=37 Для проверки дала такой вот простенький запрос. Вышло: #1436 - Thread stack overrun: 8240 bytes used of a 131072 byte stack, and 128000 bytes needed. Use 'mysqld --thread_stack=#' to specify a bigger stack. Гуглила. Нашла вариант, как исправитья: в файле my.cnf надо одну строчку привести к виду thread_stack = 256K такого файла не нашла, нашла только my.ini. Подобной строки нет, сама вставила (для эксперемента), но не работает. Что мне делать?

Ответ

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

Как удалить произвольный элемента стека Forth

Как удалить произвольный элемент из стека данных в языке Форт?

Ответ

N ROLL DROP
где N — номер элемента от вершины стека начиная с 0.
Например, фраза 4 3 2 1 0 3 ROLL DROP оставит на стеке 4 2 1 0
Такой вариант слова ROLL закреплен в спецификации начиная с Forth-83

разница между flush() и ob_flush()

Прошу вас, объясните наконец, ЧТО именно делают эти функции (объясните просто, я новичок) и какая между ними разница. Не понимаю, хоть убей, на форумах всех используют терминологию, котораял ишь путает тех, кто столкнулся с ними впервые. И что ещё за верхнии и нижнее слои стека буферов? Что за стек буферов? Что за слои? Если кто-то это доступно объяснит - это мне очень поможет. Заранее огромное спасибо

Ответ

Если в простых терминах пояснять, то когда вызывается echo/print, то данные идут на вывод (например браузер). Чтобы при многочисленных echo не гонять по байту существует выходной буфер, куда накапливаются выходные данные до какого то объема и при переполнении данные отправляются на выход. Потом снова происходит накопление данных. flush принудительно выбрасывает содержимое буфера в поток вывода.
Например, есть у вас долгая задача, где нужно постоянно досылать в браузер результаты и вы используете echo "информация". Но они накапливаются в буфере и браузер ничего не получит пока буфер не переполнится. flush после echo принудительно отправляет данные. Также буфер можно отключить, а в режиме cli его вообще нет.
ob_* позволяет же инициализировать свои вложенные буферы, наслаивая их друг на друга. И при очищении данные такого буфера будут попадать в нижележащий вплоть до дефолтного. А можно вообще не делать flush, а просто забрать накопленный результат из буфера и уничтожить его.
ob_start открывает новый буфер и все последующие print/echo будут попадать в него. В любой момент вы можете открыть новый буфер, а можете закрыть и сбросить данный на буфер открытый ранее. То есть это выглядит как слоенный пирог (стек) буферов, где данные пишутся в верхний буфер и только когда все буферы будут сброшены на нижележащие вплоть до дефолтного, только тогда данные уйдут не вывод.
Удобно это использовать в самописном шаблонизаторе. Для сегмента шаблона создаем буфер и потом забираем готовый хтмл и буфер уничтожаем. Или когда вызываем сторонний код который изобилует echo и создает мусор - мы его вызов оборачиваем в ob_* и весь этот мусор оседает там.
то есть flush сбрасывает системный буфер на вывод, а ob_flush сбрасывает последний открытый буфер через ob_start в нижележащий буфер (ob_* или системный)