Красное черное дерево медленнее, чем обычный бинарный поиск в моих тестах - PullRequest
Новая
       81

Красное черное дерево медленнее, чем обычный бинарный поиск в моих тестах

0 голосов
/ 31 марта 2020

Я реализовал Red Black Tree и хотел сравнить время с обычным бинарным деревом поиска. Однако в своих тестах я обнаружил, что в большинстве случаев дерево двоичного поиска на самом деле быстрее. Что-то не так в моей реализации, или это должно произойти? Это мое Красно-черное дерево: 

public class RedBlackTree {

    public class RedBlackNode {
        Integer val;
        RedBlackNode left, right, parent;
        boolean color;

        public RedBlackNode() {

        }

        public RedBlackNode(Integer val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }

    }

    public static final boolean red = false, black = true;

    public RedBlackNode root;
    public final RedBlackNode nil;
    public int size;

    public RedBlackTree() {
        nil = new RedBlackNode();
        nil.color = black;
        root = nil;
    }

    public void insert(int val) {
        size ++;

        if(root == nil) {
            root = new RedBlackNode(val);
            root.parent = nil;
            root.left = nil;
            root.right = nil;
            root.color = black;
            return;
        }

        RedBlackNode dummy = root;

        while(true) {
            if(val < dummy.val) {
                if(dummy.left == nil) {
                    dummy.left = new RedBlackNode(val);
                    dummy.left.parent = dummy;
                    dummy.left.left = nil;
                    dummy.left.right = nil;
                    dummy.left.color = red;
                    dummy = dummy.left;
                    break;
                }

                dummy = dummy.left;
            } else {
                if(dummy.right == nil) {
                    dummy.right = new RedBlackNode(val);
                    dummy.right.parent = dummy;
                    dummy.right.left = nil;
                    dummy.right.right = nil;
                    dummy.right.color = red;
                    dummy = dummy.right;
                    break;
                }

                dummy = dummy.right;
            }
        }

        balance(dummy);
    }

    private void balance(RedBlackNode node) {
        while(node.parent.color == red) {
            if(node.parent == node.parent.parent.left) {
                if(node.parent.parent.right.color == red) {
                    node.parent.color = black;
                    node.parent.parent.color = red;
                    node.parent.parent.right.color = black;
                    node = node.parent.parent;
                } else {
                    if(node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }

                    node.parent.color = black;
                    node.parent.parent.color = red;
                    rotateRight(node.parent.parent);
                }
            } else {
                if(node.parent.parent.left.color == red) {
                    node.parent.color = black;
                    node.parent.parent.color = red;
                    node.parent.parent.left.color = black;
                    node = node.parent.parent;
                } else {
                    if(node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }

                    node.parent.color = black;
                    node.parent.parent.color = red;
                    rotateLeft(node.parent.parent);
                }
            }
        }

        root.color = black;
    }

    private void rotateLeft(RedBlackNode node) {
        RedBlackNode temp = node.right;
        node.right = temp.left;
        temp.left.parent = node;
        temp.parent = node.parent;
        if(node.parent == nil) {
            root = temp;
        } else if(node == node.parent.left) {
            node.parent.left = temp;
        } else {
            node.parent.right = temp;
        }
        temp.left = node;
        node.parent = temp;
    }

    private void rotateRight(RedBlackNode node) {
        RedBlackNode temp = node.left;
        node.left = temp.right;
        temp.right.parent = node;
        temp.parent = node.parent;
        if(node.parent == nil) {
            root = temp;
        } else if(node == node.parent.right) {
            node.parent.right = temp;
        } else {
            node.parent.left = temp;
        }
        temp.right = node;
        node.parent = temp;
    }

    public void printInSorted() {
        printInSorted(root);
    }

    private void printInSorted(RedBlackNode root) {
        if(root == nil) {
            return;
        }

        printInSorted(root.left);
        System.out.print(root.val + " ");
        printInSorted(root.right);
    }

}

Мое дерево бинарного поиска: 

public class BinarySearchTree {

    public class BinarySearchTreeNode {
        int val;
        BinarySearchTreeNode left, right;

        public BinarySearchTreeNode(int val) {
            this.val = val;
        }
    }

    private BinarySearchTreeNode root;
    private int size;

    public void insert(int val) {
        size ++;

        if(root == null) {
            root = new BinarySearchTreeNode(val);
            return;
        }

        BinarySearchTreeNode dummy = root;

        while(true) {
            if(val < dummy.val) {
                if(dummy.left == null) {
                    dummy.left = new BinarySearchTreeNode(val);
                    break;
                }

                dummy = dummy.left;
            } else {
                if(dummy.right == null) {
                    dummy.right = new BinarySearchTreeNode(val);
                    break;
                }

                dummy = dummy.right;
            }
        }
    }

    public boolean search(int val) {
        return search(root, val);
    }

    private boolean search(BinarySearchTreeNode root, int val) {
        if(root == null) {
            return false;
        }

        if(root.val == val) {
            return true;
        }

        return search(root.left, val) || search(root.right, val);
    }

    public void printInSorted() {
        printInSorted(root);
    }

    private void printInSorted(BinarySearchTreeNode root) {
        if(root == null) {
            return;
        }

        printInSorted(root.left);
        System.out.print(root.val + " ");
        printInSorted(root.right);
    }

    public int[] inSorted() {
        int[] ans = new int[size];
        int count = 0;
        Stack<BinarySearchTreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            BinarySearchTreeNode curr = stack.pop();

            if(curr.left != null || curr.right != null) {
                if(curr.right != null) {
                    stack.push(curr.right);
                    curr.right = null;
                }

                stack.push(curr);

                if(curr.left != null) {
                    stack.push(curr.left);
                    curr.left = null;
                }
            } else {
                ans[count ++] = curr.val;
            }
        }

        return ans;
    }

}

Вот мое тестирование: 

    int better = 0;
    for(int i = 0; i < 30; i ++) {
        RedBlackTree redBlackTree = new RedBlackTree();
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] rand = Utility.createArray(100, 100);

        long start1 = System.currentTimeMillis();
        for(int j : rand) {
            redBlackTree.insert(j);
        }
        long end1 = System.currentTimeMillis();

        long start2 = System.currentTimeMillis();
        for(int j : rand) {
            binarySearchTree.insert(j);
        }
        long end2 = System.currentTimeMillis();

        long total1 = end1 - start1;
        long total2 = end2 - start2;

        if(total1 < total2) {
            better ++;
        }
    }

    System.out.println((double) (better) / 100 + "%");

Это должно вывести процент от количество раз красное черное дерево было быстрее. Utility.createArray(int size, int max) просто создает массив размером size и максимум max случайных чисел. То, что я получаю большую часть времени, это проценты типа 0.02% или 0.03%.

1 Ответ

4 голосов
/ 31 марта 2020

Это не очень хороший тест. См. Как написать правильный микро-тест в Java?

Чтобы перечислить несколько болевых точек: System.currentTimeMillis не дает достаточного разрешения по времени, ваш код не выполнить «прогрев» итераций, чтобы убедиться, что код скомпилирован, но ничего не гарантирует, что компилятор не выбрасывает код, потому что у него нет побочных эффектов, например c. Если вы заинтересованы в улучшении тестов, я бы посоветовал научиться использовать JMH .

При этом факт, что вы вставляете случайные числа, означает, что вы, скорее всего, избежите патологические случаи, из-за которых несбалансированные деревья бинарного поиска работают плохо. Вы используете "treap" (рандомизированное двоичное дерево поиска) . Накладные расходы ниже, чем в красно-черном дереве, поэтому неудивительно, что вы можете увидеть более высокую производительность.

...