1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
package de.lmu.ifi.dbs.elki.math;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2011
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
import static org.junit.Assert.assertEquals;
import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import de.lmu.ifi.dbs.elki.JUnit4Test;
import de.lmu.ifi.dbs.elki.math.statistics.QuickSelect;
/**
* Test the QuickSelect math class.
*
* @author Erich Schubert
*/
public class TestQuickSelect implements JUnit4Test {
/**
* Array size to use.
*/
final int SIZE = 10000;
@Test
public void testRandomDoubles() {
for(int i = 1; i < 10; i++) {
testQuickSelect(i);
}
testQuickSelect(SIZE);
testQuickSelect(SIZE + 1);
}
private void testQuickSelect(int size) {
double[] data = new double[size];
double[] test;
// Make a random generator, but remember the seed for debugging.
Random r = new Random();
long seed = r.nextLong();
r = new Random(seed);
// Produce data
for(int i = 0; i < size; i++) {
data[i] = r.nextDouble();
}
// Duplicate for reference, sort.
test = Arrays.copyOf(data, size);
Arrays.sort(test);
// Run QuickSelect and compare with full sort
// After a few iterations, the array will be largely sorted.
// Better just run the whole test a few times, than doing too many
// iterations here.
for(int j = 0; j < 20; j++) {
int q = r.nextInt(size);
double r1 = QuickSelect.quickSelect(data, q);
double r2 = test[q];
assertEquals("QuickSelect returned incorrect element. Seed=" + seed, r2, r1, Double.MIN_VALUE);
}
double med = QuickSelect.median(data);
if(size % 2 == 1) {
double met = test[(size - 1) / 2];
assertEquals("QuickSelect returned incorrect median. Seed=" + seed, met, med, Double.MIN_VALUE);
}
else {
double met = (test[(size - 1) / 2] + test[(size + 1) / 2]) / 2;
assertEquals("QuickSelect returned incorrect median. Seed=" + seed, med, met, Double.MIN_VALUE);
}
double qua = QuickSelect.quantile(data, 0.5);
assertEquals("Median and 0.5 quantile do not agree. Seed=" + seed, med, qua, 1E-15);
}
@Test
public void testPartialArray() {
double data[] = new double[] { 0.1, 0.2, 1, 2, 3, 0.9, 0.95 };
assertEquals("Partial median incorrect.", 1, QuickSelect.median(data, 2, 2), Double.MIN_VALUE);
assertEquals("Partial median incorrect.", 3, QuickSelect.median(data, 4, 4), Double.MIN_VALUE);
// Note: do not change the order, since this modifies the array.
assertEquals("Partial median incorrect.", 2, QuickSelect.median(data, 2, 4), Double.MIN_VALUE);
// Note: do not change the order, since this modifies the array.
assertEquals("Full median incorrect.", 0.95, QuickSelect.median(data), Double.MIN_VALUE);
}
@Test
public void testTies() {
double data[] = new double[] { 0.1, 0.1, 0.9, 0.9, 0.5, 0.9, 0.1, 0.1, 0.1, 0.9, 0.9, 0.9, 0.9, 0.1, 0.1 };
assertEquals("Full median incorrect.", 0.5, QuickSelect.median(data), Double.MIN_VALUE);
}
}
|
