Comments 10
Ну да, взять подходящий инструмент для решения задачи - это не наш метод, возьмём неподходящий и будем превозмогать)
В реальной жизни превозмогать приходится довольно часто, поэтому чем знать 30 разных языков под каждую узкую задачу, которую он идеально решает - лучше всё же хорошо знать свой основной, чтобы относительно быстро справиться с какими-то редкими особыми случаями.
Ну а если глобально, что у меня тут игровой движок на хрен пойми чём - ну таки да, я и не скрывал в прошлых своих статьях, что т.к. это хобби, где я и хотел заморочиться с чем-то странным чисто во имя искусства ?
А за +1 структуру данных - спасибище! ?
А какая у вас была задача, что возможно использование BloomFilter ? Это же вероятностная структура данных, и она гарантирует только отсутствие ложноотрицательных ответов. В общем случае, замена HashSet сотоварищи на BloomFilter не является корректной оптимизацией.
В моём случае он вроде бы подходит. Задача - закешировать результат вычисления на наличие возможности коллизии между двумя типами объектов. В принципе мне даже гарантия того, что отрицательный ответ дадут безошибочно - подходит, т.к. если объекта гарантированно нет в списке доступных к столкновению пар - всё, прерываем вычисления, едем дальше. А в этом, собственно, и состоит цель "широкой фазы" определения столкновений.
т.к. если объекта гарантированно нет в списке доступных к столкновению пар
Такой гарантии BloomFilter как раз не даёт. Он гарантирует точность ответа только для добавленных в него элементов.
Ну смотрите, предельный случай: в фильтре проставлены все битики. Тогда на вопрос "а есть тут этот элемент" всегда будет ответ "да, есть" независимо от элемента.
Можно считать, в первом приближении, что BloomFilter это HashSet без проверки на коллизии хэшей.
Я, простите, запутался: как подружить утверждение, что фильтр гарантирует отсутствие ложноотрицательных срабатываний и то, что он гарантирует точность только для добавленных в него элементов?..
Я, простите, запутался: как подружить утверждение, что фильтр гарантирует отсутствие ложноотрицательных срабатываний и то, что он гарантирует точность только для добавленных в него элементов?
Утверждения о ложноотрицательности\ложноположительности BloomFilter относятся только к условию "элемент x принадлежит фильтру".
Ложноотрицательность здесь - фильтр ответил "нет", но на самом деле элемент добавлялся. И такого быть не может, так как BloomFilter никогда не сбрасывает битики, а только выставляет.
Соответственно, ложноположительность - фильтр ответил "да", но на самом деле элемент никогда не добавлялся. А вот это вполне возможно, так как BloomFilter игнорирует коллизии хэшей.
фильтр ответил "нет", но на самом деле элемент добавлялся. И такого быть не может, так как BloomFilter никогда не сбрасывает битики, а только выставляет.
Супер, мне этого достаточно)
На этапе "прогрева" я пробегаюсь по всем игровым типам объектов и вычисляю, может ли комбинация объектов типа А и Б вызвать коллизию. Если да, то добавляю хэш этой комбинации в фильтр.
Потом, уже во время игры, я только выполняю проверку, если хэша от пары типов в фильтре нет - значит и на столкновения проверять дальше не стоит.
Вроде бы всё вписывается в логику, да и в демке работает ??♂️
В коде нету преобразования байтов обратно в модели, а используются геттеры - это добавляет некоторый оверхед на постоянную десериализацию + компилятор не может знать, что геттеры всегда возвращают одни и те же значения
разделяемой памяти нам не завезли
А может и завезли: для изолятов -> TransferableTypedData. Для веба -> SharedArrayBuffer
лучше бы этот список сделать немодифицируемым
Для web, кстати, это не поможет
List.filled(emptyObject,growable:false)
Если и оптимизировать, то лучше использовать List.generate, так как заполнение чем-то - итерация по всем элементам
if (random.nextBool()) {
objectsSet.add(i);
}
Да, другие структуры данных быстрее, но случайное заполнение тестовых данных не делает тест объективным
Garbage Collector и испортит вам все замеры, зачищая память после предыдущего теста
Можно попробовать вызывать его между тестами и добавить немного unsafe
В коде нету преобразования байтов обратно в модели, а используются геттеры - это добавляет некоторый оверхед на постоянную десериализацию + компилятор не может знать, что геттеры всегда возвращают одни и те же значения
Спасибо, ценное замечание, вернусь к этому, как устраню более серьёзные и насущные проблемы.
А может и завезли: для изолятов -> TransferableTypedData. Для веба -> SharedArrayBuffer
Ну это всё истории о том, как поработать с байтами, да ещё и только в read-only режиме. Нам привязывают руки к ногам и заявляют, что тем самым обезопасили от возможных негативных последствий, если бы мы могли двигать руками свободно =) Конечно, можно и так что-то придумать, но простого масштабирования тут не сделать, если заранее архитектуру не продумал со знанием всех возможных проблем.
Хотя в SharedArrayBuffer уже можно писать, да. Ещё бы это не только лишь в веб принесли...
но случайное заполнение тестовых данных не делает тест объективным
Ну тут уже у кого какая степень желания заморочиться. Я тест-то прогнал всего на одной машине, всего 15 раз, а в фоне ещё и работать могло что-то... в общем, никогда его нельзя будет считать объективным.
«Разгоняем» HashSet, HashMap и циклы на примере Dart