Динамические массивы

← →
FXeS (2005-08-30 14:46) [0]

Подскажите, что с точки зрения эффективности (т.е. скорость работы и занимаемый объем памяти) лучше - дин. массивы или обычные, но создаваемые "с запасом" ячеек.

← →
Суслик © (2005-08-30 14:48) [1]

зависит от того, как конкретно ты будешь писать код, использующий указанные массивы

← →
Суслик © (2005-08-30 14:51) [2]

Легче и всем полезней отвечать на вопросы с конкретным кодом...

← →
FXeS (2005-08-30 15:09) [3]

Пример: Дин. массив из 100 ячеек и обычный массив из 100 ячеек, оба типа integer.
Насколько больше памяти занимает дин. массив,
Если пройтись циклом по этим массивам, то они пройдут за одно время?

← →
Суслик © (2005-08-30 15:51) [4]

> Если пройтись циклом по этим массивам, то они пройдут за
> одно время?

да

> Насколько больше памяти занимает дин. массив,

Они хранятся в разных местах: дин массив в динамической памяти, управляемой менеджером памяти дельфи, обычный массив в стеке.

На хранение дин массив дополнительно стратится что-то порядка 4 или 8 байт (точно не помню) накладных расходов на хранение служебной информации о выделенном блоке памяти.

--------

Все же повторю, что выбор зависит от задачи. В разных случаях может разные массивы оказаться наиболее эффективны по сочетанию характеристик.

← →
Суслик © (2005-08-30 15:58) [5]

мое имхо, что про дин массивы нужно помнить 2 важных факта:
1. при копировании одной переменной в другую копируется ссылка, а не значения массива.
2. добавление в дин. массив большего кол-ва элементов по одному достаточно медлительно.

Во всем остальном дин и обычные похожи

← →
Igor_thief (2005-08-30 15:59) [6]

FXeS (30.08.05 15:09) [3]
Если пройтись циклом по этим массивам, то они пройдут за одно время?
НЕТ!

← →
TUser © (2005-08-30 16:06) [7]

С точки зрения экономии памяти - лучше дин. массив. С точки зрения скорости - обычный, статический. Если заранее (при разработке) известен размер массива, и известно, что максимальный размер будет достигнут - одназначно, статический. Если размер заведомо небольшой, но скорость очень критична - пожалй, тоже. В остальных случаях - динамический.

← →
Суслик © (2005-08-30 16:12) [8]

> С точки зрения скорости - обычный, статический

и чем же :)
скорость обращения у них одинаковая, т.к. код генерится почти одинаковый, если не одинаковый

← →
Суслик © (2005-08-30 16:28) [9]

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

Можно ради примера посмотреть такой код. У меня разница в 3%.

Если де убрать использование DoS и DoD, а непосредственно изменять знанчения по месту, то разница будет сильная. Но этот случай в жизни редок, т.к. к массиву обычно обращаешься по индексу, неизвестному в момент компиляции.

{$rangechecks on} {$optimization on} procedure TForm1.Button3Click(Sender: TObject); const cLen = 128*1024; var d: array of integer; s: array [0..cLen-1] of integer; i,j: integer; c1, c2,f: TLargeInteger; procedure DoS(); begin s[i] := 10; // тут оптимизация допустимости границ не может // быть пропущена компилятором end; procedure DoD(); begin d[i] := 10; end; begin QueryPerformanceFrequency(f); // normal QueryPerformanceCounter(c1); for j := 1 to 1000 do for i := 0 to High(s) do DoS(); QueryPerformanceCounter(c2); ShowMessageFmt("normal %.4f", [(c2-c1)/f]); // dynamic QueryPerformanceCounter(c1); SetLength(d, cLen); for j := 1 to 1000 do for i := 0 to High(d) do DoD(); QueryPerformanceCounter(c2); ShowMessageFmt("dynamic %.4f", [(c2-c1)/f]); end;

← →
Erik1 © (2005-08-30 17:08) [10]

TList с принудительным выделением памяти рулит.

← →
Суслик © (2005-08-30 17:14) [11]

tlist точно медленнее (хоть и не сильно) дин массивов, т.к. там есть вызов метода.

зато добавление быстрее, это точно.

← →
tesseract © (2005-08-30 22:22) [12]

Самый быстрый массив - статический с индексом с нуля array[0..etc] - там проще считать индекс.
В динамическом приходится ещё и проверять границы/размер массива -ещё медленнее.(PChar значительно быстрее String)
в Tlist данные могут распологаться на разных страницах памяти - ещё медленнее.

← →
Anatoly Podgoretsky © (2005-08-31 00:31) [13]

tesseract © (30.08.05 22:22) [12]
Нука, нука - еще раз про скорость PChar например для определения длины больщой строки.
Страницы памяти, ты случайно с винчестером не путаешь.

