Re[4]: чем заменить задачу по развороту списка
От: Gradiens  
Дата: 06.10.20 10:38
Оценка:
Здравствуйте, Skorodum, Вы писали:

G>>И сходу хочется объяснить постановку задачи "придурью интервьювера"

G>>А вот если сказать "операция критична по времени" — все сразу ясно.
S>Да не ясно. Еще большой вопрос будет ли сдвиг эффективнее. А вот запрет на умножение прямо говорит про сдвиг.
S>Все эти сдвиги на практике нужны в первую очередь не для скорости, а для адресации внутри байта, когда есть серьезные ограничения по памяти.

Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.

Что такое адресация внутри байта? чтобы выполнить сдвиг — навиг не нужно ничего адресовать внутри байта. Это атомарная операция. Одна инструкция процессора. Разве нет?

Сдвиги на практике нужны именно что из-за скорости.
А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.
Re[10]: чем заменить задачу по развороту списка
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 06.10.20 10:41
Оценка: +1
Здравствуйте, Тёмчик, Вы писали:

N>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?

Тё>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).
С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.
Re[11]: чем заменить задачу по развороту списка
От: Тёмчик Австралия жж
Дата: 06.10.20 10:57
Оценка: :))
Здравствуйте, Nuzhny, Вы писали:

N>>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?

Тё>>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

N>А как будет выглядеть эта матрица? Вполне может быть так, что для оптимального решения тебе не понядобятся ни матрицы, ни вектора, а простая школьная тригонометрия даст результат и лучше и быстрее, да ещё и в целых числах (что круто, если это не на видеокарте делать).

Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.

N>С такими ответами, как "применить афинное преобразование" для поворота картинки ты пролетишь, как не умеющий размышлять, а лишь применять типовые решения.


Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.
Re[9]: чем заменить задачу по развороту списка
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 06.10.20 10:59
Оценка: +2 -1
Здравствуйте, Skorodum, Вы писали:

I>>Битовые операции никакая не мутота. Оптимизации, протоколы, низкоуровневая работа с данными, системные функции — это неполный список того, где битовые операции не редкость.

S>Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло

"Современных процессоров" довольно большое количество и устроены сильно по разному, соответсвенно качество компиляторов далеко не всегда не высшем уровне. Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора. А умножение и сдвиг до сих пор отличаются по производительности, как то так.
Re[3]: чем заменить задачу по развороту списка
От: B0FEE664  
Дата: 06.10.20 11:07
Оценка:
Здравствуйте, sergey2b, Вы писали:

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

S>Это задачка из К и Р
S>И человек знающий про обратную польскую Наталию решит ее за недолго

Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
И каждый день — без права на ошибку...
Re[12]: чем заменить задачу по развороту списка
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 06.10.20 11:19
Оценка: +1
Здравствуйте, Тёмчик, Вы писали:

Тё>Давай пример. Целых чисел там не будет, только fixed float можно попробовать для ускорения.


Пример чего? Я уже несколько раз намекал, что аффинное преобразование — это оверкилл. Ты никак не можешь этого понять.

Тё>Матрица поворота — частный случай или составная часть матрицы афинного преобразования. Видишь, я не занимался этим 15 лет, но попал в точку. А ты готов изобретать велосипед.


Я не готов изобретать велосипед, потому что никакого велосипеда тут нет. Никто в здравом уме не будет поворачивать картинку аффинным преобразованием. Если это надо делать быстро на CPU, то умножение матрицы (3х3) на вектор (3х1) будет слишком медленным, когда можно сделать в несколько раз быстрее (в целых числах в том числе). Если же на GPU, то float, но тоже не умножением матриц.
Призываю посчитать, сколько операций надо для поворота картинки, а сколько для аффинного преобразования: в аффинном случае у тебя для каждого пикселя будет 4 лишних умножения на 0, 3 лишних умножения на 1, 4 лишних операции сложения. Не оверкилл? Если мы будем пачками обрабатывать многопегапиксельные снимки, то вообще туши свет — я лично обвиню тебя в ускорении приближения глобального потепления.
Re[6]: чем заменить задачу по развороту списка
От: B0FEE664  
Дата: 06.10.20 11:22
Оценка:
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Что такое "в повседневной работе"? По десять раз на дню?

SVZ>У нас в программе использовались односвязные списки. На основе стандартного вектора, с хранением удаленных элементов, с поддержкой Undo/Redo.
SVZ>Использовались для хранения полигонов, проводников на печатной плате.
SVZ>При объединении пары списков один из них нужно развернуть.
Зачем?
И каждый день — без права на ошибку...
Re[5]: чем заменить задачу по развороту списка
От: Skorodum Россия  
Дата: 06.10.20 11:25
Оценка:
Здравствуйте, Gradiens, Вы писали:

G>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

Речь про то, что оптимизатор может превратить умножение/деление в сдвиг. Уже много лет как. И он это 100% сделает в вслучае x * 80.
Это тривиальнейшая оптимизация реализованная много лет назад. Если собеседующий этого не знает...

G>Запрет на умножение говорит... хз что он говорит, но любые запреты без объяснения причин — дорога в ад.

Да нет никаких веских причин. Собеседующий прочитал задачку в интернете вот и все причины.

G>Что такое адресация внутри байта?

