Ускорение работы с динамическими массивами

← →
Mx © (2005-05-25 10:58) [40]

Если ты имеешь ввиду разницу в скорости работы через GetMem или SetLenght, то это уже обсуждалось, разницы никакой.

← →
begin...end © (2005-05-25 11:15) [41]

> Mx © (25.05.05 10:58) [40]

Нет, выделение памяти через GetMem как раз намного быстрее выделения такого же объёма через SetLength.
А вот скорость доступа к элементу массива будет практически такой же, о чём я и сказал в [1].

← →
alertus (2005-05-25 12:42) [42]

Мне не особо важна скорость выдеоления памяти, а вот скорость доступа к элементам -- важна.
А как насчет передачи параметров в функцию, как быстрее - var, const или без всего (value)??

А еще вопрос такой: я прочитал таки статью http://www.delphimaster.ru/articles/optimization.html
и поверил на слово.

Все таки интересно, как лучше написать:
for i:=0 to memo1.lines.count – 1 do...
или
lin := .lines.count – 1; for i:=0 to lin do...

Циклов у меня очень много, большой вложенности, я пытался смотреть в окно CPU, но понял мало...

← →
evvcom © (2005-05-25 15:54) [43]

Как быстрее можно понять из CPU Window. Var и Const - одинаково, а без всего - в зависимости от длины данных: до 4 байт включительно - так же, более 4-х дольше, и чем длиннее, тем дольше, так как делается копия данных в стеке.

lin := .lines.count – 1;
for i:=0 to lin do...

быстрее

← →
begin...end © (2005-05-25 16:05) [44]

> alertus (25.05.05 12:42) [42]

> Мне не особо важна скорость выдеоления памяти, а вот скорость
> доступа к элементам -- важна.

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

> я прочитал таки статью

Таки зачем?

> evvcom © (25.05.05 15:54) [43]

> lin := .lines.count – 1;
> for i:=0 to lin do...
> быстрее

И почему же, позволь полюбопытствовать?

← →
evvcom © (2005-05-25 16:15) [45]

> И почему же, позволь полюбопытствовать?

Согласен. Вспомнил какую-то статью, не проверив. Без разницы. Компилятор единожды вычисляет .lines.count – 1, а потом только dec(i) выполняет.

← →
TUser © (2005-05-25 16:23) [46]

С динамическими массивами лучше работать примерно так
var A: array of integer;
ACount: integer;

// добавление элемента
if ACount = length(A) then
SetLength(A, ACount+256);
A[ACount]:=Value;
inc (ACount);

И еще - если есть возмолжность замени все на целочисленную арифметику. Эти два примеа позволят разогнаться раза в 2-5.

← →
Kolan © (2005-05-25 16:50) [47]

А что ты делаещь с нейронной сетью. Оч оптимальное решение - упростить её.

← →
Mx © (2005-05-25 18:25) [48]

> begin...end ©

В тот раз обсуждали именно доступ, про него и написал. Насчет скорости при выделении, думаю лучше использовать то, что сама Borland рекомендует (SetLength), а то вдруг че-нить поменяют?

> alertus
> Все таки интересно, как лучше написать

Без разницы. В любом случае Lines.Count вычислится только один раз. Теоритечески даже медленее второй вариант, так как включает присвоение переменной.

> поверил на слово

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

> как быстрее - var, const или без всего

Var - там ссылка в любом случае. Однако все зависит от задачи. Если в процедуре ты не планируешь изменение размера массива, то, в моем понимании, лучше через const.

← →
alertus (2005-05-25 18:47) [49]

> Var - там ссылка в любом случае. Однако все зависит от задачи.
> Если в процедуре ты не планируешь изменение размера массива,
> то, в моем понимании, лучше через const.

