David Landup

In this piece, the Friendly Overfitting Argument is laid out, as well as when it doesn't hold. Is overfitting in Machine Learning and Artificial Intelligence really as bad as people make it out to be?

Machine Learning: Overfitting Is Your Friend, Not Your Foe

<h2 id="introduction">Introduction</h2>
Python is one of the most suitable languages for automating tasks. Whether it's repeatable (ethical) web scraping after some time period, starting some programs on a computer start up, or automating sending mundane e-mails, Python has a lot of modules that make your life easier.
One of these is a module called <code>keyboard</code>, and it takes full control of your keyboard. With this module, you can type out anything, create hot-keys, create abbreviations, block the keyboard, wait for input, etc.
<blockquote>
In this guide, we'll take a look at how to set up and use the <code>keyboard</code> module in Python.
</blockquote>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Applications working with automating human-like processes should be developed ethically and responsibly. The <code>keyboard</code> module is made to be very observable, and thus makes it both discouraged and transparent if anyone's using it to create key-loggers or malicious bots.

 </div>
 </div>
 </div>
 <h2 id="installingthekeyboardmodule">Installing the keyboard Module</h2>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: The version of Python used in this guide is 3.8. However, the <code>keyboard</code> module can work with both Python 2.x and Python 3.x.

 </div>
 </div>
 </div>
 If you're using Linux, in order to use this library, you must install it as <code>root</code>. If you don't, you'll get an:
<pre><code class="hljs">ImportError: You must be root to use this library on linux.
</code></pre>
Also, when running your script, you should run it with root privileges:
<pre><code class="hljs">$ sudo pip3 install keyboard
$ sudo python3 my_script.py
</code></pre>
On Windows and MacOS, as the privileges work much differently - you can install it simply via <code>pip</code> and run the scripts:
<pre><code class="hljs">$ pip install keyboard
$ python my_script.py
</code></pre>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: For MacOS, you might have to allow the Terminal or other apps to change the state of your machine, such as by typing. Also keep in mind that as of September 2021, the library is still experimental on MacOS.

 </div>
 </div>
 </div>
 <h2 id="thekeyboardmodulesfunctions">The keyboard Module's Functions</h2>
