// Task: Modify the loop of the // even_odd_difference function // to make it more efficient. // Explanation: // The function computes how many more even // numbers are in an array of 100000 numbers. // // the loop currently uses // eo_diff += (*it % 2 == 0 ? 1 : -1); // to increment the count if *it is even and // to decrement the count if *it is odd. // The total result will be the difference of // even and odd numbers in the array. // // This needs a rewrite to improve performance. // Write your improved version in the provided // template function // even_odd_difference_im(...) // below and hit run to test your improvement. #include #include #include #include #include #include #include // added #include #include using Int_seq = std::valarray; // YOUR IMPROVED DESIGN here: template int64_t even_odd_difference_im(ForwardIterator first, ForwardIterator last) { ForwardIterator it = first; int64_t eo_diff = 0; while(it != last) { eo_diff += (*it % 2 == 0 ? 1 : -1); it++; } return eo_diff; } // added int64_t even_odd_difference_im(Int_seq const& data) { // sololearn is not allowing me to do // static Int_seq const& iseq = // data[(data&1)>0]. Subscript returns // the valarray by reference where as // apply creates a new valarray. // Below statement checks each element // for odd and even value and create new // valarray of odd values. Size of new // valarray is the total no of odds in // in the original array. So now you // size of original array, no of odds in // original array, you can calculate // number of even elements and diff // between odd and even elements static Int_seq const& iseq = data[ (data.apply([](std::seed_seq::result_type v){return v & 1;})) > 0]; return abs( ((data.size()-iseq.size())-iseq.size())); } // DO NOT CHANGE ANYTHING // BEYOND THIS POINT // original design. DO NOT CHANGE THIS! template int64_t even_odd_difference(ForwardIterator first, ForwardIterator last) { ForwardIterator it = first; int64_t eo_diff = 0; while(it != last) { eo_diff += (*it % 2 == 0 ? 1 : -1); it++; } return eo_diff; } [[gnu::always_inline]] inline uint64_t tick() { unsigned int lo, hi; asm("rdtsc" : "=a"(lo), "=d"(hi)); return (uint64_t) lo | (uint64_t) hi << 32; } int main() { using std::cout; using std::endl; using std::setw; using std::array; using std::string; using std::seed_seq; int64_t eodiff1 = 0 , eodiff2 = 0; uint64_t t0, t1, t2 , orig_total , impr_total; constexpr unsigned RUNS = 1000; constexpr size_t DATASZ = 100000; // generate data string seed_str = "optimise"; seed_seq seed(seed_str.begin(), seed_str.end()); array data; seed.generate(data.begin(), data.end()); // added Int_seq iseq(DATASZ); // ensuring same data as in array std::copy(data.begin(), data.end(), std::begin(iseq)); // run performance test t0 = tick(); eodiff1 = even_odd_difference(data.begin(), data.end()); t1 = tick(); eodiff2 = even_odd_difference_im(iseq);//data.begin(), data.end()); t2 = tick(); if(eodiff1 != eodiff2) { cout << "non-matching even-odd difference counts\n" << "Original : " << eodiff1 << "Improved : " << eodiff2 << endl; return 0; } orig_total = t1 - t0; impr_total = t2 - t1; for(unsigned run = 1; run < RUNS; run++) { t0 = tick(); eodiff1 = even_odd_difference(data.begin(), data.end()); t1 = tick(); eodiff2 = even_odd_difference_im(iseq);//data.begin(), data.end()); t2 = tick(); orig_total += t1 - t0; impr_total += t2 - t1; } cout << " orig. impr." << endl;; cout << "e/o diff: "; cout << setw(7) << eodiff1 << setw(10) << eodiff2 << endl; cout << std::fixed << std::setprecision(0); cout << "Time avg: " << setw(7) << (double) orig_total / RUNS << setw(10) << (double) impr_total / RUNS << endl; double ratio = (double) impr_total / orig_total; cout << "\nTime ratio improved/original:\n " << std::setprecision(3) << ratio << endl; cout << "\n\n"; if(ratio < 0.4) cout << "Awesome! Well done!"; else if(ratio < 0.75) cout << "Nice improvement. Good job!"; else if(ratio < 0.9) cout << "Oh, you can do better!"; else if(ratio < 1.01) cout << "Are you sure you improved anything?"; else cout << "Wow... you made it even worse!"; cout << endl; return 0; }

even_odd_diff_optimization(Bennett_task).cpp