Using vectorization instead of a 'for Loop' in Matlab

Question

I have a set of 32 bits binary values incoming from a sensor. I have to form all the possible combinations of these values and then convert them into a decimal value.

The code slows down terribly if the incoming rows are more that 80000 - 90000. It takes 120 minutes to run.

I want to optimize this code, since 3 For loops and a function within the innermost loop is slowing down my algorithm. Is there any chance that I can eliminate some For loops and substitute them with vectorizing to speed up the process.

b1 = [0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1];
b2 = [0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1];
b3 = [0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1];
b4 = [0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1];
b5 = [0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1];

FullVector = [b1;b2;b3;b4;b5];

for Idx = 1:size(FullVector,1)
k = 1;
MinLength = 4;             
MaxLength = 8; 
StepSize = 2;          

    for StartByte = 1:8
        for StartBit = 1:8
            for SignalLength = MinLength:StepSize:MaxLength
                DecimalVals.s(Idx,k) = BitCombinations(FullVector,StartByte,StartBit,SignalLength);
                k = k+1;
            end
        end
    end
end

The function:

function decimal = BitCombinations(ByteArray,Sbyte,Sbit,lengthSignal)
%function extracts the required bits from a byte array and 
%returns the decimal equivalent of the bits.

%Inputs:
%Sbyte  - Starting byte
%Sbit   - Starting bit in the given byte
%length - length of bits to be extracted 

%Output:
%dec    - Returns the dec  

startbit_pos = ((Sbyte-1)*8+Sbit);
endbit_pos = ((Sbyte-1)*8+Sbit+lengthSignal-1);

if endbit_pos <= 64
    extractedbits = ByteArray(startbit_pos:endbit_pos);
    extractedbits = fliplr(extractedbits);
    decimal = bi2de(extractedbits);
else
    decimal = NaN;
end

end

I don't think your example code is complete/working. Idx is not incremented, for example. And can valid symbols cross byte arrays? (your code seems to allow this) — mhopeng
– mhopeng, Commented Jan 19, 2017 at 18:02
@mhopeng I am sorry but I don't think I follow. I have initialized Idx and everything seems to be working. — user161816
– user161816, Commented Jan 19, 2017 at 19:44
You could start by initializing your DecimalVals.s(Idx,k) before your start looping — Dammi
– Dammi, Commented Jan 19, 2017 at 22:13
I would recommend the same as @Dammi. In this case you are also able to see if it is a memory problem on your machine. — M_Tornack
– M_Tornack, Commented Jan 20, 2017 at 7:52
First, shouldn't it be ... = BitCombinations(FullVector(k, :), ...? Second, the b's are 32 bits long, while you check if the endbit_pos is <64. Shouldn't it be <32 in that case? — hbaderts
– hbaderts, Commented Jan 22, 2017 at 0:35

bushmills · Accepted Answer · 2017-01-20 13:16:10Z

you should preallocate your result matrix DecimalVals by using the following code example:

b1 = repmat([0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1],10000,1);
b2 = repmat([0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1],10000,1);
b3 = repmat([0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1],10000,1);
b4 = repmat([0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1],10000,1);
b5 = repmat([0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1],10000,1);

FullVector = [b1;b2;b3;b4;b5];

MinLength = 4;             
MaxLength = 8; 
StepSize = 2;  

% Preallocation of the result struct
noOfValues = (((MaxLength - MinLength) / 2) + 1) * MaxLength * MaxLength;
DecimalVals = zeros(size(FullVector,1),noOfValues);

for Idx = 1:size(FullVector,1)
    k = 1;

    for StartByte = 1:MaxLength
        for StartBit = 1:MaxLength
            for SignalLength = MinLength:StepSize:MaxLength
                DecimalVals(Idx,k) = BitCombinations(FullVector,StartByte,StartBit,SignalLength);
                k = k+1;
            end
        end
    end
end

result (on my machine):

time consumption without preallocation: 560 seconds

time consumption WITH preallocation: 300 seconds

Furthermore, please use the MATLAB Profiler (Starting the script by using "Run and Time") to identify the bottleneck, respectively which function takes most time and add the function/line to your question.

Unfortunately, I've got no access to the functions of the Communication System Toolbox, so I used the function bi2de from the File Exchange. In this version, there is one sort of error checking, which takes a lot of time: ~230 seconds

Dammi · Accepted Answer · 2017-01-22 00:08:41Z

Another thing you could do, besides pre-allocating your array, is to not use fliplr. Take a look at this code snippet

tic
N = 10000;
A = [1:N];
for i = 1:N/2
    b = A(N-i+1:-1:i);
end
toc

b = [];
tic
for i = 1:N/2
    b = fliplr(A(i:N-i+1));
end
toc

Elapsed time is 0.060007 seconds. Elapsed time is 0.118267 seconds.

So fliplr is around 2x slower to use, rather than simply use "backwards" indexing. I'm pretty sure you would have something to gain also by making your own bi2de function that is specific to your problem.

I made an attempt on this, haven't checked it for efficiency though, but maybe you can use it for your purposes

function values = myBi2Dec(byte,signalLengths)

persistent indexes
if isempty(indexes)
    % Find the matrix indexes for this 
    indexes = [];
    for iBit = 1:8
        for iSL = signalLengths
            if iBit+iSL-1<=8
                indexes = [indexes;sub2ind([8,8],iBit,iBit+iSL-1)];
            end
        end
    end
end
% Lets get the cumulative value
cumB2D = cumBi2Dec(byte);

% We already calculated their position, so simply return them
values = cumB2D(indexes);

function cumB2D = cumBi2Dec(byte)

persistent B2D
if isempty(B2D)
    B2D = zeros(8,8);
    tmp  = 2.^[0:7];
    for i = 1:8
        B2D(i,i:8) = tmp(1:8-(i-1));
    end
end

cumB2D = cumsum(repmat(fliplr(byte),8,1).*B2D,2);

Then try, for example, myBi2Dec([0,0,0,0,1,1,1,1],[4:2:8])

Collectives™ on Stack Overflow

Using vectorization instead of a 'for Loop' in Matlab

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related