Углубленный курс программирования, 322 гр., СМ

Место и время проведения: четверг, четвертая (ауд. 2414) пара.
Преподаватель: Голяндина Нина Эдуардовна
Преподаватель: Шлемов Александр Юрьевич shlemovalex@gmail.com

На этом курсе занимаются студенты, которые уже на высоком уровне владеют C++. Здесь мы рассматриваем нестандартные задачи, изучаем новые для себя области и обучаемся разработке софта на реальных проектах.

По поводу того, почему не вызывается конструктор копирования при возврате объекта из функции и передачи его в правую часть оператору присваивания.

Рассмотрим такой пример:

#include <cstdio>
#include <iostream>
 
using namespace std;
 
class A {
public:
  int i;
  A(int _i = 2) {
    i = _i;
    cout << "A(int)" << endl;
  }
  A(const A& a) {
    i = a.i;
    cout << "A(A&)" << endl;
  }
  ~A() {		
    cout << "~A()" << endl;
  }
};
 
class B {
public:
  int i;
  B(int _i = 2) {
    i = _i;
    cout << "B(int)" << endl;
  }
  B(const B& a) {
    i = a.i;
    cout << "B(B&)" << endl;
  }
  ~B() {		
    cout << "~B()" << endl;
  }
};
 
class C {
public:
  int i;
  C(int _i = 2) {
    i = _i;
    cout << "C(int)" << endl;
  }
  C(const C& a) {
    i = a.i;
    cout << "C(C&)" << endl;
  }
 
  C& operator=(const C& a) {
      i = a.i;
      cout << "C = " << endl;
      return *this;
  }
 
  ~C() {		
    cout << "~C()" << endl;
  }
};
 
C func (A a, B b) {
  C temp;
  temp.i = a.i + b.i;
  return temp;
}
 
int main() {
  A a = 3;
  B b = 2;
  C c;
  c = func(a, b);
  return 0;
}

В режиме компиляции Debug в MSVS 2010 он выдает:

A(int)
B(int)
C(int)
B(B&)
A(A&)
C(int)
C(C&)
~C()
~A()
~B()
C =
~C()
~C()
~B()
~A()

А в режиме Release (а также в G++):

A(int)
B(int)
C(int)
B(B&)
A(A&)
C(int)
~A()
~B()
C =
~C()
~C()
~B()
~A()

Т.е. разница в конструктор копирования и деструктор. Собственно, имеется два вопроса:

1. Насколько правомочна такая оптимизация?
2. Почему в обоих случаях деструкторы для копированных параметров a и b вызываются в конце?

По первому вопросу стр. 284 Стандарта C++11¹⁾ говорит (жирный шрифт мой):
When certain criteria are met, an implementation is allowed to omit the copy/move construction of a class object, even if the copy/move constructor and/or destructor for the object have side effects. In such cases, the implementation treats the source and target of the omitted copy/move operation as simply two different ways of referring to the same object, and the destruction of that object occurs at the later of the times when the two objects would have been destroyed without the optimization. This elision of copy/move operations, called copy elision, is permitted in the following circumstances (which may be combined to eliminate multiple copies):

1. in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value;
2. …

То есть если мы возвращаем из функции локальный (automatic) объект, то его дозволительно конструировать прямо по месту возврата (т.е. в случае нашего примера он конструируется прямо в параметры к оператору присваивания). Вообще говоря это будет работать не только для оператора присваивания, но и для любой функции, принимающей параметр-объект и даже несколько параметров-объектов.

Почему же параметры-копии уничтожаются после выполнения присваивания? Стандарт говорит следующее (стр. 260):
Temporary objects are destroyed as the last step in evaluating the full-expression (1.9) that (lexically) contains the point where they were created. This is true even if that evaluation ends in throwing an exception. The value computations and side effects of destroying a temporary object are associated only with the full-expression, not with any specific subexpression.

Все временные объекты живут до конца вычисления выражения.

