how to speed up my program? parallel?
3 ビュー (過去 30 日間)
古いコメントを表示
I have a piece code which would take long time to run, I am wondering how to speed up. Any hints or suggestions are welcome! One think in my mind is parallel, but I have never done that before, so please help me out! Thanks!
When time steps (nT), # of nodes (Vn and Xn) are large (> 500, or even 800), the program will take more than 24 hours to finish.
These codes is using tree method to compute value at the starting points. First, I have 2 1-D trees: V-tree and X-tree, then the two trees are combined into one 2-D tree, I need to compute the value at the starting point in 2-D tree.
Below is my matlab codes:
% compute the value using tree method
% Input:
% nT -- time step
% Vn -- total # of nodes in V-tree
% Xn -- total # of nodes in X-tree
% both V- and X- trees are layed down on the floor,
% root on the left hand side and leaves on the right hand side
% the nodes labeled (by level) from top to bottom(floor):
% 1, 2, 3,.., Vn (Xn)
% Vindex -- 2-D matrix, branches index of V-tree on each level
% pv -- 2-D martix, probability of each branch
% on each level of V-tree
% xindex -- 3-D matrix, branches index of X-tree on each level
% px -- 3-D matrix, probability of each branch
% on each level of X-tree
% r -- growth rate
% dt -- time interval
% Vmid -- V0 position in V-tree (starting point of V-tree)
% Xmid -- X0 position in X-tree (starting point of X-tree)
% value -- 2-D matrix, value at last time step
% output:
% treeValu -- value at starting point
function treeValu = treemethod(nT, Vn, Xn, vindex, pv, xindex, px, r, dt, Vmid, Xmid, value)
for tstep = (nT-1) : -1 : 1 % backward along the tree
valuenew = zeros(Vn, Xn); %value martic for 2-D tree for iteration
for vlevel = 1 : Vn % loop on V-tree
clear vi vitemp vp vptemp;
vitemp = vindex(vlevel, :);
vi = nonzeros(vitemp); % V-tree branches after truncation
vptemp = pv(vlevel, :)'; %--- MUST BE COLUMN VECTOR
vp = vptemp(vitemp>0); % V-tree probability,
% pick prob by existing branches
for xlevel = 1 : Xn % loop on X-tree
clear xi xi3 x3temp xp xp3 xp3temp
xi3 = xindex(vlevel, xlevel, :); % take branch index of
% X-tree from 3-D matrix
xi3temp = reshape(xi3, 1, Xn);% reshape into 1-D vector
xi = nonzeros(xi3temp); % then remove zeros
xp3 = px(vlevel, xlevel, :); % take prob of X-tree
% from 3-D matrix
xp3temp = reshape(xp3, 1, Xn);% reshape into 1-D vector
xp = xp3temp(xi3temp>0); % X-tree probability, pick prob
% by existing branches
% Find the expected value at current node in 2-D tree
valuenew(vlevel, xlevel) = valuenew(vlevel, xlevel)...
+ sum(sum((vp*xp).*value(vi, xi)));
end
end % end loop on V-tree level
value = exp(-r*dt)*valuenew;
end % end loop on backward time step
% output the value at starting point
treeValu = value(Vmid, Xmid);
0 件のコメント
回答 (4 件)
Roger Stafford
2015 年 3 月 24 日
There seem to be a number of inefficiencies in this code:
1) If you make 'vp' a row vector and 'xp' a column vector, the expression
sum(sum((vp*xp).*value(vi, xi)))
can be replaced by the matrix product
vp*value(vi,xi)*xp
which I rather think is faster.
2) You set 'valuenew' to all zeros at the beginning of each 'tstep' and therefore there seems no point in adding the above matrix product to valuenew(vlevel,xlevel) because it will always be zero for each new pair (vleval, xlevel) each time they are encountered. Just write
valuenew(vlevel,xlevel) = vp*value(vi,xi)*xp;
3) Though you can experiment with this, there seems no point in doing the two clearing operations. The subsequent assignment operations should be able to take care of any necessary reallocation of memory at least as quickly.
4) There is something fishy with the returned value in 'treevalue'. As it stands, it reflects only the last 'tstep' operation. The results of all previous steps are being overwritten. Are you sure you haven't copied this code incorrectly?
Stephen23
2015 年 3 月 26 日
Roger Stafford made very good comments specific to the code you gave. You also might like to consider some general advice on how to speed up MATLAB code, some of which you might find useful:
- use vectorized code rather than loops.
- preallocate arrays before loops.
- use logical indexing rather than subscripts.
- do not change a variable's data class.
- do not clear unnecessarily.
- use tic and toc to time parts of a program.
- use the profiler to check how long all parts of a function require.
Additional Tips on Improving Performance
If the performance of your program remains a concern, then consider the following suggestions:
- Split large script files into smaller ones, having the first file call the second if necessary.
- Construct separate functions (or local functions and nested functions) from the larger chunks of code.
- If you have overly complicated functions or expressions, use simpler ones to reduce size. * Simpler functions often make good utility functions that you can share with others.
- Use functions instead of scripts because they are generally faster.
- Vectorize your code to take advantage of the full functionality of MATLAB.
- Use a sparse matrix structure to vectorize code without requiring large amounts of memory.
- Avoid running large processes in the background while executing your program in MATLAB.
- Avoid overloading MATLAB built-in functions on any standard MATLAB data classes because this can negatively affect performance.
参考
カテゴリ
Help Center および File Exchange で Matrix Indexing についてさらに検索
製品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!