Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Общие вопросы по .NET и C# > Performance рекурсивной функции


Автор: SCAR 23.6.2013, 22:06
Доброго времени суток!

Добавил в программу следующую рекурсивную функцию:

Код

        private static void signFiller(SignModel mdl, int pathIndex)
        {
            int pathCount = SegX.Instance.getPathListCount() - 1;
            if (pathIndex > pathCount) return;

            ArrayList pthModels = SegX.Instance.getAllModelsForPath(pathIndex);

            SignModel initialMdl = (SignModel)mdl.Clone();

            for (int i = 0; i < pthModels.Count; i++) //Все подпути для данного пути
            {
                //Добавить модель пути в модель знака
                initialMdl.addPathModel((PathModel)pthModels[i]);

                if (pathIndex < pathCount)
                {
                    signFiller(initialMdl, pathIndex + 1); 
                }
                //Следующая модель

                SegX.Instance.addSignModel(initialMdl);
                initialMdl = (SignModel)mdl.Clone();
                modelsCount++;

                Logger.Instance.addLogRecord("SignModels count: " + modelsCount);
            }
        }


Но данная функция работает очень медленно (около 100 итераций в секунду), а с увеличением количества итераций скорость работы замедляется еще раз в 10... Функция Clone() описана ниже: 

Код

        public object Clone()
        {
            SignModel newSignModel = (SignModel)this.MemberwiseClone();
            newSignModel.addPathModelList(new Dictionary<int, PathModel>(this.getPathModelsDict()));
            newSignModel.addAnglesList(new Dictionary<int, Angle>(this.getAnglesDict()));
            return newSignModel;
        }



Подскажите пожалуйста, как ускорить данную процедуру? Я в C# не настолько спец smile

Автор: uwannadie 25.6.2013, 02:39
Для начала попробуй определить, какая часть рекурсивной функции выполняется дольше всего.
Плюс выключи логирование и проверь разницу во времени.

Автор: IBS 25.6.2013, 21:44
я бы рекомендовал почитать про развертку рекурсии с помощью стека.
Кстати, таким образом реализовать отложенный возврат элементов (нравится он мне smile)

Автор: SCAR 26.6.2013, 00:48
Большое спасибо! Очень интересная идея про стек. А не подскажите, где почитать можно? В С++ с такими проблемами не сталкивался, а тут... 

Автор: IBS 26.6.2013, 17:46
Тут ребята развели прикольный холивар на эту тему:
http://otvety.google.ru/otvety/thread?tid=4ef8214f3d124669

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

Автор: SCAR 27.6.2013, 15:21
Интересная информация, спасибо! Жаль, что большого прироста производительности данный подход не дает, но все же полезен для оптимизации.

Автор: SCAR 14.7.2013, 20:06
Как оказалось, слабое место - функция Copy(), особенно это место:

Код

SignModel newSignModel = (SignModel)this.MemberwiseClone();


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

Автор: SCAR 14.7.2013, 21:30
Нашел интересную информацию по данной теме:

http://stackoverflow.com/questions/966451/fastest-way-to-do-shallow-copy-in-c-sharp
http://whizzodev.blogspot.com/2008/03/object-cloning-using-il-in-c.html
Реализовал IL клонирование, как указано в примере. Но только вот, клона эта штука не создает, а создает объект который ссылается на ту же ячейку памяти, ну со всеми выходящими. Меняешь один объект, меняется и второй... Возможно имеет смысл сделать ILCloner рекурсивным, для глубокого копирования?

Автор: SCAR 23.7.2013, 09:36
Всем привет, 

Я опять с тем же вопросом. Ускорил данную функцию, как только мог, вот наиболее быстрый вариант: 

Код

        private static void signFiller(SignModel mdl, int pathIndex)
        {

            int pathCount = SegX.Instance.getPathListCount() - 1;
            if (pathIndex > pathCount) return;

            ArrayList pthModels = SegX.Instance.getAllModelsForPath(pathIndex);
            
            int pthCnt = pthModels.Count;

            for (int i = 0; i < pthCnt; i++) //Для каждой из моделей строим модель знака, сопоставляя ее с моделями других путей
            {
                //Добавить модель пути в модель знака
                initialMdl.addPathModel((PathModel)pthModels[i]);

                if (pathIndex < pathCount)
                {
                    signFiller(initialMdl, pathIndex + 1); 
                }
                //Следующая модель

                SegX.Instance.addSignModel(initialMdl);

                initialMdl = (SignModel)mdl.Clone();

                modelsCount++;
            }
        }


        public object Clone()
        {

            // High speed
            SignModel result = new SignModel();
            result._pathModels = new Dictionary<int, PathModel>(this._pathModels); //ILCloner.Clone<Dictionary<int, PathModel>>(this._pathModels); //
            result._angles = new Dictionary<int, Angle>(this._angles); //ILCloner.Clone<Dictionary<int, Angle>>(this._angles);

            return result;
        }



