Занимательная задачка: понимание deep copy

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Такую задачу я даю на собеседовании.

В некой программе долгое время "жил" следующий код:

Код: Выделить всё

#include <huge.h>

class CWorker
{
public:
   void Process()
   {
      m_huge.DoAction();
   }
      
private:
   CHuge m_huge;
};

void main()
{
   CWorker worker1;
   if (<SomeCondition1>)
   {
      worker1.Process();
   }

   CWorker worker2;
   if (<SomeCondition2>)
   {
      worker2 = worker1;
   }

   if (<SomeCondition3>)
   {
      worker1.Process();      
      worker2.Process();
   }
}
Класс CHuge является сторонним классом. Его особенность в том, что в момент создания объекта этого класса выполняется много "тяжёлых" действий, а именно: выделяется много памяти, производятся продолжительные расчёты. Так же он обладает всем необходимым набором конструкторов и операторов для того, чтобы указанный выше код функционировал правильно. Дополнительно следует знать, что вызов метода DoAction сохраняет результаты своей работы во внутренние переменные, так что каждый последующий вызов этого метода будет работать иначе, чем предыдущие вызовы.

Долгое время всех устраивало состояние кода. Но пришёл тот день, когда грамотный автотестер покрыл все возможные варианты тестами и доложил руководству проектом, что даже когда все три условия в коде ложны, программа всё равно долго "висит", выполняя ненужные действия.

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

Код: Выделить всё

#include <huge.h>

class CWorker
{
public:
   CWorker() : m_pHuge(nullptr)
   {
   }

   ~CWorker()
   {
      delete m_pHuge;
   }
 
   void Process()
   {
      if (nullptr == m_pHuge)
      {
         m_pHuge = new CHuge();
      }
      m_pHuge->DoAction();
   }
      
private:
   CHuge* m_pHuge;
};
Такие изменения были более, чем обоснованы, так как, благодаря им, инициализация экземпляра CHuge была отложена до первого вызова Process, то есть, иными словами, до того, момента, когда экземпляр на самом деле понадобится. Если Process не вызовется ни разу, то у нас получится избежать выполнения длительных операций, которые производятся при инициализации CHuge.

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

Вопросы:
1. Почему произошёл краш?
2. Как исправить краш, но при этом добиться необходимой оптимизации?

Напоминаю, что править мы можем только код класса CWorker, так как класс CHuge является сторонним, а функция main находится не в нашей юрисдикции и мы обязаны сохранить ожидаемое поведение нашего класса для людей, которые эту функцию пишут.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

1. Попытка двойного освобождения экземпляра CHuge по одному и тому же адресу в worker1.m_pHuge с и в worker2.m_pHuge.
2. Можно написать свой оператор присваивания, краха не будет. Сколько времени занимает копирующее присваивание CHuge? Если много, то такое решение приведёт к пессимизации для случая, когда истинны и <SomeCondition1>, и <SomeCondition2>.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Сионист писал(а):Сколько времени занимает копирующее присваивание CHuge?
А этот вопрос важен? Если внимательно посмотреть на код и на условия, то выход у нас лишь один.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

Romeo писал(а):Если внимательно посмотреть на код и на условия, то выход у нас лишь один.
Считаем:
1.

Код: Выделить всё

class CWorker
{
public:
   ~CWorker()
   {
      delete m_pHuge;
   }
   CWorker & operator = (const CWorker &Original)
   {
    if (Original.m_pHuge)
    {
     if (m_pHuge==nullptr)
     {
      m_pHuger=new CHuge;
     }
     *m_pHuger=*Original.m_pHuge;
    }
    else
    {
     if (m_pHuge==nullptr)
     {
      delete m_pHuge;
      m_pHuge=nullptr;
     }
     return *this;
    }
 
   void Process()
   {
      if (nullptr == m_pHuge)
      {
         m_pHuge = new CHuge();
      }
      m_huge->DoAction();
   }
     
private:
   CHuge* m_pHuge;
};
CHuge* m_pHuge
.
2.

Код: Выделить всё

class CWorker
{
public:
   CWorker() : m_pHuge(nullptr)
   {
   }