There are a lot of functions in this module that can be used to simulate keyboard actions.
<ul>
<li><code>keyboard.write(message, [delay])</code> - writes a message, with or without a delay.</li>
<li><code>keyboard.wait(key)</code> - blocks the program until the <code>key</code> is pressed. The <code>key</code> is passed as a string ('space', 'esc', etc.)</li>
<li><code>keyboard.press(key)</code> - presses a key and holds until the <code>release(key)</code> function is called.</li>
<li><code>keyboard.release(key)</code> - releases a key.</li>
<li><code>keyboard.send(key)</code> - presses and releases a key.</li>
<li><code>keyboard.add_hotkey(hotkey, function)</code> - creates a <code>hotkey</code> which when pressed, executes a <code>function</code>.</li>
<li><code>keyboard.record(key)</code> - records keyboard activity until <code>key</code> is pressed.</li>
<li><code>keyboard.play(recorded_events, [speed_factor])</code> - replays events recorded with <code>keyboard.record(key)</code> function, with an optional <code>speed_factor</code>.</li>
</ul>
We'll go through all of these, though, here's a quick example:
<pre><code class="hljs">&gt;&gt;&gt; import keyboard
&gt;&gt;&gt; keyboard.write(&quot;Hello&quot;)
&gt;&gt;&gt; Hello
</code></pre>
The <code>Hello</code> message appears on the screen, in the terminal, as if you've written it. You can automate a command very easily, and create a hotkey alias for it. Here's a (crude) example of exiting the Python REPL, writing a <code>curl</code> command and executing it:
<pre><code class="hljs">&gt;&gt;&gt; import keyboard
&gt;&gt;&gt; keyboard.write(&quot;exit()&quot;); keyboard.send(&quot;enter&quot;); keyboard.write(&quot;curl https://www.google.com&quot;); keyboard.send(&quot;enter&quot;);
&gt;&gt;&gt; exit()
curl https://www.google.com
$ curl https://www.google.com
&lt;!doctype html&gt;&lt;html itemscope=&quot;&quot;...
</code></pre>
<h2 id="keyboardswriteandwaitfunctions">keyboard's write() and wait() Functions</h2>
The <code>write()</code> command writes a message, as we've seen before, with an optional delay in the start. If no delay is set, writing is instant. It's very nicely combined with the <code>wait()</code> function, which awaits a certain key to be pressed.
For instance, we can create a make-shift macro, tied to, say <code>1</code>, which responds to that input with a new message. Note that there's an actual way to create hotkeys instead of this, which we'll cover later.
We'll create an infinite <code>True</code> loop to check for the key being pressed, and you can run the script in the background:
<pre><code class="hljs">import keyboard

while True:
 keyboard.wait(&quot;1&quot;)
 keyboard.write(&quot;\n The key &#x27;1&#x27; was pressed!&quot;)
</code></pre>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Special characters are not supported by this function, so if you add, say, <code>!</code> - you'll get hit with a <code>StopIteration</code> exception.

 </div>
 </div>
 </div>
 <h2 id="keyboardspressreleasefunctions">keyboard's press(), release() Functions</h2>
Since it's hard to simulate <code>press()</code> and <code>release()</code> so that the actions are visible, we'll also see <code>record()</code> and <code>play()</code> in action.
The <code>press()</code> function presses a key and releases it when you call <code>release()</code> on the same key. Note that you can't <code>sleep()</code> for some time to simulate holding down a key:
<pre><code class="hljs">&gt;&gt;&gt; import keyboard
&gt;&gt;&gt; from time import sleep
&gt;&gt;&gt; keyboard.press(&quot;a&quot;)
&gt;&gt;&gt; sleep(1)
&gt;&gt;&gt; keyboard.release(&quot;a&quot;)
&gt;&gt;&gt; a
</code></pre>
However, you can hold down some special keys, such as [SHIFT] or [CTRL] this way:
<pre><code class="hljs">&gt;&gt;&gt; keyboard.press(&quot;shift&quot;)
&gt;&gt;&gt; keyboard.write(&quot;lowercase&quot;)
&gt;&gt;&gt; keyboard.release(&quot;shift&quot;)

&gt;&gt;&gt; LOWERCASE
</code></pre>
<h2 id="keyboardsrecordandplayfunctions">keyboard's record() and play() Functions</h2>
It's not always about inputting new keys in - sometimes, you'd like to record what's going on and play it back. Keep in mind that you'll need administrator privileges to record any input like this, as the technology can easily be used to create keyloggers.
The <code>record()</code> function accepts a trigger key, until which it records, and returns a sequence of events of type <code>KeyboardEvent</code>. You can then chuck this sequence of events into the <code>play()</code> function, which faithfully replays them, with an optional <code>speed_factor</code> argument that acts as a multiplier for the speed of the original events:
<pre><code class="hljs">import keyboard
recorded_events = keyboard.record(&quot;esc&quot;)
keyboard.play(recorded_events)
</code></pre>
If we're to print the <code>recorded_events</code>, they'd look something like:
<pre><code class="hljs">KeyboardEvent(w up), KeyboardEvent(o down), ...]
</code></pre>
The effects of these methods are best seen as a GIF or recreated on your machine. For instance, a sequence of writing a message, deleting it and writing a different one instead:
<img src="https://s3.stackabuse.com/media/articles/guide-to-pythons-keyboard-module-1.gif" alt="">
<h2 id="keyboardssendfunction">keyboard's send() function</h2>
The <code>send()</code> function encompasses <code>press()</code> and <code>release()</code> together, and is used for single keys, unlike <code>write()</code> which is used for entire sentences:
<pre><code class="hljs">import keyboard

recorded_events = keyboard.record(&quot;s&quot;)

keyboard.send(&quot;w&quot;)
keyboard.send(&quot;a&quot;)

keyboard.play(recorded_events)
</code></pre>
Once <code>s</code> is pressed, the <code>w</code> and <code>a</code> keys are replayed.
The <code>press()</code> function can also accept combinations of pressed keys. You can send a combination of <code>&quot;ctrl+shift+s&quot;</code> for instance and the dialogue for saving a file should pop up, if you're in an application that supports that operation:
<pre><code class="hljs">import keyboard

while True:
 keyboard.wait(&quot;s&quot;)
 keyboard.press(&quot;ctrl+shift+s&quot;)
 # Or for MacOS
 keyboard.press(&quot;command+shift+s)
</code></pre>
Though, this isn't the right way to add hotkeys. Rather, you can use the <code>add_hotkey()</code> function.
<h2 id="keyboardsadd_abbreviationfunction">keyboard's add_abbreviation() Function</h2>
The <code>add_abbreviation()</code> function is a pretty nifty one, as it allows you to define abbreviations for long inputs, and replaces the abbreviated versions with the saved full versions.
For instance, similar to how services like Google save your email for most input forms, you can create your own abbreviation and trigger it via <code>[SPACE]</code>:
<pre><code class="hljs">&gt;&gt;&gt; import keyboard
&gt;&gt;&gt; keyboard.add_abbreviation(&quot;@&quot;, &quot;john@stackabuse.com&quot;)
</code></pre>
While running, if you type <code>@</code> followed by a <code>[SPACE]</code> - the long-form input will replace the typed <code>@</code>.
<h2 id="keyboardsadd_hotkeyfunction">keyboard's add_hotkey() Function</h2>
The <code>add_hotkey()</code> function accepts a hotkey you'd like to save, or a combination of keys, and a function. It's easy to pass in anonymous lambda functions here, though you can also add named functions.
For instance, let's add a hotkey for <code>CTRL+j</code>, which triggers a lambda function that logs this:
<pre><code class="hljs">import keyboard

keyboard.add_hotkey(&quot;ctrl+alt+j&quot;, lambda: print(&quot;ctrl+alt+j was pressed&quot;))
</code></pre>
The hotkey, <code>ctrl+alt+p</code>, is saved and when you press this combination, you should see the output of the lambda.
<h2 id="conclusion">Conclusion</h2>
The <code>keyboard</code> module is a lightweight and simple library used for simulating keystrokes and simple automation in Python. It's not very feature-rich, but can be used to automate some of the tasks you might be performing in your day-to-day work, or simply for a bit of fun.
A more mature, powerful module that can be used as an alternative is <a rel="nofollow noopener noreferrer" target="_blank" href="https://pypi.org/project/pynput/">pynput</a>.

In this guide, we'll take a look at the experimental keyboard module in Python and how to automate keyboard input and keystrokes easily.

Guide to Python's keyboard Module

In this guide - we'll take a look at how to calculate the Euclidean distance between two points in Python, using Numpy.
<h2 id="whatiseuclideandistance">What is Euclidean Distance?</h2>
Euclidean distance is a fundamental distance metric pertaining to systems in Euclidean space.
<blockquote>
Euclidean space is the classical geometrical space that you get familiar with in the Math class, typically bound to 3 dimensions. Though, it can also be prescribed to any non-negative integer dimension as well.
</blockquote>
<blockquote>
Euclidean distance is the shortest line between two points in Euclidean space.
</blockquote>
The name comes from Euclid, who is widely recognized as &quot;the father of geometry&quot;, as this was the only space people at the time would typically conceive of. Through time, different types of space have been observed in Physics and Mathematics, such as Affine space, and non-Euclidean spaces and geometry are very unintuitive for our cognitive perception.
<blockquote>
In 3-dimensional Euclidean space, the shortest line between two points will always be a straight line between them, though this doesn't hold for higher dimensions.
</blockquote>
Given this fact, Euclidean distance isn't always the most useful metric to keep track of when dealing with many dimensions, and we'll focus on 2D and 3D Euclidean space to calculate the Euclidean distance.
Measuring distance for high-dimensional data is typically done with other distance metrics such as Manhattan distance.
Generally speaking, Euclidean distance has major usage in development of 3D worlds, as well as Machine Learning algorithms that include distance metrics, such as <a target="_blank" href="https://stackabuse.com/k-nearest-neighbors-algorithm-in-python-and-scikit-learn/">K-Nearest Neighbors</a>. Typically, Euclidean distance will represent how similar two data points are - assuming some clustering based on other data has already been performed.
<h3 id="mathematicalformula">Mathematical Formula</h3>
The mathematical formula for calculating the Euclidean distance between 2 points in 2D space: 
$$ 
d(p,q) = \sqrt[2]{(q_1-p_1)^2 + (q_2-p_2)^2 } 
$$ 
The formula is easily adapted to 3D space, as well as any dimension: 
$$ 
d(p,q) = \sqrt[2]{(q_1-p_1)^2 + (q_2-p_2)^2 + (q_3-p_3)^2 } 
$$ 
The general formula can be simplified to: 
$$ 
d(p,q) = \sqrt[2]{(q_1-p_1)^2 + ... + (q_n-p_n)^2 } 
$$ 
A sharp eye may notice the similarity between Euclidean distance and Pythagoras' Theorem: 
$$ 
C^2 = A^2 + B^2 
$$
$$ 
d(p,q)^2 = (q_1-p_1)^2 + (q_2-p_2)^2 
$$
There in fact is a relationship between these - Euclidean distance is calculated via Pythagoras' Theorem, given the Cartesian coordinates of two points.
<blockquote>
Because of this, Euclidean distance is sometimes known as Pythagoras' distance, as well, though, the former name is much more well-known.
</blockquote>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: The two points are vectors, but the output should be a scalar (which is the distance).

 </div>
 </div>
 </div>
 We'll be using NumPy to calculate this distance for two points, and the same approach is used for 2D and 3D spaces:
<pre><code class="hljs">import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

fig = plt.figure()
ax = fig.add_subplot(111, projection = &#x27;3d&#x27;)

ax.scatter(0, 0, 0)
ax.scatter(3, 3, 3)
plt.show()
</code></pre>
<img src="https://s3.stackabuse.com/media/articles/calculating-euclidean-distance-with-numpy-1.png" alt="two points in euclidean space">
<h2 id="calculatingeuclideandistanceinpythonwithnumpy">Calculating Euclidean Distance in Python with NumPy</h2>
First, we'll need to install the NumPy library:
<pre><code class="hljs">$ pip install numpy
</code></pre>
Now, let's import it and set up our two points, with the Cartesian coordinates as (0, 0, 0) and (3, 3, 3):
<pre><code class="hljs">import numpy as np
# Initializing the points
point_1 = np.array((0, 0, 0))
point_2 = np.array((3, 3, 3))
</code></pre>
Now, instead of performing the calculation manually, let's utilize the helper methods of NumPy to make this even easier!
<h2 id="npsqrtandnpsum">np.sqrt() and np.sum()</h2>
The operations and mathematical functions required to calculate Euclidean Distance are pretty simple: addition, subtraction, as well as the square root function. Multiple additions can be replaced with a sum, as well: 
$$ 
d(p,q) = \sqrt[2]{(q_1-p_1)^2 + (q_2-p_2)^2 + (q_3-p_3)^2 } 
$$
NumPy provides us with a <code>np.sqrt()</code> function, representing the square root function, as well as a <code>np.sum()</code> function, which represents a sum. With these, calculating the Euclidean Distance in Python is simple and intuitive:
<pre><code class="hljs"># Get the square of the difference of the 2 vectors
square = np.square(point_1 - point_2)
# Get the sum of the square
sum_square = np.sum(square)
</code></pre>
This gives us a pretty simple result:
<pre><code class="hljs">(0-3)^2 + (0-3)^2 + (0-3)^2
</code></pre>
Which is equal to 27. All that's left is to get the square root of that number:
<pre><code class="hljs"># The last step is to get the square root and print the Euclidean distance
distance = np.sqrt(sum_square)
print(distance)
</code></pre>
This results in:
<pre><code class="hljs">5.196152422706632
</code></pre>
In true Pythonic spirit, this can be shortened to just a single line:
<pre><code class="hljs">distance = np.sqrt(np.sum(np.square(point_1 - point_2)))
</code></pre>
And you can even use the built-in <code>pow()</code> and <code>sum()</code> methods of the <code>math</code> module of Python instead, though they require you to hack around a bit with the input, which is conveniently abstracted using NumPy, as the <code>pow()</code> function only works with scalars (each element in the array individually), and accepts an argument - to which power you're raising the number.
This approach, though, intuitively looks more like the formula we've used before:
<pre><code class="hljs">from math import *
distance = np.sqrt(sum(pow(a-b, 2) for a, b in zip(point_1, point_2)))
print(distance)
</code></pre>
This also results in:
<pre><code class="hljs">5.196152422706632
</code></pre>
<h2 id="nplinalgnorm">np.linalg.norm()</h2>
The <code>np.linalg.norm()</code> function represents a Mathematical norm. In essence, a norm of a vector is it's length. This length doesn't have to necessarily be the Euclidean distance, and can be other distances as well. Euclidean distance is the L2 norm of a vector (sometimes known as the Euclidean norm) and by default, the <code>norm()</code> function uses L2 - the <code>ord</code> parameter is set to 2.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 If you were to set the <code>ord</code> parameter to some other value p, you'd calculate other p-norms. For instance, the L1 norm of a vector is the Manhattan distance!

 </div>
 </div>
 </div>
 With that in mind, we can use the <code>np.linalg.norm() </code> function to calculate the Euclidean distance easily, and much more cleanly than using other functions:
<pre><code class="hljs">distance = np.linalg.norm(point_1-point_2)
print(distance)
</code></pre>
This results in the L2/Euclidean distance being printed:
<pre><code class="hljs">5.196152422706632
</code></pre>
L2 normalization and L1 normalization are heavily used in Machine Learning to normalize input data.
<blockquote>
If you'd like to learn more about feature scaling - read our <a target="_blank" href="https://stackabuse.com/feature-scaling-data-with-scikit-learn-for-machine-learning-in-python/">Guide to Feature Scaling Data with Scikit-Learn</a>!
</blockquote>
<h2 id="npdot">np.dot()</h2>
We can also use a Dot Product to calculate the Euclidean distance. In Mathematics, the Dot Product is the result of multiplying two equal-length vectors and the result is a single number - a scalar value. Because of the return type, it's sometimes also known as a &quot;scalar product&quot;. This operation is often called the inner product for the two vectors.
To calculate the dot product between 2 vectors you can use the following formula: 
$$ 
\vec{p} \cdot \vec{q} = {(q_1-p_1) + (q_2-p_2) + (q_3-p_3) } 
$$
With NumPy, we can use the <code>np.dot()</code> function, passing in two vectors.
If we calculate a Dot Product of the difference between both points, with that same difference - we get a number that's in a relationship with the Euclidean Distance between those two vectors. Extracting the square root of that number nets us the distance we're searching for:
<pre><code class="hljs"># Take the difference between the 2 points
diff = point_1 - point_2
# Perform the dot product on the point with itself to get the sum of the squares
sum_square = np.dot(diff, diff)
# Get the square root of the result
distance = np.sqrt(sum_square)
print(distance)
</code></pre>
Of course, you can shorten this to a one-liner as well:
<pre><code class="hljs">distance = np.sqrt(np.dot(point_1-point_2, point_1-point_2))
print(distance)
</code></pre>
<pre><code class="hljs">5.196152422706632
</code></pre>
<h2 id="usingthebuiltinmathdist">Using the Built-In math.dist()</h2>
Python has its built-in method, in the <code>math</code> module, that calculates the distance between 2 points in 3d space. However, this only works with Python 3.8 or later.
<code>math.dist()</code> takes in two parameters, which are the two points, and returns the Euclidean distance between those points.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Please note that the two points must have the same dimensions (i.e both in 2d or 3d space).

 </div>
 </div>
 </div>
 Now, to calculate the Euclidean Distance between these two points, we just chuck them into the <code>dist()</code> method:
<pre><code class="hljs">import math
distance = math.dist(point_1, point_2)
print(distance)
</code></pre>
<pre><code class="hljs">5.196152422706632
</code></pre>
<h2 id="conclusion">Conclusion</h2>
Euclidean distance is a fundamental distance metric pertaining to systems in Euclidean space.
<blockquote>
Euclidean space is the classical geometrical space that you get familiar with in the Math class, typically bound to 3 dimensions. Though, it can also be prescribed to any non-negative integer dimension as well.
</blockquote>
<blockquote>
Euclidean distance is the shortest line between two points in Euclidean space.
</blockquote>
The metric is used in many contexts within data mining, machine learning, and several other fields, and is one of the fundamental distance metrics.

Bilal Hamada

In this guide, we'll take a look at how to calculate the Euclidean Distance between two vectors (points) in Python with NumPy and the math module.

Calculating Euclidean Distance with NumPy

<h2 id="introduction">Introduction</h2>
<blockquote>
Sorting is one of the fundamental techniques used in solving problems, especially in those related to writing and implementing efficient algorithms.
</blockquote>
Usually, sorting is paired with searching - meaning we first sort elements in the given collection, then search for something within it, as it is generally easier to search for something in a sorted, rather than an unsorted collection, as we can make educated guesses and impose assumptions on the data.
<blockquote>
There are many algorithms that can efficiently sort elements, but in this guide we'll be taking a look at how to implement Radix Sort in Java.
</blockquote>
<h2 id="radixsortinjava">Radix Sort in Java</h2>
Radix Sort is a non-comparative sorting algorithm, meaning it doesn't sort a collection by comparing each of the elements within it, but instead relies on something called the radix to sort the collection.
<blockquote>
The radix (often called the base) is the number of unique digits in a positional numeral system, used to represent numbers.
</blockquote>
For the well-known binary system, the radix is 2 (it uses only two digits - 0 and 1). For the arguably even more well-known decimal system, the radix is 10 (it uses ten digits to represent all numbers - from 0 to 9).
<blockquote>
How does Radix Sort use this to its advantage?
</blockquote>
Radix Sort doesn't sort by itself, really. It uses any stable, non-comparative sorting algorithm as its subroutine - and in most cases, the subroutine is Counting Sort.
<img src="https://s3.stackabuse.com/media/articles/radix-sort-in-python-1.png" alt="stable sorting">
If <code>n</code> represents the number of elements we are to sort, and <code>k</code> is the range of allowed values for those elements, Counting Sort's time complexity is <code>O(n+k)</code> when <code>k</code> is in range from <code>1...n</code>, which is significantly faster than the typical comparative sorting algorithm with a time complexity of <code>O(nlogn)</code>.
<blockquote>
But the problem here is - if the range is <code>1...n²</code>, the time complexity drastically deteriorates to <code>O(n²)</code> very quickly.
</blockquote>
The general idea of Radix Sort is to sort digit by digit from the least significant ones to the most significant (LSD Radix Sort) and you can also go the other way around (MSD Radix Sort). It allows Counting Sort to do its best by partitioning the input and running Counting Sort multiple times on sets that don't let <code>k</code> approach <code>n²</code>.
Because it's not comparison based, it's not bounded by <code>O(nlogn)</code> - it can even perform in linear time.
Since the heavy lifting is done by Counting Sort, let's first go ahead and take a look at how it works and implement it, before diving into Radix Sort itself!
<h3 id="countingsortinjavatheoryandimplementation">Counting Sort in Java - Theory and Implementation</h3>
<blockquote>
Counting Sort is a non-comparative, stable sorting algorithm, and it's main use is for sorting arrays of integers.
</blockquote>
The way it works is, it counts the number of objects having distinct key values, and then applies a prefix sum on those same counts to determine the position of each key value in the output. Being stable, the order of records with equal keys is preserved when the collection is sorted.
This operation results in, essentially, a list of integer occurrences, which we typically name the count array. Counting Sort uses the auxiliary count array to determine the positions of elements:
<img src="https://s3.stackabuse.com/media/articles/radix-sort-in-python-2.png" alt="">
Each index in the output array represents an element in the input array. The value associated with this index is the number of occurrences (the count) of the element in the input array.
The best way to show how Counting Sort works is through an example. Consider we have the following array:
<pre><code class="hljs">int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};
</code></pre>
For the sake of simplicity, we'll be using digits from 0 through 9. The maximum value of a digit we can take into consideration is obviously 9, so we'll set a <code>max = 9</code>.
This is important because we need an additional, auxiliary array consisting of <code>max + 1</code> elements. This array will be used to count the number of appearances of every digit within our array <code>arr</code>, so we need to initialize the whole counting array <code>countingArray</code> to <code>0</code>.
<pre><code class="hljs">int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
// there are 10 digits, so one zero for every element
</code></pre>
Now that we've both defined the array we'll be working with and initialized the counting array, we need to do the following steps to implement Counting Sort:
1. Traversing through our <code>arr</code> array, and counting the occurrence of every single element while incrementing the element on the position <code>arr[i]</code> in our <code>countingArray</code> array:
<pre><code class="hljs">for(int i = 0; i &lt; arr.length; i++)
 countingArray[arr[i]]++;
</code></pre>
After this step, <code>countingArray</code> has the following elements: <code>[1, 2, 0, 1, 0, 2, 0, 1, 1, 0]</code>.
2. The next step is applying prefix sums on the <code>countingArray</code>, and we get the following:
<pre><code class="hljs">for(int i=1; i &lt; countingArray.length; i++)
 countingArray[i] += countingArray[i-1];
</code></pre>
After the modification of the counting array it now consists of <code>countingArray = {1, 3, 3, 4, 4, 6, 6, 7, 8, 8}</code>.
3. The third and last step is to calculate element positions in the sorted output based on the values in <code>countingArray</code>. For that we'll need a new array that we'll call <code>outputArray</code>, and we'll initialize it to <code>m</code> zeros, where <code>m</code> is the number of elements in our original array <code>arr</code>:
<pre><code class="hljs">int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
// there are 8 elements in the arr array
</code></pre>
<blockquote>
Since Counting Sort is a stable sorting algorithm, we'll be iterating through the <code>arr</code> array in reverse order, lest we end up switching the elements.
</blockquote>
We'll find the index in our <code>countingArray</code> that is equal to the value of the current element <code>arr[i]</code>. Then, at the position <code>countingArray[arr[i]] - 1</code> we'll place the element <code>arr[i]</code>.
This guarantees the stability of this sort, as well as placing every element in it's right position in the sorted order. Afterwards, we'll decrement the value of <code>countingArray[i]</code> by 1.
At the end, we'll be copying the <code>outputArray</code> to <code>arr</code> so that the sorted elements are contained within <code>arr</code> now.
Let's unify all of these snippets and completely implement Counting Sort:
<pre><code class="hljs">int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};
int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

