CountMinSketch in C++

This C++ Program demonstrates the implementation of Count Min Sketch.

Here is source code of the C++ Program to demonstrate Count Min Sketch. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Count Min Sketch

```
 */
```
```
# include <iostream>
```
```
# include <cmath>
```
```
# include <map>
```
```
# include <cstdlib>
```
```
# include <ctime>
```
```
# include <limits>
```
```
# include <cstring>
```
```
# define LONG_PRIME 32993
```
```
# define MIN(a,b) (a < b ? a : b)
```
```
# define ui unsigned int
```
```
using namespace std;
```
```
 
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class CountMinSketch
```
```
{
```
```
    private:
```
```
        ui w,d;
```
```
        float eps;
```
```
        float gamma;
```
```
        ui aj, bj;
```
```
        ui total;
```
```
        int **C;
```
```
        int **hashes;
```

        void genajbj(int **hashes, int i);

```
    public:
```
```
        /*
```
```
         * Constructor
```
```
         */
```

        CountMinSketch(float ep, float gamm)

```
        {
```

            if (!(0.009 <= ep && ep < 1))

```
            {
```

                cout << "eps must be in this range: [0.01, 1)" << endl;

```
                exit(1);
```
```
            }
```

            else if (!(0 < gamm && gamm < 1))

```
            {
```

                cout << "gamma must be in this range: (0,1)" << endl;

```
                exit(1);
```
```
            }
```
```
            eps = ep;
```
```
            gamma = gamm;
```
```
            w = ceil(exp(1) / eps);
```
```
            d = ceil(log(1 / gamma));
```
```
            total = 0;
```
```
            C = new int *[d];
```
```
            ui i, j;
```
```
            for (i = 0; i < d; i++)
```
```
            {
```
```
                C[i] = new int[w];
```
```
                for (j = 0; j < w; j++)
```
```
                {
```
```
                    C[i][j] = 0;
```
```
                }
```
```
            }
```
```
            srand(time(NULL));
```
```
            hashes = new int* [d];
```
```
            for (i = 0; i < d; i++)
```
```
            {
```
```
                hashes[i] = new int[2];
```
```
                genajbj(hashes, i);
```
```
            }
```
```
        }
```
```
        /*
```
```
         * Destructor
```
```
         */
```
```
        ~CountMinSketch()
```
```
        {
```
```
            ui i;
```
```
            for (i = 0; i < d; i++)
```
```
            {
```
```
                delete[] C[i];
```
```
            }
```
```
            delete[] C;
```
```
            for (i = 0; i < d; i++)
```
```
            {
```
```
                delete[] hashes[i];
```
```
            }
```
```
            delete[] hashes;
```
```
        }
```
```
        /*
```
```
         * Update Int Value
```
```
         */
```
```
        void update(int item, int c)
```
```
        {
```
```
            total = total + c;
```
```
            ui hashval = NULL;
```
```
            for (ui j = 0; j < d; j++)
```
```
            {
```

                hashval = (hashes[j][0] * item + hashes[j][1]) % w;

                C[j][hashval] = C[j][hashval] + c;

```
            }
```
```
        }
```
```
 
```
```
        /*
```
```
         * Update Str Data
```
```
         */
```

        void update(const char *str, int c)

```
        {
```
```
            int hashval = hashstr(str);
```
```
            update(hashval, c);
```
```
        }
```
```
        /*
```
```
         * Estimate Min Value
```
```
         */
```
```
        ui estimate(int item)
```
```
        {
```

            int minval = numeric_limits<int>::max();

            unsigned int hashval = NULL;

            for (unsigned int j = 0; j < d; j++)

```
            {
```

                hashval = (hashes[j][0] * item + hashes[j][1]) % w;

                minval = MIN(minval, C[j][hashval]);

