AtCoderでユーザーおよび問題をイロレーティングで評価してみた その2

概要

　前回の投稿で、ABC(AtCoder Beginner Contest)の問題のレーティングを計算しました。しかしどうせならARCの結果も欲しい！
　ということでそちらも取得して計算してみました。また、プログラムも多少改良しました。

複数スレッドによる並列クロール

　前回のコードでは、1ページづつOpen-URIでアクセスしてからNokogiriで読み取っていました。しかしそれだと遅い！明らかに遅い！
　ということで、様々な手段を講じてみました。

• 「第三者のAPIを使って楽できないか」……非公式APIその1や非公式APIその2にアクセスすれば楽できるのではと思いましたが、非公式APIも結局はクロールして結果の一部をJSONで返すだけですので、今回のような高頻度アクセスに向いていません(具体的には遅い＆許容レスポンス量が低い)。よってボツ
• 「em-http-requestで非同期リクエスト」……このページなどを見ながら書いたら確かに速いんですよね。ただ、使用しているうちになぜかAtCoderへのリクエストが全て失敗するという謎のトラブルに見舞われまして、結局ボツ
• 「threadで複数スレッドを生成してopenしまくる」……冷静に考えると雑な発想ですが、結局これが一番当たりました。ただし、各ページごとにスレッドを生成するとオーバーヘッドがデカすぎるので、とりあえずコンテスト毎にスレッドを生成して並行動作させる作戦にしました。意味不明なことに「Rubyのthreadはマルチスレッド動作しない」(同時に実行されるネイティブスレッドが常に1つ)のですが、I/O待ちについては謎制限(GVL)を解いてくれるため、今回のような並列アクセス用途にはぴったりですね。

　結果、最後の手段を採用して、高速化を果たしました。コードはこちら。

download2.rb

# 対戦結果を生成する

require 'nokogiri'
require 'open-uri'
require 'thread'

# まず、全コンテストについての情報を入手する
contest_list = []
1.upto(33){|i|contest_list.push("abc#{sprintf('%03d', i)}")}
1.upto(47){|i|contest_list.push("arc#{sprintf('%03d', i)}")}
# 次に、各コンテスト毎に結果を取得し取り込む
output = {}
query_list = ['A', 'B', 'C', 'D']
threads = []
start_time = Time.now
contest_list.each{|contest_name|
    # スレッド生成
    threads << Thread.new{
        # 下準備
        name_list = {}
        ac_name_list = {}
        query_list.each{|query|ac_name_list[query] = Hash.new(0)}
        # とり込み実行
        1.upto(0/0.0){|page|
            # ページをダウンロードする
            url = "http://#{contest_name}.contest.atcoder.jp/submissions/all/#{page}"
            charset = ''
            while true
                begin
                    html = open(url){|f|charset=f.charset;f.read}
                    break
                rescue
                    next
                end
            end
            # 結果を解析する
            doc = Nokogiri::HTML.parse(html, nil, charset)
            nodes = doc.css('table[class="table table-bordered table-striped table-wb"] > tbody > tr')
            if nodes.size == 0 then
                break
            end
            puts "#{contest_name} #{page} #{nodes.size}"
            nodes.each{|node|
                query = (node.css('td > a')[0].inner_text)[0]
                name = node.css('td > a')[1].inner_text
                result = node.css('td > span').inner_text
                name_list[name] = 1
                if result == 'AC' then
                    begin
                        ac_name_list[query][name] = 1
                    rescue
                    end
                end
            }
        }
        # 結果を書き出す
        name_list.keys.each{|name|
            query_list.each{|query|
                output["[#{contest_name}_#{query}],#{name},#{(ac_name_list[query][name] == 1 ? 'Win' : 'Lose')}"] = 1
            }
        }
    }
}
threads.each{|t|t.join}
end_time = Time.now
File.write('log.txt', output.keys.join("\n"))
puts start_time
puts end_time
puts end_time - start_time

計算結果(AtCoder Beginner Contest)

　こちらは前回と同じ結果になりました。レーティングの数値自体は微妙に変わっていますが、ARCの結果も含めたので仕方ないでしょう。

問題Aで最易　問題Aで最難
問題Bで最易　問題Bで最難
問題Cで最易　問題Cで最難
問題Dで最易　問題Dで最難

No.	Q.	rate	No.	Q.	rate	No.	Q.	rate	No.	Q.	rate
1	A	733	10	A	878	19	A	1002	28	A	915
1	B	1283	10	B	1157	19	B	1461	28	B	1227
1	C	1949	10	C	1388	19	C	1643	28	C	1344
1	D	2038	10	D	2119	19	D	1761	28	D	1537
2	A	1012	11	A	997	20	A	965	29	A	826
2	B	1158	11	B	1293	20	B	1018	29	B	1086
2	C	1388	11	C	1652	20	C	2028	29	C	1463
2	D	1880	11	D	2148	20	D	2366	29	D	1969
3	A	988	12	A	1016	21	A	989	30	A	990
3	B	1381	12	B	1192	21	B	1304	30	B	1571
3	C	1499	12	C	1243	21	C	1970	30	C	1758
3	D	2244	12	D	1733	21	D	2017	30	D	1929
4	A	949	13	A	1033	22	A	1157	31	A	835
4	B	1247	13	B	1226	22	B	1319	31	B	1015
4	C	1430	13	C	1988	22	C	1947	31	C	1945
4	D	2163	13	D	2040	22	D	2075	31	D	2132
5	A	981	14	A	1116	23	A	887	32	A	985
5	B	1136	14	B	1547	23	B	1499	32	B	1506
5	C	1608	14	C	1777	23	C	2080	32	C	1802
5	D	1905	14	D	2086	23	D	2064	32	D	1956
6	A	993	15	A	906	24	A	1045	33	A	888
6	B	1583	15	B	1078	24	B	1251	33	B	1133
6	C	1773	15	C	1670	24	C	1685	33	C	1424
6	D	1957	15	D	1795	24	D	2222	33	D	2382
7	A	946	16	A	934	25	A	1032
7	B	1188	16	B	978	25	B	1187
7	C	1782	16	C	1736	25	C	2179
7	D	2086	16	D	1855	25	D	2486
8	A	887	17	A	1006	26	A	852
8	B	1519	17	B	1293	26	B	1229
8	C	2211	17	C	2013	26	C	1768
8	D	2310	17	D	2156	26	D	1842
9	A	976	18	A	1071	27	A	959
9	B	1190	18	B	1277	27	B	1633
9	C	2184	18	C	2070	27	C	2032
9	D	2287	18	D	2071	27	D	2154

計算結果(AtCoder Regular Contest)

　こちらの結果も載せてみました。ABCの平均レーティングが1516であるのに対し、ARCの平均レーティングが1873となっているのでどれぐらい難しくなっているかの参考になるかと思われます。

問題Aで最易　問題Aで最難
問題Bで最易　問題Bで最難
問題Cで最易　問題Cで最難
問題Dで最易　問題Dで最難

No.	Q.	rate	No.	Q.	rate	No.	Q.	rate	No.	Q.	rate
1	A	1236	13	A	1336	25	A	1009	37	A	1039
1	B	1630	13	B	1552	25	B	2015	37	B	1878
1	C	2133	13	C	2161	25	C	2200	37	C	2118
1	D	2555	13	D	2417	25	D	2591	37	D	2352
2	A	968	14	A	873	26	A	1018	38	A	1039
2	B	1585	14	B	1482	26	B	1764	38	B	2023
2	C	1695	14	C	1937	26	C	2202	38	C	2451
2	D	2600	14	D	2174	26	D	2265	38	D	2508
3	A	1117	15	A	992	27	A	1029	39	A	1302
3	B	1409	15	B	1317	27	B	2029	39	B	1924
3	C	2258	15	C	2302	27	C	2110	39	C	2181
3	D	2317	15	D	2566	27	D	2424	39	D	2440
4	A	1193	16	A	1034	28	A	1111	40	A	1072
4	B	1899	16	B	1299	28	B	2002	40	B	1895
4	C	2236	16	C	2313	28	C	2075	40	C	1900
4	D	2318	16	D	2473	28	D	2483	40	D	2649
5	A	1147	17	A	1114	29	A	1317	41	A	1088
5	B	1708	17	B	1645	29	B	2287	41	B	1768
5	C	1896	17	C	1968	29	C	2268	41	C	2103
5	D	2565	17	D	2287	29	D	2369	41	D	2472
6	A	1125	18	A	1030	30	A	1264	42	A	1480
6	B	1616	18	B	1867	30	B	1945	42	B	1794
6	C	1656	18	C	2206	30	C	2325	42	C	2087
6	D	2172	18	D	2563	30	D	2643	42	D	2279
7	A	1051	19	A	1144	31	A	971	43	A	1415
7	B	1290	19	B	1710	31	B	1938	43	B	2047
7	C	1877	19	C	2481	31	C	2182	43	C	2390
7	D	2451	19	D	2241	31	D	2561	43	D	2664
8	A	1045	20	A	973	32	A	1007	44	A	1295
8	B	1477	20	B	1630	32	B	1812	44	B	2129
8	C	2179	20	C	2314	32	C	2290	44	C	2303
8	D	2277	20	D	2590	32	D	2508	44	D	2321
9	A	963	21	A	1128	33	A	1060	45	A	1050
9	B	1659	21	B	1941	33	B	1596	45	B	1963
9	C	2257	21	C	2269	33	C	1992	45	C	2213
9	D	2554	21	D	2609	33	D	2437	45	D	2702
10	A	1064	22	A	1130	34	A	1125	46	A	1052
10	B	1792	22	B	1916	34	B	1638	46	B	1930
10	C	2328	22	C	2010	34	C	1942	46	C	2262
10	D	2453	22	D	2985	34	D	2431	46	D	2516
11	A	1147	23	A	1135	35	A	1114	47	A	925
11	B	1562	23	B	1695	35	B	1711	47	B	2373
11	C	1819	23	C	2143	35	C	2071	47	C	2360
11	D	2590	23	D	2383	35	D	2236	47	D	2671
12	A	997	24	A	1168	36	A	1211
12	B	1172	24	B	1893	36	B	1776
12	C	2151	24	C	2120	36	C	2302
12	D	2639	24	D	2384	36	D	2288

計算結果(ユーザーランキング)

　ABC・ARC全体で7719名でした。ちなみに私はrate1442の4428位なので雑魚です。

rank	ユーザ名	rate
1	kmjp	3415
2	chabo	2934
3	おねーちゃん	2881
4	coolwanglu	2880
5	/_/\ < queue!!	2821
6	persim	2739
7	kcm1700(韓)	2732
8	nekoyuki	2711
9	tkori	2700
10	ainu7	2672
11	Doju	2650
12	watashi	2649
13	エスカルきゅうり	2648
14	mamekin	2646
15	rook	2642
16	Otama	2629
17	duo	2625
18	Oleg	2616
19	ユーザ名	2616
20	rhd_may_20150300	2602

　分布のヒストグラムも載せておきます。前回に比べてより中央(1500)寄りになったのではないでしょうか。