Думаю, мало кто из тех, кто готовится к первому собеседованию, устраиваясь на первую работу в качестве (pre)младшего программиста, ответит на этот вопрос отрицательно.
Или хотя бы усомниться в положительном ответе.
Конечно, такая простая структура данных с прямым доступом по индексу – никаких хитростей! Нет, в некоторых языках вроде JavaScript или PHP массивы, конечно, реализованы очень интересным образом и по сути представляют собой гораздо больше, чем просто массив.
Но речь не об этом, а о «традиционной» реализации массивов в виде «твердой области памяти».
В этом случае на основе индексов и размера одного элемента просто вычисляется адрес и осуществляется доступ к соответствующему значению.
Что в этом такого сложного? Давайте разберемся.
Например, в Java. Попросить ничего не подозревающего кандидата создать массив целых чисел н Икс н .
Человек уверенно пишет что-то вроде:
Большой.int g[][] = new int[n][n];
Теперь мы просим вас чем-нибудь инициализировать элементы массива.
Хоть в единицах, хоть в сумме показателей.
Мы получаем: for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = i + j;
}
}
Они даже пишут чаще for(int i = 0; i < g.length; i++) {
for(int j = 0; j < g[i].
length; j++) {
g[i][j] = i + j;
}
}
что тоже является поводом для разговора, но мы сейчас говорим о другом.
Мы пытаемся узнать, что знает человек, и посмотреть, как он думает. Поэтому обращаем его внимание на то, что значения расположены симметрично и просим экономить на итерациях цикла.
Конечно, зачем перебирать все значения индекса, если можно пройти только по нижнему треугольнику? Субъект обычно легко соглашается и, мудро выделив главную диагональ, аккуратно пишет что-то вроде: for(int i = 0; i < n; i++) {
g[i][i] = 2* i;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = i + j;
}
}
Вместо g[i][i] = 2* i;
часто пишу g[i][i] = i + i;
или g[i][i] = i << 1;
и это тоже повод поговорить.
Но мы пойдем дальше и зададимся ключевым вопросом: Насколько быстрее будет работать программа? .
Обычное рассуждение таково: почти в 2 раза меньше расчетов индексов; почти в 2 раза меньше вычислений значений (суммирование); одинаковое количество заданий.
Это означает, что на 30 процентов быстрее.
Если у человека хорошая математическая подготовка, то можно даже увидеть точное количество сохраненных операций и более аргументированную оценку эффективности оптимизации.
Теперь настало время главного удара.
Мы запускаем обе версии кода на некотором достаточно большом значении н (около нескольких тысяч), например, Так .
Код с контролем времени class A {
public static void main(String[] args) {
int n = 8000;
int g[][] = new int[n][n];
long st, en;
// one
st = System.nanoTime();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nOne time " + (en - st)/1000000.d + " msc");
// two
st = System.nanoTime();
for(int i = 0; i < n; i++) {
g[i][i] = i + i;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = i + j;
}
}
en = System.nanoTime();
System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
}
}
Что мы видим? Оптимизированная версия работает в 10-100 раз медленнее! Теперь самое время понаблюдать за реакцией кандидата на должность.
Какова будет реакция на необычную (точнее обычную в практике разработчика) стрессовую ситуацию.
Если на лице обвиняемого отображается волнение и он начинает нажимать кнопки, на время забыв о вашем существовании, то это хороший знак.
В некоторой степени.
Вы же не хотите нанимать исследователя, которого не волнует результат проекта, не так ли? Тогда не задавайте ему вопрос «ПочемуЭ» Попросите их переработать второй вариант, чтобы он работал быстрее, чем первый.
Теперь вы можете некоторое время спокойно заниматься своими делами.
За полчаса у вас будет достаточно материала, чтобы оценить основные личностные и профессиональные качества претендента.
Кстати, когда я кратко описал эту проблему на своем рабочем сайте, самым популярным комментарием было «Это ваша кривая Java».
Специально для них публикую.
код о Великом и Свободном.
А счастливые обладатели Free Pascal для Windows могут посмотреть под спойлером program Time;
uses
Windows;
var
start, finish, res: int64;
n, i, j: Integer;
g: Array of Array of Integer;
begin
n := 10000;
SetLength(g, n, n);
QueryPerformanceFrequency(res);
QueryPerformanceCounter(start);
for i:=1 to n-1 do
for j:=1 to n-1 do
g[i,j] := i + j;
QueryPerformanceCounter(finish);
writeln('Time by rows:', (finish - start) / res, ' sec' );
QueryPerformanceCounter(start);
for i:=1 to n-1 do
for j:=1 to n-1 do
g[j,i] := i + j;
QueryPerformanceCounter(finish);
writeln('Time by cols:', (finish - start) / res, ' sec' );
end.
В приведенном выше коде на Паскале я убрал «сбивающие с толку» аспекты и оставил только суть проблемы.
Если это можно назвать проблемой.
Какие вопросы мы в конечном итоге задаем ответчику? 1. Почему он работает медленнее? А подробнее.
2. Как сделать инициализацию быстрее? Если есть необходимость поковыряться в реализации Java, то мы просим соискателя соблюдать время выполнения для малых значений.
н .
Например, на ideone.com для n=117 «оптимизированная» версия работает в два раза медленнее.
Но для следующего значения n=118 он оказывается уже в 100 (сто) раз быстрее неоптимизированного! Предложите поэкспериментировать на локальной машине.
Пусть поиграется с настройками.
Кстати, все понимают, что происходит? Несколько слов в оправдание Я хотел бы сказать несколько слов, чтобы оправдать этот метод найма на собеседованиях.
Да, я не проверяю знание синтаксиса языка и знание структур данных.
Возможно, на цивилизованном рынке труда это все работает. Но в наших условиях тотального дефицита квалифицированных кадров нам приходится оценивать скорее долгосрочную адекватность претендента той работе, с которой ему предстоит столкнуться.
Те.
способность учиться, пробиваться, понимать, делать.
По духу это похоже на «собеседование» при вербовке легионеров в Древнем Риме.
Будущий воин сильно испугался и следил, не покраснеет ли он или не побледнеет. Если он побледнел, то в стрессовой ситуации у заявителя отливает кровь от головы и он склонен к пассивной реакции.
Например, обморок.
Если заявитель краснел, то кровь приливала к его голове.
Те.
он склонен к активным действиям и бросается в драки.
Этот посчитали подходящим.
Ну и последнее.
Почему я рассказал всем об этой задаче вместо того, чтобы продолжать использовать ее на собеседованиях? Просто потенциальные претенденты уже «усвоили» эту задачу и вынуждены использовать другие.
Собственно, я обратил внимание на этот эффект именно в связи с реальной задачей обработки изображений.
Ситуация была несколько запутанной и я не сразу понял, почему у меня так сильно упал fps после рефакторинга.
В общем, таких чудесных моментов, наверное, у каждого немало.
Пока что лидирующая версия - виноват кэш процессора.
Те.
последовательный доступ в первом варианте работает внутри хеша, который обновляется при выходе за определенную границу.
При доступе по столбцам хеш вынужден постоянно обновляться и это занимает много времени.
Давайте проверим эту версию в чистом виде.
Давайте создадим массив и сравним, что быстрее — обработать все элементы подряд или обработать элементы массива со случайным числом одинаковое количество раз? Это программа - ideone.com/tMaR2S .
Для 100 000 элементов массива произвольный доступ обычно происходит заметно быстрее.
Что это значит? Тут мне (Big_Lebowski) совершенно справедливо подметили, что перестановка петель меняет результаты в пользу последовательного варианта.
Для чистоты эксперимента пришлось настроить цикл прогрева.
При этом я сделал несколько повторов, чтобы получить среднее время работы, как советовал Левентов.
Получилось вот так ideone.com/yN1H4g .
Те.
Произвольный доступ к элементам большого массива примерно на 10% медленнее последовательного доступа.
Возможно, кэш действительно может сыграть какую-то роль.
Однако в исходной ситуации производительность значительно упала.
Итак, есть что-то еще.
Постепенно лидером становится версия о дополнительных действиях при переходе из одной строки массива в другую.
И это правильно.
Осталось разобраться, что именно там происходит. Теги: #программирование #массивы #память #программирование #java #Алгоритмы
-
Блокчейн Как Структура Данных
19 Oct, 24 -
Интерфейс Игры И С Чем Его Едят
19 Oct, 24 -
Почему Я На Самом Деле Использую Linux?
19 Oct, 24 -
О Питании Внешнего Жесткого Диска
19 Oct, 24 -
Хабра-Люди По Версии Паблика
19 Oct, 24
