Хотя этот ответ в порядке, я бы порекомендовал ответ Сковородкина ниже:
>>> def partition(number):
... answer = set()
... answer.add((number, ))
... for x in range(1, number):
... for y in partition(number - x):
... answer.add(tuple(sorted((x, ) + y)))
... return answer
...
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])
Если вам нужны все перестановки (то есть (1, 3) и (3, 1) ) изменить answer.add(tuple(sorted((x, ) + y))
на answer.add((x, ) + y)
Switch statements compile to a jump table for consecutive values and to a bunch of if-else statements for sparse values. In any case, you don't want a switch statement in your inner loop for image processing if you care about performance. You want to as below instead.
Also, note that I moved the weight calculation out of the inner loop (and swapped the loops for case 2 in order to achieve this). This type of thinking, moving stuff out of the inner loop, will get you the performance you want out of C.
switch (mode) /* select the type of calculation */
{
case 0:
weight = dCentre / maxDistanceEdge;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 1:
for (x = 0; x < width; x++) {
weight = (float)x/width;
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 2:
// note - the loops have been swapped to get the weight calc out of the inner loop
for (y = 0; y < height; y++) {
weight = (float)y/height;
for (x = 0; x < width; x++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 3:
weight = dBottomLeft / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
case 4:
weight = dTopRight / maxDistanceCorner;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
default:
weight = 1;
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
// Calculate the new pixel value given the weight
...
}
}
break;
// etc..
}
Уже дано много хороших баллов. Единственное, что я мог придумать, чтобы добавить к этому, - это переместить наиболее частые случаи вверх в переключателе, а наименее частые - вниз.
Так что, если случай 4 происходит чаще, чем случай 1, он должен быть выше него:
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
] Жаль, что вы не использовали C ++, потому что тогда оператор switch можно было бы заменить полиморфизмом.
Ура!
но здесь главное - эффективность.
итерация в буфере изображений для вычисления новых значений пикселей звучит как типичная до стыда параллельная проблема, в этом смысле вы можете захотеть чтобы рассмотреть возможность переноса части работы в рабочие потоки, это должно ускорить вашу работу в большей степени, чем микрооптимизации, такие как переключение / регистр.
Кроме того, вместо того, чтобы каждый раз выполнять инструкции ветвления, вы можете вызывать указатель функции из массива указателей на функции, где индекс служит идентификатором вашего режима.
Таким образом, вы получите такие вызовы, как:
computeWeight[mode](pixel);
При 5000x5000 пикселей накладные расходы на вызов функции также могут быть уменьшены путем вызова функции для диапазон пикселей, а не отдельные пиксели.
Вы также можете использовать разворачивание цикла и передачу параметров по ссылке / указателю,для дальнейшей оптимизации.
Использование переключателя, вероятно, лучше как для скорости, так и для времени программиста. Вы делаете менее избыточный код, и он, вероятно, не потребует нового кадра стека.
Переключатели настолько эффективны, что их можно использовать для действительно странной и запутанной черной магии .
Коммутаторы не должны вызывать каких-либо значительных накладных расходов, они компилируются в своего рода массив указателей на нижнем уровне, тогда это эффективный случай:
jmp {baseaddress} + switchcasenum
Зависит от микросхемы, компилятора и деталей кода, и ... но это часто будет реализовано в виде таблицы переходов, которая должна быть довольно быстрой.
BTW- - Понимание такого рода вещей - довольно хороший аргумент в пользу того, чтобы потратить пару недель на изучение ассемблера в какой-то момент своей карьеры ...
В дополнение к совету Джима попробуйте поменять местами порядок циклов. Идеальна ли замена петель для случая 1, потребует тестирования, но я подозреваю, что это так. Вы почти всегда хотите, чтобы ваша координата x находилась внутри вашего внутреннего цикла, чтобы повысить производительность подкачки, поскольку это заставляет вашу функцию иметь лучшую тенденцию оставаться в одной и той же общей области памяти на каждой итерации. А мобильное устройство с ограниченными ресурсами может иметь достаточно низкую оперативную память, чтобы эта разница была подчеркнута.
Для повышения эффективности вам лучше переместить переключатель
за пределы цикла.
Я бы использовал указатели на функции следующим образом:
double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */
double (*fun)(void);
switch (mode) /* select the type of calculation */
{
case 0: fun = fun0;
break;
case 1: fun = fun1;
break;
case 2: fun = fun2;
break;
case 3: fun = fun3;
break;
case 4: fun = fun3;
break;
default : fun = fun_default;
break;
}
for (x = 0; x < width; x++) {
for (y = 0; y < height; y++) {
weight = fun();
// Calculate the new pixel value given the weight
...
}
}
Он добавляет накладные расходы на вызов функции, но не должен не быть слишком большим, поскольку вы не передаете функции никаких параметров. Я думаю, что это хороший компромисс между производительностью и удобочитаемостью.
РЕДАКТИРОВАТЬ: Если вы используете GCC, чтобы избавиться от вызова функции, вы можете использовать метки goto
и в качестве значений: найдите нужный ярлык внутри переключателя и каждый раз переходите к нему. Я думаю, это должно сэкономить еще несколько циклов.
Переключение / регистр выполняется очень быстро по сравнению с эквивалентом с if / else: он обычно реализуется в виде таблицы переходов. Однако это все еще имеет свою стоимость.
Пока вы оптимизируете:
1) Попробуйте перебирать строки, а не столбцы (переключите x и y циклы «for»), одно решение может быть невероятно быстрее, чем другое , из-за управления кэш-памятью.
2) Замена всех делений умножением (предварительно вычисленного) обратного даст вам значительный выигрыш и, вероятно, приемлемую потерю точности.
Операторы переключения примерно настолько эффективны, насколько это возможно. . Они скомпилированы в таблицу переходов. Фактически, поэтому switch настолько ограничен: вы можете написать только переключатель, для которого вы можете скомпилировать таблицы переходов на основе фиксированного значения.
Если эффективность важнее размера кода, то да, вам следует создать избыточные процедуры. Оператор case - это одна из вещей с меньшими накладными расходами, которую вы можете сделать в C, но она не равна нулю - она должна ветвиться в зависимости от режима, и поэтому это займет время. Если вам действительно нужна максимальная производительность, исключите случай из цикла, даже за счет дублирования цикла.
По сравнению с вычислениями, которые вы выполняете в цикле, накладные расходы на коммутатор, вероятно, будут минимальными. Сказав это, единственный способ быть уверенным - это создать разные версии для двух разных подходов и рассчитать их время.
Это, вероятно, будет зависеть от того, насколько хорош ваш предсказатель ветвления вашего процессора и как ваш компилятор генерирует код для переключателя. Для такого небольшого количества случаев он может сгенерировать дерево решений, и в этом случае обычное предсказание ветвления ЦП должно иметь возможность удалить большую часть накладных расходов. Все могло бы быть немного хуже, если бы он сгенерировал таблицу переключения ...
Тем не менее, лучший способ узнать - это профилировать его и посмотреть.