Марафонские задачки по С++

В этом посте мы обсудим решение нескольких задачек, которые я подсмотрел из «Марафон задач по С++» (мне кажется ссылки легко найдутся поисковиком). Нет, к сайту я решительно никакого отношения не имею, однако узнал о нем с хабра: либо был у кого-то в профиле, либо была ссылка в комментариях. Итак, определимся с задачками, решения которых будут рассматриваться (задачек всего 9, но эти показались мне интересными):

• Забыл, как умножать. Помогите!
  Умножить число на 7, не используя операцию умножения.
• Два в одном.
  Какой-то умник поменял местами кнопки в лифте. Поставил вместо первого этажа второй, а вместо второго – первый. Честное слово, мне лень ковырять кнопки. Я лучше перепрограммирую лифт. Но программировать мне тоже лень. На вас вся надежда. Напишите, пожалуйста, функцию-переключатель, которая возвращает 1, если на входе 2 и 2, если на входе 1.

Подготовка

Обычно меня совершенно не тянет (не тянуло) решать задачи такого «занимательного» (и, возможно, познавательного) рода, но в этот раз, то-ли прекрасная погода за окном, то-ли рабочий-плавно-перетекающий-в-нерабочий день сделали своё дело и, я решился. Как я уже описывал, мне попалась на глаза статья (правильнее написать цикл из 3 статей) о неком марафоне задач по С++. Любопытство взяло верх и решился набросать решения: но не в голове, как обычно, а на бумаге. И, как вы могли догадаться, после первой зачеркнутой строчки я закончил это бредовое занятие (писанина на бумаге) и решил так: использую только простенький текстовый редактор (gedit) и, в крайнем случае, google.

Поехали

Задача номер раз:

Забыл, как умножать. Помогите! Умножить число на 7, не используя операцию умножения.

Вариант решения для однопоточной модели выполнения напрашивается сам собой:

• функция, которая получает как аргумент число для умножения на 7, выполняет 7 последовательных сложений, после чего возвращает результат (runtime):
  

  // Дабы не стесняться в размерах typedef unsigned long long TCurrentCalculateType;  inline TCurrentCalculateType mulby7(TCurrentCalculateType value) {    return value + value + value + value + value + value + value;  }  // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(mulby7(1) == 7); assert(mulby7(7) == 49); #endif //DEBUG 

Статью на таком не вытянешь. Взглянем шире: вообще, что за ограничение такое — умножить произвольное число именно на 7? Непорядок: даешь умножение произвольного числа на произвольное число не используя умножения:

• итерационная функция, которая получает как аргумент число для умножения на N, выполняет N последовательных сложений в цикле, после чего возвращает результат (runtime):
  

  // Держим в уме // typedef unsigned long long TCurrentCalculateType;  inline TCurrentCalculateType mulbyN(unsigned long long times, TCurrentCalculateType value) {    TCurrentCalculateType result = 0;    for(unsigned long long i = 0; i < times; ++i)      result += value;    return result;  }   // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(mulbyN(7, 1) == mulbyN(1, 7)); assert(mulbyN(7, 7) == 49); #endif //DEBUG 

• параметризованный класс, который получает как аргумент число для умножения на N, выполняет N последовательных сложений, рекурсивно инстанцируя шаблоны, после чего результат доступен в static const члене класса (compiletime):
  

  // Держим в уме // typedef unsigned long long TCurrentCalculateType;  // Салат: огурцы, помидоры, салат: огурцы, ...  // Выполнится N + 1 инстанцирований шаблона (включая завершающий) template <typename T, T value, int step>  struct mulStep {    static const T partSumm = value + mulStep<T, value, step - 1>::partSumm;  };  // Завершаем рекурсию, конкретизируя шаблон template <typename T, T value>  struct mulStep<T, value, 0> {    static const T partSumm = 0;  };  template <unsigned long long times, TCurrentCalculateType value> struct mulbyNct {   static const TCurrentCalculateType result = mulStep<TCurrentCalculateType, value, times>::partSumm; };  static_assert(mulbyNct<7, 7>::result == 49, "Imposible!"); static_assert(mulbyNct<10, 10>::result == 100, "Imposible!"); 

Да, третий вариант не был написан «с лету»: пришлось освежить в памяти очень похожий на нашу задачу пример вычисления факториала. Подглядел, что поделать. Но, на самом деле, я первоначально написал следующий код, который в использовании хоть и выглядит более органично, нежели предложенный выше, но не собирается, в силу некоторых (логичных) ограничений:

