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:
# 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
print("str1: ", sys.getsizeof(str1)) # str1: 50
# 1-byte encoding for Latin-1, supporting mostly latin languages
# Such as English, Swedish, Italian, Norwegian, etc
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
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.
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
 |
| 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))
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
- 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))
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:
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))
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)
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
- 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
- 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:
# creating an array with integer and double type
iarr = arr.array('i', x) # integer
print(iarr, sys.getsizeof(iarr))
farr = arr.array('d', x) # double
print(farr, sys.getsizeof(farr))
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
- 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:
DoubleEnded = collections.deque(["a"]*63)
print (sys.getsizeof(DoubleEnded)) # 624
DoubleEnded = collections.deque(["a"]*64)
print (sys.getsizeof(DoubleEnded)) # 1152
DoubleEnded = collections.deque(["a"]*128)
print (sys.getsizeof(DoubleEnded)) # 1680
 |
| 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
print("ordered dict:", sys.getsizeof(ordd), "\t", "dict:", sys.getsizeof(d))
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:
from collections import UserString
print(sys.getsizeof(d), sys.getsizeof(userS.data))
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:
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:
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 | Types |
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 |
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
- 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
