Я новичок в Java. Укажите, какие коллекции могут/должны использоваться для ведения отсортированного списка на Java. Я пробовал Map и Set, но они не были тем, что я искал.
Сортированная коллекция в Java
Ответ 1
Это происходит очень поздно, но есть класс в JDK только для того, чтобы иметь отсортированный список. Он называется (несколько не в порядке с другими интерфейсами Sorted*) "java.util.PriorityQueue". Он может сортировать либо Comparable<?>, либо использовать Comparator.
Разница с List, отсортированная с использованием Collections.sort(...), заключается в том, что она будет поддерживать частичный порядок во все времена с использованием производительности ввода (log (n)) с использованием структуры данных кучи, тогда как вставка в отсортированную ArrayList будет O (n) (т.е. с помощью двоичного поиска и перемещения).
Однако, в отличие от List, PriorityQueue не поддерживает индексированный доступ (get(5)), единственный способ доступа к элементам в куче - это вынуть их по одному за раз (таким образом, имя PriorityQueue).
Ответ 2
TreeMap и TreeSet предоставят вам итерацию по содержимому в отсортированном порядке. Или вы можете использовать ArrayList и использовать Collections.sort() для его сортировки. Все эти классы находятся в java.util
Ответ 3
Если вы хотите сохранить отсортированный список, который будет часто изменять (т.е. структуру, которая, помимо сортировки, позволяет дублировать и чьи элементы могут быть эффективно ссылаясь на индекс), затем используйте ArrayList, но когда вам нужно вставить элемент, всегда используйте Collections.binarySearch(), чтобы определить индекс, в который вы добавляете данный элемент. Последний метод сообщает вам индекс, который вам нужно вставить, чтобы сохранить список в отсортированном порядке.
Ответ 4
Используйте Google Guava TreeMultiset класс. Guava имеет впечатляющий API коллекций.
Одной из проблем, связанных с предоставлением реализации List, поддерживающей отсортированный порядок, является обещание, данное в JavaDocs метода add().
Ответ 5
Ответ 6
Есть несколько вариантов. Я бы предложил TreeSet, если вы не хотите, чтобы дубликаты и объекты, которые вы вставляете, сопоставимы.
Для этого также можно использовать статические методы класса Collections.
Смотрите Коллекции # sort (java.util.List) и TreeSet для получения дополнительной информации.
Ответ 7
Если вы просто хотите отсортировать список, используйте любой List и используйте Collections.sort(). Если вы хотите убедиться, что элементы в списке уникальны и всегда отсортированы, используйте SortedSet.
Ответ 8
То, что я сделал, - это реализовать List с внутренним экземпляром со всеми делегированными методами.
public class ContactList implements List<Contact>, Serializable {
private static final long serialVersionUID = -1862666454644475565L;
private final List<Contact> list;
public ContactList() {
super();
this.list = new ArrayList<Contact>();
}
public ContactList(List<Contact> list) {
super();
//copy and order list
List<Contact>aux= new ArrayList(list);
Collections.sort(aux);
this.list = aux;
}
public void clear() {
list.clear();
}
public boolean contains(Object object) {
return list.contains(object);
}
После этого я внедрил новый метод "putOrdered", который вставляет правильную позицию, если элемент не существует или не заменяется на всякий случай, если он существует.
public void putOrdered(Contact contact) {
int index=Collections.binarySearch(this.list,contact);
if(index<0){
index= -(index+1);
list.add(index, contact);
}else{
list.set(index, contact);
}
}
Если вы хотите разрешить повторяющиеся элементы, вместо этого просто реализуйте addOrdered (или оба).
public void addOrdered(Contact contact) {
int index=Collections.binarySearch(this.list,contact);
if(index<0){
index= -(index+1);
}
list.add(index, contact);
}
Если вы хотите избежать вставок, вы также можете исключить исключение операции и исключить операцию "добавить" и "установить".
public boolean add(Contact object) {
throw new UnsupportedOperationException("Use putOrdered instead");
}
... а также вы должны быть осторожны с методами ListIterator, потому что они могут изменить ваш внутренний список. В этом случае вы можете вернуть копию внутреннего списка или снова создать исключение.
public ListIterator<Contact> listIterator() {
return (new ArrayList<Contact>(list)).listIterator();
}
Ответ 9
TreeSet не будет работать, потому что они не позволяют дублировать, и они не предоставляют метод для извлечения элемента в определенной позиции. PriorityQueue не будет работать, потому что он не позволяет получать элементы в определенной позиции, что является основным требованием для списка. Я думаю, вам нужно реализовать собственный алгоритм для поддержки отсортированного списка в Java с временем вставки O (logn), если вам не нужны дубликаты. Возможно, решение может использовать TreeMap, где ключ является подклассом элемента, переопределяющим метод equals, так что дубликаты разрешены.
Ответ 10
Использование LambdaJ
Вы можете решить эти задачи с помощью LambdaJ, если вы используете предыдущие версии для java 8. Вы можете найти его здесь: http://code.google.com/p/lambdaj/
Здесь у вас есть пример:
Сортировка итераций
List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
}
});
Сортировка с LambdaJ
List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge());
Конечно, наличие такой красоты влияет на производительность (в среднем 2 раза), но вы можете найти более читаемый код?
Сортировка с java 8 с использованием выражения лямбда
Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
Ответ 11
Самый эффективный способ реализовать отсортированный список, как вы хотите, - это реализовать индексируемый скип-лист, как здесь: Wikipedia: Индексируемый скип-лист. Это позволило бы иметь вставки/удаления в O (log (n)) и позволило бы иметь индексированный доступ одновременно. И это также позволило бы дубликаты.
Skiplist - довольно интересная и, я бы сказал, недооцененная структура данных. К сожалению, в базовой библиотеке Java нет индексированной реализации списка пропусков, но вы можете использовать одну из реализаций с открытым исходным кодом или реализовать ее самостоятельно. Существуют регулярные реализации Skiplist, такие как ConcurrentSkipListSet и ConcurrentSkipListMap
Ответ 12
Проблема с PriorityQueue заключается в том, что она подкрепляется простым массивом, а логика, которая получает упорядоченные элементы, выполняется "queue [2 * n + 1] и queue [2 * (n + 1)]" thingie. Он отлично работает, если вы просто тянете с головы, но делает его бесполезным, если вы пытаетесь в какой-то момент называть .toArray.
Я обойду эту проблему, используя com.google.common.collect.TreeMultimap, но я поставляю собственный Компаратор для значений, завернутых в Ordering, который никогда не возвращает 0.
ех. для Double:
private static final Ordering<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {
@Override
public int compare(Double d1, Double d2)
{
if (d1 < d2) {
return -1;
}
else {
return 1;
}
}
});
Таким образом, я получаю значения в порядке, когда я вызываю .toArray(), а также дубликаты.
Ответ 13
Что вы хотите - это двоичное дерево поиска. Он поддерживает сортированный порядок, предлагая логарифмический доступ для поиска, удаления и вставки (если у вас нет вырожденного дерева, а затем оно линейно). Его довольно легко реализовать, и вы даже можете заставить его реализовать интерфейс List, но тогда индексный доступ становится сложным.
Второй подход состоит в том, чтобы иметь ArrayList, а затем реализацию сорта пузырьков. Поскольку вы вставляете или удаляете один элемент за раз, время доступа для вставок и абзацев является линейным. Поиски являются логарифмическими и постоянными доступа к индексу (времена могут быть разными для LinkedList). Единственный необходимый вам код - 5, может быть, 6 строк пузырьковой сортировки.
Ответ 14
Вы можете использовать Arraylist и Treemap, так как вы сказали, что хотите повторять значения, но тогда вы не можете использовать TreeSet, хотя он также сортируется, но вам нужно определить компаратор.
Ответ 15
Для Set вы можете использовать TreeSet. TreeSet упорядочивает элементы на основе естественного порядка или любого порядка сортировки, передаваемого в Comparable для этого конкретного объекта. Для карты используйте TreeMap. TreeMap обеспечивает сортировку по ключам. Чтобы добавить объект в качестве ключа в TreeMap, этот класс должен реализовать сопоставимый интерфейс, который, в свою очередь, заставляет реализовать метод сравнения с(), который содержит определение порядка сортировки. http://techmastertutorial.in/java-collection-impl.html
Ответ 16
Используйте метод sort() для сортировки списка, как показано ниже:
List list = new ArrayList();
//add elements to the list
Comparator comparator = new SomeComparator();
Collections.sort(list, comparator);
Для справки см. ссылку: http://tutorials.jenkov.com/java-collections/sorting.html
Ответ 17
Используйте TreeSet, который дает элементы в отсортированном порядке. ИЛИ используйте Collection.sort() для внешней сортировки с помощью Comparator().
Ответ 18
import java.util.TreeSet;
public class Ass3 {
TreeSet<String>str=new TreeSet<String>();
str.add("dog");
str.add("doonkey");
str.add("rat");
str.add("rabbit");
str.add("elephant");
System.out.println(str);
}
Ответ 19
с Java 8 Comparator, если мы хотим отсортировать список, то вот 10 самых населенных городов мира, и мы хотим отсортировать их по названию, как сообщает Time. Осака, Япония.... Мехико, Мексика.... Пекин, Китай.... Сан-Паулу, Бразилия.... Мумбаи, Индия.... Шанхай, Китай.... Дели, Индия.... Токио, Япония.
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class SortCityList {
/*
* Here are the 10 most populated cities in the world and we want to sort it by
* name, as reported by Time. Osaka, Japan. ... Mexico City, Mexico. ...
* Beijing, China. ... São Paulo, Brazil. ... Mumbai, India. ... Shanghai,
* China. ... Delhi, India. ... Tokyo, Japan.
*/
public static void main(String[] args) {
List<String> cities = Arrays.asList("Osaka", "Mexico City", "São Paulo", "Mumbai", "Shanghai", "Delhi",
"Tokyo");
System.out.println("Before Sorting List is:-");
System.out.println(cities);
System.out.println("--------------------------------");
System.out.println("After Use of List sort(String.CASE_INSENSITIVE_ORDER) & Sorting List is:-");
cities.sort(String.CASE_INSENSITIVE_ORDER);
System.out.println(cities);
System.out.println("--------------------------------");
System.out.println("After Use of List sort(Comparator.naturalOrder()) & Sorting List is:-");
cities.sort(Comparator.naturalOrder());
System.out.println(cities);
}
}
Ответ 20
Сортировка ArrayList в соответствии с заданными пользователем критериями.
Модельный класс
class Student
{
int rollno;
String name, address;
public Student(int rollno, String name, String address)
{
this.rollno = rollno;
this.name = name;
this.address = address;
}
public String toString()
{
return this.rollno + " " + this.name + " " + this.address;
}
}
Класс сортировки
class Sortbyroll implements Comparator<Student>
{
public int compare(Student a, Student b)
{
return a.rollno - b.rollno;
}
}
Основной класс
class Main
{
public static void main (String[] args)
{
ArrayList<Student> ar = new ArrayList<Student>();
ar.add(new Student(111, "bbbb", "london"));
ar.add(new Student(131, "aaaa", "nyc"));
ar.add(new Student(121, "cccc", "jaipur"));
System.out.println("Unsorted");
for (int i=0; i<ar.size(); i++)
System.out.println(ar.get(i));
Collections.sort(ar, new Sortbyroll());
System.out.println("\nSorted by rollno");
for (int i=0; i<ar.size(); i++)
System.out.println(ar.get(i));
}
}
Выход
Unsorted
111 bbbb london
131 aaaa nyc
121 cccc jaipur
Sorted by rollno
111 bbbb london
121 cccc jaipur
131 aaaa nyc