12
\$\begingroup\$

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

14 Answers 14

10
\$\begingroup\$

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
                          }
\$\endgroup\$
  • \$\begingroup\$ I didn't know you could do ⍺⍵! That's handy. \$\endgroup\$ – Zgarb Feb 2 '15 at 11:08
  • 1
    \$\begingroup\$ Also, I think ⍳⌈/ is unnecessary, since the maximum is obtained exactly at one of the array values. \$\endgroup\$ – Zgarb Feb 2 '15 at 11:54
  • \$\begingroup\$ @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.) \$\endgroup\$ – marinus Feb 2 '15 at 13:52
  • 2
    \$\begingroup\$ This is true sorcery, right here. \$\endgroup\$ – Steven Lu Feb 2 '15 at 23:15
  • \$\begingroup\$ @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. \$\endgroup\$ – marinus Feb 8 '15 at 4:57
4
\$\begingroup\$

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

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 2 '15 at 23:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Kroltan Feb 2 '15 at 23:13
  • \$\begingroup\$ you don't need len, read the comment again :P \$\endgroup\$ – undergroundmonorail Feb 3 '15 at 9:51
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – flawr Feb 2 '15 at 10:09
  • \$\begingroup\$ @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...) \$\endgroup\$ – edc65 Feb 2 '15 at 10:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Optimizer Feb 2 '15 at 10:16
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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]))))
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Sp3000 Feb 2 '15 at 22:11
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ The requirement is to find the maximum value of D(x) for all integers values of x. Please comply to the problem spec. \$\endgroup\$ – Optimizer Feb 2 '15 at 9:39
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Sp3000 Feb 2 '15 at 9:44
  • \$\begingroup\$ Also I've added some syntax highlighting - I think it makes it look prettier :) \$\endgroup\$ – Sp3000 Feb 2 '15 at 9:45
  • \$\begingroup\$ Sorry about that, I'm new here. \$\endgroup\$ – Kapten Feb 2 '15 at 9:45
  • \$\begingroup\$ No problems :) If anything's unclear, you can ask in the comments. But once again, welcome! \$\endgroup\$ – Sp3000 Feb 2 '15 at 9:48
0
\$\begingroup\$

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;}}
\$\endgroup\$
  • \$\begingroup\$ you were right. updating. \$\endgroup\$ – Bryan Devaney Feb 2 '15 at 16:02
0
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – MtnViewMark Feb 3 '15 at 2:15
0
\$\begingroup\$

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
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.