みなさんこんにちは。マトリックスに基づいた情報の配列を管理できるコレクションを作成するというアイデアは、かなり前に生まれました。 Javaプログラミング言語を学んだ後、アイデアを実現することにしました。 この記事では、リストインターフェイスを実装するコレクションに焦点を当てます 。

Javaコレクション

現時点では、コレクションを操作するために、ネイティブJDKとサードパーティライブラリの両方を自由に使用できます。

Jdk

オープンソース

財団の選択

汎用コレクションを作成するには、ジェネリックの原則を使用することが適切です。コレクションの基礎は、 java.util.AbstractListクラスによって作成されます。オーバーライドはgetおよびsizeメソッドです。

public class FastArray<E> extends AbstractList<E> { @Override public E get(int index) { return null; } @Override public int size() { return 0; } }

さらに、AbstractList抽象クラスの一部のメソッドの本体は、必要な動作でそれらをオーバーライドすることを強制するthrow new UnsupportedOperationException()

として定義されています。

  public E set(int index, E element) { throw new UnsupportedOperationException(); } public void add(int index, E element) { throw new UnsupportedOperationException(); } public E remove(int index) { throw new UnsupportedOperationException(); }

ストレージの原則とデータの取り扱い

コレクション内のデータストレージ構造は、IndexDataタイプの1つのマトリックスと1つの配列の形式で表されます。

  private Object[][] elementData; private IndexData[] data;

リストアイテムを格納するには、elementDataの2次元配列が使用されます。メモリ容量を損なう2次元配列は、より多くのことを可能にします ~~読み取り、書き込み、削除中にリストアイテムにすばやくアクセス~~ リストの最初/中央でのクイック挿入/削除操作。

標準のArrayListの動作（要素を追加すると、配列の内容が新しい拡大配列にコピーされます）とは異なり、FastArrayでは、配列の最初の次元の長さが可変であり、必要に応じて変更されます。配列の2番目の次元の長さは32要素です。

  private static final int CAPACITY = Integer.SIZE;

つまり、すべてはelementData用の十分なストレージがない場合に実行されるという事実に帰着します。

配列の最初の次元の新しいサイズへのメモリの動的割り当て
2番目の次元のすべての配列へのリンクがコピーされます
二次元の新しい配列を動的に作成しました

IndexData配列は、elementDataの2番目の次元で占有されている場所とその総数を格納するために必要です。

クラスIndexData

  private static class IndexData { private int data; private int size; private boolean isFull() { return size == CAPACITY; } private void take(final int index) { if (isFree(index)) { data = data | 1 << index; size++; } } private void free(final int index) { if (isTaked(index)) { data = data ^ 1 << index; size--; } } private boolean isTaked(final int index) { return !isFree(index); } private boolean isFree(final int index) { return (data & 1 << index) == 0; } private int getSize() { return size; } private int getIndexLeadingFreeBit() { return CAPACITY - Integer.numberOfLeadingZeros(data); } private int getIndexTrailingFreeBit() { return Integer.numberOfTrailingZeros(data) - 1; } }

32桁は1つの32ビット数のビットに格納されます。この手法を使用すると、配列を走査する際のいくつかのサイクルを削減できます。たとえば、2番目の次元の左または右の空き領域を検索します。

しかし、ある場所ではループを使用する必要がありました

  private int getTakedIndexAt(int data, int number) { int count = 0; int index = -1; number++; do { count += data & 1; index++; } while ((data >>>= 1) != 0 && count != number); return index; }

このアルゴリズムは、たとえば最初から5番目の占有場所を見つける必要があります。このアルゴリズムからループを削除する方法についてアイデアがある場合は、コメントでそれらを示してください。

テスト

FastArrayコレクションは、サイズが1000要素を超えると肯定的な結果を表示し始めます。そうしないと、他のコレクションの結果と比較して、操作を完了する時間が大幅に長くなります。

次のアルゴリズムがテストに使用されました

  int count = 100000; for(int i = 0; i < count; i++) list.add(1); for(int i = 0; i < count; i++) list.add(rand.nextInt(count), 10); for(int i = 0; i < count * 2; i++) list.get(rand.nextInt(count)); for(int i = 0; i < count; i++) list.remove(rand.nextInt(list.size()));

採取試験結果

＃	お名前	時間（ミリ秒）
1	高速アレイ	804
2	HPPC	2857
3	グアバ	2887
4	コモンズコレクション	2909
5	配列リスト	2949
6	PCJ	6370
7	トローブ	6503
8	LinkedList	83002

UPD： JMHベンチマーク

テストのソースコードはgithubに表示されます

おわりに

繰り返しになりますが、実行時間を短縮するために、消費したメモリ量を支払うことに注意してください。デフラグ中に上記のテストを実行すると、FastArrayコレクションのサイズが公称値の3倍になりました。コレクションのサイズを小さくするには、 trimToSize()

メソッドを使用します。

このバージョンの実装は最終的なものではありません。ここでは、最低限必要な機能が実装されており、後でより完全に最適化できます。

githubで完全に送信されたソースコード

ご清聴ありがとうございました

マトリックスベースのコレクション開発