Про задачи с собеседований…

Столкнулся я недавно с одной задачей на собеседовании:

Дано множество упорядоченных по какому-то критерию элементов, состоящих из двух полей: целочисленный ключ (key) и вещественное значение (data). В процессе работы на вход программы много раз подаются пары чисел L,R . Требуется находить среднее арифметическое элементов, лежащих в массиве между индексами L и R. Вопрос состоит в том, как эффективнее хранить данные: как массив записей или как запись, состоящую из двух массивов.

Честно говоря, я раньше о таких вещах не задумывался. Но, если немного поразмыслить и вспомнить курс по организации ЭВМ и систем, то можно прийти к следующим выводам: данные из памяти считываются не побайтово, а довольно большими блоками, состоящими из сотен байт. При этом, если следующее обращение происходит по близкому адресу, то с большой долей вероятности можно утверждать, что данные уже считаны, и нового цикла обращения к памяти можно избежать.

Посмотрим, что мы считываем при каждом из возможных подходов. Если мы храним данные как массив записей, то и считаны будут записи, то есть пары ключ-значение. Учитывая, что для вычислений нам необходимы только вещественные значения, получается, что существенный объём данных (все key) считывается впустую. Если же мы храним данные о ключах в одном массиве, а о значениях в другом, то при обращении к памяти будут считаны только необходимые нам вещественные переменные. Очевидно, что во втором случае обращений к памяти будет меньше.

Именно такого ответа ждали на собеседовании, но я решил проверить насколько в действительности велик выигрыш от такого расположения в памяти. Были написаны тестовые программы, которые показали, что вторая версия (запись массивов) примерно на 7% процентов быстрее.

Результат неплохой, но я сам всегда считал и ученикам говорил, что правильный алгоритм гораздо эффективней всяких ухищрений вроде рассмотренных выше. Существует так называемое интегральное представление массива, когда i-ый элемент интегрального массива равен сумме всех предшествующих элементов оригинального массива. Например, массив A=[1,2,3,4,5] в интегральном виде выглядит так: I=[1,3,6,10,15]. Интегральное представление можно получить за O(N), где N — размер исходного массива. Главное достоинство такого представления — возможность за константное время вычислить сумму элементов любого непрерывного подмассива. Пусть надо найти сумму элементов с L по R, она вычисляется за константное время как I[R]-I[L-1] (при этом будем считать I[0]=0).Этот подход оказался в десятки раз быстрее(!), чем любой из рассмотренных ранее.

Собственно мораль здесь проста — правильные алгоритмы и структуры данных всегда эффективнее любых низкоуровневых трюков.

Про задачи с собеседований…: 2 комментария

Добавить комментарий