2418


ListIteratorでaddメソッドを実装しArrayListやLinkedListと速度比較したのですが、独自実装のListIteratorの動作が異常に遅いのです。その理由がわかりません。

ListIteratorをimplementしたMyListItrを作成し、最初にaddを実装しその速度を比較しました。

MyListに格納するオブジェクトはElm型オブジェクトとします。

[code]

    public class Elm<E> {
    
        public Elm<E> next;
        public E data;
    
        public Elm() {  }
        public Elm(E obj) {
            data = obj;
        }
        @Override
        public String toString() {
            return data.toString();
        }
    }
    
[/code]

MyListItrの未実装のメソッドは省略して載せます。

[code]

    import java.util.ListIterator;
    
    public class MyListItr<E> implements ListIterator<E>{
    
    protected Elm<E> cursor;
    public Elm<E> temp;
    
    public MyListItr(Elm<E> element, int i) {
        super();
        if(i<0)throw new IndexOutOfBoundsException();
        cursor = element;
    }
    
    @Override
    public void add(E e) {
        Elm<E> n = new Elm<>(cursor.data);
        n.next = cursor.next;
        cursor.data = e;
        cursor.next = n;
        cursor = n;
        temp = null;
    }
    }
    
[/code]

MyListItrを使用してMyListを作ります。

[code]

    import java.util.AbstractSequentialList;
    import java.util.ListIterator;
    
    public class MyList<E>  extends AbstractSequentialList<E> {
    
        public Elm<E> element;
        public MyList(){
            super();
            element = new Elm<E>();
        }
    
        @Override
        public ListIterator<E> listIterator(int arg) {
            return new MyListItr<E>(element,arg);
        }
    
        @Override
        public int size() {
            return size1(element);
        }
    
        private int size1(Elm<E> e) {
            if(e.next == null) return 0;
            return size1(e.next)+1;
        }
    
    }
    
[/code]

このMyListに50000個のElmをaddしていくと15秒近くかかります。ArrayListやLinkedListより1000倍遅いです。どうにかして少しでも早くしたいのですがなにかいい方法はないでしょうか。何故遅いのかよくわかりません。
よろしくお願い致します。


CC BY-SA 3.0
2014-12-23T06:13:03.567
2417
2014-12-24T13:02:17.427
2014-12-24T13:02:17.427
30
5546
question
java
Javaで独自実装したListの動作が異常に遅い


[OpenJDKのソース](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractList.java#AbstractList.add%28java.lang.Object%29)を追いかけてみました。

[code]

    107 public boolean add(E e) {
    108     add(size(), e);
    109     return true;
    110 }
    
[/code]

[ArrayList](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.size%28%29)では、size()メソッドは次のようになっています

[code]

    196 public int size() {
    197     return size;
    198 }
    
[/code]

[LinkedList](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.size%28%29)ではどうでしょうか

[code]

    202 public int size() {
    203     return size;
    204 }
    
[/code]

ということで、どちらもサイズは自前で数えているようです。

提示されたコードでは、size()の計算量が要素数Nに比例するので、差はここから生まれるのでは？


CC BY-SA 3.0
2014-12-23T06:36:54.913
2418
2014-12-23T06:36:54.913
845
2417
answer