Медленный код в ArrayList/Методы коллекций в Java

Question

Я пытаюсь объединить реализацию 2D KD-дерева. На данный момент он работает, но время запуска взрывается более чем на 100 тыс. Точек. Требуется 15 с для 100 кБ и около 30 минут для 1 е6. Сначала я подумал, что узким местом является сортировка, чтобы найти медианные значения, но, похоже, это методы 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<Point>(int capacity); 

Поскольку новый ArrayList по умолчанию создается с мощностью 10 элемента. Он удваивает текущую емкость каждый раз, когда достигает своего размера, создавая новый массив, а старый уничтожается сборщиком мусора. Таким образом, в вашем текущем случае ваша емкость ArrayList составляет 10-> 20-> 40-> 80-> 160 -> ...

Answer 2

Существует вызов sortByX() и sortByY() внутри функции splitList(), а параметр они принимают, не связаны друг с другом. Так что я думаю .. до тех пор, пока у вашей мощности процессора есть дополнительные ресурсы, возможно, вы можете сделать эти два вычисления для запуска в другом потоке и использовать его, когда это будет сделано.

Установка начальной емкости ArrayList при создании ArrayList также является хорошей идеей. Он имеет значение по умолчанию 32 или около того, и то, что произошло при заполнении ArrayList, это .. он создает новый внутренний массив с двойным размером, чем оригинальный, и копирует существующие элементы внутренних элементов в новый. Это нормально для небольшой длины массива, но может быть проблематичным в случае, как вы.

IIRC, существуют некоторые различия в реализации, так что производительность также подходит для subList(), поэтому, если вы запускаете тест с Java6, просто попробуйте с Java7.