DEV Community: AngelaMunyao

A brief introduction to Quadsort

AngelaMunyao — Wed, 03 May 2023 15:56:56 +0000

1. Description

Quadsort can be described as a faster merge sort. Unlike merge sort, which makes comparisons of 2 elements at a go while performing a sorting operation, Quadsort compares 4 elements at a go. It defeats the performance of Merge sort and Quicksort, which have long been considered the best sorting algorithms.

2. Implementation

Quadsort does require a successful implementation of the following methods:
i) Quad-swap -This is the main building block of Quadsort.
ii) Merging (This is where a sorted block of 4 elements is merged with another block of 4 elements or, generally, two sorted arrays are merged into one)
iii) Performing a check to see if the block of 4 elements is sorted already, either in-order, or in reverse order.

The whole array is segmented into chunks of 4 elements, and each chunk is sorted using the Quad-swap approach, then all chunks are merged together in sorted order.

Quad-swap compares and sorts 4 array elements at a go, as can be seen in the Pseudocode below:

With the simple Quadswap above, if an array is already fully sorted it writes a lot of data back and forth from swap unnecessarily. If an array is fully in reverse order, the algorithm will change numbers 10, 9, 8, 7, 6, 5, 4 to 7, 8, 9, 10, 6, 5, 4
This will reduce the degree of orderliness rather than increase it. This problem can be solved by implementing 'Quad-swap in-place', which involves checking and handling the reverse order. Reverse order may be handled using a simple reversal function, as can be seen below:

After sorting, the blocks need to be merged. If this is done by merging 4 blocks at once, this is known as Quad-merge or Ping-pong merge.

Our merging approach makes use of Timsort’s galloping merge algorithm to merge two arrays. We create an empty array, that is continuously merged with every new chunk of sorted 4 elements.
As seen while performing Quad-swap above, it is ideal checking whether the four blocks are in order. If they are in order, the merge operation is skipped. While performing the in-place Quadswap, we have already checked the reverse order. Thus, there is no need for rechecking it while performing the merge operation.

3. Other Merge Operations

3.1. Parity Merge
Parity merge works that, given 2 n length arrays, we can be able to perform n merge operations at the start of each array, and n merger operations at the end of each array. One needs to ensure that the two arrays are of equal length.

3.2. Hybrid Parity Merge
In the case the two arrays are not of equal length, we then need to perform a hybrid parity merge. A hybrid parity merge works by taking n parity merges, where n is the length of the smaller array. Once this is completed, it will then switch to the traditional merge.

Parity merge is very necessary for branchless optimisations, and this is because it helps in speeding up the sorting of random data. Another advantage of parity merge is that two separate memory regions can be accessed in the same loop, and this allows for memory-level parallelism. On most hardware, this increases the runtime speed by 2.5 times for random data.

3.3. Branchless Parity Merge
Branchless parity merge works well for random data. However, it slower sorting ordered data. This is where the Quad galloping merge comes in. Quad galloping merge makes use of the galloping idea introduced by Timsort.
The galloping merge algorithm may be implemented as follows:

When merging ABC and XYZ, for instance, it first checks if B is smaller or equal to X. If so, A and B are copied to swap. If not, it checks if A is greater than Y. If so, X and Y are copied to swap.
If either of the checks is false, it is known that the two remaining distributions are A X and X A. This will allow the execution of an optimal branchless merge.
Overally, the Quad galloping merge performs better for both ordered and unordered data.
Other merge operations you may also want to look at are the Tail-merger and the Rotate-merge.
Let’s take a look at a complete python implementation of the Quadsort algorithm. This will include calling the sorting and merging algorithms already implemented above, and may appear as follows:

4. Complexity analysis

4.1. Time Complexity

4.2. Space Complexity

5. Conclusion

Quadsort performs better than Merge sort, and Quick sort in most runtime tests, except for generic data. Unlike Quick sort, it is able to pick a reliable pivot, hence the better performance for small arrays. For arrays exceeding the L1 cache, Quicksort performs better due to its ability to partition.

