Java: Самый быстрый способ проверить, пересекаются ли несколько битовых векторов / наборов битов? - PullRequest
0 голосов
/ 25 мая 2018

У меня есть массив битовых векторов в форме BitSet в Java.Моя цель - проверить, имеют ли эти битовые векторы пересечения (все имеют 1 с хотя бы в одном бите).Мое текущее решение заключается в использовании и работе, предлагаемой BitSet в Java.

BitSet[] bitVecs = new BitSet[10]

//
// initialize all bit vectors and their lengths are 100 ...
//

BitSet check = new BitSet(100); //  
check.set(0, 100);
for (int i = 0; i < bitVecs.length; i++) {
    check.add(bitVecs[i]);
    if (check.isEmpty())
       return false // we know the bitVecs do not intersect
}

return true; // we know bitVecs intersects

BitSet имеет функцию intersects и должен быть быстрее, чем and, но он проверяет только два битовых вектора и не более.Я ценю, если кто-нибудь знает, как сделать это быстрее.

1 Ответ

0 голосов
/ 25 мая 2018

Я собираюсь сделать некоторые предположения.Похоже, вы будете иметь дело со списком векторов модулей в 10-мерном пространстве.Проблема в том, как определяются векторы.начните с начала координат и идите на 1 единицу в любом направлении, где соответствующее измерение имеет 1 вместо 0. Хорошо, все ваши векторы будут пересекаться в начале координат и в бесконечных точках, если они имеют один и тот же вектор.вектор просто собирается определить наклон линии.вам также понадобится какой-то другой вектор для определения смещения.что вам нужно сделать, это превратить векторы в линии, и тогда вы сможете определить, пересекаются ли они.

...