Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Здравствуйте, ferz1, Вы писали:
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, ferz1, Вы писали:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
TB>Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий.
это я уже все знаю, повторить только надо. но в мат. навыках минус. все таки по оставшемуся 1% какая ситуация?
Здравствуйте, ferz1, Вы писали:
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Минимум хорошо бы алгебру (не ту, что в школе, а общую алгебру) знать. Остальное предметная область диктует.
Здравствуйте, ferz1, Вы писали:
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Зависит от решаемых задач.
Но полезно знать алгебру, вероятности, графы — это по-любому.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, ferz1, Вы писали:
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Например, вот актуальное для геймдева (из широко известного в узких кругах интервью Баткина):
Секция «матемачиха и линейное щастье»
Всё, что знаете про векторное произведение, за 3 минуты.
Как посчитать нормаль треугольника по 3 точкам.
Векторы, операции над ними, нормализация вектора.
Матрицы, операции над ними, умножение вектора на матрицу.
Единичная матрица, обратная матрица, как быстро инвертировать ортонормированную матрицу.
Базисы, не ортонормированные базисы, зачем нужны, расстояние между двумя точками в таком базисе.
Сферические координаты (зачем нужны)
Кватернионы, операции для кватернионов, зачем нужны, slerp
Сравнительные харрактеристики производительности операций над векторами, матрицами, кватернионами, конверсии из и в.
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, ferz1, Вы писали:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
TB>Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий.
еще вопрос, зачем питон срр программисту? сам язык изучал давно, когда питон только еще набирал обороты. что изменилось?
Здравствуйте, ferz1, Вы писали:
F>еще вопрос, зачем питон срр программисту? сам язык изучал давно, когда питон только еще набирал обороты. что изменилось?
Да хз, постоянно такое вижу, типа скрипты ещё писать должен уметь.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
ned>Всё, что знаете про векторное произведение, за 3 минуты.
ned>Как посчитать нормаль треугольника по 3 точкам.
ned>Векторы, операции над ними, нормализация вектора.
ned>Матрицы, операции над ними, умножение вектора на матрицу.
ned>Единичная матрица, обратная матрица, как быстро инвертировать ортонормированную матрицу.
ned>Базисы, не ортонормированные базисы, зачем нужны, расстояние между двумя точками в таком базисе.
ned>Сферические координаты (зачем нужны)
ned>Кватернионы, операции для кватернионов, зачем нужны, slerp
ned>Сравнительные харрактеристики производительности операций над векторами, матрицами, кватернионами, конверсии из и в.
Я всё это знаю, но толку никакого мне от этого. Потому что все от меня хотят кутэ, линукс, паттерны...
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
ned>>Всё, что знаете про векторное произведение, за 3 минуты.
ned>>Как посчитать нормаль треугольника по 3 точкам.
ned>>Векторы, операции над ними, нормализация вектора.
ned>>Матрицы, операции над ними, умножение вектора на матрицу.
ned>>Единичная матрица, обратная матрица, как быстро инвертировать ортонормированную матрицу.
ned>>Базисы, не ортонормированные базисы, зачем нужны, расстояние между двумя точками в таком базисе.
ned>>Сферические координаты (зачем нужны)
ned>>Кватернионы, операции для кватернионов, зачем нужны, slerp
ned>>Сравнительные харрактеристики производительности операций над векторами, матрицами, кватернионами, конверсии из и в.
TB>Я всё это знаю, но толку никакого мне от этого. Потому что все от меня хотят кутэ, линукс, паттерны...
Почему ты думаешь, что твой случай можно обобщить? Я вот, например, длительное время (1998 — 2009) работал в двух фирмах, где все перечисленное было необходимо. Правильно сказали выше, специфика и уровень знаний определяется предметной областью.
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, ferz1, Вы писали:
F>еще вопрос, зачем питон срр программисту? сам язык изучал давно, когда питон только еще набирал обороты. что изменилось?
для тестов, в основном ... ну и вспомогательные скрипты писать проще, если вдруг что попарсить надо
Здравствуйте, LaptevVV, Вы писали:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут? LVV>Зависит от решаемых задач. LVV>Но полезно знать алгебру, вероятности, графы — это по-любому.
Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Здравствуйте, B0FEE664, Вы писали:
BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде.
+1
ни графы ни вероятности на практике прогеру не нужны. только если соответствуют прикладной области.
обратная сторона — если все же нужно их использовать из-за прикладной области, то изучение займет львинную долю времени и не факт, что овладеешь. поэтому некоторые держат основы в голове, некая инвестиция на будущее
а вот теория сложности (да-да, О-большое) и знание классических алгоритмов и контейнеров вполне пригождается
Здравствуйте, B0FEE664, Вы писали:
LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому. BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде.
Так математика как раз и делает неявные структуры явными, что упрощает коммуникацию и аккумулирование знаний.
Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH?
BFE>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Это вообще ни разу не аргумент и не оправдание. В стандартной библиотеке очень много чего нет, но это означает что нужно знать только то что в неё включено, очевидно же
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, LaptevVV, Вы писали:
F>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут? LVV>>Зависит от решаемых задач. LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому.
BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
тут вопрос скорее не в том, что конкретно нужно программисту с++, а что нужно любому программисту. и как "математику только за то нужно изучать, что она ум приводит в порядок", точно так же можно сказать про знания для программиста — теория графов позволяет научить мыслить нужным образом, чтобы легко представить, например, частичную упорядоченность множеств (а без этого алгоритмами, требующими отношения порядка) пользоваться сложно. да и, в конце-концов, понятие зацикливания через косвенные связи тоже легче укладывается в голове, когда уже знаком с транзитивным отношением и видел картинки циклов в графах.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
LVV>>>Но полезно знать алгебру, вероятности, графы — это по-любому. BFE>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>Так математика как раз и делает неявные структуры явными,
Но это ничего не даёт на практике.
EP>что упрощает коммуникацию и аккумулирование знаний.
Да, разумеется, только вот я не помню, что бы кто-то говорил нечто вроде:
"у нас граф наследования классов сложный..."
или
"образование цикла внутри графа построенного на смарт указателях привёло к утечке памяти".
Единственное, что приходит на ум, это граф переходов конечного автомата. Но и этот граф, опять же, присутствует в неявном виде.
EP>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH?
Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач.
BFE>>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню. EP>Это вообще ни разу не аргумент и не оправдание. В стандартной библиотеке очень много чего нет, но это означает что нужно знать только то что в неё включено, очевидно же
Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. Я за 27 лет программирования ни разу не использовал граф на практике в том смысле, что рассуждал бы о структуре, как о графе. Ну не сталкивался я с задачами обхода графа или поиска пути. И я не думаю, что я в этом какой-то уникальный.
Здравствуйте, ferz1, Вы писали:
F>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут? TB>>Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий. F>это я уже все знаю, повторить только надо. но в мат. навыках минус. все таки по оставшемуся 1% какая ситуация?
Редко бывает так, что программиста берут по принципу: был бы программист, а задача найдётся. Обычно наоборот: есть круг задач решаемых данной конторой. Если для этого круга задач требуется знание какого-то раздела математики, то ищут, соответственно, программиста который этот раздел знает. Но есть огромная масса задач, которая не требует какого-то особенного знания математики: GUI, протоколы обмена данными, базы данных, управление роботами и вообще всевозможные задачи связанные с управлением девайсами, казуальные игры...
Здравствуйте, B0FEE664, Вы писали:
LVV>>>>Но полезно знать алгебру, вероятности, графы — это по-любому. BFE>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>Так математика как раз и делает неявные структуры явными, BFE>Но это ничего не даёт на практике.
Именно что даёт.
EP>>что упрощает коммуникацию и аккумулирование знаний. BFE>Да, разумеется, только вот я не помню, что бы кто-то говорил нечто вроде: BFE>... BFE>"образование цикла внутри графа построенного на смарт указателях привёло к утечке памяти".
TB>Во-вторых, когда у меня был хитрый граф, который постоянно мутировал, постоянно новые узлы создавались, я делал так: все узлы графа
...
К>- либо исходно бардачный дизайн, приводящий к спагетти из объектов — надо один раз переосмыслить, чтобы граф связей стал топологически отсортированным
..
TB>Можно делать обход и по ходу действия. На каждый запрос по добавлению узла, например, делать две операции по обходу графа / удалению ненужных. Это если очень нужен гарантированный отклик.
Или например "объекты иммутабельные, поэтому циклов в графе ссылок нет".
Более того, GC работают по принципу обхода живых узлов в графе.
BFE>Единственное, что приходит на ум, это граф переходов конечного автомата.
А как же например вездесущие деревья?
Или например односвязные списки и генератор псевдослучайных чисел?
Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity
Например сортировка часто используется? А там те самые графы
.
BFE>Но и этот граф, опять же, присутствует в неявном виде.
Да не важно в каком виде он выражен в коде. Это не лишает его математических свойств, применимости алгоритмов и их характеристик. И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий.
EP>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач.
Да например те же вездесущие социальные сети, там графы в полный рост.
BFE>>>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню. EP>>Это вообще ни разу не аргумент и не оправдание. В стандартной библиотеке очень много чего нет, но это означает что нужно знать только то что в неё включено, очевидно же BFE>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача.
Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет
Или тебе приходят разжёванные задачи вида "вот тут примени вектор, вот тут граф, вот тот обход в ширину"
BFE>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив.
И что с того что реже чем массив? Массив например используется реже чем целые числа
Да даже если допустить что графы встречаются хотя бы в 2% задач — этого уже с головой достаточно для того чтобы их изучить хотя бы на базовом уровне, так как рано или поздно такая задача обязательно попадётся.
BFE>Я за 27 лет программирования ни разу не использовал граф на практике в том смысле, что рассуждал бы о структуре, как о графе. Ну не сталкивался я с задачами обхода графа или поиска пути. И я не думаю, что я в этом какой-то уникальный.
Правильнее будет не пытаться экстраполировать свой личный опыт на всех, а залудить опрос.
LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому.
BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Полезная абстракция.
Да и в алгоритмах обязательно читаются алгоритмы на графах.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>>>Но полезно знать алгебру, вероятности, графы — это по-любому. BFE>>Зачем графы? LVV>Полезная абстракция.
С этим не поспоришь.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
BFE>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>Так математика как раз и делает неявные структуры явными, BFE>>Но это ничего не даёт на практике. EP>Именно что даёт.
Что именно?
EP>>>что упрощает коммуникацию и аккумулирование знаний. BFE>>Да, разумеется, только вот я не помню, что бы кто-то говорил нечто вроде: BFE>>"образование цикла внутри графа построенного на смарт указателях привёло к утечке памяти". EP>Именно так и говорят — пруф
:
Ладно, здесь я не прав. Раз графы преподают, значит они такие слова будут использоваться.
BFE>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>А как же например вездесущие деревья?
Деревья — это частный случай, который намного проще.
EP>Или например односвязные списки
А список проще дерева.
EP>и генератор псевдослучайных чисел?
Причём тут генератор псевдослучайных чисел?
EP>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity
И что это даёт на практике?
EP>Например сортировка часто используется? А там те самые графы
.
И такая реализация где-то используется?
BFE>>Но и этот граф, опять же, присутствует в неявном виде. EP>Да не важно в каком виде он выражен в коде.
Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде.
EP>Это не лишает его математических свойств, применимости алгоритмов и их характеристик.
Математические свойства, конечно, остаётся, а вот насчёт алгоритмов есть большие сомнения.
EP> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий.
Что это такое — неявный граф?
EP>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>Да например те же вездесущие социальные сети, там графы в полный рост.
Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. Исключение — это когда какие-нибудь студенты проводят аналитическую работу, а на практике работа с такими графами сводится к работе со списком друзей.
BFE>>>>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню. EP>>>Это вообще ни разу не аргумент и не оправдание. В стандартной библиотеке очень много чего нет, но это означает что нужно знать только то что в неё включено, очевидно же BFE>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет
Граф — это довольно простое построение и не распознать его не получится.
EP>Или тебе приходят разжёванные задачи вида "вот тут примени вектор, вот тут граф, вот тот обход в ширину"
Последние десять лет все задачи сводились примерно к таким: вот тут у нас есть несколько потоком изображений с камер, надо надо в реальном времени убрать с них все искажения вносимые оптикой. Или. Вот мы тут девайс с моторчиками спаяли, надо обеспечить плавность и согласованность их работы, написать графический интерфейс, удалённое управление, мониторинг, обеспечить нескольких режимов ассистирования, какие нужны — спросишь у операторов.
BFE>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>И что с того что реже чем массив? Массив например используется реже чем целые числа
Ага. А целое число — это такой вырожденный граф состоящий из одной вершины.
EP>Да даже если допустить что графы встречаются хотя бы в 2% задач — этого уже с головой достаточно для того чтобы их изучить хотя бы на базовом уровне, так как рано или поздно такая задача обязательно попадётся.
У меня такое впечатление, что как человек взявший в руки молоток во всём видит гвозди, так и человеку изучившему теорию графов во всем мерещатся графы.
Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, Evgeny.Panasyuk, Вы писали:
BFE>>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>>Так математика как раз и делает неявные структуры явными, BFE>>>Но это ничего не даёт на практике. EP>>Именно что даёт. BFE>Что именно?
то же, что дает любое обобщенное знание — за частностями становится видна общая структура, которая позволяет "экономить мышление" (размышлять по дедукции).
вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Здравствуйте, B0FEE664, Вы писали:
BFE>>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>>Так математика как раз и делает неявные структуры явными, BFE>>>Но это ничего не даёт на практике. EP>>Именно что даёт. BFE>Что именно?
Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов.
BFE>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>А как же например вездесущие деревья? BFE>Деревья — это частный случай, который намного проще.
Тем не менее, это широкий раздел теории графов.
EP>>Или например односвязные списки BFE>А список проще дерева.
Это смотря как посмотреть. Список может иметь цикл, а дерево — нет
EP>>и генератор псевдослучайных чисел? BFE>Причём тут генератор псевдослучайных чисел?
При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм.
EP>>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity BFE>И что это даёт на практике?
Метрика сложности кода. Позволяет найти код с запашком в готовом проекте, либо автоматическая верификация нового.
EP>>Например сортировка часто используется? А там те самые графы
Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде.
BFE>>>Но и этот граф, опять же, присутствует в неявном виде. EP>>Да не важно в каком виде он выражен в коде. BFE>Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде.
Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение
EP>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>Что это такое — неявный граф?
Здесь это граф который присутствует в задаче, но который ты ещё не распознал.
EP>>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>>Да например те же вездесущие социальные сети, там графы в полный рост. BFE>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые.
Ага, ещё друзей друзей, ещё поиск пути между двумя людьми
BFE>>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет BFE>Граф — это довольно простое построение и не распознать его не получится.
Чтобы распознать его, нужно как минимум знать что это такое.
Ты выше не распознал граф в генераторе псевдослучайных чисел
Да и вообще, далеко не всегда лежит на поверхности
EP>>Или тебе приходят разжёванные задачи вида "вот тут примени вектор, вот тут граф, вот тот обход в ширину" BFE>Последние десять лет все задачи сводились примерно к таким: вот тут у нас есть несколько потоком изображений с камер, надо надо в реальном времени убрать с них все искажения вносимые оптикой. Или. Вот мы тут девайс с моторчиками спаяли, надо обеспечить плавность и согласованность их работы, написать графический интерфейс, удалённое управление, мониторинг, обеспечить нескольких режимов ассистирования, какие нужны — спросишь у операторов.
У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации.
Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы.
BFE>>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>>И что с того что реже чем массив? Массив например используется реже чем целые числа BFE>Ага. А целое число — это такой вырожденный граф состоящий из одной вершины.
Я этого не говорил. Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту.
EP>>Да даже если допустить что графы встречаются хотя бы в 2% задач — этого уже с головой достаточно для того чтобы их изучить хотя бы на базовом уровне, так как рано или поздно такая задача обязательно попадётся. BFE>У меня такое впечатление, что как человек взявший в руки молоток во всём видит гвозди, так и человеку изучившему теорию графов во всем мерещатся графы.
Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п.
BFE>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются
Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб
Здравствуйте, _hum_, Вы писали:
__> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Каким тут боком графы? Ordering и классы эквивалентности — скорее концепции из теории множеств и бинарных отношений. Понять их лучше всего опять же из абстрактной алгебры, где полно примеров их применения.
Здравствуйте, _hum_, Вы писали:
__> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Графы тут только как частное, это самостоятельная математическая тема. А прогеру для упомянутой экономии мышления или, если правильней сказать, времени, достаточно изучить доку по либе.
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, ferz1, Вы писали:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
A>Минимум хорошо бы алгебру (не ту, что в школе, а общую алгебру) знать. Остальное предметная область диктует.
Интересно, где программист будет использовать общую алгебру и какие конкретно разделы этой науки ему пригодятся?
Математика программисту нужна только в отдельных предметных областях: 3d графика(аналитическая геометрия), обработка звука/видео(функциональный анализ), статистика, криптография. И разумеется, нужны графы/сортировки.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Здравствуйте, lpd, Вы писали:
lpd>Интересно, где программист будет использовать общую алгебру и какие конкретно разделы этой науки ему пригодятся? lpd>Математика программисту нужна только в отдельных предметных областях: 3d графика(аналитическая геометрия), обработка звука/видео(функциональный анализ), статистика, криптография. И разумеется, нужны графы/сортировки.
1.Ниже по ветке, например, рассматривали ограничения на типы, с которыми стандартная библиотека работает.
2.Аналогично, неплохо бы представлять на какие объекты можно бы натравить, скажем, алгоритм Евклида. Тут уже понимание того, что такое кольцо нужно. Ну кто ж из программистов НОД не искал.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов.
Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
BFE>>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>>А как же например вездесущие деревья? BFE>>Деревья — это частный случай, который намного проще. EP>Тем не менее, это широкий раздел теории графов.
Когда я говорю про графы, я не говорю про деревья.
EP>Это смотря как посмотреть. Список может иметь цикл, а дерево — нет
Что-то я не припомню, чтобы я когда-то использовал список с циклом внутри... Наличие цикла внутри списка свидетельствует об ошибке, так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...
EP>>>и генератор псевдослучайных чисел? BFE>>Причём тут генератор псевдослучайных чисел? EP>При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм.
И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
EP>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде.
Ну, а я о чём? Вы мне в явном виде граф покажите.
BFE>>>>Но и этот граф, опять же, присутствует в неявном виде. EP>>>Да не важно в каком виде он выражен в коде. BFE>>Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде. EP>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение
Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии.
EP>>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>>Что это такое — неявный граф? EP>Здесь это граф который присутствует в задаче, но который ты ещё не распознал.
Т.е. воображаемый граф.
EP>>>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>>>Да например те же вездесущие социальные сети, там графы в полный рост. BFE>>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. EP>Ну так услышь: https://developers.facebook.com/docs/graph-api/overview
Ну и где там граф? Там нельзя получить граф, как структуру. Нельзя запустить поиск по графу, если я правильно понимаю.
BFE>>а на практике работа с такими графами сводится к работе со списком друзей. EP>Ага, ещё друзей друзей, ещё поиск пути между двумя людьми
С какой практической целью пользователю мог бы понадобится поиск такого пути?
BFE>>>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>>>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет BFE>>Граф — это довольно простое построение и не распознать его не получится. EP>Чтобы распознать его, нужно как минимум знать что это такое.
Если бы это было так, граф бы никогда не был придуман.
EP>Ты выше не распознал граф в генераторе псевдослучайных чисел
Покажите мне в коде генератора граф переходов.
EP>Да и вообще, далеко не всегда лежит на поверхности
Эти графы, о которых вы пишите — они ведь в голове, а не в коде. С вашей точки зрения любая функция над целыми числами — это граф, любая программа — это граф, любая последовательность символов — это граф... Алгоритмы сжатия данных без потерь — это построение графа из последовательности символов и его перенумерация, т.е. преобразования одного графа в другой граф... А поиск ошибки в программе это — это поиск неверного перехода в графе состояний программы... А программирование — это всего лишь создание графа переходов между различными состояниями в записанными в памяти машины. Это вы хотите сказать?
EP>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации.
Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает.
EP>Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы.
Графы при обработке 3D моделей? В коде? Для чего?
BFE>>>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>>>И что с того что реже чем массив? Массив например используется реже чем целые числа BFE>>Ага. А целое число — это такой вырожденный граф состоящий из одной вершины. EP>Я этого не говорил.
Это сарказм.
EP>Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту.
Хорошему программисту много чего надо знать, но это не значит, что всё что он знает ему обязательно пригодиться. На практике один из 10
разворот списка написать может, а вы тут про графы вещаете...
EP>Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п.
Уверяю вас, на свете есть много программистов, которые даже не слышали "этих ваших страшных слов". И все они что-то пишут, зарплату получают...
Это мне напоминает одну реальную историю: "-Товарищ преподаватель, вот вы говорите что у вектора есть длина. А толщина у вектора есть?".
BFE>>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика". EP>Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются
А они там точно в коде присутствуют?
EP>Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб
Ага. Вы ещё теорему Котельникова спрашивайте при приёме на работу web-программиста.
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, _hum_, Вы писали:
__>> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
A>Каким тут боком графы? Ordering и классы эквивалентности — скорее концепции из теории множеств и бинарных отношений. Понять их лучше всего опять же из абстрактной алгебры, где полно примеров их применения.
ну, так граф и есть множество с бинарным отношением а тот факт, что он имеет графическое представление, позволяет легко воспринимать такие сложные в чисто сухом алгебраическом изложении вещи, как типы отношений (антисимметричность, рефлексивность и т.п.), понятия наподобие транзитивности, классы эквивалентности и т.п.
например, строгий порядок — это транзитивно замкнутый направленный ациклический граф [легко в голове нарисовать картинку], слабый порядок — связный как ненаправленный транзитивно замкнутый направленный граф (который после факторизации по компонентам связности даст линейный список [отсюда понятно его использование при сортировке]) и т.д.
Здравствуйте, B0FEE664, Вы писали:
EP>>Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов. BFE>Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
Например Эйлерова характеристика, а из алгоритмов чаще всего обход
EP>>Тем не менее, это широкий раздел теории графов. BFE>Когда я говорю про графы, я не говорю про деревья.
Вот только непонятно почему, это та же самая теория графов
BFE>Наличие цикла внутри списка свидетельствует об ошибке,
Не обязательно.
BFE>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...
Тем не менее это она и есть.
EP>>>>и генератор псевдослучайных чисел? BFE>>>Причём тут генератор псевдослучайных чисел? EP>>При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм. BFE>И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
Нет, я не хочу этого сказать.
Я хочу сказать что в генераторах псевдослучайных чисел структурно есть граф, и к нему применимы соответствующие алгоритмы. И выделение этой графовой структуры из общего ансамбля, помогает лучше понять суть вещей.
EP>>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде. BFE>Ну, а я о чём? Вы мне в явном виде граф покажите.
Зачем именно в явном?
EP>>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение BFE>Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии.
Аналогия в том что эта ассоциативность вообще в явном виде редко где встречается, что тем не менее не умоляет полезность знаний о ней.
Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
EP>>>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>>>Что это такое — неявный граф? EP>>Здесь это граф который присутствует в задаче, но который ты ещё не распознал. BFE>Т.е. воображаемый граф.
И что с того что "воображаемый"? Это делает алгоритм поиска размера цикла не рабочим?
BFE>>>а на практике работа с такими графами сводится к работе со списком друзей. EP>>Ага, ещё друзей друзей, ещё поиск пути между двумя людьми BFE>С какой практической целью пользователю мог бы понадобится поиск такого пути?
Нужно достучаться до лично незнакомого но важного человека, это можно сделать через общих знакомых. Одна из популярных соц.сетей именно такой сценарий и предоставляет.
BFE>>>Граф — это довольно простое построение и не распознать его не получится. EP>>Чтобы распознать его, нужно как минимум знать что это такое. BFE>Если бы это было так, граф бы никогда не был придуман.
Нет, я не об этом. Переоткрыть граф и связанные свойства/алгоритмы — естественно возможно, хотя и трудоёмко.
Речь о том что ты не поймёшь что эту вновь открытую структуру люди уже столетиями называют "графом". Да и вообще непонятно зачем переотркывать то что давно известно, и имеет устоявшеюся терминологию.
EP>>Да и вообще, далеко не всегда лежит на поверхности BFE>Эти графы, о которых вы пишите — они ведь в голове, а не в коде.
Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого?
EP>>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации. BFE>Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает.
Говори прямо, намекаешь на то что я их применял не по делу?
EP>>Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы. BFE>Графы при обработке 3D моделей? В коде? Для чего?
Например для сжатия, как с потерями, так и без.
EP>>Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту. BFE>Хорошему программисту много чего надо знать, но это не значит, что всё что он знает ему обязательно пригодиться.
разворот списка написать может, а вы тут про графы вещаете...
Так зачем равняться на них?
EP>>Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п. BFE>Уверяю вас, на свете есть много программистов, которые даже не слышали "этих ваших страшных слов". И все они что-то пишут, зарплату получают...
Я знаю. Также есть много продавцов, водителей и т.п., и они точно также получают зарплату, при этом ничего не зная про упомянутые тобой массивы — и что с этого?
EP>>Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются BFE>А они там точно в коде присутствуют?
Где-то нет — и что с того? А где-то присутствуют https://en.wikipedia.org/wiki/Graph_coloring#Register_allocation
EP>>Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб BFE>Ага. Вы ещё теорему Котельникова спрашивайте при приёме на работу web-программиста.
Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту.
Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы
Здравствуйте, smeeld, Вы писали:
S>Здравствуйте, _hum_, Вы писали:
__>> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
S>Графы тут только как частное, это самостоятельная математическая тема. А прогеру для упомянутой экономии мышления или, если правильней сказать, времени, достаточно изучить доку по либе.
это когда у вас есть функция CompareCandidate(), и нужно проверить, удовлетворяет она требуемому условию на Compare() или нет. на практике же больше встречаются обратные задачи — нужно самому построить подходящую функцию. и вот тут-то как раз и проявляется выгода понимания сути всех этих вещей и эффект "экономии времени".
ребята, не спорьте на пустом месте. каждый из вас прав, просто B0FEE664 ведет речь про программирование в области embedded system (в которой затребованы в первую очередь алгоритмы работы с физическими устройствами), а Evgeny.Panasyuk в области, предполагающей несколько более высокий уровень абстрактного программирования.
Здравствуйте, _hum_, Вы писали:
__>ребята, не спорьте на пустом месте. каждый из вас прав, просто B0FEE664 ведет речь про программирование в области embedded system (в которой затребованы в первую очередь алгоритмы работы с физическими устройствами), а Evgeny.Panasyuk в области, предполагающей несколько более высокий уровень абстрактного программирования.
Мне показалось, что все несколько не так.
B0FEE664 полагает, что из осознания того, что список это граф, и "целое число — это такой вырожденный граф состоящий из одной вершины" практической пользы не извлечь. И даже к деревьям лучше применять алгоритмы разработанные именно для них, а не старательно вспоминать теорию графов завидев дерево.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Например Эйлерова характеристика, а из алгоритмов чаще всего обход
Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
EP>>>Тем не менее, это широкий раздел теории графов. BFE>>Когда я говорю про графы, я не говорю про деревья. EP>Вот только непонятно почему, это та же самая теория графов
Дерево много проще графа, встречается повсеместно и интуитивно понятно для человека. Вот даже интерфейс этого форума — дерево.
BFE>>Наличие цикла внутри списка свидетельствует об ошибке, EP>Не обязательно.
Иначе это уже не список.
BFE>>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом... EP>Тем не менее это она и есть.
Ну, это всё-таки был тестовый код, а не продакшен.
EP>>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде. BFE>>Ну, а я о чём? Вы мне в явном виде граф покажите. EP>Зачем именно в явном?
В неявном виде можно много чего где найти...
EP>>>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение BFE>>Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии. EP>Аналогия в том что эта ассоциативность вообще в явном виде редко где встречается, что тем не менее не умоляет полезность знаний о ней. EP>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
EP>Нужно достучаться до лично незнакомого но важного человека, это можно сделать через общих знакомых. Одна из популярных соц.сетей именно такой сценарий и предоставляет.
Ну, ок. Пусть будет ещё и такое применение.
BFE>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде. EP>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого?
Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение.
EP>>>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации. BFE>>Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает. EP>Говори прямо, намекаешь на то что я их применял не по делу?
Нет. Я хочу сказать, что одни и те же задачи имеют несколько способов решения. Из всех способов решений человек выбирает тот, которым он лучше владеет. И это правильно.
BFE>>На практике один из 10
разворот списка написать может, а вы тут про графы вещаете... EP>Так зачем равняться на них? EP>Я знаю. Также есть много продавцов, водителей и т.п., и они точно также получают зарплату, при этом ничего не зная про упомянутые тобой массивы — и что с этого? EP>Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту. EP>Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы
Вот приходит к нам ferz1 и спрашивает: "какой должен быть минимальный уровень знания математики?"
А вы ему сразу: без знания теории графов, алгебры и тории вероятности даже не пытайся...
Здравствуйте, B0FEE664, Вы писали:
EP>>Например Эйлерова характеристика, а из алгоритмов чаще всего обход BFE>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
Да, с маркировкой посещённых.
BFE>>>Наличие цикла внутри списка свидетельствует об ошибке, EP>>Не обязательно. BFE>Иначе это уже не список.
Почему? Например кольцевой список
BFE>>>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом... EP>>Тем не менее это она и есть. BFE>Ну, это всё-таки был тестовый код, а не продакшен.
А какая разница? Вот тебе пригодилось для решения вполне практичной задачи
EP>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%. BFE>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны.
2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок.
BFE>>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде. EP>>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого? BFE>Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение.
Во-первых, этот вывод никак не является следствием из обозначенных предпосылок. То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов.
Во-вторых, я не спорю с тем что можно до чего-то додуматься самостоятельно. Вот только изучить готовое проще, и потом тратить силы на реально неизведанное, чем постоянно переоткрывать колесо. Тяжело в учении легко в бою.
Я например лет в 12-13 налисапедил рекурсивный калькулятор арифметических выражений, без всяких знаний о парсерах, токенизаторах, грамматиках и т.п. Но со всеми этими знаниями было бы и проще и быстрее и качественнее.
BFE>Нет. Я хочу сказать, что одни и те же задачи имеют несколько способов решения. Из всех способов решений человек выбирает тот, которым он лучше владеет. И это правильно.
Лучше знать как можно больше способов, чтобы было из чего выбирать.
EP>>Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту. EP>>Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы BFE>Вот приходит к нам ferz1 и спрашивает: "какой должен быть минимальный уровень знания математики?" BFE>А вы ему сразу: без знания теории графов, алгебры и тории вероятности даже не пытайся...
Эта ветка началась совсем с другого:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>Зависит от решаемых задач.
LVV>Но полезно знать алгебру, вероятности, графы — это по-любому.
Здравствуйте, pagid, Вы писали:
P>"целое число — это такой вырожденный граф состоящий из одной вершины"
Я этого не говорил, это был его гротеск.
P>И даже к деревьям лучше применять алгоритмы разработанные именно для них, а не старательно вспоминать теорию графов завидев дерево.
Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные.
Я говорю что деревья это один из подвидов графов, в том числе изучаемый в теории графов.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>>Например Эйлерова характеристика, а из алгоритмов чаще всего обход BFE>>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов? EP>Да, с маркировкой посещённых.
А с какой целью был обход графа? Что нужно было найти?
BFE>>>>Наличие цикла внутри списка свидетельствует об ошибке, EP>>>Не обязательно. BFE>>Иначе это уже не список. EP>Почему? Например кольцевой список
Например потому, что std::find к нему применить прямо не получится.
BFE>>Ну, это всё-таки был тестовый код, а не продакшен. EP>А какая разница? Вот тебе пригодилось для решения вполне практичной задачи
Разница в оптимизации. Для тестового кода она не нужна.
EP>>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%. BFE>>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён. EP>1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны.
Насколько я помню стандарт, порядок не определён до тех пор, пока он не влияет на результат. Точно, см в стандарте 1.9/9
EP>2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок.
Note: Operators can be regrouped according to the usual mathematical rules only where the operators
really are associative or commutative.
BFE>>>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде. EP>>>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого? BFE>>Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение. EP>Во-первых, этот вывод никак не является следствием из обозначенных предпосылок.
Согласен, следствием не является. Но и вопрос был не о следствии, а о выводе.
EP>То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов.
Но и об обратном это так же не говорит.
EP>Лучше знать как можно больше способов, чтобы было из чего выбирать.
Ага. Я так во вторник сидел и три часа выбирал, чем лучше разобрать строку вида 'id=3 ssid="FreeBox" auth_fail=20'
То ли std::regex, то ли boost::tokenizer, то ли boost::xpressive, то ли boost::spirit, то ли руками...
EP>Эта ветка началась совсем с другого: EP>
F>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>>Зависит от решаемых задач.
LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому.
"графы — это по-любому" как понимать?
Я понял — в обязательном порядке. Хотя, конечно, 'никак не знать' — это тоже "по-любому"...
Здравствуйте, B0FEE664, Вы писали:
BFE>>>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов? EP>>Да, с маркировкой посещённых. BFE>А с какой целью был обход графа? Что нужно было найти?
Компоненты связности.
BFE>>>Иначе это уже не список. EP>>Почему? Например кольцевой список BFE>Например потому, что std::find к нему применить прямо не получится.
Это не "не список", а "не диапазон по определению STL". Но речи о том что это будет диапазоном STL — не было.
EP>>>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%. BFE>>>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён. EP>>1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны. BFE>Насколько я помню стандарт, порядок не определён до тех пор, пока он не влияет на результат. Точно, см в стандарте 1.9/9
EP>>2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок. BFE>
BFE>Note: Operators can be regrouped according to the usual mathematical rules only where the operators
BFE>really are associative or commutative.
BFE>
BFE>
Я выше сноску процитировал. В любом случае, перегруппировка скажем сложения unsigned'ов на результат не влияет.
И повторюсь, я не про ту ассоциативность которая левая или правая, а про ту которая позволяет скобки переставлять без изменения результата. И вот она в явном виде в коде практически не выражается, при этом используется неявно (без выражения непосредственно в коде) например при параллельной редукции. Собственно это пример к моему исходному поинту о том, что даже если что-то в коде не выражается явно, это не означает что эти знания не полезны и не нужны.
EP>>То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов. BFE>Но и об обратном это так же не говорит.
Да, и об обратном тоже не говорит. Поэтому не пойму почему ты делаешь акцент на неявности.
EP>>
F>>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>>>Зависит от решаемых задач.
LVV>>>Но полезно знать алгебру, вероятности, графы — это по-любому.
BFE>"графы — это по-любому" как понимать? BFE>Я понял — в обязательном порядке. Хотя, конечно, 'никак не знать' — это тоже "по-любому"...
Я это распарсил как "полезно знать (x,y,z) — это по-любому". Но это уже вопрос толкования, и не суть важно.
Мои основные тезисы:
— обозначенные знания не являются жёстким требованием ко всем программистам. Да, без них получится создавать реальный код, решающий некоторые реальные задачи, и получать за это реальное вознаграждение.
— для тех кто хочет стать хорошим программистом — эти знания обязательны.
— даже если допустить что эти знания являются балластом и на практике не нужны — они всё равно проверяются на некоторых реальных собеседованиях, что немаловажно.
— программирование по большей части это математическая активность — так как происходит оперирование абстрактными объектами, идеями и структурами. Более того — это строгая (rigour) математическая активность, так как нет возможности пропустить "очевидные" этапы и шаги — нужно закодировать всё — от самых низших уровней до высших. ЕМНИП, подобный тезис был у Александра Степанова. С этой позиции заявления вида "программистам математика не нужна" нелепы.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Я этого не говорил, это был его гротеск.
Разумеется, но гротеск мне показался уместным и по существу разговора.
EP>Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные.
А специальные деревянные алгоритмы это порождение теории графов, и лучше не будем путать?
EP>Я говорю что деревья это один из подвидов графов, в том числе изучаемый в теории графов.
Так это годится только для вводной лекции — "посмотрите какие еще графы бывают"
EP>>Да например те же вездесущие социальные сети, там графы в полный рост. S>Там уже полная бигдата, со всем своим хозяйством, которая уже гораздо обширней чем теория графов, и которая к математике не относится.
Оля-ля!!! Бигдата — это и статистика, и классификация, и кластеризация. Да еще на нечеткостях...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
BFE>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>А как же например вездесущие деревья? BFE>Деревья — это частный случай, который намного проще.
Не. Зависит от графа и дерева...
В-деревья, АВЛ-деревья — покруче некоторых графов будут...
EP>>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity BFE>И что это даёт на практике?
А это признак того, что надо рефакторинг начинать.
Пока код вообще в лабиринт не превратился.
EP>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>Что это такое — неявный граф?
Это значит, отсутствует представление графа в виде структуры данных, но свойства его имеются в наличии. BFE>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Читай книгу Касьянова-Емельянова о применении графов в программировании.
Они несколько штук написали про это.
Весь анализ кода построен на теории графов.
То есть, компиляторы в полный рост графы используют.
Иногда — в явном виде, чаще — в неявном.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Вот вам реальная задача, которую у нас в Астрахани сейчас пишут.
Об автоматизации мобильных сотрудников — модное ныне направление.
Существует большое количество компаний, которые выполняют курьерскую доставку.
Для этих компаний важной задачей является выбор оптимального маршрута для выполнения доставки.
Оптимальным в данном случае считается маршрут, у которого минимизированы денежные и временные затраты (задача коммивояжера).
Курьер должен придерживаться одного определённого маршрута.
Менеджеру должны быть известны маршруты, выбранные для каждого курьера.
Кроме того, возникает задача распределения заявок по курьерам (обобщенная задача о назначениях).
Решать подобную задачу без обращения к графам — немыслимо...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Решать подобную задачу без обращения к графам — немыслимо...
Так это и есть классическая задача с использованием графов. Но даже взявшись её решать, копать имеет смысл сразу же именно задачу коммивояжера, даже не особо помня, кроме основ терминологии, впрочем незатейливой, чему там учили в ВУЗовском курсе дискретной математики по поводу теории графов и учили ли.
LVV>>Решать подобную задачу без обращения к графам — немыслимо... P>Так это и есть классическая задача с использованием графов. Но даже взявшись её решать, копать имеет смысл сразу же именно задачу коммивояжера, даже не особо помня, кроме основ терминологии, впрочем незатейливой, чему там учили в ВУЗовском курсе дискретной математики по поводу теории графов и учили ли.
Ну, хотя бы представление о представлении графов надо иметь...
И поиски минимальных путей.
А еще неплохо иметь понятие о генетических и роевых алгоритмах...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Ну, хотя бы представление о представлении графов надо иметь...
Несомненно.
LVV>А еще неплохо иметь понятие о генетических и роевых алгоритмах...
Неплохо. Но там много методов и возможных алгоритмов.
И для начала стоит оценить к чему стремиться. К решению задачи наиболее близкой к оптимальной, наиболее оптимальному по быстродействию решению, или стоит сэкономить на трудозатратах разработчиков и использовать наиболее простой в реализации алгоритм, вписывающийся разумеется в разумное время расчета.
Здравствуйте, pagid, Вы писали:
P>>>"целое число — это такой вырожденный граф состоящий из одной вершины" EP>>Я этого не говорил, это был его гротеск. P>Разумеется, но гротеск мне показался уместным и по существу разговора.
Я привёл пример с вполне практическим значением — граф односвязного списка с циклом. Аналогичная структура возникает например внутри псевдослучайных генераторов.
А вот какое какое практическое значение имеет подчёркнутое, и в чём аналогия?
Я же не предлагаю например любое множество представлять как граф вершин без связей, исключительно ради того чтобы натянуть сову на глобус определение "граф", а показываю вполне реальные применения теории графов
EP>>Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные. P>А специальные деревянные алгоритмы это порождение теории графов, и лучше не будем путать?
Не понял мысли. Деревья эта та же математика, и та же теория графов.
Более того, деревья возникают не только как самостоятельные структуры, но и в том числе как подграфы более сложных графов, например остовное дерево.
Здравствуйте, smeeld, Вы писали:
EP>>>>Да например те же вездесущие социальные сети, там графы в полный рост. S>>>Там уже полная бигдата, со всем своим хозяйством, которая уже гораздо обширней чем теория графов, и которая к математике не относится. LVV>>Оля-ля!!! Бигдата — это и статистика, и классификация, и кластеризация. Да еще на нечеткостях... S>Дык, а я о чём? Cоцсети сейчас-это и статистика, и кластеризация, и классификация.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Ты о том что это к математике не относится.
Бигдата не относится? Конечно, привык к стройности и строгости построения теории, что и является отличительной чертой математики, и что не относится к тем сумбурным сочинениям, которые относятся к бигдате.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Я привёл пример с вполне практическим значением — граф односвязного списка с циклом.
И в чем польза представления последовательности псевдослучайных чисел в виде графа?
EP>Аналогичная структура возникает например внутри псевдослучайных генераторов.
И уж если возвращаться к математике с её более-менее строгими формулировками, не структура возникает в генераторе, а последовательность чисел можно представить в виде графа. Можно и не представлять.
Здравствуйте, T4r4sB, Вы писали:
TB>Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий.
Питон особо доставляет
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, B0FEE664, Вы писали:
BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде.
Можно даже быть не в курсе того, что прозой разговариваешь
BFE>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Красно-чёрные деревья больше не графы что ли? Или map и set из std выкинули?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, B0FEE664, Вы писали:
BFE>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. Исключение — это когда какие-нибудь студенты проводят аналитическую работу, а на практике работа с такими графами сводится к работе со списком друзей.
А какие представления графов ты знаешь?..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, pagid, Вы писали:
EP>>Я привёл пример с вполне практическим значением — граф односвязного списка с циклом. P>И в чем польза представления последовательности псевдослучайных чисел в виде графа?
Не самой последовательности псевдослучайных чисел, а последовательности значений внутреннего состояния генератора (seed).
1. Понимание структуры задачи. Увидев/представив/визуализировав граф в виде буквы Р (цикл с ручкой) — всё сразу становится предельно ясно.
2. Алгоритм поиска цикла, его длины и положения, для графов виде буквы P применим и для псевдослучайных генераторов.
EP>>Аналогичная структура возникает например внутри псевдослучайных генераторов. P>И уж если возвращаться к математике с её более-менее строгими формулировками, не структура возникает в генераторе, а последовательность чисел можно представить в виде графа. Можно и не представлять.
Именно что возникает структура, и именно что с точки зрения математики. Речь не о структуре данных, а о математической структуре. И такие структуры существуют независимо от того выражены ли они явно в коде или нет.
Здравствуйте, B0FEE664, Вы писали:
BFE>Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
Ну, A*, например, часто использую...
BFE>Когда я говорю про графы, я не говорю про деревья.
Если пользоваться общепринятой терминологией, понимать коллег будет проще...
EP>>Это смотря как посмотреть. Список может иметь цикл, а дерево — нет BFE>Что-то я не припомню, чтобы я когда-то использовал список с циклом внутри... Наличие цикла внутри списка свидетельствует об ошибке, так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...
std::list когда-нибудь юзал?..
BFE>И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
А что такое "в явном виде"? Ну и ты же алгоритмы просил? Как найти длину цикла генератора?
BFE>Ну и где там граф? Там нельзя получить граф, как структуру. Нельзя запустить поиск по графу, если я правильно понимаю.
Таки std::vector<std::vector<int> > g, где g[i] — массив индексов соседних с i-й вершин -- одно из популярных ЯВНЫХ представлений графов
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Да ничего особенного, просто уметь применять на практике
Скажем коллега иногда просит умножить два "широких" целых числа (в смысле код написать), тех кто не довел до рабочего состояния с 3го раза считает проф-непригодными
Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
А дальше — специфика конкретной области.
В CAD и геймдеве понятное дело будет линейка, кватернионы, простые численные методы.
Яндекс любит всякие сортировки на внешней памяти, суффиксные деревья, стемминг и т.п.
Здравствуйте, ferz1, Вы писали:
F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Если работа не связана с какими-то специальными математическими методами и моделями -- ноль.
Здравствуйте, rm822, Вы писали:
R>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде.
(при этом количество каких-то из операций необязательно прямо пропорционально затраченному времени на реальном железе, поэтому строго говоря нужно делать соответствующие оговорки)
Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде. EP>(при этом количество каких-то из операций необязательно прямо пропорционально затраченному времени на реальном железе, поэтому строго говоря нужно делать соответствующие оговорки) EP>Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.
Даже при этих уточнения остаются без ответов вопросы: зачем нужен логарифм десяти, и почему непременно по основанию два.
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>Даже при этих уточнения остаются без ответов вопросы: зачем нужен логарифм десяти, и почему непременно по основанию два.
Да, согласен — не нужно ни то, ни другое. Подозреваю что логарифм десяти взялся из попытки разложить логарифм произведения, на сумму логарифмов.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, rm822, Вы писали:
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
скорее всего он под 100K имел в виду 100 тысяч и из-за употребления "K" у него мысль немного мигрировала в сторону двоичной арифметики, смешав в кучу десятичный логарифм с двоичным (наверное, он хотел сказать "выгоняю тех кто не может посчитать десятичный логарифм от 10 или считает его [ логарифм в формуле максимального времени ] по основанию e")
Здравствуйте, LaptevVV, Вы писали:
BFE>>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>>А как же например вездесущие деревья? BFE>>Деревья — это частный случай, который намного проще. LVV>Не. Зависит от графа и дерева... LVV>В-деревья, АВЛ-деревья — покруче некоторых графов будут...
Не могу согласиться. Деревья принципиально проще графов. Достаточно посмотреть на количество открытых проблем с ними связанных, чтобы это подметить.
Здравствуйте, Erop, Вы писали:
BFE>>Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде. E>Ну, A*, например, часто использую...
И что это означает?
BFE>>Когда я говорю про графы, я не говорю про деревья. E>Если пользоваться общепринятой терминологией, понимать коллег будет проще...
Если дерево называть графом, то проблемы в понимании будут.
EP>>>Это смотря как посмотреть. Список может иметь цикл, а дерево — нет BFE>>Что-то я не припомню, чтобы я когда-то использовал список с циклом внутри... Наличие цикла внутри списка свидетельствует об ошибке, так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом... E>std::list когда-нибудь юзал?..
да.
BFE>>И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов? E>А что такое "в явном виде"?
Это когда хранятся и используются все переходы графа.
E>Ну и ты же алгоритмы просил?
да. E>Как найти длину цикла генератора?
Мне на практике такая задача никогда не встречалась, но я сомневаюсь, что для её решения надо строить граф переходов в памяти компьютера.
BFE>>Ну и где там граф? Там нельзя получить граф, как структуру. Нельзя запустить поиск по графу, если я правильно понимаю. E>Таки std::vector<std::vector<int> > g, где g[i] — массив индексов соседних с i-й вершин -- одно из популярных ЯВНЫХ представлений графов Я в курсе. Но если из всего внешнего массива доступен только один элемент, то это не граф.
Здравствуйте, B0FEE664, Вы писали:
E>>Ну, A*, например, часто использую... BFE>И что это означает?
Гуглофу на нуле что ли?
BFE>Если дерево называть графом, то проблемы в понимании будут.
А если лес, например? А если в дереве склеивать совпадающие подветки? Это будет дерево или ациклический направленный граф?
E>>std::list когда-нибудь юзал?.. BFE>да.
AFAIK, одна из популярных реализаций базируется на зацикленном списке нод...
BFE>Это когда хранятся и используются все переходы графа.
А что значит "хранятся"? Если есть функция, которая по id ноды может вернуть id следующей ноды, это в явном виде? Если таки да, то чем ГПСЧ не "явный граф"?
Чем списки соседей в соц. сети не явное представление графа?
BFE>Мне на практике такая задача никогда не встречалась, но я сомневаюсь, что для её решения надо строить граф переходов в памяти компьютера.
А для поиска цикла в списке, нужно?
BFE> Я в курсе. Но если из всего внешнего массива доступен только один элемент, то это не граф.
Это ты о чём?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>>>Ну, A*, например, часто использую... BFE>>И что это означает? E>Гуглофу на нуле что ли?
А область применения?
А то я однажды решал задачу прокладки пути от A к B с обходом препятствий и оказалось, что графы там не нужны.
BFE>>Если дерево называть графом, то проблемы в понимании будут. E>А если лес, например? А если в дереве склеивать совпадающие подветки? Это будет дерево или ациклический направленный граф?
Это будет два объекта: дерево и список.
E>>>std::list когда-нибудь юзал?.. BFE>>да. E>AFAIK, одна из популярных реализаций базируется на зацикленном списке нод...
Интересно. Где можно глянуть?
BFE>>Это когда хранятся и используются все переходы графа. E>А что значит "хранятся"? Если есть функция, которая по id ноды может вернуть id следующей ноды, это в явном виде? Если таки да, то чем ГПСЧ не "явный граф"?
Конечно это не граф.
Вы наверное и вот здесь:
int f(int n)
{
return (n + 1) % 5;
}
граф увидите.
E>Чем списки соседей в соц. сети не явное представление графа?
Вот когда список всех пользователей соц. сети лежит в базе данных, то можно сказать, что в базе данных лежит граф в явном виде. Но если в ничего с этим графом не делаете, то вам от этого ни жарко, ни холодно. Для того, чтобы его можно было рассматривать как граф, нужно чтобы к нему применялись спец алгоритмы применимые к графу. Evgeny.Panasyuk нашел один такой алгоритм, который, наверное, применяется в LinkedIn — поиск знакомого, через знакомого. Вы знаете ещё такие же задачи?
BFE>>Мне на практике такая задача никогда не встречалась, но я сомневаюсь, что для её решения надо строить граф переходов в памяти компьютера. E>А для поиска цикла в списке, нужно?
Нет, конечно.
BFE>> Я в курсе. Но если из всего внешнего массива доступен только один элемент, то это не граф. E>Это ты о чём?
Это я о списке друзей из соц сети.
объект std::vector<std::vector<int> > является графом только тогда, когда к нему применяются алгоритмы применимые к графу.
Здравствуйте, B0FEE664, Вы писали:
E>>Гуглофу на нуле что ли? BFE>А область применения?
Поиск путей в графе
BFE>А то я однажды решал задачу прокладки пути от A к B с обходом препятствий и оказалось, что графы там не нужны.
Бывает. Я, обычно, ищу пути в довольно абстрактных графах. Хотя, иногда, и в графах вполне графической природы. Например, в графе линейного деления...
E>>А если лес, например? А если в дереве склеивать совпадающие подветки? Это будет дерево или ациклический направленный граф? BFE>Это будет два объекта: дерево и список.
Что? Ациклический граф, полученный склеиванием одинаковых веток деревьев?
BFE>Интересно. Где можно глянуть?
Начни с реализации stl в твоём компиляторе
На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д...
BFE>
Ну, да. Это можно интерпретировать, как граф. Например, если рассматривать любые целые n...
E>>Чем списки соседей в соц. сети не явное представление графа? BFE>Вот когда список всех пользователей соц. сети лежит в базе данных, то можно сказать, что в базе данных лежит граф в явном виде. Но если в ничего с этим графом не делаете, то вам от этого ни жарко, ни холодно. Для того, чтобы его можно было рассматривать как граф, нужно чтобы к нему применялись спец алгоритмы применимые к графу. Evgeny.Panasyuk нашел один такой алгоритм, который, наверное, применяется в LinkedIn — поиск знакомого, через знакомого. Вы знаете ещё такие же задачи?
Поиск людей, к которым ведёт много коротких путей, что бы предложить их добавить в своих друзей.
Анализ структуры графа, что бы выявлять накрутки и т. д...
E>>А для поиска цикла в списке, нужно? BFE>Нет, конечно.
Ну так список с циклом это же таки граф?
Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же?
BFE>объект std::vector<std::vector<int> > является графом только тогда, когда к нему применяются алгоритмы применимые к графу.
И?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Ни зачем, считай как хочешь лишь бы правильно было, задача на устный счет и адекватность, прнимаются ответы и "чуть больше десяти" и любой конкретный от 12 до 15
Почти все адекватные по привычке работают с 2-чным степенным рядом
Неадекватные
* не могут связать вопрос с n log n
* не знают что такое логарифм
* умерли на подсчетах взяв его по основанию е
Здравствуйте, Erop, Вы писали:
E>Поиск путей в графе
Это понятно, что поиск пути. А в какой задаче его искать-то потребовалось?
BFE>>А то я однажды решал задачу прокладки пути от A к B с обходом препятствий и оказалось, что графы там не нужны. E>Бывает. Я, обычно, ищу пути в довольно абстрактных графах. Хотя, иногда, и в графах вполне графической природы. Например, в графе линейного деления...
Ну а я как-то обхожусь без этого.
E>>>А если лес, например? А если в дереве склеивать совпадающие подветки? Это будет дерево или ациклический направленный граф? BFE>>Это будет два объекта: дерево и список. E>Что? Ациклический граф, полученный склеиванием одинаковых веток деревьев?
Значит я не понял, что значит склеивать.
BFE>>Интересно. Где можно глянуть? E>Начни с реализации stl в твоём компиляторе E>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д...
О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар...
Похоже, что авторы, таки, реализовали эту абсурдную идею с графом из одной вершины.
Нет, ну я не могу отвечать за это извращение. Мало ли, что там под капот засунули...
BFE>>
BFE>>граф увидите. E>Ну, да. Это можно интерпретировать, как граф. Например, если рассматривать любые целые n...
А можно и не рассматривать...
E>Поиск людей, к которым ведёт много коротких путей, что бы предложить их добавить в своих друзей.
Ok. Принимается. E>Анализ структуры графа, что бы выявлять накрутки и т. д...
Не, анализ — это не то...
Анализ — это не для пользователей, а для аналитиков. Аналитики любят красивые картинки...
E>>>А для поиска цикла в списке, нужно? BFE>>Нет, конечно. E>Ну так список с циклом это же таки граф?
Да, список с циклом, это, таки, граф. А что?
E>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же?
Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю.
BFE>>объект std::vector<std::vector<int> > является графом только тогда, когда к нему применяются алгоритмы применимые к графу. E>И?
И они крайне редко нужны на практике.
Здравствуйте, B0FEE664, Вы писали:
BFE>>>Интересно. Где можно глянуть? E>>Начни с реализации stl в твоём компиляторе E>>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д... BFE>О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар...
Нет, необязательно. У end'а может быть другой тип (базовый), не включающий память под пользовательские данные.
E>>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же? BFE>Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю.
Алгоритм тот же самый, который как раз обходит структуру. А тот же самый он потому, что структура (в общепринятом математическом смысле) в обоих случаях одинаковая.
А вот выражены ли связи в коде явно как указатели, или же задаются функцией перехода — на применимость алгоритма не влияют
Здравствуйте, Evgeny.Panasyuk, Вы писали:
E>>>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д... BFE>>О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар... EP>Нет, необязательно. У end'а может быть другой тип (базовый), не включающий память под пользовательские данные.
Может, но в исходниках именно так. А почему вообще нельзя обойтись без этой ноды?
E>>>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же? BFE>>Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю. EP>Алгоритм тот же самый, который как раз обходит структуру. А тот же самый он потому, что структура (в общепринятом математическом смысле) в обоих случаях одинаковая. EP>А вот выражены ли связи в коде явно как указатели, или же задаются функцией перехода — на применимость алгоритма не влияют
В теории — да, не влияют, а вот на практике зависит от задачи.
В тех же соц. сетях, например, граф друзей сейчас и через секунду — это два разных графа.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
BFE>>>>Иначе это уже не список. EP>>>Почему? Например кольцевой список BFE>>Например потому, что std::find к нему применить прямо не получится. EP>Это не "не список", а "не диапазон по определению STL". Но речи о том что это будет диапазоном STL — не было.
Хорошо, согласен. Кольцевой буфер я использовал на практике, кольцевой список — никогда.
EP>И повторюсь, я не про ту ассоциативность которая левая или правая, а про ту которая позволяет скобки переставлять без изменения результата. И вот она в явном виде в коде практически не выражается, при этом используется неявно (без выражения непосредственно в коде) например при параллельной редукции. Собственно это пример к моему исходному поинту о том, что даже если что-то в коде не выражается явно, это не означает что эти знания не полезны и не нужны.
Ассоциативность явно применяется во многих рекурсивных алгоритмах вида:
f(a,b,c...)
{
return a + f(b,c...);
}
EP>Мои основные тезисы: EP>- обозначенные знания не являются жёстким требованием ко всем программистам. Да, без них получится создавать реальный код, решающий некоторые реальные задачи, и получать за это реальное вознаграждение. EP>- для тех кто хочет стать хорошим программистом — эти знания обязательны. EP>- даже если допустить что эти знания являются балластом и на практике не нужны — они всё равно проверяются на некоторых реальных собеседованиях, что немаловажно.
Согласен. Но не понятно, почему выбраны именно эти знания.
EP>- программирование по большей части это математическая активность — так как происходит оперирование абстрактными объектами, идеями и структурами. Более того — это строгая (rigour) математическая активность, так как нет возможности пропустить "очевидные" этапы и шаги — нужно закодировать всё — от самых низших уровней до высших. ЕМНИП, подобный тезис был у Александра Степанова. С этой позиции заявления вида "программистам математика не нужна" нелепы.
Не соглашусь. В математике легко можно пропустить те или иные действия (по ошибке), в отличии от программирования.
Здравствуйте, B0FEE664, Вы писали:
E>>>>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д... BFE>>>О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар... EP>>Нет, необязательно. У end'а может быть другой тип (базовый), не включающий память под пользовательские данные. BFE>Может, но в исходниках именно так.
Я посмотрел в исходниках libstdc++ — насколько я распарсил, там именно так — последний узел имеет только два указателя, без места под данные.
В других реализациях может быть по-другому.
BFE>А почему вообще нельзя обойтись без этой ноды?
Ты имеешь в виду использовать вместо неё nullptr? Не получится — список двусвязный, мы можем взять std::prev от .end(). Можно конечно попробовать без дополнительного узла, но будет сложнее, а главное медленнее.
Да и проблемы в дополнительной ноде нет никакой — она хранится по значению в std::list, и содержит только два указателя которые нужны в любом случае.
То есть схематически там следующая структура данных:
template<typename T, ...>
class list
{
struct base_node
{
base_node *prev, *next;
};
struct value_node : base_node
{
T value;
};
base_node end_node;
...
};
Из этого кстати вытекает что итератор .end() у такого списка инвалидируется при swap'е и т.п., что не запрещено стандартном:
no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ]
Здравствуйте, B0FEE664, Вы писали:
E>>>>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же? BFE>>>Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю. EP>>Алгоритм тот же самый, который как раз обходит структуру. А тот же самый он потому, что структура (в общепринятом математическом смысле) в обоих случаях одинаковая. EP>>А вот выражены ли связи в коде явно как указатели, или же задаются функцией перехода — на применимость алгоритма не влияют BFE>В теории — да, не влияют, а вот на практике зависит от задачи. BFE>В тех же соц. сетях, например, граф друзей сейчас и через секунду — это два разных графа.
Не вдаваясь в конкретные детали сказанного, то о чём ты говоришь — это переход к другой математической структуре, в которой возможно не выполняются изначальные математические требования.
Например если у тебя есть нечто похожее на группу, но например не имеющее обратного элемента каждому, то применять алгоритмы для групп и использовать теоремы/свойства групп естественно некорректно.
Но из этого не следует ни бесполезность теории групп, ни математики в целом. У тебя в этом случае другая математическая структура, например моноид, и ты можешь использовать алгоритмы и математические свойства для моноидов. Либо например можешь выделить группу из этой структуры, по аналогии с GLn(R) — и уже работать с этой группой.
Также и с графами — если у тебя например не один граф, а целое множество графов соответствующее предыдущим состояниям во времени — то и используй соответствующий мат.аппарат
Здравствуйте, B0FEE664, Вы писали:
EP>>И повторюсь, я не про ту ассоциативность которая левая или правая, а про ту которая позволяет скобки переставлять без изменения результата. И вот она в явном виде в коде практически не выражается, при этом используется неявно (без выражения непосредственно в коде) например при параллельной редукции. Собственно это пример к моему исходному поинту о том, что даже если что-то в коде не выражается явно, это не означает что эти знания не полезны и не нужны. BFE>Ассоциативность явно применяется во многих рекурсивных алгоритмах вида: BFE>
BFE>f(a,b,c...)
BFE>{
BFE> return a + f(b,c...);
BFE>}
BFE>
BFE>
Это не применение ассоциативности, а как раз наоборот — использование жёсткого порядка, а конкретно правая свёртка а-ля foldr.
Применение ассоциативности это например быстрый алгоритм возведения в натуральную степень, который как раз работает за счёт "перестановки скобок" https://www.sgi.com/tech/stl/power.html
И даже там, ассоциативность непосредственно в коде явно никак не выражена, только в имени типа и в документации. Там нигде нету выражения (x*y)*z == x*(y*z), тем не менее это математическое свойство используются неявно.
EP>>Мои основные тезисы: EP>>- обозначенные знания не являются жёстким требованием ко всем программистам. Да, без них получится создавать реальный код, решающий некоторые реальные задачи, и получать за это реальное вознаграждение. EP>>- для тех кто хочет стать хорошим программистом — эти знания обязательны. EP>>- даже если допустить что эти знания являются балластом и на практике не нужны — они всё равно проверяются на некоторых реальных собеседованиях, что немаловажно. BFE>Согласен. Но не понятно, почему выбраны именно эти знания.
Видимо потому что это общие знания, которые широкоприменимы и широкоизвестны.
EP>>- программирование по большей части это математическая активность — так как происходит оперирование абстрактными объектами, идеями и структурами. Более того — это строгая (rigour) математическая активность, так как нет возможности пропустить "очевидные" этапы и шаги — нужно закодировать всё — от самых низших уровней до высших. ЕМНИП, подобный тезис был у Александра Степанова. С этой позиции заявления вида "программистам математика не нужна" нелепы. BFE>Не соглашусь. В математике легко можно пропустить те или иные действия (по ошибке), в отличии от программирования.
Так я же и говорю что программирование как математическая активность более строгая нежели другие распространённые варианты — именно потому что нельзя ничего пропустить и отдать на откуп интуиции, нужно всё закодировать начиная с самого низкого уровня.
Здравствуйте, B0FEE664, Вы писали: BFE>Ну а я как-то обхожусь без этого.
Ну задачи просто разные... BFE>Значит я не понял, что значит склеивать.
у дерева есть несколько идентичных поддеревьев. Вместо того, что бы хранить/обрабатывать несколько копий этих поддеревьев, мы храним/обрабатываем ациклический ориентированный граф, где вместо этих совпадающих поддеревьев мы имеем переходы на единственную копию.
Например, если мы будем строить бор (префиксное дерево) русского языка, будет полезно "склеить" поддеревья падежных окончаний .
BFE>О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар... BFE>Похоже, что авторы, таки, реализовали эту абсурдную идею с графом из одной вершины. BFE>Нет, ну я не могу отвечать за это извращение. Мало ли, что там под капот засунули...
Просто ты предвзят. Я уверен, что если ты попробуешь, то твоей квалификации хватит реализовать такой список БЕЗ ОВЕРХЕДА...
не подсматривай
class list_node_base {
publc:
list_node_base() { next = prev = this; }
~list_node_base() { next->prev = prev; prev->next = next; }
list_node_base* get_next() { retrn assert_not_null( next ); }
list_node_base* get_prev) { retrn assert_not_null( prev ); }
bool is_along() const { return prev == this; }
void insert_after_me( list_node_base* node )
{
assert( node != 0 && node->is_along() );
node->prev = this;
node->next = next;
next->prev = node;
next = node;
}
void detach()
{
next->prev = prev;
prev->next = next;
prev = next = this;
}
protected:
list_node_base( list_node_base* prev_node ) : prev( prev_node ), next( prev_node->next )
{ prev_node->next = next->prev = this; }
static list_node_base* assert_not_null( list_node_base* p ) { assert( p != 0 ); return p; }
private:
list_node_base* prev;
list_node_base* next;
};
template<typeneme T>
class my_list : {
public:
class iterator {
public:
iterator( list_node_base* p ) : node( p ) { assert( p != 0 ); }
T* get_ptr() { assert( node != 0 && !node->is_along() ); return static_cast<T*>( node ); }
T& operator*() { return get_ptr(); }
// тут сам допишешьprivate:
list_node_base* node;
};
class riterator {
// тут сам допишешь
};
// константные итераторы тоже сам ;)
iterator end() { return &list_data; }
iterator begin() { return list_data.get_next(); }
riterator end() { return &list_data; }
riterator begin() { return list_data.get_prev(); }
private:
class node : public list_node_base {
public:
T data;
// тут сам допишешь
};
list_node_base list_data;
};
BFE>А можно и не рассматривать...
От задач зависит...
Если ты про графы не знаешь, а такой взгляд в задаче полезен, то упс.
Просто в твоей области графы, видимо, не особо нужны. Хотя мне не ясно, как ты искал путь, без чего-то вроде A*, хотя бы и самопального. BFE>Не, анализ — это не то... BFE>Анализ — это не для пользователей, а для аналитиков. Аналитики любят красивые картинки...
То. На графе связей пользователя можно, например, обучить классификатор, который отличает ботов от реальных людей... E>>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же? BFE>Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю.
И что? Там у структуры мы вызываем метод get_next_node_ptr(), а тут вызываем метод get_next_seed()/
Оба возвращают некое Id узла. В чём разница для алгоритма поиска цикла в списке? BFE>И они крайне редко нужны на практике.
Зависит от практики
Если, например, формошлёпить для интранета, то математика вообще не нужна, IMHO,..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Я посмотрел в исходниках libstdc++ — насколько я распарсил, там именно так — последний узел имеет только два указателя, без места под данные.
Похоже на то.
EP>В других реализациях может быть по-другому.
Ага:
_Value_type _Myval; // the stored value, unused if head
BFE>>А почему вообще нельзя обойтись без этой ноды? EP>Ты имеешь в виду использовать вместо неё nullptr? Не получится — список двусвязный, мы можем взять std::prev от .end(). Можно конечно попробовать без дополнительного узла, но будет сложнее, а главное медленнее.
Есть варианты. Например, .end() итератор может хранить указатель на сам List, а List может иметь хранить указатель на last. Но придётся заводить отдельный тип, который должен будет мимикрировать под вид обычного итератора...
EP>Да и проблемы в дополнительной ноде нет никакой — она хранится по значению в std::list, и содержит только два указателя которые нужны в любом случае.
Согласен.
