0

私はJavaで簡単な検索エンジンに取り組んでいます。

検索エンジンは、最初に検索対象のファイル(txtファイル)を含むディレクトリの名前を入力として受け取り、各ファイル内に多くの単語を入力します。

次に、検索エンジンは、ディレクトリで検出されたすべての単語の転置インデックスを作成します。エンジンは各ファイルを読み取り、doubleLinkedListに各単語を挿入します。

問題は、100個の.txtファイルを含むディレクトリを扱う場合です。

インデックス作成時間:〜201msソート時間:2463ms


ディレクトリの並べ替えには1000個のファイルが含まれています

インデックス作成時間:2461msソート時間:922654ms


ディレクトリの並べ替えには10000個のファイルが含まれています

約10時間:(


  1. 実行時間を短縮する方法はありますか?

  2. 挿入ソートを使用したので、ソートアルゴリズムの提案はありますか?

DoubleLinkedListクラスの実装

public class DoubleLinkedList<T> {
    private Node<T> head;
    private Node<T> current;

    public DoubleLinkedList(){
        head = current = null;
    }
    public boolean empty(){
        return head == null;
    }
    public boolean last(){
        return current.next==null;
    }
    public boolean first(){
        return current.previous == null;
    }
    public boolean full(){
        return false;
    }
    public void findFirst(){
        current = head;
    }
    public void findNext(){
        current = current.next;
    }
    public void findPrevious(){
        current = current.previous;
    }
    public T retrieve(){
        return current.data;
    }
    public void update(T val){
        current.data = val;
    }
    public void insert(T val){
        if(head == null){
            head = current = new Node<T>(val);
        }else{
            Node<T> tmp = new Node<T>(val);
            tmp.next = current.next;
            tmp.previous = current;
            if(current.next != null)
                current.next.previous = tmp;
            current.next = tmp;
            current = tmp;
        }
    }
    public void remove(){
        if(current == head){
            head = head.next;
            if(head!=null){
                head.previous=null;
            }
        }else{
            current.previous.next = current.next;
            if(current.next!=null){
                current.next.previous = current.previous;
            }
        }
        if(current.next == null){
            current = head;
        }else{
            current = current.next;
        }
    }


}
4

3 に答える 3

4

挿入ソートは(最悪の場合)O(n^2)時間で実行されます。

O(nlogn)(IIRC)時間で実行されるMergesort、QuickSort、HeapSortなどを試すことができます。これははるかに高速になります。

于 2012-11-25T16:43:18.763 に答える
1

もちろん、もっと速い方法があります。実際、より高速な方法は数十あります:-)

しかし、車輪の再発明が好きでない限り、単にを使用することができますCollections.sort(list)。また、パフォーマンスが重要な場合は、参照の局所性が向上し、メモリの消費量が少なくなるため、ArrayListむしろを使用することをお勧めします。LinkedList

長さ10000のリストの場合、これにより、挿入ソートと比較して実行時間が3桁(つまり、1000分の1)短縮されます。

于 2012-11-25T16:46:13.757 に答える
0

を使用ArrayListし、を呼び出しlist.trim()て空の予約済みリストスペースを削除してから、を呼び出しますCollections.sort(list)。はLinkedList99.5%悪いですArrayList

それでも速度が低下する場合は、次を試してください:
を使用して ArrayList、を作成しString[] words、で並べ替えますArrays.sort( words)
。Collection.sortは(変更された)MergeSortを使用します。

このアルゴリズムは、n log(n)のパフォーマンスを保証します。

コレクションのオーバーヘッドを回避することで、少し速く実行できます。これは、クイックソートでMyArrayListIntを使用して一度実行しました。

于 2012-11-25T17:04:15.340 に答える