Sequences with Memory Management In Python

 

Introduction

A Sequence contains items which are stored in an ordered way. The order of insertion is maintained and accessed in the same order. In Python we have below data types, to hold value(s) in sequential order. Let's see the Sequence Implementation In Python.

Sequence Types

String

Description: 

• String holds list of characters, either using single or double quotes. 
• These values once inserted are not changeable.

Syntax: str(<string>) or "<string>" or '<string>' or '''<multi line string''' or """<multi line string"""

Example: 

# single word string short

a = "Hello"

# multi line string

a = """This string is for testing,

showing the multi line string

as an example."""

Memory Allocation:

• Python 3 uses Unicode representation for str.
• Unicode takes 4bytes per character, making it memory expensive.
• To reduce memory and improve performance, three kinds of internal representations of unicode strings, but it is seem less for us the users:
• 1 byte per char (Latin-1 encoding)
• 2 bytes per char (UCS-2 encoding) 
• 4 bytes per char (UCS-4 encoding)
• Code:

import sys

# every string in Python takes additional 49-80 bytes of memory,

# where it stores supplementary information, such as hash,

# length, length in bytes, encoding type and string flags

str1 = "h"

print("str1: ", sys.getsizeof(str1)) # str1:  50

# 1-byte encoding for Latin-1, supporting mostly latin languages

# Such as English, Swedish, Italian, Norwegian, etc

str2 = "h"

print("str2: ", sys.getsizeof(str2*2)-sys.getsizeof(str2)) # str2: 1

# 2-byte encoding for UCS-2, supporting popular natural languages

# Such as Tamil, Chinese, Japanese, etc

str3 = 'அ'

print("str3: ", sys.getsizeof(str3*2)-sys.getsizeof(str3)) # str3: 2

# 4-byte encoding for UCS-4, supporting special characters

# Such as special symbols, emojis or rare languages.

str4 = '🐍'

print("str4: ", sys.getsizeof(str4*2)-sys.getsizeof(str4)) # str4: 4

• String Interning:
• String interning is python interpreter technique to that keeps just one copy of same short string (not exceeding 20 characters), making save space and speeds the string comparison.
• Internally, string interning is maintained by a global dictionary where strings are used as keys
• Other than strings it is used in function and class names, variable names, argument names, constants (all strings that are defined in the code), keys of dictionaries, names of attributes
• Code:

str1 = "Helloworld"

str2 = "Helloworld"

print(id(str1), id(str2))

# 140616358072432 140616358072432

• Visualization

Credits: https://arpitbhayani.me/blogs/string-interning

• Reference: https://rushter.com/blog/python-strings-and-memory/

List

Description: 

• Lists store multiple values in ordered format. 
• In list we can have more than one datatype, eg in one list we can have both string or tuple or number and so on together.

Syntax: list(<values>) or [<values>]

Example:

mylist = ["apple", "banana", "cherry", 1]

Memory Allocation:

