Kalanand's September 2008 Log

   August 2008   
September 2008
SuMoTuWeThFrSa
 123456
78910111213
14151617181920
21222324252627
282930    
   October 2008   

September 1st

Sort using C++ STL built-in functions

The std::sort() function uses QuickSort (or some variation of it) while std::stable_sort() uses MergeSort because of the stability requirement.
Here is an example code using STL sort functionality.

Complexity: On average, linear in the distance between the first and last elements.
Performs approximately N*log2(N) (where N is this distance) comparisons of elements, and up to that many element swaps.
#include < iostream>     // std::cout
#include < algorithm>    // std::sort
#include < vector>       // std::vector

bool myfunction (int i,int j) { return (i myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Finding prime numbers

Here is a program to find all prime numbers below 100.
#include <iostream>
#include <vector>

const int max = 100;

int main() 
{
   std::vector allnums;
   std::vector primes;

   for (int i = 1; i <= max; ++i)
      allnums.push_back(i);   

   allnums[0]=0;

   for (int i = 2; i < allnums.size(); ++i) {   
      if (allnums[i-1] != 0) {
         primes.push_back(allnums[i-1]);
         for (int j = 2 * allnums[i-1]; j < max; j += allnums[i-1]) 
            allnums[j-1] = 0;  
      }
   }

   std::cout << "The prime numbers up to " << max << " are : " << std::endl;
   for (int i = 1; i < primes.size(); ++i) {
      std::cout << primes[i] << "\t";   
      if(i%5 == 0) std::cout << std::endl;
   }

   std::cout << std::endl;
   return 0;
}
Output:
~>./PrimeNumbers
The prime numbers up to 100 are : 
3	5	7	11	13	
17	19	23	29	31	
37	41	43	47	53	
59	61	67	71	73	
79	83	89	97	

Calculate mean, median, mode of an array

Here is a simple program to do this:
#include <iostream>
#include <algorithm>


// Calculate mean. Works for both sorted and unsorted arrays. 
float CalcMean(const int array[] , int size){
    if ( size <= 0 ) return 0;
    int sum = 0;
    for (int i = 0; i < size; i++) sum += array[i];
    return (float)sum / size;
}


// Calculate median. Works for sorted arrays. 
float CalcMedian(const int array[], int size){
    if( size <= 0 ) return 0;

    if( size % 2 ) return (float)array[size/2];
    else return (float)(array[size/2] + array[size/2+1]) / 2;
}



// Calculate mode. Works for sorted arrays. 
int CalcMode(const int array[], int size){
   if( size <= 0) return 0;

   int frequency = 1;  // frequency of the current element 
   int max_frequency = 0; // frequency of the mode 
   int mode = array[0]; // start with the first element 

   for (int i=0; i < size -1; i++) {

      if (array[i] == array[i+1]) { 
         frequency++; 

         if(frequency > max_frequency) { 
            max_frequency = frequency; 
            mode = array[i]; 
         }

      }
      else frequency = 1; // reset the counter
   }

   return mode;
}



int main() 
{
   const int size = 9;
   int numbers[size] =  { 3, 2, 4, 5, 1, 1, 2, 2, 3 };
   
   std::sort( std::begin(numbers), std::end(numbers) );

   float mean   = CalcMean( numbers, size);
   float median = CalcMedian( numbers, size);
   float mode   = CalcMode( numbers, size);

   std::cout << "Mean   : " << mean << std::endl;
   std::cout << "Median : " << median << std::endl;
   std::cout << "Mode   : " << mode << std::endl;
    
   return 0;
}
Output:
~>./MeanMedianMode
Mean   : 2.55556
Median : 2
Mode   : 2

September 3rd

Search algorithms: linear search

Linear search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found. It is the simplest search algorithm. Its worst case complexity is O(N). Therefore, if the list has more than a few elements, other methods such as binary search or hashing will be faster.

Example:Linear search in an array

void LinearSearch(int arr[], int value)
{
    int pos = -1; // index of the item we are searching for 

    for(int i=0; i< sizeof(arr) / sizeof(arr[0]); i++) {
        if(value == arr[i]) pos = i;
        break;
    }

    return pos;
}
Example 2: Implementation of linear search in C++ STL
std::vector<int> v;

// Finds the first element in the vector that has the value 42:
// If there is no such value, it == v.end()
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), 42);

