Can this algorithm be made more efficient?

[440bx]

The problem is clearly defined. It is a straight forward statistical function.

Now I really have to disagree.  There are many questions that so far are left unanswered.  Among them:

1. what is the valid range of the data ?.  Obviously, it isn't 1 to several trillions.
2. how are duplicate values in either or both tables supposed to be handled ? ... are they even valid ?
3. what should the result be if the 2 tables are identical ?  is that an indication of invalid data ?
4. what should be done if the maximum value in one of the arrays is smaller than the smallest value in the other array.

None of these questions, which are critical in the implementation of a _valid_ algorithm have been answered.

[VTwin]

The problem is clearly defined. It is a straight forward statistical function.

Now I really have to disagree.  There are many questions that so far are left unanswered.  Among them:

1. what is the valid range of the data ?.  Obviously, it isn't 1 to several trillions.
2. how are duplicate values in either or both tables supposed to be handled ? ... are they even valid ?
3. what should the result be if the 2 tables are identical ?  is that an indication of invalid data ?
4. what should be done if the maximum value in one of the arrays is smaller than the smallest value in the other array.

None of these questions, which are critical in the implementation of a _valid_ algorithm have been answered.

1. Within the range of an IEEE double.
2. That is handled in the algorithm.
3. The function returns 0.5.
4. That is handled in the algorithm.

Cheers,
VTwin

[Thaddy]

1. Within the range of an IEEE double.
2. That is handled in the algorithm.
3. The function returns 0.5.
4. That is handled in the algorithm.

Cheers,
VTwin

I concur. If one has brains, use them, If one has eyes, try to find a way to use them.  These eyes may be useful.

[juanba]

Welcome to the forum!

What result does your function give? Your attachment has zero bytes.

Thanks for your welcome.
Sorry about my delay in answering. Blame it to my living in the Central European Timezone.
I have been polishing my routine for optimizing the CLES algorithm and measuring the results. In my solution I use static arrays, QuickSort and (integer)counting of the "Greater than" and "Equal to" events. I am not completely sure of the correctness of the program but I have checked the results against the original solution and they match 100% every time.
Here is the code:

Code: Pascal  [Select][+][-]

1. function CalcCles2: double;
2. var p1, p2e, p2: longint;
3.     cles: double;
4. begin
5.   QuickSort1(1, n1);
6.   QuickSort2(1, n2);
7.  
8.   p1 := 1;                             // Set1 index
9.   p2 := 1;                             // Set2 index such that set1[p1] > set2[p2]
10.   p2e := 0;                            // Set2 index such that set1[p1] = set2[p2e]
11.   mayor := 0;                        // number of comparisons resulting in >
12.   igual := 0;                          // number of comparisons resulting in =
13.                                            // Find the first set1[p1] >= set2[1]
14.   while (p1 <= n1) and (Set1[p1] < Set2[p2]) do
15.     Inc(p1);
16.   repeat
17.     if p1 > n1 then
18.       break;
19.                                      // if p1 > n1, we are done
20.                                      // Otherwise find the greatest p2 for wich
21.                                      // still holds that set1[p1] > set2[p2]
22.     while (p2 < n2) and (Set1[p1] > Set2[p2 + 1]) do
23.       Inc(p2);
24.  
25.     if (Set1[p1] = Set2[p2]) then
26.       Inc(igual)
27.     else
28.       mayor := mayor + p2;            // set[p1] is greater than all set2[p2]
29.                                                    // with p2 going down to 1
30.                                                    // Now find how many set2[] are equal
31.                                                    // to set1[p1] (if any)
32.     p2e := p2;
33.     while (p2e < n2) and (Set1[p1] = Set2[p2e + 1]) do
34.       Inc(p2e);
35.  
36.     if (p2e > p2) then
37.       igual := igual + (p2e - p2);
38.                                        // If set1[p1] is repeated in set1, we already
39.                                        // know how to deal with it but I don't think
40.                                        // it is worth while working along this line.
41.                                        // Finished with this p1. Move to the next i
42.     Inc(p1);
43.   until p1 > n1;
44.   cles := (igual * 0.5 + mayor) / (1.0 * n1 * n2);
45.   Result := cles;
46. end;
47.  

And these are the running times for different array sizes:

N1	N2	Time_Orig	Time_Optim	GreaterThan	EqualTo
1000	1000	7.3 mSec	630 µSec	514394	9955
2000	2000	30.4 mSec	1.1 mSec	1974194	39658
5000	5000	188.8 mSec	4.7 mSec	12305492	249907
10000	10000	766.0 mSec	7.8 mSec	49665474	1000512
20000	20000	3.057 Sec	19.5 mSec	195803601	3999005
50000	50000	19.04 Sec	101.5 mSec	1244310857	25009431
100000	100000	78.46 Sec	358.0 mSec	4931215181	100007235

The times include QuickSorting both arrays in the optimized routine. It seems to me that the "sorting before" approach is very reasonable. It does not cause execessive overload and makes possible a speed increase of over 200-fold for the 100000 items arrays. I have measured the time spent in QuickSorting and in this case it consumes 69ms out of the total 358 in sorting both 100000-item arrays. So most of the time is spent in running the CLES algorithm.
It would be interesting what is the impact of using dynamic arrays on routine speed. I may try it this afternoon if the soccer championship and the Tour de France are not very interesting.

[VTwin]