Предлагается следующая игра: дан некий алфавит, словарь (набор слов) и число K. Изначально у игрока есть пустое слово. Ему последовательно предлагаются K случайных букв из алфавита (буквы генерируются независимо, разумеется). Каждую букву он может либо добавить к своему слову (тут два варианта, в первом он может добавлять только в конец, во втором — или в конец, или в начало слова), либо отклонить. Цель игрока — собрать слово (из словаря) максимально длины. За собранное слово игрок получает столько очков, сколько в слове букв. Если собрать слово не получилось, то игрок получает ноль очков.

Исходно предлагалось провести соревнование между программами, реализующими различные стратегии игры, используя среднее число очков для оценки качества стратегии.

Требуется исследовать математическую модель игры (с точки зрения максимизации матожидания полученных очков) и ответить на следующие вопросы:

1. Существует ли оптимальная стратегия игры?
2. Какова сложность по времени и необходимая память для реализации оптимальной стратегии?
3. Каким образом можно сформулировать правила соревнований между реализациями стратегий, чтобы исключить возможность наивной реализации оптимальной стратегии?

Достаточно быстро выяснилось, что оптимальная стратегия существует и требует для игры хранить таблицу размера N_prefix(Voc) * K булевых значений для варианта, когда можно добавлять букву только в конец; и таблицу размера N_substr(Voc) * K значений из множества {0, -1, 1} для другого варианта (здесь N_prefix(Voc) — количество уникальных префиксов в словаре; N_substr(Voc) — количество уникальных подстрок в словаре, таблица по одному измерению будет проиндексирована в одном случае уникальными префиксами, в другом случае — подстроками). Tаблица рассчитывается с помощью динамического программирования, вычисление каждой ячейки требует обращения к другим ячейкам в количестве, имеющим порядок длины алфавита.

Фактически эта таблица является указанием к принятию решения во всех возможных ситуациях. Опишем, как это происходит. Для простоты рассмотрим вариант игры, когда буква добавляется только в конец. Пусть уже построено слово A, получена буква x и осталось получить еще k букв. Нужно принять решение относительно буквы x. Если слово Ax не является префиксом никакого слова из словаря, то брать букву x не имеет смысла. Если же Ax является префиксом, то находим в таблице соответствующую этому префиксу строку и принимаем решение в зависимости от ее ее k-го элемента. Т.е. таблица хранит все возможные значения функции-советника f(X, k), где X — префикс, а k — количество оставшихся букв. Если функция не определена, брать букву нельзя.

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

Также выяснилось, что для реального словаря эта таблица достаточно хорошо сжимается с помощью RLE-кодирования, в силу того, что f(X, k) редко меняется по k (т.е. фактически достаточно запоминать только точки изменения и вести по списку бинарный поиск).

Итак:

1. Оптимальная стратегия существует.
2. Для предрасчета требуется O(N_{prefix/substr}(Voc) * K * N_alphabet) операций обращения к структуре таблицы (если хранить таблицу в виде т.н. «Бора», а не ассоциативного массива, то трудоемкость обращения будет константной).
3. Таблица значений функции-советника может быть эффективно сжата.

Таким образом, оставалось только решить вопрос о правилах соревнований. Было решено, что вполне разумно разрешить линейную зависимость сложности алгоритма от количества уникальных префиксов, однако необходимо исключить линейный рост сложности с ростом K.

Было решено использовать следующую схему — иметь предрассчитанную таблицу для небольших k, а для больших использовать некоторую эвристику. Сами соревнования было решено проводить при следующих значениях K:

1. 100 — проверка реализации оптимальной стратегии;
2. 2000 — максимальное K, для которого при имеющемся словаре время вычисления таблицы разумное, а сама таблица в несжатом виде влезает в память (здесь предлагается сравнивать эвристику с оптимальным решением);
3. 5000 — при таком K реализация оптимальной стратегии затруднена (из-за большого объема таблицы²⁾).