for(int i = 0; i &lt; arr.length; i++)
 countingArray[arr[i]]++;

for(int i=1; i &lt; countingArray.length; i++)
 countingArray[i] += countingArray[i-1];

int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
for(int i = arr.length-1; i &gt;= 0; i--){
 outputArray[countingArray[arr[i]] - 1] = arr[i];
 countingArray[arr[i]]--;
}

for(int i = 0; i &lt; arr.length; i++){
 arr[i] = outputArray[i];
 System.out.print(arr[i] + &quot; &quot;);
}
</code></pre>
Running this will give us a sorted array:
<pre><code class="hljs">0, 1, 1, 3, 5, 5, 7, 8
</code></pre>
As mentioned earlier, the time complexity of this algorithm is <code>O(n+k)</code> where <code>n</code> is the number of elements in <code>arr</code>, and <code>k</code> is the value of the <code>max</code> element in the array. However, as <code>k</code> approaches <code>n²</code> this algorithm deteriorates towards <code>O(n²)</code>, which is a major downside of the algorithm.
Since we've briefly explained how Counting Sort works, let's move on to the main topic of this article - Radix Sort.
<h3 id="radixsortinjavatheoryandimplementation">Radix Sort in Java - Theory and Implementation</h3>
Again, Radix Sort typically uses Counting Sort as a subroutine, so Radix Sort itself is a stable sorting algorithm as well.
The keys used by the Counting Sort will be the digits of the integers within the array we're sorting.
<blockquote>
There are two variants of Radix Sort - one that sorts from the Least Significant Digit (LSD), and the second one that sorts from the Most Significant Digit (MSD) - we'll be focusing on the LSD approach.
</blockquote>
Radix Sort by itself isn't very complicated to understand once we understand how Counting Sort works, so the steps taken to implement it are fairly simple:
<ol>
<li>Find the <code>max</code> element in the input array.</li>
<li>Determine the number of digits, <code>d</code>, the <code>max</code> element has. The number <code>d</code> represents how many times we'll go through the array using Counting Sort to sort it.</li>
<li>Initialize the number <code>s</code> to 1 at the beginning, representing the least significant place and working its value up by multiplying it by 10 every time.</li>
</ol>
<blockquote>
For example, let's say we have the following input array <code>arr = {73, 481, 57, 23, 332, 800, 754, 125}</code>. The number of times we'll loop through the array is 3, since the <code>max</code> element in our <code>arr</code> array is 800, which has 3 digits.
</blockquote>
Let's go through a visual example of an array being sorted this way, step by step, to see how Radix Sort sorts the elements in each iteration:
<img src="https://s3.stackabuse.com/media/articles/radix-sort-in-python-3.png" alt="">
The input array is broken down into the digits that make up its original elements. Then - either using by the most significant digit and working our way down, or the least significant digit and working our way up, the sequence is sorted via Counting Sort:
<img src="https://s3.stackabuse.com/media/articles/radix-sort-in-python-4.png" alt="">
In the first pass, only the right-hand side is used to sort, and this is why stability in Radix Sort/Counting Sort is key. If there was no stability, there would be no point in sorting this way. In the second pass, we use the middle row, and finally - the left-hand row is used, and the array is fully sorted.
Finally, let's implement Radix Sort:
<pre><code class="hljs">static void radixSort(int[] arr) {
 int max = arr[0];
 for (int i = 1; i &lt; arr.length; i++) {
 if (max &lt; arr[i])
 max = arr[i];
 }

 for (int s = 1; max / s &gt; 0; s *= 10)
 countingSortForRadix(arr, s);
}
</code></pre>
We'll also want to slightly modify Counting Sort.
This modification of Counting Sort does the exact same thing as the previous implementation, only it focuses on digits in different places of the integers at a time:
<pre><code class="hljs">static void countingSortForRadix(int[] arr, int s) {
 int[] countingArray = {0,0,0,0,0,0,0,0,0,0};
 for (int i = 0; i &lt; arr.length; i++)
 countingArray[(arr[i] / s) % 10]++;

 for (int i = 1; i &lt; 10; i++)
 countingArray[i] += countingArray[i - 1];

 int[] outputArray = {0,0,0,0,0,0,0,0};
 for (int i = arr.length - 1; i &gt;= 0; i--)
 outputArray[--countingArray[(arr[i] / s) % 10]] = arr[i];

 for (int i = 0; i &lt; arr.length; i++)
 arr[i] = outputArray[i];
}
</code></pre>
Let's create an array and try sorting it now:
<pre><code class="hljs">public static void main(String[] args) {
 int[] arr = {73,481,57,23,332,800,754,125};

 radixSort(arr);
 for (int i = 0; i &lt; arr.length; i++)
 System.out.print(arr[i] + &quot; &quot;);
}
</code></pre>
This results in:
<pre><code class="hljs">23, 57, 73, 125, 332, 481, 754, 800
</code></pre>
Since we are using Counting Sort as the main subroutine, for an array containing <code>n</code> elements, that has the <code>max</code> element with <code>d</code> digits, in a system with a <code>b</code> base, we have the time complexity of <code>O(d(n+b))</code>.
That's because we're repeating the Counting Sort process <code>d</code> times, which has <code>O(n+b)</code> complexity.
<h2 id="conclusion">Conclusion</h2>
Although Radix Sort can run very efficiently and wonderfully, it requires some specific cases to do so. Because it requires that you represent the items to be sorted as integers, it's easy to see why some other comparison-based sorting algorithms can prove to be a better choice in many cases.
The additional memory requirements of Radix Sort compared to some other comparison based algorithms is also one of the reasons that this sorting algorithm is used more rarely than not.
On the other hand, this algorithm performs superbly when the input array has shorter keys, or the range of elements is smaller.

