Всем привет!
Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

int sum = 0;
for(int i=0; i<2; i++) {
for(int j=0; j<3; j++) {
sum = sum + 1;
}
}


Понятия не имею как ее решить... даже не знаю с чего начать...

Помогите разобраться, плз!

зависит от компилятора. может и 0, если он соптимизирует.

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

M>Всем привет!
M>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}

M>Понятия не имею как ее решить... даже не знаю с чего начать...
M>Помогите разобраться, плз!

Навскидку:
1 Гц означает одно исполнение такого процесса за одну секунду: 1 Гц = 1/с.
Если мы имеем 100 MГц, то это означает, что мы имеем 100*10^6 исполнений такого процесса за одну секунду.
Потом выясняется сколько тактов на сложение и присвоение * 6 (не помню и зависит от CPU). Дальше понятно, 100*10^6 за секунду, а X тактов за искомое время. Пропорция, ответ, апплодисменты

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

M>Всем привет!
M>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}


M>Понятия не имею как ее решить... даже не знаю с чего начать...

M>Помогите разобраться, плз!

100 МГц — 20 млн. коротких операций в секунду.

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

M>Всем привет!
M>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}


M>Понятия не имею как ее решить... даже не знаю с чего начать...

M>Помогите разобраться, плз

Я считаю, что эту задачу при таких исходных данных невозможно решить в принципе.
1. Не известен язык программирования. на котором написан код, следовательно мы не знаем, как он будет транслирован в машинные коды и будет ли он транслирован в них сразу вообще(java).
2. Я не специалист в железе, но по-моему у современных процессоров кроме тактовой частоты есть еще и характеристика количества операций в секунду, которая у разных процессоров соответственно разная. То есть не зная ее мы ничего вычислить не можем.

Задачу можно решить лишь добавив дополнительные условия, описанные выше.

Скорее всего вопрос был задан, чтобы:
1. Посмотреть как ты ее попытаешься решить. Как обычно, проверяют навыки решения проблем вместе с наличием логики и общей эрудиции.
2. Посмотреть, сможешь ли ты прямо сказать, что ее решить нельзя, то есть готов ли ты отстаивать свое мнение.
3. Какие доводы ты приведешь в пользу того, что задачу решить нельзя, то есть

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

M>Всем привет!
M>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}


M>Понятия не имею как ее решить... даже не знаю с чего начать...
M>Помогите разобраться, плз!

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

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

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

M>>Всем привет!
M>>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>>int sum = 0;
M>>for(int i=0; i<2; i++) {
M>> for(int j=0; j<3; j++) {
M>> sum = sum + 1;
M>> }
M>>}


M>>Понятия не имею как ее решить... даже не знаю с чего начать...

M>>Помогите разобраться, плз

H>Я считаю, что эту задачу при таких исходных данных невозможно решить в принципе.
H>1. Не известен язык программирования. на котором написан код, следовательно мы не знаем, как он будет транслирован в машинные коды и будет ли он транслирован в них сразу вообще(java).
H>2. Я не специалист в железе, но по-моему у современных процессоров кроме тактовой частоты есть еще и характеристика количества операций в секунду, которая у разных процессоров соответственно разная. То есть не зная ее мы ничего вычислить не можем.

H>Задачу можно решить лишь добавив дополнительные условия, описанные выше.

H>Скорее всего вопрос был задан, чтобы:
H>1. Посмотреть как ты ее попытаешься решить. Как обычно, проверяют навыки решения проблем вместе с наличием логики и общей эрудиции.
H>2. Посмотреть, сможешь ли ты прямо сказать, что ее решить нельзя, то есть готов ли ты отстаивать свое мнение.
H>3. Какие доводы ты приведешь в пользу того, что задачу решить нельзя, то есть

прошу прощения, не количество операций в секунду, а количество операций за такт

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

M>Всем привет!
M>Несколько дней назад ходил на собеседование и столкнулся с такой задачкой...

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}


M>Понятия не имею как ее решить... даже не знаю с чего начать...

