Fast Index Replacement for Negative Consumption

Back to Fan's Matlab Examples Table of Content

Given some matrix, replace values by some number if satisfy certain condition.

Below I demonstrate a subsetting method that is potentially much faster than the standard subsetting method.

Matlab offers indexing satisfy certain conditions.

Indexing in matlab is fast, but while one might not suspect it, setting values based on index to another value is potentially very slow.

This operation:

  • mat_a(index_a) = float_b is potentially slow. This turns out to be a speed bottleneck in solving standard problems with consumption, where for some range of choices, consumption is negative, so we need to reset utility values when utility is invalid. When other parts of codes are sped up through various other mechanism, this single index replacement operation could take up a substantial proportion of remaining overall solution time for a standard dynamic asset problem.

Below, I show speed up achieved by doing the above operation like this:

  • mat_a = mat_a.(~index_a) + float_b(index_a);

This brings up a signficant improvement in speed.

For large matrixes, this improves speed by up to 10 to 20 times.

Related to this is logical vs linear index. Logical index should be used vs linear.

NOTE: The below performance gain only achieved when using double, if using single as data type, standard method is faster.

Logical vs Linear Index

In [401]:
clear all
data = rand([10,10])-0.3;
disp(data);

    0.5277    0.6867   -0.2836    0.4138   -0.2113    0.0990    0.5155    0.2865    0.2056    0.6671
   -0.0854    0.4878    0.3732    0.1010    0.2074   -0.1707   -0.2196    0.1694    0.5447    0.3788
    0.4006    0.4566    0.3528    0.2361    0.2585    0.3627    0.0704    0.1985    0.5254    0.0946
   -0.1068    0.2367    0.2856    0.5871    0.0929    0.0206    0.4244   -0.0792   -0.2422    0.6475
    0.5228    0.5980   -0.0650    0.3024    0.0604   -0.2228    0.0737   -0.0416    0.5999    0.4811
    0.6499    0.0087    0.4472    0.5408    0.0861   -0.0391    0.4120   -0.2313    0.6501    0.1620
    0.5626   -0.0925    0.5376    0.5727    0.5547   -0.0530    0.2782    0.0798   -0.1516    0.4953
   -0.2344    0.6064   -0.2552   -0.0875    0.5590    0.6959    0.4073    0.3480   -0.1117    0.4339
    0.0575    0.3523    0.1984   -0.2129   -0.2308    0.2112    0.5928    0.3997    0.3057   -0.1443
   -0.1070   -0.0727    0.6230    0.6632   -0.1159    0.1479    0.6214   -0.2518    0.4268    0.5998
In [402]:
% Logical Index of Less than Zero Values
(data < 0)

ans =

  10x10 logical array

   0   0   1   0   1   0   0   0   0   0
   1   0   0   0   0   1   1   0   0   0
   0   0   0   0   0   0   0   0   0   0
   1   0   0   0   0   0   0   1   1   0
   0   0   1   0   0   1   0   1   0   0
   0   0   0   0   0   1   0   1   0   0
   0   1   0   0   0   1   0   0   1   0
   1   0   1   1   0   0   0   0   1   0
   0   0   0   1   1   0   0   0   0   1
   1   1   0   0   1   0   0   1   0   0
In [403]:
% linear Index
find(data<0)'

ans =

  Columns 1 through 22

     2     4     8    10    17    20    21    25    28    38    39    41    49    50    52    55    56    57    62    74    75    76

  Columns 23 through 27

    80    84    87    88    99

The Problem

In [404]:
z = 15;
iter = 50;
fl_replace_val = -61.2456;
it_rown = 300; % 4GB if 1000
it_coln = round(((it_rown-1)*it_rown)/2 + it_rown);
c_min = -1;
c_max = 1;
mt_c = rand([it_rown, it_coln])*(c_max - c_min) + c_min;
mt_c_dup = mt_c;



















In [405]:



    


% ar_fl_exe_times = {};
% ar_fl_exe_desc = {};
it_coll = 0;



    















    


























Time it Takes to Find Index of Negative C values












In [406]:



    


% Negative c value
f_neg_c_log_idx = @() (mt_c < 0);
f_pos_c_log_idx = @() (mt_c > 0);
f_neg_c_lin_idx = @() find(mt_c < 0);



    















    
























In [407]:



    


fl_exe_time = timeit(f_neg_c_log_idx);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'logical index timer';



    















    
























