あいさつします！

コレクション、すなわちArrayList



やLinkedList



などのList



実装を検討した後、これらのデータ構造を1つに結合して、その結果を確認してください。

なぜこれが必要なのですか？

• 問題はArrayList
  
  
  
  -初期デフォルトサイズがDEFAULT_CAPACITY
  
  
  
  または指定されたinitialCapacity
  
  
  
  サイズです。このサイズを超えると、より大きなサイズの新しい配列が作成されますが、古い配列のデータはそこにコピーされます。 O(n)
  
  
  
  
• LinkedList
  
  
  
  の問題は、逆に、新しい要素を追加すると、新しい接続が追加されるだけで（別のNode
  
  
  
  を作成してリンクを追加する）、インデックスで要素を取得する操作が非常に高価になることです。 リスト全体を最初から確認する必要があります。これは非常に高価であり、 O(n)
  
  
  
  を与えます。

解決策

要素の挿入と受信が一定の時間で行われるようなデータ構造を作成するとどうなりますか。 配列を再作成せずにArrayList



テクノロジーを使用します

それらを一緒に接続するために、二重リンクリストを使用します：

実装

ソースコードに直接進みます。

 public class Node<T> { Node prev; Node next; T[] value; public Node(Node prev, Node next, T[] value) { this.prev = prev; this.next = next; this.value = value; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、標準の二重リンクリスト構造を作成します。ここで、 value



はvalue



の配列です。

次に、クラスの具体的な実装に進み、必要な変数を宣言します。

 public static int INIT_CAPACITY = 100; private Object[] arr = new Object[INIT_CAPACITY]; private int index = 0; private int level = 0; private Node<T> first = new Node<>(null, null, (T[]) arr); private Node last = first; private Node current = null; private int size = 0;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでINIT_CAPACITY



は配列の初期サイズであり、対応するコンストラクターで再定義できますINIT_CAPACITY



は配列自体です。 index



変数はインデックスの計算に必要です。 level



はlevel



計算に使用されます。 first



にリストの最初の要素へのリンク、

last



リストの最後の要素へのリンク、current-リストの現在の要素（最後の選択）へのリンク。これにより、連続する要素またはそれらに近い要素の選択を高速化できます。size-サイズ（またはデータ量）。

デフォルトで2つのkostruktoraを設定し、初期サイズを変更します。

 public MyLinkedList() { first.next = last.next; } public MyLinkedList(int size) { INIT_CAPACITY = size; arr = new Object[INIT_CAPACITY]; first.next = last.next; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アイテムの追加：

 public void add(T i) { if (index == INIT_CAPACITY) { arr = new Object[INIT_CAPACITY]; last.next = new Node<>(last, null, (T[]) arr); index = 0; last = last.next; } arr[index] = i; index++; size++; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、配列が満杯の場合に条件をチェックし、新しい配列を作成して、そのリンクを記憶します。

アイテムを受け取る：

 public T get(int i) { T value; int level = i / INIT_CAPACITY; int index = i % INIT_CAPACITY; if (this.current == null) { this.level = 0; this.current = first; } if(this.level > level) for (int j = this.level; j < level; j++) { this.level = level; current = current.prev; } else for (int j = this.level; j < level; j++) { this.level = level; current = current.next; } value = (T) current.value[index]; return value; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

レベルはリスト内の配列の数です。つまり、レベル0、1配列、レベル1、2配列などです。 index



は現在のレベル0..INIT_CAPACITY



インデックスであり、現在の要素へのリンクもあります。前の選択から取得されたcurrent



リスト、つまり 新しいレベルが前のレベルよりも大きい場合、現在の要素から先に進み、逆の場合は元に戻ります。 また、2つのクイック操作を追加しました-最初と最後の要素を取得します。

 public T getFirst(){ return first.value[0]; } public T getLast() { return (T) last.value[(size-1) % INIT_CAPACITY]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初と最後のアイテムの取得は、配列の場合と同じくらい簡単で高速です。

最後の要素を削除する操作は、値をnullで上書きする最も簡単な方法です。配列全体がnullでいっぱいになると、リンクが失われ、ガベージコレクターがすべてをクリアします。

 public void removeLast(){ if (last.value[0] == null) { last = last.prev; index=INIT_CAPACITY-1; } last.value[(size-1) % INIT_CAPACITY]=null; size--; index--; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

サイズを取得することは明らかです。 イテレータも追加されました。 このクラスはIterableを実装し、iteratorメソッドを実装します

 private Node<T> first; private int index = -1; public MyLinkedListIterator(Node<T> first) { this.first = first; } @Override public boolean hasNext() { index++; return first != null; } @Override public T next() { T value; int index = this.index % INIT_CAPACITY; value= first.value[index]; if(index==INIT_CAPACITY-1||this.first.value[index+1]==null) first=first.next; return value; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

作業時間

JMHベンチマーク、テスト例を使用して測定：

 public class TestGetMyDeque { private static class SetDeque { MyDeque<Integer> deque = new MyDeque<>(); SetDeque() { for (int i = 0; i <Constant.COUNT_ELEMENT; i++) { deque.add(i); } } } @State(Scope.Benchmark) public static class MyState{ SetDeque deque; @Setup(Level.Invocation) public void setUp() { deque = new SetDeque(); } } @Benchmark @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.SECONDS) public void getFirst(MyState state, Blackhole blackhole) { for (int i = 0; i < Constant.COUNT_ELEMENT; i++) { blackhole.consume(state.deque.deque.getFirst()); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ドキュメントはインターネットで見ることができます

異なる数の要素を取得し、数秒で結果をテストします。

N = 100000	最後に挿入	最初の取得	平均を取得する	最後に
ミデケ	0.002	0	0.001	0
配列	0.002	0	-	0.001
配列リスト	0.002	0.001	0	0.001
LinkedList	0.003	0	28,465	0.001

100万個の要素を取ります：

N = 1,000,000	最後に挿入	最初の取得	平均を取得する	最後に
ミデケ	0.019	0.005	0.010	0.007
配列	0,025	0.005	-	0.005
配列リスト	0,036	0.005	0.005	0.005
LinkedList	0.051	0.005	OutOfMemoryError：Javaヒープスペース	0.006

最後に、1000万の要素を取得します。

N = 10,000,000	最後に挿入	最初の取得	平均を取得する	最後に
ミデケ	1,832	0,047	0,090	0,071
配列	2,065	0,046	-	0.058
配列リスト	4,413	0,048	0,047	0,048
LinkedList	OutOfMemoryError：Javaヒープスペース

https://github.com/jheusser/core-java-performance-examples/の原則に基づいてメモリ測定を行いました

（x軸は100万要素、y軸はmbのメモリ）

グラフからわかるように、この構造によるメモリ消去は、同様のデータ構造とそれほど変わりません。

おわりに

一番下の行には、通常のDequeよりも高速に動作するLIFOキューがあり、ArrayListよりもはるかに高速に要素を挿入するという点で、LinkedListを使用するときに遭遇する問題もありません。 将来的には、パフォーマンスを損なうことなくどこからでも挿入や削除などの操作を実装することが計画されています。このテーマについてはすでにいくつかの開発がありますが、この段階でフィードバックを受け取り、新しいデータ構造のさらなる作業のためにコミュニティの関心を見てみたいです。

プロジェクトはここで見ることができます