Нет, я изменяю только элементы массива.
Вообще все массивы создаются один раз и больше не изменяются, динамические же они потому, что это универсальный Unit, который поддержывает сети с произвольным количеством слоев, нейронов и т.д.
Так что можно сказать, что массивы статические для данной программы, но для Unit"a они динамические...
Кстати, статитические массивы примерно в 3 раза быстрее работают, сегодня проверял.
Мне же надо разогнать в 5-6 раз (именно во столько раз медленнее работает, чем аналогичные программы в Matlab)

> А что ты делаещь с нейронной сетью. Оч оптимальное решение
> - упростить её.

В том то и дело, что заранее не известно, что будет делать сеть, она универсальная...

← →
begin...end © (2005-05-25 18:57) [50]

> Mx © (25.05.05 18:25) [48]

> Насчет скорости при выделении, думаю лучше использовать
> то, что сама Borland рекомендует (SetLength), а то вдруг
> че-нить поменяют?

Я и не предлагаю использовать GetMem для динамических массивов. Я говорил про использование GetMem для типов-указателей на статический массив. И имел в виду, что выделение одного и того же объёма памяти для соответствующих типов этими двумя способами сильно различается по скорости.

> alertus (25.05.05 18:47) [49]

> Кстати, статитические массивы примерно в 3 раза быстрее
> работают, сегодня проверял.

Повторю: если речь идёт о скорости доступа к элементу, то такого не может быть.

← →
alertus (2005-05-25 19:00) [51]

> Повторю: если речь идёт о скорости доступа к элементу, то
> такого не может быть.

А какое может быть??

Я проверял так:
беру три масива (сначала динамических, а потом статических),
пробегаю по ним циклом, записывая в третий произведения первого и второго (поэлементно), результат -- в три раза быстрее...

← →
begin...end © (2005-05-25 19:02) [52]

> alertus (25.05.05 19:00) [51]

Код проверки можно увидеть?

← →
alertus (2005-05-25 19:02) [53]

Может я чего-то не понимаю, но такой код:
edit1.Text:=timetostr(time); f:=memo1.Lines.Count; for i:=1 to 1000000 do begin for j:=1 to f do begin end; end; edit2.Text:=timetostr(time);

работает намного быстрее, чем
edit1.Text:=timetostr(time); for i:=1 to 1000000 do begin for j:=1 to memo1.Lines.Count do begin end; end; edit2.Text:=timetostr(time);

Кстати, если я правильно понял, то и в окне CPU видно, что программа обращается к memo1.Lines.Count каждый раз.

← →
alertus (2005-05-25 19:08) [54]

> Код проверки можно увидеть?

Для динамического:
procedure TForm1.Button1Click(Sender: TObject); var a:array of real; b:array of real; c:array of real; i,j:integer; begin Initialize(a); Initialize(b); Initialize(c); SetLength(a,10); SetLength(b,10); SetLength(c,10); for i:=0 to 9 do begin a[i]:=i; b[i]:=9-i; end; edit1.text:=timetostr(time); for i:=1 to 1000000000 do begin for j:=0 to 9 do begin c[j]:=a[j]*b[j]; end; end; edit2.text:=timetostr(time); finalize(a); finalize(b); finalize(c); end;

Для статического:
procedure TForm1.Button2Click(Sender: TObject); var a:array[0..9] of real; b:array[0..9] of real; c:array[0..9] of real; i,j:integer; begin for i:=0 to 9 do begin a[i]:=i; b[i]:=9-i; end; edit1.text:=timetostr(time); for i:=1 to 1000000000 do begin for j:=0 to 9 do begin c[j]:=a[j]*b[j]; end; end; edit2.text:=timetostr(time); end;

← →
begin...end © (2005-05-25 19:13) [55]

> alertus (25.05.05 19:02) [53]

> for i:=1 to 1000000 do begin
> for j:=1 to memo1.Lines.Count do begin
> end;
> end;

Здесь на каждом проходе цикла по i выполняется вход в цикл по j. Поэтому совершенно нормально и логично, что на каждой итерации цикла по i вычисляется конечное значение счётчика цикла по j. Это не опровергает вышесказанного, т.к. на каждой итерации цикла по j обращения к Lines.Count не происходит.

