🚶🏾‍♂️Random Walk in Python and Julia


Random walk, also known as drunkard’s walk, is starting at some position and randomly taking the next step. In its simplest form, you can generate it in one-dimension using the following pseudocode:

Parameters:
-----------
T: number of steps to take
Initialise position = random position
for t = 1 to T-1 do
    Set position = position + randomly choose between -1 and -1
end for

The result will look something like this. The plot below shows ten random walks for 5000 steps. Random walk plot

Python

This is how the random walker will look like in pure Python.

class Walker1D:
    """Random Walker in 1D space"""
    def __init__(self, initial_position=0):
        """
        Parameters
        ----------
        initial_position: int, optional
            The initial position of the walker in 1D space
        """
        self.pos = initial_position
        
    def move(self, pos):
        """Move the walker to next position
        
        Parameters
        ----------
        pos: int
            The current position of the walker            
        """
        return pos + random.randint(-1,+1)

    def walk(self, steps):
        """Take a random walk for given steps
        
        Parameters
        ----------
        steps: int
            Number to steps to take during this walk
        """
        pos = 0
        trajectory = [pos]
        for _ in range(0, steps):
            new_pos = self.move(pos)
            trajectory.append(new_pos)
            pos = new_pos
        return trajectory
StepsTime (ms)
10^33.22
10^61,370
10^714,700
10^8129,000
10^91,680,000

Julia

And this is the Julia counterpart. Here, we make use of struct.

"""
Encapsulates 1D walker
"""
struct Walker1D
    x::Int64
end

"""
Moves the walker to the next position
# Arguments
- `w::Walker1D`: one-dimensional walker
"""
move(w::Walker1D) = Walker1D(w.x +  rand((-1,1)))

"""
Makes the walker walk for T timesteps
# Arguments
- `w::Walker1D`: one-dimensional walker
- `T:Int64`: Number of timesteps in the walk
"""
function walk(w, T)
    trajectory = [w]
    for i ∈ 1:T
        w = move(w)
        push!(trajectory, deepcopy(w))
    end
    return trajectory
end

StepsTime (ms)
10^31.917
10^620
10^7196
10^83,370
10^9359,000

Numba

The Julia micro benchmark, if we may call it, looks quite impressive. Its wayyy faster than its Python equivalent. Julia programs compile to efficient native code via LLVM⚡️. Is there any library or a tool that can do that for python🤔 ?

Enter Numba 🙌🏽, a JIT compiler that turns the Python code into fast native code. It uses LLVM⚡️ too, and so does Swift and Rust.

Sounds very good, so what’s the catch? Well, it only works on a subset of Python and Numpy code and that’s mostly we care really.

from numba import int32
from numba.experimental import jitclass

spec = [
    ('initial_position', int32),
    ('pos', int32),
]


@jitclass(spec)
class NumbaWalker1D:
    """Random Walker in 1D space"""
    def __init__(self, initial_position=0):
        """
        Parameters
        ----------
        initial_position: int, optional
            The initial position of the walker in 1D space
        """
        self.initial_position = initial_position
        
    def initialize(self):
        self.pos = self.initial_position
        
    def move(self, pos):
        """Move the walker to next position
        
        Parameters
        ----------
        pos: int
            The current position of the walker            
        """
        return pos + random.randint(-1,+1)

    def walk(self, steps):
        """Take a random walk for given steps
        
        Parameters
        ----------
        steps: int
            Number to steps to take during this walk
        """
        self.initialize()
        trajectory = [self.pos]
        for _ in range(0, steps):
            new_pos = self.move(self.pos)
            trajectory.append(new_pos)
            pos = new_pos
        return trajectory
StepsTime (ms)
10^37.7e-5
10^658
10^7539
10^85,300
10^985,000

Results

Putting it all in one table, we observe that while Julia code is significantly faster than pure Python, Numba was able to accelerate the pure Python code in this example. Numba jitted code was significantly faster than Julia when we increased the number of step to 10^9.

StepsPythonJuliaNumba
10^33.221.9177.7e-5
10^61,3702058
10^714,700196539
10^8129,0003,3705,300
10^91,680,000359,00085,000

See also