IndexError: index 0 is out of bounds for axis 0 with size 0

[cool-RR]

Running this code under Python 3.8 produced the following traceback. Note that it seems that max_n=10**7 is related to this bug, because it didn't happen before I used that.

Traceback (most recent call last):
  File "heapz.py", line 115, in <module>
    best, others = big_o.big_o(heapify, data_generator_heapify, max_n=10**6)
  File "C:\Program Files\Python38\lib\site-packages\big_o\big_o.py", line 157, in big_o
    return infer_big_o_class(ns, time, classes, verbose=verbose)
  File "C:\Program Files\Python38\lib\site-packages\big_o\big_o.py", line 97, in infer_big_o_class
    residuals = inst.fit(ns, time)
  File "C:\Program Files\Python38\lib\site-packages\big_o\complexities.py", line 38, in fit
    return residuals[0]
IndexError: index 0 is out of bounds for axis 0 with size 0

[lucasalavapena]

I did some debugging and testing. Like you mentioned this happens at larger max_n, as in the error message it also happens with max_n=10**7. I tried remove different classes and I think the error seems to occur specifically for the Cubic class, for others not. If you follow the error precisely, you see that coeff, residuals, rank, s = np.linalg.lstsq(x, y, rcond=-1) (here) we get an empty numpy vector for the residual for the Cubic case when max_n is large, the reason being that the rank of x is too small (see the relevant numpy docs) and thus numpy gives one an empty array. I think you should be able to compute the residual doing something like np.linalg.norm(y - x @ coeff) which would still work in this case, however, doing that give different residual from numpy.

Why this specifically happens for the Cubic case, I cannot tell you. I tried this also for another case that I made up and again for large max_n specifically the Cubic case has this problem.

[Tachyon5]

Did this get resolved? Seems like @lucasalavapena got to the bottom of it.

[dakra137]

I used the following to avoid Cubic:

ALL_EXCEPT_CUBIC = [big_o.complexities.Constant, 
		big_o.complexities.Logarithmic, 
		big_o.complexities.Linear, 
		big_o.complexities.Linearithmic, 
		big_o.complexities.Quadratic, 
		big_o.complexities.Polynomial, 
		big_o.complexities.Exponential]

best, others = big_o.big_o(functionname, big_o.datagen.n_, 
		classes=ALL_EXCEPT_CUBIC, 
		min_n=210000, max_n=2100000, n_measures=100)

The failure still happens, even without Cubic, at larger , such as when min_n=30000000, max_n=300000000, n_measures=100

[pberkes]

@dakra137 which complexity class fails? I think it's just a matter of numerical overflow errors. NumPy uses C-types for efficiency reasons, and so can only represent numbers up to a given size. For an n that is too large, you'll run into overflow errors.

For instance:

>>> n = np.array(30000000)
>>> n ** 3
-6033323910783565824

Is your code is so fast that it requires n's that are that high? In that case, you might think about wrapping your function into another function that executes the first 10000 times.

[dakra137]

@pberkes Cubic fails. These are a new prime number sieve (Kra) as compared to other sieves, such as Sundaram, Atkin, Euler, Pritchard, Eratosthenes and improvements to it. Mine has considerable initialization overhead and some per sieving prime overhead, so its efficiency shows only for large N.

best, others = big_o.big_o(s, big_o.datagen.n_, classes=ALL_EXCEPT_CUBIC, min_n=1021020, max_n=102102000, n_measures=100)

Question: Is what is called polynomial what others call a power law, t=a+n**b ?
Some results are given as
Polynomial: time = 2.9E-08 * x^1.1 (sec)
But most show a power of 1

The following results seem inconsistent:
A. Constant vs. Exponential with base=1 Shouldn't the constant time be the same as the exponential multiplier where 1^n, a? Shouldn't a be the same for
t=a
t=a * 1^n

B. Linear vs. "Polynomial" with power == 1 Shouldn't the constants be the same for linear and polynomial when the polynomial power is 1?
t=a + bn
t=a + b n^1