• Let's check much currently the memory is allocated.

  Source:

  # check the memory allocated

  import sys

  print(sys.getsizeof(list1))

  
  
  Output:
  

  96

  Common function to see the how much memory is allocated before and after values append.

  # appending the new item

  def append_into_list(value):

  print("address: ", id(list1))

  print("before size of list: ", sys.getsizeof(list1))

  list1.append(value)

  print("updated list: ", list1)

  print("address remains the same: ", id(list1))

  print("after sizes of list: ", sys.getsizeof(list1))

  print("")

  Please closely observe the size and memory address of the list before and post update.

  Note: In the below scenario the memory address didn't change, but it will always not be the case

  # lets see after adding couple of more values the list size

  append_into_list(6)

  append_into_list(7)

  append_into_list(8)

  append_into_list(9)

  append_into_list(10)

  append_into_list(11)

  append_into_list(12)

  Output:

  address: 140509666477824

  before size of list: 96

  updated list: [100, 2, 'three', 4, 5, 6]

  address remains the same: 140509666477824

  after size of list: 128

  
  

  address: 140509666477824

  before size of list: 128

  updated list: [100, 2, 'three', 4, 5, 6, 7]

  address remains the same: 140509666477824

  after size of list: 128

  
  

  address: 140509666477824

  before size of list: 128

  updated list: [100, 2, 'three', 4, 5, 6, 7, 8]

  address remains the same: 140509666477824

  after size of list: 128

  
  

  address: 140509666477824

  before size of list: 128

  updated list: [100, 2, 'three', 4, 5, 6, 7, 8, 9]

  address remains the same: 140509666477824

  after size of list: 128

  
  

  address: 140509666477824

  before size of list: 128

  updated list: [100, 2, 'three', 4, 5, 6, 7, 8, 9, 10]

  address remains the same: 140509666477824

  after size of list: 192

  
  

  address: 140509666477824

  before size of list: 192

  updated list: [100, 2, 'three', 4, 5, 6, 7, 8, 9, 10, 11]

  address remains the same: 140509666477824

  after size of list: 192

  
  

  address: 140509666477824

  before size of list: 192

  updated list: [100, 2, 'three', 4, 5, 6, 7, 8, 9, 10, 11, 12]

  address remains the same: 140509666477824

  after size of list: 192

  As you could see the size of list expanded from 96 to 128, but for next couple of items it didn't change whereas it stayed there for sometime. And then the size got expanded to 192. The reason in Cpython the memory is "preallocated" in chunks before hand. The reason is it avoids making frequent heavy system calls. As well if you see the over allocation is not static its mild and linear.

  The reallocation happens to extend the current memory needed.

  So when you have huge array in need, and the realloc is not having so much space. It will go ahead and create new memory and copy, this will be an very expensive operation.
  To avoid this we can preallocate required memory.

  Please find the below the code snippet of C implementation of List. And also the pictorial representation.

  C Source - from CPython:

  #### Cpython : https://github.com/python/cpython/blob/master/Objects/listobject.c
  '''
  /* This over-allocates proportional to the list size, making room
  * for additional growth. The over-allocation is mild, but is
  * enough to give linear-time amortized behavior over a long
  * sequence of appends() in the presence of a poorly-performing
  * system realloc().
  * Add padding to make the allocated size multiple of 4.
  * The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 88, 120, 160 ...
  * Note: new_allocated won't overflow because the largest possible value
  * is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
  */
  new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
  /* Do not overallocate if the new size is closer to overalocated size
  * than to the old size.
  */
  '''
  ### eg: if the current size is 24
  ### ((size_t)newsize + (newsize >> 3) + 6) == increases the one eighth which is 15 so 24+3 => 24+6 = 30
  ### ~(size_t)3 = -4
  ### 30 & -4 = 32
  
  
  
  
  ### Note: The calculations vary based on the size of the object used in the list

  
  

  

  Figure 1 : Memory allocation in list

  Credits : https://www.laurentluce.com/images/blog/list/list_insert.png

Tuples

Description: 

• Tuples are similar to lists but unchangeable. 
• Once defined the values cannot be changed.

Syntax: tuple(<values>) or (<values>)

Example:

mytuple = ("apple", "banana", "cherry", 1)

Memory Allocation:

• Check the memory allocated, it uses only required memory. They are not over-allocated as they are not resizable.

Source:

print(sys.getsizeof(tuple1))

Output:

72

• Reuse Memory
• To reduce memory fragmentation and speed up allocations, Python reuses old tuples.
• If a tuple no longer needed and has less than 20 items.
• Instead of deleting it permanently Python moves it to a free list and later uses it.
• Note: Though it's always not certain, the same memory will be used.

Source:

a = (1,2)

print(id(a))

del a

b = (1,2)

print(id(b))

Output:

140509665739520

140509665739520

• Empty Tuple
• When creating two empty tuple it will be point same address space.
• Empty tuple acts as a singleton, that is, there is always only one tuple with a length of zero.
• When creating an empty tuple Python points to already preallocated one.
• In such way that any empty tuple has the same address in the memory.
• This is possible because tuples are immutable and sometimes saves a lot of memory.

Source:

a = ()

b = ()

if a is b :

print("A and B are not mapped to same address")

print("address of a: ", id(a))

print("address of b: ", id(b))

print("A size of list: ", sys.getsizeof(a))

print("B size of list: ", sys.getsizeof(b))

Output:

A and B are not mapped to same address

address of a: 140509600395328

address of b: 140509600395328

A size of list: 40

B size of list: 40

Named Tuple

Description: 

• Named Tuples are with names for easy access, uses same memory. 
• Also these not changeable.

