DEV Community: Fred

Bit-wise operations and their use-cases.

Fred — Sun, 16 May 2021 14:51:09 +0000

Introduction

When learning how to write code we encounter so many operators like arithmetic operators and logical operators and for the most part, these operators solve most of our needs. but some operators are kept out of light not intentionally though they are called bitwise operators.

Today I would like to share more insight into these operations and what they are.

Some point to note is that this article isn't language-specific and no matter what language you code in you can still get a thing or two from it, I used python in this article to explain some concepts because it's the language I'm more comfortable with but that doesn't mean you won't get anything out of this article.

What are bitwise operators?

To simply put it Bitwise operations are performed on data on the bit level or representation of the data. In classical programming, we can perform bitwise operations on numeric data types like Integers and floating-point numbers, although note not all languages like python, C/C++ supports bitwise operations on floating-point numbers, JavaScript however supports this.

Here are all the available bitwise operators and their symbolic representation.

Operation	Sign
and	&
or	\|
not	~
xor	^
right shift	>>
left shift	<<

bitwise and operator

The bitwise and operator behaves like the logical and operator with bits instead of booleans so say we have a bit with rep 1 and another with 0 when we perform the bitwise and operation we get 1 & 0 = 0, so the bitwise and operator returns 1 if both bits are set else 0 for example

a = 3 #the binary representation of 3 is 0011
b = 5 #the binary representation of 5 is 0101

c = a & b
"""
if we perform the bitwise and operation on the two values we get.
0011
0101 &
----
0001 =>  which is equal to 1 in decimal so c will be equal to 1
"""

The bitwise and operator can be used for bit masking which is to make sure some bit is set while the rest are turned off. say we have the binary representation of 7 as 111 and we want to keep the least significant bit which is the first number from the right set, while we switch the remaining bit to 0. We perform the bitwise and on the number with 1 which is represented as 001 then we have

111
001 &
---
001

Is Even

We can use a property of even and odd numbers in binary representation to check if a given number is even or odd. here's a list of the first 10 integers and their binary representation.

0 => 0
1 => 1
2 => 10
3 => 11
4 => 100
5 => 101
6 => 110
7 => 111
8 => 1000
9 => 1001

If you notice from above all even numbers least significant bit i.e (The first bit from right) is 0 while for odd numbers it's 1. with this we can be able to create a function that takes in an integer and return if it's even or odd, so our function would look like this.

def is_even(num):
    if num & 1 == 1:
        return False
    return True

we check if our LSB (least significant bit) is set by bit masking it with the bitwise and operator if it's set we know it's odd and we return false else the number is even and we return true.

bitwise or operator

The bitwise or operator is used to perform the or operation on a sequence of corresponding pair bits and return 1 if either of the pair of bits is set else 0.
for Example

a = 5 # 0101
b = 7 # 0111

c = a | b

"""
0101
0111 |
---------
0111
"""

As you can see the or operator creates a union of the two bits. This feature can be used for role allocation, but we'll come back to that later.

bitwise not operator

The not operator returns a two's complement of a bit it takes in a bit and flips the bit representation i.e given a binary number 010110 the not or twos complement of the number will 101001.

Integers gotchas when using bitwise operators

So there are some things you need to be aware of when using bitwise operators. One is how many bits can be allocated to an integer and How are negative numbers represented by the computer? So Integers have a max bit size of 32 bits. That means the max value an integer can hold is 2^32, but that's not the case for positive integers because we need an extra bit to represent the sign of the number if it's positive or negative and we do that by setting the most significant bit i.e the first bit from the left to 0 if the number is positive and 1 if the number is negative. We have a bit size of (2^31)-1 as the maximum number a positive integer can have and -2^31 for negative integers. However, in python the size of the integer is allocated implicitly by the interpreter but for other languages like c/c++ running on a processor with a high bit size you can use the big keyword using large integers. 32 bits integers will be represented like this in binary.

5 => 00000000 00000000 00000000 00000101
-6 => 11111111 11111111 11111111 11111010

So with this knowledge, if we perform ~5 we get -6 returned ~3 = -4, and so on. the idea is that if we complement a positive integer we get a negative integer + 1. and if we perform the not operation on the negative number we get the original positive number.

There are some use-cases of the not operator, A trick that I can think of is for rounding down positive floating numbers. However, this operation can't be done in some programming languages like python which I use to explain this operator in this article. If you find yourself in a JavaScript environment Instead of using Math.floor method you can just use ~~floatingnum to round your number like so.

~~1.5021 // this will return 1

bitwise xor operator

The bitwise returns 1 if either pair bits aren't the same and return 0 if pair bits are identical i.e

1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
1 ^ 1 = 0

Some properties of the xor operator

Performing the xor operation on its self will return 0 i.e x ^ x == 0.
Performing the xor operation on a value with negative 1 will return the two's complement of the value or not x ^ -1 == ~x.
lastly xor of a value with 0 equals the value x ^ 0 == x.

