Здравствуйте, IID, Вы писали:

CC>>Если делать в лоб то будут глюки типа tearing.

IID>tearing то откуда возьмётся ?

Так CC у нас — признанный эксперт. Хотя, может он так стебётся над автором задачки.

Здравствуйте, B0FEE664, Вы писали:

X>>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

BFE>Без искажений эта задача не имеет решения.

Картинка на пиксельном мониторе — это уже искажения
Хинт — у тебя вращение текстурированной херни протестов не вызывает ?

Здравствуйте, Тёмчик, Вы писали:

Тё>Не 3x3 на 3x1, а 2x2 на 2x1.
Тогда это не аффинное преобразование по определению.

Тё>А разве алгоритмическая сложность не C * O(N)? Умножаем матрицу на каждую координату (0..N-1), N раз.
Ну, да. Но константа для аффинного преобразования будет больше раз в... 10!

Здравствуйте, IID, Вы писали:

Тё>>Нужно аффинное преобразование. А это умножение матриц. Быстро умножать матрицы- отдельная, большая (больная) тема.

IID>не нужно там ничего умножать

Эээээ давай своё решение. Там в условии произвольный угол.

Здравствуйте, Nuzhny, Вы писали:

Здравствуйте, xarcass, Вы писали:

X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.

Очень просто.
Обходим попиксельно destination буфер.
Для смещений по X к координатам источника добавляем (сos;sin).
Для смещений по Y -//- (sin;cos).
Всё!
Если домножить на коэффициет (масштаб) — то ещё увеличиваться и уменьшаться будет. Если возвращать источник с обратной стороны при выходе за границу — то с эффектом "мозаики".

Можно в fixed point если регистров и скорости хватает.
Можно в целых, если развернуть цикл, и добавление заменить инкрементами в тех случаях, когда накопленная дробная часть округляется до целого (но это не позволит сильно играть с сильным уменьшением масштаба, начнутся проскоки на более чем 1 пиксель).

Крутили такое на 8 битах при 3,5мгц, при этом ещё ухитряясь синхриться с развёрткой луча на ЭЛТ, увеличивая цветовое разрешение вдвое.

Пруф (с 2:34):
https://youtu.be/dl3wWxJmIZw?t=154

А вот в VGA для 386 (с 4:42)
https://youtu.be/rFv7mHTf0nA?t=282

Здравствуйте, Тёмчик, Вы писали:

Тё>Эээээ давай своё решение. Там в условии произвольный угол.

тут

Автор: IID
Дата: 06.10.20

Здравствуйте, Тёмчик, Вы писали:

N>>Тогда это не аффинное преобразование по определению.
Тё>Да что ты. Пространство ведь 2-мерное. Не хромает ли твоя математика?

Неа. Попробуй своей аффинной матрицей в 2D пространстве задать сдвиг, поворот и масштаб. Если получится — снимаю шляпу и всячески превозношу твой профессионализм.

Тё>Ты это, давай выкладывай свои катеты с гипотенузами, и посчитаем количество операций. Как там будут квадраты и корни квадратные считаться, да ещё и только в целых числах (!).

Эээ, нет. Там вообще никаких катетов не будет.

Здравствуйте, Nuzhny, Вы писали:

N>Эээ, нет. Там вообще никаких катетов не будет.

Блин, после поста IID я таки нагуглил ответ. Эту хрень можно знать, если однажды её сделал.

s = sin(90 - angle);
c = cos(90 - angle);
w2 = width / 2;
h2 = height / 2;

for (i=0..N-1) {
  newX[i] = (X[i] - w2) * c - (Y[i] - h2) * s + w2;
  newY[i] = (X[i] - w2) * s + (Y[i] - h2) * c + h2;
}

Здравствуйте, Skorodum, Вы писали:

I>>"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне.
S>Неплохо было бы подтвердить свои слова. Найдите компилятор и целевую архитектуру, когда x*80 не будут разложены на сдвиг и сложение.

Для примера, в Атоме сдвиг это 1 такт, умножение 3..6 тактов, div — 9..41. https://software.intel.com/content/dam/develop/public/us/en/documents/intel-atom-tremont-microarchitecture-throughput-and-latency.pdf
В микроконтроллерах всяких дело будет еще хуже.

То есть, выиграть есть где. На счет компилера трудновато будет, я как то давно отошел от таких дел.

Здравствуйте, Тёмчик, Вы писали:

Тё>Эту хрень можно знать, если однажды её сделал.

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

Здравствуйте, Ikemefula, Вы писали:

