BinarySearchTree скорость поиска эффективности - PullRequest
Новая
       9

BinarySearchTree скорость поиска эффективности

0 голосов
/ 15 мая 2011 
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;


public class BSTSearchTimer {

int [] n = {10000, 50000, 100000, 250000};
Random rand = new Random();

public static void main(String[] args) throws IOException{

    BSTSearchTimer timer = new BSTSearchTimer();
    timer.runBSTSearchTimer();

}

public void runBSTSearchTimer() throws IOException{
    PrintWriter out = new PrintWriter( new FileWriter("tree2.csv"));
    int reps = 10000; // the number of searches that we will do on the tree


    for (int i = 0; i < n.length; i++){
        BinarySearchTree<Long> longBST = new BinarySearchTree<Long>();
        boolean success = true;

        int numOfElements = n[i];

        while (longBST.size() < numOfElements){

                success = longBST.add(rand.nextLong());
                while (!success){ // should keep attempting to add values until success is true
                    success = longBST.add(rand.nextLong());
            }

        }

        long start = System.currentTimeMillis(); // start the timer for searching

        for ( int j = 0; j < reps; j++){ // search rep times
            longBST.find(rand.nextLong());
        }
        long end = System.currentTimeMillis(); // end timer for searching tree

        double time = end-start;

        System.out.printf("%d, %f\n", longBST.size(), time);
        out.printf("%d, %f\n", n[i], time);

    }
    out.close();
}
}

Когда я запускаю эту программу, она должна создавать 4 дерева разных размеров: 10000, 50000, 100000, 250000. Я знаю, что эффективность поиска по BST должна быть O (Log n), но я получаю номера:

при выполнении 10 000 поисков я получаю следующие числа: (первый столбец - размер дерева, второй - время, необходимое для поиска) 

10000, 9.000000
50000, 3.000000
100000, 4.000000

при выполнении 100 000 поисков: 

10000, 41.000000
50000, 31.000000
100000, 40.000000
250000, 74.000000

Любые советы приветствуются.

1 Ответ

1 голос
/ 15 мая 2011

Скорее всего, вы видите эффект "промахов". Поскольку вы просто ищете случайные числа, числа, которых нет в дереве, займут намного больше времени, чем числа.

Кроме того, эффективность бинарного дерева поиска составляет O (h), где h - высота дерева. Красно-черные деревья и AVL деревья гарантируют, что они будут построены с высотой O (log n), но случайно построенные деревья могут легко оказаться с высотой, близкой к O ( п).

...