How to create a web crawler with Beautiful Soup

AngelaMunyao — Sat, 29 Apr 2023 09:23:37 +0000

Web crawling is an essential technique used in data extraction, indexing, and web scraping. Web crawlers are automated programs that navigate through websites, extract data, and save it for further processing. Python is an excellent language for building web crawlers, and the Beautiful Soup library is one of the most popular tools for web scraping.

In this article, we will show you how to create a web crawler using Python and Beautiful Soup. We will extract text data from a website and save it to a CSV file.

First, we need to import the required libraries. We will use the requests library to send GET requests to the website and the Beautiful Soup library to parse the HTML.

import requests
import csv
from bs4 import BeautifulSoup

url = "https://www.businessdailyafrica.com/"

We will use the requests library to send a GET request to the website and store the response

response = requests.get(url)

Now, we can create a Beautiful Soup object from the response HTML.

soup = BeautifulSoup(response.text, "html.parser")

We will use the find_all method to extract all anchor tags from the HTML.

links = soup.find_all("a")

We need to filter out links that do not belong to the website. We will create an empty list to store the internal links.

internal_links = []

We will loop through all the links and append the internal links to the internal_links list.

for link in links:
    href = link.get("href")
    if href and href.startswith("/bd"):
        href1 = 'https://www.businessdailyafrica.com'+href
        internal_links.append(href1)

Next, we will visit each internal link and repeat the process. We will create a set to store the visited links and a list to store the text data.

visited_links = set()
p_array = []

We will open a CSV file to store the text data.

with open('bdailyps.csv', mode='w') as csv_file:
    fieldnames = ['words']
    writer = csv.DictWriter(csv_file, fieldnames=fieldnames)
    writer.writeheader()

We will loop through each internal link and send a GET request to the website. We will create a Beautiful Soup object from the response HTML and extract all the paragraphs.

    for link in internal_links:
        if (len(visited_links) >= 100000 & len(p_array)>=10000001):
            break
        if link not in visited_links:
            visited_links.add(link)
            response = requests.get(link)
            soup = BeautifulSoup(response.text, "html.parser")
            h2s = soup.find_all("h2")
            ps = soup.find_all("p")

We will extract all the links from the HTML and append the internal links to the internal_links list.

links = soup.find_all("a")
for sublink in links:
    href = sublink.get("href")
    if href and href.startswith("/bd"):
        href1 = 'https://www.businessdailyafrica.com'+href
        internal_links.append(href1)

We will loop through all the paragraphs and extract the text. We will split the text into words and save each word to the p_array list and the CSV file.

for p in ps:
    paragraph =  p.text.strip()
    for word in paragraph.split():
        p_array.append(word)
        writer.writerow({'words': word})

Finally, we will print the number of visited links.

print(f'{len(visited_links)} links visited.')

A summary of the code:

import requests
import csv
from bs4 import BeautifulSoup

# Set the URL of the website to crawl
url = "https://www.businessdailyafrica.com/"

# Send a GET request to the URL and store the response
response = requests.get(url)

# Create a BeautifulSoup object from the response HTML
soup = BeautifulSoup(response.text, "html.parser")

# Find all anchor tags in the HTML
links = soup.find_all("a")

# Filter out links that do not belong to the website
internal_links = []
p_array = []
for link in links:
    href = link.get("href")
    if href and href.startswith("/bd"):
        href1 = 'https://www.businessdailyafrica.com'+href
        internal_links.append(href1)

# Visit each internal link and repeat the process
visited_links = set()
with open('bdailyps.csv', mode='w') as csv_file:
    fieldnames = ['words']
    writer = csv.DictWriter(csv_file, fieldnames=fieldnames)
    writer.writeheader()

    for link in internal_links:
        if (len(visited_links) >= 100000 & len(p_array)>=10000001):
            break
        if link not in visited_links:
            visited_links.add(link)
            response = requests.get(link)
            soup = BeautifulSoup(response.text, "html.parser")
            h2s = soup.find_all("h2")
            ps = soup.find_all("p")
            links = soup.find_all("a")
            for sublink in links:
                href = sublink.get("href")
                if href and href.startswith("/bd"):
                    href1 = 'https://www.businessdailyafrica.com'+href
                    internal_links.append(href1)

            # Print each h1 tag and the element directly below it
            for p in ps:
                print(link, p)
                paragraph =  p.text.strip()
                for word in paragraph.split():
                    p_array.append(word)
                    writer.writerow({'words': word})

