Non-linear scaling for linear increase in complexity

I have a class which defines an array and then loops over this array updating each element in turn. If I change the length of the array linearly the runtime increases non-linearly. Why? I must be missing something silly.

classdef C
    properties
        N uint32 {mustBeInteger, mustBePositive}
        x (1, :) {mustBeFloat, mustBeNonnegative} = []
    end

    methods
        function c = C(N)
            arguments
                N uint32 {mustBeInteger, mustBePositive}
            end
            c.N = N;
            c.x = zeros(1, c.N);
        end

        function run(c)
            arguments
                c C
            end
            for i = 1:c.N
                c.x(i) = 1;
            end
        end
    end
end

N_range = 1e4:1e4:1e5;
times = zeros(1, length(N_range));
N_i = 1;
for N = N_range
    c = C(N);
    tic
    c.run();
    times(N_i) = toc;
    N_i = N_i + 1;
end
plot(times)

[VBBV]

@James, Thats possibly due to embedded for loop inside the run function which is being called inside another loop .

Answer 1

[Matt J]

It is because you are applying property validations {mustBeFloat, mustBeNonnegative} on the x property. This means that in every iteration of the loop in run(), the code has to do the O(N) work of checking whether the entirety of c.x contains non-negative floats.

You will see that the computation becomes both linear and much faster if you modify the classdef to,

properties

N uint32 {mustBeInteger, mustBePositive}

x

end

N_range = 1e4:1e4:1e5;
times = zeros(1, length(N_range));

for i=1:numel(N_range)

    N=N_range(i);

    c = C(N);

    times(i) = timeit(@c.run);

end

plot( times,'bo-');

●

[James]

Thanks for the updated answer. Interesting that it has to do O(N) work instead of just O(1) for the new assignment.

[Matt J]

It has no way of knowing that you have only updated a single component. The validators mustBeNonnegative and mustBeFloat are only invoked after the modification is made and they receive the entirety of x as input.

BTW, a consequence of this is that mustBeFloat is not really screeing against non-float updates like I think you suppose. You can see this in the example below, which shows that an error is not raised when I assign the non-float uint(10) to c.x(i).

classdef  myclass
    properties
     x {mustBeFloat}
    end
end

>> c=myclass; c.x=rand(1,5);

>> c.x(1)=uint8(10) %non-float assignment

c =

myclass with properties:

x: [10 0.2429 0.2394 0.6772 0.0797]

[James]

Ah OK, that makes sense, thanks for explaining.

[Paul]

Hi Matt,

In your example, when exactly would mustBeFloat catch a problem?

When I look at this section of the doc, it seems to me that just defining

x {mustBeFloat}

should result in a failed assignment of a uint8 into x for the same reason as on that section of the linked doc page where {mustBeNumeric} caused a failed assignment of a char into the Data property that was not defined with an actual class to which a char could be converted.

[Matt J]

@Paul Assigning a non-float vector to x would cause an error. Basically, there is a difference in assigning to c.x and assigning to c.x(i).

c=myclass;

c.x=rand(1,5); 
c.x(1)='A'

c = 
  myclass with properties:

    x: [65 0.4349 0.8522 0.9195 0.1168]

But,

c.x=uint8(1:5)

Error setting property 'x' of class 'myclass'. Value must be a floating-point array.

[Paul]

I poked around on a couple of other doc pages and I didn't see anything on point, i.e., that property validation functions do not apply on indexed assignment to a property. Is that not a simple way for a user to circumvent property validation, at least in some cases?

c = myclass

c = 
  myclass with properties:

    x: []

The user of the class can't do this

try
    c.x = 'a';
catch ME
    ME.message
end

ans = 'Error setting property 'x' of class 'myclass'. Value must be a floating-point array.'

But this assignment is no problem.

c.x(1) = 'a'

c = 
  myclass with properties:

    x: 97

Is there any way to define a class to preclude assignments such as above? Would that entail validation of the right hand side in the subsassgn (or the mixin.indexing function) ?

[Matt J]

Would that entail validation of the right hand side in the subsassgn (or the mixin.indexing function) ?

It would, I think.

The property validators are meant just to be a shorthand for the set.property() methods, it seems. The same limitations exist there.

[Matt J]

Note also this nuance,

classdef  myclass

    properties
     x double {mustBeFloat}
    end

end

>> c.x=uint8(1:5)

c =

myclass with properties:

x: [1 2 3 4 5]

This worked fine, apparently because the 'double' converter specification on the x-property is applied before the mustBeFloat or any other validators.

[Paul]

Yes, that behavior is documented.

[Matt J]

I poked around on a couple of other doc pages and I didn't see anything on point, i.e., that property validation functions do not apply on indexed assignment to a property.

Perhaps, but you can see when you write a custom validation function that the function receives the entire candidate variable to be stored in the property, and not just the data from the right hand side of the subsasgn. This means that, in an indexed assignment, a conversion of the right hand side data to the left hand side data's class must implictly occur. And, naturally, if that will be true for custom functions, it will be true for built-in validators as well:

classdef myclass
    properties
        x {mustBeNumel3(x)} = 1:3
    end
end
function mustBeNumel3(a)

    disp ' '
    disp("a="), disp(a);

    assert(numel(a)==3, 'Improper Length')

end

>> clear classes

>> c=myclass;

a=

1 2 3

>> c.x=4:6;

a=

4 5 6

>> c.x(3)=7;

a=

4 5 7

>> c.x(3)=[]

a=

4 5

Error setting property 'x' of class 'myclass'. Improper Length

[Paul]

Would that entail validation of the right hand side in the subsassgn (or the mixin.indexing function) ?

Actually, does subsasgn really come into play here for the example as presented? Thinking about it some more, I think subsasgn (or mixin.indexing function) would come into play only for subscripted assignment into an array of c objects, but here we're talking about c.x, which would just use the subsasgn for ordinary double, wouldn't it? Seems like the only way, or at least one way, to protect against indexed assignment into c.x with an invalid type would be for c.x itself to be a class instance and that class would have the check built into its subsasgn.

[Matt J]

Seems like the only way, or at least one way, to protect against indexed assignment into c.x with an invalid type would be for c.x itself to be a class instance and that class would have the check built into its subsasgn.

I agree it would be one way, but not the only way. If you provide an overloaded subsasgn for c, it will be called by c.x(i)=rhs and give you access to rhs.

[Paul]

Ah yes. I was too focused on subsasgn as applied to paren indexing on c, which is not applicable here. But now I realize that subsasgn on c will be called on c.x(i) = rhs because of the dot indexing on c, at which point one could enforce constraints on rhs.