Как я могу получить поведение Sorted List в Java без использования Collections.sort()?
Я понимаю, что Java не обладает отсортированным списком по различным концептуальным причинам, но рассмотрим случай, когда мне нужно иметь коллекцию, которая похожа на приоритетную очередь, но также предоставляет мне произвольный доступ (индексируемый), другими словами, мне нужен Список, который следует за определенным порядком. Я бы предпочел не использовать Collections.sort()
Предпочтительные ограничения работы:
получить - O(1) (произвольный доступ на основе индекса)
поиск - O (войти n)
вставить - O(log n)
удалить - O (войти n)
Итератор над коллекцией должен дать мне все элементы в отсортированном порядке (на основе предопределенного Comparator предоставляется во время создания структуры данных)
Я бы предпочел использовать для этого встроенную библиотеку Java, но не стесняйтесь предлагать и внешние библиотеки.
РЕДАКТИРОВАТЬ: TreeSet не будет делать, так как доступ на основе индекса затруднен, использование коллекций оболочек также не лучший выбор, так как удаление подразумевает, что мне нужно удалить из обеих коллекций.
EDIT2: мне не удалось найти реализацию и / или документацию для indexable skip list это кажется немного уместным, кто-нибудь может мне помочь найти его? Любые комментарии за или против предложенной структуры данных также приветствуются.
РЕДАКТИРОВАТЬ 3: Хотя это, возможно, не самый лучший ответ, я хочу добавить этот фрагмент кода, который я написал, чтобы любой, у кого есть подобные проблемы для необходимости отсортированного списка, мог использовать его, если сочтет его полезным.
Проверьте наличие ошибок (если они есть) и предложите улучшения (особенно для sortedSubList метод)
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
public class SortedList<E> extends ArrayList<E> {
private final Comparator<? super E> comparator;
public SortedList(Comparator<? super E> comparator) {
this.comparator = comparator;
}
public SortedList(int initialCapacity, Comparator<? super E> comparator) {
super(initialCapacity);
this.comparator = comparator;
}
@Override
public boolean add(E e) {
if (comparator == null)
return super.add(e);
if (e == null)
throw new NullPointerException();
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), e) == 0) {
super.add(mid, e);
return true;
}
if (comparator.compare(get(mid), e) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
super.add(start, e);
return true;
}
@Override
public boolean contains(Object o) {
if (comparator == null)
return super.contains(o);
if (o == null)
return false;
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return true;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
@Override
public int indexOf(Object o) {
if (comparator == null)
return super.indexOf(o);
if (o == null)
throw new NullPointerException();
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return mid;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return -(start+1);
}
@Override
public void add(int index, E e) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public E set(int index, E e) {
throw new UnsupportedOperationException();
}
public SortedList<E> sortedSubList(int fromIndex, int toIndex) {
SortedList<E> sl = new SortedList<>(comparator);
for (int i = fromIndex; i < toIndex; i++)
sl.add(get(i));
return sl;
}
}
3 ответа
Трудно получить индексирование O(1) и вставку / удаление O(log n) в одной структуре данных. Индексирование O(1) означает, что мы не можем позволить себе переход по ссылкам при индексации дерева, списка, списка пропусков или другой структуры данных на основе ссылок, в то время как модификация O(log n) означает, что мы не можем позволить сместить половину элементы массива на каждой вставке. Я не знаю, возможно ли выполнить эти требования одновременно.
Если мы ослабим одно из этих требований, все станет намного проще. Например, O(log n) для всех операций может быть достигнуто с помощью индексируемого списка пропусков или самобалансирующегося BST с узлами, которые отслеживают размер поддерева, укорененного в узле. Однако ни один из них не может быть построен поверх списка пропусков или BST в стандартной библиотеке Java, поэтому вам, вероятно, потребуется установить другую библиотеку или написать собственную структуру данных.
O(1) индексирование, O(log n) поиск и O (n) вставка и удаление могут быть выполнены, сохраняя отсортированный ArrayList и используя Collections.binarySearch искать элементы или вставлять / удалять позиции. Вам никогда не нужно звонить Collections.sort, но вам все равно нужно вызвать методы ArrayList O (n) для вставки и удаления. Это, вероятно, самый простой вариант для сборки поверх встроенных инструментов Java. Обратите внимание, что в последних версиях Java Collections.sort адаптивная сортировка, которая будет принимать O(n) время для сортировки массива, в котором только последний элемент находится не в порядке сортировки, так что вы, вероятно, можете сойти с рук, полагаясь на Collections.sort, Однако это деталь реализации, которой альтернативные реализации Java не должны следовать.
Если вашей основной целью является O(1) для индексированного поиска (get()), то вы можете реализовать свой собственный класс реализации List, опираясь на массив, используя Arrays.binarySearch(),
retrieve: get(int) - O(1) - array index
search: contains(Object) - O(log n) - binarySearch
indexOf(Object) - O(log n) - binarySearch
insert: add(E) - O(n) - binarySearch + array shift
delete: remove(int) - O(n) - array shift
remove(Object) - O(n) - binarySearch + array shift
add(E) метод нарушает List определение (приложение), но согласуется с Collection определение.
Следующие методы должны бросить UnsupportedOperationException:
add(int index, E element)
addAll(int index, Collection<? extends E> c)
set(int index, E element)
Если дублирующиеся значения не допускаются, что может быть логическим ограничением, рассмотрите также реализацию NavigableSet, который является SortedSet,
Создайте пользовательскую коллекцию, которая поддерживается ArrayList и TreeSet. Делегируйте произвольный доступ к ArrayList и поиск к TreeSet. Конечно, это означает, что каждая операция записи будет очень дорогой, поскольку каждый раз придется сортировать ArrayList. Но чтение должно быть очень эффективным.