Сортировка списка советов по производительности сборников

Question

У меня есть список коллекций, который содержит пары, я должен сохранять список отсортированным по алфавиту по ключу пар коллекций, Мое текущее решение - сохранять список отсортированным, переопределяя метод add, Как в коде ниже.

Примечание: ключ списка пар коллекций всегда такой же, как

(Автомобиль, 1) (Автомобиль, 1)

(Медведь, 1)

Так что мне просто нужнополучить первый ключ пары коллекций для сортировки списка

List<Collection<Pair<String, Integer>>> shufflingResult;

public void init() {
    shufflingResult = new ArrayList<>() {
        public boolean add(Collection<Pair<String, Integer>> c) {
            super.add(c);
            Collections.sort(shufflingResult, new Comparator<Collection<Pair<String, Integer>>>() {
                @Override
                public int compare(Collection<Pair<String, Integer>> pairs, Collection<Pair<String, Integer>> t1) {
                    return pairs.iterator().next().getKey().compareTo(t1.iterator().next().toString());
                }
            });
            return true;
        }
    };
}

Это лучший способ выполнить то, что я ищу?

Answer 1

Производительность - сложная вещь.Лучший алгоритм сортировки будет во многом зависеть от объема и типа данных, а также от того, насколько они случайны.Некоторые алгоритмы лучше всего подходят для частично отсортированных данных, другие для действительно случайных данных.

Вообще говоря, беспокойтесь об оптимизации, пока вы не определите, что рабочий код недостаточно эффективен.Сначала все заработает, а затем определите, где это узкое место.Это может быть не сортировка, а что-то еще.

Java предоставляет хорошие общие алгоритмы сортировки.Вы используете один с Collections.sort ().В Java нет SortedList, , но javafx.base содержит SortedList , который упаковывает предоставленный список и сохраняет сортировку на основе Comparator, предоставленного при создании экземпляра.Это избавит вас от необходимости переопределять базовое поведение реализации List.

Хотя ваш код выглядит так, как будто он может работать, вот несколько советов:

1. pair.iterator () .next (). getKey () сгенерирует NPE, если пары пустые.
2. pair.iterator (). next (). getKey () сгенерирует исключение NoSuchElementException, если пары пустые.
3. pair.iterator (). Next (). GetKey () сгенерирует NPE, если в первой паре нулевой ключ пуст.
4. Все это верно и для t1.
5. Вы сравниваете pair.iterator (). Next (). GetKey () с t1.iterator (). Next (). ToString ().Одним из них является строковое представление пары, а другим - ключ от пары.Это правильно?

Хотя ваш код может гарантировать, что эти условия никогда не произойдут, кто-то может изменить его позже, что приведет к неприятным сюрпризам.Возможно, вы захотите добавить проверки в ваш метод add, чтобы гарантировать, что эти случаи не произойдут.Вызывать исключение IllegalArgumentException, когда аргументы недопустимы, как правило, является хорошей практикой.

Еще одна мысль: поскольку содержимое вашей коллекции всегда одинаковое, и если нет двух коллекций с одинаковыми типами пар, вы должны иметь возможность использоватьSortedMap>> вместо списка.Если вы сравниваете по ключу, этот вид карты будет сортировать вещи для вас.Вы будете put Коллекцию, используя ключ первой пары в качестве ключа карты / входа.keySet(), values() и entrySet() карты будут возвращать Коллекции, которые повторяются в отсортированном порядке.

Answer 2

Если коллекция уже отсортирована и вам нужно только добавить.выполнить бинарный поиск, а затем просто использовать list.add(index,element); сортировку каждый раз, когда вы хотите вставить, это плохо.Вы должны сделать это один раз, а затем просто поддерживать с хорошим порядком вставки.

добавление некоторого кода для отображения bsearch.поскольку тот для коллекций возвратит только совпадения.просто предоставьте список.новый объект.и компаратор, который сортирует список, как вы хотите.если добавляется много элементов, где N> текущий размер списка, вероятно, лучше добавить все, а затем сортировать.

private static void add(List<ThingObject> l, ThingObject t, Comparator<ThingObject> c) {
    if (l != null) {
        if (l.size() == 0) {
            l.add(t);
        } else {
            int index = bSearch(l, t, c);
            l.add(index, t);
        }
    }
}

private static int bSearch(List<ThingObject> l, ThingObject t, Comparator<ThingObject> c) {
    boolean notFound = true;
    int high = l.size() - 1;
    int low = 0;
    int look = (low + high) / 2;
    while (notFound) {
        if (c.compare(l.get(look), t) > 0) {
            // it's to the left of look
            if (look == 0 || c.compare(l.get(look - 1), t) < 0) {
                //is it adjacent?
                notFound = false;
            } else {
                //look again.
                high = look - 1;
                look = (low + high) / 2;
            }
        } else if (c.compare(l.get(look), t) < 0) {
            // it's to the right of look
            if (look == l.size() - 1 || c.compare(l.get(look + 1), t) > 0) {
                //is it adjacent?
                look = look + 1;
                notFound = false;
            } else {
                //look again.
                low = look + 1;
                look = (low + high) / 2;
            }
        } else {
            notFound = false;
        }

    }
    return look;
}