Измените пример так:

for i:=1 to memo1.Lines.Count do begin for j:=1 to 1000000 do begin end; end
и удивитесь результату.

← →
alertus (2005-05-25 19:16) [56]

Да, не могу не согласиться, тут я неправ.
Но если присутствуют именно такие вложенные циклы, то второй код выгоднее.

← →
Mx © (2005-05-25 19:17) [57]

> alertus (25.05.05 19:02) [53]

Насчет примера: Initialize вызывать не надо. Если ты сравниваешь скорость всей ButtonXClick, то возможно ее съедает SetLength, но доступ по скорости не может отличаться.

> Кстати, если я правильно понял, то и в окне CPU видно, что
> программа обращается к memo1.Lines.Count каждый раз

Естественно! Каждый раз в цикле по I, но не по J.

← →
alertus (2005-05-25 19:22) [58]

Я сравниваю скорость по этому фрагменту:
edit1.text:=timetostr(time); for i:=1 to 1000000000 do begin for j:=0 to 9 do begin c[j]:=a[j]*b[j]; end; end; edit2.text:=timetostr(time);
И он отличается минимум в 2 раза.

← →
begin...end © (2005-05-25 19:22) [59]

> alertus (25.05.05 19:08) [54]

Выполнил оба кода. В 3 раза времена выполнения не различаются. Они почти одинаковые. Что я делаю не так?

P.S. В данном случае не надо ни Initialize, ни Finalize.

← →
alertus (2005-05-25 19:24) [60]

Не знаю, я на двух машинах тестировал, на работе -- в 3 раза, дома -- в 2.
Может от машины зависит??

← →
alertus (2005-05-25 19:26) [61]

Кстати, надо выставить цикл побольше, у меня порядка
i:=1 to 1000000000 а в маленьком цикле разницы конечно нет, если счет идет на 1-2 секунды...

← →
Mx © (2005-05-25 19:28) [62]

> begin...end © (25.05.05 19:22) [59]
> В данном случае не надо ни Initialize, ни Finalize.

Верно говоришь.

← →
Mx © (2005-05-25 19:30) [63]

Интересно, а почему в CPU View коды выполнения умножений различаются? С дин.массивами на пару инструкций больше.

← →
alertus © (2005-05-25 19:33) [64]

> Интересно, а почему в CPU View коды выполнения умножений
> различаются? С дин.массивами на пару инструкций больше.

Факт!

← →
begin...end © (2005-05-25 19:33) [65]

> Mx © (25.05.05 19:30) [63]

Потому что в случае с дин. массивами требуется двойное разыменование.

← →
Kolan © (2005-05-25 19:34) [66]

Я что-то наверно упустил. Но вот как я вижу сеть:
Есть класс Нейронн(веса итд).
И есть класс Сеть - массив нейронов. Да?
Потом как ты меняешь веса итд может у тебя алгоритм обратного распространения ошибки неоптимальный? А в maple можно исходник посмотреть? Передири тот алгоритм что там.

Я весь алгоритм передрал из Matcad, включая алгоритм Левенберга-Марквардта, самый быстрый алгоритм обучения полносвязных сетей.
А насчет видения сетей, есть как минимум две идеалогии:
1) сеть - массив слоев, слой - массив нейронов, нейрон - массив параметров;
2) сеть - массив слоев, слой - набор матриц параметров (веса, смещения, входы, выходы, всякие вспомогательные).

Ну вот я делал 1. Но я схитрил и взял 1 слой. И сё.
Так а ты как сделал?
Я думая тут дело в алгоритме или еще где.

1 слой - плохо, 3 и больше тоже, два - хорошо.
А еще алгоритмы обучения никуда не годятся, только Левенберг-Марквардт.
Моя программа может аппроксимировать функции, находит коэффициенты рядов Тэйлора и Фурье, распознает образы и многое многое другое, но ПРОБЛЕМА!!! циклы обучения медленные, виноват не алгоритм, а реализация, в Matlab"бе же все работает точно также, но в 5 раз быстрее.

