Need advice on improving my code: Search Algorithm

Question

I'm pretty new at C++ and would need some advice on this. Here I have a code that I wrote to measure the number of times an arbitrary integer x occurs in an array and to output the comparisons made.

However I've read that by using multi-way branching("Divide and conqurer!") techniques, I could make the algorithm run faster.

Could anyone point me in the right direction how should I go about doing it?

Here is my working code for the other method I did:

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

vector <int> integers;
int function(int vectorsize, int count);
int x;
double input;

int main()
{
cout<<"Enter 20 integers"<<endl;
cout<<"Type 0.5 to end"<<endl;

while(true)
{
cin>>input;

if (input == 0.5)
break;

integers.push_back(input);
}

cout<<"Enter the integer x"<<endl;
cin>>x;

function((integers.size()-1),0);

system("pause");

}

int function(int vectorsize, int count)
{
    if(vectorsize<0) //termination condition
{
    cout<<"The number of times"<< x <<"appears is "<<count<<endl;
    return 0;
}    

if (integers[vectorsize] > x)
{
    cout<< integers[vectorsize] << " > " << x <<endl;
}

if (integers[vectorsize] < x)
{
    cout<< integers[vectorsize] << " < " << x <<endl;
}
if (integers[vectorsize] == x)
{
    cout<< integers[vectorsize] << " = " << x <<endl;

    count = count+1;
}

return (function(vectorsize-1,count));
}

Thanks!

Answer 1

If the array is unsorted, just use a single loop to compare each element to x. Unless there's something you're forgetting to tell us, I don't see any need for anything more complicated.

If the array is sorted, there are algorithms (e.g. binary search) that would have better asymptotic complexity. However, for a 20-element array a simple linear search should still be the preferred strategy.

Answer 2

If your array is a sorted one you can use a divide to conquer strategy:

Efficient way to count occurrences of a key in a sorted array

Answer 3

A divide and conquer algorithm is only beneficial if you can either eliminate some work with it, or if you can parallelize the divided work parts accross several computation units. In your case, the first option is possible with an already sorted dataset, other answers may have addressed the problem.

For the second solution, the algorithm name is map reduce, which split the dataset in several subsets, distribute the subsets to as many threads or processes, and gather the results to "compile" them (the term is actually "reduce") in a meaningful result. In your setting, it means that each thread will scan its own slice of the array to count the items, and return its result to the "reduce" thread, which will add them up to return the final result. This solution is only interesting for large datasets though.

There are questions dealing with mapreduce and c++ on SO, but I'll try to give you a sample implementation here:

#include <utility>
#include <thread>
#include <boost/barrier>

constexpr int MAP_COUNT = 4;

int mresults[MAP_COUNT];

boost::barrier endmap(MAP_COUNT + 1);

void mfunction(int start, int end, int rank ){
    int count = 0;
    for (int i= start; i < end; i++)
        if ( integers[i] == x) count++;
    mresult[rank] = count;
    endmap.wait();
}

int rfunction(){
    int count = 0;
    for (int i : mresults) {
        count += i;
    }
    return count;
}

int mapreduce(){
    vector<thread &> mthreads;
    int range = integers.size() / MAP_COUNT;
    for (int i = 0; i < MAP_COUNT; i++ )
        mthreads.push_back(thread(bind(mfunction, i * range, (i+1) * range, i)));
    endmap.wait();
    return rfunction();
}

Once the integers vector has been populated, you call the mapreduce function defined above, which should return the expected result. As you can see, the implementation is very specialized:

• the map and reduce functions are specific to your problem,
• the number of threads used for map is static,
• I followed your style and used global variables,
• for convenience, I used a boost::barrier for synchronization

However this should give you an idea of the algorithm, and how you could apply it to similar problems.

caveat: code untested.