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

Question

С 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: Выяснил, что я делаю неправильно. Вместо того, чтобы использовать предыдущую опорную точку, я должен был установить и изменить границы области, которую я проверял, и создать на ней новый опорный стержень.

Answer 1

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

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

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

if (next != null && next.compareTo(insertElement) > 0){ 
    // You have the right location 
} 

Answer 2

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

Answer 3

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

 


    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(); 

 

(на основе How to find the index of an element in a TreeSet?)

Answer 4

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

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 ...; 

Answer 5

Сделать реализацию списка ваших, и в методе добавите эти строки:

wrappedList.add(object); 
Collections.sort(wrappedList);