Для проекта в университете мы должны были реализовать несколько различных алгоритмов для вычисления классов эквивалентности, когда дан набор элементов и набор отношений между этими элементами.
Нам было поручено реализовать, среди прочего, алгоритм Union-Find и его оптимизацию (Union by Depth, Size). Случайно (делая то, что мне показалось необходимым для правильности алгоритма), я нашел другой способ оптимизации алгоритма.
Это не так быстро, как Union By Depth, но близко. Я не мог понять, почему это было так быстро, как это было, поэтому я посоветовался с одним из ассистентов преподавателя, который тоже не мог понять.
Проект был на Java, а используемые мной структуры данных основывались на простых массивах целых чисел (объект, а не int)
Позже, при оценке проекта мне сказали, что он, вероятно, как-то связан с «кэшированием Java», но я не могу найти в Интернете ничего о том, как кэширование повлияет на это.
Каков наилучший способ, без расчета сложности алгоритма, доказать или опровергнуть, что моя оптимизация такая быстрая из-за способа работы java? Реализовать это на другом, более низком уровне? Но кто скажет, что язык не будет делать то же самое?
Надеюсь, я дал понять,
спасибо