Integer swapping

A very useful use case of the xor operator I discovered recently was using it to swap two variables without the need of a temp variable, pretty cool right? Here's the python code.

x = 10
y = 15

x = x ^ y
y = x ^ y
x = x ^ y

print("x", x) # prints x 15
print("y", y) # prints y 10

Explaining this concept can be very tricky but bear with me as I try to explain it.
I showed you some bitwise properties earlier well with that knowledge we can be able to decode what's going on above.

the binary representation of 10 is 1010
and the binary representation of 15 is 1111

x = x ^ y => 1010 ^ 1111 => 0101

So now our new value for x is 0101.

y = x ^ y => 0101 ^ 1111 => 1010

To further understand what happened above let's expand the expression like so.

y = (1010 ^ 1111) ^ 1111

since bitwise operations are associative we can also write it as.

y = 1010 ^ (1111 ^ 1111)

from the properties above we know that x ^ x = 0 so,

y = 1010 ^ 0

since x ^ 0 = x,

y = 1010

So from this, we can be able to know how we get the value of x.

x = 0101 ^ 1010 => (1111 ^ 1010) ^ 1010 => 
    1111 ^ (1010 ^ 1010) => 1111 ^ 0 => 1111

That was a lot to unpack, but if you were able to understand this is basically how to swap integers using bitwise operators.

bitwise left-shift operator

The bitwise left-shift operator is used for moving bits n step to the left. So let's say we have a number represented in binary as 100110 if we perform 1 left-shift on the number like so 100110 << 1, we get 1001100. so what happened here is that all the bit from right to left shifted one position to the left and the LSB is replaced with 0. If we were to shift it by two we would end up with 10011000.

I mostly use them to get the power of two i.e a number that is 2 ^ n, because 2's power in binary always starts with 1 and followed by 0's, for example. 2 => 10, 4 => 100, 16 => 10000. so I'll just shift 1 two the power and I get the value. so 1 << 2 == 4 e.t.c.

Converting RGB to HEX

One use-case of the left shit operator is converting a tuple of RGB color to its hexadecimal form so let's take a look at how it will be done.
The first thing to note is that for each channel in RGB tuple the value ranges from 0 - 255, which means that the can be represented as 8 bits integers. So given our 32-bit integer bit space, and an RGB tuple of (10, 128, 1) can be represented as.

00000000 00000000 00000000 00001010 => 10 => R
00000000 00000000 00000000 10000000 => 128 => G
00000000 00000000 00000000 00000001 => 1 => B

A hex color is a string of a hexadecimal value of length 6. The hex value is divided into 3 parts each represents either red, green, and blue. For example #10ff0e red = 10, green = ff, e = 0e in hex. So to combine RGB and produce a hex value we use left-shift to move every channel to its corresponding position. we shift the red channel to the 24th bit by shifting all its bit by 16 to the left then we do that also for the green but by 8 and we leave the blue channel the same. we then merge the integers by performing a bitwise or on them so it would be like so.

00000000 00001010 00000000 00000000
00000000 00000000 10000000 00000000
00000000 00000000 00000000 00000001 |
----------------------------------------
00000000 00001010 10000000 00000001 => output

So our python code will be like this.

def rgb_to_hex(rgb):
    res = rgb[0] << 16 | rgb[1] << 8 | rgb[2]
    _hex = hex(res).replace("0x", "")
    return f"#{_hex}"

bitwise right-shift operator

The bitwise right-shift operator behaves like the left-shift operator but instead of shifting the bits to the left by n, it shifts them to the right by n, therefore reducing the value. let's take a number with a binary representation of 101101 if we perform a right shift operation on the number with 1 shift we would end up with 10110 as our new value. we can also move it by any amount as we did when using left-shift.

Converting HEX to RGB

This time we are trying to convert a hex string to RGB, we use the same concept from above but inverse but this time our input is a single value. We would shift our bits to the left and bitmask it using the bitwise and operator then get our value, so it will be something like this.

inp => 00000000 00001010 10000000 00000001

       00000000 00000000 00000000 00001010 >> 16
       00000000 00000000 00000000 11111111 & => R

       00000000 00000000 00000000 10000000 >> 8
       00000000 00000000 00000000 11111111 & => G

       00000000 00000000 00000000 00000001
       00000000 00000000 00000000 00000000 & => B

So this is how the conversion works in theory, here's the python code that performs this operation.

def hex_to_rgb(hex_string):
    _hex = eval(f"0x{hex_string.replace('#','')}")
    r = _hex >> 16 & 0xff
    g = _hex >> 8 & 0xff
    b = _hex & 0xff

    return (r, g, b)

0xff here is used for bit masking its binary form is 11111111.

Creating Permissions and Role

Bitwise operators are most commonly used in applications that require users to have roles and access privileges. You'll most likely come across this if you work on an application that requires these features. So in this example, we would put everything together we've learned so far in this article to create a mini function that emulates user access role.

