In this article, I would like to talk about Python Sorted Containers. In python language, the build-in data collection is implemented differently from another language (e.g., C\/C++). That makes python losing some ability or performance to access specific data. For example, in C++ language, std::map and std::set are implemented by a tree structure, that causes the data collections to have an ability to search upper or lower bound (upper_bound, lower_bound) of the selected value. In python, such abilities don’t exist in the built-in data collection. However, Python has a library to support that ability, which can install additionally. Sorted containers is an open-sourced library that allows us to insert or delete elements very efficiently and the elements maintaining a sorted order. The library contains three containers: SortedList, SortedDict, and SortedSet.<\/p>\n\n\n\n
Installation: we can install sorted collection by pip command:<\/p>\n\n\n\n
$sudo pip install sortedcontainers <\/code><\/pre>\n\n\n\nPython Sorted Container contains three sorted data structure:<\/p>\n\n\n\n
- SortedList <\/li>
- SortedDict <\/li>
- SortedSet<\/li><\/ul>\n\n\n\n
We can use these sorted containers in the same way as build-in python; List\/Dict\/Set. These are some examples of code to use the Sorted containers.<\/p>\n\n\n\n
SortedList<\/strong><\/p>\n\n\n\nfrom random import random\nfrom sortedcontainers import SortedList\n\nmainList = SortedList()\nfor i in range(100):\n mainList.add(random())\n<\/pre>\n\n\nSortedDict<\/strong><\/p>\n\n\n\nfrom sortedcontainers import SortedDict\nfrom random import random\n\nmainList = SortedDict()\n\nfor i in range(100):\n mainList[i]=(random())\n<\/pre>\n\n\nSortedSet<\/strong><\/p>\n\n\n\nfrom sortedcontainers import SortedSet\nfrom random import random\n\nmainList = SortedSet()\n\nfor i in range(100):\n mainList.add(random())\n<\/pre>\n\n\nSince the data inside Python Sorted Containers are sorted, the containers can fetch the nearest value (upper bound\/lower bound) like upper_bound, lower_bound in c++ language. In Python Sorted Containers, they are called bisect_left(value<\/em>)<\/strong> and bisect_right(value<\/em><\/strong>). <\/p>\n\n\n\nbisect_left(value)<\/strong> return an index to insert value<\/strong> in the sorted container. if the value<\/strong> already exists in the container, the function will return the existing value’s index.<\/p>\n\n\n\nbisect_left(value)<\/strong> return an index to insert value<\/strong> in the sorted container. if the value<\/strong> already exists in the container, the function will return the index after the existing value’s index.<\/p>\n\n\n\nLet’s see an example.<\/p>\n\n\n\n
>>> sl = SortedList([10, 12, 14, 16, 18])\n>>> sl.bisect_left(12)\n1\n>>> sl.bisect_left(13)\n2\n>>> sl.bisect_right(13)\n2\n>>> sl.bisect_right(14)\n3<\/code><\/pre>\n\n\n\nAs we can see from the example, function bisect_left returns an index of the value, if the value exists in the list; sl.bisect_left(12) return 1 because the index of 12 is the 1st. On the other hand, if the value doesn’t exist, the function will return the index of an insertion point of the value; sl.bisect_left(13) return 2 because the index 2 is the new position of 13 if there is an insertion. In a similar way to bisect_right, if the value doesn’t exist, the function will return the index of an insertion position; sl.bisect_right(13) return 2, because it is the insertion position. However, if the value is already in the container, the function will return the index after the existing value; sl.bisect_right(14) returns 3 because 14 is at index 2.<\/p>\n\n\n\n
The most advantage of these two functions is the performance. bisect_left and bisect_right can run with O(nlgn) running time, which is optimized for searching application.<\/p>\n\n\n\n