A. Constant vs. Exponential with base=1

SieveKra12	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.0045 + 6.1E-08*n (sec)
residuals=	3.280e+02	class=	Constant: time = 3.2 (sec)	SieveKra12
residuals=	1.076e+02	class=	Exponential: time = 0.57 * 1^n (sec)	SieveKra12

SieveSundaramj	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = -0.016 + 4.8E-09*n*log(n) (sec)
residuals=	6.825e+02	class=	Constant: time = 4.4 (sec)	SieveSundaramj
residuals=	2.568e+02	class=	Exponential: time = 0.69 * 1^n (sec)	SieveSundaramj

SieveEuler	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.29 + 3.6E-07*n (sec)
residuals=	1.152e+04	class=	Constant: time = 18 (sec)	SieveEuler
residuals=	4.225e+03	class=	Exponential: time = 3.1 * 1^n (sec)	SieveEuler

SieveAtkinSOj	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.55 + 1.3E-06*n (sec)
residuals=	1.472e+05	class=	Constant: time = 67 (sec)	SieveAtkinSOj
residuals=	5.180e+04	class=	Exponential: time = 11 * 1^n (sec)	SieveAtkinSOj

SieveEratosthenes0	start=	1021020	stop=	102102000	steps=100	Polynomial: time = 4.2E-07 * x^1.1 (sec)
residuals=	1.510e+05	class=	Constant: time = 65 (sec)	SieveEratosthenes0
residuals=	5.619e+04	class=	Exponential: time = 10 * 1^n (sec)	SieveEratosthenes0

SieveEratosthenes1	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = 0.15 + 1.5E-08*n*log(n) (sec)
residuals=	7.189e+03	class=	Constant: time = 14 (sec)	SieveEratosthenes1
residuals=	2.715e+03	class=	Exponential: time = 2.3 * 1^n (sec)	SieveEratosthenes1

SieveEratosthenes2	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.22 + 2.6E-07*n (sec)
residuals=	5.851e+03	class=	Constant: time = 13 (sec)	SieveEratosthenes2
residuals=	2.185e+03	class=	Exponential: time = 2.2 * 1^n (sec)	SieveEratosthenes2

SieveEratosthenes3	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = -0.0065 + 9.4E-09*n*log(n) (sec)
residuals=	2.654e+03	class=	Constant: time = 8.7 (sec)	SieveEratosthenes3
residuals=	1.079e+03	class=	Exponential: time = 1.3 * 1^n (sec)	SieveEratosthenes3

SieveEratosthenes4	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = -0.0034 + 5.6E-09*n*log(n) (sec)
residuals=	9.457e+02	class=	Constant: time = 5.2 (sec)	SieveEratosthenes4
residuals=	3.892e+02	class=	Exponential: time = 0.79 * 1^n (sec)	SieveEratosthenes4

SieveEratosthenes5	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.13 + 9.6E-08*n (sec)
residuals=	8.041e+02	class=	Constant: time = 4.8 (sec)	SieveEratosthenes5
residuals=	3.311e+02	class=	Exponential: time = 0.76 * 1^n (sec)	SieveEratosthenes5

SieveEratosthenes6	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = 0.034 + 4.4E-09*n*log(n) (sec)
residuals=	5.766e+02	class=	Constant: time = 4.1 (sec)	SieveEratosthenes6
residuals=	2.240e+02	class=	Exponential: time = 0.65 * 1^n (sec)	SieveEratosthenes6

SieveEratosthenes7	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.1 + 8.3E-08*n (sec)
residuals=	5.918e+02	class=	Constant: time = 4.2 (sec)	SieveEratosthenes7
residuals=	2.243e+02	class=	Exponential: time = 0.68 * 1^n (sec)	SieveEratosthenes7

