Python Sorted Containers

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.

Installation: we can install sorted collection by pip command:

$sudo pip install sortedcontainers 

Python Sorted Container contains three sorted data structure:

  • SortedList 
  • SortedDict 
  • SortedSet

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.

SortedList

from random import random
from sortedcontainers import SortedList

mainList = SortedList()
for i in range(100):
    mainList.add(random())

SortedDict

from sortedcontainers import SortedDict
from random import random

mainList = SortedDict()

for i in range(100):
    mainList[i]=(random())

SortedSet

from sortedcontainers import SortedSet
from random import random

mainList = SortedSet()

for i in range(100):
    mainList.add(random())

Since 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) and bisect_right(value). 

bisect_left(value)  return an index to insert value in the sorted container. if the value already exists in the container, the function will return the existing value’s index.

bisect_left(value) return an index to insert value in the sorted container. if the value already exists in the container, the function will return the index after the existing value’s index.

Let’s see an example.

>>> sl = SortedList([10, 12, 14, 16, 18])
>>> sl.bisect_left(12)
1
>>> sl.bisect_left(13)
2
>>> sl.bisect_right(13)
2
>>> sl.bisect_right(14)
3

As 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.

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.

reference: http://www.grantjenks.com/docs/sortedcontainers/

Run a job in the background on Linux instance

When we are working on a remote Linux instance, there are a lot of times that we need to run some intensive computation Job/Process on the instance, which are time-consuming. The Job/Process can be run for more than an hour or even a day, and the struggle connecting can ruin the whole process. I had that issue a few years ago that I need to run some experiments for more than a day and I always stuck with the message “Write Failed: broken pipe” by unstable connection. Therefore, in this post, I want to share a solution to that issue. On the one hand, you can increase the timeout of ssh to avoid the connection lost issue. However, that is not a good solution to the problem, power or the Internet outage can still ruin your process. There is a special command for this task.

On the Linux system, there is a command called “nohup“, which allows Job/Process to able to run in the background (even we are logged off). The usage of this command is very simple. We just need to run “nohup” with our regular command. 

$nohup ./testRunning "argv1" "argv2" ... &

Note that the last symbol (&) is required. This will set the system to run the process even we are logged off. However, we might want to keep the output (stdout and stderr) from the process. We can also save the result to output file by the following command

$nohup ./testRunning "argv1" "argv2" ... > out.txt 2>&1 &

The command will redirect the output from both stdout and stderr to a filename “out.txt”. The first “>” symbol pipeline stdout to filename out.txt and the second symbol “2>&1” append stderr (“2”) to stdout (“1”).

With nohup command, you don’t need to keep worrying about the connection to the instant and you don’t need to keep your machine login to the instant ( Safe some energy ( ͡❛ ͜ʖ ͡❛) ).