Complexity-free Kolmogorov(-Smirnov)

Question

In statistics, sometimes it's useful to know whether two data samples come from the same underlying distribution. One way to do this is to use the two-sample Kolmogorov-Smirnov test.

Your task will be to write a program that reads in two unsorted nonnegative integer arrays and calculates the main statistic used in the test.

---

Given an array A and a real number x, define the distribution function F by

F(A,x) = (#number of elements in A less than or equal to x)/(#number of elements in A)

Given two arrays A1 and A2, define

D(x) = |F(A1, x) - F(A2, x)|

The two-sample Kolmogorov-Smirnov statistic is the maximum value of D over all real x.

Example

A1 = [1, 2, 1, 4, 3, 6]
A2 = [3, 4, 5, 4]

Then:

D(1) = |2/6 - 0| = 1/3
D(2) = |3/6 - 0| = 1/2
D(3) = |4/6 - 1/4| = 5/12
D(4) = |5/6 - 3/4| = 1/12
D(5) = |5/6 - 4/4| = 1/6
D(6) = |6/6 - 4/4| = 0

The KS-statistic for the two arrays is 1/2, the maximum value of D.

Test cases

[0] [0] -> 0.0
[0] [1] -> 1.0
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] -> 0.2
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] -> 0.4
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] -> 0.5
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] -> 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] -> 0.363636

Rules

• You may write a function or a full program. Input may be via STDIN or function argument, and output may be via STDOUT or return value.
• You may assume any unambiguous list or string format for the input, as long as it is consistent for both arrays
• On the off-chance that your language has a builtin for this, you may not use it.
• Answers need to be correct to at least 3 significant figures
• This is code-golf, so the program in the fewest bytes wins

Answer 1

APL (29 24)

(Thanks to Zgarb for the extra inspiration.)

{⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵}

This is a function that takes the arrays as its left and right arguments.

      8 9 9 5 5 0 3 {⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵} 4 9 0 5 5 0 4 6 9 10 4 0 9 
0.1758241758

Explanation:

{⌈/                                maximum of
   |                               the absolute value of
    -⌿                             the difference between
      ⍺⍵∘.(         )∊⍺⍵          for both arrays, and each element in both arrays
            +/≤                    the amount of items in that array ≤ the element
               ÷                   divided by
                (⍴⊣)              the length of that array
                          }

Answer 2

J - 39

I'm sure can be shorten much more

f=:+/@|:@(>:/)%(]#)
>./@:|@((,f])-(,f[))

Usage

2 10 10 10 1 6 7 2 10 4 7 >./@:|@((,f])-(,f[)) 7 7 9 9 6 6 5 2 7 2 8
0.363636

Answer 3

JavaScript (ES6) 99 119 128

More or less straightforward JavaScript implementation, probably more golfable. In the F function I use > instead of <=, as abs(F(a)-F(b)) === abs((1-F(a))-(1-F(b)))

No more function definition as default parameer in this last edit.

As I said, it's straightforward. The F function is the F function, the D function is the unnamed function used in line 2. It's evaluated using .map for each value present in the two arrays, as the max value for all reals must be one of these. At last, the spread operator (...) is used to pass the D values array as a parameter list to the max function.

K=(a,b)=>Math.max(...a.concat(b).map(x=>
  Math.abs((F=a=>a.filter(v=>v>x).length/a.length)(a)-F(b))
))

Test In FireFox/FireBug console

