高速Nearest関数

code: https://colab.research.google.com/drive/1aZGlDpDZKShpAzCW_w4xJ1lAnXnkNWAA

-1から1を範囲に持つ３次元データを100万個生成し、pointsとします。

In [ ]:
points = RandomReal[{-1, 1}, {100000000, 3}];

点集合pointsに対し、点{0,0,0}から最も近い点10個を選びます。

計算内部では連想形式でデータを保持し、キー"Element"は値を、キー"Index"は点集合内のインデックスを、キー"Distance"は実際の距離を保持します。

In [ ]:
Timing[
  Nearest[points -> All, {0, 0, 0}, 10] ]
Out[ ]:
{0.804811, {<|Element -> {-0.000592109, 0.00074285, 0.00280029}, Index -> 2147735, Distance -> 0.00295704|>, <|Element -> {-0.000196012, 0.000287628, -0.00416973}, Index -> 52781578, Distance -> 0.00418423|>, <|Element -> {-0.00186127, -0.0010087, 0.0037282}, Index -> 26749638, Distance -> 0.00428733|>, <|Element -> {0.00394233, -0.00171932, -0.00155872}, Index -> 41570499, Distance -> 0.00457467|>, <|Element -> {0.00245737, 0.00398018, 0.00124364}, Index -> 51676531, Distance -> 0.00484016|>, <|Element -> {-0.00146834, 0.00243729, 0.00417856}, Index -> 93206195, Distance -> 0.00505537|>, <|Element -> {-0.00426879, 0.000443966, -0.00344119}, Index -> 10772377, Distance -> 0.00550105|>, <|Element -> {-0.00341679, 0.00454887, 0.000660731}, Index -> 88892845, Distance -> 0.00572741|>, <|Element -> {0.00491854, 0.000919225, -0.00299445}, Index -> 82784110, Distance -> 0.00583127|>, <|Element -> {-0.00528791, 0.000103233, -0.00284723}, Index -> 32926632, Distance -> 0.00600662|>}}

距離情報だけを取り出します。

In [ ]:
Timing[
  Nearest[points -> "Distance", {0, 0, 0}, 10]]
Out[ ]:
{0.009761, {0.00469279, 0.0119717, 0.0146737, 0.0154951, 0.0161344, 0.0213999, 0.0239279, 0.0248331, 0.027007, 0.0271181}}

インデックス情報のみを取り出します。

In [ ]:
Timing[
  Nearest[points ->"Index", {0, 0, 0}, 10] ]
Out[ ]:
{0.009775, {937171, 767805, 680256, 997518, 96144, 820169, 171383, 526479, 546183, 729947}}

距離0.02以内にあるすべての点のインデックスのみを取り出します。

In [ ]:
Nearest[points -> "Index", {0, 0, 0}, {All, 0.02}]
Out[ ]:
{937171, 767805, 680256, 997518, 96144}

オブジェクトidと座標の連想リストに対し、複数の拠点に近接するオブジェクトidのリストを返す関数を作る。

In [ ]:
size = 1000000;
Timing[
 (*Field=<オブジェクト\[Rule]座標の連想集合>*)
 Field = MapThread[Rule, {
    (*オブジェクトIDの集合*)
    IDS = Table[Unique["ga"], {size}],
    (*対応する座標の集合 *)
    RandomReal[{-1, 1}, {size, 3}]}
   ];
 (*Ruleのリストに関し直接連想化するより２段階にばらした方が高速*)
 Field = Association[Field];]
Out[ ]:
Output
In [ ]:
findNeighbors[field_, ids_, n_, dist_] :=
 (*
 入力：field 場Field
    ids オブジェクトの集合IDS
 　　n 探索サイズ
    dist 指定距離
 出力：指定距離内のオブジェクトリスト
 *)
 Module[{points, group, centers, neighbors},
  points = Values[field];
  (*ここではランダムにn個選択*)
  group = RandomChoice[ids, n];
  centers = field[#] & /@ group;
  neighbors =
   Nearest[points -> "Index", centers, {All, dist}];
  (*Nearestは複数の拠点から近傍を探索することが可能*)
  ids[[#]] & /@ neighbors]
In [ ]:
Timing[
 (*10000箇所拠点を決め、各拠点から距離0.02以内にあるオブジェクトIDのリストを求める*)
 
 neighborList = findNeighbors[Field, IDS, 10000, 0.02];]
Out[ ]:
Output
In [ ]:
neighborList // Short
Out[ ]:
Output
In [ ]: