En statistiques, il est parfois utile de savoir si deux échantillons de données proviennent de la même distribution sous-jacente. Une façon de procéder consiste à utiliser le test de Kolmogorov-Smirnov à deux échantillons .

Votre tâche sera d'écrire un programme qui lit dans deux tableaux d'entiers non négatifs non triés et calcule la statistique principale utilisée dans le test.

Étant donné un tableau Aet un nombre réel x, définissez la fonction de distribution Fen

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

Étant donné deux tableaux A1et A2, définissez

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

La statistique de Kolmogorov-Smirnov à deux échantillons est la valeur maximale de Dtout réel x.

Exemple

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

Alors:

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

La statistique KS pour les deux tableaux est 1/2la valeur maximale de D.

Cas de test

[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

Règles

• Vous pouvez écrire une fonction ou un programme complet. L'entrée peut être via STDIN ou un argument de fonction, et la sortie peut être via STDOUT ou une valeur de retour.
• Vous pouvez assumer n'importe quel format de liste ou de chaîne sans ambiguïté pour l'entrée, tant qu'il est cohérent pour les deux tableaux
• Au cas où votre langue possède une fonction intégrée pour cela, vous ne pouvez pas l'utiliser.
• Les réponses doivent être correctes à au moins 3 chiffres significatifs
• C'est du code-golf , donc le programme dans le moins d'octets gagne

APL ( 29 24)

(Merci à Zgarb pour l'inspiration supplémentaire.)

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

Il s'agit d'une fonction qui prend les tableaux comme arguments gauche et droit.

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

Explication:

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

Je suis sûr que cela peut être raccourci beaucoup plus

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

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)

Les entrées sont 2 listes pour la fonction g

Merci à: Sp3000, xnor, undergroundmonorail

Ligne 2, premier appel à flit comme "fax". J'ai trouvé ça légèrement amusant

JavaScript (ES6) 99 119 128

Implémentation JavaScript plus ou moins simple , probablement plus jouable . Dans la fonction F, j'utilise> au lieu de <=, comme abs (F (a) -F (b)) === abs ((1-F (a)) - (1-F (b)))

Plus de définition de fonction comme paramètre par défaut dans cette dernière édition.

Comme je l'ai dit, c'est simple. La fonction F est la fonction F, la fonction D est la fonction sans nom utilisée à la ligne 2. Elle est évaluée en utilisant .map pour chaque valeur présente dans les deux tableaux, car la valeur maximale pour les allréels doit être l'une d'entre elles. Enfin, l'opérateur d'étalement (...) est utilisé pour passer le tableau de valeurs D en tant que liste de paramètres à la fonction max.

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 dans la console FireFox / FireBug

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

Production

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

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

L'entrée est un tableau de styles CJam des deux tableaux.

Exemple:

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

Production:

0.17582417582417587

Essayez-le en ligne ici

Matlab (121) (119)

Il s'agit d'un programme qui prend deux listes via stdin et imprime le résultat sur stdout. C'est une approche efficace et j'ai essayé de jouer au golf autant que possible. K(a)renvoie une fonction qui calcule x -> F(a,x). Ensuite, la fonction anonyme @(x)abs(g(x)-h(x))qui correspond à la fonction Dest appliquée à chaque entier possible de 0:max([a,b])et le maximum des résultats est affiché. ( arrayfunfait la même chose que mapdans les autres langages: il applique une fonction à chaque élément d'un tableau)

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 octets

La solution JavaScript d'edc65 portée sur 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]).

Tester:

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

Production:

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

Cela représente 90% de l'entrée dans un format utilisable car STATA a déjà une commande ksmirnov.

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 octets

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

Cette fonction prend deux vecteurs comme arguments et renvoie la différence maximale de leurs fonctions de distribution cumulative empirique.

Si les fonctions intégrées étaient autorisées, cela réduirait à seulement 12 octets:

ks.test(a,b)

Mathematica, 76 73 63

Mathematica a la fonction intégrée KolmogorovSmirnovTest, mais je ne l'utilise pas ici.

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

Usage:

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

0,5

Implémentation rapide en Python 3.4.2 (79 octets):

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

Exemple:

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

D'accord, tout d'abord, en essayant de m'améliorer en java, c'est pourquoi je l'ai essayé en java, je sais que je ne réussirai jamais bien, mais eh, c'est amusant. deuxièmement, je pensais honnêtement que je pouvais faire cela de manière beaucoup moins, puis je suis arrivé à l'étape où il y avait des doubles partout, et les déclarations de méthode signifiaient que l'utilisation de méthodes ne permettait de sauver que 4-5 caractères au total. bref, je suis un mauvais golfeur.

modifier: format d'utilisation> 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

(!) est la fonction kolmogorov-smirnov qui prend deux listes

R, 107 octets

Une approche différente

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}

Non golfé

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
}