Abstract Base Classes/Methods – Object Oriented Programming

Abstract classes, in short, are classes that are supposed to be inherited or subclassed, rather than instantiated.

Through Abstract Classes, we can enforce a blueprint on the subclasses that inherit the Abstract Class. This means that Abstract classes can be used to define a set of methods that must be implemented by it subclasses.

Abstract classes are used when working on large projects where classes have to be inherited, and need to strictly follow certain blueprints.

Python supports Abstract Classes via the module abc from version 2.6. Using the abc module, its pretty straight forward to implement an Abstract Class.

Example 0:

import abc

class My_ABC_Class(object):
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def set_val(self, val):
        return

    @abc.abstractmethod
    def get_val(self):
        return

# Abstract Base Class defined above ^^^

# Custom class inheriting from the above Abstract Base Class, below

class MyClass(My_ABC_Class):

    def set_val(self, input):
        self.val = input

    def get_val(self):
        print("\nCalling the get_val() method")
        print("I'm part of the Abstract Methods defined in My_ABC_Class()")
        return self.val

    def hello(self):
        print("\nCalling the hello() method")
        print("I'm *not* part of the Abstract Methods defined in My_ABC_Class()")

my_class = MyClass()

my_class.set_val(10)
print(my_class.get_val())
my_class.hello()

In the code above, set_val() and get_val() are both abstract methods defined in the Abstract Class My_ABC_Class(). Hence it should be implemented in the child class inheriting from My_ABC_Class().

In the child class MyClass() , we have to strictly define the abstract classes defined in the Parent class. But the child class is free to implement other methods of their own. The hello() method is one such.

This will print :

# python abstractclasses-1.py

Calling the get_val() method
I'm part of the Abstract Methods defined in My_ABC_Class()
10

Calling the hello() method
I'm *not* part of the Abstract Methods defined in My_ABC_Class()

The code gets executed properly even if the  hello() method is not an abstract method.

Let’s check what happens if we don’t implement a method marked as an abstract method, in the child class.

Example 1:

import abc

class My_ABC_Class(object):
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def set_val(self, val):
        return

    @abc.abstractmethod
    def get_val(self):
        return

# Abstract Base Class defined above ^^^

# Custom class inheriting from the above Abstract Base Class, below

class MyClass(My_ABC_Class):

    def set_val(self, input):
        self.val = input

    def hello(self):
        print("\nCalling the hello() method")
        print("I'm *not* part of the Abstract Methods defined in My_ABC_Class()")

my_class = MyClass()

my_class.set_val(10)
print(my_class.get_val())
my_class.hello()

Example 1 is the same as Example 0 except we don’t have the get_val() method defined in the child class.

This means that we’re breaking the rule of abstraction. Let’s see what happens:

# python abstractclasses-2.py
Traceback (most recent call last):
  File "abstractclasses-2.py", line 50, in
    my_class = MyClass()
TypeError: Can't instantiate abstract class MyClass with abstract methods get_val

The traceback clearly states that the child class MyClass() cannot be instantiated since it does not implement the Abstract methods defined in it’s Parent class.

We mentioned that an Abstract class is supposed to be inherited rather than instantiated. What happens if we try instantiating an Abstract class?

Let’s use the same example, this time we’re instantiating the Abstract class though.

Example 2:

import abc

class My_ABC_Class(object):
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def set_val(self, val):
        return

    @abc.abstractmethod
        def get_val(self):
            return

# Abstract Base Class defined above ^^^

# Custom class inheriting from the above Abstract Base Class, below

class MyClass(My_ABC_Class):

    def set_val(self, input):
        self.val = input

    def hello(self):
        print("\nCalling the hello() method")
        print("I'm *not* part of the Abstract Methods defined in My_ABC_Class()")

my_class = My_ABC_Class()    # <- Instantiating the Abstract Class

my_class.set_val(10)
print(my_class.get_val())
my_class.hello()

What does this output?

# python abstractclasses-3.py
Traceback (most recent call last):
    File "abstractclasses-3.py", line 54, in <module>
       my_class = My_ABC_Class()
