Сергей Талантов (hitfounder) wrote,
Сергей Талантов
hitfounder

Category:
  • Mood:

О стратегиях выделения динамической памяти

Представьте, что вам необходимо написать реализацию структуры данных "вектор". Вектор - это динамический массив с возможностью произвольного доступа к элементам по индексу. Раз массив динамический, то необходимо использовать динамическое выделение памяти, и здесь возникает главный вопрос, какого размера блоки памяти следует выделять?

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

Итак, наиболее очевидный вариант - выделение блоками константной длины. Частным случаем этого варианта является выделение памяти по одному элементу, при этом константа равна единице (C=1). Можно прикинуть сложность выполнения этого алгоритма. Для массива длиной N и размере блока С, количество расширений массива, т.е. выделений блоков, будет равно N/C. При каждом расширении происходит копирование старых элементов, число которых при каждом новом выделении растет на значение С. В итоге будет следующее число копирований:

Это ни что иное, как сумма первых N/С членов арифметической прогрессии. По формуле, подсказанной Википедией (http://ru.wikipedia.org/wiki/Арифметическая_прогрессия) узнаем, что эта сумма равна:

Сложность такого алгоритма квадратичная О(N^2).

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

Это геометрическая прогрессия со знаменателем q = 1/2. Сумма первых logN членов геометрический прогрессии вычисляется по формуле подсказанной википедией (http://ru.wikipedia.org/wiki/Геометрическая_прогрессия):

Сложность такого алгоритма линейная О(N).

Очевидно, вторая стратегия является более выигрышной. Догадаться об этом можно и без формул. Однако не всем это удается. А привел я этот пример только потому, что он является, на мой взгляд, отличным вопросом на собеседовании для разработчика. В простейшем варианте кандидат может написать интерфейс и реализацию вектора на своем основном языке, так можно проверить базовое умение кодить. А потом можно задать вопрос на сообразительность на счет эффективности стратегии выделения памяти.

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

UPD: спасибо plebedev за подсказку, что во втором случае все-таки геометрическая прогрессия, а не арифмитическая как я ошибочно написал вначале. К счастью, принципиально ошибка ни на что не повлияла. Сложность в итоге получилась линейная, а не линейно-логарифмическая, что еще больше подтвердило эффективность второй стратегии.

Tags: задачи, культура программирования
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 4 comments