July 14th, 2010 in Uncategorized | No Comments »
Sometimes we need counters that wrap around at certain intervals ex:
1,2,3,1,2,3,1,2,3
One way of doing this would be to increment our ‘counter’ and then reset it when it reaches our number
int N = 3;
int counter = 0;
if (counter == N){
counter = 0;
}
counter++;
But there are also couple other ways this same could be achieved.
Modulus
Using modulus operator ‘%’ we can divide the counter and get our wrapped value, where N is the value we will wrap at.
counter = (counter+1) % N;
Binary AND
This is almost this same approach as modulus but we are ‘AND’ing the counter with a power of 2. ex 1, 2, 4, 8, 16 … 2^n . Only problem here is that we have to AND with a power of 2.
counter = (counter+1) & 0x1;
produces 0,1,0,1,0,1
Test program
/**
* Test program for testing Modulus, Binary AND increments
* @author greg
*
*/
public class ModulePowerCounter {
private static final int MAX_LOOP = 100000000;
private static final int N = 2;
private static final int POWER_OF_2 = 0x1;
public static void main(String[] args) {
long modTime = modulo();
long counterTime = counter();
long po2Time = powerOf2();
System.out.println(String.format("modTime = %s", modTime));
System.out.println(String.format("counterTime = %s", counterTime));
System.out.println(String.format("po2Time = %s", po2Time));
}
private static long powerOf2(){
long start = System.currentTimeMillis();
int counter = 0;
for (int i = 0; i < MAX_LOOP; i++) {
counter = (counter+1) & POWER_OF_2;
}
return System.currentTimeMillis() - start;
}
private static long modulo(){
long start = System.currentTimeMillis();
int counter = 0;
for (int i = 0; i < MAX_LOOP; i++) {
counter = (counter+1) % N;
}
return System.currentTimeMillis() - start;
}
private static long counter(){
long start = System.currentTimeMillis();
int counter = 0;
for (int i = 0; i < MAX_LOOP; i++) {
if(counter == N)counter = 0;
counter++;
}
return System.currentTimeMillis() - start;
}
}Performance
This is the fun part, so we have 3 different ways to achieve same thing but how do they perform.
Lets think about it, division is much more expensive than ‘addition and test’ which is more expensive than binary manipulation, our test program confirms our assumption.
modTime = 1258
counterTime = 449
po2Time = 108
As we see Power of 2 outperforms other methods by far, but its only for powers of 2, also our plain counter is almost 2.5 times faster than modulus as well. So why would we like to use modulus increments at all? Well in my opinion I think they provide a clean code and if used properly they are a great tool to know of.
July 14th, 2009 in Uncategorized | No Comments »
Using linear probing for collision resolution in hashtable
#define ERROR_TABLE_FULL -1
#define ERROR_RECORD_NOT_FOUND -1
#define ERROR_DUPLICATE_RECORD -1
class HashTable{
public:
HashTable(int table_size);
int insert(const string &record);
int retrieve(const string &record);
private:
int hash(const string &record);
int hash_size;
int record_count;
string* table;
};
/**
* Constructor accepting table_size
*/
HashTable::HashTable(int table_size){
hash_size = table_size;
table = new string[hash_size];
record_count = 0;
}
/**
* Hash function calculated using
* product p of all the characters of the key
* and then returns the index where index=s%hash_size
*/
int HashTable::hash(const string &record) {
int value = 1;
for (int position = 0; position < max_key_length; position++){
if(record[position] == 0){
break;
}
value *= record[position];
}
value %= hash_size;
if (value < 0){
value += hash_size;
}
return value;
}
/**
* Insert new record into out table, making sure that the table is not full
*/
int HashTable::insert(const string &record){
//Check if HashTable is full if it is then return overflow
if(record_count == hash_size){
return ERROR_TABLE_FULL;
}
int hash_key = hash(record);
while(1){
string tmp = table[hash_key];
//Check if table bucket is empty
if(tmp.empty()) {
break;
}//Position already taken, duplicate keys are not allowed 0 = equal
else if(tmp.compare(record) == 0) {
return ERROR_DUPLICATE_RECORD;
}
//Collision detected multiple records mapped to same location
//Try next bucket
else {
hash_key = (hash_key+1) % hash_size;
}
}
table[hash_key] = record;
record_count++;
return hash_key;
}
/**
* Retrieve record index
*/
int HashTable::retrieve(const string &record){
int hash_key = hash(record);
while(1){
string tmp = table[hash_key];
//Record empty for the key
if(tmp.empty()){
break;
}//if entry found return index
else if(tmp.compare(record) == 0) {
return hash_key;
}
else { //Resolving collision using linear probing
hash_key = (hash_key+1) % hash_size;
}
}
//No record Found
return ERROR_RECORD_NOT_FOUND;
}
July 9th, 2009 in Uncategorized | No Comments »
About QuickSort
Wikipedia QuickSort definition.
General idea revolves around partitioning a list where values less than pivot go into left list while greater than go into right list.
Pivot here is the first item of the passed in list. We apply this recursively to the sublists them merge left+pivot+right.
CPP Code
First of all not a cpp developer so if you can improve this them post a comment with suggestions.
template <class Record>
Node<Record> * List<Record>::quick_sort_recursive(Node<Record>* list)
{
//Base case : list is NULL
if(list == NULL){
return NULL;
}
//We choose first entry in the list as the pivot node
Node<Record> * pivotNode = new Node<Record>();
pivotNode->entry=list->entry;
Record pivot = pivotNode->entry;
Node<Record> *tmp=list->next;
Node<Record> *leftHead=NULL;
Node<Record> *rightHead=NULL;
Node<Record> *leftTail=NULL;
Node<Record> *rightTail=NULL;
//Partition the list into left/right sublists
while(tmp != NULL){
Node<Record> *entryNode=new Node<Record>();
entryNode->entry = tmp->entry;
entryNode->next = NULL;
if(tmp->entry < pivot){
if(leftTail == NULL){
leftTail = entryNode;
leftHead=entryNode;
}else{
leftTail->next=entryNode;
leftTail=leftTail->next;
}
}
else{
if(rightTail == NULL){
rightTail = entryNode;
rightHead=entryNode;
}else{
rightTail->next=entryNode;
rightTail=rightTail->next;
}
}
tmp = tmp->next;
}
//Recursively subdivide the left / right list
leftHead = quick_sort_recursive(leftHead);
rightHead = quick_sort_recursive(rightHead);
//Combine left+pivot+right
Node<Record> * mergedHead=NULL;
Node<Record> * mergedTail=NULL;
Node<Record> *tmpNode=leftHead;
while(tmpNode){
Node<Record> *new_node=new Node<Record>();
new_node->entry=tmpNode->entry;
if(mergedTail == NULL){
mergedTail = new_node;
mergedHead= new_node;
}else{
mergedTail->next= new_node;
mergedTail=mergedTail->next;
}
tmpNode=tmpNode->next;
}
//Pivot point
if(mergedTail == NULL){
mergedTail = pivotNode;
mergedHead = pivotNode;
}else{
mergedTail->next=pivotNode;
mergedTail=mergedTail->next;
}
//Right sublist
tmpNode=rightHead;
while(tmpNode){
Node<Record> *new_node=new Node<Record>();
new_node->entry=tmpNode->entry;
mergedTail->next=new_node;
mergedTail=mergedTail->next;
tmpNode=tmpNode->next;
}
return mergedHead;
}
template <class Node_entry>
struct Node {
// data members
Node_entry entry;
Node<Node_entry> *next;
// constructors
Node();
Node(Node_entry, Node<Node_entry> *link = NULL);
};