class Permissions:
    CAN_READ = 1
    CAN_WRITE = 1 << 1
    CAN_CREATE = 1 << 2
    CAN_DELETE = 1 << 3

Here you can use the enum type if you come from a language that supports enums, python doesn't support this type that's why I used class in place of it. one thing to note here is all the numbers are 2 ^ n from 0 to 3, which means they are the power of 2.

user = {
    "name": "sam",
    "role": Permissions.CAN_READ | Permissions.CAN_WRITE
    }

We create a user dictionary object with a name and role. the role is assigned by performing a bitwise or on the access we want to assign to the user. so if CAN_READ = 1 and CAN_WRITE = 10 performing a bitwise or will return 11. To check if a user has access we make sure the nth bit is set i.e for READ we check the 0th bit from the right, WRTIE 1st bit, CREATE 2nd bit e.t.c.

def do_operation(user, operation):
    if operation == "create":
        if Permissions.CAN_CREATE & user["role"] == \
         Permissions.CAN_CREATE:
            open("file", mode="w")
            print("file created successfully")
        else:
            print("Create Permission Required!")

    elif operation == "write":
        if Permissions.CAN_WRITE & user["role"] == \
        Permissions.CAN_WRITE:
            with open("file", "w") as f:
                f.write("00000000000000000000")
                print("wrote text to file!")
        else:
            print("Write Permission Required!")
    elif operation == "read":
        if Permissions.CAN_READ & user["role"] == \
         Permissions.CAN_READ:
            with open("file", "r") as f:
                print(f.read())
        else:
            print("Read Permission Required!")
    elif operation == "delete":
        if Permissions.CAN_DELETE & user["role"] == \
         Permissions.CAN_DELETE:
            os.remove("file")  
        else:
            print("Delete Permission Required!")

We create a function do_operation that takes in a user dictionary and an operation a user should perform, here's a list of the operations the user can perform.

create
write
read
delete

Permission is required from the user to perform the operations. if the user doesn't have the right access privilege the operation will fail. we use the bitwise and operator here to check if the nth bit for the corresponding permission is set or not.

do_operation(user, "create") #Create Permission Required!
do_operation(user, "write") # wrote text to file!
do_operation(user, "read") # 00000000000000000000
do_operation(user, "delete") # Delete Permission Required!

As you can see the operations that the user doesn't have access to failed while the rest were successful. you can play around with the code to discover new kinds of stuff and as a little assignment for you try finding out how to create a super admin role that has access to do everything.

Conclusion

Well, that's mostly it for working with bitwise operations hope you learned a lot from this and made an impact in your coding style there is a lot you can do with bitwise operators, go online and search for them or play around with it and see what cool stuff you can discover.

An Introduction to concurrency in python

Fred — Thu, 14 Jan 2021 14:00:55 +0000

So, what do we mean by running code concurrently? Well, a surface-level definition merely is running code in parallel. But shortly we would learn that is not always the case in some scenarios. Another question is why do we need to run our code concurrently? well first of it adds a performance boost to your code and it also makes working with your software smooth.
So in this post, I'm going to show you how to add concurrency to your python code to improve its performance but first, let's get a background of how python code runs normally.

Introduction

The python Interpreter runs your code in a top to bottom manner, which means that all code depends on code that is above it to run before it executes. But that's not always the case, take for example this code snippet below.

def do_something():
    time.sleep(2)
    print(10)

do_something()
print(20)

In the above code, the do_something function is called before we print 10, it sleeps for 2 sec which makes the interpreter idle then it then prints 10 before we get 20.
So imagine a scenario where we want to do stuff when our interpreter is idle in our case say we want to print 20 or do something else. one solution to that is creating threads.

Threading

What is a thread? Well according to Wikipedia "A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system". Woah that was a mouth full let me give a less technical definition based on my knowledge. A thread is a block of code that can run independently from each other and can be executed one at a time. In python only one thread can have access to the interpreter at a time this is because of the global interpreter lock (GIL) so it restricts threads from running in parallel which we would discuss more later but you can read more about the GIL here. So how do threads work? well, when you hear concurrency the first thing that comes to mind is running code at the same time or in parallel, but that's not the case with threads they just give the illusion of running in parallel. Threads are stored in memory and only run when the interpreter is idle like in a case of sending a request to a server and waiting for a response, or opening a file and waiting for the stream, any IO task that requires waiting is an excellent example of when the interpreter goes idle. The image below illustrates how a synchronous or normal python code works.

If you observe the image above you'll see that our second I/O operation was dependent on the previous and waited for 2 seconds for the first operation to complete before it ran and used another 2 seconds before the operation ends. The whole operation took about 4 seconds and that's not good, Take a look at how using threading solves this.

Like I said threads don't run in parallel, rather when another thread is idle the interpreter then executes the other thread so we save our self some waiting time and as you can see we get a performance boost, we got a runtime of 2.5 seconds.