TypeError: Can't instantiate abstract class My_ABC_Class with abstract methods get_val, set_val

As expected, the Python interpreter says that it can’t instantiate the abstract class My_ABC_Class.

Takeaway: 

  1. An Abstract Class is supposed to be inherited, not instantiated.
  2. The Abstraction nomenclature is applied on the methods within a Class.
  3. The abstraction is enforced on methods which are marked with the decorator @abstractmethod or @abc.abstractmethod, depending on how you imported the module, from abc import abstractmethod or import abc.
  4. It is not mandatory to have all the methods defined as abstract methods, in an Abstract Class.
  5. Subclasses/Child classes are enforced to define the methods which are marked with @abstractmethod in the Parent class.
  6. Subclasses are free to create methods of their own, other than the abstract methods enforced by the Parent class.

Reference:

  1. https://pymotw.com/2/abc/
  2. Python beyond the basics – Object Oriented Programming

Instance, Class, and Static methods – Object Oriented Programming

Functions defined under a class are also called methods. Most of the methods are accessed through an instance of the class.

There are three types of methods:

  1. Instance methods
  2. Static methods
  3. Class methods

Both Static methods and Class methods can be called using the @staticmethod and @classmethod syntactic sugar respectively.

Instance methods

Instance methods are also called Bound methods since the instance is bound to the class via self. Read a simple explanation on self here.

Almost all methods are Instance methods since they are accessed through instances.

For example:

class MyClass(object):

def set_val(self, val):
    self.value = val

def get_val(self):
    print(self.value)
    return self.value

a = MyClass()
b = MyClass()

a.set_val(10)
b.set_val(100)

a.get_val()
b.get_val()

The above code snippet shows manipulating the two methods  set_val() and get_val() . These are done through the instances a and b. Hence these methods are called Instance methods.

NOTE: Instance methods have self as their first argument. self is the instance itself.

All methods defined under a class are usually called via the instance instantiated from the class. But there are methods which can work without instantiating an instance.

Class methods and Static methods don’t require an instance, and hence don’t need self as their first argument.

Static methods

Static methods are functions/methods which doesn’t need a binding to a class or an instance.

  1. Static methods, as well as Class methods, don’t require an instance to be called.
  2. Static methods doesn’t need  self or cls as the first argument since it’s not bound to an instance or class.
  3. Static methods are normal functions, but within a class.
  4. Static methods are defined with the keyword @staticmethod above the function/method.
  5. Static methods are usually used to work on Class Attributes.

=============================
A note on class attributes

Attributes set explicitly under a class (not under a function) are called Class Attributes.

For example:

class MyClass(object):
    value = 10

    def my_func(self):
        pass

In the code snippet above, value = 10 is an attribute defined under the class MyClass() and not under any functions/methods. Hence, it’s called a Class attribute.
=============================

Let’s check out an example on static methods and class attributes:

class MyClass(object):
# A class attribute
    count = 0

    def __init__(self, name):
        print("An instance is created!")
        self.name = name
        MyClass.count += 1

    # Our class method
    @staticmethod
    def status():
        print("The total number of instances are ", MyClass.count)

print(MyClass.count)

my_func_1 = MyClass("MyClass 1")
my_func_2 = MyClass("MyClass 2")
my_func_3 = MyClass("MyClass 3")

MyClass.status()
print(MyClass.count)

This prints the following:

# python statismethod.py

0
An instance is created!
An instance is created!
An instance is created!

The total number of instances are 3
3

How does the code work?

  1. The example above has a class  MyClass() with a class attribute count = 0.
  2. An __init__ magic method accepts a name variable.
  3. The __init__ method also increments the count in the count counter at each instantiation.
  4. We define a staticmethod status() which just prints the number of the instances being created. The work done in this method is not necessarily associated with the class or any functions, hence its defined as a staticmethod.
  5. We print the initial value of the counter count via the class, as MyClass.count. This will print 0since the counter is called before any instances are created.
  6. We create three instances from the class  MyClass
  7. We can check the number of instances created through the status() method and the count counter.

