Re: [Gretl-devel] Dealing with big(!) matrix

On Sun, 28 May 2017, Riccardo (Jack) Lucchetti wrote: Ok, two more things on this: (1) it turn out that if you combine the matrix-based algorithm with a divide-and-conquer strategy you do get some improvement. (2) The timings of the loop-based versions depend heavily on how many different values are contaned in the column to be serched: this is the scalar called H in the script below. Have fun. <hansl> set verbose off function scalar find_0(const matrix a, scalar column, scalar target) n = rows(a) c = a[,column] .= target if maxc(c) == 0 return NA endif c = selifr(seq(1,n)', c) return c[1,1] end function function scalar find_1(const matrix a, scalar column, scalar target) #n = rows(a) chk = 0 i = 1 loop while !chk --quiet chk = a[i++,column] == target endloop return i-1 end function function scalar find_2(const matrix a, scalar column, scalar target) n = rows(a) loop for i=1..n --quiet if (a[i,column] == target) index = i break endif endloop return index end function function scalar find_3(const matrix a, scalar column, scalar target) n = rows(a) h = floor(n/2) c = find_0(a[1:h,column], 1, target) if ok(c) return c else c = find_3(a[h+1:,column], column, target) endif return c end function n = 50000 H = 450 # try different values here a = mrandgen(i,1,H,n,2) column = 1 rep = 2000 u = mrandgen(i,1,H,n,1) set stopwatch loop i=1..rep find_0(a, column, u[i]) endloop t0 = $stopwatch loop i=1..rep find_1(a, column, u[i]) endloop t1 = $stopwatch loop i=1..rep find_2(a, column, u[i]) endloop t2 = $stopwatch loop i=1..rep find_3(a, column, u[i]) endloop t3 = $stopwatch print t0 t1 t2 t3 </hansl> ------------------------------------------------------- Riccardo (Jack) Lucchetti Dipartimento di Scienze Economiche e Sociali (DiSES) Università Politecnica delle Marche (formerly known as Università di Ancona) r.lucchetti(a)univpm.it http://www2.econ.univpm.it/servizi/hpp/lucchetti -------------------------------------------------------