В качестве функции клонирования перепробовал все варианты, которые нашел в интернете, к примеру: Deep IL Cloning, Reflection cloning, MemberwiseClone, BinnaryFormatter (с использованием MemoryStream и Serialize). Кстати, последний способ - наиболее медленный.
Но проблема так и не исчезла, первые 25000 моделей формируются очень быстро (меньше секунды), но дальше - хуже. С каждой новой итерацией скорость работы существенно замедляется и когда кол-во моделей достигает отметки в пол миллиона, то скорость формирования моделей становится около 50 шт./сек. 
Размер объектов SignModel всегда примерно один и тот же, т.е. это  не может происходить из-за увеличения размера клонируемых данных. 
Подскажите пожалуйста, на что стоит обратить внимание? 

Автор: mihryak 23.7.2013, 14:21
на профайлер.
нельзя заниматься оптимизацией без профилирования - велик шанс, что не только кучу времени потрачено будет на вылизывание некритичного куска, но и код ощутимо испортится после ненужной оптимизации.

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

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

Автор: SCAR 23.7.2013, 20:58
Большое спасибо за совет!

Профайлер указал на процедуру SegX.Instance.addSignModel(initialMdl);

Она выглядит следующим образом:

Код

        public void addSignModel(SignModel model)  //Добавляет модель знака в список
        {
            if(signModels.IndexOf(model) < 0)
                signModels.Add(model);
        } 


Затык на ArrayList.IndexOf, подскажите пожалуйста, какие есть альтернативы? Чем можно заменить использование IndexOf? 
Я читал про BinarySearch, но он требует сортировки списка, а я не думаю, что сортировка будет быстрее.

Лог профайлера:

http://s1.ipicture.ru/uploads/20130723/CchKD6Ap.bmp

Автор: SCAR 23.7.2013, 21:22
Заменил ArrayList на Dictionary<long, SignModel>, стало работать очень быстро, но случилась другая проблема  smile 
Когда создается 5999472 модели, то Dictionary выплевывает System.OutOfMemoryException )) 
Как можно добавить ему памяти, чтоб можно было разместить больше объектов?

Автор: mihryak 23.7.2013, 21:50
5999472 объектов в памяти - безумно много
надо смотреть в сторону базы данных, мне кажется, это неизбежно

Автор: SCAR 23.7.2013, 22:04
Согласен, что много, но надо больше. А даст ли база такой перформанс? И не могли бы вы посоветовать, в сторону чего смотреть? 
Была глупая идея, сделать несколько контейнеров и обертку, которая бы переключалась между ними smile
Кстати, может стоит посмотреть в сторону HeshSet? Говорят он может хранить почти 90 млн. записей. Но не уверен, что мне хватит smile

И почему я не начал писать это приложение на C++?!   smile 

Автор: SCAR 23.7.2013, 22:55
Взвесил все "за" и "против", решил пока не смотреть на базу, а сделать фильтрацию моделей "на лету". Перед добавлением в словарь буду проверять на соответствие определенным критериям и если по ним модель не подходит, то добавлять ее не буду. Хотя планировал сделать данную фильтрацию после добавления всех моделей. Надеюсь в этом случае все поместится smile

А не подскажите, есть ли в C# какой-нить аналог std::remove_copy_if (С++) для generic контейнеров? 

Автор: mihryak 24.7.2013, 11:43
Цитата(SCAR @  23.7.2013,  23:55 Найти цитируемый пост)
А не подскажите, есть ли в C# какой-нить аналог std::remove_copy_if (С++) для generic контейнеров?  

у List<T> есть RemoveAll, принимающий предикат, также есть Linq-расширение All, тоже с предикатом
но лучше и правда ещё перед добавлением постараться понять, что добавлять не стоит, чем просеивать после добавления

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

контроль над коллекциями позволит сократить требуемую память, но не особо значительно - элементы коллекции "про запас" сами по себе будут занимать только размер ссылки на будущий контент (4 байта, поправьте, если не прав)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)