```
            }
```
```
            return minval;
```
```
        }
```
```
        /*
```
```
         * Estimate Min Str Value
```
```
         */
```
```
        ui estimate(const char *str)
```
```
        {
```
```
            int hashval = hashstr(str);
```
```
            return estimate(hashval);
```
```
        }
```
```
        /*
```
```
         * Total Count 
```
```
         */
```
```
        ui totalcount()
```
```
        {
```
```
            return total;
```
```
        }
```
```
 
```
```
        /*
```
```
         * Hashing String to Int
```
```
         */        
```
```
        ui hashstr(const char *str)
```
```
        {
```
```
            unsigned long hash = 5381;
```
```
            int c;
```
```
            while (c = *str++)
```
```
            {
```

                hash = ((hash << 5) + hash) + c;

```
            }
```
```
            return hash;
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
* Generate Random Hashes
```
```
*/
```

void CountMinSketch::genajbj(int** hashes, int i)

```
{
```

    hashes[i][0] = int(float(rand())*float(LONG_PRIME)/float(RAND_MAX) + 1);

    hashes[i][1] = int(float(rand())*float(LONG_PRIME)/float(RAND_MAX) + 1);

```
}
```
```
/*
```
```
* Main Contains menu
```
```
*/
```
```
int main()
```
```
{
```

    const char *ar_str[] = { "hello", "some", "one", "hello", "alice",

                             "one", "lady", "let", "us", "lady",

                             "alice", "in", "us", "wonderland", "lady",

                             "lady", "some", "hello", "none", "pie" };

```
    CountMinSketch c(0.01, 0.1);
```
```
    ui i, total = 0, count;
```
```
    map<const char *, int> mapitems;
```

    map<const char *, int>::const_iterator it;

```
    for (i = 0; i < 20; i++)
```
```
    {
```

        if ((it = mapitems.find(ar_str[i])) != mapitems.end())

```
        {
```
```
            mapitems[ar_str[i]] += i;
```
```
        }
```
```
        else
```
```
        {
```
```
            mapitems[ar_str[i]] = i;
```
```
        }
```
```
        c.update(ar_str[i], i);
```
```
        total = total + i;
```
```
 
```
```
    }
```
```
    // 1. test for items in ar_str
```

    for (it = mapitems.begin(); it != mapitems.end(); it++)

```
    {
```

        if (c.estimate(it->first) != mapitems[it->first])

```
        {
```

            cout << "Incorrect count for " << it->first << ":->error: ";

            count = abs(int(c.estimate(it->first)-mapitems[it->first]));

```
            cout << count << endl;
```
```
        }
```
```
        else
```
```
        {
```

            cout << "Correct count for '" << it->first;

            cout << "' :-->count: " << c.estimate(it->first) << endl;

```
        }
```
```
    }
```
```
    cout << "c.totalcount()==total ? ";
```

    cout << (c.totalcount() == total ? "True" : "False") << endl;

    cout << "Sketch Total: " << c.totalcount() << endl;

```
 
```
```
    // 2. test for items not in ar_str
```

    cout << "Testing for strings not in ar_str..." << endl;

    const char *arn_str[] = {"sanfoundry", "hello", "linux", "us"};

```
    for (i = 0 ; i < 4; i++)
```
```
    {
```
```
        if (!c.estimate(arn_str[i]))
```

            cout<<arn_str[i] << " not found in string array"<<endl;

```
        else
```

            cout<<arn_str[i] << " found in string array"<<endl;

```
    }
```
```
    return 0;
```
```
}
```

$ g++ countmin.cpp
$ a.out
Correct count for 'hello' :-->count: 20
Correct count for 'us' :-->count: 20
Correct count for 'some' :-->count: 17
Correct count for 'one' :-->count: 7
Correct count for 'alice' :-->count: 14
Correct count for 'lady' :-->count: 44
Correct count for 'let' :-->count: 7
Correct count for 'in' :-->count: 11
Correct count for 'wonderland' :-->count: 13
Correct count for 'none' :-->count: 18
Correct count for 'pie' :-->count: 19
c.totalcount()==total ? True
Sketch Total: 190
Testing for strings not in ar_str...
sanfoundry not found in string array
hello found in string array
linux not found in string array
us found in string array
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Bloom Filter

» Next - C++ Program to Implement Direct Addressing Tables

Related Posts:

Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Check Programming Books
Check Data Structure Books

Recommended Articles: