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万個でやったら前処理で時間切れだな