   ~CWorker()
   {
      delete m_pHuge;
   }
    
   void Process()
   {
      if (nullptr == m_pHuge)
      {
         m_pHuge = new CHuge();
      }
      m_huge->DoAction();
   }
     
private:
   static CHuge* CWorker::m_pHuge;
};
.
И это только на вскидку. И вообще, вся земная цивилизация до сих пор не придумала ИТ-задачу, которая бы имела ровно одно возможное решение. Так что не надо мнить себя излишне гениальным.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Пфф, даже не задело на счёт того, что я считаю себя гениальным. Никогда не считал. И, кстати, всем условиям, а так же здравому смыслу удовлетворяет действительно лишь одно решение. Сейчас поймёшь почему.

Первое решение у тебя идёт в правильном направлении, но оператор заимплеменчен неверно, его следует исправить, а так же доработать. Ко всему прочему у тебя ещё кое-чего не хватает помимо оператора присваивания.

Во втором решении у тебя будет краш. Сможешь объяснить почему? Это даже без обсуждения того факта, что делая экземпляр CHuge статическим ты ломаешь изначальное поведение класса CWorker, ведь раньше каждый экземпляр CWorker мог иметь экземпляр CHuge в своём собственном состоянии, а после переделки у них у всех состояние будет одним. Как следствие, часть тестов, которые написал умный автотестер разломаются. Таким образом, второе решение не подходит и... о чудо... остаётся одно единственное. Неужели это свидетельствует о моей гениальности? Чёрт побери, я действительно гений, видимо!
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Сионист
Сообщения: 1211
Зарегистрирован: 31 мар 2014, 06:18

Во втором решении у тебя будет краш. Сможешь объяснить почему? Это даже без обсуждения того факта, что делая экземпляр CHuge статическим ты ломаешь изначальное поведение класса CWorker, ведь раньше каждый экземпляр CWorker мог иметь экземпляр CHuge в своём собственном состоянии, а после переделки у них у всех состояние будет одним. Как следствие, часть тестов, которые написал умный автотестер разломаются.
1. После

Код: Выделить всё

class CWorker
{
public:
   CWorker() : m_pHuge(nullptr)
   {
   }

   ~CWorker()
   {
      delete m_pHuge;
   }
 