# Print the number of visited links
print(f'{len(visited_links)} links visited.')

That's it! We have created a web crawler using Beautiful Soup

Choosing the right Linux Distro for you.

AngelaMunyao — Sat, 05 Feb 2022 07:06:19 +0000

The word ‘Distro’ is short for distribution. Linux distributions come in many different names such as Debian, Arch Linux, Kali Linux, Ubuntu, etc. Sometimes as a potential Linux user, you may find it difficult to choose a Linux distribution. Several questions need to be asked:
• How do I use my computer?
• How well do I know tech stuff?
• Am I using this for business or personal use?
• What hardware is installed on my desktop?
With questions come many considerations that need to be put in place while choosing a Linux distro and they include:

1 Server versus Desktop.

Stability is a major concern when it comes to servers, hence you need to go for Linux distributions that are reliable and backed by a strong client support team. For servers, you also need to consider the distro's community support. Distros like Ubuntu have huge community support where you can always run for help in case things break down. Another consideration you would want to put in place for servers is ensuring that the distro has long release cycles. Some distros get updated more frequently than others. There’s a disadvantage in running new software all the time. Newly released software is not always the best and can cause things to break. You certainly do not want this for your server. You may want to consider distributions like Ubuntu, SolusOS, or OpenSUSE as they do not update as frequently, and they are not outdated either.
For a desktop environment, you need shorter update cycles to keep your apps updated with the latest version. Community support is a point of consideration too but is not as urgent as in for servers.

2 Beginner versus Advanced.

Whether you are a beginner, an intermediate, or an advanced user, there is always a Linux distribution waiting for you, and all you need is to make the best choice. For beginners, friendly distributions would be Ubuntu, Linux Mint, and Elementary OS. For intermediate users, Solus, OpenSUSE, Fedora, and Debian would be a perfect choice. Advanced users are well suited to choose between Arch Linux, Kali Linux, and Gentoo. As an advanced user, you may also build your distro from scratch using Linux!

3 Hardware resources.

When choosing a Linux distribution, it is important to consider the hardware specifications of your whole computer system.
For instance, some Linux distributions such as Fedora, and Redhat do not support anything that is not open-source, and hence if your computer does not have open-source driver support from the manufacturer, running Distros like Fedora and Redhat would conflict with your system.
Moreover, if using an old machine, or a new one but with limited resources you need to go for lightweight distros such as Puppy Linux, Linux Lite, or Lubuntu. These will support a RAM between 128MB and 512 MB. For a system RAM between 512MB and 1GB, consider Bodhi Linux, Manjaro, and Linux Mint. For a RAM between 2GB and 4GB, consider using Ubuntu, Fedora, Mageia, and Peppermint OS. If your computer RAM is greater than 4GB, then use CentOS, Debian, or OpenSUSE.

4 Software repositories.

Another consideration that needs to be made is ensuring that the distro you choose has the software that you need. If you intend to use your desktop for daily tasks, Ubuntu would be a great choice, as it has a large software repository and huge third-party support.

In conclusion, each Linux distribution is unique and serves the purpose it was designed for. With so many Linux distributions present, there is no perfect one, but there is a most suitable one, highly dependent on your expectations, your personal preferences, requirements, your hardware, and expertise.

Ensuring Cross-browser Website Compatibility

AngelaMunyao — Thu, 03 Feb 2022 06:22:40 +0000

Introduction.

When building websites, every developer desires their site to be visible to all target users.
Users make use of different browsers, such as Chrome, IE, Safari, Firefox, Opera, etc.
Developers must ensure site compatibility with all the browsers.
I will share some tips on how to enhance browser visibility:

