kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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

なんか高速化の余地あるかな
お手軽なところから探してみよう

答えには影響ないのでわざと後回しにしてたところがある

分ける基準になった点はどっちに入れる?両方?

両方の領域に入れるというのはうまくなさそうだったので
右側または上側にいれることにした
その代り、境界を0.5だけずらしてる

そうすると、座標がマイナス10億以上10億以下なのは
座標を2倍にしろというお告げに見えてくる
そうすれば整数

やってみた
Case #13でTLE

って変わってへんやんけ!
Case #12がデータ10万個、#13がデータ40万個だから速くなってもわからないだけかもね

Case #12を解いた時間で見てみよう
今回は3.72s
修正前は3.74s
って目を疑うほど変わってないな

2倍するだけのことをかっこつけて関数で書いてたので単純に*2って書いたら
3.69sになった
誤差の範囲

input()の代わりにstdin.readline()を使う
3.45sに
まあ一応

入力データまるごと取れたらプロファイリングしてみたいところだけれども
途中で切れてるんだよなあ

答えは合ってるんだから自分でデータ作ればいいのか
点の数10万(から重複分を削除)、問い合わせ1万回のテストファイル作成

from random import randrange

n = 100000
q = 10000

MIN = -10000
MAX = 10000
RANGE = 1000

points = set()
for _ in range(n):
    points.add((randrange(MIN, MAX), randrange(MIN, MAX)))

print(len(points))
for p in points:
    print(p[0], p[1])

print(q)
for _ in range(q):
    sx = randrange(MIN, MAX-RANGE)
    sy = randrange(MIN, MAX-RANGE)
    print(sx, sx+RANGE, sy, sy+RANGE)

でプロファイリングってどうやるんだ
こうか

$ python3 -m cProfile -s cumulative DSL_2_C.py < in.txt

主要なところだけ抜粋

         12825811 function calls (9424502 primitive calls) in 15.204 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   15.146   15.146 DSL_2_C.py:145(main)
        1    0.149    0.149    7.432    7.432 DSL_2_C.py:134(process_queries)
        1    0.004    0.004    7.312    7.312 DSL_2_C.py:88(make_area_tree)
 200634/1    0.799    0.000    7.308    7.308 DSL_2_C.py:54(divide_area)
    10000    0.014    0.000    5.593    0.001 DSL_2_C.py:103(find_points)
3210676/10000    4.959    0.000    4.994    0.000 DSL_2_C.py:107(rec)
   110644    1.721    0.000    2.268    0.000 {method 'sort' of 'list' objects}
   200633    0.645    0.000    2.147    0.000 copy.py:66(copy)
   100644    0.827    0.000    1.662    0.000 DSL_2_C.py:37(find_mid)
    20000    1.605    0.000    1.605    0.000 {built-in method builtins.print}
   100644    0.765    0.000    0.984    0.000 DSL_2_C.py:43(partition)
        1    0.180    0.180    0.402    0.402 DSL_2_C.py:25(read_points)
  2089936    0.272    0.000    0.272    0.000 {method 'append' of 'list' objects}

さすがに前処理(make_area_tree)に時間かけすぎ?
10秒でTLEになるわけだから

プロファイリングなしでも12秒だから、この中で前処理が6秒程度

$ time python3  DSL_2_C.py < in.txt > out.txt

real    0m12.425s
user    0m12.003s
sys     0m0.201s

50万個でやったら前処理で時間切れだな