Branko Ilic

In this guide, you'll learn the theory behind Radix Sort and Counting Sort through visual examples, as well as implement them both in Java!

Radix Sort in Java

<h2 id="introduction">Introduction</h2>
The Portable Document Format (PDF) is not a WYSIWYG (What You See is What You Get) format. It was developed to be platform-agnostic, independent of the underlying operating system and rendering engines.
To achieve this, PDF was constructed to be interacted with via something more like a programming language, and relies on a series of instructions and operations to achieve a result. In fact, PDF is based on a scripting language - <a rel="nofollow nopener noreferrer" target="_blank" href="https://www.adobe.com/products/postscript.html">PostScript</a>, which was the first device-independent Page Description Language.
In this guide, we'll be using <a rel="nofollow noopener noreferrer" target="_blank" href="https://borbpdf.com/">borb</a> - a Python library dedicated to reading, manipulating and generating PDF documents. It offers both a low-level model (allowing you access to the exact coordinates and layout if you choose to use those) and a high-level model (where you can delegate the precise calculations of margins, positions, etc to a layout manager).
<blockquote>
In this guide, we'll take a look at how to split and merge PDF documents in Python using borb, we'll also look at how to rotate pages in a PDF document.
</blockquote>
Splitting and merging PDF documents are the basis for many use-cases:
<ul>
<li>Processing an invoice (you don't need the terms and conditions so you can remove those pages)</li>
<li>Adding a cover letter to documents (a test report, an invoice, promotional material)</li>
<li>Aggregating test-results from heterogeneous sources</li>
<li>Etc.</li>
</ul>
<h2 id="installingborb">Installing borb</h2>
borb can be downloaded from source on <a rel="nofollow noopener noreferrer" target="_blank" href="https://github.com/jorisschellekens/borb">GitHub</a>, or installed via <code>pip</code>:
<pre><code class="hljs">$ pip install borb
</code></pre>
<h2 id="splittingapdfusingborb">Splitting a PDF using borb</h2>
To demonstrate this, you'll need a PDF with a few pages. 
We'll start by creating such a PDF using <code>borb</code>. This step is optional, you can of course simply use a PDF you have laying around instead:
<pre><code class="hljs">from borb.pdf.canvas.color.color import HexColor
from borb.pdf.canvas.layout.page_layout.multi_column_layout import SingleColumnLayout
from borb.pdf.canvas.layout.page_layout.page_layout import PageLayout
from borb.pdf.canvas.layout.text.paragraph import Paragraph
from borb.pdf.document import Document
from borb.pdf.page.page import Page
from borb.pdf.pdf import PDF
from decimal import Decimal

def create_document(heading_color: HexColor = HexColor(&quot;0b3954&quot;), 
 text_color: HexColor = HexColor(&quot;de6449&quot;),
 file_name: str = &quot;output.pdf&quot;):

 d: Document = Document()

 N: int = 10
 for i in range(0, N):
 
 # Create a new Page, and append it to the Document
 p: Page = Page()
 d.append_page(p)
 
 # Set the PageLayout of the new Page
 l: PageLayout = SingleColumnLayout(p)
 
 # Add the paragraph to identify the Page
 l.add(Paragraph(&quot;Page %d of %d&quot; % (i+1, N),
 font_color=heading_color,
 font_size=Decimal(24)))
 
 # Add a Paragraph of dummy text 
 l.add(Paragraph(&quot;&quot;&quot;
 Lorem Ipsum is simply dummy text of the printing and typesetting industry. 
 Lorem Ipsum has been the industry&#x27;s standard dummy text ever since the 1500s, 
 when an unknown printer took a galley of type and scrambled it to make a type specimen book. 
 It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. 
 It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, 
 and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum.
 &quot;&quot;&quot;,
 font_color=text_color))
 
 # Persist the Document to disk
 with open(file_name, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, d)
</code></pre>
This example code generates a PDF document consisting of 10 pages:
<ul>
<li>Each page starts with &quot;Page x of 10&quot;. This will make it easier to identify the pages later on.</li>
<li>Each page contains 1 paragraph of text.</li>
</ul>
<h2 id="splittingpdfdocumentsinpython">Splitting PDF Documents in Python</h2>
Now let's split this PDF. We'll start by splitting it in two, the first half containing the first 5 pages, and the second half containing the remaining pages:
<pre><code class="hljs">def split_half_half():

 # Read PDF
 with open(&quot;output.pdf&quot;, &quot;rb&quot;) as pdf_file_handle:
 input_pdf = PDF.loads(pdf_file_handle)

 # Create two empty PDFs to hold each half of the split
 output_pdf_001 = Document()
 output_pdf_002 = Document()

 # Split
 for i in range(0, 10):
 if i &lt; 5:
 output_pdf_001.append_page(input_pdf.get_page(i))
 else:
 output_pdf_002.append_page(input_pdf.get_page(i))

 # Write PDF
 with open(&quot;output_001.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, output_pdf_001)

 # Write PDF
 with open(&quot;output_002.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, output_pdf_002)
</code></pre>
We've extracted the first 5 pages into a new <code>Document</code>, and the following 5 pages into a second new <code>Document</code>, effectively splitting the original one into two smaller entities.
<blockquote>
This is made easy via the <code>get_page()</code> method, as its return type can be directly used to with <code>append_page()</code>.
</blockquote>
You can check the resulting PDFs to verify the code works as intended:
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-2.png" alt="splitting a pdf document in python">
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-3.png" alt="spllitting a pdf document in python">
<blockquote>
The first document ends at page 5, and the second one starts at page 6.
</blockquote>
We can also split it based on other criteria as well! In the next example we'll split the PDF by putting all odd pages in one PDF, and the even pages in another one:
<pre><code class="hljs">def split_even_odd():

 # Read PDF
 with open(&quot;output.pdf&quot;, &quot;rb&quot;) as pdf_file_handle:
 input_pdf = PDF.loads(pdf_file_handle)
 
 # Rreate two empty PDFs to hold each half of the split
 output_pdf_001 = Document()
 output_pdf_002 = Document()

 # Split
 for i in range(0, 10):
 if i % 2 == 0:
 output_pdf_001.append_page(input_pdf.get_page(i))
 else:
 output_pdf_002.append_page(input_pdf.get_page(i))

 # Write PDF
 with open(&quot;output_001.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, output_pdf_001)

 # Write PDF
 with open(&quot;output_002.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, output_pdf_002)
</code></pre>
You can verify the resulting PDF documents represent the aforementioned split:
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-4.png" alt="split pdf on odd pages">
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-5.png" alt="split pdf on odd pages">
<h2 id="mergingpdfdocumentsinpython">Merging PDF Documents in Python</h2>
In order to work the next examples we'll need two PDF's. Let's use the earlier code to generate them if you don't already have some:
<pre><code class="hljs">create_document(HexColor(&quot;247B7B&quot;), HexColor(&quot;78CDD7&quot;), &quot;output_001.pdf&quot;)
create_document(file_name=&quot;output_002.pdf&quot;)
</code></pre>
The intuition used for splitting is pretty similar to merging - though, we can add entire documents to other documents, not just pages. Though, sometimes you might want to split a document (cut off the last page) before merging it with another one.
We can merge them entirely (concatenating both PDFs), but we can also just add some pages of the first PDF to the second if we'd prefer it that way - using the <code>append_page()</code> function like before.
Let's start by concatenating them entirely:
<pre><code class="hljs">def concatenate_two_documents():

 # Read first PDF
 with open(&quot;output_001.pdf&quot;, &quot;rb&quot;) as pdf_file_handle:
 input_pdf_001 = PDF.loads(pdf_file_handle)
 
 # Read second PDF
 with open(&quot;output_002.pdf&quot;, &quot;rb&quot;) as pdf_file_handle:
 input_pdf_002 = PDF.loads(pdf_file_handle)
 
 # Build new PDF by concatenating two inputs
 output_document = Document()
 output_document.append_document(input_pdf_001)
 output_document.append_document(input_pdf_002)
 
 # Write PDF
 with open(&quot;output.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, output_document)
</code></pre>
This code should result in:
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-6.png" alt="merging pdf documents in python with borb">
<h2 id="rotatingpagesinpdfdocumentsinpython">Rotating Pages in PDF Documents in Python</h2>
A page in a PDF document can be rotated by any multiple of 90 degrees. This kind of operation allows you to easily switch between landscape and portrait mode.
In the next example you'll rotate a page from one of the input PDFs we created earlier:
<pre><code class="hljs">def rotate_first_page():
 # Read PDF
 with open(&quot;output_001.pdf&quot;, &quot;rb&quot;) as pdf_file_handle:
 input_pdf_001 = PDF.loads(pdf_file_handle)

 # Rotate page
 input_pdf_001.get_page(0).rotate_left() 
 
 # Write PDF to disk
 with open(&quot;output.pdf&quot;, &quot;wb&quot;) as pdf_out_handle:
 PDF.dumps(pdf_out_handle, input_pdf_001)
</code></pre>
The resulting PDF looks like this:
<img src="https://s3.stackabuse.com/media/articles/split-merge-and-rotate-pdf-documents-in-python-with-borb-7.png" alt="rotating pages of pdf documents in python">
<h2 id="conclusion">Conclusion</h2>
In this guide, we've taken a look at how to merge and split PDF documents. We've also modified an existing PDF by rotating some of its pages.

Joris Schellekens

In this guide, we'll use borb, a pure-Python PDF library to split, merge and rotate pages of PDF documents in Python, with practical examples!

Split, Merge and Rotate PDF Documents in Python with borb

In this in-depth practical tutorial, learn everything you need to know about the @Query annotation with Spring Data MongoDB and Spring Boot!

Spring Data MongoDB - Guide to the @Query Annotation

Lazar Ristic

In this beginner-oriented guide, we'll take a look at JavaScript's built-in array functions, how to work with arrays and some tips and tricks.

Working with JavaScript's Built-In Array Functions

In this guide, we'll take a look at JavaScript's built-in string functions, and how to utilize them, as well as some tips and tricks on good practices.

Working with JavaScript's Built-In String Functions

Hiram Kamau

In this detailed and extensive guide to the filter() method in Java 8 - you'll understand how the method works, as well as several use-cases and how to get the best performance out of large datasets.