1 Use less complicated coding.

The more complicated the code is, the higher the chances of something going wrong. Better to choose a simple layout over a complex one. For instance, for layout purposes, it is a better idea to go for “ul” and “li” instead of a 'Table', because this will serve fewer nested elements in the mark-up.

In the figure above, for similar content display, the first block of code, which is a “ul” has fewer nested loops than the second, which is a “Table”.

2 Make sure to validate the code.

While code validation may not be a guarantee that the code will work in all browsers, it does minimize issues along the way. A good HTML and CSS validation service is provided by https://validator.w3.org/. As a developer, you get to decide how often to validate your code, eg, after every block, or after a whole page block.

3 Set a Doctype.

A doctype or document type declaration (DTD) informs the web browser about the markup language in which the current page is written, and in this case, lets the browser know that the document is an HTML document and the version of HTML used in the document. This will usually eliminate browser-related errors.
In an HTML building block, the doctype should be included at the beginning of the block as in the figure below.

4 Keep CSS rewrite rules in mind.

With every browser having its own rewrite rules, making use of CSS rewrite rules ensures that CSS is normalized, and this sets a standard for how CSS used will perform on different
sites.

A tool that can be used for this is, ‘normalize.css’.

Normalize.css makes browsers render more consistently and in line with modern standards, and precisely targets only styles that need normalizing. Several companies like Twitter, TweetDeck, Soundcloud, Guardian, Medium, GOV.UK, Bootstrap, and HTML5 Boilerplate make use of normalize.css.

5 Use Conditional Comments.

Conditional comments are used when targeting older browsers such as Internet Explorer and they help ensure that your code is compatible with these browsers and functions as expected.

Conditional statements usually make use of HTML markup wrapped up in a conditional statement. If the statement evaluates to true, the enclosed HTML is revealed within the document. Since these conditional comments are placed within HTML comments, the enclosed HTML also remains hidden from all browsers that don’t support conditional comments.
Conditional comments make use of operators as below:

Operator Description
IE -Represents Internet Explorer; And if a number value is also specified, it represents a version vector.
lt -Less than operator
lte -Less than or equal to
gt -Greater than
gte -Greater than or equal to
! -The NOT operator
() -Subexpression operator
& -The AND operator
| -The OR operator
true -Evaluates to true
false -Evaluates to false

Conditional statements placed inside HTML appear as below:

6 Use Cross-Browser compatible libraries.

Such libraries include Bootstrap, Foundation, etcetera. When building websites, it is a better choice to make use of libraries that were built with compatibility in mind, instead of using separate elements, and this reduces the chance of errors.

7 Use Dedicated Stylesheets for Each Browser.

With dedicated Stylesheets, a list of commands that tell each browser to launch each stylesheet designed for it is also included.

8 Include as many browsers as possible in the testing process

While building websites, it is much necessary to test in as many browsers as possible. Testing should also be considered for older browsers such as Internet Explorer 6, Safari 3, and Opera 9.

Cross-browser testing tools will provide better results. A good example of these tools is Comparium, which not only allows cross-browser testing but also allows for testing across multiple Operating Systems. Comparium will also allow for results comparison and help in finding differences between browsers used in testing. It allows for both manual and live testing.

If using Comparium for testing, the following steps would be helpful.
• Visit https://comparium.app/.

• Get the URL of the site you need to test.
• Select the browser you intend to test. You may also go ahead and include the
Operating system you intend to test, and even choose the screen width.
• Click “Create Screenshots”.
• Comparium will use your selected metrics to display your site and make screenshots
of the site.
• Additional steps you may perform on your own will include deleting, refreshing, or finding differences from the comparium’s menu. To start all over, click on “New configuration” .

Conclusion.
Users make use of different browsers on their devices; hence, developers must implement everything possible to ensure users of different browsers can access their content fully. Site content visibility in different browsers should be considered right from the ground up. The tips declared above are a great way to ensure cross-browser visibility of websites and web applications.

