Перемещение экземпляров из Сета в другое в Scala

Question

В игре мне нужно следить за тем, какие из моих объединенных спрайтов используются. Когда «активируются» сразу несколько спрайтов, я хочу перенести их из моего passivePool в activePool, оба из которых являются неизменяемыми HashSets (хорошо, я буду создавать новые наборы каждый раз, чтобы быть точным). Поэтому моя основная идея заключается в следующем:

activePool ++= passivePool.take(5)
passivePool = passivePool.drop(5)

но, читая документацию по scala, я предполагаю, что 5, которые я беру, может отличаться от 5, которое я тогда отбрасываю. Что, безусловно, не то, что я хочу. Я также мог бы сказать что-то вроде:

val moved = passivePool.take(5)
activePool ++= moved
passivePool --= moved

но так как это то, что мне нужно делать практически каждый кадр в реальном времени на ограниченном устройстве (телефон Android), я думаю, это будет намного медленнее, так как мне придется искать один за другим каждый из moved спрайтов из passivePool.

Какие-нибудь умные решения? Или я что-то упустил? Помните, что эффективность является главной задачей здесь. И я не могу использовать списки вместо наборов, потому что мне также нужно удалить спрайты с произвольным доступом из activePools, когда спрайты уничтожены в игре.

Answer 1

Нет ничего лучше сравнительного анализа для получения ответов на эти вопросы. Давайте возьмем 100 комплектов размером 1000 и бросим их по 5 за раз, пока они не опустеют, и посмотрим, сколько времени это займет.

passivePool.take(5); passivePool.drop(5)                    // 2.5   s
passivePool.splitAt(5)                                      // 2.4   s
val a = passivePool.take(5); passivePool --= a              // 0.042 s
repeat(5){ val a = passivePool.head; passivePool -= a }     // 0.020 s

Что происходит?

Причина, по которой все работает так, состоит в том, что immutable.HashSet построен как хэш-дерево с оптимизированными (эффективно O(1)) операциями добавления и удаления, но многие другие методы не реализованы повторно; вместо этого они наследуются от коллекций, которые не поддерживают добавление / удаление и поэтому не могут получить эффективные методы бесплатно. Поэтому они в основном воссоздают весь хэш-набор с нуля. Если ваш хэш-набор содержит только несколько элементов, это плохая идея. (В отличие от замедления 50-100x с наборами размера 1000, набор размера 100 имеет "только" замедление 6-10x ....)

Итак, суть: пока библиотека не улучшится, делайте это «неэффективно». Вы будете значительно быстрее.

Answer 2

Я думаю, что здесь может быть некоторое расстояние при использовании splitAt, которое вернет вам как пять спрайтов для перемещения, так и урезанный пул в одном вызове метода:

val (moved, newPassivePool) = passivePool.splitAt(5)
activePool ++= moved
passivePool = newPassivePool

Бонусные баллы, если вы можете напрямую присвоить passivePool в первой строке, хотя я не думаю, что это возможно в коротком примере, где вы также определяете новую переменную moved.