[May 27 - June 02]

All BinarySearchTree methods and all tree traversals done! Amazing speed results!

Coding info

This week, I completed all the methods of BinarySearchTree class. All of them can now be accessed in the C++ backend. This gives BinarySearchTree’s C++ backend the complete functionality. The methods are:

  • delete()
  • _simple_path()
  • lower_bound
  • upper_bound
  • lowest common ancestor algorithm 1
  • lowest common ancestor algorithm 2
  • rank()
  • select()
  • str()

Along with this, I also added all traversals in the BinaryTreeTraversal class. These include:

  • pre_order
  • in_order
  • post_order
  • out_order
  • depth_first_search
  • breadth_first_search

I am speed!!!

Now that I have completed the BinarySearchTree class, I decided to test it’s speed against the existing Python implementation and the results were amazing!!! My implementations in the C++ backend are 6-8 times faster than the Python backend.

Here’s a benchmark test:

def test_BinarySearchTree(**kwargs):
    cpp = Backend.CPP
    repeat = 1
    number = 1

    size = int(os.environ.get("PYDATASTRUCTS_BENCHMARK_SIZE", "1000"))
    size = kwargs.get("size", size)

    BST = BinarySearchTree
    b1 = BST(backend=Backend.PYTHON)
    b2 = BST(backend=Backend.CPP)

    def f(backend, tree):
        for node in range(-1000,1000):
            tree.insert(node, node)
    def g(backend, tree):
        for node in range(-1000, 1000):
            tree.search(node)
    def h(backend, tree):
        for node in range(2000):
            tree.delete(node)

    kwds_dict_PY = {"backend": Backend.PYTHON, "tree":b1}
    kwds_dict_CPP = {"backend": Backend.CPP, "tree":b2}

    timer_python = timeit.Timer(functools.partial(f, **kwds_dict_PY))
    python_insert = min(timer_python.repeat(repeat, number))

    timer_cpp = timeit.Timer(functools.partial(f, **kwds_dict_CPP))
    cpp_insert = min(timer_cpp.repeat(repeat, number))
    assert cpp_insert < python_insert

    timer_python = timeit.Timer(functools.partial(g, **kwds_dict_PY))
    python_search = min(timer_python.repeat(repeat, number))

    timer_cpp = timeit.Timer(functools.partial(g, **kwds_dict_CPP))
    cpp_search = min(timer_cpp.repeat(repeat, number))
    assert cpp_search < python_search

    timer_python = timeit.Timer(functools.partial(h, **kwds_dict_PY))
    python_delete = min(timer_python.repeat(repeat, number))

    timer_cpp = timeit.Timer(functools.partial(h, **kwds_dict_CPP))
    cpp_delete = min(timer_cpp.repeat(repeat, number))
    assert cpp_delete < python_delete

    print("Python Time:")
    print("insert(): ",python_insert,"s")
    print("search(): ",python_search,"s")
    print("delete(): ",python_delete,"s")
    python_total = python_insert+python_search+python_delete
    print("Total Python time: ", python_total,"s\n")

    print("C++ Time:")
    print("insert(): ",cpp_insert,"s")
    print("search(): ",cpp_search,"s")
    print("delete(): ",cpp_delete,"s")
    cpp_total = cpp_insert+cpp_search+cpp_delete
    print("Total C++ time: ", cpp_total,"s\n")

    print("C++ backend is",round(python_total/cpp_total),"times faster!")
    
test_BinarySearchTree()

Output:

Python Time:
insert():  7.025027044000126 s
search():  3.316694295000161 s
delete():  3.271200282000109 s
Total Python time:  13.612921621000396 s

C++ Time:
insert():  0.9178718929999832 s
search():  0.43746472500015443 s
delete():  0.7311443830001281 s
Total C++ time:  2.0864810010002657 s

C++ backend is 7 times faster!

Relevant PRs:

I worked on the PR: #556

There have been a plethora of commits to this PR. Commits of this week focused on adding all the methods and completing the BinarySearchTree class, adding all traversals and adding benchmark tests.

In the following week, I will work on SelfBalancingBinaryTree class and add all its functionality in the C++ backend. It includes methods like _right_rotate(), _left_rotate, _left_right_rotate and _right_left_rotate. Hence, it serves as the base class for AVL Trees, Cartesian Trees, Splay Trees and Red Black Trees.

Learnings/Difficulties

This week was amazing, I was busy working and I achieved several goals! I faced some difficulty specific to the Python-C API, and I spent time referring to its documentation. After hours of reading the documentation, I finally figured out the solution! This taught me the importance to document work and read the documentation (something that most enthusiastic coders like me skip).


Thanks to my mentor, Gagandeep Singh, for guiding me whenever requested.

See you again after amazing 7 days! 😊