Почему при максимальной заполненности массива его размер нужно увеличивать именно вдвое (наиболее оптимальное значение)?
Единственно что приходит в голову это то, что поиск по массивам внутренними структурами CLR происходит бинарным поиском, то есть делением пополам.
Может кто-либо сказать или дать ссылку на статью с научным обоснование ответа на мой вопрос?
Здравствуйте, Alex Lakers, Вы писали:
AL>Если исходный массив имел длину 1 и требуется вставить n элементов, то кол-во операций изменения размера будет равно где-то lgN, что дешево.
А если увеличивать не вдвое, а впятеро, то кол-во изменений будет и того меньше.
Почему тогда увеличивают не впятеро?
Re: Почему размер массива нужно увеличивать именно вдвое?
Здравствуйте, Shuisky, Вы писали:
S>День добрый!
S>Почему при максимальной заполненности массива его размер нужно увеличивать именно вдвое (наиболее оптимальное значение)? S>Единственно что приходит в голову это то, что поиск по массивам внутренними структурами CLR происходит бинарным поиском, то есть делением пополам.
S>Может кто-либо сказать или дать ссылку на статью с научным обоснование ответа на мой вопрос?
Не всегда. Помнится в Delphi было 25%. Но суть в том, что при малом увеличении память больше фрагментируется, а при большем при достижении определенных значений может и не хватить как памяти, так и выход размера объекта за кэш процессора.
Вот от этих факторов и ищи оптимум. И им будет 2 кратное увеличение.
и солнце б утром не вставало, когда бы не было меня
Re: Почему размер массива нужно увеличивать именно вдвое?
Здравствуйте, Shuisky, Вы писали:
S>День добрый!
S>Почему при максимальной заполненности массива его размер нужно увеличивать именно вдвое (наиболее оптимальное значение)? S>Единственно что приходит в голову это то, что поиск по массивам внутренними структурами CLR происходит бинарным поиском, то есть делением пополам.
S>Может кто-либо сказать или дать ссылку на статью с научным обоснование ответа на мой вопрос?
Вообще говоря с памятью дело обстоит так
Какуюу бы стратегию выделения/перевыделения/освобождения Вы не взяли,
всегда найдётся алгоритм, который будет работать наименне эффективно именно при такой стратегии.
Re: Почему размер массива нужно увеличивать именно вдвое?
Здравствуйте, Shuisky, Вы писали:
S>Почему при максимальной заполненности массива его размер нужно увеличивать именно вдвое (наиболее оптимальное значение)? S>Единственно что приходит в голову это то, что поиск по массивам внутренними структурами CLR происходит бинарным поиском, то есть делением пополам.
Потому, что это разумный компромисс между потерями памяти (из-за частичного заполнения массива) и издержками на реаллокацию.
Но нигде не сказано, что именно для вашей задачи увеличение вдвое оптимально. Может, именно в вашем случае надо увеличивать не вдвое, а впятеро, или вместо геометрической прогрессии использовать ряд Фиббоначи
S>Может кто-либо сказать или дать ссылку на статью с научным обоснование ответа на мой вопрос?
Вопрос более сложный чем кажется. Правильный коэффициент зависит от стратегии работы с памятью (аллокатора).
Могу дать сслыку на грамотное обоснование почему в случае использования буфера с выделением/возвратом блоков разного размера именно вдвое как раз не надо
В .NET это менее актуально, так как GC делает уплотнение мелких объектов. Но для больших объектов — резидентов LOH (которых лучше вообще не иметь), снова актуально. Только насчёт именно 1.32 не уверен — копал эту тему годы тому назад.
Re[2]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, hi_octane, Вы писали:
_>В .NET это менее актуально, так как GC делает уплотнение мелких объектов. Но для больших объектов — резидентов LOH (которых лучше вообще не иметь), снова актуально. Только насчёт именно 1.32 не уверен — копал эту тему годы тому назад.
Чтобы получить большой не-ссылочный объект надо очень сильно постараться.
Re[3]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, hi_octane, Вы писали:
_>>В .NET это менее актуально, так как GC делает уплотнение мелких объектов. Но для больших объектов — резидентов LOH (которых лучше вообще не иметь), снова актуально. Только насчёт именно 1.32 не уверен — копал эту тему годы тому назад.
L>Чтобы получить большой не-ссылочный объект надо очень сильно постараться.
double'ы ложаться в LOH при гораздо меньшем размере, чем 85k, а именно при размере массива более 1000.
Re[4]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, hi_octane, Вы писали:
L>>Чтобы получить большой не-ссылочный объект надо очень сильно постараться. _>Не уловил мысль. А почему важна не-ссылочность?
Размер каких обхектов вы имели в виду, когда говорили о "больших объектах"? Об элементах массива или о чем-то другом?
Re[4]: Вдвое - ошибка! Правильно 1.32, но не всегда
=L>>Чтобы получить большой не-ссылочный объект надо очень сильно постараться.
R>double'ы ложаться в LOH при гораздо меньшем размере, чем 85k, а именно при размере массива более 1000.
Массив — ссылочный тип.
Re[5]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, hi_octane, Вы писали:
L>>Размер каких обхектов вы имели в виду, когда говорили о "больших объектах"? Об элементах массива или о чем-то другом?
_>Скорее о самих массивах, чем об их элементах.
Что значит "скорее"? Вы сомневаетесь, что именно вы же и имели в виду?
Re[5]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, rumatavz, Вы писали:
L>=L>>Чтобы получить большой не-ссылочный объект надо очень сильно постараться.
R>>double'ы ложаться в LOH при гораздо меньшем размере, чем 85k, а именно при размере массива более 1000.
L>Массив — ссылочный тип.
Тогда я как и hi_octane тоже не уловил вашу мысль.
Re[5]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, Lloyd, Вы писали:
L>Размер каких обхектов вы имели в виду, когда говорили о "больших объектах"? Об элементах массива или о чем-то другом?
Надо полагать, обо всех, подразумеваемых в терминологии Microsoft: http://msdn.microsoft.com/en-us/magazine/cc534993.aspx.
На практике — о достаточно длинных массивах, независимо от ссылочности типа их элементов.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[6]: Вдвое - ошибка! Правильно 1.32, но не всегда
Здравствуйте, Sinclair, Вы писали:
L>>Размер каких обхектов вы имели в виду, когда говорили о "больших объектах"? Об элементах массива или о чем-то другом? S>Надо полагать, обо всех, подразумеваемых в терминологии Microsoft: http://msdn.microsoft.com/en-us/magazine/cc534993.aspx.
Не надо полагать, достаточно дождаться ответа.
Re[6]: Вдвое - ошибка! Правильно 1.32, но не всегда