Обращение к битам

G>Сдвиги на практике нужны именно что из-за скорости.

Нет. Компиляторы уже умеют это делать сами лет дцать как.

G>А какая память расходуется при умножении? Лично я не вижу, где там перерасход по сравнению со сдвигом.

Битовые операции используются, чтобы один байт памяти использовался для хранения 8 (*) бит информации, а не одного.

* байт бывает и не 8 бит.
Re[4]: чем заменить задачу по развороту списка
От: sergey2b ЮАР  
Дата: 06.10.20 11:29
Оценка: :)
Здравствуйте, B0FEE664, Вы писали:

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


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

S>>Это задачка из К и Р
S>>И человек знающий про обратную польскую Наталию решит ее за недолго

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



А какие операции доступны и можно ли использовать скобки в выражениях
Re[2]: чем заменить задачу по развороту списка
От: B0FEE664  
Дата: 06.10.20 11:35
Оценка:
Здравствуйте, xarcass, Вы писали:

S>>несколько хороших задачь которымиможно заменить разоворот списка


X>1. Найти смещение знакоместа в видеопамяти (для текстового режима — так проще). Количество знакомест в строке — константа (скажем, 80). Одно знакоместо — один байт. Операцию умножения — не использовать.

X> странное дело, но мало кто может решить из тех, с кем я сталкивался

Заполняем константный массив размером 80xRows числами от 0 до 79 и потом, по смещению в массиве получаем смещение знакоместа в видеопамяти. Но вы ведь не этого ждали, правда?

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


Без искажений эта задача не имеет решения.
И каждый день — без права на ошибку...
Re[13]: чем заменить задачу по развороту списка
От: Тёмчик Австралия жж
Дата: 06.10.20 11:37
Оценка: :)
Здравствуйте, 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 раз.
Re[5]: чем заменить задачу по развороту списка
От: B0FEE664  
Дата: 06.10.20 11:39
Оценка:
Здравствуйте, sergey2b, Вы писали:

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

S>>>Это задачка из К и Р
S>>>И человек знающий про обратную польскую Наталию решит ее за недолго

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

S>А какие операции доступны и можно ли использовать скобки в выражениях
Числа только в десятичной системе исчисления?
И каждый день — без права на ошибку...
Re[10]: чем заменить задачу по развороту списка
От: Skorodum Россия  
Дата: 06.10.20 11:40
Оценка:
Здравствуйте, 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>А умножение и сдвиг до сих пор отличаются по производительности, как то так.

Код и бенчмарк в студию.
Re[6]: чем заменить задачу по развороту списка
От: sergey2b ЮАР  
Дата: 06.10.20 11:43
Оценка:
Здравствуйте, B0FEE664, Вы писали:

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


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

S>>>>Это задачка из К и Р
S>>>>И человек знающий про обратную польскую Наталию решит ее за недолго

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

S>>А какие операции доступны и можно ли использовать скобки в выражениях
BFE>Числа только в десятичной системе исчисления?

В восьмеричной шестначтиричной или двоичной
Re[4]: чем заменить задачу по развороту списка
От: wraithik Россия  
Дата: 06.10.20 11:45
Оценка:
Здравствуйте, xarcass, Вы писали:

vsb>>Константа произвольно задаваемая, или 80?


X>Конечно любая — можно даже нечётную. Смысл не меняется.


vsb>>offset = row * 80 + col. row * 80 = row * 64 + row * 16 = row << 6 + row << 4. Такой алгоритм предполагается?


X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.


Было две мысли:
1. Цикл. Тут хотя бы можно в любой момент менять ширину.
2. Использовать сдвиг.

Оба варианта изврат.
Была еще мысль №0 — вопрос какой то дебильный, пора валить.

Интересно, почему мониторы были 80*25, а не 64*32 или 128*32.... Сдвиг вроде быстрее.
Re[7]: чем заменить задачу по развороту списка
От: Stanislav V. Zudin Россия  
Дата: 06.10.20 11:46
Оценка: 7 (2)
Здравствуйте, 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
Re[4]: чем заменить задачу по развороту списка
От: Тёмчик Австралия жж
Дата: 06.10.20 11:49
Оценка:
Здравствуйте, B0FEE664, Вы писали:

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


Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная. Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
Re[5]: чем заменить задачу по развороту списка
От: IID Россия  
Дата: 06.10.20 11:55
Оценка: +1 :)
Здравствуйте, Pzz, Вы писали:

Pzz>Кто на 8080 не программировал, те и буксуют.


кто программировал синклер графику, разбивают себе лицо фейспалмом
kalsarikännit
Re[6]: чем заменить задачу по развороту списка
От: IID Россия  
Дата: 06.10.20 11:57
Оценка:
Здравствуйте, CreatorCray, Вы писали:

X>>Если представить, что у нас есть просто массив байтов (условно двумерный), то для того, чтобы его попиксельно повернуть достаточно базовых знаний тригонометрии.

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

tearing то откуда возьмётся ?
kalsarikännit
Re[8]: чем заменить задачу по развороту списка
От: IID Россия  
Дата: 06.10.20 11:57
Оценка: +1
Здравствуйте, Тёмчик, Вы писали:

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


не нужно там ничего умножать
kalsarikännit
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.