So… Wieder verworfen! Hab die Eingabe von 15 Mio. auf 0,5 Mio. begrenzt, und suche mitten in der Punktwolke.
Es ist dabei immer noch O(n^2/2), das ist für 0,5 Mio. verschmerzbar:
class Worker implements Runnable {
final int from, to, n;
final ArrayList<Sys> syss1;
volatile long count = 0;
int pro = 0;
Worker(int n, int index, ArrayList<Sys> syss1) {
double[] ds = new double[n];
double sum = 0;
for (int i = 1; i <= n; i++) {
ds[n - i] = Math.pow(0.5, i);
sum += Math.pow(0.5, i);
}
System.out.println("sum = " + sum);
System.out.println(Arrays.toString(ds));
for (int i = 1; i < n; i++) {
ds** = ds[i - 1] + ds**;
}
for (int i = 0; i < n; i++) {
ds** /= sum;
}
System.out.println(Arrays.toString(ds));
from = index == 1 ? 0 : (int) (ds[index - 2] * syss1.size()) + 1;
to = (int) (ds[index - 1] * syss1.size());
/*
double d2 = 1.0 / n * (index - 1);
from = (int) (d2 * syss1.size()) + (index == 1 ? 0 : 1);
to = (int) ((1.0 / n + d2) * syss1.size());
*/
System.out.println("from = " + from);
System.out.println("to = " + to);
System.out.println((to - from) * 100.0 / syss1.size());
this.syss1 = syss1;
this.n = n;
}
@Override
public void run() {
System.out.println(System.currentTimeMillis() + " Start " + this + " from " + from + " to " + to + ".");
Sys sys1, sys2;
for (int i = from; i < to; i++) {
sys1 = syss1.get(i);
for (int j = i + 1; j < syss1.size(); j++) { // beachte: Läuft bis n
sys2 = syss1.get(j);
float d = (sys1.x - sys2.x) * (sys1.x - sys2.x) + (sys1.y - sys2.y) * (sys1.y - sys2.y) + (sys1.z - sys2.z) * (sys1.z - sys2.z);
if (d >= 784 && d <= 1024) {
// now go on with some Filtering...
// with sys1 and sys2
count++;
if ((int) ((i - from) * 100 / (to - from)) > pro) {
pro = (int) ((i - from) * 100 / (to - from));
System.out.println(this + " , pro = " + pro);
}
}
}
}
System.out.println(System.currentTimeMillis() + " End " + this + " from " + from + " to " + to + ".");
}
}
Problem: Die Threads laufen unterschiedlich lange!!
Runtime.getRuntime().totalMemory() = 2705850368
Runtime.getRuntime().maxMemory() = 5726797824
Runtime.getRuntime().freeMemory() = 770249688
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 0
to = 2406
0.39209742789954094
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 2407
to = 7219
0.7841948557990819
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 7220
to = 16844
1.5683897115981638
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 16845
to = 36095
3.13710535622035
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 36096
to = 74597
6.274373678952712
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 74598
to = 151600
12.548747357905423
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 151601
to = 305608
25.097983615346884
sum = 0.99609375
[0.00390625, 0.0078125, 0.015625, 0.03125, 0.0625, 0.125, 0.25, 0.5]
[0.00392156862745098, 0.011764705882352941, 0.027450980392156862, 0.058823529411764705, 0.12156862745098039, 0.24705882352941178, 0.4980392156862745, 1.0]
from = 305609
to = 613623
50.19596723069377
Wie berechnet man, “von wo bis wo” ein Thread/Runnable laufen muss? wenn das gesamte Schleife (n^2+n)/2 ist?