А почему, кстати, О(1)? Уже придумали алгоритм, ищущий быстрее двоичного поиска?
Да, придумали. Хэш-таблица.
Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.
А если хэш-таблица не влезает в оперативку?
Это не влияет на ассимптотику.
А если таблицу надо часто перестраивать?
Это не влияет на ассимптотику.
А дальше попрошу сходить в любую книжку по алгоритмам и разобраться с понятием амортизированной сложности алгоритма
Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем "какой алгоритм быстрее".
Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil…
Yet we should not pass up our opportunities in that critical 3%… A 12% improvement, easily obtained, is never considered marginal
Получается совсем другой смысл, не так ли?
Эта вырваная из контекста фраза часто используется как оправдание для того чтобы пропустить этап обдумывания, и зафигачить линейный поиск по большому списку там, где можно было бы спокойно использовать HashMap.
Из него вполне очевидно, что по ассимптотике хэш-таблица быстрее других методов, т.к. время работы других методов так же растет линейно с ростом длины строки.
Если быть чуть более дотошным, то время работы O(hashTime).
Т.е. если у нас есть N строк с длиной L, хэш-таблица отработает за O(L). Но заметьте, что поиск в отсортированном массиве был бы O(L * log(N)), а поиск в неупорядоченном массиве был бы O(L * N).
Согласен с EvgeniiR.
Поставил вам "Плюсик" авансом.
Очень вам рекомендую аккуратнее выражать свое субъективное мнение. Как мне кажется, проблема в том, что вы зачастую высказываете его довольно безаппеляционно, и, вероятно, как в данном случае, без глубокого понимания вопроса.
Ммм. Вы правы. Я неправильно интерпретиловал следующую цитату:
Even though const_cast may remove constness or volatility from any pointer or reference, using the resulting pointer or reference to write to an object that was declared const or to access an object that was declared volatile invokes undefined behavior.
А конкретно я упустил
using the resulting pointer or reference to write to an object that was declared const
Т.е. если у нас есть объект, который не объявлен как const, мы его скастовали в const, а потом кастом сняли const, в него можно писать и это не ошибка.
Так что кажется что ни в моём, ни в вашем примере UB нет.
Если функция получает объект по const ref, компилятор не знает как этот объект был объявлен. А значит компилятор не может предположить, что неконстантный объект, который мы передали по константной ссылке не может быть изменён.
Если вы видели предыдущие соревнования, то должны понимать, что модель игрового мира стала гораздо проще чем раньше (шарики, пинающие шарики, кайф же!)
Хз. Вроде в пределах погрешности. А в чем смысл фотографировать на рекламу бОльший бургер? Вряд ли люди опираются на размер кунжутного зернышка для масштаба.
… И хотя WebRTC позволяет удобно отправлять ненадёжные «беспорядочные» данные из браузера в браузер, он терпит крах, когда требуется передача данных между браузером и выделенным сервером.
Проблема возникает из-за чрезвычайной сложности WebRTC. Причины этой сложности понятны: WebRTC в первую очередь был разработан для обмена данными peer-to-peer между браузерами, поэтому для обхода NAT и передачи пакетов он в худшем случае требует поддержки STUN, ICE и TURN.
Оригинальный комментарий:
Да, придумали. Хэш-таблица.
Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.
Это не влияет на ассимптотику.
Это не влияет на ассимптотику.
Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем "какой алгоритм быстрее".
Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.
На самом деле, полная цитата звучит иначе
Получается совсем другой смысл, не так ли?
Эта вырваная из контекста фраза часто используется как оправдание для того чтобы пропустить этап обдумывания, и зафигачить линейный поиск по большому списку там, где можно было бы спокойно использовать HashMap.
Дочитайте мой комментарий до конца.
Из него вполне очевидно, что по ассимптотике хэш-таблица быстрее других методов, т.к. время работы других методов так же растет линейно с ростом длины строки.
То все равно за O(1).
Если быть чуть более дотошным, то время работы O(hashTime).
Т.е. если у нас есть N строк с длиной L, хэш-таблица отработает за O(L). Но заметьте, что поиск в отсортированном массиве был бы O(L * log(N)), а поиск в неупорядоченном массиве был бы O(L * N).
Ещё как минимум Яндекс, Odnoklassniki.
Согласен с EvgeniiR.
Поставил вам "Плюсик" авансом.
Очень вам рекомендую аккуратнее выражать свое субъективное мнение. Как мне кажется, проблема в том, что вы зачастую высказываете его довольно безаппеляционно, и, вероятно, как в данном случае, без глубокого понимания вопроса.
+1. У меня и моих знакомых в точности такой же опыт, за редкими исключениями.
Ммм. Вы правы. Я неправильно интерпретиловал следующую цитату:
А конкретно я упустил
Т.е. если у нас есть объект, который не объявлен как const, мы его скастовали в const, а потом кастом сняли const, в него можно писать и это не ошибка.
Так что кажется что ни в моём, ни в вашем примере UB нет.
Если функция получает объект по const ref, компилятор не знает как этот объект был объявлен. А значит компилятор не может предположить, что неконстантный объект, который мы передали по константной ссылке не может быть изменён.
Компилятор имеет право и может заменить это выражение на true.
const_cast снимает модификатор const со ссылки, но не позволяет писать в неё. Попытка сделать это приводит к undefined behavior.
Так что хоть я не смог заставить ни один компилятор на godbolt превратить эту проверку в true, полагаться на такое поведение компиляторов не стоит.
Причём у гуглдоков уже есть версионирование:)
Если вы видели предыдущие соревнования, то должны понимать, что модель игрового мира стала гораздо проще чем раньше (шарики, пинающие шарики, кайф же!)
Ну и прикольно всёже 3д делать:)
Deleted
Да, это выглядит гораздо лучше, чем в статье)
В компьютерной графике Scale Space Pyramid традиционно называется MIP maps.
Хз. Вроде в пределах погрешности. А в чем смысл фотографировать на рекламу бОльший бургер? Вряд ли люди опираются на размер кунжутного зернышка для масштаба.
Что забавно, КДПВ — тоже рекламный трюк. Если отскейлить бургеры в один масштаб, такой вопиющей несправедливости уже не видно.
Поздравляю с первой статьей!
Частицы выглядят круто.
Вы очень правильные вещи пишите, но я не смог сдержать улыбку от "Здравствуйте!" в комментариях:)
Виртуальные вызовы конечно же заметно медленнее прямых.
Но ваш тест абсолютно некорректен.
Если бы вы скомпилировали без оптимизаций, я бы сказал что это нечестный бенчмарк, т.к. в продакшене всегда включают -O2.
Но, судя по результатам, вы таки включили O2. И компилятор не только заинлайнил вызовы, но и векторизовал их.
Source