java - 优化java代码以更少的时间对数组/数组列表进行排序

Question

我正在编写一个测验程序，它要求我对一些数字进行排序并打印相应的字符串。

为此，我创建了一个类 Song，并获取了该类的对象数组。我必须根据变量 qi 进行排序。问题是，根据法官的说法，我的解决方案花费了太多时间，而且效率不够。我之前尝试过使用对象的 ArrayList 并转向数组思维，这可以在一定程度上优化它，但没有任何帮助。

如何进一步优化？

我的代码:

   class Song{
    long fi;
    long qi;
    String si;

    public Song(long fi,String si, long qi){
        this.fi = fi;
        this.si = si;
        this.qi = qi;
    }
}

      public class Zipf {
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        long fi;
        long qi;
        String si;
        int noOfSongs = scan.nextInt();
        int selection = scan.nextInt();
        List<Song> list=new ArrayList<Song>(); // all songs
        TreeSet<Song> set = new TreeSet<Song>(new treeComparator());
        for(int i=0; i< noOfSongs;i++)
        {
            fi=(scan.nextLong());
            si=(scan.next());
            qi=(fi*(i+1));
            list.add(new Song(fi,si,qi));//adding all songs to list
        }
        for(int i=0; i< selection;i++)
        {
            set.add(list.get(i));//adding no of songs to be selected into set

        }

        Song min = set.first();
        for (int i = selection; i < list.size(); i++) {
            Song song = list.get(i);
            if (song.qi > min.qi) {
                set.remove(min);
                set.add(song);
                min = set.first();
            }
        }
     Iterator<Song> iterator = set.descendingIterator();

                //Displaying the Tree set data
                for(int i=0;i<selection;i++){
                    System.out.println(iterator.next().si);
                }   

    }


}
class treeComparator implements Comparator<Song>{

    @Override
    public int compare(Song o1, Song o2) {
          if (o1.qi <= o2.qi) return -1;
            if (o1.qi > o2.qi) return 1;
            return 0;
    }
}   

Answer 1

就 Big-O 复杂性而言，您的解决方案是最佳的。无论您使用的是数组还是 ArrayList，排序在这两种情况下都需要 O(nlogn)。

您可以进行小规模优化，例如避免在 compare 方法中创建新的废弃对象。但从整体上看，这将对性能产生边际影响。

因此，您确定您执行任务的总体方法是正确的吗？我的意思是，你真的需要对列表进行排序吗？例如，如果任务只是找到最小 qi，则无需对整个列表进行排序即可。这可以推广到 n 个最小的 qi，如下所示:

List<Song> list; // all songs
int n; // provided by user

TreeSet<Song> set = new TreeSet<Song>(new Comparator() ...);
for (int i = 0; i < n; i++) {
    set.add(list.get(i));
}

Song max = set.last();
for (int i = n; i < list.size(); i++) {
    Song song = list.get(i);
    if (song.qi < max.qi) {
        set.remove(max);
        set.add(song);
        max = set.last();
    }
}

这里，我们假设歌曲列表非常大，并且n小于列表中歌曲的数量。正如您所看到的，您不必对整个列表进行排序，线性迭代列表一次就足够了，并且只保持输出集排序。

Comparator 与您在自己的代码中使用的相同，但如果您“手动”进行比较，则可以不使用 new Long

public int compare(Song s1, Song s2) {
    if (s1.qi < s2.qi) return -1;
    if (s1.qi > s2.qi) return 1;
    return 0;
}