Рассмотрим целочисленный массив a длины n. Назовём расстоянием от индекса i до множества индексов S величину dist(i,S)=∑_j∈S|a_i−a_j|. Зафиксируем целое число k. Рассмотрим функцию f(i)=min dist(i,S), где минимум берётся по множествам S размера k, не содержащим индекс i. Определите значение f(i) для всех i от 1 до n. Пример ввода:
5 3
3 2 5 1 2 В первой строке заданы два целых числа n и k (2≤n≤300000, 1≤kn), описанные в условии. Во второй строке содержится n целых чисел ai (1≤a_i≤10^9) — элементы массива a. Пример вывода:
4 2 8 4 2 Алгоритм работы примерно следующий: К каждому элементу массива ищем k ближайших по значению элемента (сам элемент не учитывается). Получаем сумму модулей разницы найденного и исходного.
def nearest(lst, target): return min(lst, key=lambda x: abs(x — target)) def func(k, arr): result = » for i in range(len(arr)): f = 0 arr_copy = arr.copy() arr_copy.pop(i) for j in range(k): num = nearest(arr_copy, arr[i]) if num in arr_copy: f += abs(arr[i] — num) arr_copy.remove(num) result += str(f) + ‘ ‘ return result def main(): f = input().split() s = map(int, input().split()) print(func(int(f[1]), list(s)))
Пробовал обходить алгоритм при встрече высчитанного элемента — результатов в плане сокращения времени не дало.
⚡ УСКОРЯЕМ PYTHON в 20 РАЗ! | Новый способ :3
Отслеживать
задан 12 фев 2022 в 20:53
13 3 3 бронзовых знака
Сложность вашего алгоритма — кубическая O(n*k*3n) . Как минимум можно за за O(n*k) . Плюс копирование списка — это довольно времязатратная процедура.
Источник: ru.stackoverflow.com
Оптимизация кода на С++
Иногда бывает сложно решить, какую конструкцию лучше использовать i++ или ++i, либо выбрать между конструкцией if-else и switch. В этой статье, написанной специально для сообщества iT works, представлены наиболее реальные средства оптимизации кода, которые должен знать каждый профессиональный программист.
Некоторые считают, что времена оптимизации на уровне кода прошли навсегда, однако это не так. Сейчас существует множество платформ в которых нет таких могущественных компиляторов как в Microsoft Visual Studio. Например шейдерные языки (hlsl, glsl) или код для CUDA, PlayStation3, SPU или мобильные платформы. В зависимости от организации кода, может в десятки раз отличаться его эффективность иногда из-за неэффективности компилятора, на чаще из-за доступа к памяти.
Программируя для разных платформ изучите возможности вашего компилятора и особенности архитектуры процессора (если вы пишите для конкретной консоли). Проведите тесты производительности разных вариантов оптимизации. Часто сложно предполагать, какие именно способы будут наиболее эффективными. А эта статья подскажет разные приемы, которые могут вам помочь.
Как ускорить Python
Однако не следует оптимизировать слепо, без предварительного анализа и профилирования. Помните, что преждевременная оптимизация — это зло.
Если вы являетесь программистом в VS под Windows, то скорее всего со многими описанными приемами оптимизации компилятор эффективно справится. Обратите внимание на пункты работы с памятью, а так же я рекомендую ознакомиться с техникой Data oriented design. Некоторые советы по ее использования ищите в статье Методы оптимизации памяти.
1. Используйте векторизацию данных и векторные команды их обработки (например SSE в CPU или упаковывайте данные если используете шейдеры или CUDA). Это позволит использовать SIMD (Single Instruction, Multiple Data) архитектуру, что значительно повысит скорость вычислений. Если вы решите использовать этот метод, то не забывайте про выравнивание данных в памяти.
2. Эффективнее складывать и умножать в перемешку, чем сначала все сложить, а потом все умножить. Это происходит от того, что сложение и умножение выполняются разными модулями процессора и могут выполняться одновременно.
int [float, double, single, unsigned] a,b,c,k,m,n,t,f1,f2,f3,g1,g2,g3; a = b + с; k = m + n; t = a + k; f1 = f2 * f3; g1 = g2 * g3; Менее эффективно чем: a = b + с; f1 = f2 * f3; k = m + n; g1 = g2 * g3; t = a + k;
3. Нет разницы по скорости в работе с float и double при сложении и умножении. Они выполняются за равное число тактов процессора и используют одни и те же регистры. При делении и извлечении корня, float работает быстрее.
Однако если вы будете использовать большие объемы данных, то за счет кеша быстрее будет работать тот тип, который занимает меньше памяти (т.е. float), поэтому в общем случае именно его предпочтительно использовать. Выбирать double имеет смысл когда нужна большая точность.
Допустим есть. const float a = 100.0f; float some1 = some3 * 1.0f / a; float some2 = some4 * 1.0f / a; более эффективно написать не: const float a_inv = 1.0f / a; some1 = some3 * a_inv; some2 = some4 * a_inv; а так: some1 = some3 * (1.0f / a); some2 = some4 * (1.0f / a);
Почему это будет эффективнее? Операторы с равным приоритетом выполняются последовательно. Это значит, что будет выполнено сначала умножение, а затем деление.
Если же обрамить операцию деления в скобки, то ее выполнит компилятор, а в реальном времени будет выполняться только операция умножения. Что качается отличий варианта 3 от варианта 2, то в 3-ем варианте не создается дополнительной переменной, нет нужны глядя на код думать о том, что это за переменная. А эффективность 2-го и 3-го варианты будет одинаковой.
5. На больших объемах данных и вычислений на них float выгоднее чем double (из за cache miss’ов, см. пункт 3).
a, b — любое выражение Func1, Func2 — функции, которые вызовутся для вычисления условия if( a b ) — нужно первым ставить менее вероятное условие, для большей эффективности if( a || b ) — нужно первым ставить более вероятное условие, для большей эффективности if( Func1() Func2() ) — нужно ставить более быстрый оператор первым
void Func( int* a ) < int b = 10; Следующие строки одинаковые по эффективности (по времени выполнения): b = 100; *a = 100; >Это происходит по тому, что доступ к стековой переменной осуществляется по указателю на стек.
Тоже идет разыменование указателя.
8. Если есть большой массив структур, то нужно делать размер его элементов равным степени двойки. Тогда проход по такому массиву будет значительно быстрее (в 4 -6 раз), за счет выравнивания указателя на каждую структуру в массиве.
int a[ 1000 ]; for( int i =0; i
SomeClass* p; — указатель на массив элементов x = *(p++); — значительно эффективнее x = *(++p);
По той же причине что и пункт 1. В первом случае будет осуществляться разыменование указателя и его инкремент параллельно, а во втором — последовательно.
11. Количество колонок двумерного массива желательно должно быть равно степени двойки. Это увеличит скорость работы с массивом. Это выравняет указатели на первые элементы каждой строки, что ускорит доступ к элементам.
int mas[ 10 ][ 16 — количество колонок желательно должно быть равно степени двойки ]
u32 a; f32 b; b = (f32)(i32)a; — быстрее b = (f32)a;
13. Избегайте операции приведения типов.
float f; int a; float b = (float)a; — долго int m = (int)f; — очень долго
14. Разумно используйте операции округления:
только для unsigned: (u32)x are 10x times faster than ‘u32(floor(x))’ u32( x + 1.0f ) are 10x times faster than ‘u32(cell(x))’ u32( x + 0.5f ) are 10x times faster than ‘u32(round(x))’
float f = 1.0f; *(int*) — быстрее чем f *= -1.0f;
16. Если в switch используются последовательные значения параметров case ( case 0: case 1: case 2. ) то switch значительно эффективнее чем if-else. Это происходит за счет того, что при if-else будет вычисляться значение каждого условия, а в случае таких параметров в конструкции switch значение будет вычислено один раз, а затем будет переход сразу к нужному пункту.
17. Ветвления — это зло. Старайтесь сокращать их количество. Не делайте их внутри больших циклов. switch — это тоже ветвление. Процессор старается предсказывать результат условия (branch prediction) и если значение выражение почти всегда одно и то же, то ветвление не отразится на скорости выполнения кода.
Однако в общем случае, предсказание ветвления будет не верно в 50% случаев, что будет замедлять выполнение алгоритма. Каждое ветвление — это переход к последовательности команд процессора. Такой переход ломает конвейер команд процессора и стоит достаточно дорого.
Это особенно актуально для шейдеров, SPU подпрограмм, CUDA подпрограмм и в алгоритмах, где идет обработка большого количества данных. Если вам нужно для ста тысяч частиц выполнить какой то код, то постарайтесь минимизировать количество ветвлений. Это может существенно ускорить выполнение кода.
const int NN = 12500000; const int N = 10; следующее плохо (200ms на моей машине): for( int i = 0; i < NN; ++i ) < switch( i % N ) < case 0: res += 10; break; case 3: res += 30; break; case 5: res += 50; break; case 6: res += 60; break; case 8: res += 80; break; >> гораздо лучше (120 ms на моей машине): const int arr[] = < 10, 0, 0, 30, 0, 50, 60, 0, 80, 0 >; for( int i = 0; i < NN; ++i ) res += arr[ i % N ];
18. Рассмотрим пример. Двумерный спрайт содержит массив вершин vertex[ 4 ]. Гораздо эффективнее было бы сделать одно хранилище вершин, а в спрайте индекс смещения относительно первого элемента.
Это по памяти сэкономит 16 байт на каждый спрайт, а по скорости будет процентов на 30 быстрее проход по вершинам. Это data orientad design. Для С# он так же справедлив.
Основные направления оптимизаций:
1. Уменьшение числа ветвлений
2. Группировка данных по одинаковым типам в памяти (в C# никто еще не отменял массивы структур)
3. Уменьшение размеров структур
19. inline функции:
+ дает выигрыш в скорости
— увелечивает код
— добавляет в код зависимости (*.h файлов) при компиляции. Это увеличивает время и объем компиляции при изменении кода в функции
Факты:
1. компилятор может не встроить функцию (даже _forceinlie — нет горантии встраивания)
2. VS компилятор при включенной оптимизацией по скорости встраивает любые функции по своему усмотрению, даже если они не объявлены как inline.
Вывод: нужно избегать использования inline функций. Сейчас это не необходимо. Исключением может быть только очень часто выполняемый низкоуровневый код (как например математические функции) или, если вы пишите программу используя компилятор без полной оптимизации кода (например для компилятора под PlayStation3 использование inline до сих пор актуально).
20. Рассмотрим результат смены порядка переменных в структуре.
struct s1 < short int a; double b; int d; >sizeof(s1[ 10 ]) == 24 * 10 struct s2 < double b; int d; short int a; >sizeof(s1[ 10 ]) == 16 * 10 double по 8 выравнивается всегда
21. От перестановки мест слогаемых для float value, сумма меняется:
1e+8f + 1.23456 — 1e+8f == 0 но 1e+8f — 1e+8f + 1.23456 == 1.23456
22. Бинарный поиск не следует использовать на малом количестве элементов. Если количество элементов меньше чем 40-60 (это число может варьироваться от реализации алгоритмов, но имеет примерно такой порядок), бинарный поиск будет медленнее линейного.
Можно так: bool b; int a = b ? x : y; Но быстрее: int b; ( 0 — false, -1 — true) int a = (x ~b);
int a, b; 1. int x = (a >= b ? 1 : 0); 2. int x = (a >= b ? -1 : 0); Можно заменить на: 1. int x = (b — a) >> 31; 2. int x = (b — a)
i32 iIndex; Условие: if( iIndex < 0 iIndex >= iSize ) Можно заменить таким: if( (u32)iIndex >= iSize ) Условие: if( i >= min i
26. Выше был пример, как можно switch превратить в static const array и обращаться по индексу.
Это применимо например для rtti (run time type identification). Если таким образом определены switch указателей на функции, то замена его доступом к нужной функции за константное время — может быть крайне полезна. То же самое — если это машина состояний. Вместо того, чтобы добавлять новый элемент в свитч, его можно добавлять в массив выше. Но помните про пункт 16.
int func( int index ) < switch( index ) < case 0 : return f_Func1(); case 3 : return f_Func2(); case 4 : return f_Func2(); .. case .. return f_FuncN(): >return 0; > заменить на: int func( int index ) < static funcPtr array[] = < f_Func2, . return array[ index ](); >
Дополнительно
Дополнительные рекомендации по написанию более эффективного кода, можно найти в статьях:
Эффективный код на С++
Методы оптимизации памяти
- c++
- оптимизация
- FiloXSee,
- 31 августа 2010, 11:32
- рейтинг: +2
- это интересно | не интересно
Источник: itw66.ru
Как ускорить выполнение цикла? Алгоритм оптимизации циклов
Что-то на канале давно ничего не было про кодинг. Попытаюсь исправить ситуацию. Сегодня поговорим с вами об оптимизациях цикла. Хорошо известно, что для оптимизации программы, для её ускорения, наши усилия должны быть сосредоточены на локальных областях, чтобы отдача была максимальной. Конструкции цикла в программе как раз представляют собой такие области.
Определенная степень ускорение достигается за счет размыкания, объединения и развертывания циклов.
Размыкание цикла
Если внутри цикла есть условный оператор if-else, и принятие решение внутри цикла происходит на каждой итерации, то это называется замыканием (switching) цикла. Но если при выполнении цикла условие не изменяется, то вы можете разомкнуть (unswitch) цикл, приняв решение вне цикла. Таким образом мы как будто выворачиваем цикл наизнанку. Смысл этого действия в том, чтобы исключить инструкцию проверки условия при каждой итерации, в том случае, когда это условие не изменяется во время итераций цикла.
Размыкание цикла
Не смотря на то, что такие действия нарушают удобочитаемость кода, такое размыкание приводит к увеличению производительности примерно на 20% в C++, Java и Python, а также около 1% в Visual Basic.
Нужно еще понимать, что результат отдельного вида оптимизации непредсказуем в контексте разных языков программирования. Поэтому стоит проверять отдельно на каждом ЯП.
Объединение циклов
А вот и альтернативный, даже противоположный, вариант. Допустим, есть два цикла, которые работаю с одним набором элементов. Тогда можно объединить (jamming) их для получение выгоды при устранение затрат на выполнение дополнительного цикла. Самое важное здесь — это чтобы совпадали диапазоны изменение данных. Приведем пример:
Объединение циклов
В результате объединения производительность улучшается: в С++ на 28%, в PHP на 32%, в VB на 4%.
Развертывание цикла
В информатике под этой фразой подразумеваются различные способы оптимизации программ, такой своеобразный рефакторинг, при котором количество инструкций в цикле увеличивается. То есть за одну итерацию выполняется либо несколько инструкций, либо более сложная инструкция, которая может быть разбита компилятором на несколько.
Зачем это нужно? В результате таких манипуляций увеличивается количество инструкций, которые (в теории) могут быть исполнены параллельно, а также происходит более интенсивное задействование регистров процессора (быстрая память), кэша данных и исполнительных устройств ( АЛУ, Арифметико-логическое устройство ).
Пример развертывания цикла
Целью развертывания является сокращение затрат, которые связаны с выполнением цикла. Интересен факт, что полное развертывание цикла, состоящего из инициализации 10 элементов массива циклом увеличивает производительность на 60% в C++ и Java. То есть 10 отдельных обращений к элементам массива выполняется быстрее, чем три строчки цикла. В народе такой код считают индусским , но он объективно работает быстрее.
Приведем еще пару интересных примеров с однократным и двухкратным развертыванием цикла:
Однократное развертывание цикла
Двукратное развертывание цикла
Как видно отсюда, мы сталкиваемся с возможность ускорения на 15-43%, не считая Python. Тут уже нужно разбираться в байт-коде, не всё является однозначным.
Для дальнейшей оптимизации циклов стоит подумать надо ценой различных операций. Иногда умножение можно заменить на сложение. Иногда вложение более ресурсоемкого цикла в менее ресурсоемкий дает прирост производительности более 15% и экономии времени до 33% на C++ и 34% на Java. Обязательно нужно пробовать снижение стоимости операций. Об этом можно прочитать в главе 26 Методики оптимизации кода в книге Совершенный код Стива Макконнелла ( скачать тут ).
Расщепление цикла
Существует и другая оптимизация, которая называется расщеплением цикла ( loop fission ). Суть заключается в том, чтобы разбить цикл на несколько циклов, при этом все эти циклы имеют одинаковые диапазоны изменения индекса, только содержат разные части тела исходного цикла.
Пример расщепления цикла
Чем помогают эти методы?
Такие оптимизации помогают выполнить цикл на нескольких потоках или на различных ядрах CPU, при отсутствии зависимостей данных между инструкциями в новом цикле.
Чем плохи эти методы ?
В случае распараллеливания, происходит сбой порядка обращения к данным, то есть обращение к данным происходит не по порядку их расположения в памяти. Это плохо сказывает на эффективности работы кэширования.
История создания данного вида оптимизации
Были приложены значительные усилия для разработки методов S2S (source-to-source) преобразования кода, в которых применялась реструктуризация конструкций циклов. Делалось это для того, чтобы открыть возможности для параллелизма вычислений.
Рассмотрим следующий цикл:
Этот цикл FOR может быть преобразован в следующий эквивалентный цикл, состоящий из нескольких копий исходного тела цикла:
В этом случае говорят, что это двукратное развертывание цикла. И этот развернутый цикл должен работать быстрее из-за уменьшения расходов на создание цикла.
Изначально развертывание цикла было разработано для снижения накладных расходов на циклы и для обеспечения параллелизма на уровне инструкций для машин с несколькими функциональными блоками. Относительно недавно этот механизм был применен в сочетании с планированием инструкций для конвейерных и RISC архитектур. Увеличивая размер тела цикла, планировщик команд в большинстве случаев может создавать более короткое расписание инструкций для развернутого цикла.
Циклы for , работающие с массивами, можно развернуть, просто изменив счетчик и условие завершения цикла, как было показано выше. В то время как циклы while , как правило, сложнее развернуть. Это происходит главным образом из-за трудностей определения условия завершения развернутого цикла while.
Обобщенная теория развертывания цикла while
Предположим, что циклы записываются в виде while B do S , семантика которого определяется привычным для нас образом ( пока выполняется условие B делать инструкцию S). Это предположение не должно приводить к потере общности, потому что любой другой цикл может быть переписан в этой форме, которую мы предположили в начале абзаца.
Будем называть B — предикатом цикла, а S — телом цикла. Если подробнее, то так:
тело — это набор инструкций, от одной и более.
предикат — выражение, использующее одну или несколько величин с вычисляемым результатом логического типа.
Используя данный метод анализа, можно показать, что выполняются следующее соотношение эквивалентности.
Обобщенная схема однократного развертывания цикла while
Здесь ⇔ обозначает отношение эквивалентности, а wp(S, B) — самое слабое предварительное условие S ( w eakest p recondition ) по отношению к постусловию B .
Будем говорить, что эквивалентная программа (с правой стороны) получается при однократном развертывании цикла. Обратите внимание, что если какие-либо данные приведут к тому, что цикл слева повторится n раз, то это приведет к тому, что первый цикл справа повторится ⌊ n / 2 ⌋ раза, а второй цикл справа 0 или 1 раз. Теперь, если мы можем упростить B ∧ wp(S, B) или S; S , как объясняется ниже, то мы можем развернуть цикл для достижения определенной степени ускорения вычислений.
⌊ x ⌋ — функция «пол», определяется как наибольшее целое, меньшее или равное x. Обозначения из дискретной математики. ( почитать здесь )
Цикл while можно разворачивать и дальше. Можно показать, что :
Обобщенная схема двукратного развертывания цикла while
Выражение в правой части показывает, как дважды развернуть цикл. Естественно, цикл можно развернуть трижды, четыре раза и так далее и тому подобное.
Таким образом, учитывая конструкцию цикла вида while B do S мы можем ускорить его выполнение, выполнив перечисленные ниже шаги, чтобы развернуть его один раз:
1. Сформировать wp(S, B) как самое слабое предварительное условие S по отношению к B .
2. Развернуть (размотать) цикл один раз, заменив его последовательностью из двух циклов:
while B ∧ wp(S, B) do begin S; S; end;
while B do S
3. Упростите предикат B ∧ wp(S, B) и тело цикла S; S для ускорения.
Обратите внимание, что второй цикл в развернутой конструкции — это исходный цикл. Поскольку он будет повторяться не более одного раза, теоретически его можно заменить конструкцией if B then S . Да, так тоже будет работать. Однако с точки зрения разработки ПО желательно оставлять его неизменным, потому что исходный (оригинальный) цикл легче понять.
Кроме того, если по какой-то причине разворачивание цикла становится нежелательным, всё, что нам требуется сделать, так это просто удалить первый цикл. С этой целью желательно разграничивать первый и второй циклы комментариями. Также с помощью многострочного комментария будет легко отыскать и удалить первый цикл при отладке кода.
Пример 1 . Цикл для вычисления целой части q от деления a на b
Обычный цикл нахождения целой части от деления
Развертываем наш цикл и получаем:
1 вариант развертывания
Эксперименты показывают, что эти варианты однократного развернутого цикла способны достичь коэффициента ускорения очень близкого к 2. Если развернуть цикл k раз, то можно достичь коэффициента ускорения k.
Коэффициент скорости определяется как соотношение между временем процессора, необходимым для выполнения измененной программы (развернутого цикла), и временем, необходимым для выполнения исходной программы.
Замечания и обсуждения
Хотя три приведенных выше варианта развертывания логически эквивалентны в теории, на практике это может быть не совсем так. Обратите внимание, что в приведенном выше отношении эквивалентности ( смотри выше Обобщенная схема однократного развертывания цикла while ) предикатом цикла первого цикла с правой стороны является B ∧ wp(S, B) . Поскольку логическая операция «∧» (И, and,
2. программа компилируется и выполняется в среде, где компоненты предиката цикла оцениваются в указанном порядке, и оценка завершается сразу же, как только обнаруживается, что один из компонентов предиката является ложным.
В противном случае, если эти два условия не выполняются, развернутый цикл может содержать ошибки во время выполнения, которые не возникали бы в исходном коде цикла.
Рассмотрим следующий пример.
Пример 2. Цикл для нахождения GCD ( G reatest C ommon D ivisor) или НОД ( Н аибольшего О бщего Д елителя) двух положительных целых чисел a и b с использованием алгоритма Евклида, конечный результат цикла, который является GCD a и b, хранится в a.
Источник: dzen.ru