In my solution I use static arrays, QuickSort and (integer)counting of the "Greater than" and "Equal to" events. I am not completely sure of the correctness of the program but I have checked the results against the original solution and they match 100% every time.
...
It would be interesting what is the impact of using dynamic arrays on routine speed. I may try it this afternoon if the soccer championship and the Tour de France are not very interesting.

I am not completely sure of the correctness of your program either. Enjoy the games.

[VTwin]

To elaborate:

4. That is handled in the algorithm, and the function returns 0 or 1.

@Thaddy 

[Thaddy]

To elaborate:

4. That is handled in the algorithm, and the function returns 0.

@Thaddy 

Actually 42 ms (on a raspberry pi 3) but cheers,it is magnitudes faster.

[440bx]

1. Within the range of an IEEE double.
2. That is handled in the algorithm.
3. The function returns 0.5.
4. That is handled in the algorithm.

Cheers,
VTwin

You just discovered the fountain of youth.  Have your age stored in an IEEE double to ensure you have a long life.   

Cheers!.

[juanba]

The algorithm computes something called the "common language effect size" (cles) in statistics. The core of it is simple : given 2 lists of numbers or "scores" you compare all pairs in the lists and if the score in list1 is higher than the score in list2 you add 1 to the numerator of the effect size fraction and if the scores are equal you add 0.5 to the numerator. Finally you divide the numerator by the total number of comparisons (length(list1) *  length(list2)).
Two versions of this algorithm are available on Github in Python. The above algorithm is included but is described as "naive", however not knowing Python I don't understand how the other more efficient one works. With just a small number of values in the lists it's not too bad but with thousands it will be very slow. Any suggestions? Thanks.

Although it has been discussed in some (or many) of the previous posts I failed to grasp the
importance of repeated or equal values in the arrays. The algorithm has to find the equality of
elemntes between one array and the other, which suggests (at least to me) that it is likely that
there are repeated values within each of the arrays. The example given in the initial post contains
duplicated values in both arrays. If that is the case this feature can be used to speed up the
algorithm provided of course that the arrays are ordered. I heve developed an algorithm based on these
ideas:
- Do not do the calculations inside the loop. Rather count how many s1 > s2 ("GreaterThan") and how
many s1 = s2 ("EqualTo") events are and do the math at the end.
- Start the loop at the High end of the arrays and work all the way down to 1 (for results comparable
 to the BruteForce approach) or 0. Working this way makes the program more understandable, at
 least to me.
- Consider the sorted arrays as a sucession of chunks or segments with one or more equal values.
- For each segment in set1 find the segment in set2 which has the same value. If it exists, the
number of EqualTo events is the same as the length of the segment. Then find the higher segment
in set2 that is less than the value of the segment in set1. The number of GreaterThan events is
given by the highest position of the set2 segment.
- Once the values GreaterThan and EqualTo are calculated for the segment in set1 multiply them times
the length of this segment since all its items have the same value and therefore get the same
events. This can save a lot of time. If for instance the average segment is 10 items long, the
total time would be reduced to roughly one tenth.
- Move down to the previous (lower index since I work top to bottom) set1 segment and repeat the
process until the beginning of set1 is reached.
- And now do the calc. Watch for overflows that could happen with more than 50000 items in the arrays.

I have programmed this algorithm in a fully commented procedure (name CalcCles2) and have used it
to build a little test program (inspired in one of the examples posted) and will try to attach it
here. I am getting run times of 3,5 Ticks versus 3800 ticks of the bruteforce approach for 20000
item arrays. And the two calculations are coincidental to at least 9 decimal places.
And yes, I think this time I got it right.
Anyway it would be interesting to know if my asumptions about repeated values are correct,
Cheers.

[Thaddy]

- As OP stated, his data is not normal.
- As he also stated the implementation is for the exact solution, not the guesstimate.
And the solution for the latter was already given too. Read the whole thread.

There's nothing worse than a programmer trying to understand statistics....

[egsuh]

What is your intended result, if

set1 = [5];
set2 = [5,5,5];    // this is possible as this is array, net set.


Then should the result (num)  1.5?

[Thaddy]

[This syntax is not possible if "set2" is a dynamic array.
set2 = [5,5,5];    // this is wrong syntax for type declaration for dynamic arrays. You can't assign and auto-construct in the type declaration.

This is possible (in trunk), however:
set2 := [5,5,5]; // auto constructor to dynamic array of 3 elements that all have value 5

But set2 needs to be a dynamic array, not a set...

Of course you can not call a constructor in a type declaration 

[segfault]

Hi Thaddy, I was wondering if you could initialise a dynamic array before I saw your post, and according to the docs you can use the type.create() syntax, eg :

Code: Pascal  [Select][+][-]

1. type
2.   Tvector = array of real;
3. var
4.    v1, v2 : Tvector;
5. begin
6.   v1 := Tvector.create(5,5,5);
7.   v2 := Tvector.create(5);
8. end.

BTW, I shouldn't have named those arrays "set1" and "set2" in my initial post because it's bit misleading (they're not sets in the pascal sense).

[Thaddy]

Yes, but in trunk you have the implicit array constructor as per my code example:

Code: Pascal  [Select][+][-]

1. {$mode objfpc}
2. var
3.   x:array of integer;
4.   v:integer;
5. begin
6.   // use implicit array constructor;
7.  x :=[5,6,7,8,9];
8.  for v in x do write(v:3);
9. end.

[VTwin]

What is your intended result, if

set1 = [5];
set2 = [5,5,5];    // this is possible as this is array, net set.


Then should the result (num)  1.5?

Assuming you corrected the syntax, the result would be 0.5.