<このシリーズの、前の記事 | このシリーズの目次 |
ナビゲート可能で要素挿入可能なリンクトハッシュマップを作った
話題: Javaプログラミング言語
ナビゲート可能で要素挿入可能なリンクトハッシュマップの用途
バイアス惑星の山あいの小川のほとりのある部屋で-Hypothesizerと-Rebutterがコンピュータースクリーンの前に座っている。
これは、スプレッドシートセルエディターを作った際に遭遇したことだが、Javaの標準ライブラリには、ナビゲート可能で要素挿入可能なリンクトハッシュマップが見当たらなかった。
「ナビゲート可能」というのはどういう意味だ？
私が意味していることにその用語が適切なのかどうか知らないが、より適切な用語が見つからなかった。
とにかく、君はどういう意味で使っているのか？
私が意味しているのは、先頭の要素や末尾の要素を得ることができ、任意の指定した要素の前や後の要素を得ることができること、効率的にだ。
それらは、標準の'LinkedHashMap'でできないのか？
できない。それは要素の順序は覚えているのだが、そうした機能は提供しない。
ああ、それでは、要素の順序の恩恵は、先頭の要素から要素をイテレートするためだけに受けられるわけか。指定した要素から次の要素に直接ジャンプすることはできない。
要は、'LinkedHashMap'はリンクトリストではない。要素の挿入順序を内部的に保持するマップにすぎない。
要素は、キーで指定したいのか？
そうだ。実際、スプレッドシートセルエディターの場合には、値は必要なくて、キーだけが必要だ。
それでは、Mapの代わりに、Setでいいわけだ。
実はそうだ、だが、それはここでは問題ではない。'LinkedHashMap'においてと同じ理由で、'LinkedHashSet'も使えない。Mapについて話しているのは、用途がより広いからだ。値を無視すれば、MapをSetとして使える。
しかし、キー‐値ペアが要らないのであれば、代わりに、'LinkedList'を使えないのか？
ああ、機能だけを考えれば、使える。'LinkedList'では、指定した要素の次の要素を以下のように得られる。'l_linkedList'は'LinkedList'のインスタンスであり、'l_specifiedElement'は指定した要素だ。
l_searchedElement = l_linkedList.get (l_linkedList.indexOf (l_specifiedElement) + 1);
しかしながら、処理は効率的ではない。内部的に、それは、指定した要素を見つけるために、要素を先頭の要素からイテレートする。
ふーむ、「ナビゲート可能」なリンクトハッシュマップにはほとんど需要がないのだろうか？つまり、それが、標準Javaライブラリに「ナビゲート可能」なリンクトハッシュマップがない理由なのか？
おそらく、多くの需要がないのだろう、しかし、いくらかはある、というのは、Apache.commonsにそういうクラス、'org.apache.commons.collections4.map.LinkedMap'があるから。
. . . じゃあ、なぜそれを使わないのか？
使ってもよいが、1つのクラスのためにJarを丸ごと導入するのに躊躇したわけ。特に、その1つのクラスを実装するのが別に難しく思えなかったから。
うーん、 . . . そこは、難しい判断だ。
それに、任意の指定した要素の前に要素を挿入できる必要もある。
ああ、標準の'LinkedHashMap'では、要素は常に末尾に追加される。Apache commonsの'LinkedMap'はどうだ？
同じのようだ。
我々の求める機能を持ったクラスがApache commonsに別にあるのじゃないか。
うーん、 . . .
-Hypothesizerは、インターネットで、Apache commonsのAPI文書の中を探す。
これかな？
「これ」とは？
'org.apache.commons.collections4.map.ListOrderedMap'だ。
-RebutterはそのクラスのJavadocページに目を通す。
まあ、少なくとも、これには、我々の求めるメソッドがあるようだ。
しかし、これは効率的かな？わからないな。
そもそも、君は、セルエディターのどこで、ナビゲート可能で要素挿入可能なリンクトハッシュマップを使いたかったのか？
セルエディターフレームの上のSwingコンポーネント群のタブ順を設定するために、'java.awt.FocusTraversalPolicy'のメソッド、'getComponentBefore'および'getComponentAfter'を実装しなければならない。これらメソッドのそれぞれは、Swingコンポーネントを受け取り、次にフォーカスを受けるSwingコンポーネントを戻す。このタブ順を、ナビゲート可能で要素挿入可能なリンクトハッシュマップで指定したかったわけ。
引数として渡されたSwingコンポーネントの前または後のSwingコンポーネントを得られるように？
そう。
なぜ、指定した要素の前に要素を挿入しなければならないのか？
セルエディターフレームを、もっと汎用的なエディターフレームのサブクラスにしたかったから。汎用的なエディターフレームには、「指定されたフレーズを検索する」ボタンなどのSwingコンポーネント群があって、セルエディターには、追加の、「左のセルに移動する」ボタンなどのセルエディター特有のSwingコンポーネント群がある。汎用的なエディターフレームでタブ順を指定し、そのタブ順のあるSwingコンポーネントの前に、セルエディターフレームで、いくつかのSwingコンポーネントを挿入したい。
とにかく、君のSwingコンポーネントは、'LinkedList'を使ってパフォーマンスに感知できるほどのインパクトがあるほどそんなに多くないんじゃないか？
まあ、実のところ、 . . . 多くない。実際問題としては、その件で'LinkedList'を使うことに何の問題もないだろう。しかし、先頭要素から毎回イテレートしなければならないのは、ねえ、ばからしい気がするんだよ。それに、ナビゲート可能で要素挿入可能なリンクトハッシュマップを必要に思ったのはこれが最初ではないし。そこで思ったわけ、「今回作ったらどうだろう？」
まあ、そうしていけない理由があるとは言わない。
我々の、ナビゲート可能で要素挿入可能なリンクトハッシュマップ、のデザイン
前場と同じ。
それで、君のデザインは？
先に言った通り、簡単だ。値が単に値ではなく、値、先行する要素のキー、後続する要素のキーを持つオブジェクトであるハッシュマップのインスタンスが必要なだけだ。ハッシュマップなので、キーによって指定した要素にジャンプでき、先行する要素や後続する要素にもジャンプできる。
それでは、そのハッシュマップインスタンスは'LinkedHashMap'インスタンスではないわけだ。
'LinkedHashMap'は必要ない、どのみち、'LinkedHashMap'インスタンスに保存された要素の順序は使えないから。我々は、任意の位置に要素を挿入しなければならない。
すると、エントリーセットを、先行キー、後続キーリンクに基づいて自分で作ることになる。
そう。そしてもちろん、要素が我々のマップインスタンスに放り込まれるにつれ、リンクが維持されなければならない。そのロジックは普通のリンクトリストにおけるものと同じだ。
'HashMap'クラスを拡張するのか？
いや。それはうまくいかないようだ。'NavigableLinkedHashMap <T, U>'を作りたいが、我々は'HashMap <T, U>'を拡張できない。'ValueAndLinks'を値、先行キー、後続キーを持つクラスとして、'HashMap <T, ValueAndLinks <U, T>>'を使うから。我々は、'java.util.Map'インターフェースを実装しなければならない。'HashMap'インスタンスは、我々のマップのメンバーになる。
すると、'HashMap'インスタンスをラップするわけだ。
そう。
我々の、ナビゲート可能で要素挿入可能なリンクトハッシュマップ、の実装
前場と同じ。
以下が、我々の、ナビゲート可能で要素挿入可能なリンクトハッシュマップ、の全コードだ。
package thebiasplanet.coreutilities.collections;
import java.util.AbstractMap;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
public class NavigableLinkedHashMap <T, U> implements Map <T, U> {
private HashMap <T, ValueAndLinks <T, U>> i_keyToValueAndLinksHashMap;
private T i_firstKey;
private T i_lastKey;
private class ValueAndLinks <T, U> {
U i_value;
T i_previousKey;
T i_nextKey;
public ValueAndLinks (U a_value, T a_previousKey, T a_nextKey) {
i_value = a_value;
i_previousKey = a_previousKey;
i_nextKey = a_nextKey;
}
public U getValue () {
return i_value;
}
public void setValue (U a_value) {
i_value = a_value;
}
public T getPreviousKey () {
return i_previousKey;
}
public void setPreviousKey (T a_previousKey) {
i_previousKey = a_previousKey;
}
public T getNextKey () {
return i_nextKey;
}
public void setNextKey (T a_nextKey) {
i_nextKey = a_nextKey;
}
}
public NavigableLinkedHashMap () {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> ();
initialize ();
}
public NavigableLinkedHashMap (int a_initialCapacity) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_initialCapacity);
initialize ();
}
public NavigableLinkedHashMap (int a_initialCapacity, float a_loadFactor) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_initialCapacity, a_loadFactor);
initialize ();
}
public NavigableLinkedHashMap (Map <? extends T,? extends U> a_map) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_map.size ());
initialize ();
putAll (a_map);
}
private void initialize () {
i_firstKey = null;
i_lastKey = null;
}
@Override
public boolean containsKey (Object a_key) {
return i_keyToValueAndLinksHashMap.containsKey (a_key);
}
@Override
public boolean containsValue (Object a_value) {
for (Map.Entry <T, ValueAndLinks <T, U>> l_keyToValueAndLinksHashMapEntry: i_keyToValueAndLinksHashMap.entrySet ()) {
U l_value = l_keyToValueAndLinksHashMapEntry.getValue ().getValue ();
return (a_value == null ? l_value == null : a_value.equals (l_value));
}
return false;
}
@Override
public U get (Object a_key) {
return i_keyToValueAndLinksHashMap.get (a_key).getValue ();
}
@Override
public int hashCode () {
return i_keyToValueAndLinksHashMap.hashCode ();
}
@Override
public boolean isEmpty () {
return i_keyToValueAndLinksHashMap.isEmpty ();
}
@Override
public Set <T> keySet () {
LinkedHashSet <T> l_keys = new LinkedHashSet <T> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_keys.add (l_key);
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_keys;
}
@Override
public U put (T a_key, U a_value) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
U l_value = l_valueAndLinks.getValue ();
l_valueAndLinks.setValue (a_value);
return l_value;
}
else {
l_valueAndLinks = new ValueAndLinks <T, U> (a_value, i_lastKey, null);
i_keyToValueAndLinksHashMap.put (a_key, l_valueAndLinks);
T l_previousKey = l_valueAndLinks.getPreviousKey ();
if (l_previousKey != null) {
i_keyToValueAndLinksHashMap.get (l_previousKey).setNextKey (a_key);
}
else {
i_firstKey = a_key;
}
i_lastKey = a_key;
return null;
}
}
public U putBefore (T a_insertedPositionKey, T a_key, U a_value) {
ValueAndLinks <T, U> l_existingValueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_existingValueAndLinks != null) {
return null;
}
else {
ValueAndLinks <T, U> l_insertedPositionValueAndLinks = i_keyToValueAndLinksHashMap.get (a_insertedPositionKey);
if (l_insertedPositionValueAndLinks == null) {
return null;
}
else {
T l_previousKeyOfInsertedPosition = l_insertedPositionValueAndLinks.getPreviousKey ();
ValueAndLinks <T, U> l_valueAndLinks = new ValueAndLinks <T, U> (a_value, l_previousKeyOfInsertedPosition, a_insertedPositionKey);
i_keyToValueAndLinksHashMap.put (a_key, l_valueAndLinks);
if (l_previousKeyOfInsertedPosition != null) {
i_keyToValueAndLinksHashMap.get (l_previousKeyOfInsertedPosition).setNextKey (a_key);
}
else {
i_firstKey = a_key;
}
l_insertedPositionValueAndLinks.setPreviousKey (a_key);
return l_insertedPositionValueAndLinks.getValue ();
}
}
}
@Override
public void putAll (Map <? extends T,? extends U> a_map) {
for (Map.Entry <? extends T,? extends U> l_mapEntry: a_map.entrySet ()) {
put (l_mapEntry.getKey (), l_mapEntry.getValue ());
}
}
@Override
public U remove(Object a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
i_keyToValueAndLinksHashMap.remove (a_key);
T l_previousKey = l_valueAndLinks.getPreviousKey ();
T l_nextKey = l_valueAndLinks.getNextKey ();
if (l_previousKey != null) {
i_keyToValueAndLinksHashMap.get (l_previousKey).setNextKey (l_nextKey);
}
else {
i_firstKey = l_nextKey;
}
if (l_nextKey != null) {
i_keyToValueAndLinksHashMap.get (l_nextKey).setPreviousKey (l_previousKey);
}
else {
i_lastKey = l_previousKey;
}
return l_valueAndLinks.getValue ();
}
else {
return null;
}
}
@Override
public void clear () {
i_keyToValueAndLinksHashMap.clear ();
i_firstKey = null;
i_lastKey = null;
}
@Override
public Set <Map.Entry <T, U>> entrySet () {
LinkedHashSet <Map.Entry <T, U>> l_keyToValueEntries = new LinkedHashSet <Map.Entry <T, U>> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_keyToValueEntries.add (new AbstractMap.SimpleEntry <T, U> (l_key, l_valueAndLinks.getValue ()));
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_keyToValueEntries;
}
@Override
public Collection <U> values () {
LinkedHashSet <U> l_values = new LinkedHashSet <U> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_values.add (l_valueAndLinks.getValue ());
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_values;
}
@Override
public boolean equals (Object a_object) {
if (a_object == null || a_object instanceof Map) {
return false;
}
return entrySet ().equals ( ( (Map) a_object).entrySet ());
}
@Override
public int size () {
return i_keyToValueAndLinksHashMap.size ();
}
public T getPreviousKey (T a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
return l_valueAndLinks.getPreviousKey ();
}
else {
return null;
}
}
public T getNextKey (T a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
return l_valueAndLinks.getNextKey ();
}
else {
return null;
}
}
public T getFirstKey () {
return i_firstKey;
}
public T getLastKey () {
return i_lastKey;
}
}
ははあ、確かに、大したものじゃない。
クラスはこのzipファイルに含まれている。我々のzipファイルの使い方は、ここに書いてある。
. . . それで？
それで、何？
少なくとも、我々の、ナビゲート可能で要素挿入可能なリンクトハッシュマップ、にパフォーマンス上何らかのアドバンテージがあるかテストすべきじゃないか？だって、もし何にもなければ、意味がないだろう . . .
うーん、正直なところ、少なくとも幾分かのアドバンテージがあることは疑っていなかった、たいしたものじゃないとしても、メカニズムを考えれば。
まあ、何かある可能性はあるが、 . . .
オーケー。ちょっとテストしてみよう。
-Hypothesizerは、'coreUtilitiesTestToDisclose'プロジェクトに３つのクラスを書く、若干の時間をかけて。
. . . . . . . . . zzz
いいだろう。これが、我々の、ナビゲート可能で要素挿入可能なリンクトハッシュマップ、のテストクラスだ。
package test.navigablelinkedhashmaptest1;
import java.util.Map;
import thebiasplanet.coreutilities.collections.NavigableLinkedHashMap;
public class Test1Test {
private Test1Test () {
}
public static void main (String [] p_arguments) throws Exception {
int l_numberOfElements = 10000;
int l_mode = 0;
if (p_arguments.length > 0) {
l_numberOfElements = Integer.valueOf (p_arguments [0]);
}
if (p_arguments.length > 1) {
l_mode = Integer.valueOf (p_arguments [1]);
}
Test1Test.test (l_numberOfElements, l_mode);
}
// a_mode: 0 -> without dummy processing, 1 -> with dummy processing, 2 -> show some intermediate results without dummy processing
public static void test (int a_numberOfElements, int a_mode) {
long l_nanoTimeForInsertionStart = -1;
long l_nanoTimeForInsertionStop = -1;
long l_nanoTimeForInsertionAccumulation = 0;
long l_nanoTimeForSearchStart = -1;
long l_nanoTimeForSearchStop = -1;
long l_nanoTimeForIterationStart = -1;
long l_nanoTimeForIterationStop = -1;
int l_power = -1;
NavigableLinkedHashMap <Integer, String> l_navigableLinkedHashMap = new NavigableLinkedHashMap <Integer, String> (a_numberOfElements);
Integer l_lastElement = null;
Integer l_currentElement = null;
Integer l_searchedElement = null;
l_power = 1;
System.out.println ("#For NavigableLinkedHashMap Beginning");
System.out.println ("#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)");
l_nanoTimeForInsertionStart = System.nanoTime ();
l_nanoTimeForInsertionAccumulation = 0;
for (int l_elementIndex = 0; l_elementIndex < a_numberOfElements; l_elementIndex ++) {
l_currentElement = Integer.valueOf (l_elementIndex);
if (l_lastElement != null) {
l_navigableLinkedHashMap.putBefore (((l_elementIndex % 2) == 0) ? l_navigableLinkedHashMap.getNextKey (l_lastElement) : l_lastElement, l_currentElement, "");
}
else {
l_navigableLinkedHashMap.put (l_currentElement , "");
}
l_lastElement = l_currentElement;
// Dummy Processing BEGINNING
if (a_mode == 1 && l_elementIndex == 1) {
l_nanoTimeForInsertionStop = System.nanoTime ();
l_nanoTimeForInsertionAccumulation += l_nanoTimeForInsertionStop - l_nanoTimeForInsertionStart;
l_searchedElement = l_navigableLinkedHashMap.getNextKey (l_lastElement);
for (Map.Entry <Integer, String> l_navigableLinkedHashMapEntry: l_navigableLinkedHashMap.entrySet ()) {
Integer l_element = l_navigableLinkedHashMapEntry.getKey ();
}
l_nanoTimeForInsertionStart = System.nanoTime ();
}
// Dummy Processing END
if (l_elementIndex + 1 == Math.pow (10, l_power)) {
l_nanoTimeForInsertionStop = System.nanoTime ();
l_nanoTimeForInsertionAccumulation += l_nanoTimeForInsertionStop - l_nanoTimeForInsertionStart;
l_nanoTimeForSearchStart = System.nanoTime ();
l_searchedElement = l_navigableLinkedHashMap.getNextKey (l_lastElement);
if (a_mode == 2) {
System.out.println (String.format ("#Searched Element: %d", l_searchedElement));
}
l_nanoTimeForSearchStop = System.nanoTime ();
l_nanoTimeForIterationStart = System.nanoTime ();
for (Map.Entry <Integer, String> l_navigableLinkedHashMapEntry: l_navigableLinkedHashMap.entrySet ()) {
Integer l_element = l_navigableLinkedHashMapEntry.getKey ();
if (a_mode == 2 && l_power == 2) {
System.out.println (String.format ("#Iterated Element: %d", l_element));
}
}
l_nanoTimeForIterationStop = System.nanoTime ();
System.out.println (String.format ("# %,9d: %,18d; %,16d; %,18d", l_elementIndex + 1, l_nanoTimeForInsertionAccumulation, l_nanoTimeForSearchStop - l_nanoTimeForSearchStart, l_nanoTimeForIterationStop - l_nanoTimeForIterationStart));
l_nanoTimeForInsertionStart = System.nanoTime ();
l_power ++;
}
}
System.out.println ("#For NavigableLinkedHashMap End");
}
}
もちろん、'LinkedList'用にも作ったし、実は、'ListOrderedMap'用にも作った。しかし、ここに示すのはやめておこう、ロジックはほとんど同じだから。
-Hypothesizerはターミナルを開き、カレントディレクトリを'coreUtilitiesTestToDisclose'ディレクトリに移し、以下のコマンドを実行する。
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test1Test" -PCOMMAND_LINE_ARGUMENTS="1000000 0"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test2Test" -PCOMMAND_LINE_ARGUMENTS="100000 0"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test3Test" -PCOMMAND_LINE_ARGUMENTS="100000 0"
結果は以下の通りだ。
#For NavigableLinkedHashMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 23,149,950; 4,906; 6,691,418
# 100: 27,823,886; 956; 4,523,059
# 1,000: 57,166,916; 1,005; 17,431,587
# 10,000: 98,915,977; 380; 55,901,657
# 100,000: 401,701,939; 57,463; 339,302,036
# 1,000,000: 1,847,431,862; 54,360; 1,391,781,924
#For NavigableLinkedHashMap End
#For LinkedList Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 673,338; 32,917; 798,186
# 100: 2,880,055; 12,040; 78,205
# 1,000: 36,506,260; 23,692; 5,656,543
# 10,000: 1,047,642,813; 260,234; 6,519,878
# 100,000: 128,732,712,283; 2,437,329; 27,707,494
# 1,000,000: -; -; -
#For LinkedList End
#For ListOrderedMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 7,039,154; 107,793; 58,504,655
# 100: 10,158,446; 10,332; 856,906
# 1,000: 57,747,306; 19,041; 15,046,638
# 10,000: 1,685,974,232; 165,994; 20,261,828
# 100,000: 88,471,135,958; 601,450; 39,563,050
# 1,000,000: -; -; -
#For ListOrderedMap End
zzzzzz . . .
結果は以下の通りだと言ったんだよ！
はあ？. . . 何だこれは？
結果だ！
もちろん、分かっている。. . . これらの数字のそれぞれがどういう意味かを聞いたのだ。
コレクションインスタンス（我々のナビゲート可能で要素挿入可能なリンクトハッシュマップの、または'LinkedList'の,または'ListOrderedMap'の）に一定数の要素を、各要素が最後に挿入された要素の、交互に前または後になるように挿入した。
うむ？その意図は？
その意図は、新たな要素を、常に、既存のリストのほとんど中央に挿入することだ。だって、先頭または末尾に挿入するのは我々のテストとしては意味がないだろう。'LinkedList'インスタンスの先頭または末尾に効率的に挿入できるのは分かりきっている。
もちろん。
要素の数が10、100、1,000、などになったとき、要素数とそこまでの挿入にかかった時間を出力した。次に、コレクションインスタンスから、最後に挿入した要素（ほとんど中央にある要素という意味になる）の次の要素を取得して、そうするのにかかった時間を出力した。次に、コレクションインスタンスの全要素をイテレートして、そうするのにかかった時間を出力した。
それらを、要素数が10の累乗になる度に行なったわけか？
そうだ。短く言うと、上の'NavigableLinkedHashMap'（我々のナビゲート可能で要素挿入可能なリンクトハッシュマップ）の表で、第3行は、1,000要素の挿入に57,166,916ナノ秒かかり、1,000要素から1要素を取得するのに1,005ナノ秒かかり、1,000要素をイテレートするのに17,431,587ナノ秒かかったことを意味する。
君の説明は特に「短く」は思えないが、意味は分かった。
-Rebutterは、しばらくかけて、3つの数表に目を通す。
ふーむ、 . . . 興味深い。
'LinkedList'と'ListOrderedMap'のほうが、挿入は、 要素数が小さい時は速いが、要素数が大きくなると耐え難く遅くなる。
実際、それが、それらに、1,000,000要素のテストをしなかった理由だ。時間がかかりすぎる。
'NavigableLinkedHashMap'のほうが、予期通り検索時間は小さいが、要素数に応じた変化は予期できなかったものだ。なぜ、380へ減少し、突然57,463へ増加し,しかし、1,000,000要素では増加しないのか？
正直、まったく分からない。
これらの数字は、テスト実行毎にそんなに一定していないと思うが。
もちろん、そんなに一定していないが、上記傾向はかなり一定している。
それに、'NavigableLinkedHashMap'のイテレーションは他の2つより遅いな。なぜだ？
まあ、'NavigableLinkedHashMap'は、マップエントリーセットをビューとして作らなければならないという違いはある。イテレータに、マップインスタンスにあるままの要素をイテレートさせるわけにはいかない。
それはあると思うが、'NavigableLinkedHashMap'は'ListOrderedMap'と比べても遅い。
そう。. . . 我々の'entrySet'メソッドが粗野にすぎるだけかもしれない。
'ListOrderedMap'の実装原理は何なのだろうか？
検索時間からすると、ハッシュベースではないようだ。傾向は、我々のマップによりは'LinkedList'のほうに似ているが、ある種の違いもある。
10要素の検索時間とイテレーション時間は、コレクションタイプにかかわらず、なぜ、こんなに不可解に長いのか？
ああ、根本的な理由はわからないが、それは、要素数のためではなく、最初の計測だからだ。実際、テストを以下のように、別のモードで動かすと、それらのアノマリーは消える。
-Hypothesizerは、以下のコマンドを実行する。
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test1Test" -PCOMMAND_LINE_ARGUMENTS="1000000 1"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test2Test" -PCOMMAND_LINE_ARGUMENTS="100000 1"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test3Test" -PCOMMAND_LINE_ARGUMENTS="100000 1"
#For NavigableLinkedHashMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 28,520,467; 2,908; 156,256
# 100: 33,321,037; 797; 2,413,758
# 1,000: 38,163,177; 1,065; 13,511,453
# 10,000: 89,912,506; 391; 30,831,210
# 100,000: 395,634,986; 62,369; 234,624,658
# 1,000,000: 1,879,539,755; 57,196; 1,385,221,677
#For NavigableLinkedHashMap End
#For LinkedList Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 647,509; 3,608; 12,280
# 100: 2,723,686; 9,707; 76,147
# 1,000: 63,961,605; 23,011; 7,731,741
# 10,000: 1,384,062,815; 259,357; 4,904,449
# 100,000: 132,988,500,832; 2,434,372; 28,290,306
# 1,000,000: -; -; -
#For LinkedList End
#For ListOrderedMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 510,002; 5,851; 32,134
# 100: 3,148,831; 8,390; 2,031,163
# 1,000: 49,244,310; 16,848; 15,572,011
# 10,000: 920,952,896; 168,168; 8,021,630
# 100,000: 82,659,823,277; 655,516; 41,154,981
# 1,000,000: -; -; -
#For ListOrderedMap End
うむ？'NavigableLinkedHashMap'の検索時間のアノマリーが消えたようには見えないな、私には。. .
そう . . .、しかし、別のアノマリーは消えた。
なぜ、'NavigableLinkedHashMap'の検索時間のだけ消えない？
知らない。
新しいモードでは何をしたのか？
要素数が2のときに、密かに、検索とイテレーションをしただけだ。
ふーむ、すると、最初の検索と最初のイテレーションには長い時間がかかるわけだ、なぜか . . .
正直、その裏にあるメカニズムは知らない。. .
とにかく、これらのテストコードをzipファイルに含めたが、'Test3Test'は、ソースファイルをリネームして無効化しておいた。Apache commonsのJarファイルをzipファイルに含めなかったから、さもないと、プロジェクトが正常にビルドできない。有効化するには、Apache commonsのJarファイルをダウンロードし、そのJarファイルを、プロジェクト用GradleビルドスクリプトまたはAntビルドファイルの'OTHER_CLASSES_PATHS'に登録し、'Test3Test'のソースファイル名を元に戻せばよい。
- Oracle and/or its affiliates. (2017). Overview (Java Platform SE 8). Retrieved from https://docs.oracle.com/javase/8/docs/api/
- The Apache Software Foundation. (2017). Overview (Apache Commons Collections 4.2-SNAPSHOT API). Retrieved from https://commons.apache.org/proper/commons-collections/apidocs/
<このシリーズの、前の記事 | このシリーズの目次 |
