В моем приложении мне нужно проверить коллекцию 2D-координат (x, y), чтобы увидеть, имеется ли заданная координата в коллекции, она должна быть как можно быстрее, и к ней будет доступен только один поток. (для проверки на столкновение)Какова самая быстрая коллекция Java для однопоточных функций Contains (Point (x, y))?
Может ли кто-нибудь дать мне толчок в правильном направлении?
Абсолютное быстро я могу думать о том, чтобы поддерживать матрицу 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 матрица будет работать. Ясно, что это было бы быстро, если бы матрица была создана только один раз и, возможно, обновлена, поскольку Points добавлены в коллекцию.
Короче говоря, основные коллекции не идеальны для этого (хотя приблизился бы 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>...
}
Согласовано: если вы не хотите поддерживать всю «логическую» матрицу, «HashSet», вероятно, лучший выбор. – VeeArr
Добавлена реализация Set, основанная на этом принципе; обратите внимание, что вам лучше всего указать, где/если он нарушает контракт Set. Например, это не проверяет границы, поэтому, если вы добавите Point out-of-range, это не удастся. –
Вы можете попробовать какой-то сортированный набор, например treeet, так как вы можете выполнять бинарные поиски на нем.
двоичный поиск - O (log N) в отличие от решений O (1), указанных в других ответах. –
хорошо, я догадываюсь, что вы теряете в скорости, которую вы можете получить в использовании пространства и гибкости. – Vinh
Я бы пошел использовать некоторые структуры данных Trove collections.
Если точки сохраняются в виде пару int или пару float вы можете упаковать их в long: 32 бит для й коорда и 32 бит для у-коорда. Затем вы можете использовать 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.
Хорошее предложение, хотя стоит отметить, что вы, вероятно, захотите изменить стратегию хэширования, используемую 'TLongHashSet'. По умолчанию используется 'return ((int) (значение^(значение >>> 32))) * 31;' что хорошо для случайных распределенных данных, но ужасно для данных, подобных этому. Например, такие простые данные, как (0,1) и (1,0), приведут к хеш-коллизии. Это не хорошо для длин, где первые 32 бита имеют корреляцию с последними 32 битами. –
Фактически, я запустил ваш 'computeKey' против хэш-функции по умолчанию для данных, включая каждую Точку с X и Y между 0 и 1000, и она генерировала только 1024 уникальных хэша! Это вероятность столкновения хеша 99.90%! –
Да, возможно, вы правы. Я использовал его для проблемы, подобной этой, но имел различное распределение значений, поэтому он работал как шарм (я смог сделать код, который работал на 25% быстрее и сэкономил до 300-400 МБ из 2.0 Gb) – Jack
Как часто вы обновляете коллекцию по сравнению с поиском? На основе этого вы должны выбрать соответствующую структуру данных.
Point2D реализует сравнимые, не так ли? Тогда ваш лучший выбор, вероятно, TreeSet, они невероятно быстры, и я считаю, что они полагаются на деревья B +, которые, как вы знаете, используются в реальных базах данных и файловых системах.
Если вы считаете, что собираетесь внести достаточное количество обновлений в структуру, взгляните на SkipList. Они гарантируют O (журнал (операции)) ** ПРИМЕЧАНИЕ Это для ВСЕХ операций, которые вы выполняете, нет гарантии относительно времени автономной работы)
HashSet. Его O (1) среднее.Если вы хотите, чтобы true O (1), вы можете сделать оболочку для своего объекта, которая имеет ссылку на коллекцию. Таким образом, вы не можете сравнить это с вашей коллекцией.
они целые или плавающие? – Jack