template <int times, typename T> inline T mulbyNct(T value) {   return mulStep<T, value, times>::partSumm; }  // Барабанная дробь... // std::cout << mulbyNct<7>(calcMeDigit) << std::endl; // и нифига. ошибка компиляции :( 

«Лажаете, парниша» — заметит внимательный читатель. Согласен, что можно оптимизировать хлебные крошки: если инициализировать result начальным значением, равным value — получится сэкономить на одном шаге цикла. Получаем:

// Держим в уме // typedef unsigned long long TCurrentCalculateType;  inline TCurrentCalculateType mulbyNlittleFast(unsigned long long times, TCurrentCalculateType value) {    TCurrentCalculateType result = value;  // первая крошка   for(unsigned long long i = 1; i < times; ++i)  // вторая крошка     result += value;    return result;  }   // Псевдо код замены функции // хотя я ее не переименовывал, просто поправил #undef mulbyN #define mulbyN mulbyNlittleFast  // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(mulbyN(7, 1) == mulbyN(1, 7)); assert(mulbyN(7, 7) == 49); #endif //DEBUG 

«Все равно мало вариантов», подумалось мне и, открыв этот сайтик, оглядев функторы я сообразил четвертый вариант:

• ох уж этот четвертый вариант:
  

  // Держим в уме // typedef unsigned long long TCurrentCalculateType;  inline TCurrentCalculateType mulbyNSTL(unsigned long long times, TCurrentCalculateType value) {    TCurrentCalculateType result = value;    std::binder1st<std::plus<TCurrentCalculateType> > plus1st(std::plus<TCurrentCalculateType>(), value);       for(unsigned long long i = 1; i < times; ++i)      result = plus1st(result);         return result;  }   // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(mulbyNSTL(7, 1) == mulbyNSTL(1, 7)); assert(mulbyNSTL(7, 7) == 49); #endif //DEBUG 

Знаю, жениться мне нужно, а не изобретать таких монстров… но не об этом сейчас. Для того, чтобы говорить о том, какое решение «лучше», для начала необходимо определиться с метрикой сравнения. По хорошему — метрика минимального произведения используемой памяти и времени выполнения:
algo_diff = used_mem * calc_time; algo_winner = min(algo_diff(1, 2, 3, ..., N))
А погода-то отличная, так что решил остановиться только на минимизации времени выполнения: быстрее — лучше.

Prepare to fight

Начнем с вещей, которые писать самому не хотелось — «таймер» времени выполнения. Для замера будем пользоваться классом, найденным когда-то на просторах интернета. Классец маленький и простенький, однако даже он использует подобие принципа RAII (да, снова помощь google). Располагаем это на стеке и вуаля:

#include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h>  class StackPrinter { public:   explicit StackPrinter(const char* msg) :  msMsg(msg)  {     fprintf(stdout, "%s: --begin\n", msMsg.c_str());     mfStartTime = getTime();   }    ~StackPrinter()  {     double fEndTime = getTime();     fprintf(stdout, "%s: --end (duration: %.10f sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));   }    void printTime(int line) const  {     double fEndTime = getTime();     fprintf(stdout, "%s: --(%d) (duration: %.10f sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));   }  private:   double getTime() const  {     timeval tv;     gettimeofday(&tv, NULL);     return tv.tv_sec + tv.tv_usec / 1000000.0;   }      ::std::string msMsg;   double mfStartTime; };  // Use case //  //{ //  StackPrinter("Time to sleep") sp; //  sleep(5000); //} 

Но, этот «принтер» подойдет для вывода на консоль, а мне хочется более удобного вывода для последующего анализа с помощью LabPlot (LabPlot sourceforge). Тут можно плакать кровавыми слезами, ибо я злосто нарушаю DRY (да польются слезы кровавые у увидевшего сие. И вообще, делайте скидку на теплую погоду и холодную голову):

class StackPrinterTiny { public:   explicit StackPrinterTiny(const char* msg) {     mfStartTime = getTime();   }    ~StackPrinterTiny() {     double fEndTime = getTime();     fprintf(stdout, "%g\n", (fEndTime-mfStartTime));   }    void printTime(int line) const {     double fEndTime = getTime();     fprintf(stdout, "(%d) %g\n", line, (fEndTime-mfStartTime));   }  private:   double getTime() const {     timeval tv;     gettimeofday(&tv, NULL);     return tv.tv_sec + tv.tv_usec / 1000000.0;   }      double mfStartTime; };  #ifdef OutToAnalyze typedef StackPrinterTiny usedStackPrinter; #else typedef StackPrinter usedStackPrinter; #endif  // Use case //  //{ //  usedStackPrinter("Time to sleep") sp; //  sleep(5000); //} 

