DartのList<T>のデータのソートとサーチでこんなのがあったあらよかったのにというのを紹介。
- ソートキーが2つ以上ある場合、比較関数をもっとスマートに実装できないか。
- サーチでKeyではなくValueで検索したい場合。
ソートキーが複数ある場合の実装
データをソートするときに、名前順とか日付順とかでソートする場合、そのキーが重複している場合の対処をする場合、第2キーや、最終キーなどにユニークなキーを置いて、複数キーでソートするのが普通だと思う。
その場合の一般的な比較関数の書き方は以下の様な感じになるのではないか。
例えば、以下の様なDataクラスのListの場合。
class Data {
const Data(this.a, this.b, this.id);
final String a;
final DateTime b;
final int id;
}
void main(List<String> args) {
final List<Data> lists = [
Data("a", DateTime(2017, 10, 7, 17, 30), 1),
Data("a", DateTime(2017, 9, 7, 17, 30), 2),
Data("1", DateTime(2018, 9, 7, 17, 30), 3),
Data("b", DateTime(2017, 9, 7, 17, 30), 4),
];
for (final data in lists) {
print("${data.a} ${data.b} ${data.id}");
}
}第1キーをaに、最終キーをidにした場合の比較は以下の様になる。
// 第1キーがaで最終キーがid
lists.sort((a, b) {
final result = a.a.compareTo(b.a);
if (result == 0) {
return a.id.compareTo(b.id);
} else {
return result;
}
});これでもいいのだけど、なんかやぼったい感じがする。
そこで、以下の様にintの拡張を作って実装してみる。
/// intの比較用拡張でnextで第2キーを指定できる
extension Compare on int {
int next(int Function() func) {
return this == 0 ? func() : this;
}
}これをもとにした比較関数が以下になる。
lists.sort(((a, b) => a.a.compareTo(b.a).next(() => a.id.compareTo(b.id))));if文が抜けたので結構見やすくなるのではないかと思う。
これは、if文判断をnextというメソッドにまとめて、ついでに次の検索キーを指定させるという感じに作ってみたというもの。
サーチでKeyではなくValueで検索したい場合
こちらはソート済みのList<E>をバイナリサーチする場合の話。
バイナリサーチのメソッドは、coreの方には入っておらず拡張としてcollectionで提供されている。
ここでKeyといっているのはList<E>のEをKeyとして検索するというもの。
binarySearch～では検索キーをelementのパラメータ名として用意しているのだけどその型はEになる。
これはこれで使うのだろうけど、他によく使うのはEという型にしないで別の値を検索キーとして使うケース。
上の「class Data」及び「List<Data>」でいうと、通常はDataを作ってそれをキーにするのだけど、それをString及びint(id)の2パラメータを使用したデータを検索キーにしたい、という欲求。
例えば以下の様な感じ。
// collectionを使った場合
var result = lists.binarySearch(Data("a", DateTime.now(), 1),
(a, b) => a.a.compareTo(b.a).next(() => a.id.compareTo(b.id)));Collection側はDataを作らなければいけないのだけど、このDataを構築するのにコスト（実装上のコスト含む）がかかる場合はかなり面倒になる。
実際に同じように思う人がいるらしく、collectionのgithubにissuesとしてあげられていた。
どうなるかなとウォッチしてたのだけど、結果トンデモ回答でCloseされてしまっていた。
binarySerach用とlowerBound用の実装として使う場合は、以下のを参考にしてほしい。
int binarySearchByKey<E, K>(List<E> sortedList, K Function(E element) keyOf,
int Function(K, K) compare, K key,
[int start = 0, int? end]) {
end = RangeError.checkValidRange(start, end, sortedList.length);
var min = start;
var max = end;
while (min < max) {
var mid = min + ((max - min) >> 1);
var element = sortedList[mid];
var comp = compare(keyOf(element), key);
if (comp == 0) return mid;
if (comp < 0) {
min = mid + 1;
} else {
max = mid;
}
}
return -1;
}
/// キーを使ったKeyの最初の位置検索
int lowerBoundByKey<E, K>(List<E> sortedList, K Function(E element) keyOf,
int Function(K, K) compare, K key,
[int start = 0, int? end]) {
end = RangeError.checkValidRange(start, end, sortedList.length);
var min = start;
var max = end;
while (min < max) {
var mid = min + ((max - min) >> 1);
var element = sortedList[mid];
var comp = compare(keyOf(element), key);
if (comp < 0) {
min = mid + 1;
} else {
max = mid;
}
}
return min;
}これで前の検索を実装してみると以下の様な感じになる。
// 下で示すbinarySearchByKeyを使った場合
result = binarySearchByKey<Data, List<dynamic>>(
lists,
(key) => [key.a, key.id],
(a, b) => (a[0] as String)
.compareTo(b[0] as String)
.next(() => (a[1] as int).compareTo(b[1] as int)),
["a", 1]);Dataを構築しないのでsortした際の比較関数は使用できないのだけど、Dataを構築しなくても検索できるので使いやすいケースもあると思う。
コメント