Syntax: namedtuple(<name>, <values>)

Example:

from collections import namedtuple

# Declaring namedtuple()

Student = namedtuple('Student', ['name', 'age', 'DOB'])

# Adding values

S = Student('Nandini', '19', '2541997')

# Access using index

print("The Student age using index is : ", end="")

print(S[1])

# Access using name

print("The Student name using keyname is : ", end="")

print(S.name)

Memory Allocation:

• The namedtuple and normal type uses exactly same amount of memory. Because the field names are stored in the class
• So we can either use tuple or named tuple, it will be the same. And named tuple will increase the readability of the program as well. 
• Memory Allocation Source:

from collections import namedtuple

City = namedtuple("City", "name country status")

chennai = City("Chennai", "India", "Red")

print(chennai)

print("Size of named tuple: ", sys.getsizeof(chennai))

normaltuple = ("Chennai", "India", "Red")

print(normaltuple)

print("Size of normaltuple tuple: ", sys.getsizeof(normaltuple))

Output:

City(name='Chennai', country='India', status='Red')

Size of named tuple: 64

('Chennai', 'India', 'Red')

Size of normaltuple tuple: 64

Bytearray

Description: 

• Bytearray convert objects into bytearray objects, by the defined encoding method. 
• To create empty bytearray object of the specified size.

Syntax: bytearray(source, encoding, error)

• source[optional]: Initializes the array of bytes
• encoding[optional]: Encoding of the string
• errors[optional]: Takes action when encoding fails

Example: 

val = "hello"

# encoding the string with unicode 8 and 16

val1 = bytearray(val, 'utf-8')

val2 = bytearray(val, 'utf-16')

print(val1) # bytearray(b'hello')

print(val2) # bytearray(b'\xff\xfeh\x00e\x00l\x00l\x00o\x00')

 Memory Allocation:

• Fundamentally, computers just deal with numbers. They store letters and other characters by assigning a number for each one.
• To store anything in a computer, you must first encode it, i.e. convert it to bytes. For example: 
• If you want to store music, you must first encode it using MP3, WAV, etc.
• If you want to store a picture, you must first encode it using PNG, JPEG, etc.
• If you want to store text, you must first encode it using ASCII, UTF-8, etc.
• In Python, a byte string is just that: a sequence of bytes. It isn't human-readable. Under the hood, everything must be converted to a byte string before it can be stored in a computer.
• A byte string can be decoded back into a character string, if you know the encoding that was used to encode it. 
• Few Encoding Options:
• UTF-8  - "size optimized": has an advantage in the case where ASCII characters represent the majority of characters in a block of text, because UTF-8 encodes these into 8 bits (like ASCII). It is also advantageous in that a UTF-8 file containing only ASCII characters has the same encoding as an ASCII file.
• UTF-16 - "balance": is better where ASCII is not predominant, since it uses 2 bytes per character, primarily. UTF-8 will start to use 3 or more bytes for the higher order characters where UTF-16 remains at just 2 bytes for most characters.
• UTF-32 - "balance": will cover all possible characters in 4 bytes. This makes it pretty bloated. But allows using of simple algorithms as result of fixed size
• Long story short based on the encoding the memory will be allocated.
• Code:

mytext = 'Python'

x = len(mytext.encode('ascii'))

print('Length of string in Bytes:', x)

# Single byte for each character

x = len(mytext.encode('utf-8'))

print('Length of string in Bytes:', x)

# Byte Size varies for each character

x = len(mytext.encode('utf-16'))

print('Length of string in Bytes:', x)

# Fixed size for each character, 4 bytes but additionally holds 1 byte

x = len(mytext.encode('utf-32'))

print('Length of string in Bytes:', x)

"""

Output:

Length of string in Bytes: 6

Length of string in Bytes: 6

Length of string in Bytes: 14

Length of string in Bytes: 28

"""

• References
• https://stackoverflow.com/questions/6224052/what-is-the-difference-between-a-string-and-a-byte-string
• https://stackoverflow.com/questions/496321/utf-8-utf-16-and-utf-32

Bytes

Description: 

• Bytes are similar to bytesarray, but are unchangeable after defined.

Syntax: bytes(source, encoding, error)

Example:

# encoding the string with unicode 8 and 16

val1 = bytes(val, 'utf-8')

