QuickStart - glozanoa/adas GitHub Wiki

There are several examples (in test directory) that show you how to use algorithms and data structures in adas library.

test
|- algorithm
| `|- sort
|  | `|- serial       # Contains examples of serial sort algorithms
|  |  |- multithread  # Contains examples of multi-thread sort algorithms
|  |
|  |- search
|   `|- serial        # Contains examples of serial search algorithms
|    |- multithread   # Contains examples of multi-thread search algorithms
|   
|- benchmarks         # Contains example to compare efficiency between multi-thread and serial algorithms
|- ds                 # Contains examples of data structures

First of all, we are going to create build directory in the root of adas directory and run cmake .. inside it (check Compilation guide for more details). Nowwe are ready to compile and run some examples.

First, we have to compile insertion algorithm, as follow:

# Now I am in ADA_REPOSITORY_ROOT/build directory
make insertion

Then we will check what options this algorithm accepts.

./test/insertion -h
Options for serial insertion algorithm:
  -h [ --help ]         Show help.
  -i [ --input ] arg    Input file with unsorted numbers.
  -v [ --verbose ]      Increase algorithm's verbosity.

So we have to pass input option ,which is the path to a file that store unsorted numbers (this is only for testing purpose, because there are more efficient algorithms that sort numbers stored in a file). Then, I am going to create 8 unique random numbers between 0 and 10 and save them in unsorted.txtfile using adas' utilities (check utilities guide for more details).

# I continue in ADA_REPOSITORY_ROOT/build directory
python3 ../dgen/intgen.py -u 0 10 8 unsorted.txt

After that, I am going to execute insertion sort algorithm.

./test/insertion -i unsorted.txt
# You will have an output like this
Elapsed time (insertion sorting algorithm) : 1.323e-06
Sorted: 0 2 3 4 6 8 9 10 

But if you want to see the execution of the algorithm step by step then you have to pass -v option to increase algorithm's verbosity.

./test/insertion -i unsorted.txt -v
# You will have an output like this (step by step)
3 9 6 8 4 0 10 2 
3 6 9 8 4 0 10 2 
3 6 8 9 4 0 10 2 
3 4 6 8 9 0 10 2 
0 3 4 6 8 9 10 2 
0 3 4 6 8 9 10 2 
0 2 3 4 6 8 9 10 
Elapsed time (insertion sorting algorithm) : 4.3049e-05
Sorted: 0 2 3 4 6 8 9 10 

Execute a multi-thread algorithm is very similar to execute a serial algorithm. But in this case you will supplied the number of threads.

# Compiling multi-thread insertion algorithm
make mt_insertion

./test/mt_insertion -h
Options for multi-thread insertion algorithm:
  -h [ --help ]              Show help.
  -i [ --input ] arg         Input file with unsorted numbers.
  -v [ --verbose ]           Increase algorithm's verbosity.
  -n [ --nthreads ] arg (=1) Number of threads

# Executing multi-thread insertion algorithm using 3 thread 
./test/mt_insertion -i unsorted.txt -n 3 -v
Thread 0: 3 9 
Thread 1: 6 8 
Thread 2: 0 2 4 10 
merge: 3 6 8 9 0 0 0 0 
merge: 0 2 3 4 6 8 9 10 
Elapsed time (parallel insertion): : 0.000417701
Sorted vector: 0 2 3 4 6 8 9 10

In a similar way you can use all the other examples inside test/algorithm directory.

I am sure that you are thinking, Why even when I use a multi-thread algorithm, this is more slow than the serial algorithm?.

This happen because the parallel algorithm do more things (split, process and merge) than the serial algorithm. But what happens if we compare then solving a BIG problem (sorting 50K numbers).

To do that we have some benchmarks that compare the execution time of a serial algorithm with their multi-thread version.

So, let's create 50K random numbers and execute bm_bubble benchmark.

# I am still in ADA_REPOSITORY_ROOT/build directory
# Generating 50K numbers between 0 and 100K
python3 ../dgen/intgen.py 0 100000 50000 unsorted50K.txt

# Compiling bm_bubble benchmark
make bm_bubble

./test/bm_bubble -h
Options for bubble algorithm benchmark:
  -h [ --help ]              Show help.
  -i [ --input ] arg         Input file with unsorted numbers.
  -o [ --output ] arg        File to write sorted numbers.
  -v [ --verbose ]           Increase algorithm's verbosity.
  -n [ --nthreads ] arg (=1) Number of threads

I am going to use 8 threads in the multi-thread algorithm.

# This can take a while (for the serial algorithm)
./test/bm_bubble -i unsorted50K.txt -o sorted50K_bubble.txt -n 8 
Running serial bubble algorithm
Elapsed time (serial bubble algorithm) : 29.0934
Running multithread bubble algorithm with 8 threads
Elapsed time (multithread bubble algorithm) : 0.70904
Data was saved to sorted50K_bubble.txt

As you can see the multi-thread bubble algorithm is super more faster than the serial algorithm, so use multi-thread algorithms for BIG problems.

Well at this point you know how to compile and execute the algorithms in test, but until now they only manipulate simple data structures (integers). But adas's algorithms were developed thinking in manipulate abstract data structures.

Let me first explain you the general structure of the algorithms in adas library.

• Almost every serial algorithms have the following structure:

   template<class Iterator>
   void ALGORITHM_NAME(Iterator first, Iterator last, bool verbose)

• Almost every multi-thread algorithms have the following structure:

   template<class Iterator>
   void ALGORITHM_NAME(Iterator first, Iterator last, unsigned int nthreads, bool verbose)

These algorithms process the elements between the range [first, last>, and for element I refer to any object with the operation < defined. So you can use these algorithm in an array, vector or list of objects.

NOTE:

• In the case of vector and list STL containers you can user begin and end methods to pass as firstand last arguments.
• In the case of array you can pass pointers of array elements as first and last arguments.

As a examples of how to use adas' algorithms to sort customized data structure I am going show you how to search a contact from the phone-book and also how to sort it.

So to do that I am going to create the class Contact and represent the phone-book with the vector<Contact> structure (perhaps there is a more efficient way of implement a phone-book, but this example is only for show you how to process customized data with algorithms of adas library).

Files in test/phonebook:

• contact.hpp - Definition of Contact class
• phone_book.cpp - Source code to manipulate phone-book data structure
• ca-500.csv - Data to test our algorithm

COMMING SOON

Adas library has several data structures that can be useful. These data structures support templates so you can use any kind of data inside them. And of course they can be used together with adas' algorithms.

Matrix<T>, Node<T>, ... (ADD MORE DEVELOPED DS)

$ pip install pyadas

It will install a package called adas.

• adas.ds : Module of data structures

from adas.ds import SLList, SLNode
# Importing SLList (single linked list) and SLNode (single linked node) data structures
# NOTE: To get more information about the data structures use help function

• adas.algorithm : Module of algorithms