• Зачем нужно знать эффективность\сложность алгоритма?

    Maksclub
    @Maksclub
    maksfedorov.ru
    Есть два алгоритма для одной задачи:
    - один проходит по всем элементам один раз и что-то делает, выполняя поставленную задачу O(N)
    - другой проходит по всем элементам для каждого элемента: O(N^2)

    При количестве элементов N=10, в цикле в первом случае будет 10 операций, во втором случае 100 (казалось бы, в 10 раз больше всего)
    Но при увеличении до N=1000 в первом случае 1000 проходов, во втором уже 1 000 000 ! Видите как сильно растет разница.

    Даже при небольших значениях N это может быть важно, если каждая операция долгая/тяжелая и даже 2-3х кратное увеличение может быть проблемой.
    Ответ написан
  • Какие вы знаете актуальные труды на тему алгоритмов и структур данных?

    dom1n1k
    @dom1n1k
    Кнут живее всех живых.
    Все классические алгоритмы и структуры данных были придуманы примерно к девяностым годам и с тех пор не менялись. Теорема Пифагора поменялась за 2 с лишним тысячи лет? А интегрирование по Риману устарело?
    То, что придумано в области алгоритмов в более поздние годы - уже, как правило, штуки для узкоспецифичных и сложных случаев. Начинать нужно явно не с них.
    Ответ написан
  • Какие вы знаете актуальные труды на тему алгоритмов и структур данных?

    dimonchik2013
    @dimonchik2013
    Твой торт с каждым годом горит всё ярче
    "Грокаем алгоритмы" посмотри, если Кнут не дается

    но он и не должен легко даваться
    Ответ написан
  • Какие вы знаете актуальные труды на тему алгоритмов и структур данных?

    BojackHorseman
    @BojackHorseman
    ...в творческом отпуске...
    там нечему устаревать. три издания для классического учебника не показатель.

    недавно в руки попалось девятое издание учебника химии для французских ВУЗов 1908(!) года оригинала. и по нему до сих пор преподают.
    Ответ написан
  • Как решать задачи на ДП такого типа (выбрать предметы, но без повторений)?

    wataru
    @wataru
    Это классическая задача о рюкзаке.

    Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

    База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
    Пересчет:
    F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))


    Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

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

    Сначала реализуйте все дп на матрице снизу вверх, двумя циклами.
    Теперь, если вы будете гнать внутренний цикл с конца к началу, то вам не понадобится смотреть на уже переписанные на текущей итерации внешнего цикла значения, и можно забить на второй параметр ДП и просто переписывать строку на месте.
    Ответ написан
  • Какие области IT сильно связаны с алгоритмикой и математикой?

    Robur
    @Robur
    Знаю больше чем это необходимо
    Когда я в универе был олимпиадником (АСМ) тоже думал - главное - быстро и круто алгоритмы писать, это настоящее программирование, а не вот эти ваши формочки клепать.
    На деле, как вам уже сказали, олимпиадные скиллы хороши ровно в одной области - выигрывании на олимпиадах.
    И основное умение получаемое там - суметь очень быстро написать код который пройдет по жестко заданным тестам. В реальной жизни, к сожалению, это называется "малоподдерживаемый говнокод который проще выкинуть".
    Потому что "пройти тесты" - это только малая часть хорошего кода и правильной архитектуры и алгоритмов.
    Там есть время подумать и написать хорошо, придумать алгоритм лучше, проверить разные варианты и так далее. Это все умеет любой хороший профессионал.

    Проведу аналогию - есть спортсмен который отлично научился в бассейне быстро плавать по прямой. Он один из лучших и вообще молодец. Знает до деталей как двигать руками, как загребать воду максимально эффективно, какую шапочку использовать для уменьшения трения и так далее. И тут задался вопросом - а где я, такой молодец, могу работать? Ответ - в том же бассейне, тем же спортсменом. Потому что за пределами бассейна, оказывается, надо еще 100500 совсем других умений. Даже спасатель на пляже из него выйдет хреновый, потому что мало быстро доплыть до человека, его сначала увидеть, а потом еще и спасти надо. Профессиональные спасатели может и плавают медленнее чем он, зато знают куда смотреть, как понять что человек тонет, как к нему плыть как вытаскивать, откачивать и так далее. И при этом плавают-то не намного хуже. Наш спортсмен из бассейна ничего этого не знает и не умеет.

    В программировании все точно так же. Нет такой профессии "решатель алгоритмических задач" (за пределами спортивного программирования). Любой профессионал в первую очередь должен будет знать огромную всяких знаний из своей области и уметь кучу умений, и уже во вторую очередь - среди прочих навыков так же уметь решать алгоритмические задачи.

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

    Понятно что области разные, но вы думаете о том что будет через 5-10 лет, а этого никто не знает. Когда я выпускался с универа, программирование было уделом очкариков не от мира сего и какая-то тухлая тема, даже в нии программисты это был больше фарс и я пошел потому что просто нравилось, совершенно без всяких перспектив а оно вон как все повернулось - сейчас работа мечта.

    Так что выбирайте по области которая нравится. Пробуйте одно, другое. Информации - море, думаете про дата саенс - полгода проживите так будто туда собрались, читайте статьи, общайтесь в сообществах, участвуйте в вебинарах - конференциях, подпишитесь/задружите с теми кто там работает. Через полгода поймете точно - оно или нет. Поменять всегда успеете, у вас 5-6 таких заходов во время учемы, можно не спрашивать на тостере а просто попробовать всё. Возможно к тому времени как вы доучитесь в универе, появится пачка новых профессий которые вам отлично подойдут.

    Удачи в общем и не грузите себе мозги раньше времени зазря.
    Ответ написан
  • Как асинхронно запускать функцию, которая блокирует управление?

    dimonchik2013
    @dimonchik2013
    Твой торт с каждым годом горит всё ярче
    1) находите любой код асинхронного парсера (asyncio, loop - вот это во все )
    2) заменяете вызовы вызовами вашей функции (срабатывание негарантировано)

    выбрасываете

    читаете про многопоточность и мультипроцессинг
    Ответ написан
  • Как асинхронно запускать функцию, которая блокирует управление?

    @bacon
    1. И где код с asyncio?
    2. Без asyncio запускать в потоке/процессе и лучше использовать что-то высокоуровневое, типа Executor https://docs.python.org/3/library/concurrent.futur...
    Ответ написан
  • Влияет скорость python на веб-программирование?

    sergey-gornostaev
    @sergey-gornostaev Куратор тега Python
    Седой и строгий
    Web-приложение это частный случай сетевого ПО, а у сетевого ПО издержки на ввод/вывод такие, что на их фоне издержки на выполнение незначительны. Проще говоря, если программист не криворукий, то Python не уступает в вопросе web-разработки любому другому языку.
    Ответ написан
  • Почему не утилизируются полностью все ядра процессора?

    @Shahelm Автор вопроса
    Я разобрался, все банально я не правильно интерпретировал вывод htop, он при отрисовки дерева процесса выводит суммарную информацию по потреблению CPU в главном процессе.

    Всем спасибо.
    Ответ написан
  • Как запускаются программы на разных операционных системах?

    saboteur_kiev
    @saboteur_kiev Куратор тега Программирование
    build engineer
    Код на С++ компилируется в исполняемый файл.
    Для виндовс компилятор выдает .exe файл
    Для линукса - один из вариантов линукс исполняемых файлов (ELF)

    Исполняемые файлы содержат, если не вдаваться в детали, инструкции для процессора, с вызовом функций операционной системы.

    Сам код на С++ может быть кроссплатформенный, предусматривающий его возможность компиляции под разные платформы.
    Ответ написан
  • Работа в IT после 30, возможно ли?

    hottabxp
    @hottabxp
    Эксперт по BeautifulSoup(но это не точно!)
    Карьера программиста после 30+. Миф или реальность?
    Мне 30 лет, кем в IT можно стать за месяц (не трол...
    Поздний старт в ИТ — есть ли шансы?
    Программирование в 28 лет, реально ли научиться и ...
    Возможна ли переквалификация в разработчики после ...
    Реально в 36-40 лет стать тестировщиком или програ...
    Есть ли жизнь программиста-новичка после 30?

    очень сложно запоминать важные детали, хоть памятку печатай!
    у меня такое в 20 было) Пол года назад(сейчас мне 29) начал активно изучать python. Важные вещи записываю в тетрадку(и как то оно само запоминается, редко заглядываю в неё, но бывает такое). Нужно кодить, желательно интересные програмки для себя и все получится(если есть интерес).
    Также прочитайте мой ответ на один вопрос)
    Ответ написан
  • Какой город есть для получения образования и с хорошими возможностями?

    paran0id
    @paran0id
    Красноглазых дел мастер
    С вашими запросами - разве что в какой-нибудь институт благородных девиц. То люди не те, то виды, то влажность. Велкам во взрослую жизнь - у нас тут всё плохо, а будет ещё хуже.

    По существу: поступайте куда сможете. Раз Европа не светит по финансовым причинам, а в МИФИ или МФТИ не пробьетесь - то пофигу, какая у вас будет корочка, лишь бы была и по специальности. Лучше профильное образование неизвестного ВУЗа, чем непрофильное известного.
    Ответ написан
  • Нужна ли вышка веб-программиста?

    @anikavoi
    Мне 48 лет, из них больше 30 я в IT. Образование - 8 классов и "подворотня".
    Мне иногда ужасающе нехватает высшего образования.
    Все-таки лучше когда "школу обучения" прививают специалисты.
    То что "программит на (чемугодно)" не столкнется с чем-то из математики - не верь.
    Сидишь такой фигачишь сайты, и тут хренак - GIS-проект, и ты начинаешь натягивать теорему арксинусов на геоид Красовского, потому что нужны расстояния между точками поверхности.
    Или задача фильтрации данных, и ты пытаешься осилить преобразование Фурье.
    Или данные от источника могут поступать с запоротыми битами, потому что источник болтается на орбите, и ты впарываешься в коды Боуза-Чоудхури-Хоквингема...

    Википедия? Агась!
    https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%...
    Стало понятнее? Вот-вот...

    Так что, послушай старого дурака, который всю жизнь испытывает трудности с тем, чему его могли давным-давно научить - бери вышку! Потом не пожалеешь.
    Ответ написан
  • Разработчик недисциплинированно трекает время. Что делать?

    sergey-gornostaev
    @sergey-gornostaev
    Седой и строгий
    А зачем вообще трекать время? Уложился в дедлайн - молодец. Не уложился - разбор полётов. Хронически не укладывается - понижение грейда или увольнение.
    Ответ написан
  • Как асинхронная программа(event loop) понимает, что пришел ответ от сервера?

    bingo347
    @bingo347
    Бородатый программер
    Что-бы понять асинхронность полностью придется постепенно опустится на самый низкий уровень, вплоть до железа. Но начать стоит с самого верха - с уровня нашего приложения.

    Итак, мы пишем на нашем высокоуровневом любимом языке, неважно JS/Rust/C#/Scala/Python или любой другой. В современном мире у нас скорее всего есть какая либо абстракция для работы с асинхронными апи, предоставляемая или стандартной библиотекой языка или сторонними библиотеками. Она может быть примитивной и основанной на колбэках или более продвинутой, вроде Future/Promise/Task или чем-то подобным. Иногда наш язык предоставляет синтаксис наподобие async/await для более простой работы с этими абстракциями, а иногда асинхронная работа может вообще быть скрыта от нас в рантайме языка, например как с горутинами в Go. Но в любом случае где-то под капотом у нас будет event-loop, а иногда и не один, так как никто не запрещает нам писать многопоточку в то же время используя асинхронные вызовы.

    Сам event-loop - это не более чем обычный while(true) или любой другой бесконечный цикл. И внутри этого цикла наша программа имеет доступ на извлечение к некоторой очереди (если не знаете, что это за структура данных, то погуглите), которая содержит в себе результаты уже обработанных задач. Программа берет очередной результат, находит ожидающий ее колбэк/Promise/Future/Task и запускает выполнение ожидающего кода. Очередей опять же может быть несколько и обрабатываться они могут по разному, но это не важно. Важно то, что наш основной поток (или потоки) ничего не знают, о том как выполняются асинхронные задачи. Он лишь смотрит, есть ли в очереди результат, и если есть - обрабатывает его, а если нет, то принимает решение или выйти из цикла (и завершить поток, а иногда и весь процесс) или уснуть пока новых результатов не появится.

    Но откуда же в очереди берутся результаты? Надо понимать, что асинхронная программа почти всегда многопоточная и результат операций попадает в очередь из фоновых потоков, которые просто блокируются в ожидании нужного ресурса (или сразу многих ресурсов, если используют системные апи вроде epoll или kqueue). Как правило такие фоновые потоки большую часть времени находятся в состоянии ожидания, а значит не потребляют ресурсы CPU и не попадают в планировщик ОС. Такая простая модель действительно позволяет сильно экономить ресурсы по сравнению с моделью, где множество потоков выполняют по 1 задаче и самостоятельно ожидают свои запросы.

    Важно отметить, что в современном мире даже на среднеуровневых языках, вроде C или C++, не говоря уже о высокоуровневых, не реализуют асинхронность сами. Во-первых, на разных ОС для этого используются разные апи. Во-вторых, эти апи на разных ОС умеют обрабатывать разные типы ресурсов (с сетью вроде как умеют работать все основные ОС, но помимо сети асинхронно можно работать с пользовательским вводом, диском и периферийными устройствами, вроде сканеров, вебкамер и прочего цепляемого в usb). Наибольшую популярность (ИМХО) имеет кроссплатформенная библиотека libuv, хотя в Rust принято использовать mio (или даже абстракции над ней, вроде tokio), в C# подобные механизмы есть в .NET Core, а в Go оно уже зашито
    в те самые 1.5МБ рантайма, что Go засовывает в каждый бинарь
    (там правда еще и GC, но один фик это много и достойно вынесения в динамическую либу)


    Ок. С прикладным кодом вроде разобрались. А что же происходит в ядре ОС? Ведь, как писалось выше, у нас даже есть апи, чтоб ждать запросы пачкой. Все просто. Ядра ОС стали асинхронными еще до того, как это стало мейнстримом, если мы конечно имеем дело не с ОС реального времени (но у нас же винда/линь/мак/фряха, а не ОС для бортового компа боинга, где это критично). Смотрите, когда что-то происходит на внешней периферии (ну например диск запрошенные данные прочитал или по сети данные пришли, или юзер мышкой дернул), то формируется прерывание. CPU реально прерывает свою текущую работу и бежит смотреть что случилось, точнее вызывает обработчик предоставленный ОС. Но у ОС то есть основная работа, поэтому она скорее старается освободить обработчик и просто скидывает все данные в оперативку, а разбираться будет потом, когда очередь дойдет. Ничего не напоминает? Очень похоже, на то что происходило в event-loop, только вместо фоновых потоков "результаты" попадают в очередь из прерываний. А уже когда-то потом ОС отдаст данные в драйвер устройства, ну и т.д., пока они не дойдут до нашего прикладного приложения. Вот и все, никакой магии.
    Ответ написан
  • Что использовать для получения TCP-пакетов в python?

    sergey-gornostaev
    @sergey-gornostaev Куратор тега Python
    Седой и строгий
    Использовать нужно сокеты. В некоторых случаях можно с asyncio.
    Ответ написан
  • Существует ли ассинхронное программирование в языке Си и где про него почитать?

    sergey-gornostaev
    @sergey-gornostaev Куратор тега C
    Седой и строгий
    Начать с чтения про мультиплексирование неблокирующихся сокетов, epoll, kqueue и iocp, продолжить знакомством с библиотеками libevent и libuv.
    Ответ написан
  • Как выполнить нормализацию адресов?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    После того, как открыли для себя сервис https://dadata.ru/, вообще перестали тратить время и деньги на собственные костыли из граблей. Сервис просто огонь.
    Для нас онлайн режим и скорость обработки не критична, поэтому мы даже уложились в бесплатный пробный тариф.
    Вроде бы у них были решения по установке их ПО в закрытом контуре, а это не что иное, как нужный вам оффлайн. Правда тут уже бесплатно не прокатит точно.

    До дадаты этот вопрос решался жутким нагромождением фильтров, регекспов с заменами и человеко-машинного совокупления.
    Общая схема годится не только для адресов, а вообще любых грязных данных:
    1. Входной датасет сохраняем в CSV и НИКОГДА не меняем.
    2. Обработка многоступенчатая. Каждая ступень состоит из фильтра и модификатора. Фильтр решает применим ли модификатор к каждой записи. Модификатор применяет свою модификацию если фильтр разрешил.
    3. Отладочный выхлоп, который показывает и позволяет быстро просмотреть полностью внесённые изменения.
    4. Каждая ступень должна делать минимальное однотипное улучшение максимально большого числа строк. Цель - каждой ступенью уменьшать разнообразие проблем, увеличивать регулярность, стандартизировать.
    5. При огромных входных датасетах можно сохранять промежуточный выхлоп, но в общем очистка должна выглядеть как пайп их последовательных ступеней обработки.
    - Очень часто бывает, что какая-то ступень незаметно ломает данные, а понимаешь это уже поздно, когда последующие ступени реализованы и отлажены, и сильно опираются на результат ломающей. Благодаря ступенчатости и иммутабельности процесса всегда можно зипнуть текущее состояние с любым предыдущим шагом и очередным фильтром заменить необходимые куски.
    - Часто бывает, что какая-то из ступеней улучшив отдельные записи убирает характерные признаки для фильтрации элемнтов для другой ступени. Благодаря такому инкрементальному процессу можно переставлять ступени местами.
    - При внесении ступенью изменения в запись. ступень должна оставлять свою сигнатуру в отдельном столбце. Удобно для поиска проблем.

    Расскажите подробнее почему не рассматривается онлайн. Заинтриговали.
    Ответ написан