val2 = bytes(val, 'utf-16')

print(val1) # b'hello'

print(val2) # b'\xff\xfeh\x00e\x00l\x00l\x00o\x00'

Memory Allocation:

• Same as bytearray, but immutable.

Memoryview

Description: 

• Memoryview returns memoryview class object, used to access C level buffer protocol as python object. 
• Buffer protocol provides a way to access the internal data of an object. 
• Buffer protocol beneath the covers to avoid copies and just juggle pointers to data, when performing slices. 
• Memoryview objects supports the buffer protocol without copying. 
• It yields large performance gains when operating on large objects since it doesn’t create a copy when slicing.

Syntax: memoryview(obj)

Example:

byte_array = bytearray('XYZ', 'utf-8')

mv = memoryview(byte_array)

print(mv[0]) # 88

print(chr(mv[0])) # X

print(bytes(mv[0:1])) # b'X'

print(mv.obj) # bytearray(b'XYZ')

print(mv.tobytes()) # b'XYZ'

print(mv.tolist()) # [88, 89, 90]

Memory Allocation:

• The memoryview() method in Python returns a memoryview object based on the bytes or bytearray parameter. 
• It allows you to access the data without having to copy/replicate it first. 
• Here without copying means that we will obtain the reference to the data rather than the data itself.
• Ideally the memory allocated is same like bytes, based on the en.

Array

Description: 

• Arrays are used for storing same type of data.

Syntax: array(data_type, value_list)

Example:

# importing "array" for array creations

import array as arr

# creating an array with integer type

a = arr.array('i', [1, 2, 3])

Memory Allocation:

• In Arrays the memory allocation is as like List, but the difference in the datatype.
• Code:

import sys

import array as arr 

# creating an array with integer and double type

for i in range(12):

x = range(i)

iarr = arr.array('i', x) # integer

print(iarr, sys.getsizeof(iarr))

farr = arr.array('d', x) # double

print(farr, sys.getsizeof(farr))

• Output:

array('i') 64

array('d') 64

array('i', [0]) 80

array('d', [0.0]) 96

array('i', [0, 1]) 80

array('d', [0.0, 1.0]) 96

array('i', [0, 1, 2]) 80

array('d', [0.0, 1.0, 2.0]) 96

array('i', [0, 1, 2, 3]) 80

array('d', [0.0, 1.0, 2.0, 3.0]) 96

array('i', [0, 1, 2, 3, 4]) 96

array('d', [0.0, 1.0, 2.0, 3.0, 4.0]) 128

array('i', [0, 1, 2, 3, 4, 5]) 96

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0]) 128

array('i', [0, 1, 2, 3, 4, 5, 6]) 96

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0]) 128

array('i', [0, 1, 2, 3, 4, 5, 6, 7]) 96

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]) 128

array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8]) 128

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]) 192

array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) 128

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]) 192

array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) 128

array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]) 192

Deque

Description: 

• Deque (Doubly Ended Queue) performs inserts/deletions from both the ends (works as stacks and queues together)

Syntax: collections.deque([<values>])

Example:

import collections

# Create a deque

DoubleEnded = collections.deque(["Mon","Tue","Wed"])

print (DoubleEnded)

# Append to the right

print("Adding to the right: ")

DoubleEnded.append("Thu")

print (DoubleEnded) # deque(['Mon', 'Tue', 'Wed', 'Thu'])

# append to the left

print("Adding to the left: ")

DoubleEnded.appendleft("Sun")

print (DoubleEnded) # deque(['Sun', 'Mon', 'Tue', 'Wed', 'Thu'])

# Remove from the right

print("Removing from the right: ")

DoubleEnded.pop()

print (DoubleEnded) # deque(['Sun', 'Mon', 'Tue', 'Wed'])

# Remove from the left

print("Removing from the left: ")

DoubleEnded.popleft()

print (DoubleEnded) # deque(['Mon', 'Tue', 'Wed'])

# Reverse the dequeue

print("Reversing the deque: ")

DoubleEnded.reverse()

print (DoubleEnded) # deque(['Wed', 'Tue', 'Mon'])

Memory Allocation:

• Deque uses a linked list of block of 64 pointers to objects.
• Hence it reduces memory overhead since there are fewer previous and next links.
• For an empty deque, a linked list is created with a single block of 64 pointers.
• The index points to the centre using the left and right link, for append left and right.
• Code:

