|
stcherny
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 07.09.2002
|
|
Сообщений: 255
|
|
Из: Театр на Юго-Западе
|
|
Рейтинг: 3
|
|
|
Видимо не шарю, вот и хочется открыть что-то новое для себя в этой области. Хоть ссылку дай почитать 
|
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
|
Керниган объясняет, как сделан стек в сях?
---
...Я работаю антинаучным аферистом...
|
|
|
stcherny
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 07.09.2002
|
|
Сообщений: 255
|
|
Из: Театр на Юго-Западе
|
|
Рейтинг: 3
|
|
|
Я тебе не говорю про конкретную реализацию - смотри шире. И сообрази, что эффективную структуру данных работы с памятью на основе стека сделать нельзя. Либо, это нужно называть своими именами, а не стеком Обрати внимание, что Rott тебе уже дал подробный ответ.
Чтобы конкретнее разговаривать. Приведи список операций, которые умеет делать твой уникальный стек и для каждой операции прикинь асимптотику ее выполнения. А мы тебе раскажем что это за такая реализация и как она называется 
|
|
|
stcherny
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 07.09.2002
|
|
Сообщений: 255
|
|
Из: Театр на Юго-Западе
|
|
Рейтинг: 3
|
|
|
Просмотрел еще раз Кернигана и что-то не нашел, чтобы там шло описания работы с динамической памятью путем отказа от malloc через стек. В книжке вроде бы подробно разъясняется как происходят вызовы функций, как функционирует сам стек. Но заметь, что про работу с блоками памяти нет ни слова. Что-то я не нашел, где там дается описание как удалять из середины стека. Или я в чем-то не прав?
|
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
|
bcopy одного элемента зависит от глубины стека?
Сложение зависит?
return/longjmp зависит?
Вот и получается, что удаление из стека производится за O(1), а не O(n).
---
...Я работаю антинаучным аферистом...
|
|
|
stcherny
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 07.09.2002
|
|
Сообщений: 255
|
|
Из: Театр на Юго-Западе
|
|
Рейтинг: 3
|
|
|
Quote:
bcopy одного элемента зависит от глубины стека?
Не зависит, только копировать приходится не один элемент.
По ходу дела ты рассматриваешь только операции Push и Pop, которые очевидно работают за O(1), а операций удаления из середины стека у тебе просто не предусмотрено (хотя двунаправленный список спасает ситуацию). Но вот удалять и выделять блоки произвольного размера уже не получится точно!
Попробуй объясни, как последовательный вызов комманд malloc() и free(),с разной величиной блоков реализовать при помощи стека?
Редактировал stcherny (24.12.2005 03:11)
|
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
|
В том-то и дело, что один.
free для верхних элементов знаешь, как сделать.
А free для нижних элементов откладывается на потом.
Лечись от обобщизма.
---
"Математик может говорить, что ему хочется,
но физик должен, хотя бы в какой-то мере, быть в здравом рассудке."
Дж. В. Гиббс
|
|
|
penartur2
|
|
|
|
|
|
|
|
|
Рег.: 16.06.2005
|
|
Сообщений: 54495
|
|
|
|
Рейтинг: 429
|
|
|
Если я тебя правильно понял, то это влечет очень нерациональный расход памяти...
|
Я ушел на новый форум.
Там правовое государство. А еще можно удобно листать аплоад  |
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
|
В зависимости от.
Разумеется, если ты очень хочешь очень экономить память,
можешь пожертвовать скоростью и устроить кучу.
Или сделать удаление за O(n).
---
...Я работаю...
|
|
|
stcherny
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 07.09.2002
|
|
Сообщений: 255
|
|
Из: Театр на Юго-Западе
|
|
Рейтинг: 3
|
|
|
Реально круто!!! Ты сделал клевое открытие Срочно ботаю ASM и изучаю исходники
Кстати, если почитаешь Кернигана повнимательнее, там написано для каких ситуаций описанная тобой стратегия работает неплохо - постоянно что-то небольших размеров переменной длины выделяется и освобождается.
Если бы все было настолько просто, люди бы не стратади и не думали как сделать виртуальную память, какие алгоритмы использовать, операции malloc и free бы тогда не тормозили. Была бы польная идилия. Но учитывая, что все эти аспекты в настоящее время присутсвуют, эффективной структуры для выделяения и освобождения памяти не придуманы. Всегда приходится чем-то жертвовать либо скоростью, либо объемами нерационально выделенной памяти.
Ладно, думаю тут предельно понятно, что ты имеешь в виду, и все вытекающие отсюда проблемы. Можно завтра дисскусию продолжить, если тебе еще что-то не ясно
|
|
|
penartur2
|
|
|
|
|
|
|
|
|
Рег.: 16.06.2005
|
|
Сообщений: 54495
|
|
|
|
Рейтинг: 429
|
|
|
Где тут "очень экономить"?
Если, например, хотим постоянно хранить два или три числа - предыдущее, текущее, следующее - если делать это с помощью твоего "стека" - кончится любое количество памяти.
|
Я ушел на новый форум.
Там правовое государство. А еще можно удобно листать аплоад |
|
|
alcogolic
|
|
anonymous
|
|
|
|
|
|
|
Рег.: 01.06.2005
|
|
Сообщений: 1678
|
|
|
|
Рейтинг: 2109
|
|
|
Милый KOHTPA,
тот факт, что что malloc возвращает NULL не является минусом реализации malloc-а, он просто означает, что твоя программа не может получить больше памяти. Почему, это отдельный вопрос. Может админ запретил выделять больше, может параллельно запущенная прога сожрала всю память, а может кто-то просто вытащил планку памяти, в общем не суть. В такой ситуации все твои предложения отказаться от malloc-а и перейти на стек посылаются куда подальше - ты хоть на два стека перейди, но это не изменит решение администратора о том, сколько памяти нужно твоей программе, и, как бы это не было обидно, не вставит еще одну планку памяти.
|
'НИКАКИХ КРЫЛЬЕВ НЕТ. ПРОСТО УМИРАЕШЬ И ВСЕ' Гусеница |
|
|
alcogolic
|
|
anonymous
|
|
|
|
|
|
|
Рег.: 01.06.2005
|
|
Сообщений: 1678
|
|
|
|
Рейтинг: 2109
|
|
|
При работе с динамическими структурами чаще всего встречается две задачи: выделить память под N-байт и выделить память под некую структуру. Для решения первой задачи malloc подходит идеально, а при помощи функции sizeof подходит и для решения второго типа задач.
Можешь описать, как ты собираешся реализовывать подобные задачи на стеке или что тебе там большее нравится?
|
'НИКАКИХ КРЫЛЬЕВ НЕТ. ПРОСТО УМИРАЕШЬ И ВСЕ' Гусеница |
|
|
Druxa
|
|
Дрюха
|
|
|
|
|
|
|
Рег.: 27.06.2003
|
|
Сообщений: 2722
|
|
Из: Троицк
|
|
Рейтинг: 1974
|
|
|
Quote:
А free для нижних элементов откладывается на потом.
Может так оказаться, что никакого "потом" не будет. Ну зачем я что-то пишу в ответ КОНТРЕ ?  
|
нет, я не богат... я сказочно не богат... но я и не умен... |
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8952
|
|
|
> А free для нижних элементов откладывается на потом.
это, наверное, все правильно - только речь сейчас идет не об абстрактной машине Тьюринга, а о конкретных программах на конкретных исполнителях, которые, как я уже писал, часто вынуждены работать с сущностями время жизни которых различно и сильно зависит от окружения в момент запуска.
|
|
|
Shurick
|
|
Bad Man
|
|
|
|
|
|
|
Рег.: 30.08.2002
|
|
Сообщений: 6379
|
|
|
|
Рейтинг: 303
|
|
|
Quote:
сейчас идет не об абстрактной машине Тьюринга, а о конкретных программах на конкретных исполнителях, которые, как я уже писал, часто вынуждены работать с сущностями время жизни которых различно и сильно зависит от окружения в момент запуска.
ура!
надо полагать, теперь ты наконец-то покажешь примеры правильных в этом смысле программ!
|
|
|
Rott
|
|
|
|
|
|
|
|
|
Рег.: 07.09.2005
|
|
Сообщений: 4403
|
|
|
|
Рейтинг: 2885
|
|
|
В ответ на:
В том-то и дело, что один.
free для верхних элементов знаешь, как сделать.
А free для нижних элементов откладывается на потом.
Лечись от обобщизма.
Плохая идея. Сравнима с тем, чтобы память вообще не освобождать.
Например, программа в самом начале считывает из файла матрицу, чтобы найти решение соответствующего ЛУ, выделяет много памяти под промежуточные матрицы, в итоге получает вектор со значениями. Вполне нормально будет, что промежуточные матрицы будут сначала находиться в памяти, а итоговой вектор (который и нужен дальше в программе) - за ними. Вот получается, что довольно большой объем памяти не может быть освобожден только из-за того, что не удален относительно небольшой кусок памяти под итоговый вектор.
Короче, я не очень понимаю - тебе не нравится внутренняя организация malloc (тогда чем, и чем то, что ты предлагаешь, принципиально отличается?), либо тебе не нравится архитектура malloc-free (или new-delete)?
|
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8952
|
|
|
> надо полагать, теперь ты наконец-то покажешь примеры правильных в этом смысле программ!
ты до сих пор не видел примеры такого подхода?
Страуструпа хотя бы открывал? Базовые идеи такого подхода у него описываются.
|
|
|
Shurick
|
|
Bad Man
|
|
|
|
|
|
|
Рег.: 30.08.2002
|
|
Сообщений: 6379
|
|
|
|
Рейтинг: 303
|
|
|
>> надо полагать, теперь ты наконец-то покажешь примеры правильных в этом смысле программ!
> ты до сих пор не видел примеры такого подхода?
меня не примеры подхода с базовыми идеями интересуют, а реальные программы
причем, чтобы там был чистый malloc с проверками на ошибки
|
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31415
|
|
|
|
Рейтинг: 8952
|
|
|
> причем, чтобы там был чистый malloc с проверками на ошибки
такого точно не бывает, потому что это дорого.
|
|
Список
Плоский
Дерево
