Чтобы работало быстрее, можно применить shl/shr (у них тоже есть форма mem, const), но там будет больше инструкций (т.к. развилками в коде придется реализовывать ветки по 0 и 1).
Здравствуйте, SkyDance, Вы писали:
SD>Но вы вообще правы — даже dec использует регистр (flags сей регистр зовется).
опс, забыл упомянуть, что по условию задачи, регистр флагов использовать разрешалось. нельзя было использовать стек и другую память (кроме переменных, которые мы сравниваем). самомодификация кода, которую предложили на васме, (записать cmp [a],0x0 и скопировать b вместо константы) формально условиям задачи не противоречит, но я бы не взялся писать его в условиях ограниченного времени, да и на ум оно мне вообще не пришло. я конкретно ступил.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали: М>на все это (с размышлениями) ушло даже меньше 90 секунд. у них было другое решение, но по скорости сопоставимое с моим.
можно по битам скакать. 0ый бит взведен — jump туда, там проверяем что бит тоже взведен. если нет — не равны. тогда время константное
Здравствуйте, SkyDance, Вы писали:
SD>Я приехал в Австралию с 7.5 по speaking. Меня спасла только 9-ки по reading и listening, настолько в первое время было сложно понимать тот миллион диалектов и акцентов, с которым пришлось столкнуться. Тот английский, который в фильмах, или, хуже того, на IELTS, к "жизненному" английскому отношения почти не имеет. Хотя бы потому, что говорят в фильмах с артикуляцией и жестикуляцией. И обычно не с набитым ртом.
SD>Первые пару недель я вообще не понимал, что у меня спрашивают всякие обслуживающие азиаты (в кафешках и прочих забегаловках). Хорошо, на работе только белые (и в основном из Англии и ЮАР), их я понимаю с первого раза и на 100%.
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, мыщъх, Вы писали:
М>>на все это (с размышлениями) ушло даже меньше 90 секунд. E>Нда. Крут немеряно, либо долго тренировался такие задачи решать.
это было в те далекие времена, когда я активно искал работу за рубежом и к телефонным собеседованиям привык настолько, что, прижимая трубку к уху, даже не отрывался от текущей работы. там и не такие задачки были. вообще я от природы тугодум и предпочитаю все обстоятельно взвесить и обдумать, но... пришлось в том числе и решать задачи на скорость. так что вы совершенно правы на счет "натренировался".
> Но вообще — лучше уж гномики, чем такие задачи.
да что тут сложного-то? базовый асм.
> А когда думаешь в этом направлении, додуматься декремент целого числа > делать крайне тяжело, тем более на практике такое никогда в жизни делать не будешь.
с этим согласен. с другой стороны -- работодатели (если не ошибаюсь -- японцы, но могу соврать) были уверены, что такое в гугле я не найду. интервью же удаленное. кто знает, что я там делаю?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, SkyDance, Вы писали:
D>>Итог таков: D>>1) Английский не очень важен, главное пройти собеседование. D>>2) Чтобы его знать, нужно заниматься самому. Страна большой роли не играет.
SD>Пункт 1 верный, пункта 2 — опционально. Фильмы, сериалы, радио, речь — чтобы побольше было английского. И все, дело пойдет. Ах да, еще очень важно _МНОГО_ писать самому. И говорить самому. А то будешь как та самая собака, которая все понимает, но ответить ничего не может.
Ты сказал тоже самое, что написано у меня.
Здравствуйте, Nuzik, Вы писали:
N>Здравствуйте, мыщъх, Вы писали:
М>>я решил но неоптимально. очень даже тупо решил.
N>По-моему, классное решение, я сразу именно его придумал.
N>А что, помимо самомодификации, является оптимальным решением?
коллега ответил тут: http://www.rsdn.ru/forum/NewMsg.aspx?mid=4655725
но решений много. вот почему у меня dec? почему не inc? наверное потому, что мне кажется, что хотя бы одно из чисел будет маленьким. а если анализировать флаги более детально?
позже до меня дошло, что я лабух, баклан и шлемаз и что более быстродействующее решение может выглядеть так:
l1:
sub [a], 100h
jb l2
sub [b], 100h
jae l1
jmp l3
l2:
sub [b], 100h
l3:
; // а тут мы проверяем цикла как раньше, только делаем inc, вместо dec
тут идея -- отнимать большими кусками пока не получим заем. а как получим заем -- применяем старый трюк с пошаговым увеличением. в этом случае макс. кол-во шагов равно: (2^n)/step_size+step_size. кстати, за 90 сек. со своим знанием математики я не решу эту задачу -- как найти наилучший step_size (n — разрядность ячейки памяти, в данном случае 32). я даже примерно не представляю как это решается (исключая построение графиков).
кстати, тут есть небольшая багафича. если сравнивать нули, то алгоритм сработает, но стормозит. и потому перед началом сравнения желательно дать inc/dec -- для быстрой проверки на нуль. ибо если у нас изначально был ноль, то мы прогоним все 32 разряда пока снова достигнем его. а ноль вполне вероятен во входных данных.
так что задачка интересная. она из немногих из того что запомнилось.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, мыщъх, Вы писали: М>>на все это (с размышлениями) ушло даже меньше 90 секунд. у них было другое решение, но по скорости сопоставимое с моим. __>можно по битам скакать. 0ый бит взведен — jump туда, там проверяем что бит тоже взведен. если нет — не равны. тогда время константное мне нравится ваша идея. а за 90 секунд код успеете написать? хорошо, что я пользуюсь far+colorer и мне за 90 секунд и написать и проверить можно. а так приходится писать прямо в окне чата.
если я правильно понял, вы предлагаете делать
test ..., (1<<0)
test ..., (1<<1)
test ..., (1<<2)
test ..., (1<<3)
но это ж очень много кода писать... хотя на макросах, вероятно, можно и успеть, т.к. тут шаблон главное задать.
ЗЫ. может это в этюды? смотрите сколько уже решений.
1) тупой dec
2) тупой dec с быстрой проверкой на ноль
3) вычитание большими кусками и переходом на подпрограмму (1) при флаге заема
4) само модификация
5) shl/shr от SkyDance
6) битовые скачки от вас
подозреваю, что это не предел и возможных решений даже больше.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
М> мне нравится ваша идея. а за 90 секунд код успеете написать? хорошо, что я пользуюсь far+colorer и мне за 90 секунд и написать и проверить можно. а так приходится писать прямо в окне чата.
Код на test/jump будет медленнее, т.к. процессору весь TLB поломает. А если это еще и на Pentium 4 выполнить — столько пенальти наберешь, что слово "производительность" будет неприменимо.
"Вычитание большими кусками" в своем пределе дойдет до binary partitioning и посему будет полностью повторять shr/shr, но выполняться будет медленнее (т.к. команды с константами — большие, декодеру неприятно их читать )
М>подозреваю, что это не предел и возможных решений даже больше.
По-любому. Надо просто посмотреть, что там вообще есть в списке команд современных x86 (а то и AMD64). Не удивлюсь, если среди каких-нибудь SSE4 найдется нужная команда. Надо ж понимать, SIMD (single instruction multiple data) для того и задуман, чтобы в один опкод поставлять более одной адресуемой ячейки памяти.
Здравствуйте, SkyDance, Вы писали:
М>> мне нравится ваша идея. а за 90 секунд код успеете написать? хорошо, что я пользуюсь far+colorer и мне за 90 секунд и написать и проверить можно. а так приходится писать прямо в окне чата.
SD>Код на test/jump будет медленнее, т.к. процессору весь TLB поломает. А если это еще и на Pentium 4 выполнить — столько пенальти наберешь, что слово "производительность" будет неприменимо.
ну тут по любому сравнение будет тормозить. особенно если числа 64 бит будут на x86-64. вот если бы сказали, что числа 8 бит -- это другое дело.
SD>"Вычитание большими кусками" в своем пределе дойдет до binary partitioning и посему будет полностью повторять shr/shr,
с вычитанием тонкость есть. на первом же шаге мы можем сказать -- если одно из чисел меньше step или же сумма числа со step превышает 32 бита. и тогда мы будем знать куда выгоднее крутить.
> но выполняться будет медленнее (т.к. команды с константами — большие, декодеру неприятно их читать )
с этим -- согласен, но shr/shr я не так часто использую чтобы сразу написать без ошибок. это же не просто этюд. это же блиц-крик.
М>>подозреваю, что это не предел и возможных решений даже больше. SD>По-любому. Надо просто посмотреть, что там вообще есть в списке команд современных x86 (а то и AMD64).
так что -- голосую за этюды
> Не удивлюсь, если среди каких-нибудь SSE4 найдется нужная команда.
не уверен, что у них будет команда не трогающая никаких регистров кроме регистра флагов...
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
М>с вычитанием тонкость есть. на первом же шаге мы можем сказать -- если одно из чисел меньше step или же сумма числа со step превышает 32 бита. и тогда мы будем знать куда выгоднее крутить.
Тогда это уже не sub, а add, и можно анализировать два флага (второй — overflow). Однако, навскидку, это все равно не быстрее shr, поскольку там можно еще и fast exit — как только флаг zero/equals после shr установлен для [a], тупой test [b], 0 будет устанавливать флаг "равно/не равно".
М>не уверен, что у них будет команда не трогающая никаких регистров кроме регистра флагов...
Здравствуйте, Darooma, Вы писали:
D>Я воспринимаю английскую речь на слух, но не очень хорошо. Говорю, но, тоже, не очень. D>Как определить, что моего уровня английского достаточно для того, чтобы искать работу за границей с последующим переездом? Или, хотя бы, как узнать, что я обладаю необходимым минимумом знания английского (разговорного, письменного, все как надо) для этого? А, может, это зависит от конкретной конторы?
Нужно просто разговаривать, не трать время на правильное построение фразы и прочие вещи (сохрани этоn навык для переписки по мылу), носитель языка способен понять почти любое мычание, так же как ты легко можешь понять какого-нибудь Джамшута.
Здравствуйте, мыщъх, Вы писали: М> мне нравится ваша идея. а за 90 секунд код успеете написать? хорошо, что я пользуюсь far+colorer и мне за 90 секунд и написать и проверить можно. а так приходится писать прямо в окне чата.
не, мне нужно минут 10. написать, проверить, замерить скорость
М>если я правильно понял, вы предлагаете делать М>test ..., (1<<0) М>test ..., (1<<1) М>test ..., (1<<2) М>test ..., (1<<3)
вот примерно так:
_start:
test a, 1
jnz _a_is_1
test b, 1
jnz _not_equal
jmp _next
_a_is_1:
test b, 1
jz _not_equal
_next:
shr a, 1
jz _check_shifted_b_is_0
shr b, 1
jmp _start
_check_shifted_b_is_0:
shr b, 1 // test b, 2
jnz _not_equal
//////////////
mov a, 1 // equal
jmp _end
_not_equal:
mov a, 0
_end:
на моем компе работает в среднем за 72 такта для двух случайных 32битных чисел.
изначально я предлагал без цикла делать, но потом понял, что и с циклом можно и вроде бы на скорость не влияет
результат для отладки сохраняется в a. да и не помню я как красиво флаг взвести нужный, чтобы без регистров
а вот кстати решение в два раза быстрее, но работает только для положительных:
_start:
sar a, 1
jb _a_is_1
sar b, 1
jb _not_equal
jmp _next
_a_is_1:
sar b, 1
jae _not_equal
_next:
// flags after b sar 1 state
jz _check_a_is_0
jmp _start
_check_a_is_0:
cmp a, 0
jnz _not_equal
//////////////
mov a, 1 // equal
jmp _end
_not_equal:
mov a, 0
_end:
__>вот примерно так: __>[code] _> shr b, 1 // test b, 2
Не соберется: в asm-е комментарии обозначаются точкой с запятой
__>изначально я предлагал без цикла делать, но потом понял, что и с циклом можно и вроде бы на скорость не влияет
С циклом будет не медленнее, т.к. в данном случае предсказание ветвлений даст максимум 2 пенальти.
Здравствуйте, SkyDance, Вы писали: SD>Не соберется: в asm-е комментарии обозначаются точкой с запятой
я писал во inline-asm'e в студии. там гораздо проще проверить правильность и такие комменты работают
__>>изначально я предлагал без цикла делать, но потом понял, что и с циклом можно и вроде бы на скорость не влияет SD>С циклом будет не медленнее, т.к. в данном случае предсказание ветвлений даст максимум 2 пенальти.
да, и я про то же
Здравствуйте, Darooma, Вы писали:
D>Я воспринимаю английскую речь на слух, но не очень хорошо. Говорю, но, тоже, не очень. D>Как определить, что моего уровня английского достаточно для того, чтобы искать работу за границей с последующим переездом? Или, хотя бы, как узнать, что я обладаю необходимым минимумом знания английского (разговорного, письменного, все как надо) для этого? А, может, это зависит от конкретной конторы?
Я когда-то пытался свалить в Великобританию, там захотели чтобы я прошел тест IELTS, набрал 6 по 10 бальной, т.е. могу разобраться но есть еще до фига учить.
)
