Ответы пользователя по тегу Алгоритмы
  • Где найти задачу на распределенные вычисления?

    ErmIg
    @ErmIg
    Программист
    У вас неправильный порядок действий. Надо было не решать абстрактную задачу путем распределенных вычислений, а потом искать куда бы ее можно применить. Правильный путь, хотя конечно это мое сугубо личное мнение, это при наличии реальной задачи - пытаться ускорить ее при помощи распределенных вычислений, если это конечно требуется и если это возможно. Потому как все задачи разные в плане требований к вычислительным ресурсам, памяти, возможности распараллеливания. И потому не возможно создать систему одинаково эффективную для них всех.
    Ответ написан
  • Какую литературу можете посоветовать по Computer Vision?

    ErmIg
    @ErmIg
    Программист
    В свое время читал "Цифровая обработка изображений" Рафаэль Гонсалес, Ричард Вудс. Рекомендую ее.
    Ответ написан
  • Как автоматически посчитать людей в вагоне метро при помощи видеокамеры?

    ErmIg
    @ErmIg
    Программист
    Ваш алгоритм может базироваться на следующих принципах:

    1) Детектирование движения на фоне неподвижного фона, сегментация движущихся объектов, их сопровождение, а в конце подсчет числа траекторий, которые пересекают вход/выход. В ваше случае этот подход, скорее всего, работать не будет, так как будут проблемы с выявлением фона и с сегментацией отдельных людей - в метро слишком много народа - все будет сливаться.

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

    3) Детектирование людей на основе их вида сверху при помощи HAAR, HOG или LBP каскада (смотри OpenCV). Затем трекинг (например корреляционный), а в конце подсчет числа траекторий, которые пересекают вход/выход. Каска/Каскады потребуется обучить (готовых для такого ракурса я не встречал). Минусы - люди слишком разные (шляпы прически, поворот относительно камеры), каскады хорошо работают с похожими объектами (лицами например).

    4) Отказаться от видео анализа и посмотреть в стороны аппаратных датчиков (хотя я в них не специалист, ничего посоветовать не могу).
    Ответ написан
  • Есть ли основные правила супер оптимизации?

    ErmIg
    @ErmIg
    Программист
    Есть развернутый ответ для С++ кода, но его можно обобщить и на другие языки и платформы:

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

    1) Важно понимать, что алгоритмическая оптимизация практически всегда может дать лучший эффект, чем программная. Так, если алгоритм имеет сложность O(n^2), то на больших исходных данных он при любой оптимизации будет медленнее, чем неоптимизированный алгоритм сложности O(n). Впрочем, при выборе алгоритма, опираться только на его сложность не стоит: если объем исходных данных не велик, то вполне может оказаться, что алгоритм со сложностью O(n^2) будет работать быстрее, чем с O(n).
    2) Очень важно повторное использование (кеширование) промежуточных данных, вычисленных в программе – ибо быстрее всего выполняется работа, которую не надо делать. Тем не менее, не надо чрезмерно кешированием увлекаться – если объем кэшируемых данных слишком велик, то это может отрицательно сказаться на общей производительности программы (некоторые данные быстрее вычислять на лету, чем считывать из памяти).
    3) Следует избегать излишнего копирования данных (например, передавать сложные типы данных по ссылке, а не по значению).
    4) По возможности следует избегать условных операторов во вложенных циклах. Так как условные переходы, вызываемые такими операторами, плохо обрабатываются современными процессорами с конвейерной архитектурой.
    5) Данные в памяти, которые используются алгоритмами, должны по возможности лежать упорядочено, и использоваться последовательно. Это позволит процессору их эффективно кешировать. Важно помнить, что доступ к кэшу процессора значительнее быстрее, чем к оперативной памяти.
    6) Если алгоритмы это позволяют, то возможно стоит реализовать их параллельное исполнение (в отдельных потоках или процессах). Это позволит эффективно задействовать современные многоядерные процессы.
    7) В некоторых случаях (например обработка изображений) большого эффекта можно достичь применением специализированных расширений процессора (SSE, SSE2, AXX, AVX2 и другие). Стоит отметить, что большинство современных компиляторов (GCC, MSVS, ICC) поддерживают непосредственное использование данных расширений непосредственно из С++ кода при помощи специальных встроенных функций (intrinsics). Минусами такого подхода является потеря переносимости (впрочем, эта проблема решается наличием разных веток программы под разные процессоры) и значительное усложнение программы.
    8) Также большого эффекта можно достичь применением специализированных ускорителей, например GPU (технологии CUDA, OpenCL). Минусами таких решений являются потеря универсальности и значительное усложнение программы, а также то, что на специализированных ускорителях, как правило, хорошо работает далеко не каждый алгоритм.
    Ответ написан
  • Как удалять табуляцию?

    ErmIg
    @ErmIg
    Программист
    Для Visual Studio была такая волшебная комбинация клавиш: Control + K а потом Control+ F - авто выравнивание выделенного куска кода.
    Ответ написан
  • Как правильно сравнить массивы и оценить их схожесть?

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