Binary search

The binary search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value. The array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. The time complexity of a binary search is O(logN).

Example: There are many use cases of searching a sorted collection in daily life. A dictionary is a sorted list of word definitions. Given a word, one can find its definition. A telephone book is a sorted list of people's names, addresses, and telephone numbers. Knowing someone's name allows one to quickly find their telephone number and address.

Here is a simple example of binary search in an array:

int BinarySearch(int arr[], int value, int min, int max) 
{

  int pos = -1; // index of the item we are searching for 

  while (max >= min && pos == -1) {
    int mid = min + (max-min)/2;

    if(arr[mid] ==  value) pos = mid;
    else if(arr[mid] < value) min = mid++;
    else if(arr[mid] > value) max = mid--;
  }
  return pos;
}
Example 2: Implementation of binary search in C++ STL
   std::vector<int> v;

// Finds whether an element in the vector that has the value 42 or not:
   bool found = std::binary_search(v.begin(), v.end(), 42);

// Now, let's say we want to insert 11 and 14 into the sorted vector
  std::vector<int>::iterator where;
  where = std::lower_bound(v.begin(), v.end(), 11);
  v.insert(where, 11);

  where = std::upper_bound(v.begin(), v.end(), 14);
  v.insert(where, 14);

Search by hashing

In this technique, a function called the hash function, maps keys to array indices. Suppose we name our hash function hash. If a record has a key of k, then we will try to store that record at location data[hash(k)]. Using the hash function to compute the correct array index is called hashing the key to an array index. The hash function must be chosen so that its return value is always a valid index for the array.

Hashing has a worst-case behavior that is linear for finding a target, but with some care, hashing can be dramatically fast in the average-case. Hashing also makes it easy to add and delete elements from the collection that is being searched.

Open Addressing:
One way to resolve collisions is to place the colliding record in another location that is still open. This storage algorithm is called open-addressing. Open addressing requires that the array be initialized so that the program can test if an array position already contains a record.
With this method of resolving collisions, we still must decide how to choose the locations to search for an open position when a collision occurs... There are 2 main ways to do so.

1. Linear Probing: Uses the following algorithm:

  1. For a record with given key, compute the index hash(key).
  2. If data[hash(key)] does not already contain a record, then store the record in data[hash(key)] and end the storage algorithm.
  3. If the location data[hash(key)] already contains a record then try data[hash(key)+1]. If that location already contains a record, try data[hash(key)+2], and so forth until a vacant position is found. When the highest numbered array position is reached, simply go to the start of the array. For example, if the array indices are 0..99, and 98 is the key, then try 98,99,0,1 and so on, in that order. Searching for a vacant spot in this manner is called linear probing.
2. Double Hashing: There is a problem with linear probing. When several different keys hash to the same location, the result is a cluster of elements, one after another. As the table approaches its capacity, these clusters tend to merge into larger and larger clusters. This makes insertions take longer and searches require more time.
The most common technique to avoid clustering is called double hashing. Replace step 3. in the above algorithm with the following step:
  1. Let i = hash(key). If the location data[i] already contains a record then let i = (i+hash2(key)) % SIZE, and try the new data[i]. If that location already contains a record, then let i= (i+hash2(key)) % SIZE, and try that data[i], and so forth until a vacant position is found.
Note that with double hashing, we could return to our starting position before we have examined every available location. An easy way to avoid this problem is to make sure that the array size is relatively prime with respect to the value returned by hash2(). In addition, hash2(key) must return a value in the range [1..SIZE-1].
Two possible implementations are:
  1. hash2(key) = 1 + ( key % (SIZE-2) )
  2. hash2(key) = max(1, (key / SIZE) % SIZE)
