4万件のデータを持つ配列を高速で探せる方法 (データ検索)

はじめに

今回はコミュニティ参加者の方から業務で行っているデータ検索について質問がありましたので、そちらを書いていきます。

質問内容

課題
4 万件のデータを持つ配列を高速で探せる方法 (データ検索)

状態
二次元配列かつ、中身の型はバラバラ (部分的にソートされてるっぽいかも..?)
ソートされて無い状態の input データを直接そのまま取ってきている状態

条件
検索条件は文字列だけなのかな？ → 文字列のみ
検索回数は一回で完結させなきゃいけない？ → 検索回数は１回で完結させなきゃいけないわけではない
データがの場合はあるか？→ なし
検索文字は任意? → 任意
検索対象はエクセル内のデータ？または csv or tsv？ → エクセル内のデータ>（CSV の検索もしなきゃいけないのですが。。。）
エクセル内のデータってフィルターで並べ替えできると思うんですが、それって禁止されている？ できるならそれ自体がソートなのでコスト軽い

対応策

vba で検索対象のシートをコピー

exel と、おなじ機能でソート

ソートしたデータを元に検索

コピーしたシートを消去

※もし、場所が知りたいのであれば id が振られているということだったので、元のシートの id の場所で割り出せる

参考: https://officedic.com/excel-vba-sorts-set/

リニアサーチ（線形探索法）について

先頭から順番に探す値が見つかるまで探していく
データを端から順番に「探す値が見つかるまで」調べていく方法

ティムソート

マージソートは再起関数を使って、分割して実行するやつ
ティムソートはマージソートの進化版(?)

おすすめのサイト: http://福嶋.jp/mobile/movie/ar

まとめ

やりたいことは同じでも条件によってベストプラクティスは変わっていく。
現在、置かれている状況把握や条件の洗い出しは早期課題解決の第一歩になる。