Список отсортированных массивов в Java

Question

Я сбит с толку, что не могу найти быстрый ответ на это.По сути, я ищу структуру данных в Java, которая реализует интерфейс java.util.List, но хранит ее члены в отсортированном порядке.Я знаю, что вы можете использовать обычный ArrayList и использовать Collections.sort() для него, но у меня есть сценарий, в котором я иногда добавляю и часто получаю элементы из своего списка, и я не хочу сортировать его каждый раз, когда явосстановить участника в случае добавления нового.Может кто-нибудь указать мне на такую ​​вещь, которая существует в JDK или даже сторонних библиотеках?

EDIT : структура данных должна будет сохранять дубликаты.

РЕЗЮМЕ ОТВЕТА : Я нашел все это очень интересным и многому научился.Aioobe, в частности, заслуживает упоминания за его настойчивость в попытке выполнить мои требования выше (в основном, отсортированная реализация java.util.List, которая поддерживает дубликаты).Я принял его ответ как наиболее точный из того, что я просил, и больше всего думал о последствиях того, что я искал, даже если то, что я спрашивал, не совсем то, что мне нужно.

Проблема с тем, что я просил, заключается в самом интерфейсе List и концепции необязательных методов в интерфейсе.Процитируем javadoc:

Пользователь этого интерфейса имеет точный контроль над тем, где в списке каждый элемент вставлен.

Вставка в отсортированный список не имеетТочный контроль над точкой вставки.Затем вы должны подумать, как вы будете обрабатывать некоторые методы.Возьмите add, например:

public boolean add (Object o)

 Appends the specified element to the end of this list (optional operation).

Теперь вы находитесь в неудобной ситуации: 1) Нарушение контрактаи реализации отсортированной версии add 2) Позволяя add добавить элемент в конец списка, нарушая ваш отсортированный порядок 3) Оставляя add (как необязательный), выбрасывая UnsupportedOperationException и реализуя другой метод, которыйдобавляет элементы в отсортированном порядке.

Вариант 3, вероятно, является лучшим, но я нахожу нежелательным иметь метод add, который вы не можете использовать, и другой метод sortedAdd, которого нет в интерфейсе.

Другие связанные решения (без определенного порядка):

• java.util.PriorityQueue , который, вероятно, ближе всего к тому, что мне было нужно, чем то, что я просил.В моем случае очередь - не самое точное определение коллекции объектов, но функционально она делает все, что мне нужно.
• net.sourceforge.nite.util.SortedList .Однако эта реализация нарушает контракт интерфейса List, реализуя сортировку в методе add(Object obj), и причудливо не имеет метода без эффекта для add(int index, Object obj).По общему мнению, throw new UnsupportedOperationException() может быть лучшим выбором в этом сценарии.
• TreeMultiSet Guava Реализация набора, которая поддерживает дубликаты
• ca.odell.glazedlists.SortedList Этот класс содержит оговорку в своем javadoc: Warning: This class breaks the contract required by List

Answer 1

Минималистичное решение

Вот «минимальное» решение.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

Вставка выполняется за линейное время, но это все равно, что вы получите, используя ArrayList в любом случае (все элементы справа от вставленного элемента должны быть смещены так или иначе).

Вставка чего-то несопоставимого приводит к исключению ClassCastException. (Этот подход также применяется PriorityQueue: Очередь приоритетов, основанная на естественном упорядочении, также не позволяет вставлять несопоставимые объекты (это может привести к ClassCastException). )

Переопределение List.add

Обратите внимание, что переопределение List.add (или List.addAll в этом отношении) для вставки элементов отсортированным способом будет прямым нарушением спецификации интерфейса . То, что вы могли бы сделать, это переопределить этот метод, чтобы бросить UnsupportedOperationException.

Из документов List.add:

boolean add(E e)
Добавляет указанный элемент в конец этого списка (необязательная операция).

Одинаковые рассуждения применимы к обеим версиям add, обеим версиям addAll и set. (Все из которых являются необязательными операциями в соответствии с интерфейсом списка.)

Некоторые тесты

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

.... печать:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Answer 2

Использование java.util.PriorityQueue.

Answer 3

Вы можете попробовать Гуава TreeMultiSet .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Answer 4

Посмотрите на SortedList

Этот класс реализует отсортированный список. Он построен с помощью компаратора, который может сравнивать два объекта и сортировать объекты соответственно. Когда вы добавляете объект в список, он вставляется в правильном месте. Объект, равный по данным компаратора, будет находиться в списке в том порядке, в котором они были добавлены в этот список. Добавляйте только те объекты, которые компаратор может сравнивать.

---

Когда список уже содержит объекты, которые равны по сравнению с компаратором, новый объект будет вставлен сразу после этих других объектов.

Answer 5

Подход Айобе - это путь. Я хотел бы предложить следующее улучшение по сравнению с его решением.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

Решение aioobe становится очень медленным при использовании больших списков. Использование того факта, что список отсортирован, позволяет нам найти точку вставки для новых значений с помощью бинарного поиска.

Я бы также использовал композицию вместо наследования, что-то вроде

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Answer 6

Списки обычно сохраняют порядок, в котором элементы добавляются.Вам определенно нужен список , или вам подойдет сортированный набор (например, TreeSet<E>)?Вам нужно сохранить дубликаты?

Answer 7

Это может быть слишком тяжело для вас, но GlazedLists имеет SortedList , который идеально подходит для использования в качестве модели таблицы или JList

Answer 8

Вы можете создать подкласс ArrayList и вызывать Collections.sort (this) после добавления любого элемента - для этого вам потребуется переопределить две версии add и две addAll.

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

Answer 9

У меня была такая же проблема.Поэтому я взял исходный код java.util.TreeMap и написал IndexedTreeMap .Он реализует мой собственный IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

Реализация основана на обновлении весов узлов в красно-черном дереве при его изменении.Вес - это количество дочерних узлов под данным узлом, плюс один - «я».Например, когда дерево поворачивается влево:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight просто обновляет веса до корня:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

И когда нам нужно найти элемент по индексу, вотреализация, которая использует веса:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Также очень удобно находить индекс ключа:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Результат этой работы можно найти на http://code.google.com/p/indexed-tree-map/

TreeSet / TreeMap (а также их индексированные аналоги из проекта indexed-tree-map) не допускают дублирования ключей, вы можете использовать 1 ключ для массива значений.Если вам нужен SortedSet с дубликатами, используйте TreeMap со значениями в качестве массивов.Я бы сделал это.

Answer 10

Поскольку предлагаемые в настоящее время реализации, которые реализуют отсортированный список, нарушая API-интерфейс Collection, имеют собственную реализацию дерева или чего-то подобного, мне было любопытно, как будет реализовываться реализация, основанная на TreeMap.(Особенно потому, что TreeSet также базируется на TreeMap)

Если кому-то это тоже интересно, он или она может свободно его изучить:

TreeList

Является частью базовой библиотеки , вы, конечно, можете добавить ее через зависимость Maven.(Лицензия Apache)

В настоящее время реализация, похоже, довольно хорошо сравнивается на том же уровне, что и SavaMultiSet guava и TreeList библиотеки Apache Commons.

Но я был бы рад, если бытолько я бы протестировал реализацию, чтобы убедиться, что я не пропустил что-то важное.

С наилучшими пожеланиями!