matlabで「漸進的に成長する」セル配列を実装するために、次のクラスを作成しました。
classdef growinglist < handle
properties (GetAccess='private',SetAccess='private')
inner_cells % inner pre-allocated cell array
end
properties (GetAccess='public',SetAccess='private')
n_elements % current number of elements (index of last valid element in inner_cells)
end
methods
%% constructor
function self=growinglist(varargin)
% you can pass the initial capacity of inner_cells to constructor
if nargin == 1
self.inner_cells =cell(ceil(varargin{1}),1);
else
self.inner_cells =cell(4,1); % initial size is 4
end
self.n_elements = 0;
end
function add(self, element)
% inner_cells is not enough, double it before adding
if self.n_elements + 1 > size(self.inner_cells,1)
n = floor(size(self.inner_cells,1) * 2) - size(self.inner_cells,1) + 1;
self.inner_cells = [self.inner_cells; cell(n,1)];
end
self.n_elements = self.n_elements + 1;
self.inner_cells{self.n_elements} = element;
end
function elements = get_elements(self)
elements = self.inner_cells(1:self.n_elements,1);
end
end
end
ただし、期待どおりに高速ではないようです。
実際、これらのテストを実行します。
n = 30000;
%%%%%% concat everytime
tic
lst = {};
for i=1:n
lst = [lst; 1:10];
end
disp('1 - concat everytime');
toc
%%%%%% exact pre-allocation
tic
lst = cell(n,1);
for i=1:n
lst{i} = 1:10;
end
disp('2 - exact pre-allocation');
toc
%%%%%% "progressive" pre-allocation
tic
inner_cells = cell(4,1);
n_elements = 0;
for i=1:n
if n_elements + 1 > size(inner_cells,1)
n1 = floor(size(inner_cells,1) * 2) - size(inner_cells,1) + 1;
inner_cells = [inner_cells; cell(n1,1)];
end
n_elements = n_elements+1;
inner_cells{n_elements} = 1:10;
end
elements = inner_cells(1:n_elements,1);
disp('3 - "progressive" pre-allocation');
toc
%%%%%% using growing list class
tic
glst = growinglist();
for i=1:n
glst.add(1:10);
end
elements = glst.get_elements();
disp('4 - using growing list class');
toc
%%%%%% using growing list class with exact allocation
tic
glst = growinglist(n);
for i=1:n
glst.add(1:10);
end
elements = glst.get_elements();
disp('5 - use growing list class with exact allocation');
toc
次の結果が得られます。
1 - concat everytime
Elapsed time is 4.954054 seconds.
2 - exact pre-allocation
Elapsed time is 0.006791 seconds.
3 - "progressive" pre-allocation
Elapsed time is 0.099431 seconds.
4 - using growing list class
Elapsed time is 11.618202 seconds.
5 - use growing list class with exact allocation
Elapsed time is 12.774726 seconds.
実際、テストn.4とn.5の経過時間はテストn.3にはるかに近いと予想しました。しかし、それらはテストn.1よりもさらに遅いです(私は最悪だと思っていました)。さらに、奇妙なことに、テストn.5はn.4よりも低速です。
設定されるたびにinner_cells配列がコピーされるか、他のコピーが実行される可能性がありますが、可変性をサポートするためにハンドルクラスからクラスを派生させたため、理由がわかりません。
私はmatlabにかなり慣れていないので、おそらく重要な何かが欠けています...
何か洞察はありますか?
前もって感謝します。
PS
私はMATLAB2011aを使用しています。
編集 :
@Edricが提案したように、プロファイラーを使用してボトルネックを見つけました。速度の低下の原因はsize(self.inner_cells,1)
、メソッド内で呼び出された関数であることがわかりましたAdd()
(理由はわかりません)。
この方法でクラスを変更する(size()呼び出しを減らすため):
classdef growinglist < handle
properties (GetAccess='private',SetAccess='private')
inner_cells
inner_cells_size
end
properties (GetAccess='public',SetAccess='private')
n_elements % current number of elements (index of last valid element in inner_cells)
end
methods
% constructor
function self=growinglist(varargin)
% you can pass the initial capacity of inner_cells to constructor
if nargin == 1
self.inner_cells =cell(ceil(varargin{1}),1);
self.inner_cells_size = ceil(varargin{1});
else
self.inner_cells =cell(4,1); % initial size is 4
self.inner_cells_size = 4;
end
self.n_elements = 0;
end
function add(self, element)
% inner_cells is not enough, double it before adding
if self.n_elements + 1 > self.inner_cells_size
n = floor(size(self.inner_cells,1) * 2) - size(self.inner_cells,1) + 1;
self.inner_cells = [self.inner_cells; cell(n,1)];
self.inner_cells_size = self.inner_cells_size + n;
end
self.n_elements = self.n_elements + 1;
self.inner_cells{self.n_elements} = element;
end
function elements = get_elements(self)
elements = self.inner_cells(1:self.n_elements,1);
end
end
end
テストで次の結果が得られます。
1 - concat everytime
Elapsed time is 6.825776 seconds.
2 - exact pre-allocation
Elapsed time is 0.011783 seconds.
3 - "progressive" pre-allocation
Elapsed time is 0.088668 seconds.
4 - using growing list class
Elapsed time is 0.841975 seconds.
5 - use growing list class with exact allocation
Elapsed time is 0.818212 seconds.
それははるかに理にかなっています。