# Complexity-free Kolmogorov(-Smirnov)

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 , so the program in the fewest bytes wins
• Are all inputs going to be integer arrays, or can they contain floating points? Commented Feb 2, 2015 at 10:20
• @KennyTM Just nonnegative integers. I thought I'd keep things simple. Commented Feb 2, 2015 at 10:22
• Is there a maximum value we can assume for arrays? (E.g. all entries of A are below length(A)?) Commented Feb 2, 2015 at 11:12
• @flawr No you can't assume a maximum value Commented Feb 2, 2015 at 11:18
• I like the title. I'm stile targeting the kolmogorov complexity bagde, but not this time. Commented Feb 2, 2015 at 11:29

## 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
}

• I didn't know you could do ⍺⍵! That's handy. Commented Feb 2, 2015 at 11:08
• Also, I think ⍳⌈/ is unnecessary, since the maximum is obtained exactly at one of the array values. Commented Feb 2, 2015 at 11:54
• @Zgarb: you're right of course, I just have to test for each possible array value. That means I can get rid of the 0, too, as it'll test for that if the array contains it. Thanks! (And that'll teach me, as usually if you have to add in a special case, that means the algorithm isn't simple enough.) Commented Feb 2, 2015 at 13:52
• This is true sorcery, right here. Commented Feb 2, 2015 at 23:15
• @Sp3000: did you write the one-element arrays correctly? You can't just write 1, as that would be a scalar. You should write (,1) instead. If you do that, it works. Commented Feb 8, 2015 at 4:57

# 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

• Does this create a function or use stdin/stdout? What does the second part exactly do? (Looks a bit long for a function call?) Commented Feb 2, 2015 at 11:06
• @flawr A function, similar to APL Commented Feb 2, 2015 at 11:08
• I think you could avoid explicitly defining f if you use something like >./@:|@({.-{:)f"1@, but I'm not quite sure. Commented Feb 2, 2015 at 13:27

# 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

• I am curous about your function K: Is it correct that you define other functions F,D in the argument list? Does this behave like some optional arguments or so? Commented Feb 2, 2015 at 10:09
• @flawr yes, they are optional arguments with a default value. So avoiding the pollution of global variable space (that's not a problem in code golf, but anyway...) Commented Feb 2, 2015 at 10:14
• Plus, since the function already required 2 variables (thus the brackets), it would be 2 extra bytes to move those variables out of the option var list to inside of the function body. Commented Feb 2, 2015 at 10:16

# Python 3, 13210895 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

• To count the number of elements of a list that satisfy a property, it's shorter to do sum(n>x for n in a). Also, it looks like you're not using s=filter. And for max, you don't actually need the list brackets; Python lets the function parens double as comprehension parens.
– xnor
Commented Feb 2, 2015 at 23:06
• Thanks! I used filter in a previous version, forgot to remove it. Sadly I can't remove the first pair of square brackets since then it will be a generator, which has no len. Commented Feb 2, 2015 at 23:13
• you don't need len, read the comment again :P Commented Feb 3, 2015 at 9:51

# 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 ## 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]))))  # 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  ## 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)  • Oh wow, I didn't think that languages would have a builtin for this... I just did some research and I decided it would be best to disallow builtins from now on, but you can keep this because it was posted before the rule change :) Commented Feb 2, 2015 at 22:11 ## 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)  # 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 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  • The requirement is to find the maximum value of D(x) for all integers values of x. Please comply to the problem spec. Commented Feb 2, 2015 at 9:39 • Welcome! As Optimizer says, the task is to find the maximum value of D, not to just implement D as a function. Also, I'm sorry if I wasn't clear, but you can't assume that A1 and A2 are already defined variables (you can put them in the lambda though, e.g. lambda x,A1,A2: - that's okay) Commented Feb 2, 2015 at 9:44 • Also I've added some syntax highlighting - I think it makes it look prettier :) Commented Feb 2, 2015 at 9:45 • Sorry about that, I'm new here. Commented Feb 2, 2015 at 9:45 • No problems :) If anything's unclear, you can ask in the comments. But once again, welcome! Commented Feb 2, 2015 at 9:48 ## 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;}}  • you were right. updating. Commented Feb 2, 2015 at 16:02 # 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

• some quick golfs: use map rather than fmap; use maximum rather than foldr1 max; define l=fromIntegral.length and you can get rid of i, and then you can shorten % to l(filter(<=x)a)/l a. Gets it down to 84! Commented Feb 3, 2015 at 2:15

# 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
}