Java의 ArrayList/Collections 메서드에서 코드가 느리다

Question

2D KD 트리 구현을 구성하려고합니다. 이 시점에서 작동하지만 실행 시간은 ~ 100k 포인트 이상 폭발합니다. 100k의 경우 15 초, 1e6의 경우 약 30 분이 소요됩니다. 처음에는 병목 현상이 중간 값을 찾는 정렬이라고 생각했지만 subList 및 addAll 메서드를 사용하는 것으로 보입니다. 개선을위한 제안 사항은 훌륭합니다.

감사합니다,

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; 
    } 
    //**************************************************** 

} 

Answer 1

사용이 : 새로운 ArrayList를 10 요소의 용량을 기본으로 생성되기 때문에

ArrayList<Point>(int capacity); 

. 그것은 새로운 배열을 생성하여 크기에 도달 할 때마다 현재 용량을 두 배로 늘리고 오래된 배열은 가비지 컬렉터에 의해 파괴됩니다. 따라서 귀하의 현재 ArrayList 용량은 10-> 20-> 40-> 80-> 160->

Answer 2

입니다. splitList() 함수 내에 sortByX() 및 sortByY() 호출이 있고 매개 변수 그들은 서로의 결과와 관련이 없습니다. 내 생각에 .. 당신의 CPU 파워가 약간의 여분의 리소스를 가지고 있다면 어쩌면 당신은 두 개의 계산을 다른 쓰레드에서 실행하고 완료되었을 때 사용할 수 있습니다.

ArrayList를 만들 때 초기 ArrayList 용량을 설정하는 것도 좋습니다. 그것은 기본 32 정도이며 ArrayList를 채울 때 일어난 일은 원래의 것보다 두 배 크기의 새로운 내부 배열을 만들고 내부 항목의 기존 항목을 새로운 항목으로 복사합니다. 어레이의 길이는 적당하지만 문제가 될 수 있습니다.

IIRC, 구현 상 약간의 차이가 있으므로 subList()에서도 성능이 비슷하므로 Java6으로 테스트를 실행 한 경우 Java7로 시도해보십시오.