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

Приветствую всех!

В этом посте мы обсудим решение нескольких задачек, которые я подсмотрел из «Марафон задач по С++» (мне кажется ссылки легко найдутся поисковиком). Нет, к сайту я решительно никакого отношения не имею, однако узнал о нем с хабра: либо был у кого-то в профиле, либо была ссылка в комментариях. Итак, определимся с задачками, решения которых будут рассматриваться (задачек всего 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: --beginn", 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, "%gn", (fEndTime-mfStartTime));
  }

  void printTime(int line) const {
    double fEndTime = getTime();
    fprintf(stdout, "(%d) %gn", 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. Ошибки или опечатки пишите, пожалуйста, в личку.}

Автор: maxvodo

Источник