Java TreeSet - Как эффективно вставить и опросить ближайших соседей?

Question

Ищите решение, которое будет работать на складе Java 8, без библиотек.

Я пытаюсь реализовать стандартный алгоритм пересечения линейных сегментов. Это включает в себя отслеживание отсортированной коллекции (по y-координате) сегментов линии, которые в настоящее время «активны».

Часть алгоритма состоит в предположении, что TreeSet actives и новый сегмент строки s:

• вставка s в actives
• поиск ближайших соседей s в actives и выполнение математических операций

У меня есть реализовал это следующим образом:

// left neighbor of s, as though already added
try {
    Segment sa = actives.tailSet(s).first();
    if (math(sa, s) {
        ...
    }
} catch(NoSuchElementException ignore) {}
// right neighbor versus s, as though already added
try {
    Segment sb = actives.headSet(s).last();
    if (math(sb, s) {
        ...
    }
} catch(NoSuchElementException ignore) {}   

// add s => actives
actives.add(s);

Помимо усугубляющих попытки / уловки в случае неудачи first() или last() (что является компромиссом с первым получением подмножества в переменной, ТО проверяет, если оно пустое , ТОГДА продолжая, если нет), реальная проблема, насколько я понимаю, заключается в том, что это неэффективно, а именно:

tailSet(), headSet() и add() все несут O (log (N)) работать на моем TreeSet actives, в то время как алгоритм предполагает, что я могу вставить один раз в O (log (N)), а затем искать соседей в O (1).

Как я могу сделать что-то подобное, но выполнить O (log (N)) бинарный поиск только один раз? Я делаю в 3 раза больше работы, чем необходимо.

Answer 1

Я немного переписал ваш код:

// left neighbor of s, as though already added
SortedSet<Segment> trailSet = actives.tailSet(s);
if (!trailSet.isEmpty()) {
    Segment sa = trailSet.first();
    if (math(sa, s) {
        ...
    }
}

// right neighbor versus s, as though already added
SortedSet<Segment> headSet = actives.headSet(s);
if (!headSet.isEmpty()) {
    Segment sb = headSet.last();
    if (math(sb, s) {
        ...
    }
}

// add s => actives
actives.add(s);

Не нужно ничего ловить (так как вы можете проверить пустоту перед извлечением первого (или последнего) элемента). Это более производительно, так как не вызывает генерацию трассировки стека.

Но вы можете даже go с чем-то лучшим. Согласно https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html, вы можете вызвать метод, который

возвращает наибольший элемент в этом наборе строго меньше, чем заданный элемент, или ноль, если такого элемента нет.

или самый маленький, строго больше. Методы называются lower и higher.

Segment sa = actives.higher(s);
if (sa != null && math(sa, s) {
    ...
}

// right neighbor versus s, as though already added
Segment sb = actives.lower(s);
if (sb != null && math(sb, s) {
    ...
}

// add s => actives
actives.add(s);

Answer 2

Возможно, попробуйте сначала добавить элемент s к actives, затем вызвать actives.lower(s) и actives.higher(s). Документы TreeSet не указывают на сложность этих методов, но они выглядят как O (1) для меня в исходном коде.