Хороший Отсортированный Список для Java
Я ищу хороший отсортированный список для Java. Поиск с помощью Google вокруг дает мне некоторые подсказки об использовании TreeSet/TreeMap. Но эти компоненты являются отсутствием одной вещи: произвольный доступ к элементу в наборе. Например, я хочу получить доступ к энному элементу в отсортированном наборе, но с TreeSet, я должен выполнить итерации по другим n-1 элементам, прежде чем я смогу добраться там. Это были бы отходы, так как у меня будет до нескольких тысяч элементов в моем Наборе.
В основном я ищу некоторую вещь, подобную отсортированному списку в.NET, со способностью добавить элемент быстро, удалить элемент быстро и иметь произвольный доступ к любому элементу в списке.
Имеет этот вид отсортированного списка реализованный где-нибудь?Спасибо.
Отредактированный
Мой интерес к SortedList выращивает из этого проблемы: Я должен, ведет список многих тысяч объектов (и может расти ко многим сотням тысяч). Эти объекты будут сохранены к базе данных. Я хочу случайным образом выбрать немного десятков элемента из целого списка. Так, я пытался вести разделенный список на памяти, который содержит первичные ключи (Длинные числа) всех объектов. Я должен добавить/удалить ключи из списка, когда объект добавляется / удаленный из базы данных. Я использую ArrayList прямо сейчас, но я боюсь, что ArrayList не удовлетворил бы ему, когда количество записей растет. (Предположите, что необходимо выполнить итерации более чем нескольких сотен тысяч элементов каждый раз, когда объект удален из базы данных). Назад ко времени, когда я сделал программирование.NET, затем я буду использовать отсортированный Список (Список является классом.NET, что когда-то Отсортированный набор свойств к истинному, поддержит порядок своего элемента и обеспечит двоичный поиск, что справка удаляет/вставляет очень быстрый элемент). Я надеюсь, что могу найти некоторую вещь подобной от Java BCL, но к несчастью, я не нашел хорошее соответствие.
5 ответов
Похоже, вам нужна структура списка с очень быстрым удалением и произвольным доступом по индексу (не по ключу) раз. ArrayList дает последнее, а HashMap или TreeMap дает первое.
В коллекциях Apache Commons есть одна структура, которая может быть тем, что вы ищете, - TreeList . JavaDoc указывает, что он оптимизирован для быстрой вставки и удаления по любому индексу в списке. Если вам также нужны дженерики, это вам не поможет.
Фуонг:
Сортировка 40 000 случайных чисел:
0,022 секунды
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class test
{
public static void main(String[] args)
{
List<Integer> nums = new ArrayList<Integer>();
Random rand = new Random();
for( int i = 0; i < 40000; i++ )
{
nums.add( rand.nextInt(Integer.MAX_VALUE) );
}
long start = System.nanoTime();
Collections.sort(nums);
long end = System.nanoTime();
System.out.println((end-start)/1e9);
}
}
Поскольку сортировка требуется редко, согласно вашей постановке задачи, это, вероятно, более эффективнее, чем должно быть.
В зависимости от того, как вы используете список, может быть стоит использовать TreeSet, а затем использовать метод toArray () в конце. У меня был случай, когда мне нужен отсортированный список, и я обнаружил, что TreeSet + toArray () работает намного быстрее, чем добавление в массив и сортировка слиянием в конце.
Как насчет использования HashMap ? Вставка, удаление и извлечение - это все операции O (1). Если вы хотите отсортировать все, вы можете взять список значений на карте и запустить их с помощью алгоритма сортировки O (n log n).
править
Быстрый поиск нашел LinkedHashMap , который поддерживает порядок вставки ваших ключей. Это не точное решение, но довольно близкое.
GlazedLists имеет очень, очень хорошую реализацию отсортированного списка