import collections

import sys

# Create a deque

DoubleEnded = collections.deque(["a"]*63)

print (sys.getsizeof(DoubleEnded)) # 624

# Create a deque

DoubleEnded = collections.deque(["a"]*64)

print (sys.getsizeof(DoubleEnded)) # 1152

# Create a deque

DoubleEnded = collections.deque(["a"]*128)

print (sys.getsizeof(DoubleEnded)) # 1680

• Visualization:

Credits: https://www.laurentluce.com/posts/python-deque-implementation/

• References
• https://www.laurentluce.com/posts/python-deque-implementation/

Ordered dictionary

Description: 

• Ordered dictionary is designed to remember the order of items, which is defined by the insertion order of keys. 
• When the value of a certain key is changed, the position of the key remains unchanged.

Syntax: OrderedDict()

Example:

from collections import OrderedDict

numbers = OrderedDict()

numbers["one"] = 1

numbers["two"] = 2

numbers["three"] = 3

print(numbers) # OrderedDict([('one', 1), ('two', 2), ('three', 3)])

Memory Allocation:

• As like dictionary the memory is allocated which grows linearly based on the number of keys added, but in ordered dictionary to maintain the order nearly 50% more memory is used to preserve the order of the items.
• Code:

from collections import OrderedDict

import sys

ordd = OrderedDict()

d = {}

for x in range(15):

ordd[x] = x

d[x] = x

print("ordered dict:", sys.getsizeof(ordd), "\t", "dict:", sys.getsizeof(d))

'''

Output:

-------

ordered dict: 392 dict: 232

ordered dict: 424 dict: 232

ordered dict: 456 dict: 232

ordered dict: 488 dict: 232

ordered dict: 520 dict: 232

ordered dict: 744 dict: 360

ordered dict: 776 dict: 360

ordered dict: 808 dict: 360

ordered dict: 840 dict: 360

ordered dict: 872 dict: 360

ordered dict: 1312 dict: 640

ordered dict: 1344 dict: 640

ordered dict: 1376 dict: 640

ordered dict: 1408 dict: 640

ordered dict: 1440 dict: 640

'''

• References:
• https://lerner.co.il/2019/05/12/python-dicts-and-memory-usage/

User string

Description: 

• To support a string like a container called UserString present in the collections module. 
• UserString class acts as a wrapper class around the string objects. 
• It is useful when need create a string of their own with some modified functionality or with some new functionality. 
• Also can be considered as a way of adding new behaviours for the string. 
• It takes any argument that can be converted to string and simulates a string whose content is kept in a regular string. 
• String is accessible by the data attribute of this class.

Syntax: collections.UserString(seq)

Example: 

from collections import UserString

d = 12344

# Creating an UserDict

userS = UserString(d)

print(userS.data)

# Creating an empty UserDict

userS = UserString("")

print(userS.data)

Memory Allocation:

• Similar to string
• Code:

from collections import UserString

import sys

d = "x"*10000

# Creating an UserDict

userS = UserString(d)

print(sys.getsizeof(d), sys.getsizeof(userS.data))

• Output:

10049 10049

User list

Description: 

• User list is similar to user string, instead of string uses list class implementation to edit lists features. 
• It acts as a wrapper class around the List objects.

Syntax: collections.UserList([list])

Example:

from collections import UserList

L = [1, 2, 3, 4]

# Creating a userlist

userL = UserList(L)

print(userL.data) # [1, 2, 3, 4]

# Creating empty userlist

userL = UserList()

print(userL.data) # []

# Creating a List where

# deletion is not allowed

class MyList(UserList):

# Function to stop deletion

# from List

def remove(self, s = None):

raise RuntimeError("Deletion not allowed")

 

    # Function to stop pop from

# List

def pop(self, s = None):

raise RuntimeError("Deletion not allowed")

# Driver's code

L = MyList([1, 2, 3, 4])

# Inserting to List"

L.append(5)

print("After Insertion")

print(L) # [1, 2, 3, 4, 5]

# Deleting From List

L.remove() # Exception will be raised here: Traceback ... RuntimeError: Deletion not allowed 

Memory Allocation:

• Similar to list

NumPy

Description: 