Another example:

class Car(object):

    def sound():
        print("vroom!")

The code above shows a method which is common to all the Car instances, and is not limited to a specific instance of Car. Hence, this can be called as a staticmethod since it’s not necessarily bound to a Class or Instance to be called.

class Car(object):

    @staticmethod
    def sound():
        print("vroom!")

Class methods

We can define functions/methods specific to classes. These are called Class methods.

The speciality of a class methods is that an instance is not required to access a class method. It can be called directly via the Class name.

Class methods are used when it’s not necessary to instantiate a class to access a method.

NOTE: A method can be set as a Class method using the decorator @classmethod.

Example:

class MyClass(object):
    value = 10

    @classmethod
    def my_func(cls):
        print("Hello")


NOTE: Class methods have cls as their first argument, instead of self.

Example:

class MyClass(object):
    count = 0

    def __init__(self, val):
        self.val = val
        MyClass.count += 1

    def set_val(self, newval):
        self.val = newval

    def get_val(self):
        return self.val

    @classmethod
    def get_count(cls):
        return cls.count

object_1 = MyClass(10)
print("\nValue of object : %s" % object_1.get_val())
print(MyClass.get_count())

object_2 = MyClass(20)
print("\nValue of object : %s" % object_2.get_val())
print(MyClass.get_count())

object_3 = MyClass(40)
print("\nValue of object : %s" % object_3.get_val())
print(MyClass.get_count())

Here, we use a get_count() function to get the number of times the counter was incremented. The counter is incremented each time an instance is created.

Since the counter is not really tied with the instance but only counts the number of instance, we set it as a classmethod, and calls it each time using MyClass.get_count()when an instance is created. The output looks as following:

# python classmethod.py

Value of object : 10
1

Value of object : 20
2

Value of object : 40
3

 

Courtsey: This was written as part of studying class and static methods. Several articles/videos have helped including but not limited to the following:

  1. https://jeffknupp.com/blog/2014/06/18/improve-your-python-python-classes-and-object-oriented-programming/
  2. Python beyond the basics – Object Oriented Programming – O’Reilly Learning Paths

 

`self` in Python – Object Oriented Programming

This article was long overdue and should have been published before many of the articles in this blog. Better late than never.

self in Python is usually used in an Object Oriented nomenclature, to denote the instance/object created from a Class.

In short, self is the instance itself.

Let’s check the following example:

class MyClass(object):
def __init__(self, name):
        self.name = name
        print("Initiating the instance!")

    def hello(self):
        print(self.name)

myclass = MyClass("Dan Inosanto")

# Calling the `hello` method via the Instance `myclass`
myclass.hello()

# Calling the `hello` method vai the class.
MyClass.hello(myclass)

The code snippet above is trivial and stupid, but I think it gets the idea across.

We have a class named MyClass() which takes a name value as an argument. It also prints the string “Initiating the instance”.  The name value is something that has to be passed while creating an instance.

The function hello() just prints the name value that is passed while instantiating the class MyClass().

We instantiate the class MyClass() as myclass and pass the string  Dan Inosanto as an argument. Read about the great Inosanto here.

Next, we call the hello() method through the instance. ie..

myclass.hello()

This should print the name we passed while instantiating MyClass() as myclass , which should be pretty obvious.

The second and last instruction is doing the same thing, but in a different way.

MyClass.hello(myclass)

Here, we call the class MyClass() directly as well as it’s method hello(). Let’s check out what both prints:

# python /tmp/test.py

Initiating the instance!
Dan Inosanto
Dan Inosanto

As we can see, both prints the same output. This means that :

myclass.hello(self) == MyClass.hello(myclass)

In general, we can say that:

<instance-name>.<method>(self) == <Class>.<method>(<instance-name>)

ie.. The keyword self actually represents the instance being instantiated from the Class. Hence self can be seen as Syntactic sugar.

Magic methods and Syntactic sugar in Python

Magic methods

Magic methods are special methods which can be defined (or already designed and available) to act on objects.