;[[[0],[0]], [[0],[1]],
[[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
[[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
[[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
[[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
[[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]
.forEach(x=>console.log(x[0],x[1],K(x[0],x[1]).toFixed(6)))

Output

[0] [0] 0.000000
[0] [1] 1.000000
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] 0.200000
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] 0.400000
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] 0.500000
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] 0.363636

Answer 4

Python 3, 132 108 95 88

f=lambda a,x:sum(n>x for n in a)/len(a)
g=lambda a,b:max(abs(f(a,x)-f(b,x))for x in a+b)

The input are 2 lists to the function g

Thanks to: Sp3000, xnor, undergroundmonorail

Line 2, first call to f reads like "fax". I found that mildly amusing

Answer 5

CJam, 33 31 bytes

q~_:+f{\f{f<_:+\,d/}}z{~-z}%$W=

Input is a CJam styles array of the two arrays.

Example:

[[8 9 9 5 5 0 3] [4 9 0 5 5 0 4 6 9 10 4 0 9]]

Output:

0.17582417582417587

Try it online here

Answer 6

Matlab (121)(119)

This is a program that takes two lists throu stdin and prints the result to stdout. It is a strightfwd approcht and I tried to golf it as much as possible. K(a) returns a function that calculates x -> F(a,x). Then the anonymous function @(x)abs(g(x)-h(x)) which corresponds to the function D is applied to every possible integer of 0:max([a,b]) and the maximum of the results is displayed. (arrayfun does the same as map in other languages: it applies a function to every element of a array)

a=input('');b=input('');
K=@(a)@(x)sum(a<=x)/numel(a);
g=K(a);h=K(b);
disp(max(arrayfun(@(x)abs(g(x)-h(x)),0:max([a,b]))))

Answer 7

Erlang, 96 Bytes

edc65's JavaScript solution ported to Erlang.

f(A,B)->F=fun(A,X)->length([V||V<-A,V>X])/length(A)end,lists:max([abs(F(A,X)-F(B,X))||X<-A++B]).

Test:

lists:foreach(fun ([H,T] = L) -> io:format("~p ~p~n", [L, w:f(H, T)]) end, [[[0],[0]], [[0],[1]],
        [[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
        [[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
        [[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
        [[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
        [[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]).

Output:

[[0],[0]] 0.0
[[0],[1]] 1.0
[[1,2,3,4,5],[2,3,4,5,6]] 0.20000000000000007
[[3,3,3,3,3],[5,4,3,2,1]] 0.4
[[1,2,1,4,3,6],[3,4,5,4]] 0.5
[[8,9,9,5,5,0,3],[4,9,0,5,5,0,4,6,9,10,4,0,9]] 0.17582417582417587
[[2,10,10,10,1,6,7,2,10,4,7],[7,7,9,9,6,6,5,2,7,2,8]] 0.36363636363636365

Answer 8

STATA 215

This is 90% getting the input into a format that can be used because STATA already has a ksmirnov command.

di _r(a)
di _r(b)
file open q using "b.c",w
forv x=1/wordcount($a){
file w q "1,"(word($a,`x'))_n
}
forv x=1/wordcount($b){
file w q "2,"(word($b,`x'))_n
}
file close q
insheet using "b.c"
ksmirnov v2,by(v1)
di r(D)

Answer 9

R, 65 bytes

f=function(a,b){d=c(a,b);e=ecdf(a);g=ecdf(b);max(abs(e(d)-g(d)))}

This function takes two vectors as arguments and returns the maximum difference of their empirical cumulative distribution functions.

If built-ins were allowed, it would reduce to mere 12 bytes:

ks.test(a,b)

Answer 10

Mathematica, 76 73 63

Mathematica has the built-in function KolmogorovSmirnovTest, but I won't use it here.

k=N@MaxValue[Abs[#-#2]&@@(Tr@UnitStep[x-#]/Length@#&/@{##}),x]&

Usage:

k[{1, 2, 1, 4, 3, 6}, {3, 4, 5, 4}]

0.5

Answer 11

Quick implementation in Python 3.4.2 (79 bytes):

F=lambda A,x:len([n for n in A if n<=x])/len(A)
D=lambda x:abs(F(A1,x)-F(A2,x))

Example:

>>> A1 = [-5, 10, 8, -2, 9, 2, -3, -4, -4, 9]
>>> A2 = [-5, -3, -10, 8, -4, 1, -7, 6, 9, 5, -7]
>>> D(0)
0.045454545454545414

Answer 12

Java - 633 622 Bytes

Ok,first up, trying to get better at java so thats why i tried it in java, I know i'll never do well, but eh, its fun. second, I honestly thought i could do this in way less, then i got to the stage where there were doubles everywhere, and the method declarations meant using methods only saved 4-5 chars in total. in short, i'm a bad golfer.

edit: usage format> java K "2,10,10,10,1,6,7,2,10,4,7" "7,7,9,9,6,6,5,2,7,2,8"

import java.lang.*;
class K{public static void main(String[]a){double[]s1=m(a[0]);double[]s2=m(a[1]);
int h=0;if(H(s1)<H(s2))h=(int)H(s2);else h=(int)H(s1);double[]D=new double[h];
for(int i=0;i<h;i++){D[i]=Math.abs(F(s1,i)-F(s2,i));}System.out.println(H(D));}
static double[]m(String S){String[]b=S.split(",");double[]i=new double[b.length];
for(int j=0;j<b.length;j++){i[j]=new Integer(b[j]);}return i;}
static double H(double[]i){double t=0;for(int j=0;j<i.length;j++)
{if(i[j]>t)t=i[j];}return t;}
static double F(double[]A,int x){double t=0;double l=A.length;
for(int i=0;i<l;i++){if(A[i]<=x)t++;}return t/l;}}

Answer 13

Haskell 96 83

l=fromIntegral.length
a%x=l(filter(<=x)a)/l a
a!b=maximum$map(\x->abs$a%x-b%x)$a++b

(!) is the kolmogorov-smirnov function which takes two lists

Answer 14

R, 107 bytes

Different Approach

f=function(a,b){e=0
d=sort(unique(c(a,b)))
for(i in d-min(diff(d))*0.8)e=max(abs(mean(a<i)-mean(b<i)),e)
e}

Ungolfed

f=function(a,b){
    e=0
    d=sort(unique(c(a,b)))
    d=d-min(diff(d))*0.8
    for(i in d) {
        f=mean(a<i)-mean(b<i)
        e=max(e,abs(f))
    }
    e
}