4

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

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

另外我想知道是为了实现queues，LinkedList更快ArrayList还是任何其他数据结构。

4

5 回答 5

3

这是一个加载的问题。

你想加快什么操作？现在，您的 peekMin/Max/Mid 代码非常慢，因为您必须每次都进行排序。但是，您的插入代码很快。如果你愿意，你可以在内部维护一个排序的数据结构。这会减慢您的插入方法，但会加快您的窥视方法。像这样的操作之间通常需要权衡速度。很少能够仅加速某些数据结构上的所有操作，因此您需要选择您认为常见的操作，并对其进行优化。

这是关于您想要加快哪些操作。

于 2012-08-27T14:19:43.403 回答
2

目前您有O(1)用于插入和O(nlogn)用于getMin/getMax/getMedian. 您可以使用排序的数据结构将logn从 getter 移动到插入部分。或者，您可以保持插入不变，并getMin/getMax通过对列表进行线性搜索并仅存储最小值进行优化。因为getMedian没有什么可做的，因为您需要一个排序集。

进一步的优化是存储最小值/最大值并在每个插入步骤期间更新这两个值。这在插入时不会有任何（非常量）变化，并将减少getMin/getMax到O(1)。（感谢泰迪尔）

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

于 2012-08-27T14:23:13.023 回答
0

回答你的后一个问题。请查看此主题以了解在结构中使用数组或链表之间的区别。

此外，作为建议，在声明结构时，请始终使用接口作为类型，这样您就可以在不影响功能的情况下更改实现。

于 2012-08-27T14:18:58.803 回答
0

这取决于。

实际上，大多数人回答/评论没有意识到的一件事是 Collections.sort 在几乎排序的列表上提供了大约 N 性能。（N log N 是列表未排序时的性能。）

正如其他人所说，也许您应该在更改列表而不是阅读列表时进行排序。也许您应该使用有序集而不是列表。（如果您确实需要一个列表来保存一个项目的多个副本，请考虑使用有序映射并将出现次数设为值。）

您还可以考虑创建一个对象来存储集合并跟踪最小值和最大值而不对其进行排序。如果找到中位数很少，或者您可以摆脱对中位数的需要，这将很有效。

于 2012-08-27T14:36:21.047 回答
0

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

我认为这将节省浪费在对列表进行排序的时间。

于 2013-04-04T15:12:37.167 回答