• NumPy is a Python library used for working with arrays.
• It also has functions for working in domain of linear algebra, fourier transform, and matrices.
• NumPy stands for Numerical Python.
• We already have lists that serve the purpose of arrays, but they are slow to process.
• NumPy aims to provide an array object that is up to 50x faster than traditional Python lists.
• The array object in NumPy is called ndarray, it provides a lot of supporting functions that make working with ndarray very easy.
• NumPy arrays are stored at one continuous place in memory unlike lists, so processes can access and manipulate them very efficiently.
• This behaviour is called locality of reference in computer science.
• This is the main reason why NumPy is faster than lists. Also it is optimized to work with latest CPU architectures

Syntax: numpy.array(<list>)

Example:

import numpy

arr = numpy.array([1, 2, 3, 4, 5])

print(arr) # [1 2 3 4 5]

Memory Allocation:

• Similar to arrays depends on the datatype saved.
• Different dtypes have different ranges of values they can represent:
• 16-bit uint range is 0-65535.
• 64-bit uint range is 0-18446744073709551615.
• And they have different levels of memory usage; a 64-bit integer uses 4× memory than a 16-bit integer.
• Code:

from numpy import ones

import numpy as np

int64arr = ones((1024, 1024), dtype=np.uint64)

int16arr = ones((1024, 1024), dtype=np.uint16)

print(int16arr.nbytes, int64arr.nbytes) # 2097152 8388608

• References:
• https://pythonspeed.com/articles/numpy-memory-footprint/

Grouping Sequence

All the above datatypes can be grouped in few forms, below we have tried to group in two forms.

Mutable vs Immutable

Mutable	Immutable
Values can be changed	Values can not be changed after definition
Types list  bytearray  array.array collections.deque memoryview collections.ordereddictionary collections.userstring collections.userlist	Types tuple named tuple str bytes

Flat vs Container Sequences

Flat sequences	Container Sequences
Holds items on one type.	Holds items of different types
Called homogeneous	Called heterogeneous
Are more compact, more efficient than heterogeneous in terms of storage and operations.	Less compact, but easy to use as structure which holds multiple types together
Types str  bytes byte array memory view array	Types list tuples collections.deque collections.ordereddictionary collections.userstring collections.userlist

Sequence Operations

Concatenation

Description: 

• The operator (+) is used to concatenate the second element to the first. 
• We can concatenate all other sequences like this.

Syntax: x + y

Example:

east = ['New York', 'New Jersey']

west = ['San Diego', 'San Francisco']

cities = east + west

print(cities) # ['New York', 'New Jersey', 'San Diego', 'San Francisco']

Membership Operators

In

Description:

• Search the value in the sequence using in operator.

Syntax: x in seq / x not in seq

Example:

cities = ['San Francisco', 'New York', 'Washington DC']

print('New York' in cities) # True

Slicing

Description:

• Slicing returns the substring range of characters by using slice.

Syntax: a[start:stop:skip]

Example: 

b = "Hello, World!"

# slice inbetween of the string

print(b[2:5]) # llo

# slice start of the string

print(b[:5]) # Hello

# slice end of the string

print(b[7:]) # World!

# negative slicing of the string

print(b[-6:]) # World!

Repeating

Description:

• To repeat a sequence a number of times, use the multiplication operator (*). 
• This also works on sequences other than tuples.

Syntax: x * n or n * x

Example:

s = 'ha'

print(s*3) # hahaha

Implementation:

Min and Max

Description:

• To get the Minimum and the Maximum element in the sequence.

Syntax: min(seq) or max(seq)

Example:

print(min([5,3,2,1])) # 1

print(max([5,3,2,1])) # 5

Index

Description:

• The index() method searches an element in the sequence and returns the index of the first occurrence.

Syntax: seq.index(x[, i[, j]])

• Index of the first occurrence of x (in the index range i and j)

Example:

numbers = [1, 4, 5, 3, 5, 7, 8, 5]

print(numbers.index(5, 3, 5)) # 4

Length

Description:

• Length or number of elements in the sequence.

Syntax: len(seq)

Example:

cities = ['San Francisco', 'New York', 'Washington DC']

print(len(cities)) # 3

Count

Description:

• The count() method counts the number of times an element has occurred in the sequence.

Syntax: seq.count(x)

Example:

“Hahaha”.count(“a”) # 3

Range

Description:

