Какая самая быстрая коллекция Java для однопоточных функций Contains (Point (x, y))?

Question

В моем приложении мне нужно проверить коллекцию 2D координат (x, y), чтобы увидеть, находится ли заданная координата в коллекции, она должна быть максимально быстрой и доступ к ней возможен только из одного потока. (Это для проверки столкновения)

Может ли кто-нибудь дать мне толчок в правильном направлении?

Answer 1

Самое быстрое, что я могу придумать, - это сохранить 2D-матрицу этих точек:

//just once
int[][] occurrences = new int[X_MAX][Y_MAX];
for (Point p : points ) {
    occurrences[p.x][p.y]++;
}

//sometime later
if ( occurrences[x][y] != 0 ) {
    //contains Point(x, y)
}

Если вам все равно, сколько их будет, просто сработает матрица boolean. Понятно, что это будет быстро, только если матрица была создана только один раз, и, возможно, будет обновлена ​​по мере добавления Точек в коллекцию.

Короче говоря, базовые Коллекции не идеальны для этого (хотя HashSet подошел бы близко).

Редактировать

Это может быть легко адаптировано к Set<Point>, если вы не найдете библиотеку, которая уже делает это для вас. Примерно так:

public class PointSet implements Set<Point> {
    private final boolean[][] data; 
    public PointSet(int xSize, int ySize) {
        data = new boolean[xSize][ySize];
    }

    @Override
    public boolean add(Point e) {
         boolean hadIt = data[e.x][e.y];
         data[e.x][e.y] = true;
         return hadIt;
    }

    @Override
    public boolean contains(Object o) {
        Point p = (Point) o;
        return data[p.x][p.y];
    }

    //...other methods of Set<Point>...
}

Answer 2

Я бы использовал несколько коллекций Trove структур данных.

Если ваши точки хранятся в виде пары int или пары float, вы можете упаковать их в long: 32 бита для x-координаты и 32 бита для y-координаты. Затем вы можете использовать TLongHashSet, который HashSet оптимизирован для работы с примитивными данными (он будет быстрее и будет занимать меньше памяти по сравнению с обычными наборами Java).

Если у вас есть int координаты, это будет что-то вроде

static private long computeKey(int h1, int h2)
{           
    return ((long)h1) << 32 | h2;
}

чтобы вычислить ключ и затем использовать его

TLongHashSet set = new TLongHashSet()
set.add(long v);
set.addAll(long[] v);
set.containsAll(..);

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

Answer 3

HashSet. Его O (1) среднее. Если вы хотите true O (1), вы можете сделать обертку для вашего объекта, которая имеет ссылку на коллекцию. Таким образом, вы не можете просто сравнить it с имеющейся у вас коллекцией.

Answer 4

Как часто вам приходится обновлять коллекцию по сравнению с ее поиском? На основании этого вы должны выбрать подходящую структуру данных.

Point2D реализует сопоставимость, верно? Тогда вам лучше всего выбрать TreeSet, они невероятно быстрые, и я полагаю, что они полагаются на деревья B +, которые, как вы знаете, используются в реальных базах данных и файловых системах.

Если вы думаете, что собираетесь вносить достаточное количество обновлений в структуру, посмотрите SkipList. Он гарантирует O (журнал (операции)) ** ПРИМЕЧАНИЕ, это для ВСЕХ операций, которые вы делаете, нет гарантии относительно времени выполнения одной операции)

Answer 5

Вы можете попробовать какой-то сортированный набор, например, набор деревьев, поскольку вы можете выполнять бинарный поиск по нему.