О реализациях мультистека

[DIzer]

Господа , в этом году мне перепало руководство летней практикой у первокурсников. Лектор определил им задачу составить ООП версию мультистека (набора обычных  стеков с изменяемым количеством в общем случае). Все бы ничего, но уж больно корявую (на мой взгляд) реализацию затребовал. Из трех массивов
1. Целочисленный массив вершин (номер элемента - номер стека, значение - индекс вершины последнего введенного элемента этого стека (индекс элемента из массива индексов ).
2. Целочисленный  массив индексов (значение элемента этого массива индекс предыдущего элемента).
3. Массив данных, такого же  размера как и массив 2 -в нем хранятся собственно данные.
Утверждается , что такая конструкция используется в системном программировании.
 У меня вопросы -
а) Какие преимущества у данной реализации мультистека перед естественной ( на мой взгляд)  - основанной на массиве
указателей (ссылок) на узлы обычного односвязного списка?
б) Есть ли реальные (не притянутые за уши примеры использования такой лабуды, т.е. где эти преимущества  были бы определяющими)?

[vlad]

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

Гхм. У каждого свои представления о "естественности". Для меня, например, еще более естественна вот такая конструкция:

Код: [Выделить]

std::vector< std::stack<T> > multi_stack;

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

P.S. Куда тут ООП воткнуть - трудно представить. Но можно, конечно

[Comdiv]

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

[DIzer]

Гхм. У каждого свои представления о "естественности". Для меня, например, еще более естественна вот такая конструкция:

Код: [Выделить]

std::vector< std::stack<T> > multi_stack;

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

P.S. Куда тут ООП воткнуть - трудно представить. Но можно, конечно

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

[DIzer]

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

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

[Илья Ермаков]

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

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

Те же мультистеки можно использовать для реализации какого-нибудь Форта.

====

Просто в тему, как раз читал интервью с автором Форта Чарльзом Муром. Про то, что напрасно нам кажется, что времена крайне ограниченных ресурсов прошли.

Большое количество простых программ побуждает тщательно продумать каждую из них. И требуется при этом какой-нибудь 1% объёма кода, который был бы написан в других случаях.
Слыша, как кто-то похваляется миллионами строк кода, я уверен, что этот человек
вопиющим образом не разобрался в своей задаче. Нет в наше время задач, которые требовали бы миллионов строк кода. Зато есть небрежные программисты, плохие начальники и неоправданные требования к совместимости.
....
На большом компьютере можно позволить себе большие накладные расходы, обычно неизбежные при многопоточности. В конце
концов, уже существует огромная операционная система. Но для параллельной обработки почти всегда чем больше компьютеров, тем лучше. Когда ресурсы фиксированы, больше компьютеров значит — меньшие компьютеры. А маленькие компьютеры не могут позволить себе такие же накладные расходы, как большие.
Маленькие компьютеры должны объединяться — на одном чипе, на одной плате или беспроводными соединениями. У маленького
компьютера маленькая память. Для операционной системы там нет места. Эти компьютеры должны быть автономными, с собственными средствами связи. Поэтому связь должна быть простой — никаких изощрённых протоколов. Программы должны быть компактными и эффективными. Идеальная область для применения Форта.
Системы из миллионов строк кода отпадут. Они порождены большими централизованными компьютерами. Для распределённых вычислений нужен иной подход. Язык, созданный для поддержки массивного синтаксического кода, способствует то-
му, что программисты пишут большие программы. Это поощряется и приносит удовлетворение. Нет факторов, побуждающих стремиться к компактности.

[vlad]

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

Дык Какая тогда разница - три там массива или сколько. Пусть делают через три массива. Потом через список. Не меняя интерфейса - будет ООП

[vlad]

Системы из миллионов строк кода отпадут. Они порождены большими централизованными компьютерами. Для распределённых вычислений нужен иной подход. Язык, созданный для поддержки массивного синтаксического кода, способствует то-
му, что программисты пишут большие программы. Это поощряется и приносит удовлетворение. Нет факторов, побуждающих стремиться к компактности.

Нет факторов. Появятся - будут писать компаткно и эффективно на Форте. К чему нота сожаления - не понятно. И сейчас пишут на Форте там, где даже на асме слишком "жирно".

[DIzer]

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

Более того,(ИМХО) - вредно.

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

Нет , там по условию задачи динамичность подразумевалась.

Просто в тему, как раз читал интервью с автором Форта Чарльзом Муром. Про то, что напрасно нам кажется, что времена крайне ограниченных ресурсов прошли.

По всей видимости так оно и есть.

[DIzer]

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

Дык Какая тогда разница - три там массива или сколько. Пусть делают через три массива. Потом через список. Не меняя интерфейса - будет ООП

Разумеется интерфейс будет тем же, разница в сложности(относительной) алгоритмизации, лично я сторонник простых решений (при прочих равных факторах, в конце концов зря, что ли обучали из 4 месяца базовым структурам данных, а так, получили то что ожидалось, проверил работы - 1/2 от общего количества списывали у 2-3 человек).