Здравствуйте, Skorodum, Вы писали:
G>>И сходу хочется объяснить постановку задачи "придурью интервьювера" G>>А вот если сказать "операция критична по времени" — все сразу ясно. S>Да не ясно. Еще большой вопрос будет ли сдвиг эффективнее. А вот запрет на умножение прямо говорит про сдвиг. S>Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.
Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.
Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.
Что такое адресация внутри байта? чтобы выполнить сдвиг — навиг не нужно ничего адресовать внутри байта. Это атомарная операция. Одна инструкция процессора. Разве нет?
Сдвиги на практике нужны именно что из-за скорости.
А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.
Здравствуйте, Тёмчик, Вы писали:
N>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица? Тё>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.
А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).
С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
Здравствуйте, Nuzhny, Вы писали:
N>>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица? Тё>>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.
N>А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).
Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.
N>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.
Здравствуйте, Skorodum, Вы писали:
I>>Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость. S>Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло
"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне. Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора. А умножение и сдвиг до сих пор отличаются по производительности, как то так.
Здравствуйте, sergey2b, Вы писали:
S>Здравствуйте, Тёмчик, Вы писали: S>Это задачка из К и Р S>И человек знающий про обратную польскую Наталию решит ее за недолго
Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Здравствуйте, Тёмчик, Вы писали:
Тё>Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.
Пример чего? Я уже несколько раз намекал, что аффинное преобразование — это оверкилл. Ты никак не можешь этого понять.
Тё>Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.
Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.
Призываю посчитать, сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл? Если мы будем пачками обрабатывать многопегапиксельные снимки, то вообще туши свет — я лично обвиню тебя в ускорении приближения глобального потепления.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Что такое "в повседневной работе"? По десять раз на дню? SVZ>У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo. SVZ>Использовались для хранения полигонов, проводников на печатной плате. SVZ>При объединении пары списков один из них нужно развернуть.
Зачем?
Здравствуйте, Gradiens, Вы писали:
G>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.
Речь про то, что оптимизатор может превратить умножение/деление в сдвиг. Уже много лет как. И он это 100% сделает в вслучае x * 80.
Это тривиальнейшая оптимизация реализованная много лет назад. Если собеседующий этого не знает...
G>Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.
Да нет никаких веских причин. Собеседующий прочитал задачку в интернете вот и все причины.
G>Что такое адресация внутри байта?
Обращение к битам
G>Сдвиги на практике нужны именно что из-за скорости.
Нет. Компиляторы уже умеют это делать сами лет дцать как.
G>А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.
Битовые операции используются, чтобы один байт памяти использовался для хранения 8 (*) бит информации, а не одного.
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, sergey2b, Вы писали:
S>>Здравствуйте, Тёмчик, Вы писали: S>>Это задачка из К и Р S>>И человек знающий про обратную польскую Наталию решит ее за недолго
BFE>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
А какие операции доступны и можно ли использовать скобки в выражениях
Здравствуйте, xarcass, Вы писали:
S>>несколько хороших задачь которымиможно заменить разоворот списка
X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать. X> странное дело, но мало кто может решить из тех, с кем я сталкивался
Заполняем константный массив размером 80xRows числами от 0 до 79 и потом, по смещению в массиве получаем смещение знакоместа в видеопамяти. Но вы ведь не этого ждали, правда?
X>2. Повернуть прямоугольную картинку на произвольный угол (без сглаживания). Для простоты допустить, что 1 пиксель — 1 байт.
Здравствуйте, Nuzhny, Вы писали:
N>Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.
Не 3x3 на 3x1, а 2x2 на 2x1.
N>Призываю посчитать,
Призываю расписать здесь операции для поворота, основанные на школьных тригонометрических знаниях.
Как быстро будем считать гипотенузу, или можно сразу повернуть тангенс?
N> сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл? Если мы будем пачками обрабатывать многопегапиксельные снимки, то вообще туши свет — я лично обвиню тебя в ускорении приближения глобального потепления.
А разве алгоритмическая сложность не C * O(N)? Умножаем матрицу на каждую координату (0..N-1), N раз.
Здравствуйте, sergey2b, Вы писали:
S>>>Здравствуйте, Тёмчик, Вы писали: S>>>Это задачка из К и Р S>>>И человек знающий про обратную польскую Наталию решит ее за недолго
BFE>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано. S>А какие операции доступны и можно ли использовать скобки в выражениях
Числа только в десятичной системе исчисления?
Здравствуйте, Ikemefula, Вы писали:
I>"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне.
Неплохо было бы подтвердить свои слова. Найдите компилятор и целевую архитектуру, когда x*80 не будут разложены на сдвиг и сложение.
I>Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора.
Джытами не пользуюсь, но вот что мне гугл дает:
There’s effectively zero difference between using division versus a shift with numbers this small. Those are nanoseconds, after all. Using a negative number shows no difference in the result.
With this we can now definitely say that replacing value / 2 with value >> 1 offers no benefit. Stop doing it for arithmetic operations and reserve it only for strictly bitwise things!
I>А умножение и сдвиг до сих пор отличаются по производительности, как то так.
Код и бенчмарк в студию.
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, sergey2b, Вы писали:
S>>>>Здравствуйте, Тёмчик, Вы писали: S>>>>Это задачка из К и Р S>>>>И человек знающий про обратную польскую Наталию решит ее за недолго
BFE>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано. S>>А какие операции доступны и можно ли использовать скобки в выражениях BFE>Числа только в десятичной системе исчисления?
Здравствуйте, B0FEE664, Вы писали:
SVZ>>У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo. SVZ>>Использовались для хранения полигонов, проводников на печатной плате. SVZ>>При объединении пары списков один из них нужно развернуть.
BFE>Зачем?
Чтобы из двух получить один, сохранив форму.
K
o---+L
|
|
|
M+-------+N
|
|
\|/
o Z
/|\
|
|
|
R+---------o P
Была дорожка K-L-M-N-Z, нарисовали еще одну дорожку P-R-Z.
В точке Z нужно обе дорожки объединить в одну. Для этого одну из них необходимо развернуть.
На выходе должно получиться либо K-L-M-N-Z-R-P, либо P-R-Z-N-M-L-K.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, B0FEE664, Вы писали:
BFE>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная. Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
Здравствуйте, CreatorCray, Вы писали:
X>>Если представить, что у нас есть просто массив байтов (условно двумерный), то для того, чтобы его попиксельно повернуть достаточно базовых знаний тригонометрии. CC>Если делать в лоб то будут глюки типа tearing.
