Рубрика «оптимизация кода» - 7

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.

image
КДПВ: задача о ранце на живом примере

Предыстория

Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2n (количество сочетаний, умноженное на длину суммы).
Читать полностью »

Добрый день!
Я занимаюсь научными исследованиями в области систем управления, и Matlab — мой основной рабочий инструмент. Одна из возможностей в MatLab — численная оптимизация. Оптимизировать (минимизировать) можно любую функцию, которая принимает на вход вектор варьируемых параметров и возвращает значение минимизируемого критерия. Естественно, в процессе оптимизации целевая функция вызывается множество раз и ее быстродействие существенно. В матлабе есть хорошие программные средства, которые часто позволяют существенно улучшить быстродействие, сохранив при этом читаемость и удобство сопровождения кода. Я приведу пример задачи, покажу на нём, что такое anonymous functions и nested functions, а потом покажу, как можно совместить эти два инструмента для заметного повышения быстродействия.

Читать полностью »

Профильная оптимизация это очень интересный способ оптимизации кода приложения в среде выполнения (в команде разработчиков Visual C этот метод называют POGO или PGO, от английского Profile Guided Optimization). Впервые профильная оптимизация была применена в конце 90-х исследовательскими группами в Visual C и Microsoft. Тогда она была рассчитана для архитектуры Itanium. Затем PGO была включена в состав Visual Studio C/C++ 2005. На сегодня это основной процесс оптимизации, значительно повышающий производительность приложений Microsoft и других разработчиков.
В этом посте будет рассказано, как создавать более быстрые и высокопроизводительные нативные приложения. Для начала, познакомимся ближе с PGO, а затем рассмотрим на примере (симуляция NBody), как с помощью нескольких простых шагов можно применить этот процесс оптимизации в ваших приложениях. Для работы используйте исходный код из примера. Для сборки проекта вам понадобится DirectX SDK.
Читать полностью »

Canvas в GIF на Javascript
Расскажу об особенностях с которыми я столкнулся при сохранении изображения из canvas в gif.
Тут будут рассмотрены готовые решения и мой собственный javascript код квантизации изображения (то есть уменьшение палитры до 256 цветов). Так же будут затронуты вопросы быстродействия некоторых javascript конструкций.
Читать полностью »

В ноябре 2012 года был дан старт конкурсу по параллельному программированию от компании Intel, и этому даже был посвящён отдельный пост на хабре. О конкурсе мы узнали от нашего преподавателя Евгения Калишенко. Он читает курс по «высокопроизводительным и параллельным вычислениям» в Санкт-Петербургском Академическом Университете и стал руководителем нашей команды.

Цель конкурса заключалась в том, чтобы в течение нескольких недель написать и оптимизировать решение одной алгоритмической задачи. Прежде чем описывать её условие, отметим несколько особенностей конкурса.
Читать полностью »

asm.js — новый язык?

Нет, это просто подмножество JavaScript. Программа на asm.js одинаково поведёт себя и в существующих движках JavaScript, и в движке с предварительной (ahead-of-time, AOT) компиляцией, способном распознавать и оптимизировать asm.js; различаться будет её скорость, разумеется!

Какой выигрыш в производительности можно ожидать от asm.js?

Сейчас ещё рано утверждать. Однако наши предварительные измерения производительности программ, скомпилированных из Си в asm.js, показывают не более чем двукратное замедление по сравнению с компилированными в машинный код посредством clang. Мы опубликуем дальнейшие измерения, когда насобираем их.

Как я могу следить за ходом реализации?

Мозилла работает над первой реализацией оптимизирующего компилятора asm.js для SpiderMonkey. В вики Фонда Мозиллы также опубликован план разработки дальнейших выпусков и оптимизаций. Если авторы других движков JavaScript опубликуют собственные планы реализации компиляторов asm.js, мы их здесь упомянем.

Почему бы вам не разработать синтаксис байткода вместо необычного диалекта джаваскрипта?

Для компиляторов наподобие Emscripten или Mandreel синтаксис байткодового языка попросту не особенно значим. Притом большинство байткодов и вообще машинных языков имеют двоичный формат, не читаемый людьми. Однако мы можем создать на уровне asm.js более человеко-читаемый синтаксис, который будет и удобным в дизассемблировании, и пригодным для чтения и записи людьми.

То обстоятельство, что asm.js — это JavaScript, не обернётся ли непредсказуемым выполнением кода?

Предварительная (ahead-of-time, AOT) компиляция asm.js может генерировать код, выполнение которого весьма предсказуемо, потому что валидный код asm.js ограничен крайне небольшим подмножеством JavaScript, состоящим только из строго типизированных целых чисел, чисел с плавающей точкою, арифметических операций, вызовов функций и обращения к куче.

Почему бы тогда не NaCl или PNaCl вместо этого? Вы просто упорствуете насчёт JavaScript?

Принципиальным достоинством asm.js по сравнению с новыми технологиями вроде NaCl и PNaCl является то, что asm.js работает сегодня: существующие движки JavaScript ужé неплохо оптимизируют код, написанный в таком стиле. Что означает, что разработчики могут выпускать код на asm.js сегодня, а со временем его работа будет ускоряться. Другою важною пользою является заметно бóльшая простота реализации, для которой потребуется совсем немного дополнительных механизмов поверх существующих движков JavaScript — и не понадобится слой совместимости API.

Читать полностью »

NUMизматика, NUMерология и просто о NUMANUMA (Non-Uniform Memory Access — «Неравномерный доступ к памяти» или Non-Uniform Memory Architecture — «Архитектура с неравномерной памятью») — технология совсем не новая. Я бы даже сказала, что совсем старая. То есть, в терминах музыкальных инструментов, это уже даже не баян, а, скорее, варган.
Но, несмотря на это, толковых статей, объясняющих, что это, а главное, как с этим эффективно работать, нет. Данный пост, исправляющий эту ситуацию, предназначен прежде всего для тех, кто ничего не знает про NUMA, но также содержит кое-что интересное и для знатоков-NUMизматов, а главное, он облегчает жизнь мне, инженеру Intel, так как отныне всех интересующихся NUMA русскоязычных разработчиков буду отсылать к нему.
Читать полностью »

performanceЯ поделюсь 30 практиками для достижения максимальной производительности приложений, которые этого требуют. Затем, я расскажу, как применил их для коммерческого продукта и добился небывалых результатов!
Приложение было написано на C# для платформы Windows, работающее с Microsoft SQL Server. Никаких профайлеров – содержание основывается на понимании работы различных технологий, поэтому многие топики пригодятся для других платформ и языков программирования.
Читать полностью »

Общий привет.

Недавно, для шлифовки морфологического словаря, способного (предположительно) генерировать все возможные формы слова из инфинитива — мне понадобился достаточно объемный частотный словарь русского языка. Частотный словарь — вещь очень простая, слова в нем упорядочены по частоте, с которой они встречаются в анализируемом тексте.
Читать полностью »

Проверить принадлежность точки невыпуклому многоугольнику за линейное время совсем не сложно. Один из самых распространенных методов — выпустить луч и посчитать число точек пересечения. Однако, при этом нужно аккуратно рассматривать случаи, когда точки многоугольника попадают на луч. Отсюда естественно возникает вопрос, как рассмотреть эти случаи проще всего? Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js