На финишной прямой

Теперь, чтобы поделка собралась, нам понадобится немного «обвязочного» кода — давайте уважим компилятор:

#include <iostream> #include <functional> #include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h> #include <climits>  typedef unsigned long long TCurrentCalculateType;  // Closured: result, fiMax // loop, loooop, loooooooop #define LOOP_LOOP(what) \ for(unsigned long long fi = 0; fi < fiMax; ++fi) \ for(unsigned long long fi2 = 0; fi2 < fiMax; ++fi2) \ for(unsigned long long fi3 = 0; fi3 < fiMax; ++fi3) \ result = what  int main() {    // Константа необходима только для  mulbyNct<>   const TCurrentCalculateType calcMeDigit = 9000000;   const unsigned long long fiMax = ULLONG_MAX;       #ifndef OutToAnalyze   std::cout << "Calculate: " << calcMeDigit << " with fiMax = " << fiMax << std::endl; #endif    currentCalculateType result = 0;    #ifdef CALCULATE_IN_COMPILE_TIME   std::cout << "compile time " << calcMeDigit << " * " << calcMeDigit << " = " << mulbyNct<calcMeDigit, calcMeDigit>::result << std::endl; #endif    {     usedStackPrinter sp("1");              // on image - mulby7     LOOP_LOOP(mulby7(calcMeDigit)); #ifndef OutToAnalyze         std::cout << "by x7 = " << result << std::endl; #else     std::cout << "=" << result << std::endl; #endif       }     {     usedStackPrinter sp("2");              // on image - mulbyN     LOOP_LOOP(mulbyN(calcMeDigit, calcMeDigit)); #ifndef OutToAnalyze         std::cout << "x*x where x is " << calcMeDigit << " = " << result << std::endl; #else     std::cout << "=" << result << std::endl;     #endif       }      {     usedStackPrinter sp("3");              // on image - mulbyNSTL     LOOP_LOOP(mulbyNSTL(calcMeDigit, calcMeDigit)); #ifndef OutToAnalyze         std::cout << "STL x*x where x is " << calcMeDigit << " = " << result << std::endl; #else     std::cout << "=" << result << std::endl; #endif       }    return 0; }  // Compile with // // clear && g++ main.1.cpp -O3 -std=c++0x -o main.1 // P.S. не сообразил я про ключик -Ofast. Если будет интерес - дополню позже. 

У нас есть все необходимое для успешной сборки и получения результатов. Если собралось (а оно должно) — продолжаем.

Мы считали, мы считали — наши ядерки устали

Кстати, пока не забыл: в compile time у меня не получилось посчитать больше, чем 498 * 498. Иначе говоря, если я при #if defined(CALCULATE_IN_COMPILE_TIME) выставлял calcMeDigit = 499 (и более) то получал ошибку компиляции: уж не stack overflow при разворачивании шаблонов? Каюсь, не разбирался. Итак, возвращаемся к тестам в run time: цифры приводить, на мой взгляд, бессмысленно, т.к. на вашей машине они будут другими: а вот визуализировать в картиночке — это пойдет. Хм, я смотрю вы стали забывать, как нужно плакать кровавыми слезами — я с радостью напомню. Далее приведен скриптик, который помогал собирать циферики в файл, для последующего анализа и построения картинок в LabPlot’e (я вас предупреждал):

Результаты на моей машине (Intel® Core(TM) i5 CPU @2.8 GHz CPU, 8 GiB Memory):

Совет под номером 43 Скотта Мейерса гласит «Используйте алгоритмы вместо циклов». В более широком смысле совет можно понимать как используйте стандартные алгоритмы, коллекции и объекты, чтобы получить более читаемый, поддерживаемый и безопасный, а, иногда, и более производительный код. Какого ху… дожника, спросите вы (я уже перестал задаваться этим вопросом), среднее время варианта mulbyNSTL, меньше чем у его родителя mulbyN. Я грешу на свои не cовсем прямые руки… но что есть, то есть.

Первый первый, я второй

Задача номер два:

Два в одном. Какой-то умник поменял местами кнопки в лифте. Поставил вместо первого этажа второй, а вместо второго – первый. Честное слово, мне лень ковырять кнопки. Я лучше перепрограммирую лифт. Но программировать мне тоже лень. На вас вся надежда. Напишите, пожалуйста, функцию-переключатель, которая возвращает 1, если на входе 2 и 2, если на входе 1.