M>Помогите разобраться, плз!

Вариант 1) Для оценки берем модель сферического коня. а) при условии отсутствия оптимизации б) при условии что одна операция ++ выполняется за 1 такт (т.е 10^–8 с) считаем операции инкрементации для i, j, sum и умножаем на время такта.
Вариант 2) более практичный. Смотрим дизассемблированный код и конкретно понимаем как там и что компилятор соптимизировал, таким образом получаем оценку как для такой задачи, так и для группы задач где магические числа 2 и 3 могут варьироваться.
Вариант 3) тупо запускаем и засекаем

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

M>Понятия не имею как ее решить... даже не знаю с чего начать...
На неизвестные условия берутся допущения, эти допущения указываются. Ответ дается с учетом нижней и верхней границы, в ответе могут фигурировать некоторые константы, которые берутся в допущении. Решается слету, не думая, максимум за 5 минут, критерий оценки — чтоб не было явной ахинеи. Если ответ такой устраивать не будет, радуемся, что не попали в контору, где собеседование проводят невменяемые люди, ничего хорошего там не жди.
А вообще, это задачка имеет смысл только для студентов вообще без опыта работы. Если ее дают всем подряд — еще одно подозрение на неадекватность.

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

Ovl>зависит от компилятора. может и 0, если он соптимизирует.

Я бы добавил, что зависит от настроек компилятора. В дебаге он, может, и не станет разворачивать циклы, но в релизе — наверняка развернёт. По крайней мере все основные: msvc, gcc, icc — так сделают, даже bcc — и то догадается

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

M>Сколько времени займет выполнение следующего кода на машине 100Мгц, если предположить, что других задач в это время выполнятся не будет?

M>int sum = 0;
M>for(int i=0; i<2; i++) {
M> for(int j=0; j<3; j++) {
M> sum = sum + 1;
M> }
M>}

Я бы принял такую задачку как тест на умение рассуждать и оценивать.
Ход мыслей примерно следующий.

Если что-то помните от институтского курса ассемблера, то код можно преобразовать к виду (сумма будет в ax):
xor ax, ax
xor ch, ch
lb1: xor cl, cl
lb2: inc ax
inc cl
cmp cl, 3
jne lb2
inc ch
cmp ch, 2
jne lb1

Тупо посчитаем инструкции:
xor 5, inc 27, cmp 15, jmp 15

Зададимся числом тактов на каждую инструкцию вашего абстрактного 100МГц-процессора (не сказали же, какой у вас процессор):
xor: 2, inc: 2, cmp: 5, jmp: 4

Суммируя, получаем ~200 тактов.
Поскольку на 100МГц один такт выполняется за 10^-8 секунд, то наши 200 тактов пролетят за 2 микросекунды — и это ответ.

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

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

B>После этого тема разговора может плавно перейти к поиску недочетов/ошибок в такой оценке, к оптимизации вручную, оптимизации компилятора, про современные процессоры и т.д. Мне кажется, смысл вопроса — узнать вашу эрудицию в этой области, а не получение конкретного ответа.
К чему тогда ассемблер? Во-первых, кто сказал что процессор арихитектуры x86? Зачем вы используете ассемблер, не зная хотя бы марки процессора? Чтобы показать "знания"?
Во-вторых, если так всем хочется считать такты, то хотя бы уточняйте наличие конвеера и как выглядит машинный код того, что непосредстенно пойдет на выполнение. Может там вообще цикла не будет, а будет константа, посчитанная в результате оптимизации?

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

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

M>>Понятия не имею как ее решить... даже не знаю с чего начать...
E>На неизвестные условия берутся допущения, эти допущения указываются. Ответ дается с учетом нижней и верхней границы, в ответе могут фигурировать некоторые константы, которые берутся в допущении. Решается слету, не думая, максимум за 5 минут, критерий оценки — чтоб не было явной ахинеи. Если ответ такой устраивать не будет, радуемся, что не попали в контору, где собеседование проводят невменяемые люди, ничего хорошего там не жди.
E>А вообще, это задачка имеет смысл только для студентов вообще без опыта работы. Если ее дают всем подряд — еще одно подозрение на неадекватность.

