Здравствуйте, hattab, Вы писали:
H>Здравствуйте, Феоктистов Александр, Вы писали:
ФА>> да fastmm не хватает в fpc...
H>Странно, почему не используют, open source же
Потому что его нереально сделать кроссплатформенным. Потеря скорости, все из-за кроссплатформенности и ваш тест неадекватный, более 10 млн строк fpc не в состоянии быстро выделить. Поэтому такие тормоза, не знаю, в моем проекте, когда все в комплексе разница не такая уж большая.
Здравствуйте, dim-s, Вы писали:
d> ФА>> да fastmm не хватает в fpc...
d> H>Странно, почему не используют, open source же
d> Потому что его нереально сделать кроссплатформенным. Потеря скорости, все из-за кроссплатформенности
Почему они не могут использовать FastMM, когда проект собирается для x86 (коли) Других то привязок, кроме ассемблера, там нет.
d> и ваш тест неадекватный, более 10 млн строк fpc не в состоянии быстро выделить. Поэтому такие тормоза, не знаю, в моем проекте, когда все в комплексе разница не такая уж большая.
Дело тут не в адекватности теста (а бенчи они никогда адекватными не бывают), а в том, что менеджер памяти FPC сливает со свистом на сценариях требующих частой аллокации и переаллокации (кстати, строки там выделять не требуется т.к. пустая строка это nil, и там по сути происходит хранение пустых указателей, с вызовом соответствующих функций выполняющих присваивание строк). И такие сценарии отнюдь не редкость. Хорошо. Заменим TStringArray на TPtrArray в этом тесте.
Uses
sysutils, ori_FastArrays;
Var
i : Integer;
sa : TPtrArray;
begin
sa := TPtrArray.Create;
WriteLn(DatetimeToStr(Now));
for i := 1 to 100000000 do
sa.Add(nil);
WriteLn(DatetimeToStr(Now));
Delphi 2010 — 1 сек. FPC 2.5.1 — я снова не дождался
Здравствуйте, gandjustas, Вы писали:
G>STL как раз упрощает C++: по-максимуму прячет указатели, реализацию строк и работу с динамической памятью. Это как раз те аспекты С++, которые делают его переусложненным.
Разве прячет динамическую память? Я бы так не сказал. Можно свои аллокаторы определять.
Итераторы вместо указателей тоже не совсем безопасно, можно легко аналогичные проблемы поиметь.
Имхо, основное удобство STL — разделение алгоритмов и контейнеров, предикаты, функциональные объекты.
Легкость описания сложных алгоритмов обработки данных в сочетании с широким полем деятельности для оптимизатора, после раскрытия шаблонов.
HA>Разве прячет динамическую память? Я бы так не сказал. Можно свои аллокаторы определять.
Прячет, аллокаторы определять по умолчанию не нужно.
И между просто объявлением std::vaector<..> и плясками с new/delete разница огромная, не говоря уже
о resize и push_back
HA>Итераторы вместо указателей тоже не совсем безопасно, можно легко аналогичные проблемы поиметь.
Это да, дань эффективности. Тут Степанов сделал ошибку, хотя если учесть когда это разрабатывалось то простительную.
Здравствуйте, Head Ache, Вы писали:
HA>Здравствуйте, gandjustas, Вы писали:
G>>STL как раз упрощает C++: по-максимуму прячет указатели, реализацию строк и работу с динамической памятью. Это как раз те аспекты С++, которые делают его переусложненным.
HA>Разве прячет динамическую память? Я бы так не сказал. Можно свои аллокаторы определять.
Тем не менее с использованием STL писать new, а тем более delete, приходится в разы меньше.
HA>Итераторы вместо указателей тоже не совсем безопасно, можно легко аналогичные проблемы поиметь.
Это если итератор по вектору, то да. А по другим контейнерами — нет.
HA>Имхо, основное удобство STL — разделение алгоритмов и контейнеров, предикаты, функциональные объекты. HA>Легкость описания сложных алгоритмов обработки данных в сочетании с широким полем деятельности для оптимизатора, после раскрытия шаблонов.
Не спорю. Я говорю не о сути, а о влиянии на язык\программы.
Здравствуйте, Ночной Смотрящий, Вы писали:
I>>Joshua Kerievsky
НС>Нет, ты определение давай. Или предлагаешь мне все сочинения этого автора перечитать?
У него есть книга, рефакторинг с использованием паттернов. Вот туда и смотри. Ссылок на эту книгу у меня нет.
Здравствуйте, vdimas, Вы писали:
I>>Т.е. это нечто, что выглядит как функция, но ею не является и по этой причине вводит в заблуждение + затрудняет понимание — это как раз про СТЛ и БУСТ.
V>Что значит "ею не является"? В STL и boost во всех местах, где можно подать как параметр обычную ф-ию, можно подать и функтор (функциональный объект в терминах С++).
Это и значит, что не является — два разных типа с разными возможностями. Реально даже три — указатели на методы та еще дрянь. В итоге надо постоянно приседать вокруг этого, особенно если пишешь какое то расширение.
V>И поясни, плиз, что именно вводит в заблуждение, и в чем состоит само заблуждение?
см выше
V>-------------------------- V>Я было хотел начать пояснять прямо тут, но гугл по фразе "функтор С++" вываливает более доходчивую инфу.
Что такое функтор я знал задолго до того, как ты на этом сайте зарегился.
Здравствуйте, gandjustas, Вы писали:
I>>В задаче нужно найти покрытие для которого функция минимальна I>>Очевидно — задача слишком сложная, что бы мерять её ради форумной баталии. Потому я предложил тебе упрощенный случай — только первую фазу, поиск всех маршрутов. G>Ну я даже не удивлен что ты снова поменял условия задачи.
Я ничего не менял
I>>Код я скипнул, потому что ты поторопился с решением. В этой функции нельзя заранее отсекать варианты Потому еще раз — лучше ограничиться только поиском всех маршрутов — первая фаза. G>Это как раз прекрасно делает ленивый вариант обхода.
Делает. И заметь — универсальность сама собой куда то пропала потому что возвращается IEnumerable<IEnumerable<T>>, а ленивость ни одного преимущества не дает. Ленивость нужна когда с большой вероятностью не нужен полный перебор. В задаче, которую я тебе показал, ленивые переборы себя _не_ _оправдали_.
G>Ты не привел ни одного обоснования своим словам, ни про размер кода, ни про быстродействие, ни про визиторы, постоянно пытаешься увильнуть.
С перформансом все достаточно просто — императивная версия оптимизирована под _массив_, по скорости она чуток уступает С++. Именно те рекурсивные, что я приводил, не тестировались, но Linq-оверхед будет медленеее чистой рекурсии это ты сам знаешь. Тест для JS V8 в принципе можно оформить, но на это пока нет времени, т.к. для теста надо поработать
Про визиторы уже вроде все сказано. Размер кода сам сравнить можешь. При одинаковом кол.ве строк твой код больше чем в двое шире из за дурацкого синтаксиса
function AllRoutes(root, createRoute){
var route = new List();
var routes = new List();
(function (v){
route.Push(v);
routes.Push(createRoute(route));
if(!route.Contains(v))
for(x in v.Connections)
arguments.callee(x);
route.Pop();
})(root);
return routes;
}
G>Кстати с чего все началось: для обхода графов вполне достаточно Linq и комбинаторов.
Linq можно использовать, только надо ли, если код превращается непойми во что да еще становится длиннее ажно вдвое ? И при этом ни универсальности ни быстродействия даже MemoizeAll не спасает
Здравствуйте, hattab, Вы писали:
H>Я как то тестировал на своих задачах — ~30%. С вариантами вообще 40%. Можешь сам проверить:
... H>Delphi 2010 — 9 сек. FPC 2.5.1 — 15 сек.
Вероятно, цифры ты взял с потолка, т.к. у тебя 66% а не 40
Здравствуйте, gandjustas, Вы писали:
HA>>Разве прячет динамическую память? Я бы так не сказал. Можно свои аллокаторы определять. G>Тем не менее с использованием STL писать new, а тем более delete, приходится в разы меньше.
Это как бы так, зато гораздо сложнее становится узнать, когда же надо писать new/delete и конструкторы всякие, а когда нет.
Здравствуйте, Ikemefula, Вы писали:
I> H>Я как то тестировал на своих задачах — ~30%. С вариантами вообще 40%. Можешь сам проверить:
I> ...
I> H>Delphi 2010 — 9 сек. FPC 2.5.1 — 15 сек.
I> Вероятно, цифры ты взял с потолка, т.к. у тебя 66% а не 40
Здравствуйте, Ikemefula, Вы писали:
G>>Тем не менее с использованием STL писать new, а тем более delete, приходится в разы меньше.
I>Это как бы так, зато гораздо сложнее становится узнать, когда же надо писать new/delete и конструкторы всякие, а когда нет.
Не становится, правило очень простое, new писать только в конструкторах умных указателей, delete в прикладном коде не использовать никогда.
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
I>>>В задаче нужно найти покрытие для которого функция минимальна I>>>Очевидно — задача слишком сложная, что бы мерять её ради форумной баталии. Потому я предложил тебе упрощенный случай — только первую фазу, поиск всех маршрутов. G>>Ну я даже не удивлен что ты снова поменял условия задачи. I>Я ничего не менял
Ага, ты не сообщал все условия, это по сути то же самое.
I>>>Код я скипнул, потому что ты поторопился с решением. В этой функции нельзя заранее отсекать варианты Потому еще раз — лучше ограничиться только поиском всех маршрутов — первая фаза. G>>Это как раз прекрасно делает ленивый вариант обхода.
I>И заметь — универсальность сама собой куда то пропала потому что возвращается IEnumerable<IEnumerable<T>>, а ленивость ни одного преимущества не дает.
не понял фразы. Ты можешь придумать более универсальный интерфейс чтобы вернуть все маршруты на графе?
I>Ленивость нужна когда с большой вероятностью не нужен полный перебор. В задаче, которую я тебе показал, ленивые переборы себя _не_ _оправдали_.
Ты скрыл важные детали до того как я показал код. Теперь не строй из себя самого умного.
G>>Ты не привел ни одного обоснования своим словам, ни про размер кода, ни про быстродействие, ни про визиторы, постоянно пытаешься увильнуть. I>С перформансом все достаточно просто — императивная версия оптимизирована под _массив_, по скорости она чуток уступает С++. Именно те рекурсивные, что я приводил, не тестировались, но Linq-оверхед будет медленеее чистой рекурсии это ты сам знаешь. Тест для JS V8 в принципе можно оформить, но на это пока нет времени, т.к. для теста надо поработать
Ты как-то забыл что мой код с небольшими усилиями можно распараллелить. Каких усилий будет стоить сделать то же самое на C++ или на JS?
Вообще сейчас любой переборной алгоритм надо параллелить.
I>Про визиторы уже вроде все сказано. Размер кода сам сравнить можешь. При одинаковом кол.ве строк твой код больше чем в двое шире из за дурацкого синтаксиса I>
I>function AllRoutes(root, createRoute){
I> var route = new List();
I> var routes = new List();
I> (function (v){
I> route.Push(v);
I> routes.Push(createRoute(route));
I> if(!route.Contains(v))
I> for(x in v.Connections)
I> arguments.callee(x);
I> route.Pop();
I> })(root);
I> return routes;
I>}
I>
Ты как-то опять обошел вниманием что мой код:
1)Довольно легко распараллелить
2)Обобщенный
Добейся в коде выше тех же характеристик, тогда поговорим.
G>>Кстати с чего все началось: для обхода графов вполне достаточно Linq и комбинаторов. I>Linq можно использовать, только надо ли, если код превращается непойми во что да еще становится длиннее ажно вдвое ?
Неверно, ибо один и тот же код обхода можно использовать для любых графов.
I>И при этом ни универсальности ни быстродействия даже MemoizeAll не спасает
MemoizeAll не для быстродействия, а для однократного появления сайд-эффектов, а универсальности более чем достаточно.
Здравствуйте, FR, Вы писали:
I>>Это как бы так, зато гораздо сложнее становится узнать, когда же надо писать new/delete и конструкторы всякие, а когда нет.
FR>Не становится, правило очень простое, new писать только в конструкторах умных указателей, delete в прикладном коде не использовать никогда.
Шота я смотрю, это простое правило мало у кого получается применить
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
HA>>>Разве прячет динамическую память? Я бы так не сказал. Можно свои аллокаторы определять. G>>Тем не менее с использованием STL писать new, а тем более delete, приходится в разы меньше.
I>Это как бы так, зато гораздо сложнее становится узнать, когда же надо писать new/delete и конструкторы всякие, а когда нет.
Простые правила:
1)Если не писал new — не пиши delete
2)Если хочешь написать new, то не пиши delete, а используй один из классов умных указателей.
3)Никогда не возвращай обычный указатель из функции.
Только тогда C++ из сверх-супер-пупер-мега быстрого монстра превращается маленького пушистого котенка.
G>Ты как-то забыл что мой код с небольшими усилиями можно распараллелить. Каких усилий будет стоить сделать то же самое на C++ или на JS? G>Вообще сейчас любой переборной алгоритм надо параллелить.
Империя зла нас плюсистов не обделила на этот раз:
Здравствуйте, gandjustas, Вы писали:
G>>>Ну я даже не удивлен что ты снова поменял условия задачи. I>>Я ничего не менял G>Ага, ты не сообщал все условия, это по сути то же самое.
Я сразу сказал, что реальную задачу слишком сложно описать и решить
I>>И заметь — универсальность сама собой куда то пропала потому что возвращается IEnumerable<IEnumerable<T>>, а ленивость ни одного преимущества не дает. G>не понял фразы. Ты можешь придумать более универсальный интерфейс чтобы вернуть все маршруты на графе?
Ты всегда начинаешь со второстепенных требований ?
I>>Ленивость нужна когда с большой вероятностью не нужен полный перебор. В задаче, которую я тебе показал, ленивые переборы себя _не_ _оправдали_. G>Ты скрыл важные детали до того как я показал код. Теперь не строй из себя самого умного.
Я ничего не скрывал кроме самого решения Тебе нужно было не валять дурака а сразу написать AllRoutes и все дела.
G>Ты как-то забыл что мой код с небольшими усилиями можно распараллелить. Каких усилий будет стоить сделать то же самое на C++ или на JS? G>Вообще сейчас любой переборной алгоритм надо параллелить.
Распараллеливается на раз и еще легче чем тебе кажется
G>Ты как-то опять обошел вниманием что мой код: G>1)Довольно легко распараллелить
см выше
G>2)Обобщенный
и толку в этом никакого
G>Добейся в коде выше тех же характеристик, тогда поговорим.
Твой код обладает перформансом ниже плинтуса.
I>>Linq можно использовать, только надо ли, если код превращается непойми во что да еще становится длиннее ажно вдвое ? G>Неверно, ибо один и тот же код обхода можно использовать для любых графов.
1 Не для любых 2 с потерей перформанса
I>>И при этом ни универсальности ни быстродействия даже MemoizeAll не спасает G>MemoizeAll не для быстродействия, а для однократного появления сайд-эффектов, а универсальности более чем достаточно.
Универсальность без перформанса никому не нужна в таких задачах.
Здравствуйте, gandjustas, Вы писали:
G>Простые правила: G>1)Если не писал new — не пиши delete G>2)Если хочешь написать new, то не пиши delete, а используй один из классов умных указателей. G>3)Никогда не возвращай обычный указатель из функции.
G>Только тогда C++ из сверх-супер-пупер-мега быстрого монстра превращается маленького пушистого котенка.
Спасибо, К.О. За 5 лет до твоей регистрации на РСДН я писал примерно тож самое.
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
G>>>>Ну я даже не удивлен что ты снова поменял условия задачи. I>>>Я ничего не менял G>>Ага, ты не сообщал все условия, это по сути то же самое. I>Я сразу сказал, что реальную задачу слишком сложно описать и решить
Тем не менее продолжал что-то доказывать, хотя фактически не привел оснований.
I>>>И заметь — универсальность сама собой куда то пропала потому что возвращается IEnumerable<IEnumerable<T>>, а ленивость ни одного преимущества не дает. G>>не понял фразы. Ты можешь придумать более универсальный интерфейс чтобы вернуть все маршруты на графе? I>Ты всегда начинаешь со второстепенных требований ?
Не меняй тему, ответь на вопрос.
I>>>Ленивость нужна когда с большой вероятностью не нужен полный перебор. В задаче, которую я тебе показал, ленивые переборы себя _не_ _оправдали_. G>>Ты скрыл важные детали до того как я показал код. Теперь не строй из себя самого умного. I>Я ничего не скрывал кроме самого решения
И задачи
I>Тебе нужно было не валять дурака а сразу написать AllRoutes и все дела.
Так ты не мог объяснить что есть route
G>>Ты как-то забыл что мой код с небольшими усилиями можно распараллелить. Каких усилий будет стоить сделать то же самое на C++ или на JS? G>>Вообще сейчас любой переборной алгоритм надо параллелить. I>Распараллеливается на раз и еще легче чем тебе кажется
Покажи код. Иначе не верю.
G>>Ты как-то опять обошел вниманием что мой код: G>>1)Довольно легко распараллелить I>см выше
G>>2)Обобщенный I>и толку в этом никакого
Ну да, кроме того что меньше кода писать — действительно никакого.
G>>Добейся в коде выше тех же характеристик, тогда поговорим. I>Твой код обладает перформансом ниже плинтуса.
Давай тестовые данные, проведем забеги.
I>>>Linq можно использовать, только надо ли, если код превращается непойми во что да еще становится длиннее ажно вдвое ? G>>Неверно, ибо один и тот же код обхода можно использовать для любых графов. I>1 Не для любых 2 с потерей перформанса
1 — докажи, 2 — докажи
I>>>И при этом ни универсальности ни быстродействия даже MemoizeAll не спасает G>>MemoizeAll не для быстродействия, а для однократного появления сайд-эффектов, а универсальности более чем достаточно. I>Универсальность без перформанса никому не нужна в таких задачах.
Короче ты снова приводишь какие-то высказывания и не обосновываешь их. А там где очевидно неправ пытаешься сменить тему разговора.
С тебя:
1)Распараллеленный вариант allroutes
2)Формальное доказательство что не для любых графов подходит мой код
Без этого можешь и не писать. Полезного и умного в твоих практически нет.
Здравствуйте, gandjustas, Вы писали:
G>>>Ага, ты не сообщал все условия, это по сути то же самое. I>>Я сразу сказал, что реальную задачу слишком сложно описать и решить G>Тем не менее продолжал что-то доказывать, хотя фактически не привел оснований.
Тебе спецификацию что ли показать ? Я не уверен что ты сможешь её прочесть, если ты даже не знаешь что такое маршрут.
G>>>не понял фразы. Ты можешь придумать более универсальный интерфейс чтобы вернуть все маршруты на графе? I>>Ты всегда начинаешь со второстепенных требований ? G>Не меняй тему, ответь на вопрос.
Что же касается универсальности, то объясни, куда она девается если надо вдруг искать циклы ? Внезапно оказалось что твой универсальный подход стал вдруг частным случаем
I>>Тебе нужно было не валять дурака а сразу написать AllRoutes и все дела. G>Так ты не мог объяснить что есть route
Кто ж виноват, что ты не в теме и даже можешь отрыть википедию да глянуть что такое маршрут в графе.
I>>Распараллеливается на раз и еще легче чем тебе кажется G>Покажи код. Иначе не верю.
Про паралельный dfs написано достаточно много работ. См стр 328
G>>>2)Обобщенный I>>и толку в этом никакого G>Ну да, кроме того что меньше кода писать — действительно никакого.
У тебя кода БОЛЬШЕ. К тому же код ТОРМОЗНОЙ А распараллелить просто так не получится,нужно знать фокус параллелизации этого dfs. Я этот фокус знаю, а ты ?
I>>Твой код обладает перформансом ниже плинтуса. G>Давай тестовые данные, проведем забеги.
Все что надо я тебе уже дал. Если хочешь, что бы я поработал над этим какое то время, предложи чтото что может меня заинтересовать.
I>>>>Linq можно использовать, только надо ли, если код превращается непойми во что да еще становится длиннее ажно вдвое ? G>>>Неверно, ибо один и тот же код обхода можно использовать для любых графов. I>>1 Не для любых 2 с потерей перформанса G>1 — докажи, 2 — докажи
1 графы задаются разными способами, ты этого не знал ? вычислительная сложность алгоритма зависит от этого способа.
2 linq это _вагон_ _кода_,а у меня только чистая рекурсия. доказательсво см. в рефлекторе
G>Короче ты снова приводишь какие-то высказывания и не обосновываешь их. А там где очевидно неправ пытаешься сменить тему разговора. G>С тебя: G>1)Распараллеленный вариант allroutes
см выше
G>2)Формальное доказательство что не для любых графов подходит мой код
Ты хорошо понимаешь, что вычислительная сложность задач на графах зависит от способа представления графа ?
Потому еще раз — лучше ограничиться только поиском всех маршрутов — первая фаза.