← →
Джо © (2005-08-31 01:09) [14]

> [12] tesseract © (30.08.05 22:22)

Да, я тоже не совсем понял, почему PChar "значительно быстрее" String... Уж про определение длины строки спрашивать не буду, спрошу в общем.

← →
Суслик © (2005-08-31 11:31) [15]

а вы все-таки тест мой посмотрите - разница по доступу к элементам при {$rangechecks on} в 3 процента. При {$rangechecks off} разница больше но все равно не более 20 процентов. TList при {$rangechecks on} сильно проигрывает обоим типам массивов.

> [12] tesseract © (30.08.05 22:22)

> В динамическом приходится ещё и проверять границы/размер
> массива

насколько мне известно эта проверка отключается {$rangechecks off}

← →
tesseract © (2005-08-31 13:51) [16]

>>насколько мне известно эта проверка отключается {$rangechecks off}
Да но выход за пределы массива проверяются
и скрытые блоки try..except всё равно остаются. AccessViolation видел? так вот это как раз реакция на скрытый try..except.

>> Страницы памяти, ты случайно с винчестером не путаешь

Не путаю Tlist выделяет память блоками, и на какой именно странице будет расположен блок неизвестно. А при обращении к другой странице памяти на неё необходимо переключится.

>>Нука, нука - еще раз про скорость PChar например для определения длины больщой строки.

Запустика две функции поиска /копирования/добавления строк PChar и string - какой метод быстрее?

конечно определение длины строки быстрее в string - там длина в начале строки хранится нечего вычислять.

← →
Суслик © (2005-08-31 14:00) [17]

> и скрытые блоки try..except всё равно остаются. AccessViolation
> видел? так вот это как раз реакция на скрытый try..except.

можно про это подрбней, что ты имеешь в виду?

← →
tesseract © (2005-08-31 14:07) [18]

>> можно про это подрбней, что ты имеешь в виду?

Поподробней "Фундаментальные алгоритмы и структуры данных в Delphi". Там про это подробно написано.

А проще при работе с разными "опасными" типами данных вроде указателей вставляется проверка. И мы получаем AV delphi а не "крындец " Винды. Если бы не было проверок всё работало бы не совсем так :-)

← →
Суслик © (2005-08-31 14:10) [19]

> [18] tesseract © (31.08.05 14:07)

> А проще при работе с разными "опасными" типами данных вроде
> указателей вставляется проверка

А давай подробней. Например, примером кода, где при нормальном использовании дин. массивов есть av. Ты же вроде про это говоришь? На cpu посмотрим, поразбираемся, тогда и обсудим твое высказываение

> Да но выход за пределы массива проверяются
> и скрытые блоки try..except всё равно остаются. AccessViolation
> видел? так вот это как раз реакция на скрытый try..except.

← →
Суслик © (2005-08-31 14:14) [20]

> [18] tesseract © (31.08.05 14:07)

по поводу {$rangechecks off/on} ты не прав. Эта опция действительно отключает/включает проверку границ в том числе и в дин. массивах.
Проверь, cpu посмотри.

← →
tesseract © (2005-08-31 14:35) [21]

>>по поводу {$rangechecks off/on} ты не прав. Эта опция действительно отключает/включает проверку границ в том числе и в дин. массивах.

Возможно, я как-то реально не пользовался rangecaheck не отключал.

Мне приятнее вставить on EAccessViolation и получить лог присылаемый заказчиком, выяняя где AV.

Для справки посмотри производительность функций:

PosOFChar:=Pos(SomeChar,MyString);

и
function GetCharPos(aCh:AnsiChar; const S: string):integer;
begin
Result:=0;
for i:=1 to length (S) do
if (S[i] = aCh) then
begin
result:=i;
exit;
end;
end;

насчёт try..finally
попробуй передать в функции параметр как var и как const. КАК ПРАВИЛО const быстрее процентов на 10.

← →
Суслик © (2005-08-31 14:38) [22]

> var и как const

вполне может быть.
ничего удивительного, т.к. зачастую при const не происходит увеличения счетчика ссылок. Не буду уствержать что это так для дин массивов. Но для интерфейсов это так. Может и для дин. массивов тоже.

-------
Про строки я ничего не говорил. Т.е. про них разговор продолжать бы не хотел.

А вот "порочный" av при дин. массивах было бы интересно посмотреть.

← →
tesseract © (2005-08-31 15:11) [23]

to Суслик >> давай без флуда не по теме tesseract@mail.ru

← →
Суслик © (2005-08-31 15:13) [24]

Ок.
Только флуда тут не видно, вроде даже по теме.

← →
Sapersky (2005-08-31 15:21) [25]