Chained hashing: In this approach, each component of the hash table's array can hold more than one entry. We still hash the key of each entry, but upon collision, we simply place the new entry in its proper array component along with other entries that happened to hash to the same array index. The most common way to implement chaining is to have each array element be a linked list. The nodes in a particular linked list will each have a key that hashes to the same value.

Comparison of search algorithms

Example1: Here is a simple program to computate hash key for a string:

#include <iostream>
#include <functional>
#include <string>
 
int main()
{
   std::string str = "I am sitting in my office ...";
   std::hash hash_fn;
   std::size_t str_hash = hash_fn(str);
 
   std::cout << "Hash table key value is:" << str_hash << std::endl;
}
Output:
Hash table key value is:10134380172069548041

Example2: A program to compare hash keys:

#include <iostream>
#include <functional>
#include <string>

int main ()
{
  char char1[] = "Test";
  char char2[] = "Test";
  std::string str1 (char1);
  std::string str2 (char2);

  std::hash ptr_hash;
  std::hash str_hash;

  std::cout << "Same hashes:\n" << std::boolalpha;
  std::cout << "char1 and char2: " << (ptr_hash(char1)==ptr_hash(char2)) << '\n';
  std::cout << "str1 and str2: " << (str_hash(str1)==str_hash(str2)) << '\n';

  return 0;
}
Output:
Same hashes:
char1 and char2: false
str1  and str2:  true

Example3: The following program demonstrates creation of a hash function for a user defined type.

#include <iostream>
#include <functional>
#include <string>
 
struct S
{
    std::string first_name;
    std::string last_name;
};
 
template <class T>
class MyHash;
 
template<>
class MyHash<S>
{
public:
    std::size_t operator()(S const& s) const 
    {
        std::size_t h1 = std::hash<std::string>()(s.first_name);
        std::size_t h2 = std::hash<std::string>()(s.last_name);
        return h1 ^ (h2 << 1);
    }
};
 
int main()
{
    std::string s1 = "Kalanand";
    std::string s2 = "Mishra";
    std::hash<std::string> h1;
 
    S n1;
    n1.first_name = s1;
    n1.last_name =  s2;
 
    std::cout << "s1 = " << s1.c_str() << std::endl;
    std::cout << "s2 = " << s2.c_str() << std::endl;
    std::cout << "n1 = " << s1.c_str()  << " " 
              << s2.c_str() << std::endl << std::endl;

    std::cout << "hash(s1) = " << h1(s1) << "\n"
              << "hash(s2) = " << std::hash<std::string>()(s2) << "\n"
              << "hash(n1) = " << MyHash<S>()(n1) << "\n";
 
}
Output:
s1 = Kalanand
s2 = Mishra
n1 = Kalanand Mishra

hash(s1) = 9491039084864179940
hash(s2) = 5501961356046300852
hash(n1) = 1946461744545948556

September 4th

Card shuffling and dealing program

cards.C
#include<iostream>
#include<ctime>

void shuffle( int deck[][13] ) 
{
   int row, column;

   for (int card = 1; card <= 52; card++) {
      do {
         row = rand() % 4;
         column = rand() % 13;
      }
      while ( deck[row][column] !=0);

      deck[row][column] = card;
   }
}


void deal( int deck[][13], const char* face[], const char* suit[] )
{
   for (int card = 1; card <= 52; card++) 
      for (int row = 0; row < 4; row++) 
         for (int column = 0; column < 13; column++) 
            if(deck[row][column] == card) 
               std::cout << face[column] << " of " << suit[row] 
                         << (card %2 == 0 ? '\n' : '\t');
}