В качестве отправной точки для разработки эвристик был предложено следующее рассуждение:
Пусть K = Inf. Тогда оптимальная стратегия выглядит следующим образом: выбираем в словаре самое длинное слово, затем ждем, пока оно соберется. Таким образом гарантировано имеем максимум очков. Количество шагов, необходимое для получения одной нужной буквы, распределено по геометрическому закону, можем найти распределение общего количества шагов (нетривиально для варианта, когда букву можно добавлять с обоих концов из-за того, что буквы в слове могут повторяться).

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

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

Было выяснено, что при больших K (K >= 1000) результат работы оптимального алгоритма практически не отличается от жадного решения, состоящего в наборе какого-нибудь слова из множества слов максимальной длины. Формула для вероятности собрать заданное слово описана в приложении. Например, вероятность P построить выбранное слово длины n = 23 (максимальная длина слова для использованного словаря) при K = 1000 равна 0.996, а среднее число набранных очков при данной стратегии равно 22.91 (=P * n). Таким образом, использование более изощренного эвристического решения в реальном случае выглядит нецелесообразно.

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

Будем хранить таблицу размера N_prefix(Dict) * N_alphabet булевых значений для варианта игры, когда можно добавлять букву только в конец слова; и таблицу размера N_substr(Dict) * N_alphabet значений из множества {-1, 0, 1} для двустороннего варианта. Таблицу рассчитаем методом динамического программирования следующим образом:
Для каждого префикса определим множество тех символов, которые следует брать, находясь в данной вершине в процессе игры (т.е. имея данный префикс в качестве уже составленного слова). Очевидно, что символы, ведущие в отсутствующие в словаре префиксы, не принадлежат данному множеству. Также будем хранить для каждого префикса матожидание количества символов, необходимое для того, чтобы закончить слово. Предположим, что мы находимся в каком-либо префиксе, для которого для всех исходящих строк уже произведен подсчет. Такого можно добиться, используя рекурсивный обход в глубину. Пусть {m₁, …, m_k} — множество исходящих ребер из текущего префикса, а f(m_i) - матожидание соответствующего исходящего префикса, 1 ≤ i ≤ k ≤ N_alphabet. Допустим, что необходимо оставить 1 ≤ d ≤ k символов для данной вершины. Тогда матожидание для текущего префикса может быть рассчитано, как f_cur = (N_alphabet + Σ_{i = 1} ^d f(m_{a_i})) / d, где a_i — множество индексов требуемого подмножества. Однако, нам не нужно перебирать все возможные подмножества {a_i}. Заметим, что величина f_cur при фиксированном d достигает наименьшего значения, когда f(m_{a_i}) являются первыми d элементами последовательности отсортированных по возрастанию матожиданий f(m_i). Таким образом, требуется произвести сортировку, после чего перебрать возможные значения d, и выбрать то, при котором f достигает наименьшего значения, после чего пометить символы m_{a_i} как «необходимые», т.е. те, которые следует брать при данном префиксе.

Решение продолжается на вариант, когда добавление букв допустимо с обеих сторон, аналогично предыдущей задаче.

Таким образом, мы получили алгоритм, имеющий трудоемкость O(N_prefix(Dict) * N_alphabet * log(N_alphabet)) для варианта, когда символы добавляются в конец строки, и O(N_subst(Dict) * N_alphabet * log(N_alphabet)) для другого варианта. O(N_alphabet * log(N_alphabet)) в данном случае — трудоемкость работы сортировки множества ребер. Для более подробного решения см. приложение.

1. Подробное описание полученных результатов (редакция 5, 08.10, 21:00, вероятно, окончательная)
2. Программные реализации описанных стратегий (редакция 4, 08.10, 22:00, добавлено README и описание в заголовках файлов, улучшен код, сборка CMAKE (проверялось на gcc и VS2010), нет проверки эвристики и сравнения стратегий).