In [408]:



    


fl_exe_time = timeit(f_neg_c_lin_idx);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'linear index timer';



    















    


























Time it Takes to Subset Based on Logical Index












In [409]:



    


% Negative c value
mt_log_idx = f_neg_c_log_idx();
mt_lin_idx = f_neg_c_lin_idx();
f_set_neg_c_log_idx = @() mt_c(mt_log_idx);
f_set_neg_c_lin_idx = @() mt_c(mt_lin_idx);



    















    
























In [410]:



    


fl_exe_time = timeit(f_set_neg_c_log_idx);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'get subset logical index timer';



    















    
























In [411]:



    


fl_exe_time = timeit(f_set_neg_c_lin_idx);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'get subset linear index timer';



    















    


























Index Replace












In [412]:



    


mt_pos_log_idx = f_pos_c_log_idx();
mt_neg_log_idx = f_neg_c_log_idx();



    















    
























In [413]:



    


% Fan Index Replace Method
tic;
mt_c_dup = mt_c_dup.*(~mt_neg_log_idx) + fl_replace_val*(mt_neg_log_idx);
toc;



    















    






Elapsed time is 0.028170 seconds.




















In [414]:



    


% Standard Index Replace Method
tic;
mt_c_dup(mt_neg_log_idx) = fl_replace_val;
toc;



    















    






Elapsed time is 0.090054 seconds.




















In [415]:



    


% Fan Replace
f_replace_idx_fan = @() ff_subscript_fan_replace(mt_c, mt_neg_log_idx, fl_replace_val);



    















    
























In [416]:



    


fl_exe_time = timeit(f_replace_idx_fan);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'matrix fan replace method';



    















    
























In [417]:



    


% Standard Replace
f_replace_idx_mat = @() ff_subscript_mat_replace(mt_c, mt_neg_log_idx, fl_replace_val);



    















    
























In [418]:



    


fl_exe_time = timeit(f_replace_idx_mat);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'matrix standard replace method';



    















    


























Double vs Single
Double vs Single data definition.
Previously Double, now Single.













In [419]:



    


% Double to Single
mt_c_single = single(mt_c);
mt_neg_log_idx_single = single(mt_neg_log_idx);
fl_replace_val_single = single(fl_replace_val);



    















    
























In [420]:



    


% mt_neg_log_idx_single



    















    
























In [421]:



    


% Fan Replace
f_replace_idx_fan = @() ff_subscript_fan_replace(mt_c_single, mt_neg_log_idx, fl_replace_val_single);



    















    
























In [422]:



    


fl_exe_time = timeit(f_replace_idx_fan);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'matrix fan replace method single';



    















    
























In [423]:



    


% Fan Replace Single Matrix converted to Double
f_replace_idx_fan = @() ff_subscript_fan_replace(double(mt_c_single), mt_neg_log_idx, fl_replace_val_single);



    















    
























In [424]:



    


fl_exe_time = timeit(f_replace_idx_fan);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'matrix fan replace method double(single)';



    















    
























In [425]:



    


% Standard Replace
f_replace_idx_mat = @() ff_subscript_mat_replace(mt_c_single, mt_neg_log_idx, fl_replace_val_single);



    















    
























In [426]:



    


fl_exe_time = timeit(f_replace_idx_mat);
it_coll = it_coll + 1;
ar_fl_exe_times(it_coll) = fl_exe_time;
ar_fl_exe_desc{it_coll} = 'matrix standard replace method single';



    















    


























Timing Results












In [427]:



    


tb_exe_times = array2table([ar_fl_exe_times', ar_fl_exe_times'*z*iter]);
tb_exe_times.Properties.RowNames = ar_fl_exe_desc;
tb_exe_times.Properties.VariableNames = {'speedmat', 'speedfull'};
disp(tb_exe_times);



    















    






                                                speedmat     speedfull
                                                _________    _________

    logical index timer                         0.0050284     3.7713  
    linear index timer                            0.13325     99.934  
    get subset logical index timer                0.11559     86.691  
    get subset linear index timer                0.073728     55.296  
    matrix fan replace method                    0.033476     25.107  
    matrix standard replace method                0.15291     114.68  
    matrix fan replace method single              0.16469     123.52  
    matrix fan replace method double(single)      0.15583     116.88  
    matrix standard replace method single         0.11789     88.416