Magic methods start and end with underscores "__", and are not implicitly called by the user even though they can be. Most magic methods are used as syntactic sugar by binding it to more clear/easy_to_understand keywords.

Python is mostly objects and method calls done on objects. Many available functions in Python are actually tied to magic methodsLet’s checkout a few examples.

Example 0:

In [1]: my_var = "Hello!"

In [2]: print(my_var)
Hello!

In [3]: my_var.__repr__()
Out[3]: "'Hello!'"

As we can see, the __repr__() magic method can be called to print the object, ie.. it is bound to the print() keyword.

This is true for many other builtin keywords/operators as well.

Example 1:

In [22]: my_var = "Hello, "
In [23]: my_var1 = "How are you?"

In [24]: my_var + my_var1
Out[24]: 'Hello, How are you?'

In [25]: my_var.__add__(my_var1)
Out[25]: 'Hello, How are you?'

Here, Python interprets the + sign as a mapping to the magic method __add__(), and calls it on the L-value (Left hand object value) my_var, with the R-value (Right hand object value) as the argument.

When a builtin function is called on an object, in many cases it is mapped to the magic method.

Example 2:

In [69]: my_list_1 = ['a', 'b', 'c', 'd']

In [70]: 'a' in my_list_1
Out[70]: True

In [71]: my_list_1.__contains__("a")
Out[71]: True

The in builtin is mapped to the __contains__()method.

The methods available for an object should mostly be dependent on the type of the object.

Example 3:

In [59]: my_num = 1

In [60]: type(my_num)
Out[60]: int

In [61]: my_num.__doc__
Out[61]: Out[61]: "int(x=0) -> int or long\nint(x, base=10) -> int or long\n\nConvert a number or string to an integer, or return 0 if no arguments\nare given. ....>>>

In [62]: help(my_num)
class int(object)
| int(x=0) -> int or long
| int(x, base=10) -> int or long
|
| Convert a number or string to an integer, or return 0 if no arguments
| are given. If x is floating point, the conversion truncates towards zero.
| If x is outside the integer range, the function returns a long instead.

From the tests above, we can understand that the help() function is actually mapped to the object.__doc__ magic method. It’s the same doc string that __doc__ and help() uses.

NOTE: Due to the syntax conversion (+ to __add__(),and other conversions), operators like + , in, etc.. are also called Syntactic sugar.

What is Syntactic sugar?

According to Wikipedia, Syntact sugar is:

In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language “sweeter” for human use: things can be expressed more clearly, more concisely, or in an alternative style that some may prefer.

Hence, magic methods can be said to be Syntactic sugar. But it’s not just magic methods that are mapped to syntactic sugar methods, but higher order features such as Decorators are as well.

Example 4: 

def my_decorator(my_function):
    def inner_decorator():
        print("This happened before!")
        my_function()
        print("This happens after ")
        print("This happened at the end!")
    return inner_decorator

def my_decorated():
    print("This happened!")

var = my_decorator(my_decorated)

if __name__ == '__main__':
    var()

The example above borrows from one of the examples in the post on Decorators.

Here, my_decorator() is a decorator and is used to decorate my_decorated(). But rather than calling the decorator function my_decorator() with the argument my_decorated(), the above code can be syntactically sugar-coated as below:

def my_decorator(my_function):
    def inner_decorator():
        print("This happened before!")
        my_function()
        print("This happens after ")
        print("This happened at the end!")
    return inner_decorator

@my_decorator
def my_decorated():
    print("This happened!")

if __name__ == '__main__':
    my_decorated()

Observing both code snippets, the decorator is syntactically sugar coated and called as:

@my_decorator

instead of instantiating the decorator with the function to be decorated as an argument, ie..

var = my_decorator(my_decorated)

A few syntax resolution methods:

  1. ‘name’ in my_list       ->      my_list.__contains__(‘name’)
  2. len(my_list)                  ->      my_list.__len__()
  3. print(my_list)              ->      my_list.__repr__()
  4. my_list == “value”     ->      my_list.__eq__(“value”)
  5. my_list[5]                      ->      my_list.__getitem__(5)
  6. my_list[5:10]                 ->     my_list.__getslice__(5, 10)

