DSL_2_C: Range Search (kD Tree) (続き4)

で自作データでやってたらバグが見つかったという
境界となる点を求めるのにこんな関数を使っていたんだけれども

def find_mid(points, indices, dir):
    return points[indices[len(indices) // 2]][dir]

これだとたとえば3つの点のx座標が2,2,3だったとき、境界が2になって
境界で分けたときに[]と[2,2,3]に分かれてしまう
これはよくない
ていうか運が悪くてy座標も2,2,3だったりすると無限ループ

えーとちゃんとやるにはと
ユニークな値だけ集めてから境界値？
こう？

def find_mid(points, indices, dir):
    s = sorted(set(points[x][dir] for x in indices))
    return s[len(s)//2]

これでまた遅くなるわけだな
Case #12が04.28sに（涙

いやそもそも
同一座標の点がふたつあったらそれで無限ループになってしまうな
そう思って読み直すと同じ座標の点が含まれてないとは書いてない

・・・判定入れてもいいけどそこって大事じゃない気がするな
同一の点は含まないことにしておこう

それより、indicesをソートしたりユニークな値を拾ったりと
手間をかけて真ん中を探すっていうのが方向違いなのかも知れない
クイックソートだって先頭から取ってる例が多いし
ただ今回は適当にやると無限ループになるからそこは考慮しないといけない
ということでランダムな要素を選ぶことに（てきとう
検索には時間がかかるようになると思うけど
前処理がうんと速くなればペイするかも

def find_mid(points, indices, dir):
    return points[indices[randrange(len(indices))]][dir]

だめでした #12で3.64s

プロファイルはこんな感じ
前処理が期待したほど速くなってないなあ
検索がほぼ２倍時間かかるように

         15162931 function calls (8418353 primitive calls) in 17.954 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   17.848   17.848 DSL_2_C.py:144(main)
        1    0.127    0.127   11.780   11.780 DSL_2_C.py:133(process_queries)
    10000    0.013    0.000    9.964    0.001 DSL_2_C.py:102(find_points)
6499980/10000    9.377    0.000    9.435    0.001 DSL_2_C.py:106(rec)
        1    0.004    0.004    5.740    5.740 DSL_2_C.py:87(make_area_tree)
 254556/1    0.600    0.000    5.736    5.736 DSL_2_C.py:57(divide_area)
   254555    1.296    0.000    3.252    0.000 copy.py:66(copy)
    20000    1.634    0.000    1.634    0.000 {built-in method builtins.print}
   154566    0.964    0.000    1.256    0.000 DSL_2_C.py:46(partition)
   254555    0.521    0.000    1.187    0.000 copy.py:268(_reconstruct)
   154566    0.139    0.000    0.585    0.000 DSL_2_C.py:40(find_mid)
    10000    0.515    0.000    0.515    0.000 {method 'sort' of 'list' objects}
   154566    0.148    0.000    0.425    0.000 random.py:173(randrange)
  3020410    0.364    0.000    0.364    0.000 {method 'append' of 'list' objects}
        1    0.143    0.143    0.328    0.328 DSL_2_C.py:25(read_points)