   void Process()
   {
      if (nullptr == m_pHuge)
      {
         m_pHuge = new CHuge();
      }
      m_huge->DoAction();
   }
     
private:
   CHuge* m_pHuge;
};
все экземпляры CWorker уже имеют общий экземпляр CHuge.
2. Ни где не было сказано, что сам CHuge не является оболочкой над ещё одним статиком.
Таким образом, второе решение не подходит и... о чудо... остаётся одно единственное. Неужели это свидетельствует о моей гениальности? Чёрт побери, я действительно гений, видимо!
Остаётся ещё как минимум обратная разработка CHuge. А также куча эквивалентной всячины и много решений разной паршивости вплоть до варианта "оставить старый код и накрутить частоту". Вот оптимальное решение действительно бывает одно, да и то не всегда.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Сионист писал(а):все экземпляры CWorker уже имеют общий экземпляр CHuge
Неверно. В варианте начинающего программиста, все имеют свой экземпляр. С чего ты взял, что он общий?

Кстати, изначально начинающий программист пошёл по правильному пути. Он отложил создание экземпляра CHuge до момента, когда он действительно будет необходим. Вот только о других вещах он не подумал.
Сионист писал(а):Ни где не было сказано, что сам CHuge не является оболочкой над ещё одним статиком.
Не важно, как представлен внутри CHuge. Мы вообще не имеем права делать никаких предположений о его внутреннем устройстве. Это black box. Мы знаем о нём только то, что сказано в задании. А там, кстати, есть вот такие строки:
Romeo писал(а): Дополнительно следует знать, что вызов метода DoAction сохраняет результаты своей работы во внутренние переменные, так что каждый последующий вызов этого метода будет работать иначе, чем предыдущие вызовы.
Мне кажется, что это уже отметает предположение о том, что класс обёртывает статическую имплементацию, а так же автоматически заставляет нас сохранять состояние объекта при копировании. Хотя, напоминаю ещё раз, никаких предположений о его внутреннем устройстве мы просто не имеем право делать. Мы просто должны сохранить старое поведение CWorker и все его состояния, лишь добавив оптимизацию.
Сионист писал(а): Остаётся ещё как минимум обратная разработка CHuge. А также куча эквивалентной всячины и много решений разной паршивости вплоть до варианта "оставить старый код и накрутить частоту". Вот оптимальное решение действительно бывает одно, да и то не всегда.
Reverse engineering здесь точно излишен. Ведь изначальный вариант CWorker работал без всяких дополнительных знаний о CHuge, значит у нас уже есть всё, что требуется. Ты пытаешься усложнять сущность без надобности.

На самом деле эта задачка не только на понимание deep copy (как указано в заголовке), но и на логику и на архитектурное чутьё. На ней получается очень хорошо понять насколько программист умеет правильно мыслить. Я часто прошу мыслить вслух, когда собеседуемый решает эту задачу. Просто великолепная задачка. Она, кстати, не моя - лавры присваивать не собираюсь. Её любил давать на собеседованиях мой напарник на прошлом месте работы. Я её лишь полностью формализовал.

Ты, кстати, так и не указал причину краша в твоём втором решении :) Разобрался почему он будет?
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

А вот этой редакции я не понял:
Последний раз редактировалось Сионист; Сегодня в 12:05.
Сионист писал(а):

Код: Выделить всё

static CHuge* CWorker::m_pHuge]
[/quote]
Что ты этим синтаксисом хотел сказать? Пробовал хоть скомпилить такое? До правки у тебя эта строка правильно была, вроде как...

Ещё вижу правку - добавил константность во входной параметр оператора. Хвалю. Но это была лишь косметическая ошибка. В операторе ещё есть логическая ошибка, а так же он не доведён до ума. И по прежнему не хватает ещё одной сущности, помимо оператора.

Кстати, если хочешь проверить компилябельность и правильность работы, достаточно вместо
[code=cpp]
#include <huge.h>
написать

Код: Выделить всё

class CHuge
{
public:
   void DoAction(){}
};
И вместо кондишенов поставить true или false.

Краши уж точно так отловить можно будет.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Romeo
Сообщения: 3126
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Господа, большие свои силы никто не хочет попробовать? Где Оксалайушка?
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Duncon
Сообщения: 2085
Зарегистрирован: 10 окт 2004, 14:11
Откуда: Питер
Контактная информация:

Нет, напряга для мозга каждый день хватает чтоб ещё тут вникать. Собеседования на заграничный манер считаю глупостью, достаточно посмотреть на код нанимаемого.. Человек может волноваться на собеседовании или наоборот с лёгкостью решить задачку как ты этого хочешь (задачки в принципе одни и те же, конторы друг у друга тырят (ты тож не оригинален : ), другие делятся о чём спрашивают в сети, некоторые просто готовы). По факту кандидат оказывается бездельником, точнее сегодня необязательность в моде, нанимаешь такого "про", а следом приходиться высаживать выходные и праздники из-за того, что работа так и не сделана или сделана через крыльцо, или просажены сроки и прибегает менеджер с мольбами спасти его горящий пердак. В общем я люблю на практике смотреть на человека, и с задач попроще, пока не буду в нём уверен, другой вопрос не всегда есть такая возможность, зачастую нужно делать дело сразу..
[syntax=Delphi] [/syntax]
Ответить