Вставить в уже отсортированный список

В Java у меня есть класс, известный как TestClass, в котором есть член с именем Name, который является строкой. У меня также есть ArrayList этого типа, который уже отсортирован в алфавитном порядке по имени. Что я хочу сделать, так это найти лучший индекс, в который можно поместить новый экземпляр TestClass. Лучший подход, который я мог придумать, заключается в следующем:

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

По сути, разбейте массив пополам, проверьте, находится ли ваше значение до, после или в этот момент. Если это после, проверьте первую половину массива. В противном случае проверьте второй тайм. Затем повторите. Я понимаю, что этот метод проверяет только по первому символу, но это легко исправить и не относится к моей основной проблеме. Для некоторых сценариев этот подход работает достаточно хорошо. Для большинства это работает ужасно. Я предполагаю, что он не находит новую точку разворота должным образом, и если это так, как бы я это исправить?

Изменить: Для пояснения, я использую это для системы инвентаризации, поэтому я не уверен, что LinkedList будет уместным. Я использую ArrayList, потому что они мне более знакомы, и, следовательно, было бы проще перевести их на другой язык, если это необходимо (что, вероятно, в данный момент может перейти на C#). По этой причине я стараюсь избегать таких вещей, как Comparable, поскольку мне пришлось бы полностью переписать, если в C# этого нет.

Редактировать часть Duex: разобрался, что я делал не так. Вместо того, чтобы использовать предыдущую опорную точку, я должен был установить и изменить границы области, которую я проверял, и создать новую опорную точку на основе этого.

Источник

6 ответов

Возможно, не стоит использовать для этого SortedSet (например, TreeSet), поскольку деревья не допускают дублирования элементов. Если у вас есть дубликаты элементов (например, экземпляры TestClass с одинаковыми именами), то следует использовать список. Вставить элемент в уже отсортированный список так же просто, как это:

void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

Этот код требует Java 8 или более поздней версии, но может быть переписан для работы и в более старых версиях Java.

Источник

Как уже указывалось, нет причин реализовывать это самостоятельно, простой пример кода:



    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

(На основе Как найти индекс элемента в TreeSet?)

Источник

Я думаю, что проблема в этом фрагменте кода:

else if (test < entry)
{
    int tempPiv = pivot;
    pivot = oldPivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}
else
{
    int tempPiv = pivot;
    pivot = pivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}

Вы выполняете одни и те же действия, если вход . Это приведет к линейному поиску, когда искомый элемент находится в начале массива.

Я предпочитаю использовать (низкий и высокий) как

high = list.size();
low = 0;

do {
   pivot = (high + low) / 2;
   if (test < entry) {
      low = pivot;
   } else if (test > entry) {
      high = pivot
   } else {
      ....
   }
} while ...;
Источник

Вы должны использовать что-то вроде PriorityQueue, которое уже имеет чувство порядка. Вставка в коллекцию с определенным порядком автоматически поместит элемент в правильное место с минимальным временем (обычно log(n) или меньше).

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

Также код для поиска местоположения вставки в связанном списке намного проще.

if (next != null && next.compareTo(insertElement) > 0){
    // You have the right location
}
Источник

Существуют и другие используемые структуры данных, которые можно использовать вместо списка, например дерево, очередь с приоритетами и т. Д.

Источник

Создайте собственную реализацию списка, и в вашем методе add есть следующие строки:

wrappedList.add(object);
Collections.sort(wrappedList);
Источник
Другие вопросы по тегам