А почему |E| = 5? |E| - общее количество рёбер в графе, а не среднее на вершину. Так что для случая, когда есть хотя бы по одному ребру на вершину у вас не лучше |V|^2. Ну а если граф настолько уж разрежен, то и Дейкстра с нормальной очердью будет очень быстр. В очереди же лежат достижимые вершины, а не все, поэтому он быстро переберёт все достижимые и выйдет. За то же время количество посещённых вершин, что и у вас, только выбирать наименьший вес будет много быстрее, чем линейный поиск по всем рёбрам в графе.
Если вы утверждаете, что в каких-то случаях ваш алгоритм быстрее, то показали бы бенчмарки на этих примерах и сравнили бы с какой-нибудь готовой реализацей Дейкстры.
Соглашусь с вами, но не про данную модель. Горный велосипед - спортивный инвентарь. На нём можно ездить по городу и использовать как транспорт, но для этого гораздо лучше подходит городской велосипед: шоссейник, гибрид, да даже гравел. В городе MTB выглядит как прокаченный внедорожник (которые несомненно встречаются).
А в качестве горного и внедорожного у электрического есть большой минус - он тяжёлый, что очень плохо для маневренности и отработки неровностей. Единственное известное мне применение - полный привод для грязи и снега. Сам хотел поставить передний привод для глубокого снега зимой.
Запрещено. В силу требований потоковой безопасности в первую очередь. Вот только не всем она нужна, особенно с учётом её цены. Такой же пример - std::shared_ptr, его атомарный счётчик слишком уж дорог для многих применений. Имхо, это нарушение базового принципа "не платить за то, что не используешь". Поэтому мы отказались от этих довольно слабых гарантий (класс в целом всё равно не thread-safe) в пользу производительности в одном потоке.
P.S. Струкутуру проекта поправили, ссылка изменилась panda::string
Сложно утвержать сразу про все реализации std, но скорее нет, чем да. На 64-битной архитектуре sizeof(panda::string) == 40. Стандартная у меня 32 (Debian 11, GCC 10.2). То есть просто так передавать по значению тоже может быть чуть-чуть дороговато, лучше бы по ссылке. Но скопировать себе для хранения - ни о чём на фоне аллокации и копии в std.
Шёл 2023 год, а в статьях GCC 6.3. Не удивительно при оригинале статьи из 2017 года. При этом ни про устройство, ни про гарантии и потенциальный UB от повисших указателей. `string_view` - замечательная вещь, но хоть какие-нибудь размышления и сравнения с char* не помешали бы.
Ну и воспользуюсь случаем и порекламмирую panda::string. CopyOnWrite(CoW), все те же substr тоже без копирований и аллокаций, но с полной гарантией безопасности. Тот же SSO на 23 байта. Цена полной безопасности дешёвого subbstr - CoW не лучшим образом дружит с потоками. Но если не шарить стейт и передавать копии данных аккуратно, ну или как мы вообще не использовать потоки, то это совсем не цена.
Я так понял, что в векторе вы взяли magic_get (который нынче Boost.PFR) и развернули массив структур в структуру массивов. Интересное упражнение.
А что насчёт индексов и выборок? Для ECS же важно уметь выбирать наборы компонент. Типа для всех, содержащих компоненту Health и Collision, запустить систему нанесения урона при столкновении.
Немецкие власти запретили в школах земли Гессен Office 365 ещё в 2019 году. В июле текущего года Microsoft представила облачную услугу, которая позволит клиентам из государственного сектора использовать сервисы в соответствии с политикой ЕС.
Вот так, например? Да, французы ещё не сделали, но явно не в вакууме решение принимали.
Я не C, а C++ программист и может быть поэтому не понимаю, но как использовать сигналы вместо исключений? Для взаимодействия с другими процессами - понятно, но что толку слать сигнал самому себе? Стек после хэндлера будет тем же, выполнение продолжится со следующей после kill строки. Зачем?
Я действительно не специалист, но разве доказательство теоремы Белла не опровергает наличие скрытых параметров? Ок, остаются версии типа возможности путешествия во времени, но мы серьёзно будем их рассматривать?
Как-то слегка нелепо даже упоминать, не то что продвигать, теорию скрытых параметров, когда в этом году за практическое её низвержение дали нобелевку. Как минимум в том, что там честный рандом в связанных частицах, сомневаться уже давно не приходится. Алогритм в посте разобран интересно, но не надо так смеяться над теоретиками.
Есть и другое решение вопроса производительности - кэш. Мы реализовали банальный map по typeid и это стало тоже в разы быстрее. Да, всё ещё требует rtti, зато работает с любыми наследованиями (множественным виртуальным), не требует модификации базового класса и тд. https://github.com/CrazyPandaLimited/panda-lib/blob/master/clib/src/panda/cast.h
Не ходите в геймдев, особенно мобильный. Вас ещё сильнее шокируют соотношения затрат на рекламу и разработку, а так же показатели roi. Да и других сфер, где есть только один показатель - отбиваемость рекламы, не так уж и мало.
Этим активно занимался Александреску, пытаясь внести в D. Но в итоге не получилось даже стандартную библиотеку нормально описать. Он обещает вернуться к этой задаче, но уже лет 5 никаких подвижек.
К сожалению исходники закрыты. Я, например, давно хотел поиграться с ИИ боя, написать хороший алгоритм, использовать его как инструмент для поиска новых приёмов, как это произошло в шахматах. И даже при наличии исходников хоты было бы сложно это сделать в силу того, что это не с ноля написанный проект, а патчи к старой игре без исходников. VCMI - наоборот, полный набор исходников, с ним гораздо приятнее работать.
Что же вы для VCMI скрин из HotA взяли? Я уж было подумал, что они портировали хоту и теперь можно поиграть. Но нет. А без HDmod, ладдера и HotA этот движок не нужен.
Огромное спасибо за статью. Давно сам хотел написать что-то подобное, потому что постоянно сталкиваюсь с библиотеками на CMake, которыми совершенно невозможно пользоваться. То как subdirectory не работает, то свои переменные выставляет сложно.
Вы путаете книги. Дизайн и эволюция - не справочник, а история создания. Она про причины принятых решений, в то время как cppreference - справочник с результатами принятых решений.
Робинзон Крузо нервно курит в сторонке. 4 человека выживали 6 лет на необитаемом острове за полярным кругом, а потом фактически купили себе билет домой. Я только для погружения в эту историю готов туда лететь, но надо аутентично, на паруснике из Архангельска.
Идея и решение - извращение, но спасибо, что поделились, это интересно.
Если хотите запретить создание на стеке, то лучше делать приватным деструктор, а не конструкторы. Это даёт возможность не делать create и при появлении новых публичных конструкторов, например в потомках, всё ещё будет работать.
А почему |E| = 5? |E| - общее количество рёбер в графе, а не среднее на вершину. Так что для случая, когда есть хотя бы по одному ребру на вершину у вас не лучше |V|^2. Ну а если граф настолько уж разрежен, то и Дейкстра с нормальной очердью будет очень быстр. В очереди же лежат достижимые вершины, а не все, поэтому он быстро переберёт все достижимые и выйдет. За то же время количество посещённых вершин, что и у вас, только выбирать наименьший вес будет много быстрее, чем линейный поиск по всем рёбрам в графе.
Если вы утверждаете, что в каких-то случаях ваш алгоритм быстрее, то показали бы бенчмарки на этих примерах и сравнили бы с какой-нибудь готовой реализацей Дейкстры.
Соглашусь с вами, но не про данную модель. Горный велосипед - спортивный инвентарь. На нём можно ездить по городу и использовать как транспорт, но для этого гораздо лучше подходит городской велосипед: шоссейник, гибрид, да даже гравел. В городе MTB выглядит как прокаченный внедорожник (которые несомненно встречаются).
А в качестве горного и внедорожного у электрического есть большой минус - он тяжёлый, что очень плохо для маневренности и отработки неровностей. Единственное известное мне применение - полный привод для грязи и снега. Сам хотел поставить передний привод для глубокого снега зимой.
Запрещено. В силу требований потоковой безопасности в первую очередь. Вот только не всем она нужна, особенно с учётом её цены. Такой же пример - std::shared_ptr, его атомарный счётчик слишком уж дорог для многих применений. Имхо, это нарушение базового принципа "не платить за то, что не используешь". Поэтому мы отказались от этих довольно слабых гарантий (класс в целом всё равно не thread-safe) в пользу производительности в одном потоке.
P.S. Струкутуру проекта поправили, ссылка изменилась panda::string
Сложно утвержать сразу про все реализации std, но скорее нет, чем да. На 64-битной архитектуре sizeof(panda::string) == 40. Стандартная у меня 32 (Debian 11, GCC 10.2). То есть просто так передавать по значению тоже может быть чуть-чуть дороговато, лучше бы по ссылке. Но скопировать себе для хранения - ни о чём на фоне аллокации и копии в std.
Шёл 2023 год, а в статьях GCC 6.3. Не удивительно при оригинале статьи из 2017 года. При этом ни про устройство, ни про гарантии и потенциальный UB от повисших указателей. `string_view` - замечательная вещь, но хоть какие-нибудь размышления и сравнения с char* не помешали бы.
Ну и воспользуюсь случаем и порекламмирую panda::string. CopyOnWrite(CoW), все те же substr тоже без копирований и аллокаций, но с полной гарантией безопасности. Тот же SSO на 23 байта. Цена полной безопасности дешёвого subbstr - CoW не лучшим образом дружит с потоками. Но если не шарить стейт и передавать копии данных аккуратно, ну или как мы вообще не использовать потоки, то это совсем не цена.
Меня тоже не порадовал этот момент. Самокат тем и отличается от скутера или мотоцикла, что его легко занести домой. Где ещё его заряжать?
Я так понял, что в векторе вы взяли magic_get (который нынче Boost.PFR) и развернули массив структур в структуру массивов. Интересное упражнение.
А что насчёт индексов и выборок? Для ECS же важно уметь выбирать наборы компонент. Типа для всех, содержащих компоненту Health и Collision, запустить систему нанесения урона при столкновении.
Вот так, например? Да, французы ещё не сделали, но явно не в вакууме решение принимали.
Я не C, а C++ программист и может быть поэтому не понимаю, но как использовать сигналы вместо исключений? Для взаимодействия с другими процессами - понятно, но что толку слать сигнал самому себе? Стек после хэндлера будет тем же, выполнение продолжится со следующей после kill строки. Зачем?
Я действительно не специалист, но разве доказательство теоремы Белла не опровергает наличие скрытых параметров? Ок, остаются версии типа возможности путешествия во времени, но мы серьёзно будем их рассматривать?
Как-то слегка нелепо даже упоминать, не то что продвигать, теорию скрытых параметров, когда в этом году за практическое её низвержение дали нобелевку. Как минимум в том, что там честный рандом в связанных частицах, сомневаться уже давно не приходится. Алогритм в посте разобран интересно, но не надо так смеяться над теоретиками.
Есть и другое решение вопроса производительности - кэш. Мы реализовали банальный map по typeid и это стало тоже в разы быстрее. Да, всё ещё требует rtti, зато работает с любыми наследованиями (множественным виртуальным), не требует модификации базового класса и тд. https://github.com/CrazyPandaLimited/panda-lib/blob/master/clib/src/panda/cast.h
Не ходите в геймдев, особенно мобильный. Вас ещё сильнее шокируют соотношения затрат на рекламу и разработку, а так же показатели roi. Да и других сфер, где есть только один показатель - отбиваемость рекламы, не так уж и мало.
Этим активно занимался Александреску, пытаясь внести в D. Но в итоге не получилось даже стандартную библиотеку нормально описать. Он обещает вернуться к этой задаче, но уже лет 5 никаких подвижек.
https://forum.dlang.org/thread/58be13e9-91cc-9cdd-0c1f-e6c439aa8c53@erdani.org
К сожалению исходники закрыты. Я, например, давно хотел поиграться с ИИ боя, написать хороший алгоритм, использовать его как инструмент для поиска новых приёмов, как это произошло в шахматах. И даже при наличии исходников хоты было бы сложно это сделать в силу того, что это не с ноля написанный проект, а патчи к старой игре без исходников. VCMI - наоборот, полный набор исходников, с ним гораздо приятнее работать.
Что же вы для VCMI скрин из HotA взяли? Я уж было подумал, что они портировали хоту и теперь можно поиграть. Но нет. А без HDmod, ладдера и HotA этот движок не нужен.
Огромное спасибо за статью. Давно сам хотел написать что-то подобное, потому что постоянно сталкиваюсь с библиотеками на CMake, которыми совершенно невозможно пользоваться. То как subdirectory не работает, то свои переменные выставляет сложно.
Вы путаете книги. Дизайн и эволюция - не справочник, а история создания. Она про причины принятых решений, в то время как cppreference - справочник с результатами принятых решений.
Переезжать на Шпицберген на удалёнку в России было модно ещё 300 лет назад.
https://ru.wikipedia.org/wiki/Выживание_четырёх_моряков_на_острове_архипелага_Шпицберген
Робинзон Крузо нервно курит в сторонке. 4 человека выживали 6 лет на необитаемом острове за полярным кругом, а потом фактически купили себе билет домой. Я только для погружения в эту историю готов туда лететь, но надо аутентично, на паруснике из Архангельска.
Идея и решение - извращение, но спасибо, что поделились, это интересно.
Если хотите запретить создание на стеке, то лучше делать приватным деструктор, а не конструкторы. Это даёт возможность не делать create и при появлении новых публичных конструкторов, например в потомках, всё ещё будет работать.