Time in nano seconds

mail@pastecode.io avatar
unknown
java
3 years ago
7.0 kB
1
Indexable
Never
import java.util.Random;

public class TreeOperationTest {

    final static int NUMS = 100000;
    final static Random random = new Random(100);
    public static BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<Integer>();
    public static AVLTree<Integer> avlTree = new AVLTree<Integer>();
    public static RedBlackBST<Integer, Integer> redBlackBST = new RedBlackBST<Integer, Integer>();
    public static SplayTree<Integer> splayTree = new SplayTree<Integer>();

    public static void main(String[] args) {

        String format = "%-20s\t|\t%-15.3f";
        System.out.println();
        System.out.println("-".repeat(60));
        System.out.println(String.format("%-20s\t|\t%-18s", "Insert Operation", "Average Time in nanosecond"));
        System.out.println("-".repeat(60));
        System.out.println(String.format(format, "BinarySearchTree", insertInBinarySearchTree()));
        System.out.println(String.format(format, "AVLTree", insertInAVLTree()));
        System.out.println(String.format(format, "RedBlackBST", insertInRedBlackBST()));
        System.out.println(String.format(format, "SplayTree", insertInSplayTree()));

        System.out.println();
        System.out.println("-".repeat(60));
        System.out.println(String.format("%-20s\t|\t%-18s", "Search Operation", "Average Time in nanosecond"));
        System.out.println("-".repeat(60));
        System.out.println(String.format(format, "BinarySearchTree", searchInBinarySearchTree()));
        System.out.println(String.format(format, "AVLTree", searchInAVLTree()));
        System.out.println(String.format(format, "RedBlackBST", searchInRedBlackBST()));
        System.out.println(String.format(format, "SplayTree", searchInSplayTree()));

        System.out.println();
        System.out.println("-".repeat(60));
        System.out.println(String.format("%-20s\t|\t%-18s", "Delete Operation", "Average Time in nanosecond"));
        System.out.println("-".repeat(60));
        System.out.println(String.format(format, "BinarySearchTree", deleteInBinarySearchTree()));
        System.out.println(String.format(format, "AVLTree", deleteInAVLTree()));
        System.out.println(String.format(format, "RedBlackBST", deleteInRedBlackBST()));
        System.out.println(String.format(format, "SplayTree", deleteInSplayTree()));

    }

    public static double insertInBinarySearchTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= NUMS; i++) {
            start = System.nanoTime();
            binarySearchTree.insert(i);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;
    }

    public static double searchInBinarySearchTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= NUMS; i++) {
            int search = random.nextInt(100000) + 1;
            start = System.nanoTime();
            binarySearchTree.contains(search);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double deleteInBinarySearchTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = NUMS; i >= 1; i--) {
            start = System.nanoTime();
            binarySearchTree.remove(i);
            end = System.nanoTime();
            avg += (end - start);
        }
        return avg / NUMS;
    }

    public static double insertInAVLTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= 100000; i++) {
            start = System.nanoTime();
            avlTree.insert(i);
            end = System.nanoTime();
            avg += (end - start);
        }
        return avg / NUMS;
    }

    public static double searchInAVLTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= NUMS; i++) {
            int search = random.nextInt(100000) + 1;
            start = System.nanoTime();
            avlTree.contains(search);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;
    }

    public static double deleteInAVLTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = NUMS; i >= 1; i--) {
            start = System.nanoTime();
            avlTree.remove(i);
            end = System.nanoTime();
            avg += (end - start);
        }
        return avg / NUMS;
    }

    public static double insertInRedBlackBST() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= 100000; i++) {
            start = System.nanoTime();
            redBlackBST.put(i, i);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double searchInRedBlackBST() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= NUMS; i++) {
            int search = random.nextInt(100000) + 1;
            start = System.nanoTime();
            redBlackBST.contains(search);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double deleteInRedBlackBST() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = NUMS; i >= 1; i--) {
            start = System.nanoTime();
            redBlackBST.delete(i);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double insertInSplayTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= 100000; i++) {
            start = System.nanoTime();
            splayTree.insert(i);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double searchInSplayTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = 1; i <= NUMS; i++) {
            int search = random.nextInt(100000) + 1;
            start = System.nanoTime();
            splayTree.contains(search);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;

    }

    public static double deleteInSplayTree() {
        long start = 0;
        long end = 0;
        double avg = 0;

        for (int i = NUMS; i >= 1; i--) {
            start = System.nanoTime();
            splayTree.remove(i);
            end = System.nanoTime();
            avg += (end - start);
        }

        return avg / NUMS;
    }

}