In der Statistik ist es manchmal hilfreich zu wissen, ob zwei Datenstichproben aus derselben zugrunde liegenden Verteilung stammen. Eine Möglichkeit hierfür ist die Verwendung des Kolmogorov-Smirnov-Tests mit zwei Stichproben .

Ihre Aufgabe besteht darin, ein Programm zu schreiben, das zwei unsortierte nichtnegative Ganzzahl-Arrays einliest und die im Test verwendete Hauptstatistik berechnet.

Definieren Sie die Verteilungsfunktion für ein Array Aund eine reelle Zahl mitxF

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

Gegeben zwei Arrays A1und A2definieren

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

Die Kolmogorov-Smirnov-Statistik mit zwei Stichproben ist der Maximalwert von Dover all real x.

Beispiel

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

Dann:

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

Die KS-Statistik für die beiden Arrays ist 1/2der Maximalwert von D.

Testfälle

[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

Regeln

• Sie können eine Funktion oder ein vollständiges Programm schreiben. Die Eingabe kann über STDIN oder ein Funktionsargument erfolgen, und die Ausgabe kann über STDOUT oder einen Rückgabewert erfolgen.
• Sie können jedes eindeutige Listen- oder Zeichenfolgenformat für die Eingabe annehmen, sofern es für beide Arrays konsistent ist
• Wenn es unwahrscheinlich ist, dass Ihre Sprache dafür eine eingebaute Sprache ist, können Sie diese möglicherweise nicht verwenden.
• Die Antworten müssen auf mindestens 3 signifikante Zahlen zutreffen
• Das ist Code-Golf , also gewinnt das Programm mit den wenigsten Bytes

APL ( 29 24)

(Danke an Zgarb für die zusätzliche Inspiration.)

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

Dies ist eine Funktion, die die Arrays als linkes und rechtes Argument verwendet.

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

Erläuterung:

{⌈/                                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
                          }

J - 39

Ich bin sicher, man kann viel mehr verkürzen

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

Verwendung

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

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)

Die Eingabe sind 2 Listen zur Funktion g

Dank an: Sp3000, xnor, undergroundmonorail

Zeile 2, erster Anruf fliest sich wie "Fax". Ich fand das leicht amüsant

JavaScript (ES6) 99 119 128

Mehr oder weniger unkomplizierte JavaScript-Implementierung , wahrscheinlich besser zum Golfen geeignet . In der F-Funktion verwende ich> anstelle von <= als abs (F (a) -F (b)) === abs ((1-F (a)) - (1-F (b)))

Keine Funktionsdefinition mehr als Standardparameer in dieser letzten Bearbeitung.

Wie gesagt, es ist unkompliziert. Die F-Funktion ist die F-Funktion, die D-Funktion ist die unbenannte Funktion, die in Zeile 2 verwendet wird. Sie wird mit .map für jeden in den beiden Arrays vorhandenen Wert ausgewertet, da der Maximalwert für reelle Werte alleiner dieser Werte sein muss. Zuletzt wird mit dem Spread-Operator (...) das D-Wertearray als Parameterliste an die Max-Funktion übergeben.

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 - Konsole

;[[[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)))

Ausgabe

[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

CJam, 33 31 Bytes

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

Input ist ein CJam-Styles-Array der beiden Arrays.

Beispiel:

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

Ausgabe:

0.17582417582417587

Probieren Sie es hier online aus

Matlab (121) (119)

Dies ist ein Programm, das zwei Listen in stdin aufnimmt und das Ergebnis in stdout ausgibt. Es ist eine leichte Aufgabe und ich habe versucht, so viel wie möglich Golf zu spielen. K(a)Gibt eine berechnete Funktion zurückx -> F(a,x) . Dann wird die anonyme Funktion, @(x)abs(g(x)-h(x))die der Funktion entspricht, Dauf jede mögliche ganze Zahl angewendet 0:max([a,b])und das Maximum der Ergebnisse angezeigt. ( arrayfunverhält sich wie mapin anderen Sprachen: Es wendet eine Funktion auf jedes Element eines Arrays an.)

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

Die JavaScript-Lösung von edc65 wurde nach Erlang portiert.

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]).

Prüfung:

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]]]).

Ausgabe:

[[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

Dies bedeutet, dass 90% der Eingaben in ein Format gelangen, das verwendet werden kann, da STATA bereits über einen Befehl ksmirnov verfügt.

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)

R, 65 Bytes

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

Diese Funktion nimmt zwei Vektoren als Argumente und gibt die maximale Differenz ihrer empirischen kumulativen Verteilungsfunktionen zurück.

Wenn eingebaute Funktionen zulässig wären, würden sie auf nur 12 Byte reduziert:

ks.test(a,b)

Mathematica, 76 73 63

Mathematica hat die eingebaute Funktion KolmogorovSmirnovTest, aber ich werde sie hier nicht verwenden.

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

Verwendung:

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

0,5

Schnelle Implementierung 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))

Beispiel:

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

Java - 633 622 Bytes

Ok, als erstes versuche ich, mich in Java zu verbessern. Deshalb habe ich es in Java versucht. Ich weiß, ich werde es nie gut machen, aber es macht Spaß. zweitens dachte ich ehrlich, ich könnte dies viel weniger tun, dann kam ich zu dem Stadium, in dem es überall Doppelte gab, und die Methodendeklarationen bedeuteten, dass mit Methoden nur 4-5 Zeichen insgesamt gespart wurden. Kurz gesagt, ich bin ein schlechter Golfer.

Bearbeiten: Verwendungsformat> 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;}}

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

(!) ist die Kolmogorov-Smirnov-Funktion, die zwei Listen nimmt

R, 107 Bytes

Anderer Ansatz

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
}