我想要放在一起的2D KD樹實現。此時它可以工作,但運行時間爆炸超過100k點。 1e6需要15秒,10分鐘需要30分鐘。起初,我認爲瓶頸是找到中值的排序,但它似乎與subList和addAll方法。任何改進建議都會很棒。在Java中的ArrayList/Collections方法的慢代碼
感謝,
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class KDtree {
//****************************************************
//setting up a data set for input
//****************************************************
public kdLite() {
long startTime = System.currentTimeMillis()/1000;
//select random values to generate data set
double[][] dataSet = new double[2][100000];
for (int i = 0; i < 100000; i++) {
dataSet[0][i] = (Math.random() * (99));
dataSet[1][i] = (Math.random() * (99));
//System.out.print(dataSet[0][i] + "\t" + dataSet[1][i] + "\n");
}
//System.out.print("\n");
//setup a point class for simple data manipulation and add data to it
ArrayList<Point> preSorted = new ArrayList<Point>();
for (int i = 0; i < dataSet[0].length; i++) {
Point point = new Point(i, dataSet[0][i], dataSet[1][i], 0);
preSorted.add(point);
}
//split and sort the list
ArrayList<Point> outList = splitList(preSorted);
// add the list to the binary tree structure
BinaryST buildKD = new BinaryST();
for (int i = 0; i < outList.size(); i++) {
buildKD.insertNode(outList.get(i));
}
long endTime = System.currentTimeMillis()/1000;
System.out.println((int) (endTime - startTime)/60 + " Minutes and " + (endTime - startTime) + " Seconds");
// buildKD.printTree();
//****************************************************
}
//****************************************************
//the brunt of the code. this method takes a list of Point objects
//solves for the axis to split on and cuts the list into 2^i segments
//****************************************************
public ArrayList<Point> splitList(ArrayList<Point> arrToSplit) {
ArrayList<ArrayList<Point>> splitList = new ArrayList<ArrayList<Point>>();
ArrayList<Point> Meds = new ArrayList<Point>();
int axis = 0;
int toSplit = 0;
double maxXdif = 0;
double maxYdif = 0;
//populate first bucket
splitList.add(new ArrayList<Point>());
for (int i = 0; i < arrToSplit.size(); i++) {
splitList.get(0).add(arrToSplit.get(i));
}
for (int slice = 0; slice < arrToSplit.size(); slice++) {
//get first bucket that has more than one value then use it first
for (int i = 0; i < splitList.size(); i++) {
if (splitList.get(i).size() >= 1) {
toSplit = i;
if (splitList.get(i).size() > 1) {
break;
}
}
}
if (splitList.get(toSplit).size() > 1) {
sortByX(splitList.get(toSplit));
maxXdif = Math.abs(splitList.get(toSplit).get(0).x - splitList.get(toSplit).get(splitList.get(toSplit).size() - 1).x);
sortByY(splitList.get(toSplit));
maxYdif = Math.abs(splitList.get(toSplit).get(0).y - splitList.get(toSplit).get(splitList.get(toSplit).size() - 1).y);
//arrange by splitting axis according to largest distance to find splitting axis
if (maxXdif > maxYdif) {
axis = 0;
sortByX(splitList.get(toSplit));
} else {
axis = 1;
sortByY(splitList.get(toSplit));
}
//solve for median point .. arbitrate if no point lies on axis (uneven split)
int Med = (int) Math.floor(splitList.get(toSplit).size()/2);
//take median point, assign splitting axis
splitList.get(toSplit).get(Med).axis = axis;
Meds.add(splitList.get(toSplit).get(Med));
splitList.get(toSplit).remove(Med);
---- >>>>>> PROBLEM CODE
// relocate all points except median to new list, delete the median value
List<Point> head = splitList.get(toSplit).subList(Med, splitList.get(toSplit).size());
splitList.add(new ArrayList<Point>());
splitList.get(splitList.size() - 1).addAll(head);
head.clear();
splitList.get(toSplit).subList(Med - 1, splitList.get(toSplit).size() - 1).clear();
} else {
//these are the leftover points so ordering is arbitrary
//randomize axis to ensure balance
Random random = new Random();
int randomAxis = random.nextInt(2 - 0);
Meds.add(splitList.get(toSplit).get(0));
splitList.get(toSplit).get(0).axis = randomAxis;
splitList.remove(toSplit);
}
}
return Meds;
}
//****************************************************
//****************************************************
//sorting methods for sorting a list by x or y
//must use comparator to sort by custom object attributes
//****************************************************
private ArrayList<Point> sortByX(ArrayList<Point> xList) {
Collections.sort(xList, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
return Double.compare(p1.getX(), p2.getX());
}
});
return xList;
}
private ArrayList<Point> sortByY(ArrayList<Point> yList) {
Collections.sort(yList, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
return Double.compare(p1.getY(), p2.getY());
}
});
return yList;
}
//****************************************************
}
謝謝兩個回到我身邊!之後我發現問題不在於排序或拆分,而是與代碼中看似無害的部分相關://獲取具有多個值的第一個桶,然後首先使用它。 我每次迭代都無意中增加了我的搜索空間。我現在可以在20秒內完成1e6次迭代,而不是30分鐘。任何更多的計算,瓶頸成爲nlogn排序,這是一個伎倆來解決。再次感謝! – user3347844