Если же убрать использование DoS и DoD, а непосредственно изменять знанчения по месту, то разница будет сильная. Но этот случай в жизни редок, т.к. к массиву обычно обращаешься по индексу, неизвестному в момент компиляции.

Не очень понял, что значит "по месту/не по месту", но, ИМХО, вызов процедуры для каждого элемента типа integer - не очень жизненная ситуация. Скорее так:

for i := 0 to High(s) do s[i]:=10

При этом статический быстрее где-то в 1.3 раза, т.к. компилятор обращается к его элементам через инкрементируемый указатель, т.е. код оптимизируется до примерно такого:

pi:=@s[0];
for i := 0 to High(s) do begin pi^:=10; Inc(pi); end;

В случае динамического массива при обращении к каждому элементу заново высчитывается его смещение (start + index * elementsize).

С многомерными динамическими массивами ситуация ещё хуже, т.к. они хранятся не линейно, а как массив указателей. И для каждой размерности смещение нужно считать отдельно.

← →
Суслик © (2005-08-31 15:25) [26]

> Не очень понял, что значит "по месту/не по месту", но, ИМХО,
> вызов процедуры для каждого элемента типа integer - не очень
> жизненная ситуация

Про жизненность можно поспорить все-таки. Т.к. сплошной перебор элементов это не 100 процентов вариантов использования массивов. Зачастую в массивах лежал данные, к которым происходит выборочное обращение из разных мест. В этом случае компилатор оптимизировать обращение не может. Разница все же есть, но в несколько процентов. Проверь. Для того, чтобы имитировать обращение к элементам массивов я ввел две процедуры DoD и DoS.

← →
Игорь Шевченко © (2005-09-01 18:35) [27]

> Не путаю Tlist выделяет память блоками, и на какой именно
> странице будет расположен блок неизвестно. А при обращении
> к другой странице памяти на неё необходимо переключится.

Путаешь. Переключаться не надо.

← →
Кефир87 © (2005-09-01 22:06) [28]

> обычный массив в стеке.

Всегда думал что в DS 8)

> [28] Кефир87 © (01.09.05 22:06)

Вроде в стеке

{$optimization on} procedure TForm1.Button6Click(Sender: TObject); var s: array [0..1023] of byte; begin s[1] := 1; end;

0045AA18 81C400FCFFFF add esp,$fffffc00 0045AA1E C644240101 mov byte ptr [esp+$01],$01 0045AA23 81C400040000 add esp,$00000400 0045AA29 C3 ret

я асм. ваще не знаю, но вроде это стек :) Или нет? Просветите, кто знает :)

Ну и где сдесь стэк?! На сколько я помню регистр стэка IP (или EIP в
32).
А стэк этож ваще что?! Мы туда кладем на верх и берем то что сверху (команды PUSH и POP соответственно) там еще адреса возврата сохраняются командой CALL. Ну так и как там что-то можно хранить? 8)

> [30] Кефир87 © (02.09.05 17:06)

вроде бы esp меняется каждый раз когда делаешь pop или push.
Опать же если не ошибаюсь esp показывает на голову стека.

В общем о чем спор то?

> Суслик © (02.09.05 11:31) [29]

Если в подпрограмме, то в стеке (как и любая другая локальная переменная, не удалённая оптимизатором). Если нет, то не в стеке.

> Кефир87 © (02.09.05 17:06) [30]

> На сколько я помню регистр стэка IP

Нет. IP -- это Instruction Pointer. Он содержит часть полного адреса машинной команды, подлежащей выполнению.

> Ну так и как там что-то можно хранить?

ESP -- это указатель на вершину стека. В коде [29] от содержимого указателя отнимается $fffffc00 = -1024, т.е. в стеке резервируется область размером в 1024 байта. Потом можно инициализировать регистр указателя базы кадра стека EBP, и обращаться к размещённым данным, указывая смещение относительно адреса в EBP. Команды PUSH и POP тоже изменяют содержимое ESP, но только либо на 2, либо на 4 байта.

К [32]:

> от содержимого указателя отнимается $fffffc00 = -1024

В смысле, к содержимому указателя прибавляется -1024. Или отнимается 1024.

Да нет спора. Просто я б не догадался хранить массивы в стэке 8)

>>Путаешь. Переключаться не надо.

Да сдесь задействован менеджер памяти Windows. Размер страницы d Win 32 - 4кб.

> Да нет спора. Просто я б не догадался хранить массивы в
> стэке 8)

Я тоже :-)

Просто я б не догадался хранить массивы в стэке 8)

На сколько помню - массивы всегда в стеке ханились... ))))

> [37] Кефир87 © (04.09.05 13:06)
> > Суслик © (02.09.05 20:22) [35]
> Ну говорю же, в DS (Data Segment) 8)

Это как?
А рекурсия? Или имитировать стек?
Или я что-то не понимаю?

Динамические массивы Найти похожие ветки