Покумекав, я придумал только 1 вариант решения:

• функция, которая получает как аргумент номер этажа, производит побитовое сложение по модулю два и возвращает результат:
  

  int worker1(unsigned int n) { return (n xor 3); }  // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(worker1(2) == 1); assert(worker1(1) == 2); #endif //DEBUG 

Один вариант маловато. Один вариант не сравнить, поэтому я решил придумать второй идиотский вариант: делает побитовое «И», инкрементирует результат и возвращает получившееся значение:

int worker2(unsigned int n) { return (n & 1) + 1; }  // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(worker2(2) == 1); assert(worker2(1) == 2); #endif //DEBUG 

И, к моему несчастью, я подглядел изящный ответ этой задачки (по версии того, кто её породил): возвращаем результат вычитания номера этажа из 3:

int worker3(unsigned int n) { return 3 - n; }  // Не забываем, что assert() тянется из // #include <assert.h> #ifdef DEGUB assert(worker3(2) == 1); assert(worker3(1) == 2); #endif //DEBUG 

Теперича, с использованием уже известного скриптика для сбора данных (вы не могли забыть кровавые слезы) мы напишем программку для тестирования скорости выполнения этих крошечных функций (worker1, worker2, worker3). Кажется, вы уже заподозрили у меня нездоровую тягу к шаблонам — спешу вас огорчить, это неправда. А тут что у нас? Это вспомогательный класс для использования генераторов в алгоритме std::generate:

// Like binder1st // require #include <numeric>, #include <random> template <class Operation, class TRandomEngine> class binderRandom: public std::unary_function <void, typename Operation::result_type> { protected:   Operation op;   TRandomEngine& y; public:   binderRandom ( const Operation& x, TRandomEngine& y) : op (x), y (y) {}   typename Operation::result_type operator()() { return op(y); } };  

Идея стара как С++ мир: соорудим вектор случайных чисел (номеров этажей, т.е. [1, 2]) и выполним предложенные функции для каждого элемента последовательности… Итого:

#include <iostream> #include <functional> #include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h> #include <climits>  #include <vector> #include <algorithm> #include <numeric> #include <random> #include <iterator>  int main() {    static std::mt19937 _randomNumbersEngine;    std::vector<unsigned int> _vectorNumbers(50000000); // сколько вешать в граммах?   std::uniform_int<unsigned int> uiRandomNumber(1, 2);     std::generate(_vectorNumbers.begin(), _vectorNumbers.end(), binderRandom<std::uniform_int<unsigned int>, std::mt19937>(uiRandomNumber, _randomNumbersEngine)); // заполняет вектор киногероем Раз-Два      // Погнали наши городских   //   {     usedStackPrinter sp("1");         std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker1);   }     {     usedStackPrinter sp("2");         std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker2);   }    {     usedStackPrinter sp("3");         std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker3);   }    return 0; } 

Результаты на моей машине (Intel® Core(TM) i5 CPU @2.8 GHz CPU, 8 GiB Memory):

Вот тут результат адекватный: оба (нормальных) варианта выполняются за одинаковое время (разницу скинем как погрешность измерения). Интересно, а если глянуть в генерируемый код, он будет похожим или даже одинаковым? Это уже тема отдельного разговора, так что остаётся на домашнее задание читателю.
В любом случае — мне понравилось заниматься этой фигней, а значит время потрачено не зря (личное оценочное суждение).

Заключение

• Оказывается, писать без IDE со всяческими auto complete (типа Visual Assist X от Whole Tomato) не так смертельно сложно (видимо пока не более 200+ строчек и простая логика). Да, не хватает множества вещей: умное выравнивание, парные скобки и кавычки, но есть в этом что-то такое… что-то такое, что говорит мне: правильная и удобная IDE — это круто!
• Если интернет в офисе отключат… работа, конечно, не встанет, но странных поделок прибавится
• Из описания простой задачки можно выжать столько воды
• Версия gcc 4.4.5 и поэтому я не использовал lambda — а ведь в случаях с «workerN» так бы здорово смотрелось
  

  std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(),    [](int n) { return n xor 3; } );

• Моё отношение к ШП — IT MMM

Такие дела. Спасибо за внимание и удачи!

^{P.S. Ошибки или опечатки пишите, пожалуйста, в личку.}