• Range returns a sequence of numbers, starting from 0 by default, and increments by 1 (by default), and stops before a specified number.

Syntax: range(start, stop, step)

Example:

# get all the even numbers

x = range(0, 10, 2)

for n in x:

print(n) # 0 2 4 6 8

List comprehension

Description:

• List comprehension offers a shorter syntax when you want to create a new list based on the values of an existing list. 
• List comprehensions are faster than loops, but avoid to use when nested for readability

Syntax: newlist = [expression for item in iterable if condition == True]

Example:

# get the list of fruites which contains 'a' and change the case to upper

fruits = ["apple", "banana", "cherry", "kiwi", "mango"]

newlist = [x.upper() for x in fruits if "a" in x]

print(newlist) # ['APPLE', 'BANANA', 'MANGO']

Generator Expressions

Description:

• Generators are written just like a normal function but we use yield() instead of return() for returning a result. 
• Lazy loading is done, only when the next value is needed it will be yielded. 
• Generator over a list is that it takes much less memory. 

Syntax: yield

Example:

generator = (num ** 2 for num in range(10))

for num in generator:

    print(num) # 0 1 4 9 16 25 36 49 64 81

Packing and Unpacking

Description:

• Unpacking: We can use * to unpack the list so that all elements of it can be passed as different parameters.
• Packing: When we don’t know how many arguments need to be passed to a python function, we can use Packing to pack all arguments in a tuple.

Syntax: Operator * 

Example:

# A Python program to demonstrate both packing and

# unpacking.

# A sample python function that takes three arguments

# and prints them

def fun1(a, b, c):

print(a, b, c)

# Another sample function.

# This is an example of PACKING. All arguments passed

# to fun2 are packed into tuple *args.

def fun2(*args):

# Convert args tuple to a list so we can modify it

args = list(args)

# Modifying args

args[0] = 'Python'

args[1] = 'awesome'

# UNPACKING args and calling fun1()

fun1(*args)

# Driver code

fun2('Hello', 'beautiful', 'world!')

# Output: (Python, awesome, world!)

List sort and sorted function

Description:

• .sort() and sorted() can provide exactly the sort order you need if you use them properly with both the reverse and key optional keyword arguments. 
• Both have very different characteristics when it comes to output and in-place modifications.

Syntax: .sort() and sorted()

Example: .sort()

values_to_sort = [5, 2, 6, 1]

# Sort the list and assign to new variable

sorted_values = values_to_sort.sort()

print(sorted_values) # will not return anything rather perform inplace sort

# None

print(values_to_sort) # original list will be sorted

# [1, 2, 5, 6]

Example: sorted()

names_with_case = ['harry', 'Suzy', 'al', 'Mark']

sorted_values = sorted(names_with_case, reverse=True) # order of sort mentioned

print(sorted_values)

# ['harry', 'al', 'Suzy', 'Mark']

names_with_case # original list will be unaffected

# ['harry', 'Suzy', 'al', 'Mark']

Bisect

Description:

• Bisect algorithm is to find a position in list where an element needs to be inserted to keep the list sorted. 
• Bisect algorithms using the module “bisect” which allows to keep the list in sorted order after insertion of each element. 
• This is essential as this reduces overhead time required to sort the list again and again after insertion of each element. 
• These functions returns the position in the sorted list, where the number passed in argument can be placed so as to maintain the resultant list in sorted order.

Syntax: 

• bisect(list, num, beg, end) : If the element is already present in the list, the right most position where element has to be inserted is returned. 

• bisect_left(list, num, beg, end) : If the element is already present in the list, the left most position where element has to be inserted is returned. 

• bisect_right(list, num, beg, end) : Similar to the “bisect()”

Example:

# Python code to demonstrate the working of

# bisect(), bisect_left() and bisect_right()

# importing "bisect" for bisection operations

import bisect

# initializing list

li = [1, 3, 4, 4, 4, 6, 7]

# using bisect() to find index to insert new element

# returns 5 ( right most possible index )

print ("The rightmost index to insert, so list remains sorted is : ", end="")

print (bisect.bisect(li, 4))

# using bisect_left() to find index to insert new element

# returns 2 ( left most possible index )

print ("The leftmost index to insert, so list remains sorted is : ", end="")

print (bisect.bisect_left(li, 4))