NOTE: This article is written from the notes created while learning magic methods. The following articles (along with several others) were referred as part of the process.

  1. A Guide to Python’s Magic Methods, by Rafe Kettler
  2. Special method names, The Official Python 3 documentation

Method Resolution Order – Object Oriented Programming

Method Resolution Order or ‘MRO’ in short, denotes the way a programming language resolves a method or attribute. This post looks into how Method Resolution Order works, using Python.

Python supports classes inheriting from other classes. The class being inherited is called the Parent/Super class, while the class that inherits is called the Child/Sub class.

While inheriting from another class, the interpreter needs a way to resolve the methods that are being called via an instance. Hence a method resolution order is needed.

Example 0:


class A(object):
    def my_func(self):
        print("Doing this in class A")

class B(A):
    def my_func(self):
        print("Doing this in class B")

my_instance = B()
my_instance.my_func()

Structure:

  1. We’ve two classes,  class A and class B.
  2. Instantiate class B as my_instance.
  3. Call the my_func() method through the my_instance instance.

Where is the method fetched from? From class B or class A?

How does the code work?

This should be pretty obvious, the answer would be class B. But why is it being called from class B and not from class A?

Answer : The Method Resolution Order [MRO].

To understand this in depth, let’s check another example:

Example 1:

class A(object):
    def my_func(self):
        print("Doing this in Class A")

class B(A):
    pass

