今回はDartの言語について少し紹介です！
key→valueを紐づけるデータ構造としてDartではMapやSplayTreeMapが用意されています。
一般的な言語で対応するものは…
C++ → unordered_map / map
C# → Dictionary / SortedDictionary
Java → HashMap / TreeMap
Python → dict / OrderedDict
この説明で納得できた方は終わりです。閲覧ありがとうございました！
何ができるのか
MapやSplayTreeMapはkeyとvalueを紐づけるデータ構造として考えることができます。
key : アクセスする際に指定する要素。辞書の索引
value : keyで指定した場所にある要素。辞書の内容・説明
例えば「パソコン」と辞書で調べると「パーソナルコンピュータの略」と記されているとします。このとき、「パソコン」がkeyで「パーソナルコンピュータの略」がvalueとなります。
MapやSplayTreeMapはkeyの型もvalueの値の範囲も自由に取ることができます。
プログラムの例で確認してみましょう！
void main() {
Map<int, String> map = {1: "1番目", 5: "5番目", 57: "素数", 1729: "タクシー"};
print("${map[1]}, ${map[1729]}"); // → 1番目, タクシー
String? str = map[57]; // → 素数
print(str);
String? nullStr = map[333];
print(nullStr); // → null
}この例ではkeyをint、valueをStringとしていますので 整数→文字列 の紐づけをしていますね！
注意点として、map[333]のように存在しないkeyを指定するとnullが帰ってきます。
nullチェックをして処理を分岐したり、null値をデフォルト値で埋めたりしましょう??
SplayTreeMapも同様に扱うことができます。
importが増えて変数がspMapに変わっただけで扱い方も結果も全く同じになっていますね。
import 'dart:collection';
void main() {
Map<int, String> map = {1: "1番目", 5: "5番目", 57: "素数", 1729: "タクシー"};
SplayTreeMap<int, String> spMap = SplayTreeMap.from(map);
print("${spMap[1]}, ${spMap[1729]}"); // → 1番目, タクシー
String? str = spMap[57]; // → 素数
print(str);
String? nullStr = spMap[333];
print(nullStr); // → null
}MapとSplayTreeMapの違い
MapとSplayTreeMapの違いは内部の実装方法です！
それによって要素へのアクセスやkeyの順次アクセスに速度の違いが生まれます。
Map
実装 ： HashMap。keyのハッシュ値を計算してvalueにアクセス
順序 ： 保証されない。挿入順やkeyの値から内部の要素の順番を推測できない
速度 ： 1要素の挿入/削除/検索はO(1)。ハッシュの衝突が多い場合は最悪O(n)
用途 ： keyの順番に意味が無い場合。ユーザID→ユーザ情報 へのアクセスなど
SplayTreeMap
実装 ： Splay木。平衡二分探索木の一種。
順序 ： keyの順序が保証される。最初の例では1→5→57→1729となる。
速度 ： 1要素の挿入/削除/検索はO(log(n))。
用途 ： keyの順番に意味が有る場合。得点→ユーザ情報 へのアクセスなど。
速度比較 (書き込み)
実際にどれぐらいの速度差があるのか確認しましょう！
MapとSplayTreeMapそれぞれに100万回ランダムな値を書き込んでみます。
そのテストを10回ずつ行い平均時間を算出してみます。
Mapの速度 (書き込み)
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
Map<int, int> map = {};
Random random = Random();
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// ランダムなkeyにランダムな値を100万回書き込む
for (int i = 0; i < num; i++) {
int key = random.nextInt(num);
int value = random.nextInt(num);
map[key] = value;
}
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}書き込みにかかった時間: 156ミリ秒
書き込みにかかった時間: 137ミリ秒
書き込みにかかった時間: 136ミリ秒
書き込みにかかった時間: 142ミリ秒
書き込みにかかった時間: 141ミリ秒
書き込みにかかった時間: 170ミリ秒
書き込みにかかった時間: 169ミリ秒
書き込みにかかった時間: 138ミリ秒
書き込みにかかった時間: 158ミリ秒
書き込みにかかった時間: 148ミリ秒
平均時間: 149.5SplayTreeMapの速度 (書き込み)
import "dart:collection";
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
SplayTreeMap<int, int> spMap = SplayTreeMap<int, int>();
Random random = Random();
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// ランダムなkeyにランダムな値を100万回書き込む
for (int i = 0; i < num; i++) {
int key = random.nextInt(num);
int value = random.nextInt(num);
spMap[key] = value;
}
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}書き込みにかかった時間: 1212ミリ秒
書き込みにかかった時間: 1196ミリ秒
書き込みにかかった時間: 1199ミリ秒
書き込みにかかった時間: 1206ミリ秒
書き込みにかかった時間: 1257ミリ秒
書き込みにかかった時間: 1255ミリ秒
書き込みにかかった時間: 1241ミリ秒
書き込みにかかった時間: 1239ミリ秒
書き込みにかかった時間: 1297ミリ秒
書き込みにかかった時間: 1209ミリ秒
平均時間: 1231.1速度比較
Mapは平均149.5ミリ秒でSplayTreeMapは平均1231.1ミリ秒でした！
おおよそ8倍の差がつきました！
log2(10^6) ≒ 20 ですので、オーダーだけで考えると20倍の差がついても良さそうです。8倍程度に収まったのはハッシュ値の計算など定数倍の影響によるものでしょう。
ハッシュ値の計算が重いのかSplay木の定数倍が軽いのか情報あれば教えてくださると嬉しいです！
速度比較 (読み込み)
次はランダムアクセスの速度を測ってみましょう！
最初に0~100万のkeyにランダムな値を書き込んでおきます。
その後、100万回ランダムなkeyにアクセスをしてその速度を比較します！
Mapの速度 (読み込み)
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
Map<int, int> map = {};
Random random = Random();
// [0,num)にランダムな値を用意
for (int i = 0; i < num; ++i) map[i] = random.nextInt(num);
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// [0,num)の範囲で100万回ランダムアクセス
for (int i = 0; i < num; i++) {
int key = random.nextInt(num);
int? value = map[key];
}
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}書き込みにかかった時間: 134ミリ秒
書き込みにかかった時間: 97ミリ秒
書き込みにかかった時間: 87ミリ秒
書き込みにかかった時間: 79ミリ秒
書き込みにかかった時間: 75ミリ秒
書き込みにかかった時間: 83ミリ秒
書き込みにかかった時間: 82ミリ秒
書き込みにかかった時間: 89ミリ秒
書き込みにかかった時間: 80ミリ秒
書き込みにかかった時間: 84ミリ秒
平均時間: 89.0SplayTreeMapの速度 (読み込み)
import "dart:collection";
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
SplayTreeMap<int, int> spMap = SplayTreeMap<int, int>();
Random random = Random();
// [0,num)にランダムな値を用意
for (int i = 0; i < num; ++i) spMap[i] = random.nextInt(num);
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// [0,num)の範囲で100万回ランダムアクセス
for (int i = 0; i < num; i++) {
int key = random.nextInt(num);
int? value = spMap[key];
}
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}書き込みにかかった時間: 1066ミリ秒
書き込みにかかった時間: 1132ミリ秒
書き込みにかかった時間: 1087ミリ秒
書き込みにかかった時間: 1112ミリ秒
書き込みにかかった時間: 1112ミリ秒
書き込みにかかった時間: 1149ミリ秒
書き込みにかかった時間: 1145ミリ秒
書き込みにかかった時間: 1132ミリ秒
書き込みにかかった時間: 1120ミリ秒
書き込みにかかった時間: 1131ミリ秒
平均時間: 1118.6速度比較
Mapは平均89.0ミリ秒でSplayTreeMapは平均1118.6ミリ秒でした！
こちらも大きな差がつきました！オーダーを考えれば当然
MapとSplayTreeMapの両方で速度が早くなってるのは、書き込みと違ってメモリを確保しなくて良くなったからでしょう。
速度比較 (順次アクセス)
最後はkeyの昇順にデータにアクセスしてみましょう！
ランダムアクセスではMapの圧勝ですが、SplayTreeMapはkeyの順序が保証されるメリットがあります。ここらで有用性を示してもらいましょう！
Mapの順次アクセス方法
まずはこちらのコードと実行結果をご覧ください。
import "dart:io";
void main() {
int num = 10;
// Mapと乱数の初期化
Map<int, int> map = {};
// [0,num)をランダムな順番に挿入
List<int> shuffled = List.generate(num, (index) => index);
shuffled.shuffle();
for (int i = 0; i < num; ++i) map[shuffled[i]] = i;
// 各keyとvalueに対して繰り返し
map.forEach((key, value) {
stdout.write("${key} ");
});
}7 5 9 0 8 4 6 1 2 3 順番がバラバラに表示されていますね！
これがMapの持つ特性である「keyの順序を保証しない」です。
筆者の環境では0~9の順番に挿入するとforEachのkeyも連番になっていたので、挿入順をシャッフルしています💧
同じコードでSplayTreeMapのforEachを確認してみましょう！
import "dart:collection";
import "dart:io";
void main() {
int num = 10;
// Mapと乱数の初期化
SplayTreeMap<int, int> spMap = SplayTreeMap<int, int>();
// [0,num)をランダムな順番に挿入
List<int> shuffled = List.generate(num, (index) => index);
shuffled.shuffle();
for (int i = 0; i < num; ++i) spMap[shuffled[i]] = i;
// 各keyとvalueに対して繰り返し
spMap.forEach((key, value) {
stdout.write("${key} ");
});
}0 1 2 3 4 5 6 7 8 9 ランダムな順番で挿入しましたがforEachはkeyの値が昇順になっていますね！
以上を踏まえて、順次アクセスの方法は以下の通りとします。
Map → keyをソートしてイテレーション
SplayTreeMap → forEachでイテレーション
Mapの速度 (順次アクセス)
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
Map<int, int> map = {};
Random random = Random();
// [0,num)をランダムな順番に挿入
List<int> shuffled = List.generate(num, (index) => index)..shuffle();
for (int i = 0; i < num; ++i) map[shuffled[i]] = i;
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// keyの昇順にイテレーション
List<int> keys = map.keys.toList()..sort();
for (var key in keys) {
int? value = map[key];
}
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}書き込みにかかった時間: 441ミリ秒
書き込みにかかった時間: 335ミリ秒
書き込みにかかった時間: 321ミリ秒
書き込みにかかった時間: 316ミリ秒
書き込みにかかった時間: 318ミリ秒
書き込みにかかった時間: 314ミリ秒
書き込みにかかった時間: 319ミリ秒
書き込みにかかった時間: 312ミリ秒
書き込みにかかった時間: 317ミリ秒
書き込みにかかった時間: 316ミリ秒
平均時間: 330.9SplayTreeMapの速度 (順次アクセス)
import "dart:collection";
import "dart:math";
void main() {
List<int> result = [];
for (int i = 0; i < 10; ++i) result.add(mapTest());
print("平均時間: ${result.reduce((a, b) => a + b) / result.length}");
}
int mapTest() {
// 書き込み回数
int num = 1000000;
// Mapと乱数の初期化
SplayTreeMap<int, int> spMap = SplayTreeMap<int, int>();
Random random = Random();
// [0,num)をランダムな順番に挿入
List<int> shuffled = List.generate(num, (index) => index)..shuffle();
for (int i = 0; i < num; ++i) spMap[shuffled[i]] = i;
// 時間計測開始
Stopwatch stopwatch = Stopwatch()..start();
// keyの昇順にイテレーション
spMap.forEach((key, value) {
int value2 = value;
});
// 時間計測終了
stopwatch.stop();
print("書き込みにかかった時間: ${stopwatch.elapsedMilliseconds}ミリ秒");
return stopwatch.elapsedMilliseconds;
}
書き込みにかかった時間: 100ミリ秒
書き込みにかかった時間: 90ミリ秒
書き込みにかかった時間: 93ミリ秒
書き込みにかかった時間: 89ミリ秒
書き込みにかかった時間: 85ミリ秒
書き込みにかかった時間: 86ミリ秒
書き込みにかかった時間: 89ミリ秒
書き込みにかかった時間: 93ミリ秒
書き込みにかかった時間: 83ミリ秒
書き込みにかかった時間: 85ミリ秒
平均時間: 89.3速度比較
Mapは平均330.9ミリ秒でSplayTreeMapは平均89.3ミリ秒でした！
ついにSplayTreeMapが勝ちました！別に勝負はしていませんが
オーダーで評価するとMapはO(nlog(n))、SplayTreeMapはO(n)です！
Mapはバラバラのkeyをソートすることがネックになっています。
SplayTreeMapはkeyの順序が保証されているのでソートの必要がなく線形時間になっています。
速度比較は以上です！
ランダムアクセスするならMap。
keyの順序を保って列挙するならSplayTreeMap。
これだけ覚えて快適なDart/Flutterライフを！！
※補足
思ったよりもSplayTreeMapの順次アクセスが遅いと感じたかもおられるでしょうか✋️
SplayTreeMapは完全な平衡二分探索木であることが保証されておらず、最悪計算量はO(n)のようです。今回は挿入順をシャッフルしているため、乱数によっては木の均衡が崩れて計算量が増えるパターンもありそうです。
しかし悪いところばかりではなく、頻繁にアクセスする要素ほど根に集まる特性を持つため局所性の有るデータ群に対してはO(1)に近づくとされています。
データのアクセス頻度に偏りが無い場合や最悪計算量を改善したい場合は赤黒木ライブラリを使うことをおすすめします。
→ red_black_tree_collection
※補足の補足
Mapの読み書きの速度と比較するとSplayTreeMapが遅いわけではなさそうです。
map.keys.toList()..sort()のソートがかなり速いのでボトルネックにならずに300ミリ秒台が出てそう？
この記事が役に立ちましたらぜひ左下のGoodボタンをお願いします！
皆様のGoodが執筆の励みになります。
コメント