Сортировка списка занимает много времени

Question

У меня есть следующий список для сортировки:

A 0.53 
    B 0.56 
    C 0.56 
    D 0.98 
    E 0.33 

Пожалуйста, не то, что мой список может содержит 1000-х такого типа записей. Я сортировка мой список и поместить отсортированный список в массив как:

String str=""; 
     for(String s: mylist){ 
      str+=s+","; 
     } 
     String[] sArr = str.split(","); 
     String temp=""; 
     for(int i=0; i<sArr.length;i++) { 
      for(int j= i+1; j<sArr.length;j++){ 
       if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){ 
        temp= sArr[j]; 
        sArr[j]= sArr[i]; 
        sArr[i]=temp; 
       } 
      } 
     } 

     //sArr now contains the sorted list 

Проблема заключается в том, что она занимает слишком много времени, чтобы получить отсортированный, когда у меня есть 1000-записей. Мой вопрос: Есть ли другой выход для выполнения одной и той же задачи за меньшее время! или что-то не так с моим способом кодирования. Может кто-нибудь, пожалуйста, помогите мне.

Answer 1

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

Arrays.sort(sArr); 

который должен быть быстрее, чем ваш сортимент вставки.

Если вы хотите узнать больше о алгоритмах сортировки: wikipedia

Answer 2

Ну, причина вашего сорт занимает так много времени, потому что вы не используете эффективный алгоритм в сортировочном. Обычно, когда вы сортируете большое количество данных/записей/и т. Д., Вы хотите определить алгоритм или решение, которое лучше всего работает с тем, что у вас есть.

В настоящее время, ваш алгоритм, кажется, есть время выполнения O (N^2), который, как правило, очень плохо, вот почему это O (N^2)

//The outer-loop traverses through the "N" indexes of the array. 
for(int i=0; i<sArr.length;i++) { 

     //The inner-loop also traverses through the "N" indexes of the array 
     for(int j= i+1; j<sArr.length;j++){ 

      //Most comparisons are able to be done in O(1) 
      if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){ 

       //Assignments are done in O(1) 
       temp= sArr[j]; 
       sArr[j]= sArr[i]; 
       sArr[i]=temp; 
      } 
     } 

Итак, мы действительно связаны с временем выполнения, когда N растет достаточно большим. По мере роста N мы получим результат: O(N) * O(N) = O(N^2) Это потому, что мы смотрим на наихудший случай . Лучшим случаем было бы то, что все уже отсортировано, и все, что нам нужно сделать, это посмотреть на каждый элемент, что приводит к O(N) runtime.

Если посмотреть на алгоритм, как Quicksort (Или посмотрите на слиянии), вы обязательно увидят большое улучшение в связи с тем, что в худшем случае и лучший случай (как правило) видят время выполнения O(n log n), который значительно быстрее, чем текущий метод.

Я бы посоветовал вам взглянуть на реализацию лучших/более эффективных алгоритмов сортировки.

Я считаю, что Java реализует сортировку слияния в своей библиотеке массивов. Arrays.sort()

Answer 3

Ваш код опирается на множество операций со строками. Строки неизменны в java. Например: если у вас есть String a и String b, и вы пишете + = b; java не просто добавляет String b в a. Он создает новый экземпляр String из строки a + String b, в результате чего создается новый объект String. Выполнение этого один или два раза не имеет большого значения, но ваш код сильно полагается на это.

Мой подход было бы создать новый класс для ваших данных, который реализует интерфейс Comarable:

public class DataPoint implements Comparable<DataPoint>{ 
    public String key; 
    public double value; 

    public int compareTo(DataPoint p2){ 
     if(this.value < p2.value) 
      return -1; 
     if(this.value == p2.value) 
      return 0; 
     if(this.value > p2.value) 
      return 1; 
    } 
} 

Затем создать список этих объектов DataPoint и коллекции вызовов.сортировать (dataPointList);

Затем DataPointList содержит отсортированные по значению значения.

Answer 4

Возможно, вы захотите использовать TreeSet, который сортируется с самого начала. Я занял небольшую часть DataPoint класс от laubed.

import java.util.TreeSet; 

public class Main { 
    public static void main(String[] args) { 
     TreeSet<DataPoint> set = new TreeSet<DataPoint>(); 
     String[] splitS; 
     for (String s : YOUR_LIST) { 
      splitS = s.split(" "); 
      set.add(new DataPoint(splitS[0], Double.parseDouble(splitS[1]))); 
     } 
     DataPoint[] sortedArray = new DataPoint[set.size()]; 
     set.toArray(sortedArray); //but to be honest there is no reason for using array at this point 
    } 
} 

class DataPoint implements Comparable<DataPoint> { 
    public String key; 
    public double value; 

    public DataPoint(String key, double value) { 
     this.key = key; 
     this.value = value; 
    } 

    public int compareTo(DataPoint p){ 
     return Double.compare(value, p.value); 
    } 
} 

Answer 5

Кажется, есть две проблемы с кодом. Первый заключается в следующем:

String str=""; 
for(String s: mylist) { 
    str+=s+","; 
} 
String[] sArr = str.split(","); 

Здесь, по-видимому без причины, вступив в коллекцию строк, а затем разбить его снова в массив. Это усугубляется тем фактом, что вы используете конкатенацию строк (оператор +).

В Java строки являются неизменяемыми объектами. Это означает, что каждая операция, которая выглядит так, как будто это изменение строкового объекта, фактически создает новый. Каждый раз, когда вы делаете str+=s+",", вы создаете новые объекты. Повторение этой тысячи раз очень неэффективно.

Если вам нужно составить String вот так, вы должны использовать StringBuilder. Хотя, в данном случае, я не думаю, что это необходимо вообще.

Если я правильно понял ваш код, кажется, что список mylist уже содержит свои записи в следующем формате:

["A 0.53", "B 0.56", ...] 

Если это так, то вы можете сортировать mylist непосредственно.

Отсюда я буду считать, что mylist является List<String>. Если это не так, и mylist действительно String[], вам просто нужно использовать Arrays.sort(mylist, comparator) вместо mylist.sort(comparator).

Во-первых, вам нужен метод для извлечения значения Double из String записей, как я полагаю, вы пытаетесь сравнить числами, как double, а не String.

static Double doubleFromRecord(String record) { 
    return Double.valueOf(record.split("\\s")[1]); 
} 

Так, doubleFromRecord("A 0.53") возвращает 0.53 как Double.

Теперь вам просто нужно позвонить sort непосредственно на mylist пропускании Comparator, который будет сравнивать числа из различных элементов:

mylist.sort((r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2))); 

И mylist будет отсортирован.

Компаратор:

(r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2)) 

Просто принимает два элемента из mylist и возвращает результат сравнения их части числа.

Если можно, я хотел бы предложить вам создать класс для ваших записей, таких как:

class Record { 
    final String label; 
    final double value; 

    Record(String label, double value) { 
     this.label = label; 
     this.value = value; 
    } 
} 

И работать с List<Record> вместо List<String>. Таким образом, вы можете легко сделать:

myRecordList.sort((r1, r2) -> Double.compare(r1.value, r2.value));