379
Воспользуйтесь колесиком мышки чтобы настроить масштаб
aaaadddaaaa
КАК ВСПОМНИТЬ "И ТАК ИЗВЕСТНОЕ"

Язык записи сути креативных задач в программировании и не только

© Сергей Сычёв, TRIZ-RI Group, Кирилл Лебедев, г. Санкт-Петербург

Язык записи сути креативных задач в программировании

Для людей с неклиповым мышлением.

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


ЗАДАЧА 1.
СЭКОНОМИТЬ ДЕЙСТВИЯ
РЕШЕНИЕ ЗАДАЧИ 1 ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ
ЗАДАЧА 2.
СЭКОНОМИТЬ КЛАССЫ
РЕШЕНИЕ ЗАДАЧИ 2 РЕШЕНИЕ ЗАДАЧИ 4
ЗАДАЧА 3.
СЭКОНОМИТЬ СИЛЫ
РЕШЕНИЕ ЗАДАЧИ 3 СЭКОНОМИТЬ МЫШЛЕНИЕ
СЭКОНОМИТЬ ЗАДАЧИ СЭКОНОМИТЬ РЕШЕНИЯ    

Сразу начнем с сути дела.  Существует некий язык записи сути задачи. Если его применять, то сложные (креативные) задачи решать становится удобнее.

Как и любая модель, эта модель тоже жизнь собой не заменяет, однако авторы статьи попробовали и убедились в том, что действительно удобно. Хотя поначалу кажется непривычным… Впрочем, авторы, уважая время Коллег, постеснялись бы писать о привычном, знакомом, общеизвестном.

Рассмотрим серию примеров. Пока намеренно несложных. (Более сложные мы в дальнейшем тоже рассмотрим).

ПРИМЕР 1
Программа для просмотра документов должна отображать такой цвет фона, который задан в документе, и должна отображать цвет фона, заданный в настройках самой программы.

ПРИМЕР 2
В момент запуска программы красивая заставка с анимацией должна появляться, чтобы качественно презентовать продукт, и не должна появляться, чтобы не раздражать пользователя.

ПРИМЕР 3
Для более точной настройки программа должна содержать много разных опций, и, в то же время, количество опций должно быть невелико, чтобы пользователь не замучался их выставлять.

ПРИМЕР 4
Среда разработки программ должна представлять проект в виде набора файлов, чтобы пользователь имел возможность оперировать файлами, и в то же самое время должна представлять проект в виде набора классов, чтобы пользователь имел возможность оперировать классами.

ПРИМЕР 5
В редакторе документов тулбаров должно быть много, чтобы пользователь имел возможность быстро вызвать нужную ему команду, и должно быть мало, чтобы на экране оставалось место для окна редактирования, и у пользователя "не рябило" в глазах.

ПРИМЕР 6
По нажатию кнопки "Compile" среда разработки должна вызывать то один компилятор, то – другой.

В приведенных примерах  "суть задачи" записана в виде противоречия. Зачем? Ответу на этот вопрос и посвящен данный материал.

В рассматриваемой модели используется принцип, сформулированный в ТРИЗ (Теории Решения Изобретательских Задач, автор 1 Г.С. Альтшуллер): "Если нет противоречия, то нет и креативной задачи". Действительно, если никаких объективных препятствий (кроме, быть может, незнания предметной области) перед программистом не возникает, надо просто сделать то, что требуется. Если программист это знает, то он и делает. В таких случаях, в рамках данной модели, будем говорить: "Творческой задачи нет".

Это, конечно, допущение и найдется немало людей, которые не согласятся с подобным определением творчества. Однако сегодня нашей целью является не поиск философской истины, а описание приемов решения прикладных задач. Поэтому не будем залипать на дефинициях. Рамки поставят и без нашего участия. А лучше рассмотрим несколько конкретных примеров.


ЗАДАЧА 1. СЭКОНОМИТЬ ДЕЙСТВИЯ

Вот задача, решая которую программист столкнулся с противоречием (пока не очень сложным, но все же противоречием).

Предположим, дан фрагмент некоторой функции:  

// Указатель на буфер с данными
char * pszBuff;
// Размер буфера
DWORD dwSize;
// Вспомогательные указатели
char * pszTemp = pszBuff;
char * p0;
char * pEnd;
 
// Ищем строку
p0 = FindStr(pszTemp, dwSize, "/FullName", strlen("/FullName"));
// Ищем открывающий символ
p0 = FindSymbol(p0, ‘(‘);
p0++;
// Ищем закрывающий символ
pEnd = FindSymbol(p0, ‘)’);
// Сохраняем значение
OutputValue(p0, pEnd – p0);
// Вычитаем из общего размера разницу
dwSize -= (pEnd - pszTemp);
// Запоминаем указатель
pszTemp = pEnd;
 
// Ищем строку
p0 = FindStr(pszTemp, dwSize, "/FamilyName", strlen("/FamilyName"));
// Ищем открывающий символ
p0 = FindSymbol(p0, ‘(‘);
p0++;
// Ищем закрывающий символ
pEnd = FindSymbol(p0, ‘)’);
// Сохраняем значение
OutputValue(p0, pEnd – p0);
// Вычитаем из общего размера разницу
dwSize -= (pEnd - pszTemp);
// Запоминаем указатель
pszTemp = pEnd;
 
