==============================
Insert-Overlapping Performance
==============================

.. include:: performance_compared.txt     

The following figure shows the running time of inserting integer intervals one by one into a set and, and finding the
intervals overlapping the inserted interval after each insertion, as a function of the number of intervals (see :download:`_set_insert_overlapping_intervals.py` for the source). It primarily shows the effect of key-type specificication:

.. figure:: IntSetInsertOverlappingAll.png

The faster Banyan implementations here are those which specify the key types, e.g., 

::

    >>> # An integer-interval tree
    >>> t = SortedSet(key_type = (int, int), updator = OverlappingIntervalsUpdator)
    >>>
    >>> # A float-interval tree
    >>> t = SortedSet(key_type = (float, float), updator = OverlappingIntervalsUpdator)

following that is the `bx`_ implementation, which presumably uses some homogeneous keys internally as well. The slowest Banyan implementation is due to its flexibility: without key-type specification, "intervals" of any type can be used, e.g.,

::

    >>> SortedSet([('a', 'aa'), ('bb', 'mmm')], updator = OverlappingIntervalsUpdator).overlap_point('a')
    [('a', 'aa')]
    
This flexibility comes with a performance penalty.