Max function for the set of parameters

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 {  max(+$g(args(i))) = }
  i=""max=$o(max(i),-1, iQ $lb(maxi)
}

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

Your variant?

  • + 1
  • 0
  • 357
  • 6
  • 2

Answers

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...) {
  max=$g(args(1)),im=1 for i=2:1:args s:max<$g(args(i)) max=args(i),im=i
  $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

I've amended the testing result due to some inaccuracy found.

New results surprised me as I didn't expect to scan a local array about 10 times faster than to create a new one. 

Alexey! What a research! Thank you!

So, "if" is faster than "set in local array" approximately ten times and even more. What is the version? 

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.

Comments

ClassMethod Max(args...)
{
    q:(+$g(args)<2) $lb($g(args(+$g(args))),+$g(args))

    s max=$g(args(1))
    for i=2:1:args { s:($g(args(i))]]max) max=$g(args(i)),maxI=}
    q $lb(max,$g(maxI,1))
}