// Ищем строку
p0 = FindStr(pszTemp, dwSize, "/FontName", strlen("/FontName"));
// Ищем открывающий символ
p0 = FindSymbol(p0, ‘/‘);
p0++;
// Ищем закрывающий символ
pEnd = FindSymbol(p0, ‘ ’);
// Сохраняем значение
OutputValue(p0, pEnd – p0);
// Вычитаем из общего размера разницу
dwSize -= (pEnd - pszTemp);
// Запоминаем указатель
pszTemp = pEnd;

Мы видим, что в данном фрагменте кода трижды повторяется одинаковая последовательность действий. Вот эта последовательность: 

// Ищем строку
FindStr(...);
// Ищем открывающий символ
FindSymbol(...);
// Ищем закрывающий символ
FindSymbol(...);
// Сохраняем значение
OutputValue(...);

Теоретически, ее можно поместить в тело цикла и, тем самым, существенно сократить код функции. Но вот беда: каждый раз последовательность применяется к разным данным. Как быть?

Не суть важно досталась ли данная задача программисту "в наследство" от предыдущего разработчика или, создавая программу, он на каком-то этапе столкнулся с ней самостоятельно, мы видим, что в момент рассуждения он имеет дело с противоречием:

"Если поместить последовательность действий в тело цикла, то можно существенно сократить размер кода (+), но при этом утратится возможность выполнять последовательность каждый раз для уникальных данных" (-).

Если Вы знаете, как решаются такие задачи, и Вы не считаете их творческими, то пока просто представьте себе, что Вы учите думать школьника, обучающегося программированию. Вы хотите добиться, чтобы он сначала подумал, а потом написал. Между тем, призывы "Думай!" не помогают. Как бы Вы ясно и лаконично объяснили такому школьнику суть творческой (для него!) задачи?

Но оставим ненадолго Задачу 1 и рассмотрим Задачу 2.


ЗАДАЧА 2. СЭКОНОМИТЬ КЛАССЫ

Предположим, в графический редактор, который "умеет" работать с линиями, прямоугольниками и многоугольниками, понадобилось добавить новую фигуру – кривую Безье второго порядка.

Это вот такая штуковина.
Кривая Безье 2-го порядка.

Согласно требованиям, фигура должна делать следующее:

  • Во-первых, рисовать себя в окне.
  • Во-вторых, проверять, попадает ли заданная точка на линию контура.  

Поскольку вторая задача для кривых Безье аналитически неразрешима, она выполняется в два прохода:

  • Сначала кривая Безье преобразуется в ломаную линию,
  • а затем (уже для ломаной линии!) осуществляется проверка на попадание точки.

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

Для устранения дублирования кода программист инкапсулировал алгоритм растеризации в базовом классе, а конкретные функции "рисования", вызываемые из алгоритма, поместил в производные классы. В результате, получились три класса: базовый и два производных. Базовый класс ответственен за алгоритм, производные – за рисование в окне и формирование набора точек.

// Базовый класс: содержит алгоритм растеризации
class CBezier2

{
public:
   CBezier2(const POINT points[3]);
   void Draw();
 
protected:
   virtual void MoveTo(const POINT & pt) = 0;
   virtual void LineTo(const POINT & pt) = 0;
 
private:
   POINT m_points[3];
};
// Производный класс: реализует функции MoveTo и LineTo для рисования в окне
class CBezier2InWindow : public CBezier2
{
public:
   CBezier2InWindow(HDC hDC, const POINT points[3]);
 
protected:  
   virtual void MoveTo(const POINT & pt)
   virtual void LineTo(const POINT & pt);
 
private:
   HDC m_hDC;
};
// Производный класс: реализует функции MoveTo и LineTo для рисования в памяти
class CBezier2InMemory : public CBezier2

{
public:
   CBezier2InMemory(const POINT points[3]);
   bool Contains(const POINT & pt) const;
 
protected:
   virtual void MoveTo(const POINT & pt);
   virtual void LineTo(const POINT & pt);
 
private:
   std::vector m_PolyLine;
};

После того, как данное решение было реализовано, в программу потребовалось внести еще одно изменение. По просьбе Заказчика нужно было добавить кривую Безье 3-го порядка.

Это вот такая штуковина.
Кривая Безье 3-го порядка.

 

Если такое добавление делать аналогично, то придется снова создавать три класса. Как и в предыдущем случае, один из них будет отвечать за алгоритм, а два других – за рисование в окне и формирование набора точек.

// Базовый класс: содержит алгоритм растеризации
class CBezier3

{
public:
   CBezier3(const POINT points[4]);
   void Draw();
 
protected:
   virtual void MoveTo(const POINT & pt) = 0;
   virtual void LineTo(const POINT & pt) = 0;
 
private:
   POINT m_points[4];
};
 
// Производный класс: реализует функции MoveTo и LineTo для рисования в окне
class CBezier3InWindow : public CBezier3