Threading in practice.

Well, this all sounds good but let's write some code to truly get practical use of threads. first I'll write some synchronous code to see how our example code behaves.

import time

def do_something(sec):
    print("Sleeping for %d seconds..."%sec)
    time.sleep(sec)
    print("Done Sleeping for %d seconds"%sec)

start = time.time()
do_something(1)
do_something(2)
do_something(3)
do_something(4)
do_something(5)

print("Finished in %s seconds"%(time.time() - start))

Outputs

Sleeping for 1 seconds...
Done Sleeping for 1 seconds
Sleeping for 2 seconds...
Done Sleeping for 2 seconds
Sleeping for 3 seconds...
Done Sleeping for 3 seconds
Sleeping for 4 seconds...
Done Sleeping for 4 seconds
Sleeping for 5 seconds...
Done Sleeping for 5 seconds
Finished in 15.0119268894 seconds

We created a function that takes in an argument of sec then prints how many seconds it will sleep, sleeps then outputs Done sleeping for the value of sec. We then called our function with arguments from 1 to 5 inclusive. Our function will sleep for 1, 2, 3, 4, 5 seconds totaling 15 seconds before our code stop running. And if you observe the output you'll see that the function output is in other so 1 ran before 2 which also ran before 3 and so on.
Let look at how we can optimize our code with threads.

import threading
import time

def do_something(sec):
    print("Sleeping for %d seconds..."%sec)
    time.sleep(sec)
    print("Done Sleeping for %d seconds"%sec)

start = time.time()
t1 = threading.Thread(target=do_something, args=(1,))
t2 = threading.Thread(target=do_something, args=(2,))
t3 = threading.Thread(target=do_something, args=(3,))
t4 = threading.Thread(target=do_something, args=(4,))
t5 = threading.Thread(target=do_something, args=(5,))

t1.start()
t2.start()
t3.start()
t4.start()
t5.start()
print("Finished in %s seconds"%(time.time() - start))

Output

Sleeping for 5 seconds...
Sleeping for 4 seconds...
Sleeping for 3 seconds...
Sleeping for 2 seconds...
Sleeping for 1 seconds...
Finished in 0.00273704528809 seconds
Done Sleeping for 1 seconds
Done Sleeping for 2 seconds
Done Sleeping for 3 seconds
Done Sleeping for 4 seconds
Done Sleeping for 5 seconds

I'll argue that the threading code seems bulkier but I assure you it will save you that runtime and also with loops you can reduce the amount of code written. so let's walk through the code above, we import the threading module this time it contains everything we need to run threads in python. our function is still the same but this time we create a Thread object and pass in our target function note that we don't use the parathesis when we pass it to the target argument that will automatically call the function so we just pass in the function object like this target=do_something instead of target=do_something(). so how do we pass in an argument to our target function? well the threading object takes in an argument of args which is for passing in positional arguments and also kwargs for keyword arguments. we used args to pass in our sec value like so args=(2,) in our example, args take in any iterable as an argument e.g list, tuple, range e.t.c. Optionally we can also use the kwargs argument which takes in a dictionary as its argument so in our example, it would look like this kwargs={"sec":2} those are the main arguments you need to know about the Thread class. We start each thread with the start method as we see all the threads are started in order but notice that we get our finish runtime before all our function call stops. This is intentional let me explain, so after all the threads are created with the start() method the interpreter doesn't stop It goes on and executes any synchronous code left it then when a thread finishes running it runs code after the sleep here we print "Done sleeping for n seconds". How do we let the interpreter wait for our threads to finish before we run any code? well, A solution is that we use the join method to block the interpreter till our threads finish running, our code will then look like this.

import threading
import time

def do_something(sec):
    print("Sleeping for %d seconds..."%sec)
    time.sleep(sec)
    print("Done Sleeping for %d seconds"%sec)

start = time.time()
t1 = threading.Thread(target=do_something, args=(1,))
t2 = threading.Thread(target=do_something, args=(2,))
t3 = threading.Thread(target=do_something, args=(3,))
t4 = threading.Thread(target=do_something, args=(4,))
t5 = threading.Thread(target=do_something, args=(5,))

t1.start()
t2.start()
t3.start()
t4.start()
t5.start()

t1.join()
t2.join()
t3.join()
t4.join()
t5.join()
print("Finished in %s seconds"%(time.time() - start))

Outputs

Sleeping for 1 seconds...
Sleeping for 2 seconds...
Sleeping for 3 seconds...
Sleeping for 4 seconds...
Sleeping for 5 seconds...
Done Sleeping for 1 seconds
Done Sleeping for 2 seconds
Done Sleeping for 3 seconds
Done Sleeping for 4 seconds
Done Sleeping for 5 seconds
Finished in 5.00275301933 seconds