I>Для примера, в Атоме сдвиг это 1 такт, умножение 3..6 тактов, div — 9..41. https://software.intel.com/content/dam/develop/public/us/en/documents/intel-atom-tremont-microarchitecture-throughput-and-latency.pdf
Прекрасно, только это ровно ничего не доказывает, т.к. разговор не про то, что в процессоре умножение/деление более дорогая операция чем сдвиг, а про то, что в программе нет смысла заменять умножение на константу на сдвиг.

I>В микроконтроллерах всяких дело будет еще хуже.
Может, но к обсуждаемому случаю это вообще никак не относится.

I>То есть, выиграть есть где.
Конечно есть: если писать на ассемблере. А так нет.
Более того, это намного хуже читается.

I>На счет компилера трудновато будет, я как то давно отошел от таких дел.
Давно это когда? В 2010 это точно уже было в gcc.

Хорошая иллюстрация, что с вопросами на собеседовании надо быть аккуратнее (да, это не вы этот вопрос предложили).

Здравствуйте, IID, Вы писали:

IID>необязательно именно ее. Афинное текстурировние (а я его тоже упоминал) более общий случай той же самой задачи. И та же самая реализация — растеризатор заполняет построчно пиксели, шарясь по байтам текстуры.

Т.е. по сути нужно разобраться в видах растеризаторов. Мне не довелось с этим сталкиваться. Поигрался немного с 3D для чартов и отсечением невидимых граней (была идея получить векторную картинку для печати) и забросил. В 2004-2005г это было. Насколько оно у меня тормозило вручную на CPU, настолько летало в OpenGL.

Здравствуйте, Skorodum, Вы писали:

S>Прекрасно, только это ровно ничего не доказывает, т.к. разговор не про то, что в процессоре умножение/деление более дорогая операция чем сдвиг, а про то, что в программе нет смысла заменять умножение на константу на сдвиг.

I>>В микроконтроллерах всяких дело будет еще хуже.
S>Может, но к обсуждаемому случаю это вообще никак не относится.

Не надо передёргивать — просто утверждение без конкретики.

I>>То есть, выиграть есть где.
S>Конечно есть: если писать на ассемблере. А так нет.

Ты точно в курсе, что все джыты всех языков сделают лучше? А если микроконтроллер?

I>>На счет компилера трудновато будет, я как то давно отошел от таких дел.
S>Давно это когда? В 2010 это точно уже было в gcc.

Цитирую себя "не все ведь к С++ сводится"

IID>Очень просто.
IID>Обходим попиксельно destination буфер.

Про это и задача. Тут то и нюанс. Многие начинают обходить source буфер. И всё — приплыли.

Здравствуйте, sergey2b, Вы писали:

S>несколько хороших задачь которымиможно заменить разоворот списка
Проще можно. На собеседовании предлагаешь кандидату поднять штангу. Поднимет больше 150 килограмм — это сильный программист, сеньер — берем. Поднимет 100 килограмм — это средний программист, много денег не дадим. Пожнимет килограмм 70 — это юниор, этого на стажера в лучшем случае и платить чтоб с голоду не умер. А кто меньше поднимет — это не программисты!

И главное, такое собеседование занимает несколько минут, и можно сравнивать кандидатов! Плохо что удаленно не получится собеседовать, а удаленно кандидат может надувные блины поставить. Ну удаленно можно заставить подтягиваться. Подтянется раз 30 на одной руке — сеньер. 30 раз просто — средний. Подтянулся раз 10 — это юниор, только на стажера потянет.

А то списки какие то, задачки. Совсем собеседовать не умеют, ужас!

S>Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.

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

Здравствуйте, Тёмчик, Вы писали:

BFE>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Тё>Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная.

Ага. И всё это расписать прямо на доске.

Тё>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
Интересные новости про условия задачи!

Здравствуйте, IID, Вы писали:

X>>>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.
BFE>>Без искажений эта задача не имеет решения.

IID>Картинка на пиксельном мониторе — это уже искажения
Если картинка пиксельная, то какие искажения?

IID>Хинт — у тебя вращение текстурированной херни протестов не вызывает ?
Вызывает.

Здравствуйте, Ikemefula, Вы писали:

I>А если микроконтроллер?
Тогда надо добавить в исходные условия: "есть микроконтроллеи и JIT где операция умножения дорогая и не оптимизируется...".
Иначе такие вопросы больше говорят о квалификации того, кто их задает.

S>>Давно это когда? В 2010 это точно уже было в gcc.
I>Цитирую себя "не все ведь к С++ сводится"
Gnu Compiler Collection...