{
public:
   CBezier2InWindow(HDC hDC, const POINT points[4]);
 
protected:
   virtual void MoveTo(const POINT & pt);
   virtual void LineTo(const POINT & pt);
 
private:
   HDC m_hDC;
};
// Производный класс: реализует функции MoveTo и LineTo для рисования в памяти
class CBezier3InMemory : public CBezier3

{
public:
   CBezier3InMemory(const POINT points[4]);
   bool Contains(const POINT & pt) const;
 
protected:
   virtual void MoveTo(const POINT & pt);
   virtual void LineTo(const POINT & pt);
 
private:
   std::vector m_PolyLine;
};

Данное решение является трудоемким. При добавлении одной фигуры мы вынуждены добавлять три класса. Как же быть?

Сформулируем противоречие: 

"При добавлении новой фигуры нужно добавлять 1 (один!) класс, чтобы не было трудоемко, и нужно добавлять три класса, чтобы поддержать рисование фигуры в окне и ее растеризацию в виде набора точек".

Если Вы знаете, как решаются такие задачи, не считаете их творческими или, например, если Вы сердитесь по следующей схеме: "Незачем было писать такую структуру. Я бы сделал иначе (Ваше решение) и все дела!", то вновь представьте себе школьника, который сдал Вам урок — код, приведенный выше. Вряд ли Вы поставите ему двойку, скорее перед Вами встанет задача дать ему доходчивое и компактное объяснение, а уж только потом попросить переделать работу. И что же Вы скажете?

Впрочем, и задачу 2 тоже пока отложим. Мы, конечно, вернемся и к ней, но прежде рассмотрим задачу 3. 


ЗАДАЧА 3. СЭКОНОМИТЬ СИЛЫ

В одной библиотеке происходили значительные утечки памяти. По некоторым причинам (их описание выходит за рамки данного материала) утечки нельзя было обнаружить при помощи отладчика. Поэтому в исходном коде были переопределены операторы new и delete.

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

По завершению работы программы информация о блоках памяти, которые содержал список, выводилась в файл. Таким образом, можно было составить представление о том, какой объем памяти был не освобожден.

Поначалу в файл записывались только общее количество блоков и размер каждого из них. Позже была добавлена и запись содержимого блоков.

Переопределенный оператор new имел вот такой вид:  

T * pT = new T;

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

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

T * pT = new(__FILE__, __LINE__) T;

Для этого написали специализированную версию оператора new, которая принимает на вход все необходимые параметры:

void * operator new(const size_t nSize, const char * pszFileName, const size_t nLine)

{
...
}

…И сразу столкнулись с трудностями. Такое решение потребовало существенной переделки кода: все вызовы оператора new с одним параметром (стандартная версия) пришлось бы заменять на вызовы оператора new с тремя параметрами (специализированная версия). А это для программы, исходный код которой занимает несколько мегабайт, согласитесь, достаточно трудоемкая задачка.

Конечно, не обязательно изменять код вручную. Во многих редакторах существует пофайловый search / replace. Кроме того в языке С++ , на котором написана эта библиотека, всегда можно определить макрос:

#define new new(__FILE__, __LINE__)

после подстановки которого любой код вида:

// Используется обычная версия оператора new
T * pT = new T; 

будет эквивалентен такому коду:

// Используется расширенная версия оператора new
T * pT = new(__FILE__, __LINE__) T; 

К сожалению, и этот трюк не работал корректно. Бездумная подстановка изменяла не только вызовы оператора new, но и места, где он был объявлен. Многие классы библиотеки содержали свои специализированные версии операторов new и delete:

class Object
{
public:
   ...
   void * operator new(const size_t nSize);
   void operator delete(void * pData);
   ...
}

Замена приводила к синтаксическим ошибкам.
 
Вот простая аналогия, взятая из данного источника: Соколов Г.Б., реплика на Форуме www.triz-ri.ru/forum со ссылкой на профессора мат. лингвистики Тузова:
 
"В русском языке можно:

  • разбить сквер,
  • разбить палатку, 
  • разбить вазу, 
  • разбить морду".

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

  • разрушить сквер, 
  • разрушить палатку, 
  • разрушить вазу, 
  • разрушить морду. 

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

А теперь представим себе объем текста размером с "Анну Каренину"…

Так и в нашей задаче. Объем исходного кода, который пришлось бы исследовать для локализации таких "особых мест" был очень велик, и работа по их выявлению рисковала стать чрезвычайно трудоемкой.

И как же быть? И даже не просто "как быть", а какую задачу решать?

Решать ли задачу о том, как передать оператору new дополнительные параметры, не понаделав ошибок? Или, все-таки, лучше думать о том, как иным способом (каким?) найти те некоторые вызовы оператора new (из множества возможных), которые и приводят к утечке.

А Вы как считаете?

Представим себе идеальный случай: в библиотеке присутствует только 1 (один!) вызов оператора new. В этом случае искать ничего не надо. Место, где происходит утечка, известно. Нужно только внимательнее взглянуть на код и разобраться в причинах.

Наша ситуация от идеальной отличается тем, что вызовов оператора new множество, и осуществляются эти вызовы  из разных функций (из разных мест, из разных контекстов). Мы не можем сказать, какой вызов породил утечку. Если бы вызовов было мало (в пределе – один), данная задача была бы моментально решена…

