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、何もする必要はありません。

さらなる最適化は、最小値/最大値を保存し、各挿入ステップで 2 つの値を更新することです。これにより、挿入時に（一定ではない）変更が行われず、 O(1)getMin/getMaxに削減されます。(テディルに感謝)

getMedian同じことが、並べ替えられたリストをリンクされたリストと並行して保持する場合にも当てはまります。次に、そのリストの中央から中央値を選択するだけです。もちろん、これにより挿​​入時間がO(logn)またはさらに悪化し (使用するリストによって異なります)、ストレージ容量も 2 倍になります。そのため、 の最適化よりも高価な最適化ですgetMin/getMax。

于 2012-08-27T14:23:13.023 に答える
0

後者の質問に答えるため。構造体で配列とリンクリストを使用する場合の違いについては、このトピックをご覧ください。

また、アドバイスとして、構造を宣言するときは、機能に影響を与えずに実装を変更できるように、常にインターフェイスをタイプとして使用してください。

于 2012-08-27T14:18:58.803 に答える
0

場合によります。

実際、ほとんどの人が回答/コメントしていることに気付いていないことの1つは、Collections.sortがほぼソートされたリストで約Nのパフォーマンスを提供することです。(N log N は、リストがまったくソートされていない場合のパフォーマンスです。)

他の人が言ったように、リストを読むのではなく、リストを変更するときにソートする必要があるかもしれません。おそらく、リストではなく順序付きセットを使用する必要があります。(項目の複数のコピーを保持するリストが本当に必要な場合は、順序付きマップを使用して、出現回数を値にすることを検討してください。)

Collection を格納し、ソートせずに最小値と最大値を追跡するオブジェクトを作成することも検討できます。これは、中央値を見つけることがめったにない場合、または中央値を必要としない場合にうまく機能します。

于 2012-08-27T14:36:21.047 に答える
0

peekMaximum() および peekMinimum() メソッドでは、LinkedList をソートする代わりに、メソッドCollections.max(li)およびを直接使用できますCollections.min(li)。

リストの並べ替えに費やす時間を節約できると思います。

于 2013-04-04T15:12:37.167 に答える