Вот тут вы зря огрызаетесь:)
Товарищ Fatigue прав, ваши облака не являются визически корректными хотябы потому что они не учитывают multiple scattering.
Ваша ошибка понятна: в оригинальной статье было так же написано, и здесь действительно есть элементы корректности. Но физически корректные облака пока никто не умеет рендерить в риалтайме.
Из контекста ваших ответов, я предполагаю что вы хотели использовать эти речевые обороты в формате сатиры. Но вот как-то у меня, например, сложилось мнение, что вы реально к шахтерам так относитесь.
Против сатиры ничего не имею, но если это реально ваше мнение, это мне уже не нравится:)
И если это сатира, возможно стоит это как-то ещё подчеркнуть.
Ок, тут согласен на все 100%.
Если есть априорное понимание того, что список объектов будет коротким нужно писать на списке. Хотя лучше написать реализацию ArraySet, чтобы каждый раз самому не писать:)
В случае же сомнений обычно стоит выбирать вариант с наилучшей асимптотикой (о выборе коллекций с адекватным трейд-оффом между ассимтотикой и константой за нас обычно заботятся разработчики коллекций. Вы врядли встретите упомянутое ниже дерево Ван Эмде Боаса, из-за его ужасной константы).
За 5 лет разработки игр я 1 раз видел в профайлере OrderedSet, который надо было заменить на массив чтобы стало быстрее. Ни разу я не видел в такой роли HashSet. И я видел с сотню раз линейный/бинарный поиск, который надо было заменить на HashSet.
Вы под "быстрее/медленнее" подразумеваете произваодительность в миллисекундах (измеряемую). А я подразумеваю сравнение вычислительной сложности.
Мое понимание ситуации взялось из оригинального комментария "А почему, кстати, О(1)? — тут речь шла явно именно про асимптотику.
Вы видимо зацепились за "Уже придумали алгоритм, ищущий быстрее двоичного поиска?"
Я же развернул этот вопрос так(из теории): найдется такое n0, что для любого N > n0 хэштэйбл работает быстрее двоичного поиска (в миллисекундах). При этом, из практики, находится это n0 довольно быстро:)
А почему, кстати, О(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, компилятор не знает как этот объект был объявлен. А значит компилятор не может предположить, что неконстантный объект, который мы передали по константной ссылке не может быть изменён.
Товарищ Fatigue безусловно неправ в своем тоне.
Простите, я подумал, что вы преимущественно опираетесь на эту презентацию.
Вот тут вы зря огрызаетесь:)
Товарищ Fatigue прав, ваши облака не являются визически корректными хотябы потому что они не учитывают multiple scattering.
Ваша ошибка понятна: в оригинальной статье было так же написано, и здесь действительно есть элементы корректности. Но физически корректные облака пока никто не умеет рендерить в риалтайме.
Отличная работа!
Продукт выглядит интересно; сделано хорошо. Я был бы не против ссылки:)
Только это никто так не воспринимает.
Пять рекламных вставок в одной статье? Оо
Из контекста ваших ответов, я предполагаю что вы хотели использовать эти речевые обороты в формате сатиры. Но вот как-то у меня, например, сложилось мнение, что вы реально к шахтерам так относитесь.
Против сатиры ничего не имею, но если это реально ваше мнение, это мне уже не нравится:)
И если это сатира, возможно стоит это как-то ещё подчеркнуть.
Не могу с вами не согласиться:)
Ок, тут согласен на все 100%.
Если есть априорное понимание того, что список объектов будет коротким нужно писать на списке. Хотя лучше написать реализацию ArraySet, чтобы каждый раз самому не писать:)
В случае же сомнений обычно стоит выбирать вариант с наилучшей асимптотикой (о выборе коллекций с адекватным трейд-оффом между ассимтотикой и константой за нас обычно заботятся разработчики коллекций. Вы врядли встретите упомянутое ниже дерево Ван Эмде Боаса, из-за его ужасной константы).
За 5 лет разработки игр я 1 раз видел в профайлере OrderedSet, который надо было заменить на массив чтобы стало быстрее. Ни разу я не видел в такой роли HashSet. И я видел с сотню раз линейный/бинарный поиск, который надо было заменить на HashSet.
А, все, я понял о чем мы спорим.
Вы под "быстрее/медленнее" подразумеваете произваодительность в миллисекундах (измеряемую). А я подразумеваю сравнение вычислительной сложности.
Мое понимание ситуации взялось из оригинального комментария "А почему, кстати, О(1)? — тут речь шла явно именно про асимптотику.
Вы видимо зацепились за "Уже придумали алгоритм, ищущий быстрее двоичного поиска?"
Я же развернул этот вопрос так(из теории): найдется такое n0, что для любого N > n0 хэштэйбл работает быстрее двоичного поиска (в миллисекундах). При этом, из практики, находится это n0 довольно быстро:)
Оригинальный комментарий:
Да, придумали. Хэш-таблица.
Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.
Это не влияет на ассимптотику.
Это не влияет на ассимптотику.
Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем "какой алгоритм быстрее".
Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.
На самом деле, полная цитата звучит иначе
Получается совсем другой смысл, не так ли?
Эта вырваная из контекста фраза часто используется как оправдание для того чтобы пропустить этап обдумывания, и зафигачить линейный поиск по большому списку там, где можно было бы спокойно использовать 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, полагаться на такое поведение компиляторов не стоит.
Причём у гуглдоков уже есть версионирование:)