SG
но я считаю моветоном спрашивать алгоритмы на собеседованиях.
Size: a a a
2020 October 05
K
но нужно знать
K
но я считаю моветоном спрашивать алгоритмы на собеседованиях.
почему? Хороший метод проверить problem solving skills
K
и единственный если у вас 100 человек с одинаковыми знаниями и из которых нужно отобрать 10
SG
скажем так, сегодня гораздо выше ценятся архитектурные навыки, навыки паттернов, навыки, которые позволяют заниматься экстремальным программированием (solid, design patterns, DDD), нежели написание алгоритмов. Никто в большинстве бизнесов не будет заниматься доведением кода до идеала, обычно делается простая версия решения, оборачивается в некую стратегию, потом по ходу заменяется более идеальной реализацией. Сложные вещи обычно можно отложить на потом, если уметь правильно структурировать и организовывать код. Но это лично мое имхо.
AS
Привет, может быть оффтоп, подскажите пожалуйста
Вопрос по кэшу процессора
Есть матрица 100х100 элементов
Два варианта обхода: последовательно по строкам (a)и последовательно по столбцам (b)
Три варианта ответа (T это затраченное время на полный обход):
Ta > Tb
Tb > Ta
Tb = Ta
Вопрос по кэшу процессора
Есть матрица 100х100 элементов
Два варианта обхода: последовательно по строкам (a)и последовательно по столбцам (b)
Три варианта ответа (T это затраченное время на полный обход):
Ta > Tb
Tb > Ta
Tb = Ta
A
второе
A
в обычных случаях матрица просто хранится последовательно в виде 10000 последовательных чисел. При кэшмиссе будет загружаться некоторая непрерывная последовательность байт, следовательно при обходе "по строкам" после одного промаха несколько следующих обращений заведомо будут в кэш
A
при чтении по столбцам при каждом обращении в кеш будет зачитываться кусок строки. Если бы в кеше было место на 100 записей, то ок, но по факту к концу столбца мы уже вытесним из кеша его начало
A
lru cache в этом случае будет совсем печальным, если рандом, то есть надежда
A
... правда тут может быть вопрос что такое "по строкам" и "по столбцам". Я имел в виду, что "по строкам" это по последнему индексу.
A
for (i = 0; i < S1; i++)
for (j = 0; j < S2; j++)
a[i][j];
AS
По строкам имею ввиду
[0][0] -> [0][1]
[0][0] -> [0][1]
A
ага, тогда оно
A
ну то есть когда ты обратишься к a[0][0], то в кеш влетят a[0][1], a[0][2] и так далее, но вряд ли дойдет до a[1][0]
AS
Я правильно понимаю, что при проходе по строке соседние элементы в некотором диапазоне попадут в кеш
А когда идём по столбцу, новый элемент ещё не оказался в кеше, а к тому моменту, когда пойдём новый столбец - уже будет очищено
А когда идём по столбцу, новый элемент ещё не оказался в кеше, а к тому моменту, когда пойдём новый столбец - уже будет очищено
A
да
A
ну или точнее когда идем по столбцу, в кеше оказывается много данных, которые понадобятся нескоро
A
как следствие, там значительно меньше данных, которые все-таки понадобятся, а следовательно чаще кэшмиссы
AS
Понял, большое спасибо