As you can see the total time of execution is output now after all the threads are completed. so the join method blocks the interpreter from doing anything until the thread it's called on runs till completion. You can try experimenting with this code for a bit, try rearranging the other of the start calls and the join calls, see what happens. It will also help you understand how everything works intuitively. We've covered threading now we would try another method which is multiprocessing.

Multiprocessing

So while threading doesn't enable you to run your code in parallel multiprocessing does that. Using multiprocessing enables you to put your CPU to good use. Modern CPUs come with multiple cores a typical modern-day PC comes with an average of 4 cores, but because of the python GIL we can't use all the cores at once, we use only one core per operation. Multiprocessing lets us make use of all our cores by creating processes that run on each core at the same time, again it is parallel. Multiprocessing shines best when doing CPU-bound tasks so in this example instead of using our dummy do_something function I'll create a function that finds all perfect squares in a given range so our code will look like this.


import time
import math

def find_perfect_squares(n):
    print(f"Finding perfect squares for values from 1 to {n}")
    res = []
    for i in range(1, n+1):
        if math.sqrt(i) in range(1, n+1):
            res.append(i)
    print(f"Found {len(res)} values in range of {n}")
    return res


start = time.time()
find_perfect_squares(1000)
find_perfect_squares(2000)
find_perfect_squares(5000)
find_perfect_squares(3000)
find_perfect_squares(100)
finished = time.time() - start 

print("Finished in %s seconds"%(finished))

Output

Finding perfect squares for values from 1 to 1000
Found 31 values in range of 1000
Finding perfect squares for values from 1 to 2000
Found 44 values in range of 2000
Finding perfect squares for values from 1 to 5000
Found 70 values in range of 5000
Finding perfect squares for values from 1 to 3000
Found 54 values in range of 3000
Finding perfect squares for values from 1 to 100
Found 10 values in range of 100
Finished in 8.968952894210815 seconds

If you observe you'll notice that our function here is highly computational and has a time complexity of O(n^2) which isn't the best. the total computation of our function calls is approximately 9 seconds. and some less computational calls e.g for range 100 has to wait for other highly computational calls like the range of 5000, we can run all of these in their individual process to boost our performance. The python multiprocessing API is similar to that of threads so learning both won't be a problem, let take a look at how to optimize this using multiprocessing.

import multiprocessing
import time
import math

def find_perfect_squares(n):
    print(f"Finding perfect squares for values from 1 to {n}")
    res = []
    for i in range(1, n+1):
        if math.sqrt(i) in range(1, n+1):
            res.append(i)
    print(f"Found {len(res)} values in range of {n}")
    return res


if __name__ == '__main__':

    start = time.time()
    args = [1000, 2000, 5000, 3000, 100]
    processes = []

    for val in args:
        p = multiprocessing.Process(target=find_perfect_squares, args=(val, ))
        processes.append(p)

    for p in processes:
        p.start()

    for p in processes:
        p.join()
    finished = time.time() - start 

    print("Finished in %s seconds"%(finished))

Output

Finding perfect squares for values from 1 to 100
Found 10 values in range of 100
Finding perfect squares for values from 1 to 1000
Found 31 values in range of 1000
Finding perfect squares for values from 1 to 2000
Found 44 values in range of 2000
Finding perfect squares for values from 1 to 3000
Found 54 values in range of 3000
Finding perfect squares for values from 1 to 5000
Found 70 values in range of 5000
Finished in 3.448301315307617 seconds

To use multiprocessing we import the multiprocessing module as we did for threading. So I tried to clean my code this time by using for-loops to create, start, and join the process. I also stored all my process object in a list. we used the join method the same as before to block the interpreter until the process is completed. Also if we notice the output we see that the other of the output isn't the same as the input here the first to finish execution is outputted followed by the second till the least which has the slowest execution time.

Make sure you create a process inside the if __name__ == "__main__" block. See the docs for more details.

There's an easier way to create processes in python, we use the Pool class to create a pool of processes and map through them like so.

from multiprocessing import Pool
#snippet
if __name__ == "__main__":
    #snippet
    p = Pool(processes=5)
    p.map(find_perfect_squares, [1000, 2000, 5000, 3000, 100])

We can also get the returned value of the function call in our process by getting the returned value of the map method which is a list of our returned values.

#snippet
pool = p.map(find_perfect_squares, [1000, 2000, 5000, 3000, 100])
print(pool)

Output

[[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961], [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 1]...]

This is a trimmed output because of the size, the index of the returned value is the same as the index of the input so pool[0] will be the returned value of find_perfect_squares(1000) and so on.

When to use which one

So like I've said before threading performs well on IO-bound like sending requests to a server, working with files, and any networking task. it doesn't work well with computational or CPU bound task and sometimes performs worst on those tasks. while multiprocessing can be used for IO tasks it also has its own drawbacks one is that every process memory scope is different and can't access the other. so it limits us to what we can do with it and it's why we mostly use it for computation. and also most times you won't need to use them unless you really need to optimize your code. but what to use depends on the type of your problem.