int main() 
{
   const char* suit[4] = {"Hearts", "Diamonds", "Clubs", "Spades"};
   const char* face[13] = {"Ace", "Deuce", "Three", "Four", "Five", 
                           "Six", "Seven", "Eight", "Nine", "Ten", 
                           "Jack", "Queen", "King"};
   int deck[4][13] = {0};

   srand( time(0) );
   shuffle(deck);
   deal(deck, face, suit); 

   return 0;
}
Output:
Jack of Clubs       Seven of Spades
Queen of Diamonds   King of Clubs
Six of Hearts       Five of Diamonds
Ten of Clubs        Ace of Clubs
Deuce of Spades     Ten of Spades
Four of Spades      Five of Hearts
Queen of Clubs      Three of Spades
Ten of Diamonds     Seven of Hearts
Five of Clubs       Deuce of Clubs
Nine of Hearts      Deuce of Diamonds
Queen of Spades     Seven of Diamonds
Eight of Clubs      Ace of Diamonds
Four of Hearts      Eight of Diamonds
Five of Spades      Six of Clubs
Jack of Diamonds    Ace of Spades
Six of Spades       Three of Diamonds
Deuce of Hearts     Jack of Spades
Three of Clubs      Queen of Hearts
Six of Diamonds     Four of Diamonds
Ace of Hearts       King of Diamonds
Nine of Diamonds    Seven of Clubs
Nine of Clubs       Three of Hearts
Ten of Hearts       Eight of Hearts
Eight of Spades     Nine of Spades
Four of Clubs       King of Spades
Jack of Hearts      King of Hearts

String manipulation in C++: examples

StringManipulation.C
#include <iostream>
#include <algorithm>

int main() 
{
   char first_name[] = "Kalanand ", last_name[] = "Mishra";
   char* name = strcat(first_name, last_name);
   char name_copy[20]; 


   /* Copy, concatenate, and find length */
   strcpy(name_copy, name);
   std::cout << "name = " << name << ",  length = " << strlen(name) << "\n";
   std::cout << "Copy of the name = " << name_copy << "\n";

   std::cout << "strcmp(name, last_name) = " 
             << strcmp(name, last_name) << "\n";

   std::cout << "strncmp(name, first_name, 8) = " 
             << strncmp(name, first_name, 8) << "\n";



   /* Break the string into pieces */
   char* token = strtok(name, " ");
   std::cout << "tokens: ";

   while( token != NULL ) { 
      std::cout << token << " ";
      token = strtok( NULL, " ");
   }

   std::cout << std::endl;


   /* Convert the name to upper case */
   char s[20] = "kalanand Mishra";
   std::transform( std::begin(s), std::end(s), std::begin(s), toupper);
   std::cout << "All in upper case: " << s << std::endl;

   /* Convert the name to lower case */
   std::transform( std::begin(s), std::end(s), std::begin(s), tolower);
   std::cout << "All in lower case: " << s << std::endl;


   return 0;
}
output:
name = Kalanand Mishra,  length = 15
Copy of the name = Kalanand Mishra
strcmp(name, last_name) = -2
strncmp(name, first_name, 8) = 0
tokens: Kalanand Mishra 
All in upper case: KALANAND MISHRA
All in lower case: kalanand mishra

Function pointers

A pointer to a function contains the address of the function in memory. In fact, the function name is the starting address of the code that performs the function's task. Pointers to functions can be passed to functions, returned from functions, stored in arrays, and assigned to other function pointers. The following example illustrates the use of function pointers.

FunctionPointers.C
#include <iostream>

void function1( int a) 
{
   std::cout << "You entered " << a << " so function1 was called\n\n";
}


void function2( int b) 
{
   std::cout << "You entered " << b << " so function2 was called\n\n";
}


void function3( int c) 
{
   std::cout << "You entered " << c << " so function3 was called\n\n";
}


int main() 
{
void (*f[3]) (int) = {function1, function2, function3};
int choice;

std::cout << "Enter an integer to run this program: ";
std::cin >> choice;

(*f[choice %3])(choice); 

return 0;
}

Rotating a matrix

Rotate by +90 degrees:
Rotate by -90 degrees:
Rotate by ±180 degrees:
Complixity: O(n2) time and O(1) space algorithm

Here is an example code to demonstrate the rotation of a 4x4 matrix.

#include <iostream>

