Question
· Oct 28, 2016

Max function for the set of parameters

#ObjectScript #Caché

There is an interesting discussion in the Russian forum going. 

What is the best solution for the function which returns the max for the set of parameters?

From the listed solutions I like this one:

ClassMethod max(args...) {
  for i=1:1:args {  s max(+$g(args(i))) = i }
  s i="", max=$o(max(i),-1, i) Q $lb(max, i)
}

It's great to see when Globals (or Locals in this case) are used in so elegant way.

Your variant?

Discussion (8)1
Log in or sign up to continue
Alexey Maslov · Oct 29, 2016

I agree, it's elegant, but not memory efficient design: the sorted array is built only to pick up its top node. Of course, arg lists are rarely long and yet another small array doesn't mean much, but in more generic case of searching the max element in array of sufficient size the following code should be twice more memory efficient and maybe a bit faster:

ClassMethod max(args...) {
  s max=$g(args(1)),im=1 for i=2:1:args s:max<$g(args(i)) max=args(i),im=i
  q $lb(max,im)
}

P.S. I was curious if my variant was really faster and ran some tests. Here are the results that were collected using an array filled with random whole numbers. An array was refilled on each test run. 

In the table below:
 min - the lower limit of numbers values in the array
 max- the upper limit of numbers values in the array
 n - the quantity of numbers in the array
 var - # of variant (1 - original, 2 - mine)
 dt - average run time (in seconds)
 dtfill - avg time of filling the array; just for info.

min       max       n         var  dt        dtfill
-10000000 10000000  10        1    0.000005  0.000002
-10000000 10000000  10        2    0.000001  0.000002
-10000000 10000000  100       1    0.000047  0.000012
-10000000 10000000  100       2    0.000004  0.000012
-10000000 10000000  1000      1    0.000425  0.000115
-10000000 10000000  1000      2    0.000031  0.000115
-10000000 10000000  10000     1    0.005828  0.002949
-10000000 10000000  10000     2    0.000554  0.002949
-10000000 10000000  100000    1    0.074641  0.031128
-10000000 10000000  100000    2    0.006824  0.031128
-10000000 10000000  1000000   1    1.194625  0.313878
-10000000 10000000  1000000   2    0.069191  0.313878
1 0
Alexey Maslov · Oct 31, 2016

The version of Caché is 2015.1.4 for Windows x64, on Core i5 based laptop. When I have a time gap, I'd re-run this test on more powerful server, while I don't expect a noticeable difference.

Let's try to estimate time for both operations:
1: set max(args(i))=i ~ time_to_find_args(i)_position_in_max_array + time_to_allocate_memory_for_max(args(i)) ~  O(ln(length(args(i))) + O(length(args(i)+length(i))) ~ O(3*ln(length(args(i)))
2: max<args(i)  ~ time_to_compare_max_and_args(i) ~ O(ln(length(args(i))))

So it seems that 2 should be ~3 times quicker than 1, but we don't know real coefficients which stand behind those O() estimations. I should confess that local array node allocation penalty turned to be higher than I expected.

This speed difference should be even more would args(i) values be strings rather than numbers.

0 0