Вставка Сортировка LinkedList Java

1

Я пытаюсь написать сортировку Insertion для LinkedList, у меня есть рабочий метод, но он невероятно медленный. Более часа добавить и отсортировать 50 000 элементов.

public void insert(Custom c) 
{
    int i = 0;
    for (i = 0; i < list.size(); i++)
    {
        if(list.get(i).compareTo(c) > 0  )
        {
            list.add(i,c);
            return;
        }
    }
    list.add(c);    
}

Я знаю, что могу использовать Collections.Sort, но для этого задания мне нужно написать собственный LinkedList. Я не требую полного решения только некоторых указателей.

Теги:
sorting
insertion-sort

4 ответа

1
Лучший ответ

Прежде всего, сортировка вставки в List будет медленной (O(N^2))... независимо от того, как вы это делаете. Но вы, похоже, внедрили его как O(N^3).

Вот ваш код... который будет называться N раз, чтобы добавить каждый элемент списка.

public void insert(Entry e) 
{
    int i = 0;
    for (i = 0; i < list.size(); i++)       // HERE #1
    {
        if(list.get(i).compareTo(e) > 0  )  // HERE #2
        {
            list.add(i,e);                  // HERE #3
            return;
        }
    }
    list.add(e);                            // HERE #4   
}

В "ЗДЕСЬ № 1" мы повторяем до M раз, где M - текущая (частичная) длина списка; т.е. O(M). Это присуще сортировке вставки. Однако в зависимости от того, как вы реализовали метод size(), вы могли бы превратить итерацию в последовательность операций O(M^2). (Метод LinkedList.size() просто возвращает значение переменной size. Нет проблем здесь. Но если size() подсчитал элементы...)

На "ЗДЕСЬ № 2" у нас есть выборка и сравнение. Сравнение (compareTo(...)) дешево, но операция get(i) в связанном списке включает в себя перемещение списка с самого начала. Это операция O(M). И так как вы делаете вызов get(i) O(M) раз в каждый вызов insert, это делает вызов O(M^2) и сортировку O(N^3).

В "ЗДЕСЬ № 3" add(i,e) повторяет обход списка предыдущего вызова get(i). Но это не так уж плохо, потому что вы выполняете только то, что add(i,e) вызывается один раз для каждого вызова insert. Таким образом, общая сложность не затрагивается.

В "ЗДЕСЬ № 4" операция add() может быть либо O(1) либо O(M) зависимости от того, как она реализована. (Для LinkedList.add() это O(1) потому что структура данных списка сохраняет ссылку на последний узел списка.) В любом случае общая сложность не изменяется.

Вкратце:

  • Код в # 2 определенно делает этот вид O(N^3).

  • Код в # 1 также мог бы сделать его O(N^3)... но не со стандартным классом LinkedList.

Так что делать?

  • Один из подходов состоит в том, чтобы перекодировать операцию insert так, чтобы она проходила список с использованием next и prev полей и т.д. Непосредственно. Не должно быть вызовов в какой-либо из операций списка более высокого уровня: размер, get (i), добавить (e) или добавить (i, e).

    Однако, если вы реализуете это, расширяя или обертывая LinkedList, это не вариант. Эти поля являются частными.

  • Если вы расширяете или обмениваете LinkedList, тогда решение должно использовать метод listIterator() чтобы предоставить вам ListIterator и использовать его для эффективного обхода. Операцией add в ListIterator является O(1).

  • Если (гипотетически) вы искали самый быстрый способ сортировки (большого) LinkedList, тогда решение должно использовать Collections.sort. Под обложками этот метод копирует содержимое списка в массив, выполняет сортировку O(NlogN) в массиве и восстанавливает список из отсортированного массива.

Поделиться
0

Как насчет использования более быстрого алгоритма сортировки?

Вот что называется QuickSort. Его путь быстрее, чем обычные сортировки для больших наборов данных. QuickSort имеет средний случай O (nlogn), тогда как вставка имеет только средний случай O (n ^ 2). Большая разница не так ли?

Пример внедрения

Класс QuickSort

import java.util.*;

public class QuickSort{


    public static void swap(int A[] , int x, int y){

        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;

    }



    public static int[] QSort(int A[],int L, int U){
        Random randomGenerator = new Random();

        if ( L >= U){
            return A;
        }

        if (L < U) {
            /*                                                                                                                                                                                                                                                                
              Partion the array around the pivot, which is eventually placed                                                                                                                                                                                                  
              in the correct location "p"                                                                                                                                                                                                                                     

            */

            int randomInt = L + randomGenerator.nextInt(U-L);
            swap(A,L,randomInt);
            int T = A[L];
            int p = L;

            for(int i= L+1; i<= U; i++){
                if (T > A[i]){
                    p = p+1;
                    swap(A,p,i);

                }


            }



        /* Recursively call the QSort(int u, int l) function, this deals with                                                                                                                                                                                                 
           the upper pointer first then the lower.                                                                                                                                                                                                                            
        */
            swap(A,L,p);
            QSort(A,p+1,U);
            QSort(A,L, p-1);

        }
        return A;

    }
}

Образец Основной

import java.util.*;

public class Main{
    public static void main(String [] args){

        int[] intArray =  {1,3,2,4,56,0,4,2,4,7,80,120,99,9,10,67,101,123,12,-1,-8};

        System.out.printf("Original Array was:\n%s\n\n",Arrays.toString(intArray));

        System.out.printf("Size of Array is: %d\n\n",intArray.length);

        QuickSort.QSort(intArray, 0, intArray.length - 1);
        int num = Integer.parseInt(args[0]);
        System.out.println("The sorted array is:");
        System.out.println(Arrays.toString(intArray));

    }
}

В приведенном выше примере будет сортироваться массив Int, но вы можете легко отредактировать его для сортировки любого объекта (например, запись в вашем случае). Я позволю тебе понять это.

Удачи

Поделиться
  • 0
    Следует отметить, что набор данных должен быть достаточно большим, однако. Итак, вы говорите о миллионах записей, а не о тысячах.
  • 0
    Это может быть для назначения, где необходима сортировка вставкой.
Показать ещё 9 комментариев
0

В соответствии с этим ответом вы должны использовать ListIterator.add() вместо List.add из-за лучшей производительности.

Поделиться
  • 0
    добавили итератор сейчас. Производительность значительно улучшилась. 50000 примерно за 40 секунд сейчас
0

list.add(e) и list.get(e) будут принимать o (n) при каждом вызове. Вы должны избегать их использования, когда вы отправляете свой список.

Вместо этого, если вам нужно написать свой собственный список, вы должны отслеживать элементы, которые вы путешествуете. путем замены операции i++ и get (i) на elem = elem.next или elem = elem.getnext(), (возможно, что-то еще в зависимости от того, как вы реализовали свой связанный список). Затем вы добавляете элемент:

elem.next.parent = e;
e.next = elem.next;
elem.next = e;
e.parent = elem;

здесь мой пример работает для дважды связанного списка, а elem представляет элемент в связанном списке, который вы в настоящее время сравниваете свой объект, который хотите добавить.

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню