Это копия, сохраненная 26 марта 2016 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
В этом треде анону предлагается ответить на вопрос о наиболее часто используемых алгоритмах в повседневной работе, о тех про которые спрашивали на собеседовании ну и естественно языке на котором он пишет. Если хотите, можете делиться своими реализациями алгоритмов в этом треде.
В общем, алгоритмов нить иди!
> вопрос о наиболее часто используемых алгоритмах в повседневной работе, о тех про которые спрашивали на собеседовании ну и естественно языке на котором он пишет
>самый часто используемый в повседневной работе алгоритм это алгоритм похода в туалет
Не удивлюсь если ты и пишешь так же, говнокод видимо для тебя не пустые слова.
Ну охуеть просто, этот петушок надеялся на свой долбоебский вопрос услышать что-то другое. Сажи мудаку, не осилившему Кормена.
Какая книга более годна для вкатывания, Седжвик или Кормен?
Кормен. Седжвика вообще выкинь.
Кормен/Кнут (лучше всего обе осилить) - это теория.
Седжвик - это практика, с++ книга у него хорошая.
Лучше всего сначала теорию, потом практику.
Обе - оверхайпнутая хуйня уровня СНГ. Нормальные пацаны читают Стивена Скиена.
>В этом треде анону предлагается ответить на вопрос о наиболее часто используемых алгоритмах в повседневной работе
Бинарный поиск. Были случаи когда приходилось писать самому, но обычно используется из стандартной библиотеки.
Сортировка - ну тут понятно, обычно используется стандартная. Были случаи что писал сам, но это редкость.
Всякие кэширования. Нельзя это назвать алгоритом наверное, но как прием используется очень часто.
Остальное - алгоритмы специфичные для конкретной задачи и их дохуя, они кастомные. Недавно делал градиентный поиск например.
Раз уж говорим об алгоритмах, у меня есть для вас вот какая задача:
Все мы часто заполняем платежки, налоговые декларации, выставляем инвойсы и т.п. Одной из самых неприятных частей можно назвать "напишите сумму цифрами и словами", например "90012р. – девяносто тысяч двенадцать рублей". Ее очень геморно писать и потом еще напряженнее проверять. Можно ли этот процесс автоматизировать?
Итак, дано:
Цельночисловой неотрицательный ввод (тип Int, >= 0)
Получить:
Представление ввода словами (тип Str)
Язык вывода (русский, английский) на выбор, язык программирования – тоже.
ПРИМЕЧАНИЕ: Мне это не нужно ровно низачем, это не попытка эксплуатировать анона. Более того, я эту задачу уже решил на питоне и через какое-то время выставлю решение. Пишу сюда, потому что моё решение кажется мне громоздким.
Буду очень рад вашим вариантам, господа.
>этот петушок надеялся на свой долбоебский вопрос услышать что-то другое. Сажи мудаку, не осилившему Кормена.
Причем здесь Кормен? Где ты прочел о том, что его не осилили?
Напоминаю необучаемому, суть вопроса:
>наиболее часто используемых алгоритмах в повседневной работе
Ты все алгоритмы из книги ежедневно применяешь дауненок?
Ну хоть один отписал по теме вопроса. Для харкача с 8 летними синьорами получающими по 300к - это уже достижение.
Алсо на чем пишешь? Что спрашивали в плане алгоритмов на собеседовании?
>Алсо на чем пишешь?
C#
>Что спрашивали в плане алгоритмов на собеседовании?
Дали тестовое задание распарсить Cron Expression.
> развешивание ярлыков, проецирование
Лол, ты что обиделся что ли? У тебя-то самого какой наиболее часто используемый в повседневной работе алгоритм?
Какая нахуй интеренсая задача, очевидное говно.
Суть: высчитываешь кол-во цифр до и после запятой/точки, дальше - тупое сопоставление цифр по позиции (тысячи, милионы, сотые и тд) м вставка накопипищенных словечек, "девять тысяч восемьсот пятьдесят тысячных". Решается тупым копипастом, никак иначе.
Тут больше вопрос исследования русского языка, чем программирования.
123 312 343 321
Сто двадцать три миллиарда - триста двенадцать миллионов - триста сорок три тысячи - триста двадцать один.
То есть как минимум надо разделить число на группы по 3 цифры. От группы (миллионы, тысячи и т.п.) будет зависеть последняя фраза группы (хотя она будет зависеть еще от последней цифры самой группы, например "сто одна тысяча" или "сто две тысячи").
Дальше нужно определить по какой системе произносится сама группа (там указание сотен, десятков и единиц).
Примерно так.
Эту «задачу» до тебя (и меня тоже) уже решали на посрале с алголами стопицот тысяч раз, не говоря уже про бейсики с одинесами.
>>613811
>Дали тестовое задание распарсить Cron Expression.
Правильно делают, что вас травят, меньше народу — больше кислороду.
На практике чаще всего встречаю работу с деревьями(=>рекурсией), большинство алгоритмов - линейные. SQL-запросы еще оптимизировать приходится.
>Правильно делают, что вас травят, меньше народу — больше кислороду.
Порванное затравленное быдло убеждает себя в том что оно счастливо потому что травят не только его.
>сука, запостил интересную, на мой взгляд, задачу, а в ответ потоки говна и отсылки в гугл
А хули ты хотел? Программисты даунов с синдором NIH - НЕНАВИДЯТ. За одним исключением - когда синдром NIH у самого себя.
Только вот я, в отличие от вас, выблядков, тестовые задания не делал, и до сих пор как ни странно жив.
А вы, не зная НИ ХРЕНА сосчитаете счас все грабли.
Успехов!
А ты в повседневной работе что чаще используешь - шариковую ручку или столовую вилку? И зачем может кому-то понадобиться эта информация?
А у тебя уже просто стокгольмский синдром: ты считаешь, что вот так с нами и должны они поступать, ихнее место возле корыта, наше место у параши, а вот он врёт (показывая на меня пальцем).
Беги, куда глаза глядят, просто беги, у тебя уже внутри сломался внутренний стержень, загрызут насмерть.
> ты считаешь, что вот так с нами и должны они поступать, ихнее место возле корыта, наше место у параши, а вот он врёт (показывая на меня пальцем).
Какой синдром кукаретик? С хуя ли ты решаешь за других о том, кто как считает?
>>613842
> А вы, не зная НИ ХРЕНА
На анонимной борде определил степень познания. Медиум блядь. Съеби обратно, откуда вылез.
Первый адекват в треде, спасибо.
>надо разделить число на группы по 3 цифры
именно таким путем я и пошел
после каждой группы (разряда) - элемент списка согласно порядковому номеру разряда (тысяча, миллион, миллиард, етс.)
интересна логика внутри разряда, особенно случаи с "одиннадцать" и другими "-надцать".
>хотя она будет зависеть еще от последней цифры самой группы, например "сто одна тысяча" или "сто две тысячи"
а вот это вообще интересно. я делал через английский и вот этому, как раз, внимания не уделял.
Поясняю для тупых.
Есть три куна. Фарид Аль-Факун, Ванька Ерохин и Анонька Хиккаев. Первый крутился, занимал бабло, искал дешёвые варианты, дёргал связи, в итоге открыл свой автосервис, имеет крутую бээмвэ-сэмъ, трёхкомнатную квартиру и кучу бабла чтобы открывать второй автосервис. Второй окончил ПТУ и работает у первого за зарплату, стал хорошим мастером, катается на ланосе и оплачивает однушку в ипотеку. Третий лентяй и балбес, сидит у мамке на шее и иногда фрилансит визитки для первого, денег не может накопить даже на новый велосипед, задачу «сумма прописью» спрашивает на двощах.
Так вот. С точки зрения Аль-Факуна, он всего добился сам, благодаря талантам, ну может еще немного родственники помогли. Он создаёт рабочие места для Ерохиных, платит почти все налоги, и очень одобряет капитализм. Самого Ерохина считает парнем «второго сорта», так как тот свой автосервис не открыл, а работает у него, однако старается не обижать, хотя и пытается иногда наебать с зарплатой или припахать сверхурочно. Хиккаев же — ленивый долбоёб, и всё его нищебродство только от того, что он ленивый долбоёб, и пусть пиздует работать. Это правда.
С точки зрения Ерохина, дела идут не так уж плохо. Правда, Аль-Факун и его родня не дают ни дня времени на то, чтоб открыть своё дело, ну и наёбки с зарплатой раздражают, но всегда можно подхалтурить, да и в других автосервисах платят примерно так же, а тут ещё кредит отдавать, зубы лечить и всё такое. Неплохо было бы, если бы Фарид отдавал больше денег на всякую полезную хрень — типа вот помог бы сына-распиздяя в универ пристроить, или на зубы бы выдал в виде премии. Хиккаев, по мнению Ерохина, тупица-неудачник, однако было бы здорово, если бы Аль-Факун взялся оплатить и ему шарагу, так как нищеброды-родители Хиккаева не могут, а то может быть из парня и вышел бы толк. Это маниловщина.
Аноня Хиккаев считает, что Ерохин — жлоб и быдло, которое не понимает ничего, а Аль-Факун вообще гандон, работник внутренних органов, подлежащий немедленной аннигиляции. Было бы здорово (мечтает Аноня, лёжа на диване) если бы Ерохины всего мира повесили бы на фонарях всех Аль-Факунов, ради свободы, а все аль-факунье бабло поделили, и чтобы можно было не работать, а всё равно иметь денег достаточно и на велосипед, и на машину даже, а может и на квартиру, просто так, потому что равенство. Заодно чтоб подсказали эту йобанную задачу с суммой прописью, которую он сам почему-то считает алгоритмом. Не было бы тогда так обидно смотреть на жырную аль-факунью рожу в окне бэхи, или читать тут, как трудяга-Ерохин с его соседкой на лестничной клетке обсуждают его, Анонькину, никчёмность. О том, чтобы оторвать жопу от дивана и пойти учиться и работать, Хиккаев даже слышать не хочет, а собственное дело открывать и подавно, ведь всё схвачено, прогнило, взятки, бизнес отберут, и вообще это угнетение трудящихся, к которым он почему-то причисляет и себя. Но иногда он соглашается сделать для них тестовое задание (не понимая, что ему просто плюют в харю), испытывая вместе с внезапным страхом ещё и приступ зависти и подавленной злобы, и это — стокгольмский синдром.
Поясняю для тупых.
Есть три куна. Фарид Аль-Факун, Ванька Ерохин и Анонька Хиккаев. Первый крутился, занимал бабло, искал дешёвые варианты, дёргал связи, в итоге открыл свой автосервис, имеет крутую бээмвэ-сэмъ, трёхкомнатную квартиру и кучу бабла чтобы открывать второй автосервис. Второй окончил ПТУ и работает у первого за зарплату, стал хорошим мастером, катается на ланосе и оплачивает однушку в ипотеку. Третий лентяй и балбес, сидит у мамке на шее и иногда фрилансит визитки для первого, денег не может накопить даже на новый велосипед, задачу «сумма прописью» спрашивает на двощах.
Так вот. С точки зрения Аль-Факуна, он всего добился сам, благодаря талантам, ну может еще немного родственники помогли. Он создаёт рабочие места для Ерохиных, платит почти все налоги, и очень одобряет капитализм. Самого Ерохина считает парнем «второго сорта», так как тот свой автосервис не открыл, а работает у него, однако старается не обижать, хотя и пытается иногда наебать с зарплатой или припахать сверхурочно. Хиккаев же — ленивый долбоёб, и всё его нищебродство только от того, что он ленивый долбоёб, и пусть пиздует работать. Это правда.
С точки зрения Ерохина, дела идут не так уж плохо. Правда, Аль-Факун и его родня не дают ни дня времени на то, чтоб открыть своё дело, ну и наёбки с зарплатой раздражают, но всегда можно подхалтурить, да и в других автосервисах платят примерно так же, а тут ещё кредит отдавать, зубы лечить и всё такое. Неплохо было бы, если бы Фарид отдавал больше денег на всякую полезную хрень — типа вот помог бы сына-распиздяя в универ пристроить, или на зубы бы выдал в виде премии. Хиккаев, по мнению Ерохина, тупица-неудачник, однако было бы здорово, если бы Аль-Факун взялся оплатить и ему шарагу, так как нищеброды-родители Хиккаева не могут, а то может быть из парня и вышел бы толк. Это маниловщина.
Аноня Хиккаев считает, что Ерохин — жлоб и быдло, которое не понимает ничего, а Аль-Факун вообще гандон, работник внутренних органов, подлежащий немедленной аннигиляции. Было бы здорово (мечтает Аноня, лёжа на диване) если бы Ерохины всего мира повесили бы на фонарях всех Аль-Факунов, ради свободы, а все аль-факунье бабло поделили, и чтобы можно было не работать, а всё равно иметь денег достаточно и на велосипед, и на машину даже, а может и на квартиру, просто так, потому что равенство. Заодно чтоб подсказали эту йобанную задачу с суммой прописью, которую он сам почему-то считает алгоритмом. Не было бы тогда так обидно смотреть на жырную аль-факунью рожу в окне бэхи, или читать тут, как трудяга-Ерохин с его соседкой на лестничной клетке обсуждают его, Анонькину, никчёмность. О том, чтобы оторвать жопу от дивана и пойти учиться и работать, Хиккаев даже слышать не хочет, а собственное дело открывать и подавно, ведь всё схвачено, прогнило, взятки, бизнес отберут, и вообще это угнетение трудящихся, к которым он почему-то причисляет и себя. Но иногда он соглашается сделать для них тестовое задание (не понимая, что ему просто плюют в харю), испытывая вместе с внезапным страхом ещё и приступ зависти и подавленной злобы, и это — стокгольмский синдром.
>>613768
не, ну найти готовую либу я и сам смогу.
а вот покрутить эту задачу пару дней в голове, поразмышлять о том, как мы используем свой (или не очень свой) язык – это, похоже, у местных 8-летних сеньоров не в моде.
> особенно случаи с "одиннадцать" и другими "-надцать".
Это исключения. Они свойственны естественным языкам. Поэтому придется их обработать, и таки да, это усложнит код.
йеп. вывел в отдельный список.
французы, кстати, вообще считают двадцатками. для них просто перевести списки будет недостаточно, наверное. жаль, что не знаю французского, было бы еще интереснее.
Двачую
Кстати, далеко не все программисты могут освоить поход в туалет. Например, в правильном алгоритме похода в туалет есть проверка на то, занят толчек или нет по положению индикатора на двери, а большинство быдлокодеров тупо его игнорируют и начинают ломиться.
И не лень тебе было весь этот высер сочинять кукаретик? Если бы ты зашел в википедию и прочитал что такое Стокгольмский синдром, то не обосрался бы со "своими" понятиями данного психологического состояния.
>Но иногда он соглашается сделать для них тестовое задание (не понимая, что ему просто плюют в харю), испытывая вместе с внезапным страхом ещё и приступ зависти и подавленной злобы, и это — стокгольмский синдром.
Стокгольмский синдром – психологический феномен, выражающийся в том, что жертва, поначалу испытывающая к агрессору страх и антипатию, впоследствии проникается к нему симпатией. Что ну никак не вяжется с твоими Ашотами и Ерохиными. У тебя походу Стокгольмский синдром головного мозга, поехавший.
Тестовое задание выполняется для отсеивания быдла подобного тебе и дальнейшего собеседования будущего работника. Если ты не можешь выполнить даже тестовое задание (обычно не сложное) так нахуя ты нужен как работник? Чем блядь ты тут гордишься? Тем что не сделал тестовое задание и попал на работу?
google: "сумма прописью"
>напишите сумму цифрами и словами
Можешь глянуть исходники этого гема, если понимаешь Руби:
https://github.com/kslazarev/numbers_and_words
Для каждого класса (единиц, десятков, сотен, тысяч) и для данного языка написать классы энкапсулирующие логику строкового представления числа и учитывающие языковые нюансы (суффиксы, и т.д.).
Почему?
Филологической дрисни
huit
>Если ты не можешь выполнить даже тестовое задание (обычно не сложное) так нахуя ты нужен как работник? Чем блядь ты тут гордишься? Тем что не сделал тестовое задание и попал на работу?
>Это филологическая дрисня, к программированию не имеющая отношения.
Ловите дауна, который путает филологию и лингвистику.
Лингвистика - это почти математика, методы там соответствующие, и к алгоритмам имеет очень близкое отношение, и тема интереснейшая (хотя генерация чисел прописью - это скучно, да)
Нахуй иди со своим русским языком. Особенно в плане числительных.
>Лингвистика - это почти математика, методы там соответствующие, и к алгоритмам имеет очень близкое отношение, и тема интереснейшая
От языка зависит, если какой нить африкаанс или английский, то да.
А если говно типа русского да еще и с числительными...идите в общем нахуй со своим царством исключений.
>Бинарный поиск
Мне вот сравнительно часто приходилось делать. Хотя вещь вполне себе формализуемая: сортированный массив с индексами, функция сравнения, параметр, что нужно вернуть (предыдущий/следующий/совпадающий итп).
>Сортировка - ну тут понятно, обычно используется стандартная.
Стандартной сортировки не существует. У каждого алгоритма свои уникальные наборы параметров. Например merge sort пригоден для случая когда памяти очень мало, а данных много. Бывает нужна стабильность сортировки. Кстати, существуют ещё специализированные сортировки для определённых типов данных, которые работают с ещё лучшей сложностью, чем самый крутой абстрактный алгоритм (тот который берёт произвольную функцию сравнения).
Советую глянуть код Хаффмана. Этот алгоритм выдаёт наиболее оптимальный битовый алфавит для любого набора символов. Это конечно скорее для архиваторов, но я разок использовал.
Вообще не так часто на самом деле нужно использовать всякие алгоритмы. Часто задача решается тривиально и комбинаторными переборами. Конкретные алгоритмы ищутся под конкретную задачу. Например в рендеринге дохуя разных алгоритмов. Есть около десятка разных алгоритмов разворачивания текстур (uv unwrap). Есть множество алгоритмов отсечения невидимых объектов для игор (BSP, octree, frustum culling, occlusion culling, etc). Есть множество алгоритмов LOD для них же, как генерации мешей, так и подгрузки/отрисовки/сшивания. Их очень дохуя всяких разных. Знание как делать cuckoo search здесь например бесполезно.
Есть например алгоритм A* для поиска ближайшего пути. Есть алгоритм Дейкстры для того же. Есть алгоритм поиска расстояния между строками (минимальное количество редактирований). Дохуилион их всяких разных есть. И почти все они решают определённую специфичную задачу. Вот когда встретишь эту задачу - тогда и глянешь алгоритмы. Учить всё заранее нет никакого смысла.
>Дальше нулевой листать не имеет смысла, а на ней про алгоритмы - ничего нету,
https://2ch.hk/pr/res/582230.html (М)
Найс ты порвался, что аж по штанине потекло.
https://ideone.com/hcuvMA
Блин, у нас вообще неочевидная тема с походом в туалет. Туалет не в офисном помещении, а в отдельном коридоре за закрываемой изнутри офиса дверью, туалет на две кабинки. Перед дверью в офисе висит 2 таблички свободно-знаято - типа пара битовых флагов, при заходе нужно НЕ ЗАБЫВАТЬ переворачивать флаг в правильное положение, иначе кто-то может подумать что туалет не занят, а дверь открыта и закрыть изнутри, а зашедший в туалет останется торчать у параши пока кто-то не откроет.
Есть ли задачки на алгоритмы?
Все основные алгоритмы уже давным давно есть в библиотеках. Даже если не хочешь знать реализацию, нужно хотя бы знать сложность того или иного алгоритма.
>предлагается ответить на вопрос о наиболее часто используемых алгоритмах в повседневной работе
git pull
fix
git add
git commit
git push
???
profits
>Сортировка - ну тут понятно, обычно используется стандартная.
Стандартная - это какая? Селектами?
Пузырьком.
Я вот скрипто питух и веб макака тут на 99% задач есть решений вагон и библиотеки.
Под мобильную разработку или игрули там вроде тоже давным давно все решено, если вы конечно не Кармак какой нибудь.
Какое то узкоспециализированное ПО пишите?
А деревья?
C, немного C++, скрипты для Busybox
Использую: RSA, AES, CRC32
Самому чаще всего надо писать обходы деревьев, все более сложное уже в библиотеках.
>Ребят, подскажите с алгоритмом, я застрял в 1963 и заебался совсем
Алан Бьюли, "Изучаем SQL".
Точно ж! это категория NSString+Util.
for(int i = 0; i < 100; i ++) {
[NSString russianDeclensionForNum:i one:@"селёдка" two:@"селёдки" five:@"селёдок"]
}
Пришла тебе база данных в формате csv размером 300Гб. Необходимо очистить её от повторений. Имеется обычный компуктер с 4Гб оперативы. Вперёд.
>SQL-запросы еще оптимизировать приходится
Что можешь рассказать? кроме очевидных индексов, хотя и про них будет интересно
Портишь в sql, делаешь DISTINCT, не?
Карасик, поняли да, карасик.
https://tools.ietf.org/html/rfc4122#section-4.4
>The version 4 UUID is meant for generating UUIDs from truly-random or pseudo-random numbers.
Кек.
Мне на работе хватает фибоначи.
Отвечу сам на свой вопрос. Скорее всего в стандартной реализации unordered_map поддерживается еще линкед лист, содержащий адреса непустых бакетов. А в каждом непустом бакете содержится адрес ноды листа, чтобы если че ноду можно было удалить за O(1).
Никогда не понимал зачем народ гадает, взять бы да и написать анализатор сложности алгоритмов, да и исследовать что угодно отдавая туда разные n с построением графика.
Грубо говоря, обычный for - это for 1 порядка, т.е for(i, 0..n){...}
Вложенный for(i, 0..n) {for(j, 0..n){...}} - 2го порядка, и так далее.
Так вот, если количество порядков динамическое - как реализовать сабж?
Заюзал LCS - нахождение наибольшей общей подпоследовательности.
Исправлял фильтрацию элементов в списке. Модель данных в проекте - уберкривая. Из-за этого часть данных невозможно отфильтровать с помощью айдишников, если параметры фильтрации не строки - а итемы из комбобоксов. Поэтому некоторые элементы все равно проходили фильтрацию, хотя не должны были.
Решил использовать смекалочку - дополнительно находил LCS между двумя строковыми полями в итеме, и если у нее длина меньше двух, то фильтр не пропустит. Проект - говносайт на ASP MVC.
Обычно реализации хэш таблиц, которые для людей, содержат итераторы по ключам. В C#, JavaScript например. Если в твоей крестоблядской хэш таблице есть такая хуйня, то будет O(n). Проход по итератору O(n) * доступ к элементу по ключу O(1).
А хули там гадать? На такую хуйню, которая лежит перед глазами, все находится интуитивно. Жопа наступает, если в логике куча спагетти с рекурсиями в придачу. Но для этого, в православных IDE есть профайлеры, работающие в дебаге. Но сидящим тут студентам, возомнившим себя программистами, кроме лаб ничего не писавших, это рано знать. Пусть головой научатся думать для начала. А это инструменты для опытных дядек.
Это уже есть и в виде макроса для эксел и в виде веб-станицы и подозреваю, что в виде экзешника.
Это копия, сохраненная 26 марта 2016 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.