eugrita
Помогающий
Offline
|
|
« : 24-03-2010 12:38 » |
|
Тема вопроса: в помощь изучающим программирование пояснить на конкретных примерах классов задач применение к ним конкретных структур данных как-то: cписков, очередей, деков, стеков, деревьев , графов. Если с деревьями и графами классы достаточно обширны (графы - транспортны задачи, сетевые, марковские процессы и пр) деревья (деревья синтаксического разбора, классификационные и пр) то в отношении cписков, очередей, деков, стеков у меня несмотря на основательное изучение в течение неск лет осталось неясность (видимо и у других тоже). Ну хорошо, по-моему самой ходовой структурой из этих является стек. Типовая задача: построение калькулятора разного уровня сложности (выражения со скобками, без скобок с/без функций) - основа алгоритм Дейкстры использующий стек. То по поводу самого списка и его частных случаев - дек, очередь все спорно. 1)список или массив? (и то и другое свои преимущества и недостатки) (обычно аргумент в динамический массив сложнее вставлять, зато легче доступ по индексу, в списки- наоборот. Есть и 2 концепции реализации списка а)на базе указателя на член данных б) как массив . Людям изучающим программирование и информатику все таки неясно: 1) когда массив, когда список? Возможны оба варианта 2) в отношении очередей и деков - не вижу класса задач где удобно применять именно эти а не другие структуры. Ну очередь queue -только может при имитационном моделировании систем массового обслуживания (СМО) но и это достаточно специальный класс задая. Нет чтоб как в математике: понятие, например интеграл и дифф.ур. применяется практически в любой науке - физика, экономика, химия и пр. Помогите с примерами пожалуйста.
|
|
|
Записан
|
|
|
|
Sla
|
|
« Ответ #1 : 24-03-2010 13:53 » |
|
хотел написать... даже написал... плюнул... На безграмотно и не аккуратно написанный пост, не хочется отвечать. Ведь вопрос требует осуждения, а что имеем на самом деле? Брошенная в сторону фраза с набором "специальных" терминов - стек, дек, очередь, граф. Упоминание Дейсктра - к чему?
|
|
|
Записан
|
Мы все учились понемногу... Чему-нибудь и как-нибудь.
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #2 : 24-03-2010 14:09 » |
|
Ничего не понял. Выбор структур определяется вовсе не классом задач, а классом методов решения задач.
Чисто математически связь между классами задач и структурами данных довольно слабая, так как для одного метода можно использовать инвариантные по смыслу структуры (массив, связный список); а для одного класса задач разработать разные методы, ориентированные на использование неинвариантных структур.
И уж тем более не существует в математике классов задач типа "задачи, решаемые при помощи деревьев", классификация обычно строится по проблемам.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
eugrita
Помогающий
Offline
|
|
« Ответ #3 : 24-03-2010 14:55 » |
|
Еще раз. Понимаю конечно, что есть альтернативные подходы к реализации алгоритма - как-то со список / динамический массив . Понимаю, что все изучавшие программирование серьезно в свое время проходили через школу типа "сделай ручками список или стек или еще что" на примере конкретной задачи, например связать какую-то структуру в список , может и классы такие писали. Я тоже это делал Таких людей я уважаю, только задачи на компьютерных практикумах обычно фиговые. Например типовая задача "база данных" студентов - массив структур реализовать в виде списка. Сам реализовал, да только не могу себя убедить, а на фига список, когда с обычным динамическим массивом изящнее. Ну можно скидку на отсутствие поддержки STL в Pascal, Object Pascal, C Но понимаю и других "белоручек", которым начхать на внутренние изучение структур типа список, зато они работают на С++ в любой реализации, а там поддержка STL и тот же самый список над которым потел реализатор БД студентов с STL делается буквально в 1 оператор struct Stud { }; vector <stud > p, wS; //вот вам и динамический массив с доступом по индексу, т.е проще чем список p.push_back(wS);// вставка в конец для стека p.Insert(i);//вставка в середину для списка p.Remove(i);//удаление извините, может синтаксис неточен, не в этом суть Возникает иллюзия: а на фига все эти структуры данных если все так просто "Выбор структур данных определяется не задачей а методом решения".Конечно, любую задачу можно решать разными методами - это не математика, где зачастую 1 метод. Но все таки, можно ли попытаться в выборе структур данных исходить не от метода, а от задачи, навязывающей метод. т.е. я хочу если возможно получить Пример конкретной типовой задачи, понятной и школьникам матем. школы, где алгоритм решения серьезно проще если основан на списке очереди деке.Т.е. задачи, где выбор технологии реализации - не прихоть программиста, а определяется спецификой задачи. (пусть даже это задача на нейросеть) Кроме калькулятора я ничего не могу привести в пример. Этот мой вопрос, риторический и адресован скорее не программистам, а постановщикам задач с математической культурой и кругозором. Хотя конечно задачи решаемые программистами шире и не всегда в основе имеют математическую модель
|
|
« Последнее редактирование: 24-03-2010 15:35 от eugrita »
|
Записан
|
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #4 : 24-03-2010 15:59 » |
|
Конечно, любую задачу можно решать разными методами - это не математика, где зачастую 1 метод. Но все таки, можно ли попытаться в выборе структур данных исходить не от метода, а от задачи.
Помоему эти два предложения явно противоречат друг другу. Да и если честно всё это выглядит крайне несуразно. Лично мне это представляется примерно такой ситуацией. Надо мне попасть в другой город. Мне неминуемо придется сначала определиться насчет вида транспорта (то что здесь упоминается как метод). Например на поезде или на машие, а может вообще пешком. А уже потом покупать либо билет на поезд, либо бензин для авто, либо просто взять сухарей и одеть обувь полегче. Само по себе, то обстоятельство, что мне нужно переместиться в пространстве, никоим образом не даёт однозначного ответа на то, что мне для этого нужно, до тех пор пока я не выбиру способ/метод.
|
|
|
Записан
|
|
|
|
eugrita
Помогающий
Offline
|
|
« Ответ #5 : 24-03-2010 16:27 » |
|
В качестве конкретного алгоритма инициируемого задачей еще раз упомяну известный алгоритм Дейкстры Разбор арифметического выражения: Алг1. Вычисление арифметического выражения в постфиксной (польской) записи - использует стек и только стек. (попробуйте именно эту задачу решать другим путем - если и решите - то на порядок сложнее. Недаром в промышленных калькуляторах используется аппаратно-реализованный стек. Точно так же как разновидность Алг.2 Преобразование арифметического выражения из обычной в польскую запись тоже - использует стек и только стек. Точно так же Алг.3 Одновременное преобразование вводимого в потоке арифметического выражения с одновременным преобразованием в польскую запись и вычислением результата (объединение Алг1. и Алг.2) использует 2 стека. Вот вам пример такой всем понятной даже непрограммистам задачи. Сама задача - навязывает алгоритм решения с выбором стека. Еще примеры будут???
|
|
« Последнее редактирование: 24-03-2010 16:30 от eugrita »
|
Записан
|
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #6 : 24-03-2010 18:04 » |
|
Алг.2 Преобразование арифметического выражения из обычной в польскую запись тоже - использует стек и только стек.
Это кто такое сказал? Где это написано?
|
|
|
Записан
|
|
|
|
RXL
Технический
Администратор
Offline
Пол:
|
|
« Ответ #7 : 24-03-2010 18:07 » |
|
Я бы сказал, что в разборе выражения больше подходит дерево. А стек к польской записи применим с другой стороны: сея запись заточена под стековую машину.
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #8 : 24-03-2010 18:12 » |
|
Асолютно согласен с предыдущим оратором. Если перейти от голимой теории и полнейшей абстракции на уровень реального кода, то для реализации дерева имхо самой простой структурой в данном случае является многосвязный спискок. Это если конечно всё выражение должно храниться в памяти (возможно для каких-то манипуляций). А если нужно только вывести выражение на экран, то вообще ничего этого не надо, можно обойтись несколькими обычными переменными.
|
|
« Последнее редактирование: 24-03-2010 18:19 от resource »
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #9 : 24-03-2010 18:28 » |
|
Подтверждаю, что для разбора инфиксной записи используется дерево, а вычисление осуществляется обходом дерева в глубину. Список - это вырожденное дерево, состоящее из 1 ветви, а прохождение стека - это обход такого вырожденного дерева в глубину.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #10 : 24-03-2010 18:32 » |
|
Список - это вырожденное дерево, состоящее из 1 ветви Ну если список многосвязный, то я так понимаю, что ветвей уже может быть сколько угодно
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #11 : 24-03-2010 18:58 » |
|
eugrita, то есть, цель - придумать задачи для школьников, чтобы там структуры данных были не с потолка взяты, а реально являлись наиболее эффективными при решении задачи в конкретной постановке?
Под конкретной постановкой я имею в виду дополнительные ограничения, которые диктуют использование тех или иных структур. Это могут быть ограничения по ресурсам или требование "наиболее очевидного" (т.е. наиболее естественной структуры для представления тех или иных данных).
|
|
|
Записан
|
|
|
|
Sla
|
|
« Ответ #12 : 24-03-2010 19:23 » |
|
Господа отвечающие! Я попрошу топикстартера оформить свой вопрос корректно, без лишних слов, аккуратно и с описанием существующей для него (топикстартера) проблемы дабы отделить бота от человека.
|
|
|
Записан
|
Мы все учились понемногу... Чему-нибудь и как-нибудь.
|
|
|
eugrita
Помогающий
Offline
|
|
« Ответ #13 : 25-03-2010 05:04 » |
|
Да. моя цель - придумать задачи для школьников, чтобы там структуры данных были не с потолка взяты, а реально являлись наиболее эффективными при решении задачи в конкретной постановке. При этом еще в качестве основного критерия выбора способа реализации алгоритма была не личная прихоть программиста, а скажем оптимизация алгоритма по скорости или числу операций. Тогда сразу ясно, что алгоритмы использующие много операций вставок/удаления в середину массива выгодней реализовать списком с указателями. А алгоритмы, в которых много выборок из разных мест (много обращений к массиву) по сравнению с операциями вставок/удаления в середину - те лучше динамическими массивами. Да еще чтоб при этом задачи являлись не надуманными упражнениями, как сплошь и рядом мы видим в практикумах, а по-возможности типовыми алгоритмами, используемыми в практике.
|
|
« Последнее редактирование: 25-03-2010 05:09 от eugrita »
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Online
Сообщений: 13
|
|
« Ответ #14 : 25-03-2010 05:38 » |
|
Тогда сразу ясно, что алгоритмы использующие много операций вставок/удаления в середину массива выгодней реализовать списком с указателями.
ну так прямо утверждать тоже нельзя, зависит от многого. Например, в std::vector (или в простом массиве с простыми элементами, которые можно побайтово копировать) вставка в середину даже проще, чем в список, но, конечно, выполнится заметно дольше, если объём данных велик. Зато сам массив займёт гораздо меньше памяти, чем список. Всё это ИМХО выбирается на основе поставленной задачи и опыта - ничего универсального тут не придумаешь Нужно рассказать школьникам о существующих типах массивов/контейнеров, затем расказать о их плюсах и минусах - чтобы было представление о последствиях выбора хранилища данных. Дальше всё зависит от учеников - либо они будут понимать, как это использовать и в какой ситуации, и к чему это приведёт, либо нет. А решение задач - это лишь "набивка" руки
|
|
« Последнее редактирование: 25-03-2010 05:41 от Алексей1153++ »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #15 : 25-03-2010 06:17 » |
|
Алексей1153++, поддерживаю. Что касается фразы которая тебя смутила, то я продолжу.
eugrita, цитата приведённая Алексеем показывает, что вы сами не до конца понимаете, чем придётся заплатить при выборе списка для данной конкретной задачи. Список - это отсутствие быстрого доступа к элементам (доступа по индексу), последствия: лучше не сортировать и не искать. Естественно может быть список вам и пригодится, лично мне он пригодился всего пару раз, и то я добавлял/удалял элементы в конце/начале списка. Думаю следует вас отправить к первоисточникам, т.е. Скотт Мейерс "Эффективное использование STL"
теперь конкретная задача: 1. 2*10^6 элементов, по 200 байт каждый. итого: примерно 400 мегабайт данных 2. необходимо производить быстрый поиск по различным критериям 3. периодически появляются новые элементы 4. старые элементы не удаляются 5. запрещено использовать контейнеры чувствительные к фрагментации памяти 6. запрещено перестраивать индексы
Внимание, вопрос: какие контейнеры вы будете использовать при реализации задачи (правда мне кажется пункты 4-6 слишком упростили задачу, ну да хрен с ними) ?
|
|
|
Записан
|
Странно всё это....
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #16 : 25-03-2010 08:13 » |
|
Список - это отсутствие быстрого доступа к элементам (доступа по индексу), последствия: лучше не сортировать и не искать. Естественно может быть список вам и пригодится, лично мне он пригодился всего пару раз, и то я добавлял/удалял элементы в конце/начале списка. А мне вот список (восновном двусвязный) пригождался очень много раз. Хорош он тогда, когда в какой-то функции получаешь указатель на сам элемент списка. Таким образом отпадает надобность в том, чтобы перебирать список. И главное конечно достоинство списка (двусвязного) в том, что можно легко добавлять элемент в любую позицию, равно как и удалять.
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #17 : 25-03-2010 08:33 » |
|
resource, добавление-удаление всё-таки на красно-чёрных деревьях в общем случае поприятнее будет: всё-таки, в список вставка в произвольное место занимает линейное время.
Поэтому списки хороши в основном там, где нужно добавлять данные в голову и хвост. И если нужно быстро и без переаллокации отфильтровать хранимые данные (выбросить значения, не удовлетворяющие некоторому предикату). То есть, в тех задачах, где динамические массивы страдают от переаллокаций и перемещений элементов, а деревья избыточны, поскольку доступ к данным всегда последовательный.
|
|
|
Записан
|
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #18 : 25-03-2010 08:48 » |
|
Вадкогда в какой-то функции получаешь указатель на сам элемент списка. Таким образом отпадает надобность в том, чтобы перебирать список Если же задача плоская - вставить элемент в 25ю (например) позицию, то согласен насчет линейного времени. Но с другой стороны, это всё равно лучше, чем вставка элемента в произвольную позицию массива (если эта позиция уже заполнена).
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #19 : 25-03-2010 09:09 » |
|
resource, я больше отвечал на вторую часть твоего высказывания А если вставка в список производится более частным образом, в заданном месте - тогда согласен. Скажем, слияние упорядоченных списков будет занимать всего лишь линейное время. Вот и пример задачки - сортировка слиянием (merge sort) Хороша в случаях, когда объёмы сравниваемых данных большие - то есть, копирование стоит дорого.
|
|
« Последнее редактирование: 25-03-2010 09:13 от Вад »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #20 : 25-03-2010 13:15 » |
|
если нужно много и часто вставлять куда попало (т.е. еще надо найти куда вставить), то имхо лучше деревьев ничего нету хотя конечно можно вокруг списка построить обёртку из индекса и тогда эти проблемы уйдут, но тогда почему не взять дерево
|
|
|
Записан
|
Странно всё это....
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #21 : 25-03-2010 17:05 » |
|
Похоще, я уже перестал понимать. Я то всю жизнь думал, что дерево (о котором мы говорим) это скорее математическая абстракция, в то время как список это вполне реальный и конкретный способ организации данных.
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #22 : 25-03-2010 17:36 » |
|
resource, бинарное дерево (например, красно-чёрное) - тоже вполне реальный и конкретный способ организации данных.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
resource
Молодой специалист
Offline
Пол:
|
|
« Ответ #23 : 25-03-2010 18:10 » |
|
я вот могу спокойно сказать, к примеру, что "реализовал в программе дерево с помощью списка", а наоборот не могу сказать.
в общем от теорий уже дышать трудно становится. Покажите код что ли какой-нибудь (не обязательно свой).
|
|
« Последнее редактирование: 25-03-2010 18:12 от resource »
|
Записан
|
|
|
|
Вад
|
|
« Ответ #24 : 25-03-2010 20:13 » |
|
Бинарное дерево - обычная рекурсивная структура. Такая же, кстати, как и список, только более ветвистая Очень грубо: template <typename ElemType> struct Tree{ Tree<ElemType> * left; Tree<ElemType> * right; ElemType value; };
|
|
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #25 : 26-03-2010 04:11 » |
|
Вад, забыл указатель на корень resource, вообще все ассоциативные контейнеры (почти все угадай какие не деревья), это красно-чёрные деревья и как я рассказывал Алексею в одном из топиков, эти контейнеры на самом деле 1 шаблонный класс, поведение которого немного меняется с помощью traits для получения уже финальной реализации мы кстати отклонились от темы
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Online
Сообщений: 13
|
|
« Ответ #26 : 26-03-2010 04:19 » |
|
битсет и вектор не деревянные )
|
|
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #27 : 26-03-2010 04:21 » |
|
а из ассоциативных ?
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Online
Сообщений: 13
|
|
« Ответ #28 : 26-03-2010 04:23 » |
|
да я парочку знаю то ) Там их по списку туча, я не всё ещё пробовал
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #29 : 26-03-2010 06:54 » |
|
Вад, забыл указатель на корень Умышленно Для "просто дерева" это не обязательно - ибо дополнительная сущность, оптимизирующая работу с деревом. В Лиспе, вон, и односвязные списки являются встроенным типом данных.
|
|
|
Записан
|
|
|
|
|