SievePritchard	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = -7.6 + 1.8E-07*n*log(n) (sec)
residuals=	9.920e+05	class=	Constant: time = 1.6E+02 (sec)	SievePritchard
residuals=	3.596e+05	class=	Exponential: time = 23 * 1^n (sec)	SievePritchard

B. Linear vs. "Polynomial" with power == 1

SieveEuler	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.29 + 3.6E-07*n (sec)
residuals=	5.585e-01	class=	Linear: time = -0.29 + 3.6E-07*n (sec)	SieveEuler
residuals=	1.703e+00	class=	Polynomial: time = 1.9E-07 * x^1 (sec)	SieveEuler

SieveAtkinSOj	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.55 + 1.3E-06*n (sec)
residuals=	8.317e+00	class=	Linear: time = -0.55 + 1.3E-06*n (sec)	SieveAtkinSOj
residuals=	8.655e+00	class=	Polynomial: time = 9.7E-07 * x^1 (sec)	SieveAtkinSOj

SieveEratosthenes1	start=	1021020	stop=	102102000	steps=100	Linearithmic: time = 0.15 + 1.5E-08*n*log(n) (sec)
residuals=	1.169e+00	class=	Linear: time = -0.39 + 2.9E-07*n (sec)	SieveEratosthenes1
residuals=	1.205e+00	class=	Polynomial: time = 1.2E-07 * x^1 (sec)	SieveEratosthenes1

SieveEratosthenes2	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.22 + 2.6E-07*n (sec)
residuals=	1.037e+00	class=	Linear: time = -0.22 + 2.6E-07*n (sec)	SieveEratosthenes2
residuals=	1.751e+00	class=	Polynomial: time = 1.4E-07 * x^1 (sec)	SieveEratosthenes2

SieveEratosthenes7	start=	1021020	stop=	102102000	steps=100	Linear: time = -0.1 + 8.3E-08*n (sec)
residuals=	1.777e-01	class=	Linear: time = -0.1 + 8.3E-08*n (sec)	SieveEratosthenes7
residuals=	2.188e-01	class=	Polynomial: time = 3.5E-08 * x^1 (sec)	SieveEratosthenes7

[pberkes]

"Cubic fails": does my explanation of why it fails solve the issue?

Then you open what seems to be a separate issue... it would be better to track separately. My guess for this other issue is that it's just the way the equations are printed out.
For instance, in 3.5E-08 * x^1 the exponent is probably something like 1.00001 or another number very close to 1:

>>> f = 'time = {:.2G} * {:.2G}^n'
>>> f.format(0.57, 1.00001)
'time = 0.57 * 1^n'

Can you check the actual values in the class?

[dakra137]

Appreciation

Thank you replying and especially for structuring the code to make it easy to figure out how to add complexity patterns, such as

class NLogLogN(ComplexityClass): # added by dakra
    order = 43

    def _transform_n(self, n):
        return np.vstack([np.ones(len(n)), n * np.log(np.log(n))]).T

    @classmethod
    def format_str(cls):
        return 'time = {:.4G} + {:.4G} *n*log(log(n))'

class NLogNLogLogN(ComplexityClass): # added by dakra
    order = 45

    def _transform_n(self, n):
        return np.vstack([np.ones(len(n)), n * np.log(n) * np.log(np.log(n))]).T

    @classmethod
    def format_str(cls):
        return 'time = {:.4G} + {:.4G} *n*log(n)*log(log(n))'

Do these additions require, for each, that I also define:

def _transform_time(self, t):
and
def _inverse_transform_time(self, t):

When are they required?

Format strings

Changing the format strings was helpful. Increasing the number of digits in the format string, got the power law "polynomial" complexity to show the power as being more than 1, but the exponential time model seems to be stuck at 1.

residuals=	5.911e+00	class=	Exponential: time = 0.11666371 * 1^n (sec)	SieveKra12
residuals=	9.041e-03	class=	Polynomial: time = 8.917E-09 * n^1.02291 (sec)	SieveKra12

Exceeding limits:

Quadratic also failed when N was up to 204204000