Ускорение фильтра большого списка в Котлине

Question

У меня есть ArrayList примерно с 4000 Pair<Int,Int> с (точки на сетке).В какой-то момент мне нужно получить точки в определенном диапазоне координат x и y.

Пока мой код:

val points: ArrayList = // ...

val xRange: IntRange = x: Int - spacingX: Int .. x: Int + spacingX: Int
val yRange: IntRange = y: Int - spacingY: Int .. y: Int + spacingY: Int

val nearPoints: ArrayList<Point<Int, Int>> = points.filter { xRange.contains(it.first) && yRange.contains(it.second) }

Это значительно быстрее, чем перебирать весь список, но я надеялся еще больше ускорить процесс.

Можно ли получить nearPoints: ArrayList быстрее с помощью другой конструкции?Я читал о Sequence, но, похоже, лучше использовать несколько операций, чем чистую фильтрацию.

Answer 1

sequence в Котлине заставляет процесс работать лениво.На уровне JVM у вас будет класс, подобный Iterable, который будет использовать Iterator из ArrayList для применения фильтра.

Лучше всего профилировать код на реальных данных (но 4000 элементов, вероятно, совсем немного) и посмотреть, где находятся узкие места.

Вам необходимо поместить точки в ArrayList.Это означает, что вам не нужна лень вообще.Я бы проголосовал за использование функции .filter { .. } inline в ArrayList.Лямбда встраивается в код в этом случае, нет вызова метода для элемента.Проверьте байт-код.Возможно, вы даже можете заменить диапазоны сравнениями.

Если вам нужна большая скорость - вы можете попробовать заменить ArrayList> на примитивные типы, например, используйте IntArray или LongArray (вы можете закодировать два Int как один Long. Но, пожалуйста,, профилируйте существующий код до

Answer 2

Использование ArrayList гарантирует постоянную сложность времени O (1) (на элемент, к которому осуществляется доступ) при итерации, и поскольку contains из IntRange уже выполняет проверку диапазона

override fun contains(value: Int): Boolean = first <= value && value <= last

и не выполняет поискдля конкретного элемента я не думаю, что вы можете еще больше ускорить его.

Примечание: было бы более идиоматичным использовать in вместо contains.