Как ускорить перебор массива

Question

Я делаю игру, и для генерации мира использую массив забитый фрагментами, которые уже созданы. При каждом повторении цикла игры, проверяем, нужно ли генерировать новый фрагмент:

        if (math2(px) + 1, math2(pz)) not in generatedChunks:
            generatedChunks.append((math2(px) + 1, math2(pz)))
            generate((px + 8)//8*8, math1(pz))

Функции:

@njit(cache=True, nopython=True, fastmath=True, parallel=False)
def math2(s):
    return s//8


@njit(cache=True, nopython=True, fastmath=True, parallel=False)
def math1(s):
    return s//8*8

Но игра тормозит. Есть ли более производительный алгоритм поиска, можно ли оптимизировать этот?

Answer 1

Пожалуй, суммирую всё вместе.

if (math2(px) + 1, math2(pz)) not in generatedChunks:
    generatedChunks.append((math2(px) + 1, math2(pz)))
    generate((px + 8)//8*8, math1(pz))

В худшем случае вы в этом фрагменте 3 раза считаете один и тот же кортеж. Лучше вынесите этот кортеж в переменную. Вернее, в 3-м случае у вас другой кортеж, но, возможно, лучше использовать всё же один и тот же кортеж, надо тестировать:

chunk = (math1(px) + 1, math1(pz))
if chunk not in generatedChunks:
    generatedChunks.append(chunk)
    generate(chunk)

Как абсолютно верно заметил insolor, сделайте generatedChunks вместо списка множеством, и тогда скорость поиска элемента значительно вырастет, если generatedChunks достаточно велик.

Далее, насчёт Numba:

@njit(cache=True, nopython=True, fastmath=True, parallel=False)
def math2(s):
    return s//8

@njit(cache=True, nopython=True, fastmath=True, parallel=False)
def math1(s):
    return s//8*8

Вы проводили какие-нибудь тесты? Моя интуиция подсказывает и проведённые тесты подтверждают, что для таких небольших вычислений без векторов и циклов Numba не ускоряет, а замедляет вычисления (примерно в 2 раза). Лучше используйте декоратор lru_cache, если у вас могут часто повторяться эти расчёты с одинаковыми аргументами:

from functools import lru_cache

@lru_cache()
def math2(s):
    return s//8

@lru_cache()
def math1(s):
    return s//8*8

Если же расчёты практически не повторяются - не используйте никакие декораторы, так будет быстрее всего, любой декоратор требует накладных расходов и в худшем случае замедляет скорость исполнения функций, а не ускоряет. Нужно понимать, что вы делаете и проводить тесты, а не слепо пользоваться декораторами "потому что они ускоряют". Ускоряют, но в подходящих им сценариях использования.

БЛОГ НА HUSL

Как ускорить перебор массива

Ответы (1 шт):