Dynamic Programming: 0-1 Knapsack problem

Fred — Thu, 27 Aug 2020 20:02:45 +0000

The knapsack problem is a combinatorial problem that can be optimized by using dynamic programming.
Problem: given a set of n items with set of n cost, n weights for each item. You're given a knapsack that can carry a fixed value of weight find the combination of items that maximizes the cost of items to put in the knapsack that the total weight does not surpass the maximum capacity of the knapsack.

Problem

So here's an example of the problem given above. Take a scenario where you're given a backpack that can carry about 100 kg of items and you are given five items to sell with price in dollars 120, 200, 150, 350, 100, 90 and weights for each item in kg as 15, 20, 40, 50, 20, 10 respectively. We want to know the maximum price we can get by selecting some items without surpassing the capacity. So our data structure will look like this.

values = [120, 200, 150, 350, 100, 90]
weights = [15, 20, 40, 50, 20, 10]
capacity = 100
n = len(values)

Naive Method

We are first going to solve this step by step from the naive approach then build-up to the bottom-up approach. So in the naive approach, we solve it with recursion. For each item, if the weight of the current item is less than or equal to the current capacity we take two combinations, first when we don't put the item in the knapsack and the second when we put the item and get the maximum of the two outcomes and return it.

def knapsack_naive(values, weights, capacity, n):
    if n == -1 or capacity == 0:
        return 0
    if weights[n] <= capacity:
        no_insert = knapsack_naive(values, weights, capacity, n-1)
        insert = values[n] + knapsack_naive(values, weights, capacity - weights[n], n-1)
        max_sack = max(no_insert, insert)
        return  max_sack
    else:
        return knapsack_naive(values, weights, capacity, n-1) 

print(knapsack_naive(values, weights, capacity, n-1))

Output

So as shown above our solution works, because if we analyze the items by our self we see that the maximum value we can get without surpassing the knapsack limit is the combination of items of index 0, 1, 3, 5 which corresponds with values 120, 200, 350, 90 respectively and sums up to 760, while the sum of the weight 15, 20, 50, 10 adds up to 95 which does not surpass our knapsack capacity 100. So we've got our solution but there's a problem our solution time complexity increases by $O(2^n)$ which is not good. We have to find a way to reduce the time complexity, that's where dynamic programming comes in play.

Memoization Method

In this method we reduce computation by saving computed values and reusing them in the future, instead of computing them over and over again. We create an array of n rows where n is the size of the items and capacity+1 columns to hold our computed value for each n and capacity step.

memo = [[None for _ in range(capacity+1)] for _ in range(n)]
def knapsack_memorize(values, weights, memo, capacity, n):
    if n == -1 or capacity == 0:
        return 0

    if memo[n][capacity] != None:
        return memo[n][capacity]

    if weights[n] <= capacity: 
        no_insert = knapsack_memorize(values, weights, memo, capacity, n-1)
        insert = values[n] + knapsack_memorize(values, weights, memo, capacity - weights[n], n-1)
        max_sack = max(no_insert, insert)
        memo[n][capacity] = max_sack
        return  max_sack
    else:
        memo[n][capacity] = knapsack_memorize(values, weights, memo, capacity, n-1)
        return memo[n][capacity]

Here we only change the code a little by creating a 2d array called memo to hold our computed values, after our break case we check if the value at the point n and capacity have been computed and if true we return its value and after we have computed a value we store it in the array so that it can be reused without going through the computation again. The time complexity of this method is $O (n * c a p a c i t y)$ so this is better than our previous $O(2^n)$ . If we take a case where we have 20 items and a capacity of 100 kg using the naive method, in the worst case our function will be executed 1048576 times while using the memorization method it will be executed 2000 times which is by far better than the previous.

Bottom-Up Method

The bottom-up approach is used to save memory cost that comes with recursion and bypass the recursion max stack. It does this by building up the array from the top to the bottom. And solving each sub-problem.