/*
int** getRotate90PlusMatrix(int array[][4], int size) 
{
   int** rotated = new int*[size];

   for (int i = 0; i < size; i++)
      for (int j = 0; j < size; j++)
         rotated[i][j]  =  array[j][size-1-i];

   return rotated;
}
*/



void Rotate90Plus(int array[][4], int size) 
{
   int n = size, temp;

   for (int i = 0; i < n/2; i++) {
      for (int j = 1; j < n-i; j++) { 

         temp                 =  array[i][j];
         array[i][j]          =  array[j][n-1-i];
         array[j][n-1-i]      =  array[n-1-i][n-1-j];
         array[n-1-i][n-1-j]  =  array[n-1-j][i];
         array[n-1-j][i]      =  temp;
      }
   }

}



void Rotate90Minus(int array[][4], int size) 
{
   int n = size, temp;

   for (int i = 0; i < n/2; i++) {
      for (int j = 1; j < n-i; j++) { 

         temp                 =  array[i][j];
         array[i][j]          =  array[n-1-j][i];
         array[n-1-j][i]      =  array[n-1-i][n-1-j];
         array[n-1-i][n-1-j]  =  array[j][n-1-i];
         array[j][n-1-i]      =  temp;
      }
   }

}



void Rotate180(int array[][4], int size) 
{
   int n = size;

   for (int i = 0; i < n/2; i++) 
      for (int j = 0; j < n; j++) 
         std::swap( array[i][j], array[n-1-i][n-1-j] );
}






void PrintMatrix(int array[][4], int size) 
{
   for (int i=0; i < size; i++) {

      if(i%4) std::cout << "\n";
      for (int j=0; j < size; j++)
         std::cout << array[i][j] << "  ";
   }

   std::cout << "\n";
}



int main()
{
   int a[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 1, 2}, {3, 4, 5, 6} };

   std::cout << "Original matrix: " << std::endl;
   PrintMatrix(a, 4);


   Rotate90Plus(a, 4);
   std::cout << "\nRotated original matrix +90 degree: " << std::endl;
   PrintMatrix(a, 4);



   Rotate90Minus(a, 4);
   std::cout << "\nRotated previous matrix -90 degree: " << std::endl;
   PrintMatrix(a, 4);



   Rotate180(a, 4);
   std::cout << "\nRotated original matrix 180 degree: " << std::endl;
   PrintMatrix(a, 4);

   return 0;
}
Output:
Original matrix: 
1  2  3  4  
5  6  7  8  
9  0  1  2  
3  4  5  6  

Rotated original matrix +90 degree: 
4  8  2  6  
3  1  0  5  
2  7  6  4  
1  5  9  3  

Rotated previous matrix -90 degree: 
1  2  3  4  
5  6  7  8  
9  0  1  2  
3  4  5  6  

Rotated original matrix 180 degree: 
6  5  4  3  
2  1  0  9  
8  7  6  5  
4  3  2  1  

September 5th

Some observations about C++ classes

Operator overloading

Inheritance, polymorphism

September 9th

Checking dependencies

Anytime someone gives you a tag list to check out in a CMSSW release you should check to see if there are any packages which need recompilation due to changes in the packages for which you've checked out newer tags. There is a command:
checkdeps
that will print the list of things which in principle should be checked out and recompiled and if you type:
checkdeps -a
it will even check them out for you. Then you compile the whole lot and it should be technically consistent.

September 12th

Checking memory leak using valgrind

I usually run valgrind with options like:
valgrind --tool=memcheck `cmsvgsupp` --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes cmsRun your_cfg.py >& test01.out &
You'll have to find a machine with a few GB of memory, though, depending on how big your job is normally.

September 16th

Custom build

You might find it useful to rebuild your code without optimization and with debug symbols beforehand as then it will also tell you line numbers in the tracebacks for any errors it finds:
scram b clean
scram b -v -k USER_CXXFLAGS="-O0\ -g" >& build01.log &
(i.e. rebuild like this and then run valgrind as above).

Go to August's log


Last modified: Tue Sep 30 19:18:07 CST 2008