I've written a procedure in both C++ and PHP and I don't understand why the C++ version is so much slower than the PHP one.
I have a set of elements in which every element hold a certain amount of ids. The objective is to find a (maybe all) the combinations that cover all the ids.
E.G:
A [1, 2]
B [2, 3]
C [3]
Possible combinations: A+B, A+C
This is the C++ code (please don't judge the style, when it's consolidated i'll rewrite it better):
#include <map>
#include <vector>
#include <iostream>
#include <cassert>
#include <chrono>
using namespace std;
class cRace {
public:
int id;
vector<int> drivers;
};
map<int, vector<int>> d_r;
vector<cRace> r_d;
int globcount;
map<string, int> solutions;
std::chrono::time_point<std::chrono::high_resolution_clock> start;
int get_by_fewer(vector<cRace> table_by_race, string id, int count, map<int, int> coverage)
{
auto it = table_by_race.begin();
count++;
for (int driver : (*it).drivers) {
globcount++;
string sub_id = id;
if (sub_id.length())
sub_id += "|";
sub_id += to_string(driver);
vector<cRace> copy_table = table_by_race;
map<int, int> copy_coverage = coverage;
auto driver_data = (*d_r.find(driver)).second;
for (int race : driver_data) {
copy_coverage[race] = 0;
}
if (r_d.size() == copy_coverage.size()) {
cout << "FOUND SOLUTION: " << sub_id << " (" << count << ")\n";
auto elapsed = std::chrono::high_resolution_clock::now() - start;
long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
long milliseconds = (long) (microseconds/ 1000) % 1000;
long seconds = (((long) (microseconds / 1000) - milliseconds)/1000)%60 ;
cout << "ELAPSED: " << seconds << "." << milliseconds << "\n";
cout << "COUNT: " << globcount << "\n";
return 1;
} else {
if (count >= 19)
continue;
while (true) {
copy_table.erase(copy_table.begin());
it = copy_table.begin();
if (it == copy_table.end())
break;
if (copy_coverage.find((*it).id) != copy_coverage.end())
continue;
//cout << "NEXT : " << (*it).id;
if (get_by_fewer(copy_table, sub_id, count, copy_coverage))
return 1;
break;
}
}
}
return 0;
}
int main(int argc, char **argv)
{
{
// vectors/maps initialization
}
cout << "START!\n";
start = std::chrono::high_resolution_clock::now();
get_by_fewer(r_d, "", 0, map<int, int>());
return 0;
}
this is the PHP version:
// data initialization
global $time_start;
global $solutions;
global $solutions_min;
global $globcount;
$solutions_min = 1000;
$solutions = [];
function get_by_fewer($table_by_race, $ids = [], $count = 0)
{
global $time_start;
global $table;
global $solutions;
global $solutions_min;
global $globcount;
$first_key = array_key_first($table_by_race);
$first_drivers = $table_by_race[$first_key];
$count++;
$skipfirst = 0;
foreach ($first_drivers as $driver)
{
$globcount++;
$sub_ids = $ids;
$sub_ids[] = $driver;
$copy_table = array_diff_key($table_by_race, $table[$driver]);
if (!count($copy_table))
{
if ($solutions_min > $count)
{
if ($solutions_min < 1000)
echo "FOUND SOMETHING BETTER, RESETTING RESULTS\n\n";
$solutions = [];
$solutions_min = $count;
}
if ($solutions_min === $count)
{
$solution = implode($sub_ids, "|");
if (!isset($solutions[$solution])) {
echo "FOUND SOLUTION: " . $solution . " (" . $count . ")\n";
$solutions[$solution] = $count;
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "ELAPSED: " . $time . "\n";
echo "COUNT: " . $globcount . "\n";
exit;
}
}
}
if ($count + 1 < 20)
get_by_fewer($copy_table, $sub_ids, $count);
}
}
echo "START!\n";
$time_start = microtime(true);
get_by_fewer($reverse_table);
exit;
results:
PHP
START!
FOUND SOLUTION: 66|105|49|127|114|120|118|35|39|116|100|64|106|79|117|98|78|133|93 (19)
ELAPSED: 0.47768187522888
COUNT: 472105
C++
START!
FOUND SOLUTION: 66|105|49|127|114|120|118|35|39|116|100|64|106|79|117|98|78|133|93 (19)
ELAPSED: 29.947
COUNT: 472105