Самый прикол в том, что эта задача дается среди прочих во время тестирования... на нее предлжены 4 варианта ответа (все варианты числа без неизвестных), надо выбрать правильный... к сожалению, не помню эти варианты.

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

M>Самый прикол в том, что эта задача дается среди прочих во время тестирования... на нее предлжены 4 варианта ответа (все варианты числа без неизвестных), надо выбрать правильный... к сожалению, не помню эти варианты.
Это явно показывает полную неадекватность собеседующих. Особенно если написал тест, и до свидания, если ответы совпали — говорим типа дальше. Я бы очень поостерегся с такими работать.

T>К чему тогда ассемблер? Во-первых, кто сказал что процессор арихитектуры x86? Зачем вы используете ассемблер, не зная хотя бы марки процессора? Чтобы показать "знания"?
T>Во-вторых, если так всем хочется считать такты, то хотя бы уточняйте наличие конвеера и как выглядит машинный код того, что непосредстенно пойдет на выполнение. Может там вообще цикла не будет, а будет константа, посчитанная в результате оптимизации?

Ну, если после предоставления варианта решения собеседник на меня накинется с такими вопросами, то можно и пободаться

А так — вопрос отпал.
Задача в тестах была, с готовыми вариантами.

Можно отвечать на удачу — это ж тесты!

Здравствуйте, Mihon82, Вы писали:
M>Самый прикол в том, что эта задача дается среди прочих во время тестирования... на нее предлжены 4 варианта ответа (все варианты числа без неизвестных), надо выбрать правильный... к сожалению, не помню эти варианты.
Ну тогда самый надежный вариант — это 0.

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

bxt>Навскидку:
bxt>1 Гц означает одно исполнение такого процесса за одну секунду: 1 Гц = 1/с.
bxt>Если мы имеем 100 MГц, то это означает, что мы имеем 100*10^6 исполнений такого процесса за одну секунду.
bxt>Потом выясняется сколько тактов на сложение и присвоение * 6 (не помню и зависит от CPU). Дальше понятно, 100*10^6 за секунду, а X тактов за искомое время. Пропорция, ответ, апплодисменты

1. разные команды имеют разное время выполнения
2. некоторые команды могут выполняться параллельно, поэтому иногда компилатор подбирает такие сочетания.
3. компилятор может сгенерить абсолютно любой ассембленый код. С члучае с оптимизацией я почти уверен, что он сообще весь результат заменит константой.

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

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

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

M>>>Понятия не имею как ее решить... даже не знаю с чего начать...
E>>На неизвестные условия берутся допущения, эти допущения указываются. Ответ дается с учетом нижней и верхней границы, в ответе могут фигурировать некоторые константы, которые берутся в допущении. Решается слету, не думая, максимум за 5 минут, критерий оценки — чтоб не было явной ахинеи. Если ответ такой устраивать не будет, радуемся, что не попали в контору, где собеседование проводят невменяемые люди, ничего хорошего там не жди.
E>>А вообще, это задачка имеет смысл только для студентов вообще без опыта работы. Если ее дают всем подряд — еще одно подозрение на неадекватность.

M>Самый прикол в том, что эта задача дается среди прочих во время тестирования... на нее предлжены 4 варианта ответа (все варианты числа без неизвестных), надо выбрать правильный... к сожалению, не помню эти варианты.

Ну тогда если вас туда не взяли — вам очень повезло. Сбережоте кучу своего времени и нервов.

Кстати, имя конторы в студию

M>Помогите разобраться, плз!
Надо просто вразуметельно показать знание multithreading/multitasking, основ ассемблера, строения процессора. Плюс оптимизации компилятора итд итп. Ну разве важны здесь реальные ответы — типа 15 мс?
Плюс ты должен показать, что можешь думать.