class C(object):
    def my_func(self):
        print("Doing this in Class C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

Structure:

  1. Four classes, class A, B, C, and D.
  2. Class D inherits from both B and C
  3. Class B inherits from A.
  4. Class A and C doesn’t inherit from any super classes, but from the object base class due to being new-style classes.
  5. Class A and class C both have a method/function named my_func().
  6. Class D is instantiated through my_instance

If we were to call the method my_func() through the my_instance() instance, which class would it be called from? Would it be from class A or class C?

How does the code work?

This won’t be as obvious as Example 0. 

  1. The instance my_instance() is created from class D.
  2. Since class Dinherits from both class B and C, the python interpreter searches for the method my_func() in both of these classes.
  3. The intrepreter finds that class B inherits from class A, and class C doesn’t have any super classes other than the default object class.
  4. Class A and class C both has the method named my_func(), and hence has to be called from one of these.
  5. Python follows a depth-first lookup order and hence ends up calling the method from class A.

Following the depth-first Method Resolution Order, the lookup would be in the order :

Class D -> Class B -> Class C

Let’s check another example, which can be a bit more complex.

Example 2:

class A(object):
    def my_func(self):
        print("Doing this in A")

class B(A):
    pass

class C(A):
    def my_func(self):
        print("doing this in C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

Structure:

  1. Four classes, class A, B, C, and D
  2. Class D inherits from both B and C
  3. Class B inherits from class A.
  4. Class C inherits from class A.
  5. Class A inherits from the default base class object.

This sort of inheritance is called the Diamond Inheritance or the Deadly Diamond of death and looks like the following:

 

220px-Diamond_inheritance.svg

Image courtsey : Wikipedia

How does the code work?

Following the depth-first Method Resolution Order, the lookup would be in the order :

Class D -> Class B -> Class A -> Class C -> Class A

In order to avoid ambiguity while doing a lookup for a method where multiple classes are inherited and involved, the MRO lookup has changed slightly from Python 2.3 onwards.

It still goes for the depth-first order, but if the occurrence of a class happens multiple times in the MRO path, it removes the initial occurrence and keeps the latter.

Hence, the look up order in Example 2 becomes:

Class D -> Class B -> Class C -> Class A.


NOTE: Python provides a method for a class to lookup the Method Resolution Order. Let’s recheck Example 2 using that.

class A(object):
    def my_func(self):
        print("Calling this from A")

class B(A):
    pass

class C(A):
    def my_func(self):
        print("\nCalling this from C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

print("\nPrint the Method Resolution Order")
print(D.mro())
print(D.__bases__)

This should print:

# python /tmp/Example-2.py

Calling this from C

Print the Method Resolution Order
class '__main__.D', class '__main__.B', class '__main__.C', class '__main__.A', type 'object'

(, )

Takeaway:

  1. Python follows a depth-first order for resolving methods and attributes.
  2. In case of multiple inheritances where the methods happen to occur more than once, python omits the first occurrence of a class in the Method Resolution Order.
  3. The <class>.mro()methods helps to understand the Medthod Resolution Order.
  4. The `__bases__` and `__base__` magic methods help to understand the Base/Parent classes of a Sub/Child class.

References:

  1. https://en.wikipedia.org/wiki/Multiple_inheritance

Decorators – Object Oriented Programming

Decorators are wrapper functions (or classes) that wrap and modify another function (or class), and change it’s behavior as required. Decorators help to modify your code without actually modifying the working function/class itself.

There are several inbuilt Decorators in Python, such as @classmethod and @staticmethod. Examples on these are due for another post.

Decorators are called to act upon a function or class, by mentioning the Decorator name just above the function/class.

Decorators are written such as it returns a function, rather than output something.

Example 0:

@my_decorator
def my_func():
    print("Hello")

my_func()

In the above code snippet, when my_func() is called, the python interpreter calls the decorator function my_decorator, executes it, and then passes the result to my_func().

The example above doesn’t do anything worth, but the following example should help to get a better idea.

NOTE: The examples below are taken from the excellent talks done by Jillian Munson (in PyGotham 2014) and Mike Burns for ThoughtBot. The URLs are at [1] and [2]. All credit goes to them.

Example 1:

def my_decorator(my_function):
    def inner_decorator():
        print("This happened before!")
        my_function()
        print("This happens after ")
        print("This happened at the end!")
    return inner_decorator

@my_decorator
def my_decorated():
    print("This happened!")

if __name__ == '__main__':
    my_decorated()


Components:

  1. A function named my_decorated().
  2. A decorator function named my_decorator().
  3. The decorator function my_decorator() has a function within itself named inner_decorator().
  4. The decorator function my_decorator(), returns the inner function inner_decorator().
    1. Every function should return a value, if not it defaults to None.
    2. my_decorator() decorator should return the inner_decorator() inner function, else the decorator cannot be used with the my_decorated() function.
    3. To understand this, test with ‘return None’ for the decorator function my_decorator().
  5. The inner function inner_decorator() is the one that actually decorates (modifies) the function my_decorated().
  6. The decorator function is called on the function my_decorated() using the format @my_decorator.
  7. The decorator function takes an argument, which can be named whatever the developer decides. When the decorator function is executed, the argument is replaced with the function name on which the decorator is executed. In our case, it would be my_decorated()

How does the code work?

  1. The function my_decorated() is called.
  2. The interpreter sees that the decorator @my_decorator is called wrt this function.
  3. The interpreter searches for a function named my_decorator()and executes it.
  4. Since the decorator function returns the inner function inner_decorator(), the python interpreter executes the inner function.
  5. It goes through each steps, reaches my_function() , and gets it executed.
  6. Once that function is executed, it goes back and continues with the execution of the decorator my_decorator().

Output:

# python decorators-1.py
This happened before! # Called from the decorator
This happened! # Called from the function
This happens after # Called from the decorator
This happened at the end! # Called from the decorator

 

Example 2:

def double(my_func):
    def inner_func(a, b):
        return 2 * my_func(a, b)
    return inner_func

@double
def adder(a, b):
    return a + b

@double
def subtractor(a, b):
    return a - b

print(adder(10, 20))
print(subtractor(6, 1))

Components:

  1. Two functions named adder() and subtractor().
  2. A decorator function named double().
  3. The decorator has an inner function named inner_func() which does the actual intended work.
  4. The decorator returns the value of the inner function inner_func()
  5. Both the adder() and subtractor()functions are decorated with the decorator double()

How does the code work?

  1. We call the adder() and subtractor() functions with a print(), since the said functions don’t print by default (due to the return statement).
  2. The python interpreter sees the decorator @double and calls it.
  3. Since the decorator returns the inner function inner_func(), the interpreter executes it.
  4. The decorator takes an argument my_func, which is always the function on which the decorator is applied, ie.. in our case my_case == adder()and my_case == subtractor().
  5. The inner function within the decorator takes arguments, which are the arguments passed to the functions that are being decorated. ie.. Any arguments passed to adder() and subtractor()are passed to inner_func().
  6. The statement return 2 * my_func(a, b) returns the value of :
    1. 2 x adder(10, 20)
    2. 2 x subtractor(6, 1)

Output:

# python decorators-2.py
60
10

Inbuilt decorators such as @staticmethod and @classmethod will be discussed in an upcoming post.

NOTE: To see how decorators are syntactically sugar coated, read Magic methods and Syntactic sugar in Python

Data Structures – Arrays

Arrays are a commonly used data structure, and is one of the first a DS student looks into.

It is created as a collection of memory addresses which are contiguous in memory. These memory locations store data of a specific type depending on the array’s type.

Advantages:

  • Arrays are easier to create since the size and type is mentioned at the creation time.
  • Arrays have constant access/lookup time since the lookup is done by accessing the memory location as an offset from the base/first element. Hence the complexity will be O(1).
  • Arrays are contiguous in memory, ie.. a 10 cell array can start at perhaps 0x0001 and end at 0x0010.

Disadvantages:

  • The size of an array has to be defined at the time of its creation. This make the size static, and hence cannot be resized later.
  • An array can only accomodate a specific data type. The type of data an array can store has to be defined at creation time. Hence, if an array is set to store integers, it can only store integers in each memory location.
  • Since the size of an array is set at the time of creation, allocating an array may fail depending on the size of the array and the available memory on the machine.
  • Inserting an element into an array can be expensive depending on the location. To insert an element at a particular position, for example ‘n’, the element already has to be moved to ‘n + 1’, the element at ‘n + 1’ to ‘n + 2’ etc.. Hence, if the position to which the element is written to is at the starting of the array, the operation will be expensive. But if the position is at the starting, it won’t be.

What is the lookup time in an array?

The elements in an array are continuguous to each other. The address of an element is looked up as an `offset` of the primary or base element. Hence, the lookup of any element in the array is constant and can be denoted by O(1).

Arrays in Python

Python doesn’t have a direct implementation of an Array. The one that closely resembles an array in python is a `list`.

The major differences between an array and a list are:

  • The size of lists are not static. It can be grown or shrinked using the `append` and `remove` methods. Arrays are static in size.
  • lists can accomodate multiple data types, while arrays cannot.
In [1]: mylist = []

In [2]: type(mylist)
Out[2]: list

In [3]: mylist.append("string")

In [4]: mylist.append(1000)

In [5]: mylist
Out[5]: ['string', 1000]


Time complexity of Arrays

  • Indexing    – O(1)
  • Insertion/Deletion at beginning – O(n) (If the array has space to shift the elements)
  • Insertion/Deletion at the end – O(1) (If the array has space at the end)
  • Deletion at the end – O(1) (Since it doesn’t have to move any elements and reorder)
  • Insertion at the middle – O(n) (Since it requires to move the elements to the right and reorder)
  • Deletion at the middle – O(n) (Since it requires to delete the element and move the ones from the right to the left)

The ‘array’ module

Python comes with a module named ‘array’ which emulates the behavior of arrays.

In [24]: import array

In [25]: myarray = array.array('i', [1,2,3,4])

In [26]: myarray
Out[26]: array('i', [1, 2, 3, 4])

 

 

 

 

 

Code complexity – The Big O notation [O(n)]

Efficiency or Complexity is how well you’re using your resources to get your code run.

Efficiency can be calculated on the basis of how much time your code takes to run/execute.

Understanding the efficiency of your code can help to reduce the complexity, thus improving the runtime efficiency further. Getting the same job done in less time and less system resources is always good.

Once you find the efficiency of your program, you can start to find ways for:

  • Reducing the complexity (or increase the efficiency) which will reduce the program run time, and hence free the computer resources in a proportional rate.
  • Try to maintain a constant or reduced run time for a growing data set, which will help your program to fare well when the input size grows.

In Computer Science, the `Big O` notation is used to indicate the effieciency or complexity of a program. It is denoted by ‘O(n)’, where ‘n’ is a mathematical function to denote the input. This is

Some examples:

O(n)
O(n³)
O(n log(n))
O(√n)
O(O(n) + 1) or O(1)

Efficiency can be measures on the best, average, and worst cases. For example, consider finding a specific alphabet from a list of all the alphabets jumbled up.

  • The worst case is your program running through all 26 iterations and finding the alphabet as the last value.
  • The best case is when your program finds it in the first iteration itself.
  • The average is when your program finds the alphabet somewhere around 12-15 iterations (ie.. half of the worst case scenario).

Study of Data structures and Algorithms aim to study program complexities, and to reduce it as much as possible.

Algorithms are a series of well-defined steps you follow to solve a problem, whereas Data Structures are specific structures by which how you layout your data. Application of well-known algorithms in a program can help in reducing the run time.

More on Time complexity and the Big O notation can be read at:

https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/Big_O_notation

 

 

`ceph-check` – A Ceph installation checker

Many a user wants to know if a Ceph cluster installation has been done to a specific suggested guideline.

Technologies like RAID is better avoided in Ceph due to an additional layer, which Ceph already takes care of.

I’ve started writing a tool which can be run from the Admin node, and it aims to check various such points.

The code can be seen at https://github.com/arvimal/ceph_check

The work is slow, really slow, due to my daily work, procrastination, and what not, even though I intend to finish this fast.

range() and enumerate()

The usual way to iterate over a range of numbers or a list in python, is to use range().

Example 0:

colors = ["yellow", "red", "blue", "white", "black"]

for i in range(len(colors)):
    print(i, colors[i])

This should output:

(0, 'yellow')
(1, 'red')
(2, 'blue')
(3, 'white')
(4, 'black')

print(), by default, returns a tuple. If we want to print it in a more presentable way, we’ll need to find the indice at which each value is, and print that as well. Re-write the code a bit, to achieve the desired output:

colors = ["yellow", "red", "blue", "white", "black"]

for i in range(len(colors)):
    color = colors[i]
    print("%d: %s" % (i, color))

This should print:

0: yellow
1: red
2: blue
3: white
4: black

We can see that the above output starts with ‘0’ since python starts counting from ‘0’. To change that to ‘1’, we’ll need to tweak the print() statement.

colors = ["yellow", "red", "blue", "white", "black"]

for i in range(len(colors)):
    color = colors[i]
    print("%d: %s" % (i + 1, color))

This should print:

1: yellow
2: red
3: blue
4: white
5: black

Even though the above code snippet isn’t that complex, a much better way exists to do this. This is where the builtin function enumerate() comes in.

enumerate() returns a tuple when passed an object which supports iteration, for example, a list. It also supports a second argument named ‘start‘ which default to 0, and can be changed depending on where to start the order. We’ll check what ‘start‘ is towards the end of this article.

colors = ["yellow", "red", "blue", "white", "black"]
print(list(enumerate(colors)))

This returns a list of a tuples.

[(0, 'yellow'), (1, 'red'), (2, 'blue'), (3, 'white'), (4, 'black')]

To get to what we desire, modify it as:

for i, color in enumerate(colors):
    print('%d: %s' % (i, color))

This outputs:

0: yellow
1: red
2: blue
3: white
4: black

Remember that we talked about that enumerate() takes a second value named ‘start‘ which defaults to ‘0’? Let’s check how that’ll help here.

The above output starts with ‘0’. ‘start’ can help to change that.

for i, color in enumerate(colors, start=1):
    print('%d: %s' % (i, color))

This should change the output as:

1: yellow
2: red
3: blue
4: white
5: black