Имеем противоречие:

"Если бы вызовов оператора new было мало, то мы бы быстро нашли место, где происходит утечка (+), но тогда библиотека не обладала бы полной функциональностью (-)".

Или наоборот:

"Если бы вызовов оператора new было много, то мы бы не нашли место, где происходит утечка (-), однако библиотека обладала бы полной функциональностью (+)".

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


СРАЗУ ТРИ ЗАДАЧИ… ИЛИ ОДНА. (СЭКОНОМИТЬ ЗАДАЧИ)

А. Напишем рядом три краткие формулировки.

Формулировка Задачи 1:

"Если последовательность действий не дублировать, а поместить в тело цикла, то можно существенно сократить размер кода, но при этом утратится возможность выполнять последовательность каждый раз для уникальных данных".

"Если последовательность действий дублировать, то ее можно будет выполнять каждый раз для уникальных данных, но при этом размер кода значительно возрастет".

Или более компактно:

"Последовательность действий в программе должна всякий раз повторяться (для обработки разных уникальных данных) и не должна повторяться (чтобы не усложнять программу)".

Формулировка Задачи 2:

"При добавлении новой фигуры нужно добавлять 1 (один!) класс, чтобы не было трудоемко, и нужно добавлять три класса, чтобы поддержать рисование фигуры в окне и ее растеризацию в виде набора точек".

Или более компактно: 

"Классов в программе должно быть много (чтобы поддержать каждую обработку каждой уникальной фигуры) и должно быть мало (чтобы не усложнять программу)".

Формулировка Задачи 3: 

"Если бы вызовов оператора new было мало, то мы бы быстро нашли место, где происходит утечка (+), но тогда библиотека не обладала бы полной функциональностью (-)".

"Если бы вызовов оператора new было много, то мы бы не нашли место, где происходит утечка (-), однако библиотека обладала бы полной функциональностью (+)".

Или более компактно: 

"Вызовов оператора new в программе должно быть много (для выполнения каждой функции библиотеки) и должно быть мало (чтобы не усложнять поиск места утечки)".

Очевидно, что во всех 3-х случаях мы имеем дело с одной и той же типовой задачей, с одним и тем же типовым противоречием.

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

ТИПОВАЯ ЗАДАЧА 1. "ПРОТИВОРЕЧИЕ "МНОГО — МАЛО"

(это и есть фиксация на языке записи креативных задач)

Что нам такая фиксация дает?

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

И, кстати, дать пояснения нашему школьнику будет легче. Ведь (не усложняя понимания) ему можно будет показать (и даже нарисовать!) сразу группу задач, причина возникновения которых одна. Так будет и понятнее, и экономичнее.

А теперь займемся решением.

Для целей данной статьи сначала опишем решения, а затем принципы (приемы), с помощью которых они были найдены. В дальнейшем мы, большей частью, будем поступать наоборот: сначала писать прием, а потом решение.

Вот так: "Противоречие — Прием (Принцип) — Решение".


РЕШЕНИЕ ЗАДАЧИ 1

Все данные "упаковываем" в массив. На каждой итерации цикла последовательность действий обращается к "своим" данным по значению индексной переменной.

// Указатель на буфер с данными
char * pszBuff;
// Размер буфера
DWORD dwSize;
// Вспомогательные указатели
char * pszTemp = pszBuff;
char * p0;
// Массив искомых строк
const char * pszFind[3] =
{
   "/FullName",
   "/FamilyName",
   "/FontName"
};
// Массивы открывающих и закрывающих символов
const char * szIn = "((/";
const char * szOut = ")) ";
 
