Contenedores ordenados Python | Una introducción

Sorted Containers es una biblioteca de colecciones ordenadas con licencia de Apache2, escrita en Python puro y rápida como extensiones C. Fue creado por Grant Jenks y es una biblioteca de código abierto. Es una colección de contenedores que nos permite insertar y quitar elementos de manera muy eficiente manteniendo un orden ordenado.

Características:

• Python puro
• Completamente documentado
• Comparación comparativa (alternativas, tiempos de ejecución, factores de carga)
• Rendimiento (a menudo más rápido que las implementaciones de C)
• API compatible (casi idéntica a los módulos blist y rbtree populares)
• Rico en funciones (por ejemplo, obtenga las cinco claves más grandes en un dictado ordenado: d.iloc [-5:])
• Diseño pragmático (por ejemplo, SortedSet es un conjunto de Python con un índice SortedList)

Contenedores:

• ListaOrdenada
• OrdenadoDict
• conjunto ordenado

Instalación:

Los usuarios de Mac y Linux pueden instalar a través del comando pip:

 sudo pip install sortedcontainers 

Lista ordenada –

La lista ordenada es una secuencia mutable ordenada en la que los valores se mantienen ordenados.

Funciones para añadir y quitar elementos:

add(value) : Una función que toma un elemento como parámetro y lo inserta en la lista manteniendo el orden ordenado. Complejidad del tiempo de ejecución: O(log(n))

actualizar (iterable) : una función que toma un iterable como entrada y actualiza SortedList agregando todos los valores de la complejidad de tiempo de ejecución iterable: O (k * log (n)).

clear() : elimina todos los valores de la lista ordenada. Complejidad del tiempo de ejecución: O(n).

descartar (valor) : elimina el valor de la lista ordenada si es un miembro. Si el valor no es un miembro, no haga nada. Complejidad del tiempo de ejecución: O(log(n)).

A continuación se muestra la implementación:

# importing libraries
from sortedcontainers import SortedList, SortedSet, SortedDict
  
# initializing a sorted list with parameters
# it takes an iterable as a parameter.
sorted_list = SortedList([1, 2, 3, 4])
  
# initializing a sorted list using default constructor
sorted_list = SortedList()
  
# inserting values one by one using add()
for i in range(5, 0, -1):
    sorted_list.add(i)
  
# prints the elements in sorted order
print('list after adding 5 elements: ', sorted_list)
  
print('list elements are: ', end = '')
  
# iterating through a sorted list
for i in sorted_list:
    print(i, end = ' ')
print()
  
# removing all elements using clear()
sorted_list.clear()
  
# adding elements using the update() function
elements = [10, 9, 8, 7, 6]
  
sorted_list.update(elements)
  
# prints the updated list in sorted order
print('list after updating: ', sorted_list)
  
# removing a particular element
sorted_list.discard(8)
  
print('list after removing one element: ', sorted_list)
  
# removing all elements
sorted_list.clear()
  
print('list after removing all elements using clear: ', sorted_list)

Producción :

list after adding 5 elements:  SortedList([1, 2, 3, 4, 5], load=1000)

list elements are: 1 2 3 4 5 

list after updating:  SortedList([6, 7, 8, 9, 10], load=1000)

list after removing one element:  SortedList([6, 7, 9, 10], load=1000)

list after removing all elements using clear:  SortedList([], load=1000)

Conjunto ordenado –

El conjunto ordenado es un conjunto mutable ordenado en el que los valores son únicos y se mantienen ordenados. El conjunto ordenado utiliza un conjunto para operaciones de conjuntos y mantiene una lista ordenada de valores. Los valores establecidos ordenados deben ser hashable y comparables.

Funciones para añadir y quitar elementos:

add(value) : Una función que toma un elemento como parámetro y lo inserta en el conjunto manteniendo el orden ordenado. Complejidad del tiempo de ejecución: O(log(n))

clear() : elimina todos los valores del conjunto ordenado. Complejidad del tiempo de ejecución: O(n)

descartar (valor) : elimina el valor del conjunto ordenado si es un miembro. Si el valor no es un miembro, no haga nada. Complejidad del tiempo de ejecución: O(log(n))