Building a Machine Learning model using Multiple Linear regression

AngelaMunyao — Thu, 27 Jan 2022 09:52:06 +0000

I spend couple hours this early morning modelling this article for all Machine Learning enthusiasts, and especially those at the beginner-intermediate level.

One of the very necessary skills for ML engineers is to understand the concept of regression as related to volumes of data, both small data sets, and giant data sets.

This article covers a practical example on how to build an Machine Learning model using Multiple Linear Regression.

For this exercise, make sure to have Anaconda software installed, and from there, open Jupyter notebooks.
Download combine cycle power plant Data set From UCL Machine Learning Repository: https://archive.ics.uci.edu/ml/datasets/combined+cycle+power+plant

Import the libraries below that we will be using:

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import pylab as pl

Enable inline plotting with Matplotlib

%matplotlib inline

Import the data: Unzip the downloaded zipped folder and make sure your data file exists in the same environment as your Notebook files:

data_df=pd.read_excel("Folds5x2_pp.xlsx")

You can now view your data with the command below (By default, it displays the first 5 rows)

data_df.head()

To recap the variables defined above:
AT refers to temperature in the range 1.81°c - 37.11°c
Exhaust vacuum V, in the range 25.36-81.56 cm Hg
Ambient Pressure (AP) in the range 992.89-1033.30 milibar
Relative Humidity (RH) in the range 25.56% -100.16%
Net hourly electrical energy (PE) in the range 420.26-495.76MW

Your dependent variable is PE.

Let's define X and Y, X being the independent variables and Y being the dependent variable.

To capture the independent variables, we need to use the function 'x=data_df.drop(['PE'], axis=1).values'.
The drop function excludes the independent variable PE,and 'axis=1' helps drop the column, and '.values' captures the x values.

To capture the dependent variable EP, we use 'y=data_df['PE'].values'

x=data_df.drop(['PE'], axis=1).values
y=data_df['PE'].values

Confirm X and Y values.

print(x)

print(y)

Split the data set into training and test set:

We use the function from Scikit library, 'train_test_split'
Import the train_test_split function.

from sklearn.model_selection import train_test_split

Devide your data into x_train, x_test, y_train, y_test.

x_train,x_test,y_train,y_test=train_test_split(x,y)

Voila! Your data is split into training and test set.
Next is to train the model using the training set. We will make use of linear regression.

from sklearn.linear_model import LinearRegression
model=LinearRegression()
model.fit(x_train,y_train)

After training the model, predict the test set results.

y_pred=model.predict(x_test)

Let's print the prediction results

print(y_pred)

The above prediction of PE is generated for all the rows in relation to the corresponding set of independent variables represented by X.

We can also execute as below, PE prediction per a specific one row set of x values (AT, V, AP, RH).
The example below is values from the first row of x values.

model.predict([[14.96,41.76,1024.07,73.17]])

Lets check how accurate our model is.
We need to import the function 'r2_score'.

from sklearn.metrics import r2_score
r2_score(y_test,y_pred)

The accuracy of our model is 92. :)

Next: Lets visualize the predicted results in a scatter plot
We already imported matplotlib which we are going to use.

#Make sure to import the Figure function which we will use to increase the scale of your graph so it doesn't appear too small 
plt.figure(figsize=(15, 10))
plt.scatter(y_test,y_pred)
plt.xlabel('Actual')
plt.ylabel('Predicted')
plt.title('Actual PE Values vs. Predicted')
plt.show()

From our dataset, let's also create a comparison of the test values and the predicted values.

Use Pandas already imported as 'pd', to put the values into a data frame.

pred_comparison=pd.DataFrame({'Actual Value': y_test,'Predicted Value':y_pred, 'Diffrence':y_test-y_pred})
pred_comparison

Above is the 1st 5 and the last 5 rows from our data set.

To view the first 40 rows for more clarity, we use:

pred_comparison[0:40]

Awesomeee, that's our model right there! Research on more ways on how to improve the model. Bye!