for (int i = 0; i
{
   // Ищем строку
   p0 = FindStr(pszTemp, dwSize, pszFind[i], strlen(pszFind[i]));
   // Ищем открывающий символ
   p0 = FindSymbol(p0, szIn[i]);
   p0++;
   // Ищем закрывающий символ
   char * pEnd = FindSymbol(p0, szOut[i]);
   // Сохраняем значение
   OutputValue(p0, pEnd – p0);
   // Вычитаем из общего размера разницу
   dwSize -= (pEnd - pszTemp);
   // Запоминаем указатель
   pszTemp = pEnd;

}
"Таким образом, "разные сущности" (здесь: данные) были собраны в контекстную группу (здесь: массив) и упорядочены. "Нечто Полезное" не повторяется, а вместо этого всякий раз обращается к "разным сущностям" по номеру". 

РЕШЕНИЕ ЗАДАЧИ 2

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

Т.е., вводим понятие "фигура в контексте". Так в нормальных магазинах продают не "раковины" и не "ванны", а сразу "шоу-рум" или т.н. "готовые решения", а уж в совсем нормальных анализируют чеки на предмет того, что с чем покупают, а затем выкладывают это на стеллажи сразу в виде "типовых корзин", да еще и скидку дают.

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

class CDeviceContext
{
public:
   virtual void MoveTo(const POINT & pt) = 0;
   virtual void LineTo(const POINT & pt) = 0;
};
 
classCWindowContext : public CDeviceContext
{
public:
   CWindowContext(HDC hDC);
 
   virtual void MoveTo(const POINT & pt);
   virtual void LineTo(const POINT & pt);
 
private:
   HDC m_hDC;
};
classCMemoryContext : public CDeviceContext
{
public:
   CMemoryContext();
 
   bool Contains(const POINT & pt) const;
 
   virtual void MoveTo(const POINT & pt);
   virtual void LineTo(const POINT & pt);
 
private:
   std::vector m_PolyLine;
};

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

class CBezier2
{
public:
   CBezier2(const POINT points[3]);
   void Draw(CDeviceContext & rDC);
private:
>   POINT m_points[3];
};
class CBezier3
{
public:
   CBezier3(const POINT points[4]);
   void Draw(CDeviceContext & rDC);
private:
   POINT m_points[4];
};

Таким образом, если Клиент попросит поддержать еще одну фигуру, в программу потребуется добавить лишь 1 (один!) класс. 

"Разные сущности" помещены в контексты (они входят в них, как составные части). Теперь в повторах необходимости нет. "Нечто Полезное" взаимодействует с контекстами (укрупненными единицами)".

Спрогнозируем развитие программы:

ШАГ 1. Предположим, количество различных кривых самого разного порядка начнет возрастать. Конечно, мы уже имеем решение (выше) "один класс — одна фигура", но при неограниченном количестве фигур — это будет не столь уж и экономно.

Хорошо бы иметь всегда только 1 класс (а не по классу на фигуру) и набор функций: DrawBezier2, DrawBezier3, …, DrawBezierN, и вызывать нужную функцию в зависимости от значения N. Для простоты все функции можно поместить в массив. 

// Определяет размер статического массива (в элементах)
 
#define __countof(ar) (sizeof(ar) / sizeof(ar[0]))
 
// Функции рисования кривых Безье 2-го, 3-го, 4-го и 5-го порядков
 
void DrawBezier2(CDeviceContext & rDC, const POINT * pPoints);
void DrawBezier3(CDeviceContext & rDC, const POINT * pPoints);
void DrawBezier4(CDeviceContext & rDC, const POINT * pPoints);
void DrawBezier5(CDeviceContext & rDC, const POINT * pPoints);
 
// Тип - указатель на функцию рисования кривой Безье
 
typedef void (* TBezierDrawer)(CDeviceContext &, const POINT *);
 
// Массив указателей на функции рисования кривых Безье
 
TBezierDrawer g_BezierDrawers[] =
{
   &DrawBezier2,
   &DrawBezier3,
   &DrawBezier4,
   &DrawBezier5
};
 
// Обобщенная кривая Безье
class CBezier
{
public:
   CBezier(const POINT * pPoints, const int iCount);
   ~CBezier();
 
   void Draw(CDeviceContext & rDC);
 
private:
   const int m_iCount;
   POINT * m_pPoints;
};
 
// Рисование обобщенной кривой Безье
void CBezier::Draw(CDeviceContext & rDC)
{
   // Для рисования кривой Безье 2-го порядка нужны 3 точки
   const int nIdx = m_iCount - 3;
   assert(nIdx >= 0 && nIdx < __countof(g_BezierDrawers));
 
   // Получаем указатель на функцию рисования из массива
   TBezierDrawer pfn = g_BezierDrawers[nIdx];
 
   // Вызываем функцию рисования
   (*pfn)(rDC, m_pPoints);
}

И тогда задача 2 сразу становится похожа на задачу 1.

"Разные сущности" (на этот раз функции) были собраны в группу и упорядочены. Таким образом, создан контекст. "Нечто Полезное" теперь  не повторяется, а вместо этого всякий раз обращается к "разным сущностям" по номеру". 

ШАГ 2.  Обострим задачу. Пусть перестанут повторяться не только классы, но и функции.

В идеале нужен 1 класс с универсальным алгоритмом, который может рисовать кривую Безье любого порядка CBezierN.

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

Условно говоря, в процессе свертывания кривых Безье мы проходим этапы:

Этап-0. По три класса для каждой кривой Безье. (Отсутствие свертывания).

Этап-1. Для каждой кривой Безье у нас свой класс: CBezier2, CBezier3, …, CBezierN. (Свертывание на уровне классов).

Этап-2. Для всех кривых Безье используется один класс CBezier, но в каждом конкретном случае вызывается особая функция рисования: DrawBezier2, DrawBezier3, …, DrawBezierN. (Свертывание на уровне данных).

Этап-3. Для представления всех кривых Безье используется один класс и одна функция рисования. (Свертывание на уровне данных и алгоритма).


РЕШЕНИЕ ЗАДАЧИ 3

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

НАПРИМЕР,

// Дробим основную функцию программы на контексты
 
void MainFunction()
{
   push("Context 1");
   DoSomething_1();
   pop();
 
   push("Context 2");
   DoSomething_2();
   pop();
   ...
 
   push("Context N");
   DoSomething_N();
   pop();
}
 
//Дробим дальше функции на подконтексты
 
void DoSomething_1()
{
   push("Action1");
   T * pT = new T();
   DoAction_1(pT);
   pop();
 
   push("Action 2");
   Other * pOther = new Other();
   Do_Action_2(pOther);
   pop();
}

Сами контексты мы объединяем в данном случае не в массив, а в стек и предоставляем функции push и pop для работы с ним. Функция push помещает новый контекст в вершину стека, а функция pop – наоборот, извлекает контекст из вершины стека, а на его место помещает другой контекст, который находился в стеке перед извлеченным. Используя эти процедуры, мы получаем возможность разбить любую процедуру на контексты, а любой контекст – на подконтексты и т.п.

// Размер стека
static const int MAX_CONTEXT = 100;
 
// Стек контекстов
static const char * g_ContextStack[MAX_CONTEXT];
 
// Количество контекстов в стеке
static int g_iContextCount = 0;
 
// Помещает контекст в стек
void push(const char * pszContext)
{
   assert(g_iContextCount < MAX_CONTEXT);
 
   // Помещаем контекст в вершину стека. Затем - увеличиваем количество элементов в стеке
   g_ContextStack[g_iContextCount++] = pszContext;
}
// Выталкивает контекст из стека
void pop()
{
   assert(g_iContextCount > 0);
   --g_iContextCount;
}
// Возвращает вершину стека (текущий контекст)
const char * CurrentContext()
{
   assert(g_iContextCount > 0 && g_iContextCount    return g_ContextStack[g_iContextCount - 1];
}

При выделении памяти оператор new заносит информацию о текущем контексте в служебную часть блока. Таким образом, если по завершении программы указанный блок не освобождается, мы получаем возможность определить, в каком контексте он был выделен.

struct TMemBlock
{
   unsigned long m_ulSize;
   const char * m_pszContext;
};
void * operator new(size_t nSize)
{
   if (nSize > 0)
   {
      void * pData = malloc(nSize + sizeof(TMemBlock));
      if (pData)
      {
// Преобразуем указатель pData к указателю на TMemBlock
 
         TMemBlock * pMemBlock = (TMemBlock *)pData;
         pMemBlock->m_ulSize = nSize + sizeof(TMemBlock);
         pMemBlock->m_pszContext = CurrentContext();
 
        Добавляем pMemBlock в список выделенных блоков;
 
        //Возвращаем указатель на часть памяти за pMemBlock
         return pMemBlock + 1;
      }
   }
   return NULL;
}
void operator delete(void * pData)
{
   if (pData)
   {
      // Получаем указатель на TMemBlock
 
      TMemBlock * pMemBlock = ((TMemBlock *)pData) - 1;
 
      Удаляем pMemBlock из списка выделенных блоков;
 
      // Освобождаем память
      free(pMemBlock);
   }

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

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

Таким образом, вместо того, чтобы оперировать "разными вызовами" можно оперировать более укрупненными сущностями "вызовы в контексте", которые и будут сообщать о себе. Несмотря на то, что количество вызовов операторов new в программе остается большим (в этом отличие от задач 1 и 2), для каждого контекста оно маленькое. А сами контексты упорядочены (сгруппированы в надконтекст; в данном случае, это стек). Теперь можно легко понять, в какой части программы (в каком контексте) был выделен не освобожденный блок. 

"Разные сущности" были помещены в контексты. А контексты, в свою очередь, собраны в группу и определенным образом упорядочены".


СОБЕРЕМ (СГРУППИРУЕМ) РЕШЕНИЯ. (СЭКОНОМИТЬ РЕШЕНИЯ).

Решение задачи 1: 

  • "Разные данные были собраны в массив, а повторяющиеся последовательности действий — заменены циклом. На каждой итерации цикла происходит обращение к нужным данным по соответствующему номеру".

    В общем виде:

  • "Разные сущности" были собраны в группу и упорядочены. "Нечто Полезное" не повторяется, а вместо этого всякий раз обращается к "разным сущностям" по номеру".

Решение задачи 2:

  • "Результаты растеризации помещены в контексты. Теперь в подклассах для фигур необходимости нет. Фигура рисуется в контексте, и результат рисования зависит от типа контекста".

    В общем виде:

  • "Разные сущности" помещены в контексты (они входят в них, как составные части). Теперь в повторах необходимости нет. "Нечто Полезное" взаимодействует с контекстами (укрупненными единицами)".

    На другом уровне:

  • "Функции рисования кривых Безье были помещены в массив. После этого появилась возможность создать обобщенный класс для кривой Безье любого порядка. Метод рисования такого класса обращается к нужной функции из массива в зависимости от количества узловых точек данной кривой Безье".

    В общем виде:

  • "Разные сущности" (на этот раз функции) были собраны в группу и упорядочены. Таким образом, создан контекст. "Нечто Полезное" теперь не повторяется, а вместо этого всякий раз обращается к "разным сущностям" по номеру".

Решение задачи 3:

  • "Вызовы оператора new были помещены в контексты. А контексты, в свою очередь, были помещены в стек".

    В общем виде:

  • "Разные сущности" были помещены в контексты. А контексты, в свою очередь, собраны в группу и упорядочены".

Понятно, что во всех 3-х случаях мы имеем один общий принцип, который надо бы формализовать. Прежде, чем это сделать, "на закуску" рассмотрим сквозной разбор еще одной задачи.


ЗАДАЧА 4. СЭКОНОМИТЬ ВАРИАНТЫ

Есть таблица, с большим количеством полей. И постоянно приходится делать выборку из этой таблицы, с большим количеством условий типа поле1 = значение1, поле2 <> значение2, и т.д.

При таком раскладе запросы становятся очень большими, дольше выполняются. Иногда, при сложных запросах, где объединяются несколько таких "больших подзапросов", база данных просто отказывается выполнять их, ссылаясь на слишком сложный запрос.

Вот реальный пример, когда пришлось столкнуться с такой задачей.

Для риэлтерской деятельности актуальна проблема быстрого поиска квартиры в базе данных. Другими словами, когда квартиры (в соответствие с точными пожеланиями Клиента) нет в наличии (или он не подрассчитал с ее стоимостью), нужно быстро найти замену. Но для того, чтобы что-то найти/выделить, нужно сравнить.

А любая квартира имеет 10-20 характеристик. Какие-то из них более значимы, какие-то менее. По одной (или по каждой) из них сравнение проводить возможно, но выборка получается очень грубой. Нужна именно многокритериальная выборка.

Например,

  • район,
  • престижность дома,
  • тип фонда,
  • близость транспорта,
  • этаж,
  • площади квартиры,
  • высота потолка,
  • материал дома,
  • телефон,
  • санузел,
  • отопление,
  • горячая вода,
  • балконы и лоджии,
  • пол,
  • состояние квартиры,
  • расположение квартиры в доме (угловая или нет),
  • ...и т.д.

Соответствующие SQL-запросы программистом были написаны, но время выполнения на 20 000 записях исчислялось десятками минут. Программист сказал, что быстрее невозможно и предложил купить новую машину.

Попробуем "прорваться к решению" этой задачи, используя в качестве аналогов формулы предыдущих решений.

ШАГ 1. Для того, чтобы "установить аналогию" сформулируем противоречие:

"Необходимо большое количество разных параметров в запросе, типа поле1 = значение1, поле2 <> значение2 для правильной выборки, и необходимо малое число параметров, чтобы не усложнять программу".

ШАГ 2.  Избавимся от обоснования:

"Необходимо большое количество разных параметров в запросе, и необходимо малое число параметров".

ШАГ 3.  Опишем формулу решения (пока по аналогии): 

"Все разные параметры должны быть сгруппированы в контексты (распределены по группам), которые и будут обрабатываться. Возможно, на множестве последних должно быть установлено отношение порядка (контексты должны быть сгруппированы в надконтекст)".

Иными словами, мы должны придумать, как группировать параметры и далее делать выборку групп.


РЕШЕНИЕ ЗАДАЧИ 4

Фактическое решение данной задачи описано ниже. Однако нам, конечно, будет интересна итоговая формула решения.

Все многообразие квартир в городе было разбито на 4 качественных уровня.

Имеется в виду, что квартира с определенным числом комнат делится на 4 уровня (однокомнатные — 1-го,  2-го,  3-го и 4-го уровня; двухкомнатные — 1-го,  2-го,   3-го и 4-го уровня, трехкомнатные — 1-го,   2-го,  3-го и 4-го уровня и т.д.), уровень может колебаться от 1 до 4..

Принадлежность квартиры к тому или иному качественному уровню определяется соответствием этому уровню ее характеристик (всех без исключения) с учетом веса (приоритета) каждой в определении уровня квартиры:

Устанавливаются уровни по специальным критериям качества.

Критерии уровней характеристик квартир

Каждому значению характеристики квартиры пользователь присваивает свой уровень. Например, в характеристике "Район":

Район Уровень района 
Центр  1
Район "X" 3
Район "Y" 4
Район "Z" 2
... и т.д. ... ... и т.д. ...
Район "N" 1

Аналогично, с другими характеристиками.

Например, для характеристики "Потолки" к 1-ому уровню относятся потолки, высота которых лежит в диапазоне от 3 метров и выше, ко второму – от 2.5 до 3 м. Третьего и четвертого уровня в данной характеристике нет, т.к. потолков ниже не бывает. (Оценка производится экспертом).

Значимость характеристик квартир.

Каждой характеристике квартиры выставляется свой приоритет, в зависимости от значимости этой характеристики.

Так, например, "Район", в определении уровня квартиры более весом, чем "Возможность установки телефона", а "Тип фонда" более значим, чем "Состояние квартиры" и т.д.  Есть характеристики, которые имеют более или менее одинаковый вес.
 
Для удобства пользователя (риэлтора) все характеристики разделены на четыре приоритетных уровня: 

«А» = 1 — очень высокая (во многом определяющая) значимость характеристики,
«B» = 2 — достаточно высокая значимость характеристики,
«C» = 3 — средняя значимость характеристики,
«D» = 4 — выгодно дополняющая характеристика.
 
(в данном случае, цифра обозначает приоритет)

Приоритеты для характеристик риэлтор расставляет самостоятельно, на основе опыта в риэлтерской деятельности.

Дальнейшая сортировка квартир на уровни произойдет в соответствии с выбранными приоритетами по формуле:

Уровень квартиры = Сумма характеристик по ij (Вес  i -ой характеристики х Число j-ой характеристики этого веса)/сумма характеристик

ПРИМЕР

Двухкомнатная квартира имеет 16 характеристик следующих уровней:

7 характеристик   – 1 уровня (А), приоритет = 1
4 характеристики – 2 уровня (B), приоритет = 2
2 характеристику – 3 уровня (C), приоритет = 3
3 характеристики – 4 уровня (D), приоритет = 4

Определим уровень квартиры:

Уровень = (7*1+4*2+2*3+3*4)/16 = 2,06

Таким образом, у нас появляется возможность сравнивать и сортировать квартиры (выстраивать рейтинги) с очень большим числом разнообразных "качественных" критериев.

Если теперь вернуться к базе данных, то произошло следующее:

  1. был введен соответствующий атрибут (поле)  "вес" и все квартиры, находящиеся в базе "приобрели" этот "вес" автоматически;
  2. при вводе каждой новой квартиры, "вес" для нее вычислялся автоматически (при заполнении формы);
  3. сложный запрос действительно превратился в запрос с одним условием "вес = N" (или диапазону).

Выборка на той же машине выполнялась практически мгновенно.

 

И что мы видим?

Формула решения задачи 4

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


СДЕЛАЕМ РЕЗЮМЕ. (СЭКОНОМИТЬ МЫШЛЕНИЕ).

Обещанная формализация. Конечно, многие Коллеги все это "и так знают" — нам это очевидно. Но, если, тем не менее, решая конкретную задачу, Вы столкнетесь с типовым противоречием: "Должно быть много и должно быть мало"

  • классов;
  • объектов;
  • параметров (например, в запросе);
  • элементов управления;
  • экранов;
  • таблиц;
  • строк;
  • измерений (в смысле осей...);
  • ...

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

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

В ТРИЗ такое преобразование называется "переход в надсистему". И в контексте настоящей статьи оно может показаться тривиальным. Однако — см. заголовок статьи. 

Надсистемные переходы

Конец 1 серии.

В следующих сериях Вы узнаете о том, что

а) существуют и иные приемы устранения противоречия "Много — мало"; а также о том, что
б) полный список типовых противоречий в программировании на сегодня состоит из 9-ти пунктов: 

  • "Много — мало"
  • "Нечто должно быть одно и должно быть другое"
  • "Раньше — позже"
  • "Встраивается — не встраивается"
  • "Стандартное — не стандартное"
  • "Функция выполняется — не выполняется"
  • "Точное — приближенное"
  • "Есть (должно быть) — Нет (не должно быть)"
  • "Большое — Маленькое"
  • "Быстрое — Медленное";

а также о том

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

А в завершении мы построим первую версию "Общего Справочника Решения Креативных Задач".

Примечание.
Разбор задач (приведенных в данной статье) иным способом - см. в разделе "TStupid или "Новейший органон".

СПИСОК ЛИТЕРАТУРЫ:

  • Альтшуллер Г.С.  Творчество как точная наука. — 2-е изд., доп. — Петрозаводск: Скандинавия, 2004.
  • Сайт Официального Фонда Г.С.  Альтшуллера www.altshuller.ru
  • Электронная книга "Введение в ТРИЗ. Основные понятия и подходы"  www.altshuller.ru/e-books
  • Э. Мах "Экономия науки" www.triz-ri.ru/management/?id=446
  • С.В. Сычев, К.А. Лебедев "Освобождение узников оператора "IF" www.triz-ri.ru/management/?id=303
  • С.В. Сычев, К.А. Лебедев "О потерянном уровне" www.triz-ri.ru/management/?id=279
  • С.В. Сычев, К.А. Лебедев "Что увидишь, то и неси" (TStupid) www.triz-ri.ru/management/?id=369
  • С.В. Сычев, К.А. Лебедев "Неважно, где рисовать" (TStupid) www.triz-ri.ru/management/?id=364
  • С.В. Сычев, К.А. Лебедев "Пусть само проявится" (TStupid) www.triz-ri.ru/management/?id=331
  • Г. Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на C++, 2-е изд./Пер с англ. – М.: "Издательство Бином", СПб: "Невский диалект", 1998 г.
  • Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб: Питер, 2001. — 368 с.: ил.
  • Петер Коуд, Дэвид Норт, Марк Мейфилд. Объектные модели. Стратегии, шаблоны и приложения. — М.: Издательство "ЛОРИ", 1999. — 434 с.: ил.
  • Мартин Фаулер. Рефакторинг: улучшение существующего кода. — Пер. с англ. - СПб: Символ-Плюс, 2003. — 432 с.: ил.
  • Алан Шаллоуей, Джеймс Р. Тротт. Шаблоны проектирования. Новый подход к объектно-ориентированному анализу и проектированию: Пер. с англ. — М.: Издательский дом "Вильямс", 2002. — 288 с.: ил. 

Авторы благодарят С.Г. Меняйленко, А.Б. Кавтреву, Г.Б. Соколова за помощь в работе над данным материалом.

Материал опубликован на сайте "Открытые методики рекламы и PR "Рекламное Измерение" 20 мая 2005 г.

aaaadddaaaa