Комментарии 172
Упоминание Фурсенко — это стёб?
Понимаю мысль автора, и в целом согласен. Но уж очень сумбурное и сбивчивое изложение.
хочу поделиться одним примером, наглядно демонстрирующем, насколько она нужна и даже (не побоимся этого слова) необходима.
В статье так и не дан наглядный ответ, какова конечная цель использования этих абстрактных вычислений.
Статья очень тяжело читается, но посыл понятен.
Хочется только добавить что весь вопрос «Нужна ли программисту математика» крутится вокруг непонимания того что есть разделение между ученными и инженерами. Ученные придумывают новые алгоритмы, решают такие вот абстрактные задачи чтобы посоревноваться друг с другом и публиковать статьи. Инженерная же задача тут заключается в том чтобы знать определенный набор решений и шаблонов, которые ученные уже давно разложили по полочкам и применять их на практике, интегрируя их и совмещая чтобы получить продукт укладывающийся в ТЗ. Разумеется, можно пытаться быть компьютерным волшебником-гуру, но на практике человек может эффективно использовать только тот набор умений, который ему присущ в повседневной деятельности. Если программист знает высшую математику хорошо на момент выхода из ВУЗа, то можно быть почти уверенным что через 2-3 года практики от этих знаний останется мало, зато прибавится куча знаний практических вещей, таких как CVS, администрирование, QA и тд. С другой стороны ученные, изобретающие новые алгоритмы и решающие такие вот задачи до сих пор делают это на фортране (утрирую). Правда в том, что везде где решаются на самом деле крупные и новые задачи в штате должны быть разные программисты с разными навыками, уникумов и гениев, увы, на всех на хватит.
Хочется только добавить что весь вопрос «Нужна ли программисту математика» крутится вокруг непонимания того что есть разделение между ученными и инженерами. Ученные придумывают новые алгоритмы, решают такие вот абстрактные задачи чтобы посоревноваться друг с другом и публиковать статьи. Инженерная же задача тут заключается в том чтобы знать определенный набор решений и шаблонов, которые ученные уже давно разложили по полочкам и применять их на практике, интегрируя их и совмещая чтобы получить продукт укладывающийся в ТЗ. Разумеется, можно пытаться быть компьютерным волшебником-гуру, но на практике человек может эффективно использовать только тот набор умений, который ему присущ в повседневной деятельности. Если программист знает высшую математику хорошо на момент выхода из ВУЗа, то можно быть почти уверенным что через 2-3 года практики от этих знаний останется мало, зато прибавится куча знаний практических вещей, таких как CVS, администрирование, QA и тд. С другой стороны ученные, изобретающие новые алгоритмы и решающие такие вот задачи до сих пор делают это на фортране (утрирую). Правда в том, что везде где решаются на самом деле крупные и новые задачи в штате должны быть разные программисты с разными навыками, уникумов и гениев, увы, на всех на хватит.
Я не ученый, но решал много подобных задач, да и до сих пор участвую в некоторых контестах. Ученые как раз занимаются нудным анализом и доказательством, в то время как в олимпиадных задачах обычно достаточно, чтоб прошло тесты. Потому используется много «хаков» неприменимых в науке.
Мне кажется основное разделение между учёными и инженерами, состоит в разнице между индуктивным и дедуктивным выводом.
Учёные видят факты и пытаются найти и обяснить закономерности.
Инженеры же, зная и понимая закономерности, пытаются применить их к конкретным задачам.
С этой зрения, придумывать алгоритмы учёным не надо. Их задача — их исследовать, классифицировать, доказывать корректность.
Придумывание алгоритмов — это скорее изобретательская задача, а значит, лежащая в области инженерии.
Учёные видят факты и пытаются найти и обяснить закономерности.
Инженеры же, зная и понимая закономерности, пытаются применить их к конкретным задачам.
С этой зрения, придумывать алгоритмы учёным не надо. Их задача — их исследовать, классифицировать, доказывать корректность.
Придумывание алгоритмов — это скорее изобретательская задача, а значит, лежащая в области инженерии.
НЛО прилетело и опубликовало эту надпись здесь
То есть, вот сидят учёные, смотрят, что там инженеры напридумывали, и всё это классифицируют, доказывают корректность, оценки сложности и всё такое
Задача науки — изучение окружающего мира. Алгоритмы придуманные инженерами — это часть окружающего мира.
Для изучения мира придумываются абстракци, которые опять же могут быть использованы инженерами.
Придумывание алгоритмов — это дедуктивная задача. Мы идём от общих законов (например, это np — hard проблема, она быстро не решается и плохо аппроксимируется), к конкретной цели (значит нам надо придумать хитрые эвристики и использовать такие и такие особенности)
У чисто научного познания как таковой цели не предусмотрено.
Поэтому изучение атомного ядра (любых веществ, а не только урана) это научная деятельность, а применение общих знаний о ядре к конкретному веществу (дедуктивный вывод) для достижения частной цели (создание атомной бомбы) это уже инженерия.
Получил образование в нулевых в Нижегородском университете (и само-образование, безусловно) по специальности «Математик и системный программист». Работал в инженерии ПО с 15 лет и не переставал с тех пор, с каждым годом в этом ПО было всё больше математики. Жаль, что в большинстве своём люди разделяют математиков и программистов. Для меня это почти что смешно — ведь можно как быть, так и научиться быть, математиком-программистом. Математика — не столько инструмент, сколько великолепный фреймворк для мышления. Знание и умение в git после погружения в динамическую теорию хаоса представляется по сути тривиальной задачей, вся структура (равно как и отсутствие её) во всех существующих инструментах с математическим мышлением видна почти что на ладони, что здорово ускоряет и расширяет процесс освоения и использования инструментов.
Формулирую задачу — сколько различных номеров длиной К, заканчивающихся на заданной кнопке р, можно набрать на клавиатуре телефона (тастатуре), если мы должны перемещаться по кнопкам ходом шахматного коня.
У меня один вопрос — НО ЗАЧЕМ?
Совершенно оболваненКонечно же, это олимпиадная задачка, их специально формулируют в несколько утрированной форме. И цель ее — не подсчитать количество номеров, а обучить приемам оптимизации. Надеюсь, к последнему у вас вопроса «Зачем» нет, нег?
от таких серьезных тем
тихо молвил россиянин:
«Вот же круто — а зачем?»
Ну то есть вы для демонстрации того, что математика нужна не только олимпиадникам, продемонстрировали очередную олимпиадную задачу?
«Несколько утрированной» — это ещё слабо сказано.
Даже не знаю. Если брать только коммерческую разработку, то мне за последние 5 лет приходилось заниматься оптимизацией (именно на производительность) ровно два раза. Это, конечно, ничего не доказывает, но служит хорошей иллюстрацией.
Надеюсь, к последнему у вас вопроса «Зачем» нет, нег?
Даже не знаю. Если брать только коммерческую разработку, то мне за последние 5 лет приходилось заниматься оптимизацией (именно на производительность) ровно два раза. Это, конечно, ничего не доказывает, но служит хорошей иллюстрацией.
НЛО прилетело и опубликовало эту надпись здесь
Вопрос оптимизации в работе встает постоянно. Вот уже не один десяток лет. Долгое время работал в области промавтоматизации — там приходится разрабатывать код, который должен работать быстро (а в большинстве случаев не просто быстро, а с гарантированным временем отклика), надежно и при этом в условиях ограниченных ресурсов (как по памяти, так и по быстродействию). там никто не даст менять оборудование на помощнее только потому, что разработчик не умеет вместо трех вложенных циклов сделать все за один проход. Проще разработчика поменять.
Сейчас занимаюсь разработкой под мейнфреймы. Казалось бы можно расслабиться — одной оперативки в разы больеше чем у многих на диске. Однако периодически сталкиваемся с тем, что пиковая нагрузка на сервера достигает 96-98% И кроме разработки нового приходится пересматривать старое в поисках где что можно оптимизировать.
Тут выручает привычка сразу искать оптимальное решение. И оно находится, если подумать чуть-чуть. Бывали случаи когда первое пришедшее в голову решение (в лоб) давало время выполнения задачи 3 сек (что для данной задачи было неприемлемым), а второе — 150-200 мсек.
Понятно, что всяких сайтописателей все это не волнует — ну и что с того, что сайт грузится медленно? Зато там «все красиво» и рекламы понапихали выше крыши — а это деньги.
У «мобильных разработчиков» из тех, которых заботит только вопрос монетизации своих поделий тоже всегда найдется отмазка — а что вы хотели на таком древнем девайсе?
Сейчас занимаюсь разработкой под мейнфреймы. Казалось бы можно расслабиться — одной оперативки в разы больеше чем у многих на диске. Однако периодически сталкиваемся с тем, что пиковая нагрузка на сервера достигает 96-98% И кроме разработки нового приходится пересматривать старое в поисках где что можно оптимизировать.
Тут выручает привычка сразу искать оптимальное решение. И оно находится, если подумать чуть-чуть. Бывали случаи когда первое пришедшее в голову решение (в лоб) давало время выполнения задачи 3 сек (что для данной задачи было неприемлемым), а второе — 150-200 мсек.
Понятно, что всяких сайтописателей все это не волнует — ну и что с того, что сайт грузится медленно? Зато там «все красиво» и рекламы понапихали выше крыши — а это деньги.
У «мобильных разработчиков» из тех, которых заботит только вопрос монетизации своих поделий тоже всегда найдется отмазка — а что вы хотели на таком древнем девайсе?
К вопросу древности железа.
Насколько древнее железо на ваших мэйнфреймах? Ну и его характеристики узнать тоже хотелось бы, если можно.
На мейнфреймах с железом все в порядке — тестовый IBM Power S824 (18 ядер, 1.85Тб RAM, SSD дисковые массивы 67 + 15Тб). На проде помощнее (но там и задач намного больше крутится) — S828. Точных характеристики не знаю
Общий посыл такой — загрузить под завязку можно любую систему. И чем меньше думать об оптимальности кода при разработке, тем быстрее этот момент наступит. Заниматься переоптимизацией того, что уже работает намного сложнее хотя бы потому, что каждое изменение кода требует потом длительной серии ретестов на неухудшение функциональности.
Поменять железо на помощнее (любимая отмазка плохих разработчиков — «тормозит потому что железо слабое, проапгрейдитесь и все будет ок») не вариант — затраты (даже не считая стоимости самого железа в несколько сотен килобаксов) по переносу всего и вся на новые железяки космические.
Простейший пример с прошлой работы. Была задача по разработке системы мониторинга инженерного оборудования зданий. В качестве одного из конкретных применений — система ЛДСС (лифтовая диспетчерская связь и сигнализация). Так вот, есть ПУБЭЛ (правила установки и безопасной эксплуатации лифтов), согласно которым лифт не имеет права работать без работающей системы ЛДСС. Это значит, что если вы захотите на работающем объекте переустановить (скажем, поставить новую версию) систему, то сначала вы должны отключить все лифты к ней подключенные. Т.е. физически их остановить и заблокировать. А в современных версиях их может быть несколько сотен (штук 300 даже на одной не очень большой диспетчерской). И раскиданы они по всему городу (связь идет по IP каналам). И далеко не все модели могут быть остановлены и заблокированы дистеанционно. Представляете ситуацию — бригады аварийщиков носятся по городу и останавливают лифты просто потому что вам запотимело совтину поменять?
Здесь все еще серьезнее. На порядки.
Масштабы страны во-первых, во-вторых останавливать нельзя. только вводить параллельно, потом убедиться что все работает и только потом выводить старое.
Так что единственный вариант — сразу писать оптимальный код. Для особо критических задач проводить нагрузочное тестирование (это кроме компонентного, интеграционного и бизнес).
Так что над каждой задачей приходится думать. И каждое решение переосмысливать — а можно ли написать оптимальнее? А как можно скроить на количестве ресурсоемких операций? Что вынести в инициализацию чтобы выполнялось один раз, а что придется делать на каждом обороте цикла? Как оптимально распределить функции между master`ом и worker`ами при распараллеливании обработки и как эффективно организовать межпроцессную коммуникацию.
Это то, что касается оптимизации.
Собственно по математике. Достаточно много задач, где математика особо и не нужна. А есть где нужна. На совей спрактике когда-то давно приходилось заниматься разработкой программ для обработки экспериментальных данных. Там использовались методы регрессионного анализа (в те времена книга Грейпера и Смита «Прикладной регрессионный анализ» была настольной). Потом немного коснулся темы молекулярной динамики и машинного моделирования (там и физика — статфизика и математика: микро- и макроканонические ансамбли, связь между функцией распределения параметров отдельных молекул с макропараметрами системы, потенциалы межмолекулярного взаимодействия и т.п.). Совсем краем зацепил клеточные автоматы («Машины клеточных автоматов», автора не помню уже).
Потом был долгий период промавтматизации где математики практически нет. Но параллельно для себя занимался обработкой GPS данных. Там опять математика, в частности в задачах фильтрации GPS треков. Кстати, смотрю на многие мобильные приложения типа спортивных трекеров, работающих с GPS и понимаю, что разработчики вообще не понимают природы данных, которые они получают с чипа и в результате трекеры выдают редкостный бред на экран.
Сейчас вот работа с базами данных. Опять никакой математики, но, как и в промавтоматизации, требуется хорошее знание платформы на которой работаешь, ее возможностей и того, как наиболее эффективно использовать ресурсы.
В целом, дабы быть более-менее эффективным и универсальным разработчиком и не зацикливаться на какой-то узкой области типа рисования семи красных линий одной строчкой кода, математику желательно таки знать. Ну не на уровне д.ф.-м.н., но достаточно свободно ориентироваться, но обладать базой, дающей возможность при необходимости самостоятельно углубиться в нужную тему.
Мне в этом плане повезло — в свое время заканчивал физтех, а это полный курс математики (первые три года 200 часов лекций в семестр — матанализ, аналитическая геометрия, дифференуиальное исчисление, матстатистика, функции комплексных переменных, уравнения матфизики — все это отдельными курсами) плюс полный курс теорфизики по Ландау-Лифшицу плюс еще ряд физических курсов. В жизни не раз помогало в решении на первый взгляд не связанных напрямую с физикой или математикой задач.
Как-то длинно получилось, но такие вот мысли на тему с точки зрения разработчика с 30-летним стажем.
Общий посыл такой — загрузить под завязку можно любую систему. И чем меньше думать об оптимальности кода при разработке, тем быстрее этот момент наступит. Заниматься переоптимизацией того, что уже работает намного сложнее хотя бы потому, что каждое изменение кода требует потом длительной серии ретестов на неухудшение функциональности.
Поменять железо на помощнее (любимая отмазка плохих разработчиков — «тормозит потому что железо слабое, проапгрейдитесь и все будет ок») не вариант — затраты (даже не считая стоимости самого железа в несколько сотен килобаксов) по переносу всего и вся на новые железяки космические.
Простейший пример с прошлой работы. Была задача по разработке системы мониторинга инженерного оборудования зданий. В качестве одного из конкретных применений — система ЛДСС (лифтовая диспетчерская связь и сигнализация). Так вот, есть ПУБЭЛ (правила установки и безопасной эксплуатации лифтов), согласно которым лифт не имеет права работать без работающей системы ЛДСС. Это значит, что если вы захотите на работающем объекте переустановить (скажем, поставить новую версию) систему, то сначала вы должны отключить все лифты к ней подключенные. Т.е. физически их остановить и заблокировать. А в современных версиях их может быть несколько сотен (штук 300 даже на одной не очень большой диспетчерской). И раскиданы они по всему городу (связь идет по IP каналам). И далеко не все модели могут быть остановлены и заблокированы дистеанционно. Представляете ситуацию — бригады аварийщиков носятся по городу и останавливают лифты просто потому что вам запотимело совтину поменять?
Здесь все еще серьезнее. На порядки.
Масштабы страны во-первых, во-вторых останавливать нельзя. только вводить параллельно, потом убедиться что все работает и только потом выводить старое.
Так что единственный вариант — сразу писать оптимальный код. Для особо критических задач проводить нагрузочное тестирование (это кроме компонентного, интеграционного и бизнес).
Так что над каждой задачей приходится думать. И каждое решение переосмысливать — а можно ли написать оптимальнее? А как можно скроить на количестве ресурсоемких операций? Что вынести в инициализацию чтобы выполнялось один раз, а что придется делать на каждом обороте цикла? Как оптимально распределить функции между master`ом и worker`ами при распараллеливании обработки и как эффективно организовать межпроцессную коммуникацию.
Это то, что касается оптимизации.
Собственно по математике. Достаточно много задач, где математика особо и не нужна. А есть где нужна. На совей спрактике когда-то давно приходилось заниматься разработкой программ для обработки экспериментальных данных. Там использовались методы регрессионного анализа (в те времена книга Грейпера и Смита «Прикладной регрессионный анализ» была настольной). Потом немного коснулся темы молекулярной динамики и машинного моделирования (там и физика — статфизика и математика: микро- и макроканонические ансамбли, связь между функцией распределения параметров отдельных молекул с макропараметрами системы, потенциалы межмолекулярного взаимодействия и т.п.). Совсем краем зацепил клеточные автоматы («Машины клеточных автоматов», автора не помню уже).
Потом был долгий период промавтматизации где математики практически нет. Но параллельно для себя занимался обработкой GPS данных. Там опять математика, в частности в задачах фильтрации GPS треков. Кстати, смотрю на многие мобильные приложения типа спортивных трекеров, работающих с GPS и понимаю, что разработчики вообще не понимают природы данных, которые они получают с чипа и в результате трекеры выдают редкостный бред на экран.
Сейчас вот работа с базами данных. Опять никакой математики, но, как и в промавтоматизации, требуется хорошее знание платформы на которой работаешь, ее возможностей и того, как наиболее эффективно использовать ресурсы.
В целом, дабы быть более-менее эффективным и универсальным разработчиком и не зацикливаться на какой-то узкой области типа рисования семи красных линий одной строчкой кода, математику желательно таки знать. Ну не на уровне д.ф.-м.н., но достаточно свободно ориентироваться, но обладать базой, дающей возможность при необходимости самостоятельно углубиться в нужную тему.
Мне в этом плане повезло — в свое время заканчивал физтех, а это полный курс математики (первые три года 200 часов лекций в семестр — матанализ, аналитическая геометрия, дифференуиальное исчисление, матстатистика, функции комплексных переменных, уравнения матфизики — все это отдельными курсами) плюс полный курс теорфизики по Ландау-Лифшицу плюс еще ряд физических курсов. В жизни не раз помогало в решении на первый взгляд не связанных напрямую с физикой или математикой задач.
Как-то длинно получилось, но такие вот мысли на тему с точки зрения разработчика с 30-летним стажем.
> Кстати, смотрю на многие мобильные приложения типа спортивных трекеров, работающих с GPS и понимаю, что разработчики вообще не понимают природы данных, которые они получают с чипа и в результате трекеры выдают редкостный бред на экран.
Не связано ли это с какими-нибудь законодательными ограничениями? Возможно, что разработка сверхточных GPS наказуема (возможно даже уголовно)
Не связано ли это с какими-нибудь законодательными ограничениями? Возможно, что разработка сверхточных GPS наказуема (возможно даже уголовно)
Ничего такого нет.
Речь не о субметровой точности (там нет зконодательных ограничений, насколько я в курсе, там ограничения технического характера), речь о бреде, который эти программы выводят на экран.
Есть мобильные приложения — спортвные трекеры. Например, катаемся на горных лыжах, на телефоне запущено такое приложение. По итогу оно нам показывает суммарный набор-потерю высоты, сколько по расстоянию накатали, максимальную скорость на спуске. Так вот периодически люди (обычно новички) в профильных форумах начинают хватстаться что у них где-то там максимальная скорость была аж 120км/ч (порядок величин такой). при том, что такая скорость характерна для спортсменов на соревнованиях по скоростному спуску на этапах КМ. Но те-то едут в обтекаемых комбезах в низкой аэродинамической стойке на 2+ м спусковых лыжах и по очень жесткой трассе. Для любителя в куртке и широких штанах на обычных лыжах такое в принципе недостижимо.
Да, такая цифра может придти с чипа, но надо понимать откуда она взялась и как соотносится с реальностью. На тему измерения скорости с помощью GPS написано много статей с разбором в каких ситуациях какая погрешность возможна. Есть сообщество спидсерферов (speedsurfing), которые измеряют скорость с помощью GPS и сравнивают ее с другими — у них разработаны методики записи и обработки треков для получения адекватных сравнимых величин.
Но во все это надо вникать, разбираться. А в мобильную разработку пришло огромное количество… даже не знаю как назвать… людей, которые больше озабочены проблемами монетизации, чем реальной полезностью своей разработки.
Второй пример, с теми же трекерами. Велсипед. Человек покатался по парку (условно) и хвастается что у него суммарный набор высоты аж полтора километра. Ага. На 30-50 километров пути. Родной, откуда? Ты в Альпах через перевалы катался?
Опять нужно понимать, что точность определения высоты в силу физики процесса в GPS на порядок ниже точности определения координат. И в отсутствии барометрического альтиметра в приборе высота даже стоя на месте будет «плавать» и накручивать «суммарный набор». А при наличии оного его нужно регулярно калибровать.
Кроме того, суммарный набор неплохо накручиватеся на мелких кочках. Метр туда, метр сюда, глядишь и полтора километра набежало.
Все это нужно фильтровать и указывать что набрал столько-то при таких-то настройках (скажем, не учитывал наборы на уклонах меньше одного градуса, не учитывал единичные перепады менее полутора метров и т.п.)
Есть мобильные приложения — спортвные трекеры. Например, катаемся на горных лыжах, на телефоне запущено такое приложение. По итогу оно нам показывает суммарный набор-потерю высоты, сколько по расстоянию накатали, максимальную скорость на спуске. Так вот периодически люди (обычно новички) в профильных форумах начинают хватстаться что у них где-то там максимальная скорость была аж 120км/ч (порядок величин такой). при том, что такая скорость характерна для спортсменов на соревнованиях по скоростному спуску на этапах КМ. Но те-то едут в обтекаемых комбезах в низкой аэродинамической стойке на 2+ м спусковых лыжах и по очень жесткой трассе. Для любителя в куртке и широких штанах на обычных лыжах такое в принципе недостижимо.
Да, такая цифра может придти с чипа, но надо понимать откуда она взялась и как соотносится с реальностью. На тему измерения скорости с помощью GPS написано много статей с разбором в каких ситуациях какая погрешность возможна. Есть сообщество спидсерферов (speedsurfing), которые измеряют скорость с помощью GPS и сравнивают ее с другими — у них разработаны методики записи и обработки треков для получения адекватных сравнимых величин.
Но во все это надо вникать, разбираться. А в мобильную разработку пришло огромное количество… даже не знаю как назвать… людей, которые больше озабочены проблемами монетизации, чем реальной полезностью своей разработки.
Второй пример, с теми же трекерами. Велсипед. Человек покатался по парку (условно) и хвастается что у него суммарный набор высоты аж полтора километра. Ага. На 30-50 километров пути. Родной, откуда? Ты в Альпах через перевалы катался?
Опять нужно понимать, что точность определения высоты в силу физики процесса в GPS на порядок ниже точности определения координат. И в отсутствии барометрического альтиметра в приборе высота даже стоя на месте будет «плавать» и накручивать «суммарный набор». А при наличии оного его нужно регулярно калибровать.
Кроме того, суммарный набор неплохо накручиватеся на мелких кочках. Метр туда, метр сюда, глядишь и полтора километра набежало.
Все это нужно фильтровать и указывать что набрал столько-то при таких-то настройках (скажем, не учитывал наборы на уклонах меньше одного градуса, не учитывал единичные перепады менее полутора метров и т.п.)
Но те-то едут в обтекаемых комбезах в низкой аэродинамической стойке на 2+ м спусковых лыжах и по очень жесткой трассе.
начинают хватстаться что у них где-то там максимальная скорость была аж 120км/ч
Мне кажется эти вещи не противоречат друг другу. Спортсмены едут по вешкам, любители же, как психопаты по прямой вниз с хорошим уклоном (сам таким был). Это не сложно. Когда спортсмен в действительно аэродинамическом эквипе едет просто вниз по прямой он 250 км\ч выжимает :)
Тут дело в другом. GPS достаточно точно измеряет скорость (измерения основаны на эффекте Доплера, подробности можно нагуглить — статей на эту тему достаточно много) при условии прямолинейного равномерного движения. Например, на автомобиле, когда прибор лежит на передней панели (например) и машина движется примерно с одинаковой скоростью. Тогда погрешность измерения невелика — порядка 0.1 м/с.
При катании на лыжах ситуация радикально иная. Во-первых, лыжник все-таки движется дугами т.е. постоянно меняет направление. Во-вторых, прибор обычно лежит в кармане где-то в верхней половине корпуса. Т.е. при перекантовках и смене ангуляции прибор вместе с корпусом совершает резкое движение перпендикулярно траектории.
Все это резко повышает погрешность измерения скорости и в максималку может попасть не скорость лыжника, а вот эта скорость самого прибора в момент перекантовки.
Я накопил достаточно большую коллекцию треков, записанных логгером (он тупо пишет nmea поток с чипа с частотой 5 точек в секунду на карту памяти). Просмотр таких треков по точкам показывает кратковременные рывки скорости именно в такие моменты, как указано выше.
Методика спидсерферов такая — в зачет идет усредненная на 5-10 секунд скорость на прямолинейном отрезке. Это более адекватный параметр. Возможно, там еще отбрасываются «хвосты» по правилу трех сигм. У них есть специальный софт для анализа треков и участники просто присылают свои треки, а результаты уже выдаются софтом.
У мобильных приложений далеко не у всех заложена хоть какая-то фильтрация. Многие выводят напрямую то, что прилетело с чипа.
Я далеко не все смотрел, из точно фильтрующих видел meRun (для андроида, для Blackberry пользуюсь ей же, там называется CascaRun). Правда, описания алгоритма фильтрации не знаю. Но какие-то настройки фильтров там есть.
Для компа сам писал анализатор треков. Там много всяких фильтров для прочистки треков и удаления недостоверных (в т.ч. и по скорости) точек и подсчета статистики.
При катании на лыжах ситуация радикально иная. Во-первых, лыжник все-таки движется дугами т.е. постоянно меняет направление. Во-вторых, прибор обычно лежит в кармане где-то в верхней половине корпуса. Т.е. при перекантовках и смене ангуляции прибор вместе с корпусом совершает резкое движение перпендикулярно траектории.
Все это резко повышает погрешность измерения скорости и в максималку может попасть не скорость лыжника, а вот эта скорость самого прибора в момент перекантовки.
Я накопил достаточно большую коллекцию треков, записанных логгером (он тупо пишет nmea поток с чипа с частотой 5 точек в секунду на карту памяти). Просмотр таких треков по точкам показывает кратковременные рывки скорости именно в такие моменты, как указано выше.
Методика спидсерферов такая — в зачет идет усредненная на 5-10 секунд скорость на прямолинейном отрезке. Это более адекватный параметр. Возможно, там еще отбрасываются «хвосты» по правилу трех сигм. У них есть специальный софт для анализа треков и участники просто присылают свои треки, а результаты уже выдаются софтом.
У мобильных приложений далеко не у всех заложена хоть какая-то фильтрация. Многие выводят напрямую то, что прилетело с чипа.
Я далеко не все смотрел, из точно фильтрующих видел meRun (для андроида, для Blackberry пользуюсь ей же, там называется CascaRun). Правда, описания алгоритма фильтрации не знаю. Но какие-то настройки фильтров там есть.
Для компа сам писал анализатор треков. Там много всяких фильтров для прочистки треков и удаления недостоверных (в т.ч. и по скорости) точек и подсчета статистики.
Например, на автомобиле, когда прибор лежит на передней панели (например) и машина движется примерно с одинаковой скоростью. Тогда погрешность измерения невелика — порядка 0.1 м/с.Если прибор — смартфон, закрепленный на панели, а я еду на круизе, то можно смело подстраивать круиз по данным GPS до 109,9 (для ограничения в 90)?
С учетом того, что круиз ±2 км/ч болтает разумеется.
Во-первых, лыжник все-таки движется дугами т.е. постоянно меняет направление.
Да нет. Он движется по прямой и вниз ) Во всяком случае тот участок где в пике он набирает максимальную скорость. Иначе эти 100 км\ч+ просто не выжимаются у любителя. Т.е. это какая-нибудь чёрная трасса с хорошим безопасным выкатом.
Касательно всего остального не спорю. И думаю далеко не последнюю роль играет качество GPS прибора. Плюс помнится там всё грустно с определением Z координаты, которая в случае спуска становится очень существенной.
В том и дело, что я видел на треках нереальные скорости и не на прямых.
А с высотой — да. В силу особенностей технологии точность ее определения сильно хуже точности определений координат. Тут спасает наличие барометрического альтиметра, но его нужно калибровать каждый раз перед использованием и он может вносить погрешность при резких изменениях давления (когда погода меняется резко и сильно).
Если не нужны абсолютные значения высоты, а просто оценка относительных разностей я обычно заменяю высоты, определенные прибором на высоты из SRTM таблиц (они доступны в сети) по координатам. Там тоже погрешность, но, по крайней мере если через час пришел на ту точку, где уже был, высота будет та же самая :-)
Ну или более сложные алгоритмы с усреднением высот в одинаковых точках, коррекция высоты прибора с привлечением высот из таблицы (с эвристикой какая из высот точнее) и т.п. Но тут опять математика, которая «не нужна» и без которой «можно замечательно обойтись потому что все уже до на придумано» :-)
А с высотой — да. В силу особенностей технологии точность ее определения сильно хуже точности определений координат. Тут спасает наличие барометрического альтиметра, но его нужно калибровать каждый раз перед использованием и он может вносить погрешность при резких изменениях давления (когда погода меняется резко и сильно).
Если не нужны абсолютные значения высоты, а просто оценка относительных разностей я обычно заменяю высоты, определенные прибором на высоты из SRTM таблиц (они доступны в сети) по координатам. Там тоже погрешность, но, по крайней мере если через час пришел на ту точку, где уже был, высота будет та же самая :-)
Ну или более сложные алгоритмы с усреднением высот в одинаковых точках, коррекция высоты прибора с привлечением высот из таблицы (с эвристикой какая из высот точнее) и т.п. Но тут опять математика, которая «не нужна» и без которой «можно замечательно обойтись потому что все уже до на придумано» :-)
Немного оффтоп — ездил на байке по гугл-картам (в ЮВА) так гугл понял что я был на байке а не на машине, теперь ясно как
чтоб тесты прошли :)
Хотел написать язвительный комментарий о том, что основная польза математики — это то, что она даёт возможность людям, которые её плохо знают, рассказывать людям, которые не знают её совсем, как было бы здорово, если бы все знали её хорошо.
Потом просмотрел список публикаций автора. Он неплохо знает математику. Тем не менее, статья совершенно дурацкая, и никак не доказывает то, что должна доказывать. Я считаю, что мне позволительна резкость, потому что в своё время сам писал точно такие же статьи и получал точно такую же реакцию. И, в общем-то, это справедливо.
Потом просмотрел список публикаций автора. Он неплохо знает математику. Тем не менее, статья совершенно дурацкая, и никак не доказывает то, что должна доказывать. Я считаю, что мне позволительна резкость, потому что в своё время сам писал точно такие же статьи и получал точно такую же реакцию. И, в общем-то, это справедливо.
Спасибо за оценку, хотя «неплохо» — это действительно мой предел, настоящие глубины, где обитают драконы (типа нулей дзета-функции), я честно пытался постичь, но не смог.
Дурацкая — возможно, но мне казалось, что я доказал (каламбур, однако) необходимость математики, я не верю в искренность тех 3 человек, что выбрали последний вариант опроса.
Дурацкая — возможно, но мне казалось, что я доказал (каламбур, однако) необходимость математики, я не верю в искренность тех 3 человек, что выбрали последний вариант опроса.
Ну, вам тут указали объективные недостатки статьи. Сумбурность изложения, искусственность задачи, сомнительность конечного результата. И самое (самое!) главное — вы в статье о пользе математики не осилили формулы в ТеХе запилить. Стыдно-с.
Необходимость математики лучше доказывать на реальных задачах из личной практики. С разбором как она решается (или скорее не решается) человеком не знающим математики и как она решается (успешно) человеком, способным применять математический аппарат на практике.
Ну, из статьи следует, что математика особо не нужна.
Задачка про коня задавалась на собеседовании в гугл и подробно рассматривается здесь и здесь ( кстати оцените, насколько яснее и проще объясняет этот экс-гуглер по сравнению со сбивчивым бормотанием из этой статьи).
В этих же статьях указывается, что линейное решение ( до которого вполне можно дойти «здравым смыслом») — это «Strong Hire» в гугл. Да, есть более оптимальное решение с трюком с матрицей, но практически очков оно вам не прибавит даже на собеседовании в гугл, не то что в реальной разработке.
Задачка про коня задавалась на собеседовании в гугл и подробно рассматривается здесь и здесь ( кстати оцените, насколько яснее и проще объясняет этот экс-гуглер по сравнению со сбивчивым бормотанием из этой статьи).
В этих же статьях указывается, что линейное решение ( до которого вполне можно дойти «здравым смыслом») — это «Strong Hire» в гугл. Да, есть более оптимальное решение с трюком с матрицей, но практически очков оно вам не прибавит даже на собеседовании в гугл, не то что в реальной разработке.
НЛО прилетело и опубликовало эту надпись здесь
Формулирую задачу — сколько различных номеров длиной К, заканчивающихся на заданной кнопке р, можно набрать на клавиатуре телефона (тастатуре), если мы должны перемещаться по кнопкам ходом шахматного коня.
Такая задача, возможно, вызовет интерес у любителей задачек изначально. Может быть она чуть-чуть заинтересует тех, кто любит шахматы или просто имеет иррациональную страсть к закономерностям на кнопочных телефонах.
Но сторонников «математика не нужна» она лишний раз убедит, что математики варятся в своих абстрактных задачах ради самих задач, в абсолютном отрыве от реальности. И что все эти вектора и матрицы нужны для обсчёта бесконечных ходов сферических коней по шахматным телефонам, а не для «настоящих» задач.
ИМХО чтобы человек заинтересовался математикой, нужно показать, как математика поможет решить лично его проблему. Например, для меня (учился в классе 7 в это время) это была проблема такого плана: как заставить в моём прототипе недоигры на VBA бегать объект по окружности. Тригонометрические функции тогда стали для меня «магией», которая позволила «открыть глаза» и отбросить стереотипы о «ненужных знаниях после арифметики». И чем дальше, тем больше задач, о которые я безуспешно бился лбом, внезапно оказывались решены в сильно более общем случае три века назад именно в математике.
Собственно, «отбитость» моей задачи беганья по кругу для других людей может быть такого же уровня, как и задача из поста. Чтобы привлечь человека математикой, нужно показать ему решение той задачи, которая интересует лично его.
Ирония ситуации заключается в том, что для качественного движения на экране по окружности (в любом смысле качественного — как быстрого, так и точного) вовсе не нужна тригонометрия, а нужен алгоритм Брезенхема, знание о котором не имеет к математике прямого отношения. Хотя сам Брезенхем явно в математике рубил.
Ну ок. Задача усложнилась и вместо окружности нужно нарисовать спираль. Сможете адаптировать алгоритм Брезенхема для этого?
А какие варианты? Не вижу другого способа качественно это сделать.
Я не понял ваш ответ. Вы утверждали, что тригонометрию знать не надо, а надо знать алгоритм Брезенхема. И мой вопрос — так вы сможете без знания тригонометрии модифицировать алгоритм Брезенхема на отрисовку спирали?
Конечно, смогу. Надо просто взвешивать ошибку по x и у. Всё в целых числах, причём тут тригонометрия? А для центра спирали, кстати, можно и готовые спрайты руками нарисовать, может получиться быстрее.
И тут ещё надо для начала разобраться, что имеется в виду под спиралью, потому что обычная математическая бесконечновитковая спираль не имеет практического применения.
Весь мой пойнт в том, что задача аккуратного попиксельного рисования кривой не имеет ничего общего с нахождением пикселей, ближайших к вещественным координатам точек уравнения подобной кривой. Этому просто учат программистов, как необходимому в работе факту, а чтобы прийти к этому из математических предпосылок, надо быть Брезенхемом.
И тут ещё надо для начала разобраться, что имеется в виду под спиралью, потому что обычная математическая бесконечновитковая спираль не имеет практического применения.
Весь мой пойнт в том, что задача аккуратного попиксельного рисования кривой не имеет ничего общего с нахождением пикселей, ближайших к вещественным координатам точек уравнения подобной кривой. Этому просто учат программистов, как необходимому в работе факту, а чтобы прийти к этому из математических предпосылок, надо быть Брезенхемом.
Конечно, смогуБыло бы интересно на конкретный код. Ведь я даже не уточнял, о какой именно спирали идёт речь — линейной, логарифмической или какой-то другой.
причём тут тригонометрия?Я так понимаю при том, что «движение по окружности» (о котором речь шла изначально) предполагает итеративное изменение угла вектора, от которого через синус и косинус считаются координаты точки на окружности. Зная это, получить (линейную) спираль элементарно:
x = a*cos(a)
y = a*sin(a)
А как без этой формулы вы будете отрисовывать спираль? Как сможете перейти к реккурентному виду, чтобы не вычислять синус и косинус на каждом шаге?
Вы знакомы с алгоритмом Брезенхема? Там нет никаких углов, синусов и косинусов. Там решается чисто логическая задача выбора на каждом шаге одного из 8 (а в действительности 3) соседних пикселей. Ни одного вещественного числа и функций над ними Брезенхем не использует. И его визуальный результат значительно отличается (в лучшую сторону) от округления уравнения окружности.
Никакой линейной или логарифмической спирали на экране компьютера нет и быть не может, в силу его конечности. Есть фигура, составленная из конечного числа квадратов, которая должна удовлетворять определённым условиям восприятия человеком.
С точки зрения чистого доказательства существования алгоритма, не использующего тригонометрию, вообще любой график на экране может быть задан простым перечислением пикселей (собственно, тоже реально используемый в компьютерной графике метод видеовставок). Но, конечно, можно это делать и поумнее. Например, как у Брезенхема.
Никакой линейной или логарифмической спирали на экране компьютера нет и быть не может, в силу его конечности. Есть фигура, составленная из конечного числа квадратов, которая должна удовлетворять определённым условиям восприятия человеком.
С точки зрения чистого доказательства существования алгоритма, не использующего тригонометрию, вообще любой график на экране может быть задан простым перечислением пикселей (собственно, тоже реально используемый в компьютерной графике метод видеовставок). Но, конечно, можно это делать и поумнее. Например, как у Брезенхема.
Вы знакомы с алгоритмом Брезенхема?Я знаком с алгоритмом Брезенхема и применял его на практике.
Никакой линейной или логарифмической спирали на экране компьютера нет и быть не может, в силу его конечности. Есть фигура, составленная из конечного числа квадратов, которая должна удовлетворять определённым условиям восприятия человеком.Ну если на то пошло, то не «квадратов», а «пикселей». И как удовлетворять эти условия, не зная исходной мат.модели, по-прежнему непонятно.
Вы алгоритмом Брезенхема можете нарисовать окружность. Но как сделать равномерное движение по окружности? Какой-то объект должен на экране крутиться. Нельзя просто на каждый тик переходить к следующему пикселю.
А если скорость движения нужна разная, типа индикатор загрузки крутится, то ускоряясь, то замедляясь?
Ну, будете в случае перехода к следующему пикселю по горизонтали и вертикали задерживаться на два тика, а по диагонали – на три. Делов-то. Это в том случае, если вообще на глаз можно различить такую неравномерность кругового движения, в чём я сомневаюсь.
А индикаторы загрузки вообще, к сожалению, принято рисовать, как курица лапой. Никто там не парится об угловой скорости, уж точно.
А индикаторы загрузки вообще, к сожалению, принято рисовать, как курица лапой. Никто там не парится об угловой скорости, уж точно.
Ну, будете в случае перехода к следующему пикселю по горизонтали и вертикали задерживаться на два тика, а по диагонали – на три.
А если пикселей в окружности 314, а полный оборот делается за 30 тиков? На какой пиксель прыгать каждый тик?
А индикаторы загрузки вообще, к сожалению, принято рисовать, как курица лапой. Никто там не парится об угловой скорости, уж точно.
Ну вот тут сделано прикольно — равноускоренное движение по кругу.
Ваши погрешности +- несколько пикселей и рывки движения будут заметны и заказчику не понравятся.
Не очень понимаю, как именно за 30 тиков мы сдвинемся ровно на 314 пикселей. Не делится.
Если у нас такая напряжёнка с тиками, что даже попиксельно отрисовать нет времени, то синусы и косинусы, вычисляющиеся вечность, нам точно не помогут.
Что касается заказчика (и любого другого человека), то зрение устроено так, что ему заметны не ± несколько пикселей, а, в первую очередь, неравномерная толщина линии.
Если у нас такая напряжёнка с тиками, что даже попиксельно отрисовать нет времени, то синусы и косинусы, вычисляющиеся вечность, нам точно не помогут.
Что касается заказчика (и любого другого человека), то зрение устроено так, что ему заметны не ± несколько пикселей, а, в первую очередь, неравномерная толщина линии.
Не делится.
Во-о-от. А косинусы/синусы тут как раз и помогут — сдвигаем угол на 12 градусов, получаем точное значение координат, округляем до ближайшего пикселя.
Если у нас такая напряжёнка с тиками
Стоп, при чем тут напряженка с тиками? Один тик — 16мс на 60 fps. Все хорошо. Попиксельно можно бы отрисовывать, просто вообще не понятно как это делать. Алгоритм Брезенхема не сделан для равномерного движения по окружности, он сделан чтобы пройтись по ближайшим к заданной кривой пикселям.
Вот только чтобы взвешивать ошибку, надо знать уравнение, а уравнение Архимедовой спирали — ρ = kφ, оно же x2 + y2 = k2 (arctan (y/x) ± π)2. Другие спирали тоже имеют тригонометрические функции в своих уравнениях.
И как же вы будете его без знания тригонометрии использовать?
Совершенно не нужно знать уравнение спирали в декартовых координатах, чтобы параметрически, по шагам, нарисовать спираль по пикселям. Чисто на сложениях (вычитаниях) можно построить алгоритм, на каждом шаге уменьшая длину прямого отрезка до поворота направо.
Ну-ну, попробуйте.
Вот, кстати, параметрический вариант уравнения:
x = k t cos t
y = k t sin t
А что пробовать-то? Очевидно же. Мы в 7 классе такие спирали черепашкой рисовали на Лого, без всяких синусов.
У вас параметрические уравнения от ненужного нам параметра φ. За счёт того, что вы от фонаря притянули угловую меру и решения в вещественных числах, у вас и лезет тригонометрия. А вы от N (номера шага) считайте, и чисто дискретно. Именно так построен алгоритм Брезенхема.
У вас параметрические уравнения от ненужного нам параметра φ. За счёт того, что вы от фонаря притянули угловую меру и решения в вещественных числах, у вас и лезет тригонометрия. А вы от N (номера шага) считайте, и чисто дискретно. Именно так построен алгоритм Брезенхема.
А от номера шага считать не получится, потому что длина шага-то не является константой!
Черепашка на Лого, поди, ходила не по Брезенхему, а как получится.
Так именно поэтому длину отрезка на каждом шаге нужно уменьшать, о чём я и написал выше.
Черепашка на Лого ходила отрезками прямых, для чего никакие синусы тоже не нужны. Когда отрезок прямой наклонён менее чем на 2 пикселя от горизонтали или вертикали, то он неотличим от любой другой кривой, соединяющей его концы.
Но по своей сути алгоритм Брезенхема – это и есть черепашка. Он был придуман именно для управления перьевым плоттером.
Черепашка на Лого ходила отрезками прямых, для чего никакие синусы тоже не нужны. Когда отрезок прямой наклонён менее чем на 2 пикселя от горизонтали или вертикали, то он неотличим от любой другой кривой, соединяющей его концы.
Но по своей сути алгоритм Брезенхема – это и есть черепашка. Он был придуман именно для управления перьевым плоттером.
Вы не можете уменьшать длину отрезка на каждом шаге, потому что это не будет алгоритмом Брезенхема.
Я отвечаю на следующий вопрос:
Сам алгоритм Брезенхема рисует окружность. Естественно, что алгоритм рисования окружности не рисует спираль.
И мой вопрос — так вы сможете без знания тригонометрии модифицировать алгоритм Брезенхема на отрисовку спирали
Сам алгоритм Брезенхема рисует окружность. Естественно, что алгоритм рисования окружности не рисует спираль.
Ну так вы же не алгоритм Брезенхема модифицировали, а предложили совершенно другой! Который к тому же, в зависимости от параметров, или работает слишком медленно — или рисует неправильно.
И, если на то пошло, то алгоритм Брезенхема рисует
прямую линию. А вот методом Брезенхема можно нарисовать любую непрерывную линию если известно её уравнение.
Тут для детей совсем по-простому написано, поэтому используется операция умножения. Но её можно тоже убрать.
Также, надеюсь, понятно, что отрезок прямой с заданным наклоном из заданной точки можно нарисовать, не считая тригонометрических функций (поскольку тангенс — это всего лишь отношение приращений координат, говоря простым языком).
У вас спираль получилась угловатая какая-то. Для правильной отрисовки надо брать начальный n=1, угол поворота тоже взять небольшой, ну и множитель взять ближе к 1. Вот тогда спираль получится плавная.
А теперь сравните время, которое придётся затратить на подобную отрисовку спирали, и время работы алгоритма по методу Брезенхема.
А ещё попытайтесь без математики нарисовать более плавную спираль так, чтобы она проходила через те же самые угловые точки, как и "угловатая" версия.
Это не у меня получилась, это первый попавшийся в интернете пример для детей. В ряде школ это была программа второго класса обучения. Маленькие дети уже прекрасно понимают, что для рисования спирали не нужна тригонометрия (они и слова такого не знают).
Так эта не та спираль. Вот та:
Ну вот, теперь уже и спираль не та. В вопросе не было ничего про «ту» или «не ту».
Принцип ясен, а как подкрутить длину отрезка и смещение – дело десятое.
Принцип ясен, а как подкрутить длину отрезка и смещение – дело десятое.
Ну вот, теперь уже и спираль не та. В вопросе не было ничего про «ту» или «не ту».Что значит «не было»? Я конкретную формулу приводил, которой эта спираль должна соответствовать.
подкрутить длину отрезка и смещение – дело десятое.Покажите, как. Методом проб и ошибок?
А подскажите, как вы получили уравнение?
Мы, вроде как, обсуждаем случай рисования изображения в игрушке. И тут никакой другой способ, кроме проб и ошибок по критерию красивого визуального восприятия, не просматривается.
Мы, вроде как, обсуждаем случай рисования изображения в игрушке. И тут никакой другой способ, кроме проб и ошибок по критерию красивого визуального восприятия, не просматривается.
Уравнение получилось изменением начальных условий, когда константный радиус окружности перестал быть константным, а стал линейно зависеть от времени.
У вас в каждом сообщении появляются новые дополнительные условия. Напомню, дело началось с того, что multiprogramm
написал, что тригонометрические функции – это магия, которая позволила ему нарисовать окружность. Я возразил, что для рисования окружности тригонометрия совсем не нужна, а есть Брезенхем. Тогда Вы написали буквально следующее:
Я в ответ написал про общий подход и даже, в конце концов, привёл конкретный пример с картинкой из детского программистского творчества.
Теперь пошли какие-то новые темы про линейную зависимость радиуса от времени, хотя какой в этом физический и практический смысл – уже совершенно непонятно. Если речь идёт о том, что для решения тригонометрического уравнения нужна тригонометрия, то это, вроде как, очевидно, но практического содержания в этом не больше, чем в обходе клавиатуры мобильного телефона ходом коня. Математическая задача ради самой математической задачи.
Хотя есть ведь в программировании и действительно математичные приложения, вроде криптографии. Просто примеры надо выбирать тщательнее.
написал, что тригонометрические функции – это магия, которая позволила ему нарисовать окружность. Я возразил, что для рисования окружности тригонометрия совсем не нужна, а есть Брезенхем. Тогда Вы написали буквально следующее:
Ну ок. Задача усложнилась и вместо окружности нужно нарисовать спираль. Сможете адаптировать алгоритм Брезенхема для этого?
Я в ответ написал про общий подход и даже, в конце концов, привёл конкретный пример с картинкой из детского программистского творчества.
Теперь пошли какие-то новые темы про линейную зависимость радиуса от времени, хотя какой в этом физический и практический смысл – уже совершенно непонятно. Если речь идёт о том, что для решения тригонометрического уравнения нужна тригонометрия, то это, вроде как, очевидно, но практического содержания в этом не больше, чем в обходе клавиатуры мобильного телефона ходом коня. Математическая задача ради самой математической задачи.
Хотя есть ведь в программировании и действительно математичные приложения, вроде криптографии. Просто примеры надо выбирать тщательнее.
Да, помню, как в универе забивал на электротехнику. И преподаватель ко мне относился соответственно.
Но однажды летом решил я сам спаять дисторшн для своей электрогитары. Интернета тогда не было, и искал я информацию в журналах и учебниках, а когда пришла осень, не пропускал ни одной лекции по электротехнике, а иногда и оставался после занятий с преподавателем, чисто спросить, как что работает. Это конечно для неё был шок, не узнавала былого раздолбая)))
P.S. Дисторш я в конце концов спаял, но спалил им усилитель((
Но однажды летом решил я сам спаять дисторшн для своей электрогитары. Интернета тогда не было, и искал я информацию в журналах и учебниках, а когда пришла осень, не пропускал ни одной лекции по электротехнике, а иногда и оставался после занятий с преподавателем, чисто спросить, как что работает. Это конечно для неё был шок, не узнавала былого раздолбая)))
P.S. Дисторш я в конце концов спаял, но спалил им усилитель((
Вы дядя Федор бутерброд неправильно едите. Вопрос изначально поставлен неверно.
Нужен ли олимпиадный склад ума (математика) чтобы быть хорошим высокооплачиваемым разработчиком? Ответ однозначно нет, тут вполне может работать другой набор скилов (к примеру глубокие знания в какой-нибудь доменной области).
Нужен ли олимпиадный склад ума чтобы стать гениальным программистом, как Дуров, Дин, Коэн, Торвальдс итд? Да обязателен.
Ну и собственно главный вопрос какую свою проблему вы решаете умея решать вот такие задачи?
Нужен ли олимпиадный склад ума (математика) чтобы быть хорошим высокооплачиваемым разработчиком? Ответ однозначно нет, тут вполне может работать другой набор скилов (к примеру глубокие знания в какой-нибудь доменной области).
Нужен ли олимпиадный склад ума чтобы стать гениальным программистом, как Дуров, Дин, Коэн, Торвальдс итд? Да обязателен.
Ну и собственно главный вопрос какую свою проблему вы решаете умея решать вот такие задачи?
Ответ дан в первой цитате КДПВ — именно для того, чтобы быстро и элегантно решать обычные проблемы в области программирования и нужен натренированный ум. Например, из недавнего, ускоренный алгоритм возведения в степень очень полезен при расшифровке с открытым ключом.
Хотя должен с грустью сообщить, что в последнее время интересных задач из реальной жизни не встречалось.
Но просто представьте себе на секунду объем информации, хранящейся в том же Google и скорость, с которой она должна обрабатываться — я не очень понимаю, как они этого достигли, наверняка не без каких-то алгоритмических и (или) программистских трюков.
Хотя должен с грустью сообщить, что в последнее время интересных задач из реальной жизни не встречалось.
Но просто представьте себе на секунду объем информации, хранящейся в том же Google и скорость, с которой она должна обрабатываться — я не очень понимаю, как они этого достигли, наверняка не без каких-то алгоритмических и (или) программистских трюков.
Хотя должен с грустью сообщить, что в последнее время интересных задач из реальной жизни не встречалось.Странно, а у меня куча задач, для которых гугл не находит готового решения. Например (не смог решить, знаний не хватает) найти аналитическое преобразование Фурье от функции erfc(log(x2n)). Или (смог решить) вывести формулу в полярных координатах для плавной трансформации окружности в прямоугольник (с острыми углами!):
И это задачи сугубо практические, не олимпиадные.
Я в институте на практике плавно трансформировал произвольные фигуры (точнее, там были каркасные 3d объекты) друг в друга, и могу точно сказать, что для этого ничего аналитически выводить мне не потребовалось. Просто задаём соответствие между каждой точкой исходной фигуры и каждой точкой конечной, и ведём промежуточные точки по отрезку, концы которого соответствуют исходной и конечной точке. Это красиво работает даже для топологически неэквивалентных преобразований.
в институтеЭто не аргумент. Вот если бы вы так проектировали крыло конкретного самолёта, и он «ничего, летает» — вот тогда бы да.
Крыло самолёта не надо аналитически трансформировать между окружностью и прямоугольником. Его форма определяется численными методами и натурными экспериментами.
Причём отмечу, что люди, проектирующие крыло самолёта, даже об этих численных методах имеют весьма приблизительное представление, так как пользуются готовыми пакетами прикладных программ.
Причём отмечу, что люди, проектирующие крыло самолёта, даже об этих численных методах имеют весьма приблизительное представление, так как пользуются готовыми пакетами прикладных программ.
Ну хорошо. Не самолёт, ядерная бомба или космический корабль. Как много натурных экспериментов вы можете позволить, чтобы выявить оптимальную форму ядерной бомбы и её составляющих? Как проектировали технику до того, как появились прикладные программы?
Я же не отрицаю математику ни вообще, ни в жизни программиста. Я говорю о том, что конкретные примеры неудачны. А изучаемые в школе разделы математики вообще очень мало непосредственно востребованы в программировании, хотя в отношении порядка в уме Ломоносов и Суворов, безусловно, правы.
Что же такого неиспользуемого в школе изучается? Арифметика, комплексные числа, производные, интегралы, элементарные функции, базовые алгебра логики, комбинаторика — наоборот широко нужны в куче мест. Что-то важное забыл?
Из перечисленного Вами половина даже не в любой спецшколе изучается.
Из курса общеобразовательной школы для программиста полезны: целочисленная арифметика, общее понятие о переменных и исчислении, о математическом доказательстве. Бесполезны: арифметика и алгебра вещественных чисел (в математическом смысле вещественных), геометрия, символьное взятие производной и первообразной. Вроде, больше ничего в средней школе и нет.
Из высшей математики (или, скажем более аккуратно, вузовских математических дисциплин) полезны для программиста: булева алгебра, теория алгоритмов, теория множеств, комбинаторика, теория графов, исчисление предикатов, теория вычислительных процессов, математическая статистика, анализ (включая формальное понятие о бесконечно малых, пределах, интегрировании и дифференцировании). Может, ещё пару разделов забыл. Я бы ещё назвал матлогику, но от неё при глубоком погружении скорее можно сойти с ума, чем научиться программированию.
Я здесь пишу именно о профессии программиста, а не прикладного математика.
Из курса общеобразовательной школы для программиста полезны: целочисленная арифметика, общее понятие о переменных и исчислении, о математическом доказательстве. Бесполезны: арифметика и алгебра вещественных чисел (в математическом смысле вещественных), геометрия, символьное взятие производной и первообразной. Вроде, больше ничего в средней школе и нет.
Из высшей математики (или, скажем более аккуратно, вузовских математических дисциплин) полезны для программиста: булева алгебра, теория алгоритмов, теория множеств, комбинаторика, теория графов, исчисление предикатов, теория вычислительных процессов, математическая статистика, анализ (включая формальное понятие о бесконечно малых, пределах, интегрировании и дифференцировании). Может, ещё пару разделов забыл. Я бы ещё назвал матлогику, но от неё при глубоком погружении скорее можно сойти с ума, чем научиться программированию.
Я здесь пишу именно о профессии программиста, а не прикладного математика.
геометрия
Я бы сказал, что из школьного курса как раз таки с прикладной геометрией у программиста шанс встретиться — достаточно большой (там с какого края не возьмись за графику, например — оно вылезет).
То есть, то, что вы написали в список «полезное» — оно конечно важнее, потому что задействовано практически всегда в программировании. Но с геометрией тоже можно встретиться очень легко.
НЛО прилетело и опубликовало эту надпись здесь
вывести формулу в полярных координатах для плавной трансформации окружности в прямоугольникКакая практическая польза от этой формулы?
Я не ерничаю, правда интересно, где можно применить.
Про гениальных программистов-олимпиадников как раз недавно писали.
Я вобщем-то был лучшего мнения о телеграмистах, но подозревал, что олимпиадные задачи в духе «решить по быстрому и чтобы работало быстро» хитрую задачу приводят к говнокоду и стремлению решать обычные задачи излишне сложными способами, в том числе к NIH-синдрому.
Я вобщем-то был лучшего мнения о телеграмистах, но подозревал, что олимпиадные задачи в духе «решить по быстрому и чтобы работало быстро» хитрую задачу приводят к говнокоду и стремлению решать обычные задачи излишне сложными способами, в том числе к NIH-синдрому.
Когда-то наткнулся на высказывание: «Математика дает самое непосредственное понимание истинности, в этом заключается ее непреходящее значение для образования.». Увы, не помню чье высказывание…
Формулирую задачу — сколько различных номеров длиной К, заканчивающихся на заданной кнопке р, можно набрать на клавиатуре телефона (тастатуре), если мы должны перемещаться по кнопкам ходом шахматного коня.Чтобы увеличить количество боли, нужно добавить что решение должно работать в internet explorer 6.
Посыл правильный, но блин… Задача на динамику через матрицы не самый лучший пример. Можно было бы просто взять область геймдева, где какие-то математические вычисления на каждом углу — там тоже будет векторная алгебра, матрицы. Да собственно вся компьютерная графика на математике построена.
Если искать что-то потяжелее, то взять можно физические симуляции. Вот там начинается жуть в виде решения диффуров и ангема, и вряд ли со школьными знаниями получится такое вывезти
Убедился, что математика нужна, когда крутил сферу из точек на мониторе: на хорошем, в те времена, pentium-3 800, сфера гладко крутилась только математикой внутри процессора, а на более слабых pentium 2 — уже тормозила. Пришлось включать мозг и не считать все точки в лоб.
Привет, математика и оптимизация!
PS сейчас максимум тру математики в шейдерах, ray trace, обсчёте пробивов брони в играх и всём остальном, зачем же нужны кони клавиатурные?
Привет, математика и оптимизация!
PS сейчас максимум тру математики в шейдерах, ray trace, обсчёте пробивов брони в играх и всём остальном, зачем же нужны кони клавиатурные?
Приведу свои примеры того, как пригодилась математика. Мне кажется, эти примеры… Более о практике =)
В 10м классе я делал шутер. И был там противник с двумя пушками, расположенными достаточно далеко он его центра. Нужно было сделать, чтобы снаряды появлялись конкретно у стволов пушек и летели туда, где противник. Так мне впервые понадобилась школьная геометрия.
Затем я посмотрел Терминатора 4-го и мне понравилось, как роботы-мотоциклы уклонялись от столкновений. Я решил сделать ботов для игры, которые бы уклонялись от снарядов (и чтобы от них уклониться было нельзя). Изучил такую вещь, как приближённое решение разностных уравнений.
Потом я делал 3Д движок для авиасимулятора. Оказалось, что через крен-тангаж-рысканье можно задать ориентацию самолёта, но ориентацию видеокамеры — нет. Стал изучать матрицу направляющих косинусов (это уже в вузе).
В 10м классе я делал шутер. И был там противник с двумя пушками, расположенными достаточно далеко он его центра. Нужно было сделать, чтобы снаряды появлялись конкретно у стволов пушек и летели туда, где противник. Так мне впервые понадобилась школьная геометрия.
Затем я посмотрел Терминатора 4-го и мне понравилось, как роботы-мотоциклы уклонялись от столкновений. Я решил сделать ботов для игры, которые бы уклонялись от снарядов (и чтобы от них уклониться было нельзя). Изучил такую вещь, как приближённое решение разностных уравнений.
Потом я делал 3Д движок для авиасимулятора. Оказалось, что через крен-тангаж-рысканье можно задать ориентацию самолёта, но ориентацию видеокамеры — нет. Стал изучать матрицу направляющих косинусов (это уже в вузе).
Математика учит «правильно по-программистски» думать. «Правильно по-программистски» — это оценочное суждение. Ему не место в математике. Тогда дадим определение что такое «Правильно по-программистски» — это значит что решение близко к оптимальному в указанные сроки, указанных технологиях, окружении и будущем развитии.
«Близко», «оптимальному» — это тоже оценочное суждение (и ему не место в математике) так что нам нужно вводить какие-то метрики — бенчмарки, пользовательские оценки, человеко-часы и т.д.
Думаю, что основная мысль понятна.
«Близко», «оптимальному» — это тоже оценочное суждение (и ему не место в математике) так что нам нужно вводить какие-то метрики — бенчмарки, пользовательские оценки, человеко-часы и т.д.
Думаю, что основная мысль понятна.
Вопрос из серии «Нужно ли программисту знать бухучет». Правильный ответ: «некоторым нужно».
Такой же точно ответ и про математику.
Такой же точно ответ и про математику.
Мне кажется, всё просто. Да, высшая математика программисту нужна, но… без фанатизма. Достаточно просто быть, как говорится, «в теме». Т. е. хорошо бы конечно знать язык высшей математики, общепринятые математические обозначения, чтобы можно было хотя бы поверхностно врубиться в принципы работы тех или иных алгоритмов и/или математических библиотек, почитать научные статьи, на которых основаны алгоритмы. Этого достаточно для практического использования, глубоко вникать и разбираться обычно нет необходимости. В принципе сейчас по шаблонам, с использованием готовых библиотек, можно и без знания высшей математики многие сложные вещи программировать, однако если что-то пойдет не так, выйдет за рамки шаблонов… возникнут сложности.
В школе вафлил математику, теперь хочу наверстать упущенное, подскажите пожалуйста, по какому материалу это лучше делать? Спасибо
НЛО прилетело и опубликовало эту надпись здесь
Тут посмотрите.
То что математика важна и нужна, полностью поддерживаю (Салимжанов рулит!).
Но вот способ доказательства у ТС явно притянут за уши. Согласного и убеждать не надо, а несогласный с тезисом глядя на обоснование только укрепится в своем заблуждении.
Хочется чего-то такого. Был у нас тестер и была у него задача перебрать всевозможные комбинации из 16 бинарных значений (это элементы интерфейса). Он сделал 16 вложенных циклов.
Мы на пару с другим погромистом так и не смогли его убедить в том, что бинарное представление uint16_е гарантированно пробежит по всевозможным комбинациям.
Но вот способ доказательства у ТС явно притянут за уши. Согласного и убеждать не надо, а несогласный с тезисом глядя на обоснование только укрепится в своем заблуждении.
Хочется чего-то такого. Был у нас тестер и была у него задача перебрать всевозможные комбинации из 16 бинарных значений (это элементы интерфейса). Он сделал 16 вложенных циклов.
Мы на пару с другим погромистом так и не смогли его убедить в том, что бинарное представление uint16_е гарантированно пробежит по всевозможным комбинациям.
Самое замечательное тут то, что по вычислительной сложности эти оба способа эквиваленты. То есть ни ваше, ни его решение нельзя считать формально лучше или хуже.
Есть ещё один эквивалентный способ, вообще без циклов, на одних ветвлениях. Всего-то 65535 ифов. И самое замечательное, что по вашей логике его тоже нельзя считать формально лучше или хуже.
Эквивалентны с точностью до константы (оверхеда на организацию 15 циклов), которая в данном случае будет играть значительную роль.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
При всем уважении, сэр, современной математика стала после упомянутых персонажей, но даже и сейчас математика того времени не исчезла.
Если уж помянули Ломоносова, не могу не встрять. Как то интереса ради решил почитать его учёные сочинения. Всё-таки матёрый человечище, настоящий полимат, первый русский учёный. Конечно, язык того времени просто ужасен для современного человека. Но это было ожидаемо. Ещё ранее я читал неадаптированного Радищева с его кошмарным слогом, после чего меня сложно было удивить русским языком XVIII века. Меня больше всего поразило, что научные статьи по физике и химии были написанны без единой математической формулы и практически без расчётов. Чисто описательные, что то вроде налили то, добавили это, получилась такая та штука. Тем более никакой сложной математики Ломоносов в своих работах не использовал. При том, что он был знаком с сочинениями Ньютона и Эйлера, а с последним даже переписывался. То есть, сам Ломоносов математику современного ему уровня не знал, точнее не далее базовых понятий типа арифметики. В одном письме даже промелькнуло, что и геометрию он тоже не знал, даже евклидову, так как находил объём конуса не по известной формуле, а каким то своим эмпирическим методом.
Меня больше всего поразило, что научные статьи по физике и химии были написаны без единой математической формулы и практически без расчётов
Это как раз не удивительно. Физика суть наука описательная. И в ней главное понимать как оно все между собой взаимодействует на некотором интуитивном уровне, чем уметь на каждый случай написать формулу для получения нужного ответа.
Есть у меня знакомый, занимается репетиторством по физике. Так вот у него методика сторится на том, что сналала все описывается «на пальцах», без формул. Затем вводятся понятия «базовых величин» (расстояние, время, температура, масса...) Затем переход от базовых к величинам производным (как из рассотяния и времени получить скорость и т.п.). А затем уже то, что описано на пальцах описывается формулами.
Когда он эту методику начал применять на практике, то был сам поражен насколько быстро те, кому физика в школе ну совсем никак не лезет в голову, начинали понимать ее суть и прогрессировать.
НЛО прилетело и опубликовало эту надпись здесь
А вот и не угадали, в прошлом году сменил свой чудесный Flatron 700Р на панель (ну просто сломался последний из 3х в свое время закупленных 700). Ну а по поводу мобильника — я могу его удержать в ладони возле уха, заряжаю раз в неделю и прохожу металодетектор (не всегда). Кто из владельцев смартфонов скажет то же самое?
А для того, чтобы в дороге читать книги и писать посты, у меня есть планшет с экраном 9.7" и разрешением 2048x1536.
А для того, чтобы в дороге читать книги и писать посты, у меня есть планшет с экраном 9.7" и разрешением 2048x1536.
Сам до недавнего времени пользовался связкой планшет — кнопочная звонилка. Сейчас, увы, опопсился и перешел на смартфон (ну, правда, тут тоже не без «нестандартности» :-)
Так что более чем понимаю такое решение :-)
Правда, я равнодушен к визуальным финтифлюшкам, не люблю писать интерфейсы, люблю глубокий backend и получаю удовольствие от отладки системным отладчиком в зеленом экране (эмулятор терминала IBM5250)
Так что более чем понимаю такое решение :-)
Правда, я равнодушен к визуальным финтифлюшкам, не люблю писать интерфейсы, люблю глубокий backend и получаю удовольствие от отладки системным отладчиком в зеленом экране (эмулятор терминала IBM5250)
Автор мало того что нудный и душный, так ещё и воинствующий ретард.
На всякий случай уточню, вы не перепутали «ретард» и «ретроград»? Просто единсвенное, что приходит на ум при слове «ретард» — английское retard, а на него автор явно не тянет.
Решаем задачу с противоположного конца, пусть K=1. Тогда для каждой кнопки мы можем посчитать и запомнить число комбинаций вручную. Пусть K=2, тогда для заданной кнопки просто складываем количество комбинаций K=1 всех кнопок, доступных одним ходом шахматного коня, которые мы посчитали на прошлом ходе. Пусть K=3, тогда складываем количество комбинаций K=2, доступных одним ходом коня. И так далее. Алгоритм линейно зависит от К.
Здесь используется операция сложения и здравый смысл. Да, операцию сложения программисту безусловно стоит знать, в этом автор прав. Что касается более сложной математики — пока не увидел аргументов, хотя согласен с вышеприведённым высказыванием Ломоносова.
Здесь используется операция сложения и здравый смысл. Да, операцию сложения программисту безусловно стоит знать, в этом автор прав. Что касается более сложной математики — пока не увидел аргументов, хотя согласен с вышеприведённым высказыванием Ломоносова.
А Вы до конца прочитали? То есть трюк с векторной алгеброй Вам подскажет здравый смысл — сомневаюсь.
Если я правильно понял исходную задачу, то использование матриц в данной задаче не требуется, это искусственное усложнение. Прочитайте моё решение и скажите, ошибся ли я в чём-то? Кажется, что тут достаточно обычной индукции, которая хоть и изучается в рамках олимпиадной математики, однако вполне интуитивна и часто используется даже не изучавшими её.
Дело не в том, что Вы ошиблись, а в том, что время вычисления по вашему методу на многие порядки больше, чем в трюке в матрицами при больших К.
Если Вы попробуете решать задачки на многих сайтах, то увидите, что совершенно правильные решения, проходящие по первым 3-5 тестам, проваливаются на тестах с 10го с сообщенем о превышении времени, но это не значит, что решение не верное, просто надо искать более быстрое.
Если Вы попробуете решать задачки на многих сайтах, то увидите, что совершенно правильные решения, проходящие по первым 3-5 тестам, проваливаются на тестах с 10го с сообщенем о превышении времени, но это не значит, что решение не верное, просто надо искать более быстрое.
То есть по содержанию вопросов нет, оно правильное, вопросы только по времени? Это радует.
По поводу времени, оно будет линейно, и сейчас я это докажу. Первый шаг вычисляется тривиально и мы запоминаем его результат. Таким образом у нас есть результаты для всех цифр для L=1. Сложность этой операции — константа. Далее вычисляем для L=2 и так же запоминаем результат. Сложность этого шага — так же константа, так как у нас есть вычисления первого шага. Далее повторяем эту операцию нужное число раз до требуемого L. Не сложно увидеть, что для произвольного шага вычислений L=N сложность так же будет константой, так как мы имеем вычисления шага N-1, вся работа, которую нужно сделать, это рассчитать количество комбинаций для 10 цифр, просто просуммировав значения для L=N-1. Так как мы имеем N шагов со сложностью O(1), то итоговая сложность алгоритма будет O(N). Более того, этот алгоритм имеет константное потребление памяти, так как для вычисления шага N нужно хранить результаты только шага N-1, более ранние шаги уже не нужны.
По поводу времени, оно будет линейно, и сейчас я это докажу. Первый шаг вычисляется тривиально и мы запоминаем его результат. Таким образом у нас есть результаты для всех цифр для L=1. Сложность этой операции — константа. Далее вычисляем для L=2 и так же запоминаем результат. Сложность этого шага — так же константа, так как у нас есть вычисления первого шага. Далее повторяем эту операцию нужное число раз до требуемого L. Не сложно увидеть, что для произвольного шага вычислений L=N сложность так же будет константой, так как мы имеем вычисления шага N-1, вся работа, которую нужно сделать, это рассчитать количество комбинаций для 10 цифр, просто просуммировав значения для L=N-1. Так как мы имеем N шагов со сложностью O(1), то итоговая сложность алгоритма будет O(N). Более того, этот алгоритм имеет константное потребление памяти, так как для вычисления шага N нужно хранить результаты только шага N-1, более ранние шаги уже не нужны.
Но последнее решение, приведенное в статье работает не за O(n) а за O(log n). Значительно быстрее для сколько-нибудь больших n. И тоже константное потребление памяти. Константа-множитель у него, правда, похуже. Так что для совсем мелких значений n этот логарифм может быть даже медленнее линейного решения.
Спасибо, что подтвердили мою фразу, что н**2*К линейно по К, хотя я и не сомневался. Ну а дальше Вам уже ответили.
Смешнее вопроса «Зачем нужна математика?» бывают только ответы на него. Выглядит это примерно так: человек ходит в спортзал и жмёт штангу, а его спрашивают: «В какой ситуации в жизни тебе понадобится поднимать штангу, если ты не профессиональный тяжелоатлет?» И тот начинает сочинять истории, где ему понадобиться таскать штангу. Вроде-ж очевидно, что штангу тягают для того чтобы быть сильным, иметь крепкое здоровье, красивое тело… Т.е. для того чтобы расширить свои возможности.
Сломал глаза без LaTeX'а. =(
Критерий применимости на практике в случае с математикой, как мне кажется, не должен быть определяющим. Как и в случае с физикой. Как и в случае с анатомией. Эти знания могут пригодиться в определённых ситуациях, но по большей части они ценны сами по себе, потому что устраняют белые пятна в модели устройства мира индивидуума. Математику (физику, биологию, etc.) изучать просто интересно, потому что изучение удовлетворяет здоровую человеческую любознательность.
С посылом автора согласен, но статья вышла так себе.
Эта задача уже разбиралась, по-моему даже на хабре, но я не могу найти. Оригинальная статья на английском от автора задачи — тут.
Эта же статья читается очень плохо. А главное, в качестве аргумента приводится вполне себе олимпиадная задачка с интервью, которая в проде нигде никогда почти 100% не встречается.
Да, задача красивая и показывает насколько применение правильных знаний может ускорить решение.
Но гораздо лучше было бы, если бы автор привел пример реальной задачи, которая требует математики.
Такие примеры могу привести я. Кроме очевидного геймдева, где сложные структуры данных и математика встречаются постоянно, вот 2 примера из моей практики:
1) Пример из личной практики. Давным давно, когда интернет был медленный, а hdd маленькими, было популярно записывать сериалы на двд. Но тут встает весьма нетривиальная задача компоновки дисков. Есть куча сериалов состоящих из кучи серий и все они разного размера. С одной стороны, хочется не оставлять много свободного места на болванках. С другой стороны, очень не хочется размазывать сериал по 10 разным болванкам.
Отсюда получаются такие требования: Каждый сериал пишется последовательно на одну болванку, если что-то не помещается, то конец пишется на вторую болванку и так далее. Если на текущей болванке еще есть много места, то надо начинать писать на нее какой-то другой сериал. Надо как можно меньше свободного места оставить на болванках. Полный перебор работает слишком долго, но немного эвристики и динамического программирования позволили весьма эффективно компоновать диски.
2) Пример из профессиональной деятельности. Есть некая система и она генерирует некоторую статистику с определенной периодичностью. Пользователь может в любой момент дернуть API метод, который выдает максимальное значение статистики за некоторое фиксированное временное окно. Т.е. задача — реализовать скользящий максимум. Тупое решение в лоб слишком медленное. Чисел может быть весьма много в окне и пользователь может теребить метод сотни раз в секунду. Применив немного структур данных, можно хранить все элементы в окне в heap и держать дополнительный список всех элементов, чтобы удалять их из heap при выходе из окна. Уже работает быстро, но требует довольно много памяти. Но если подумать и применить еще немного этих страшных алгоритмов с математикой, то оказывается, достаточно только одного deque.
Помимо примеров могу привести еще один аргумент в защиту тезиса, что математика нужна гораздо более широкому кругу программистов, чем принято считать.
Если вы делаете хоть что-то сложнее рисования формочек и вывода текста в системные контроллы, то рано или поздно у вас может вылезти задача к которой можно применить алгоритмы и получить не только более эффективное решение, но и в 10 раз более простой код. И вы даже не будете об этом подозревать. Поэтому, даже если у вас в команде есть выделенный гуру-математик, если только он не ревьюит абсолютно весь код, никто даже не догадается спросить его помочь.
Да, это далеко не каждый день происходит, но, по-крайней мере, на моей практике, несколько раз в год я мог бы написать совершенно не нужный медленный говнокод и даже не подозревать об этом.
Вот ещё одна задача из реальности, более близкая к этой теме.
Нужно составить таблицу из бит-реверсированных чисел заданной разрядности, исключив палиндромы.
000 → 000
001 → 100
010 → 010
011 → 110
…
Само реверсирование очевидно, менее очевидно — узнать заранее, сколько элементов в таблице понадобится, чтобы выделить под это дело память.
Нужно составить таблицу из бит-реверсированных чисел заданной разрядности, исключив палиндромы.
001 → 100
011 → 110
…
Само реверсирование очевидно, менее очевидно — узнать заранее, сколько элементов в таблице понадобится, чтобы выделить под это дело память.
А можно поинтересоваться, как такая задача возникла в реальности?
Для оптимизации Bit-reversal permutation, которая возникает в результате быстрого алгоритма для дискретного преобразования Фурье или Хартли.
Присоединяюсь к вопрошающим: дико интересно, откуда такая задача вылезла.
НЛО прилетело и опубликовало эту надпись здесь
Значит просто не попадалось еще соответствующих задач… Вот поставят задачу написания какой-нибудь навигационной системы — придется и с проекциями разбираться и с системами координат и с переводом из одной проекции в одной системе координат в другую в другой системе координат (скажем, от меркатора в WGS84 к Гаусс-Крюгеру в Пулково-1942). Тут придется немножко математику вспомнить. А если потребуется еще сохранять треки, то потребуется фильтрация — фильтр Калмана хотя бы понять как работает и как им пользоваться. Или обосновать что более простые аналоги типа двойного экспоненциального сглаживания в некоторых ситуациях работают не хуже. Как можно использовать сплайн-сглаживание или прикрутить фильтр Ходрика-Прескота (который придумывался совсем не для того). Ну про прореживание фильтром Дугласа-Пеккера как-бы и неудобно говорить — это азы.
А если потребуется еще и маршруты строить, то тут теория графов в полный рост…
Так что или не зарекаться что никогда не понадобиться, или заранее исключить для себя определенные области разработки.
А если потребуется еще и маршруты строить, то тут теория графов в полный рост…
Так что или не зарекаться что никогда не понадобиться, или заранее исключить для себя определенные области разработки.
Вот поставят задачу написания какой-нибудь навигационной системы — придется и с проекциями разбираться и с системами координат и с переводом из одной проекции в одной системе координат в другую в другой системе координат (скажем, от меркатора в WGS84 к Гаусс-Крюгеру в Пулково-1942).
Я в свое время решал эту задачу, не прибегая и к миллиграммам математики.
Вы крайне плохо читаете то, что комментируете. Для использования уже придуманных алгоритмов и инструментов — не требуется разбираться в предмете настолько, чтоб выводить эти алгоритмы и инструменты самому. То же касается треков, маршрутов, и всего прочего.
Более того, мои личные ~18 лет программистского опыта «по делу» говорят о том, что способность программиста к поиску и поверхностному анализу информации во многие разы важнее его знаний в абсолютно любой предметной области (исключая собственно программирование). Хотя личный опыт ни на какую полноту охвата конечно же не претендует.
ЗЫ: И нет, я ни в коем случае не пропагандирую невежество. Знать и шарить — при прочих равных всегда лучше, чем не знать и не шарить. Но ваша жизнь не бесконечна, и знать всего вы не будете никогда (да даже если б бесконечна была — не помогло бы). И поэтому очень важно из всех областей знания выбирать самое важное для вас.
Более того, мои личные ~18 лет программистского опыта «по делу» говорят о том, что способность программиста к поиску и поверхностному анализу информации во многие разы важнее его знаний в абсолютно любой предметной области (исключая собственно программирование)
В рамочку и на стену
Для решения конкретно вашей задачи давно уже существует proj_lib Но беда в том, что не существует ни одной 100% адекватной проекции. Да и системами координат и геоидами не все так просто. А для выбора правильной проекции под задачу иногда бывает важно понимать какая из существующих будет лучше.
Ну и еще один аспект. Бывает что программист работает по ТЗ. Где написано «возьми то и положи туда». Это работа не разработчика а кодировщика. Тут действительно ничего особо знать не нужно кроме как нарисовать семь красных линий одной строкой кода.
А бывает что разработчику дается полноценное FSD — «на входе имеем то, на выходе нужно получить это». А выбор алгоритма и его реализации уже полностью на совести разработчика. И очень часто необходимость разработки нового возникает потому что ни один из 100500 существующих продуктов не устраивает по каким-то критериям. А это значит, что нужно придумывать что-то новое, а не то что выдается гуглем в первых пяти строках поиска.
Впрочем, это отдельная тема про различия разработчика и кодировщика.
Ну и еще один аспект. Бывает что программист работает по ТЗ. Где написано «возьми то и положи туда». Это работа не разработчика а кодировщика. Тут действительно ничего особо знать не нужно кроме как нарисовать семь красных линий одной строкой кода.
А бывает что разработчику дается полноценное FSD — «на входе имеем то, на выходе нужно получить это». А выбор алгоритма и его реализации уже полностью на совести разработчика. И очень часто необходимость разработки нового возникает потому что ни один из 100500 существующих продуктов не устраивает по каким-то критериям. А это значит, что нужно придумывать что-то новое, а не то что выдается гуглем в первых пяти строках поиска.
Впрочем, это отдельная тема про различия разработчика и кодировщика.
А для выбора правильной проекции под задачу иногда бывает важно понимать какая из существующих будет лучше.
… что тоже не требует существенного знания математики, а требует как раз адекватных навыков гугления и понимания найденного.
Бывает что программист работает по ТЗ. Где написано «возьми то и положи туда». Это работа не разработчика а кодировщика.
В любом ТЗ написано «возьми то и положи туда» (да и задачи в вольной постановке тоже формулируются именно таким образом). Разница только лишь в объеме пропущенных шагов.
И очень часто необходимость разработки нового возникает потому что ни один из 100500 существующих продуктов не устраивает по каким-то критериям. А это значит, что нужно придумывать что-то новое, а не то что выдается гуглем в первых пяти строках поиска.
Если бы всё решалось гуглем — вы бы уже не работали, а за вас бы работала нейросетка. «Что-то новое» нужно придумывать примерно всегда, разница, опять же, только в объеме и сложности этого нового.
Впрочем, это отдельная тема про различия разработчика и кодировщика.
Сколько раз не встречал адептов этой «отдельной темы» — так и не услышал от них ничего более интересного, чем попытки деления по некой отфонарной градации сложности решаемых задач. Особенно любопытно было один раз (в жизни) наблюдать, когда встретились двое таких, сначала один много рассуждал о тупых кодерах, потом о своих крутых задачах, которые он порешал, и об очень-очень крутых задачах, которые еще пока не совсем порешал. А потом заговорил второй, работающий в той же области, и смешал первого с известной субстанцией, потому что у второго способностей больше, и крутые задачи первого он посчитал работой для кодера ^_^
В любом ТЗ написано «возьми то и положи туда» (да и задачи в вольной постановке тоже формулируются именно таким образом). Разница только лишь в объеме пропущенных шагов.
Хорошо когда так. А когда «ТЗ» формулируется в виде «нам нужно разработать систему, которая позволит управляющей компании, обслуживающей объекты по всему городу и в города-спутниках, держать всего одну диспетчерскую куда сходятся все сигналы со всех объектов, представляются в наглядном виде, логируются и т.д. и т.п.». В команде есть координатор, есть схемотехник, есть разрабочик под микроконтроллеры и два разработчика на верхний уровень.
Да, тут нет математики. Это просто пример из реальной практики когда ТЗ как такового нет. Есть бизнес-задача которую надо решить. Дальше строится архитектурное решение, разрабатываются протоколы обмена данными, выделяются логические блоки и дальше каждый уже в рамках своего блока ищет наиболее оптимальное решение.
И любая задача решается именно так. просто где-то есть аналитик, которрый решает вопросы с бизнесом и превращает их хотелки в FSD той или иной степени подробности для разработчика.
А где-то аналитика нет и разработчику приходится начинать разработку с чистого листа — выбора архитектуры построения системы. И далее по списку.
Вторая задача из личной практики. Нужно отфильтровать «дрифты» в GPS треках с минимальной потерей данных. Дрифт — это ситуация когда прибор неподвижен, а координаты точки «гуляют» в результате чего трек выглядит как будто прибор хаотично перемещали туда-сюда во все стороны с амплитудой, доходящей до нескольких десятков метров. Дополнительное условие — нужно максимально точно отслеживать момент как остановки, так и начала целенаправленного движения.
Никаких указаний как это можно сделать от заказчика, естественно, не поступило. Просто хотелка — удалить.
Гугль выдает обескураживающие результаты — более-менее надежного алгоритма нет. Нужно изобретать самому. Тут уже без математики туго.
Я не делю задачи по сложности. Я делю их по степени подготовки для кодирования (которое является конечным этапом любой разработки). И на практике приходилось сталкиваться с очень широким спектром от ТЗ в стиле «сделайте мне красиво» до полностью прописанного алгоритма, который остается только выразить в виде собирающегося кода.
А когда «ТЗ» формулируется в виде «нам нужно разработать систему, которая позволит управляющей компании, обслуживающей объекты по всему городу и в города-спутниках, держать всего одну диспетчерскую куда сходятся все сигналы со всех объектов, представляются в наглядном виде, логируются и т.д. и т.п.».
Если вы не понимаете, что бизнес-задача, описанная обычным языком — это тоже вполне себе ТЗ — то ой.
Гугль выдает обескураживающие результаты — более-менее надежного алгоритма нет. Нужно изобретать самому. Тут уже без математики туго.
Не вижу тут особой математики, равно как и «обескураживающих результатов». Естественно хорошего алгоритма нет — откуда ему взяться, когда у вас даже надёжной формализации «целенаправленного движения» нет? Попытки нагуглить что-то к задаче прямо в такой постановке — это классическое garbage in, garbage out. Чё-то хотим, чё-то сделаем, чё-то получим.
Я делю их по степени подготовки для кодирования (которое является конечным этапом любой разработки).
К работе программиста это всё не имеет никакого отношения. Если вы называете «настоящим программистом» человека, который на самом деле нормальный аналитик и нормальный же программист в одном флаконе — ну, называйте, ваше дело. Лично я предпочитаю не выдумывать ненужных определений на ровном месте. И да, программирование и анализ требований практически всегда идут рядышком и для того, чтоб успешно заниматься первым, нужно всегда как-то приемлемо уметь во второе. Но это разные сферы деятельности, а не критерий «настоящести» программистов.
Я вообще-то употребил термин «разработчик». Человек, разрабатывающий некий конечный продукт.
Правильно. Сначала нужно проанализировать куеву хучу треков чтобы понять по каким признакам выделять участки направленного движения, а по каким участки дрифта.
И это тоже работа для разработчика в общем смысле. Да, бывают ситуации, когда эту часть на себя берет аналитик. А бывает когда нет.
А потом еще прогнать эту кучу треков через тесты чтобы понять насколько оно получилось работоспособно. Может быть тут тестировщик поможет. А может и нет.
«Ой» — это если вы не представляете себе что при решении таких задач может потребоваться что-то сложнее правильно составленного запроса в гугл и скачивания готовой формулы.
Естественно хорошего алгоритма нет — откуда ему взяться, когда у вас даже надёжной формализации «целенаправленного движения» нет?
Правильно. Сначала нужно проанализировать куеву хучу треков чтобы понять по каким признакам выделять участки направленного движения, а по каким участки дрифта.
И это тоже работа для разработчика в общем смысле. Да, бывают ситуации, когда эту часть на себя берет аналитик. А бывает когда нет.
А потом еще прогнать эту кучу треков через тесты чтобы понять насколько оно получилось работоспособно. Может быть тут тестировщик поможет. А может и нет.
Если вы не понимаете, что бизнес-задача, описанная обычным языком — это тоже вполне себе ТЗ — то ой.
«Ой» — это если вы не представляете себе что при решении таких задач может потребоваться что-то сложнее правильно составленного запроса в гугл и скачивания готовой формулы.
НЛО прилетело и опубликовало эту надпись здесь
Я на 90% уверен что задачу можно решить за константное время.
Ghh
Фигня какая-то. Пишите ещё.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
К вопросу о математике