def knapsack_bottom_up(values, weights, capacity):
    k = [[0 for _ in range(capacity+1)] for _ in range(len(weights)+1)]

    for i in range(len(weights)+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                k[i][w] = 0
            elif weights[i-1] <= w:
                k[i][w] = max(values[i-1] + k[i-1][w - weights[i-1]], k[i-1][w])
            else:
                k[i][w] = k[i-1][w]
    return k[len(weights)][capacity]

print(knapsack_bottom_up(values, weights, capacity))

So lets break down everything above. First we create an array of capacity columns and weights length rows, this is will be the array we would build on as our knapsack. When the item index i is at 0 means we have 0 item in to put in the knapsack and the cost of 0 item is 0, so we set the score for it to 0 and also when our capacity is 0 which means we've maxed out the capacity and there's no space, we set the score for that position to 0. Then we check the weight at index i-1 we subtract 1 because list indexing start at 0 so for the first item 1 we subtract 1 to get index 0, but you can pad the weights and values list with an arbitrary value to match the indexing, a padding would look like this [None,120, 200, 150, 350, 100, 90]. We compare each weight with the value from 0 to capacity inclusive, and if the weight is less than the current capacity value we set the max cost so far at that point to the maximum of the sum of the value and the max cost of the previous value at cost weight - current cost with the previous item weight. If the weight is greater than the current cost we just set the max so far as the previous item weight. We then return the max cost so far at point len(weights) and capacity.

Python Decorators Demystified

Fred — Tue, 07 Jul 2020 19:38:05 +0000

So what are decorators? Well basically decorators are function that takes another function and wraps it. You may have seen a decorator if you've used any web development framework be it Flask or Django in Flask it looks like this.

@app.route('/home/')
def index():
    return render_template('index.html')

Functions as first-class objects

To go in depth on how decorators work we need to understand how functions in python behave. In python functions are treated as first-class objects, what that means is that functions behave like normal python objects like list, sets, integers, dict e.t.c. and can be passed to variables and stored in containers such as list and also have attributes some example.

def func(arg):
    return arg * 2

a = func
print(a(6))
print(func.__name__)

Output:

12
func

In the above code we created a function called func which returns the double of any number passed in, we then assigned the variable a to the function which means the variable a points to the address of the func object in memory. So calling a(6) will be the same as calling func(6). The last line calls the __name__ attribute of the function which returns the name of the function.

Inner Functions

Functions in python can be defined in another function and can be accessed only inside the outer function. But to access the inner function in the global scope we return it and pass it to a variable in the global scope which will be used as reference to it.

def some_function():

    def other_function(arg):
        if arg % 2 == 0: return True
        return False

    return other_function

ref = some_function()

print(ref(16))

Output:

True

As seen above the other_function is been passed to the ref variable when the some_function function is called. But if the other_function is called outside the function scope it will raise an error, so to access the other_function outside the some_function scope we return it and pass it to a variable which reference the function in memory.

Use Case

Let begin to see how all we've learned so far about functions is going to build up to decorators and an actual use case of how it's used in the real world. So we are going to create a factorial function and time it to see how long it takes on different inputs.

import time
def factorial(n):
    res = 1
    while n > 0:
        res *= n
        n -= 1
    return res


start = time.time()
factorial(2000)
finish = time.time() - start
print("Execution factorial(%d) finished in %5f(s)"%(2000, finish)) 

start = time.time()
factorial(50000)
finish = time.time() - start
print("Execution factorial(%d) finished in %5f(s)"%(50000, finish)) 

start = time.time()
factorial(100000)
finish = time.time() - start
print("Execution factorial(%d) finished in %5f(s)"%(100000, finish))

Output:

Execution factorial(2000) finished in 0.015591(s)
Execution factorial(50000) finished in 2.854175(s)
Execution factorial(100000) finished in 15.139478(s)

The factorial function is passed different input and the time elapsed in calculating the output is what we care about. So the run time got printed out, but this code seems a lot messy, and we are not abiding by the DRY (Do not repeat yourself) principle. So to make this cleaner we use what we learned above about inner functions and utilize it for our goal.

def timer(func):

    def wrapper(*args, **kwargs):
        start = time.time()
        func(*args, **kwargs)
        finish = time.time() - start
        print("Execution %s(%s) finished in %5f(s)"%(func.__name__,args[0], finish))

    return wrapper

Ok there's a lot to unpack here but I'll make sure to break it down bits by bits. So basically the timer function takes another function as an argument as func and the wrapper function is an inner function that takes any amount of positional and keyword arguments, it's common to see the wrapper function written with *args and **kwargs more on positional and keyword arguments here: https://realpython.com/python-kwargs-and-args/. The use of args and kwargs in wrapper is because we want to be able to use the decorator on different functions with varying number of arguments so in order to handle that we use args and kwargs. We create our start timer and call the function passed to the timer function with the arguments passed to the wrapper after that we print the time elapsed for calling the function, then we return the wrapper function. Here's how to use the timer function.

factorial = timer(factorial)
factorial(2000)
factorial(50000)
factorial(100000)

Output:

Execution factorial(2000) finished in 0.000000(s)
Execution factorial(50000) finished in 2.691417(s)
Execution factorial(100000) finished in 14.838543(s)

We called the timer function and pass it the factorial function as argument and the wrapper function will be returned and passed to the factorial variable so the factorial is now a reference to the wrapper function and when executing factorial(n) is the same as executing wrapper(n). The reason we pass in the original factorial function to the timer is for it to be available only in the local scope as func which is accessible to wrapper since its in the timer function. So when we call the factorial of any number we are calling the wrapper function and accessing the original factorial function pass the values to it and record its runtime and printing it out.

Python Syntax Sugar

So what we built is a decorator in a sense, but to make this more pythonic, python have a syntax to make decorators easier to write using the @ sign. The decorator is put above the function it wants to wrap and that's basically it.

@timer
def factorial(n):
    res = 1
    while n > 0:
        res *= n
        n -= 1
    return res


factorial(2000)
factorial(50000)
factorial(100000)

It works the same as previous just more clean and pythonic and now the timer can be used for any function and that's why we needed to add args and kwargs to the wrapper because we don't know how many arguments may be passed in, as seen below we created a function that takes two parameters and the wrapper gets the value and pass it to the func.

@timer
def waist_time(s,t):
    for _ in range(t):
        time.sleep(s)

Output:

Execution waist_time(1) finished in 10.009515(s)

Some Constraints

There's a caveat when using decorators the function which is being wrapped by the decorator attributes will be changed to the wrapper function attributes as seen below.

print(waist_time.__name__)

Output:

wrapper

This may not be a big deal to you or even change the functionality of your code, but its necessary to retain the function name for debugging purpose, so to retain the properties of the original function we wrap, to do this we use the wrap function in the functools module and decorate the wrapper function with it like this.

import functools

def timer(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        func(*args, **kwargs)
        finish = time.time() - start
        print("Execution %s(%s) finished in %5f(s)"%(func.__name__,args[0], finish))

    return wrapper

So running the defining the decorator like this and retains the attribute of the wrapped function and calling the __name__ attribute it returns the function name.

Nested Decorators

A function can be decorated with more than one decorator and the top decorator wraps the one below and the one below wraps what's below it.

def pad_0(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        a = func()
        res = '0' + a + '0'
        return res
    return wrapper

def pad_5(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        a = func()
        res = '5' + a + '5'
        return res
    return wrapper

@pad_5
@pad_0
def greet(name):
    return "Hello %s"%(name)

print(greet("sarah"))

Output:

50Hello sarah05

As seen above the pad_0 function wraps the greet function output then the pad_5 function wraps the pad_0 function and returns the output. More decorators can be stacked on top, but it begins to get difficult to manage or debug the function so you'll mostly use 3 to 1 decorators. And another useful thing to note is that the order of how the decorators are staked matters and changes the output take a look at this.

@pad_0
@pad_5
def greet(name):
    return "Hello %s"%(name)

print(greet("sarah"))

Output:

05Hello sarah50

As you can see the output changes if the order of the decorator is changed slightly so it's a good thing to note when using stacked decorators.

Decorator Argument

Decorators can be passed in arguments like normal function but doing this requires two or more nested functions in the decorator.
some example is @app.route('/home/'), here '/home/' is our argument passed to the route decorator, Here's how to create one.

def repeat_n_times(n):
    def dec_wrapper(func):
        def wrapper(*args, **kwargs):
            for _ in range(n):
                print(func(*args, **kwargs))
        return wrapper
    return dec_wrapper

@repeat_n_times(5)
def say_hello():
    return "hello world!"
say_hello()

Output:

hello world!
hello world!
hello world!
hello world!
hello world!

Advanced Use Case

One advanced use case of decorators are for memoization used in dynamic programming, basically what the memoization is trying to do is reduce redundant function calls to improve speed of a program by storing computed output and access them in the future instead of re-computing it. so an example will be calculating Fibonacci sequence. An understanding of Fibonacci sequence and how to write a recursive algorithm to solve it in python is required, so you can check this out https://www.edureka.co/blog/python-fibonacci-series/ or follow along.

def memoize_fibb(func):

    @functools.wraps(func)
    def wrapper(num):
        if len(wrapper.memo) == 0:
            wrapper.memo = [None] * (num+1)
        elif wrapper.memo[num]:
            return wrapper.memo[num]
        wrapper.memo[num] = func(num)
        return wrapper.memo[num]

    wrapper.memo = []
    return wrapper

@memoize_fibb
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(13))

The wrapper.memo is an attribute of the wrapper function and its a list which is initialized with n+1 values of none on the first call, then we check if the nth value is something other than None then we return the value in the list else we calculate it and store its value in the list on every function call.

DEV Community: Fred

Bit-wise operations and their use-cases.

Introduction

What are bitwise operators?

bitwise and operator

Is Even

bitwise or operator

bitwise not operator

Integers gotchas when using bitwise operators

bitwise xor operator

Some properties of the xor operator

Integer swapping

bitwise left-shift operator

Converting RGB to HEX

bitwise right-shift operator

Converting HEX to RGB

Creating Permissions and Role

Conclusion

An Introduction to concurrency in python

Introduction

Threading

Threading in practice.

Multiprocessing

When to use which one

Further Reading Resources

Dynamic Programming: 0-1 Knapsack problem

Problem

Naive Method

Output

Memoization Method

Bottom-Up Method

Python Decorators Demystified

Functions as first-class objects

Inner Functions

Use Case

Output:

Python Syntax Sugar

Some Constraints

Nested Decorators

Decorator Argument

Advanced Use Case