Как сделать отсортированный набор с O (1) произвольным доступом по индексу

Question

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

• Я могу использовать TreeSet, который удаляет дубликаты и сортирует все по порядку, но не может получить по индексу.для извлечения по индексу я могу сделать для него ArrayList и addAll элементов, но это addAll занимает много времени.

или

• Я могуиспользуйте ArrayList, вставьте необходимые, а затем удалите дубликаты каким-либо другим методом, затем используйте метод Collections.sort для сортировки элементов.

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

Answer 1

В коллекции общих ресурсов есть тип данных, называемый SetUniqueList, который, я считаю, полностью соответствует вашим потребностям.Проверьте это:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html

Answer 2

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

Настоящий признак , как указано в комментарии в ОП, состоит в том, что для помещения строк в TreeSet требуется 700 мс, а еще 700 мс для копирования этого TreeSet в ArrayList. Очевидно, что программа не делает то, о чем думает ОП, поскольку копирование должно занимать не более нескольких микросекунд. Фактически, приведенная ниже программа, работающая на моем древнем Thinkpad, занимает всего 360 мс, чтобы создать 100 000 случайных строк, поместить их в TreeSet и скопировать этот TreeSet в ArrayList.

Тем не менее, ОП выбрал ответ (дважды). Возможно, если / когда ОП решит подумать о реальной проблеме, этот пример SSCCE будет полезен. Это CW, так что не стесняйтесь редактировать его.

---

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;


public class Microbench
{
    public static void main(String[] argv)
    throws Exception
    {        
        ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
        long start = threadBean.getCurrentThreadCpuTime();
        executeTest();
        long finish = threadBean.getCurrentThreadCpuTime();
        double elapsed = (finish - start) / 1000000.0;
        System.out.println(String.format("elapsed time = %7.3f ms", elapsed));
    }


    private static List<String> executeTest()
    {
        String[] data = generateRandomStrings(100000);

        TreeSet<String> set = new TreeSet<String>();
        for (String s : data)
            set.add(s);

        return new ArrayList<String>(set);
    }


    private static String[] generateRandomStrings(int size)
    {
        Random rnd = new Random();
        String[] result = new String[size];
        for (int ii = 0 ; ii < size ; ii++)
            result[ii] = String.valueOf(rnd.nextLong());
        return result;
    }
}

Answer 3

Вы можете использовать вторую идею:

Я могу использовать ArrayList, вставить требуемые, а затем удалить дубликаты другим методом, а затем использовать метод Collections.sort для сортировки элементов.

, но вместо удаления дубликатов перед сортировкой вы можете сначала отсортировать ArrayList, затем все дубликаты находятся на последовательных позициях и впоследствии могут быть удалены за один проход.

На этом этапеоба ваших метода имеют одинаковую общую сложность: O (N * logN), и стоит отметить, что вы все равно не сможете получить отсортированную последовательность быстрее, чем эта (без дополнительной эксплуатации некоторых знаний о значениях).

Answer 4

Производительность зависит от того, как часто элементы добавляются и как часто они будут доступны по индексу.

Я могу использовать TreeSet, который удаляет дубликаты и сортирует все по порядку, но не может получить данные по индексу.для поиска по индексу я могу создать для него элементы arraylist и addall, но это addAll занимает много времени.

List.addAll (yourSortedSet) будет каждый раз занимать по крайней мере O (n) время и пространствовы хотите получить доступ к SortedSet как списку (т.е. по индексу элемента).

Я могу использовать ArrayList, вставить необходимый, а затем удалить дубликаты другим методом, а затем использовать метод Collections.sort для сортировки.elements.

сортировка, безусловно, займет больше, чем O (n) каждый раз, когда вы хотите отсортированный просмотр вашего списка.

Еще одно решение

Если вы не выбираете по индексу очень часто, то более эффективно сделать это следующим образом:

Просто сохраните String s в SortedSet, можно расширить TreeSet и предоставить /реализовать свой собственный метод get(int i), в котором вы выполняете итерации до i-го элемента и возвращаете этот элемент.В худшем случае это будет O (n), иначе намного меньше.Таким образом, вы не выполняете любое сравнение, преобразование или копирование строк.Никакого дополнительного места не требуется.

Answer 5

Я также столкнулся с проблемой нахождения элемента в определенной позиции в TreeMap. Я расширил дерево весами, которые позволяют обращаться к элементам по индексу и находить элементы по индексам. Проект называется indexed-tree-map http://code.google.com/p/indexed-tree-map/. Реализация поиска индекса элемента или элемента по индексу в отсортированной карте основана не на линейной итерации, а на бинарном поиске по дереву. Обновление весов дерева также основано на вертикальном восхождении дерева. Так что никаких линейных итераций.

Answer 6

есть два способа сделать это, используя LinkedMap, где каждый элемент на карте уникален, или добавить собственный метод списка и переопределения add

import java.util.ArrayList;

public class MyList<V> extends ArrayList<V>{

    private static final long serialVersionUID = 5847609794342633994L;

    public boolean add(V object) {
        //make each object unique
        if(contains(object)){
            return false;
        }

        //you can make here ordering and after save it at position 

        //your ordering here

        //using extended method add
        super.add(yourposition,object);
    }
}

Answer 7

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

Answer 8

Используя Hashmap, вы решите проблему с уникальными значениями и сортируете ее некоторыми методами сортировки.Если это возможно, используйте быструю сортировку.

Answer 9

Если вы привязаны к List в начале и в конце операции, преобразуйте его в Set с конструктором «copy» (или addAll) после заполнения элементов, это удалит дубликаты. Если вы конвертируете его в TreeSet с соответствующим Comparator, он даже отсортирует его. Затем вы можете преобразовать его обратно в List.

Answer 10

Я не уверен, ты тестируешь карту?Я имею в виду использовать вашу строку в качестве ключа в TreeMap.

На карте это O (1) для ключа, чтобы найти свою позицию (хеш-значение).И KeySet TreeMap вернет отсортированный набор ключей в TreeMap.

Соответствует ли это вашему требованию?