# importing libraries
from sortedcontainers import SortedList, SortedSet, SortedDict
  
# initializing a sorted set with parameters
# it takes an iterable as an argument
sorted_set = SortedSet([1, 1, 2, 3, 4])
  
# initializing a sorted set using default constructor
sorted_set = SortedSet()
  
# inserting values one by one
for i in range(5, 0, -1):
    sorted_set.add(i)
  
print('set after adding elements: ', sorted_set)
  
# inserting duplicate value
sorted_set.add(5)
  
print('set after inserting duplicate element: ', sorted_set)
  
# discarding an element
sorted_set.discard(4)
  
print('set after discarding: ', sorted_set)
  
# checking membership using 'in' operator
if(2 in sorted_set):
    print('2 is present')
else:
    print('2 is not present')
  
print('set elements are: ', end = '')
  
# iterating through a sorted set
for i in sorted_set:
    print(i, end = ' ')
print()

Producción :

set after adding elements:  SortedSet([1, 2, 3, 4, 5], key=None, load=1000)

set after inserting duplicate element:  SortedSet([1, 2, 3, 4, 5], key=None, load=1000)

set after discarding:  SortedSet([1, 2, 3, 5], key=None, load=1000)

2 is present

set elements are: 1 2 3 5

dictado ordenado –

El dictado ordenado es una asignación mutable ordenada en la que las claves se mantienen ordenadas. El dict ordenado hereda de dict para almacenar elementos y mantiene una lista ordenada de claves. Las claves de dictado ordenadas deben ser hashable y comparables.

Funciones para añadir y quitar elementos:

setdefault(key, default = None) : valor devuelto para el elemento identificado por clave en dictamen ordenado. Si la clave está en el dictado ordenado, devuelva su valor. Si la clave no está en el dictado ordenado, inserte la clave con el valor predeterminado y devuelva el valor predeterminado. Complejidad del tiempo de ejecución: O(log(n))

clear() : elimina todos los valores del dictamen ordenado. Complejidad del tiempo de ejecución: O(n)

get(key, default) : Devuelve el valor de la clave si la clave está en el diccionario, de lo contrario, el valor predeterminado.

# importing libraries
from sortedcontainers import SortedList, SortedSet, SortedDict
  
# initializing a sorted dict with parameters
# it takes a dictionary object as a parameter
sorted_dict = SortedDict({'a': 1, 'b': 2, 'c': 3})
  
# initializing a sorted dict
sorted_dict = SortedDict({'a': 1, 'c': 2, 'b':3})
  
# print the dict
print('sorted dict is: ', sorted_dict)
  
# adding key => value pairs
sorted_dict['d'] = 3
  
print('sorted dict after adding an element: ', sorted_dict)
  
# adding element using setdefault()
sorted_dict.setdefault('e', 4)
  
print('sorted dict after setdefault(): ', sorted_dict)
  
# using the get function
print('using the get function to print the value of a: ', sorted_dict.get('a', 0))
  
# checking membership using 'in' operator
if('a' in sorted_dict):
    print('a is present')
else:
    print('a is not present')
  
print('dict elements are: ', end = '')
  
# iterating over key => value pairs in a dictionary
for key in sorted_dict:
    print('{} -> {}'.format(key, sorted_dict[key]), end = ' ')
print()
  
# removing all elements from the dict
sorted_dict.clear()
  
print('sorted dict after removing all elements: ', sorted_dict)

Producción :

sorted dict is:  SortedDict(None, 1000, {'a': 1, 'b': 3, 'c': 2})

sorted dict after adding an element:  SortedDict(None, 1000, {'a': 1, 'b': 3, 'c': 2, 'd': 3})

sorted dict after setdefault():  SortedDict(None, 1000, {'a': 1, 'b': 3, 'c': 2, 'd': 3, 'e': 4})

using the get function to print the value of a:  1

a is present

dict elements are: a -> 1 b -> 3 c -> 2 d -> 3 e -> 4 

sorted dict after removing all elements:  SortedDict(None, 1000, {})

Referencia: http://www.grantjenks.com/docs/sortedcontainers/index.html