Java中实现队列的最快方法

Question

我想知道应该对这段代码进行哪些更改以减少其执行时间。

import java.util.*;

public class ExamPeekableQueueImpl <E extends Comparable<E>> implements ExamPeekableQueue<E> {

    LinkedList<E> li = new LinkedList<E>();

    public ExamPeekableQueueImpl(){
    }

    public void enqueue(E e){
        if(li.isEmpty()){
            li.add(0, e);
        }
        else
        li.add(e);
    }

    public E dequeue(){
        li.pollFirst();
        return null;
    }

    public void printlist(){
        System.out.println(li.toString());
    }

    public E peekMedian(){
        int var = (((li.size())/2)+1);
        Collections.sort(li);
        //Integer var2 = li.get(var);
        System.out.println("the median is:" + li.get(var-1));
        return null;
    }

    public E peekMaximum(){
        Collections.sort(li);
        System.out.println("the maximum is:" + li.getLast());
        return null;
    }

    public E peekMinimum(){
        Collections.sort(li);
        System.out.println("the minimum is:" + li.getFirst());
        return null;
    }

    public int size(){
        li.size();
        return 0;
    }   
}

我想知道在实现队列时，LinkedList、ArrayList或其他数据结构哪个更快。

- Bhagirath N Sai

---

您需要哪方面的改进？是添加还是查找最大值？如果是查找最大值，为什么不尝试使用TreeSet呢？或者您允许重复元素吗？请提供更多信息。 - RNJ

每次需要获取最大值、中位数或最小值时对集合进行排序非常低效。 - assylias

最后一个问题顺便说一下，是非常典型的作业问题。你确定这不是作业吗？你可能需要重新表述问题，以便获得更好的答案。 - BalusC

@BalusC 我认为这不是作业，而是准备考试，因为有像 ExamPeekableQueue 这样的类名。 - brimborium

考试跟作业/课业有何不同？ - BalusC

Answer 1

这是一个有深意的问题。

你想要加速哪些操作？目前，你的peekMin/Max/Mid代码相当缓慢，因为每次都需要进行排序。然而，你的insert代码很快。如果你愿意，可以在内部维护一个排序的数据结构。这会减慢你的插入方法，但加速你的peek方法。在这类操作中，速度常常存在权衡。很少能够加速某个数据结构上的所有操作，因此你需要选择你认为常见的操作，并优化它们。

关键在于你想要加速哪些操作。

- Oleksi

Answer 2

目前，插入操作的时间复杂度为O(1)，而getMin/getMax/getMedian的时间复杂度为O(nlogn)。您可以通过使用排序数据结构，将logn从获取器中移至插入部分。或者，您可以保留插入操作，并通过在列表中进行线性搜索并仅存储最小值来优化getMin/getMax。对于getMedian，因为您需要一个排序集合，所以无需进行任何操作。

进一步的优化是在每个插入步骤中存储最小/最大值，并更新这两个值。这不会对插入操作产生任何（非常量）变化，并将使您的getMin/getMax降至O(1)。（感谢Tedil）

对于getMedian，同样适用。您可以在链表的同时保持一个排序列表。然后，您可以简单地从该列表的中间选择中位数。当然，这将使插入时间变为O(logn)或更糟（取决于您使用的列表），并且还会使存储空间增加一倍。因此，这比getMin/getMax的优化更昂贵。

- brimborium

Answer 3

在peekMaximum()和peekMinimum()方法中，你可以直接使用方法Collections.max(li)和Collections.min(li)，而不是对LinkedList进行排序。

我认为这样做可以节省排序列表所浪费的时间。

- Nirmalya

Answer 4

回答你后面的问题，请查看this主题，了解在结构中使用数组或链表的区别。

另外，作为建议，在声明结构时，始终使用接口作为类型，这样您可以更改实现而不影响功能。

- Sednus

Answer 5

这要看情况。

实际上，大多数回答/评论的人没有意识到Collections.sort在几乎排序完成的列表上可以获得关于N的性能。(如果列表根本没有排序，性能为N log N。)

正如其他人所说，也许您应该在修改列表时对其进行排序，而不是读取列表时进行排序。也许您应该使用有序集而不是列表。(如果您真的需要一个列表来存储多个项目的副本，请考虑使用Ordered Map并将出现次数作为值。)

您还可以考虑制作一个对象，用于存储Collection并在不对其进行排序的情况下跟踪最小值和最大值。如果很少需要找到中位数或者可以避免需要中位数，那么这种方法会很好地工作。

- Joe