> alertus © (25.05.05 19:47) [69]
> 1 слой - плохо, 3 и больше тоже, два - хорошо.
> А еще алгоритмы обучения никуда не годятся, только Левенберг-Марквардт.
> Моя программа может аппроксимировать функции, находит коэффициенты
> рядов Тэйлора и Фурье, распознает образы и многое многое
> другое, но ПРОБЛЕМА!!! циклы обучения медленные, виноват
> не алгоритм, а реализация, в Matlab"бе же все работает точно
> также, но в 5 раз быстрее.

Wowwwwww :)

TMatrix = class(TObject) private w:integer; //ширина матрицы h:integer; //высота матрицы elem:array of array of real; //массив элементов матрицы public constructor Create(wset,hset:integer); virtual; destructor Destroy; override; function GetElem(i,j:integer):real; procedure SetElem(i,j:integer;r:real); function GetWidth:integer; function GetHeight:integer; end;

Мож вот в этом проблема. Зачем делать матрицу наследником TObject?

Не знаю, я посмотрел модуль NeuralBase, их пишет BaseGroup (там возможностей маловато, но написан он вроде профессионально), я объявления классов у них содрал...
Даже классы исключений написал, хотя они мне не нужны, так, для красоты.
Просто я в объявления классов не силен...
А как лучше сделать??

Может кто-нибудь поправит, вот часть кода:

unit MatrixCalc; interface uses SysUtils,Classes; const SWrongColIndex = "Индекс столбца %d не соответствует размерности матрицы."; SWrongRowIndex = "Индекс строки %d не соответствует размерности матрицы."; SWrongSizesAdd = "Размеры матриц при сложении не соответсвуют."+chr(13)+"Ширина и высота первой матрицы должны совпадать с шириной и высотой второй матрицы."; SWrongSizesSubtract = "Размеры матриц при вычитании не соответсвуют."+chr(13)+"Ширина и высота первой матрицы должны совпадать с шириной и высотой второй матрицы."; SWrongSizesMult = "Размеры матриц при умножении не соответствуют."+chr(13)+"Ширина первой матрицы должна быть равна высоте второй."; SWrongSizesLeftDiv = "Размеры матриц при левом делении не соответствуют."+chr(13)+"Высота первой матрицы должна быть равна высоте второй матрицы."; SNotSqSizeLeftDiv = "При левом делении первая матрица должна быть квадратной,"+chr(13)+"Иначе получается недоопределенная или переопределенная система."+chr(13)+"Такие системы тоже можно решать, но это будет поддерживаться в следующей версии."; SWrongStringReadMatrix = "Неверный формат строки при конвертации строки в матрицу."; SWrongHeightsGlue = "Высоты матриц при горизонтальном склеивании не должны различаться."; SWrongWidthsGlue = "Ширины матриц при вертикальном склеивании не должны различаться."; SWrongIndexesFrag = "При получении фрагмента матрицы заданы неверные индексы:"+chr(13)+"левая верхняя ячейка (%d,%d), правая нижняя ячейка (%d,%d)."; type EMatrixError = class(Exception); TMatrix = class(TObject) private w:integer; //ширина матрицы h:integer; //высота матрицы elem:array of array of real; //массив элементов матрицы public constructor Create(wset,hset:integer); virtual; destructor Destroy; override; function GetElem(i,j:integer):real; procedure SetElem(i,j:integer;r:real); function GetWidth:integer; function GetHeight:integer; end; function WriteMatrix(m:TMatrix;escape:boolean):string; //выводит матрицу в строку function ReadMatrix(s:string;escape:boolean):TMatrix; //читает матрицу из строки function EyeMatrix(wset,hset:integer;mu:real):TMatrix; //генерирует матрицу у которой на главной диагонали стоят mu, остальные - нули function FillMatrix(wset,hset:integer;r:real):TMatrix; //Заполняет матрицу числом r function EquateMatrix(m:TMatrix):TMatrix; //приравнивает матрицы, т.е. создает клон матрицы function AddNumber(m:TMatrix;r:real):TMatrix; //прибавляет к каждому элементу матрицы число function AddMatrix(m1,m2:TMatrix):TMatrix; //поэлементное сложение матриц function SubtractMatrix(m1,m2:TMatrix):TMatrix; //поэлементное вычитание матриц m1-m2 function MultMatrix(m1,m2:TMatrix):TMatrix; //умножение матриц function TransMatrix(m:TMatrix):TMatrix; //транспонирование матрицы function LeftDivMatrix(m1,m2:TMatrix):TMatrix; //левое деление матриц, или решение системы линейных уравнений, где первая матрица - коэфициенты левой части, а столбцы второй - правая часть системы, столбцы результата будут решением системы function GlueMatrix(m1,m2:TMatrix;horiz:boolean):TMatrix; //Склеивает две матрицы, horiz=true - по горизонтали, horiz=false - по вертикали function ColMatrix(m:TMatrix;i:integer):TMatrix; //выводит колонку с номером n матрицы m в вектор-столбец (матрица-результат) function FragMatrix(m:TMatrix;i1,j1,i2,j2:integer):TMatrix; //возвращает матрицу-фрагмент входной матрицы function SqSumMatrix(m:TMatrix):real; //возвращает сумму квадратов всех элементов матрицы implementation constructor TMatrix.Create(wset,hset:integer); var i,j:integer; begin inherited Create; Initialize(elem); SetLength(elem,wset,hset); w:=wset; h:=hset; for i:=1 to wset do begin for j:=1 to hset do begin SetElem(i,j,0); end; end; end; destructor TMatrix.Destroy; begin Finalize(elem); inherited Destroy; end; function TMatrix.GetElem(i,j:integer):real; begin if (i<1) or (i>w) then begin raise EMatrixError.CreateFmt(SWrongColIndex,[i]); exit; end; if (j<1) or (j>h) then begin raise EMatrixError.CreateFmt(SWrongRowIndex,[j]); exit; end; result:=elem[i-1,j-1]; end; procedure TMatrix.SetElem(i,j:integer;r:real); begin if (i<1) or (i>w) then begin raise EMatrixError.CreateFmt(SWrongColIndex,[i]); exit; end; if (j<1) or (j>h) then begin raise EMatrixError.CreateFmt(SWrongRowIndex,[j]); exit; end; elem[i-1,j-1]:=r; end; function TMatrix.GetWidth:integer; begin result:=w; end; function TMatrix.GetHeight:integer; begin result:=h; end;

> begin...end © (25.05.05 19:33) [65]
> Потому что в случае с дин. массивами требуется двойное
> разыменование.

Что такое "разыменование"? Указатель на указатель?

> Mx © (25.05.05 20:15) [73]

> Что такое "разыменование"?

Операция получения содержимого памяти по значению указателя.

Что нужно сделать, чтобы получить значение i-го элемента статического массива (будем считать, что он индексируется с нуля), являющегося локальной переменной? Нужно к адресу этой переменной (в стеке) прибавить i * размер_элемента_массива байт, а затем разыменовать полученный указатель.

А как обстоит дело с локальной переменной динамического массива? Переменная является указателем на область памяти, в которой находятся элементы. Значит, вначале нужно разыменовать адрес переменной в стеке, чтобы получить этот указатель. А потом уже к тому, что получилось, прибавить i * размер_элемента_массива байт. И после этого -- разыменовать, для получения значения элемента.

Разыменование указателя - получение значения ячейки памяти, куда он ссылается

a:integer; b:integer; p:^integer; ... a:=5; p:=@a; b:=p^;

Последняя операция - разыменование указателя.
Итого: b=5.

2begin...end
Но ведь все эти операции требуют времени, значит работа с динамическими массивами медленнее.

Ускорение работы с динамическими массивами Найти похожие ветки