# using bisect_right() to find index to insert new element

# returns 4 ( right most possible index )

print ("The rightmost index to insert, so list remains sorted is : ", end="")

print (bisect.bisect_right(li, 4, 0, 4))

'''

- Output:

The rightmost index to insert, so list remains sorted is : 5

The leftmost index to insert, so list remains sorted is : 2

The rightmost index to insert, so list remains sorted is : 4

- Time Complexity:

O(log(n)) -> Bisect method works on the concept of binary search

'''

Insort

Description:

• Insort returns the sorted list after inserting number in appropriate position.

Syntax:

• insort(list, num, beg, end) : If the element is already present in the list, the element is inserted at the rightmost possible position.

• insort_left(list, num, beg, end) : If the element is already present in the list, the element is inserted at the leftmost possible position.

• insort_right(list, num, beg, end) : This function works similar to the “insort()”

Example:

# Python code to demonstrate the working of

# insort(), insort_left() and insort_right()

# importing "bisect" for bisection operations

import bisect

# initializing list

li1 = [1, 3, 4, 4, 4, 6, 7]

# initializing list

li2 = [1, 3, 4, 4, 4, 6, 7]

# initializing list

li3 = [1, 3, 4, 4, 4, 6, 7]

# using insort() to insert 5 at appropriate position

# inserts at 6th position

bisect.insort(li1, 5)

print ("The list after inserting new element using insort() is : ")

for i in range(0, 7):

print(li1[i], end=" ")

# using insort_left() to insert 5 at appropriate position

# inserts at 6th position

bisect.insort_left(li2, 5)

print("\r")

print ("The list after inserting new element using insort_left() is : ")

for i in range(0, 7):

print(li2[i], end=" ")

print("\r")

# using insort_right() to insert 5 at appropriate position

# inserts at 5th position

bisect.insort_right(li3, 5, 0, 4)

print ("The list after inserting new element using insort_right() is : ")

for i in range(0, 7):

print(li3[i], end=" ")

'''

- Output:

The list after inserting new element using insort() is :

1 3 4 4 4 5 6

The list after inserting new element using insort_left() is :

1 3 4 4 4 5 6

The list after inserting new element using insort_right() is :

1 3 4 4 5 4 6

- Time Complexity:

O(n) -> Inserting an element in sorted array requires traversal

'''

Functional Programming Methods

Filter

Description:

• filter() function is used to generate an output list of values that return true when the function is called. 
• Lambda within filter() functions can be used.

Syntax: filter (function, iteratables)

Example:

def func(x):

if x>=3:

return x

y = filter(func, (1,2,3,4))

print(list(y)) # [3, 4]

Implementation:

Map

Description:

• The map() function is a higher-order function. 
• Map function accepts another function and a sequence of ‘iterables’ as parameters and provides output after applying the function to each iterable in the sequence.

Syntax: map(function, iterables)

Example: 

def function(a):

return a*a

x = map(function, (1,2,3,4)) #x is the map object

print(set(x)) # {16, 1, 4, 9}

Reduce

Description:

• The reduce() function applies a provided function to ‘iterables’ and returns a single value, as the name implies. 
• The function specifies which expression should be applied to the ‘iterables’ in this case. 
• The function tools module must be used to import this function.

Syntax: reduce(function, iteratables)

Example:

from functools import reduce

reduce(lambda a,b: a+b,[23,21,45,98]) # 187

Conclusion: 

Today we saw few sequence data types and how the its memory is managed, along with few functions to operate them. This is not an exhaustive list for Python 3 version. Please add more of your ideas and missed details in the comments!!

Reference: 

https://www.analyticsvidhya.com/blog/2021/07/python-most-powerful-functions-map-filter-and-reduce-in-5-minutes/

https://realpython.com/python-sort/

https://betterprogramming.pub/an-interviewers-favorite-question-how-are-python-strings-stored-in-internal-memory-ac0eaef9d9c2

https://rushter.com/blog/python-strings-and-memory/

https://bhattaca.github.io/cse2122/images/array-2_0.png

http://guilload.com/python-string-interning/

https://rushter.com/blog/python-strings-and-memory/

https://betterprogramming.pub/an-interviewers-favorite-question-how-are-python-strings-stored-in-internal-memory-ac0eaef9d9c2

https://github.com/python/cpython