Нужен совет по улучшению моего кода: Алгоритм поиска

Question

Нужен совет по улучшению моего кода: Алгоритм поиска

Я довольно новичок в C ++, и мне нужно несколько советов по этому вопросу.
Здесь у меня есть код, который я написал, чтобы измерить, сколько раз произвольное целое число x встречается в массиве, и выводить сделанные сравнения.

Однако я читал, что с помощью методов многократного ветвления («Разделяй и властвуй!») Я мог заставить алгоритм работать быстрее.

Может ли кто-нибудь указать мне правильное направление, как я должен делать это?

Вот мой рабочий код для другого метода, который я сделал:

#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));
}

Спасибо!

2

c++divide search

Решение

Другие решения

Если ваш массив отсортирован, вы можете использовать разделение, чтобы победить стратегию:

Эффективный способ подсчета вхождений ключа в отсортированный массив

2

Алгоритм «разделяй и властвуй» полезен только в том случае, если вы можете либо исключить некоторую работу с ним, либо если вы можете распараллелить разделенные рабочие части на несколько вычислительных блоков. В вашем случае первый вариант возможен с уже отсортированным набором данных, другие ответы могли решить проблему.

Для второго решения имя алгоритма — map lower, который разбивает набор данных на несколько подмножеств, распределяет подмножества на как можно большее количество потоков или процессов и собирает результаты, чтобы «скомпилировать» их (на самом деле это термин «Reduce») в значимый результат. В ваших настройках это означает, что каждый поток будет сканировать свой собственный фрагмент массива для подсчета элементов и вернет свой результат в поток «Reduce», который сложит их, чтобы вернуть конечный результат. Это решение интересно только для больших наборов данных.

Есть вопросы, касающиеся mapreduce и c ++ для SO, но я постараюсь дать вам пример реализации здесь:

#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();
}

Однажды integers вектор был заполнен, вы называете mapreduce определенная выше функция, которая должна вернуть ожидаемый результат. Как видите, реализация очень специализированная:

функции карты и сокращения специфичны для вашей проблемы,
количество потоков, используемых для карты, является статическим,
Я следовал вашему стилю и использовал глобальные переменные,
для удобства я использовал boost::barrier для синхронизации

Однако это должно дать вам представление об алгоритме и о том, как вы можете применить его к аналогичным задачам.

предостережение: код не проверен.

1

Источник

Accepted Answer

Если массив не отсортирован, просто используйте один цикл, чтобы сравнить каждый элемент с x, Если ты что-то забываешь нам сказать, я не вижу необходимости во что-то более сложном.

Если массив отсортирован, существуют алгоритмы (например, бинарный поиск), которые имеют лучшую асимптотическую сложность. Однако для массива из 20 элементов простой линейный поиск все еще должен быть предпочтительной стратегией.

4