template.dvi

Size: px

Start display at page:

Download "template.dvi"

ゆたかたておか
5 years ago
Views:

1 30 2 7

2 29 Codeforces 1,644,636 1

3 2

4 RQ1-a: RQ1-b: RQ2-a: RQ2-b: RQ3:

5 41 4

6 1 [5,6,14] Topcoder 1 Codeforces 2 [11] [12,13] Codeforces 2016/5/ /11/15 6 Codeforces 1,644,636 9 C++ Codeforces API

7 Codeforces

8 2 2.1 AIZU ONLINE JUDGE 4 Topcoder 2.2 [3,10] ACM ICPC

9 2.2.1 Codeforces Codeforces Codeforces Codeforces : 2 3 : 7000 : ( ) 6 Codeforces Codeforces Codeforces [10] [3] 8

10 2 A B r A,r B A B 1 P(r A,r B ) = 1+10 r B r A 400 A B Codeforces Codeforces Algorithm 1 (1) seed i r i seed i rank i m i getseed(r i ) = m i R i R i r i i (2) (1) (2) r i 2.3 [5,6,14] [1,7] Codeforces Codeforces 9

11 Algorithm 1: Codeforces Data: U : Data: r i : i Data: rank i : i Result: r i : i Function getseed(r) return i U P(r i,r)+1; Function getratingtorank(r) left 1; right 8000; while right left > 1 do mid left+right 2 ; if getseed(mid) < r then else return left; right mid; left mid; sum 0; for i U do seed i getseed(r i ); m i seed i rank i ; R i getratingtorank(m i ); d i R i r i 2 ; sum sum+d i ; for i U do d i d i ( sum U +1); // (1) // 0 topu U min( U,4 U ) ; sum i topu d i; inc min(max( sum topu, 10),0); for i U do d i d i +inc; r i r i +d i ; // (2) 10 //

12 HTML ソースコードページ REST API JSON 提出履歴データ Python Scraping Tool Python Datamining Tool データセット Text ソースコード MySQL 提出履歴データベース 1: 3 Codeforces Codeforces API

13 2: Codeforces 1: AU API Codeforces Topcoder CodeChef Codeforces 2 Codeforces 767 ID 1 Codeforces API 9 Codeforces API JSON Python MySQL Codeforces API Codeforces API 10 1 API Codeforces HTML URL ID ID

14 2: Participant user name PK Codeforces String Submission rating max rating user name files Integer 2016/11/15 Integer PK FK Participant Integer user name Integer user name File file name PK String submission id lang Codeforces ID Integer String user name FK String verdict String timestamp Date/Time competition id FK Competition Integer problem id url during competition competition id Participant- prob- String lem id Codeforces String URL Competition competition id PK ID name start time duration time participants Boolean Integer String Date/Time Integer Integer 13

15 Problem problem id PK ID String competition id FK Integer prob index points Acceptance problem id Problem- Submission- Statistics submission in sample solved in sample submission solved competition id Index of the problem in the competition String Integer PK FK problem id String Integer Integer Integer Integer acceptance rate solved/submissions Double lastmodified problem id PK problem id filesize max filesize min filesize mean filesize median filesize variance filesize max competition filesize min competition Date/Time String Integer Integer Integer Integer Integer filesize max Integer filesize min Integer 14

16 Distance filesize mean competition filesize median competition filesize variance competition filesize mean Integer filesize median Integer filesize variance Integer file name PK String problem id next file submission index levenshtein distance add node delete node update node move node node sum Submission- prob- String lem id file name String Integer file name next file Integer file name next file Integer file name next file Integer file name next file Integer file name next file Integer Integer /5/ /11/15 1,644,636 15

3: ER 3: DB 2016/5/19 2016/11/15 1,644,636 14,520 739 3,218 357MB

17 3: ER 3: DB 2016/5/ /11/15 1,644,636 14, , MB /5/ /11/15 1 Codeforces Codeforces Codeforces 16

18 3.2.2 Codeforces API JSON MySQL 2 3 Participant 2016/5/ /11/15 1 Codeforces 2 3 Codeforces ID ID 2016/11/15 ParticipantSubmission File 2016/5/ /11/15 Codeforces 1,644,636 ID ID URL url Competition Codeforces Problemset Problem 3,218 ID ID ID 601B ID 601 B

19 Acceptance Problem sample File 2016/11/15 acceptance rate ProblemSubmissionStatistics Problem Byte competition SubmissionDistance file name next file levenshtein distance [8] node GumtreeDiff [4] Codeforces /11/15 r = / a = 5r + 1 /

20 4: % C++ Java 4% 1.2KB GNU C++ GNU C++11 GNU C % 19

21 5: 6: 20

22 7: 21

23 4 4.1 [5,6] 3 Research Question(RQ) RQ1 RQ2 RQ3 RQ RQ1 RQ2 22

24 4: RQ

25 4.3 RQ1 2 RQ2 RQ RQ1-a: RQ C++ 5 U p := p k u,p,t := u p t k p,t := 1 U p x U p k x,p,t ( p t ) σ p,t := 1 U p x U p (k x,p,t k p,t ) 2 ( p t ) k u,p,t := ku,p,t kp,t σ p,t (k u,p,t 0 1 ) p k u,p,t

26 1. k u,p,t 2. k u,p,t k u,p,t 3. k u,p,t t K t,high K t,low 4. K t,low K t,high Welch t 5. K t,low K t,high Cohen s d [2] Cohen s d 2 Cohen s d [2] Cohen s d x 1 x 2 2 Cohen s d d = x 1 x 2 s s := (n1 1)s 2 1 +(n 2 1)s 2 2 n 1 +n 2 2 n i := x i s 2 i := x i 6 7 K t,low K t,high 5% t 6 K t,high < K t,low Cohen s d 7 K t,high > K t,low Cohen s d 6 typedef template class 25

27 5: 12 alignas decltype namespace static cast alignof default new struct and delete noexcept switch and eq do not template asm double not eq this auto dynamic cast nullptr thread local bitand else operator throw bitor enum override true bool explicit or try break export or eq typedef case extern private typeid catch false protected typename char final public union char16 t float register unsigned char32 t for reinterpret cast using class friend requires virtual compl goto return void concept if short volatile const inline signed wchar t constexpr int sizeof while const cast long static xor continue mutable static assert xor eq 7 else break if RQ1-b: RQ1 Web 26

28 6: t K t,low K t,high p Cohen s d typedef e template e return e typename e while e operator e class e using e continue e struct e do e public e namespace e enum e asm e private e typeid e friend e decltype e try e catch e SourceMonitor [9]

29 7: t K t,low K t,high p Cohen s d else 8.760e e e e break 5.797e e e e if 2.283e e e e for 3.069e e e e goto 9.375e e e e case e e e e switch e e e e extern e e e e McCabe M = E N +2P M := E := (Control Flow Graph: CFG) N := CFG P := CFG ( ) SourceMonitor U p := p m u,p,c := u p c m u,p,c := m u,p,c

30 M c,low := m u,p,c M c,high := m u,p,c u u c M c,low M c,high 2 t Cohen s d c M c,low M c,high ( ) t 5% 9 Cohen s d 10 Cohen s d C RQ RQ RQ2-a: 3.3 RQ U p := p s u,p := u p 29

31 8: avg complexity max complexity avg depth max depth methods per class n classes n func n lines n statements percent branch statements (if, else, for, percent comments while, goto, break, continue, switch, case, default, return ) 9: c M c,low M c,high p Cohen s d n statements e n func e n lines e methods per class e n classes e s u,p := s u,p 0 1 S a,low := s u,p u p a S a,high := s u,p u p a 30

32 8: SourceMonitor 2 (M c,low < M c,high ) 10: c M c,low M c,high p Cohen s d avg depth e percent branch e statements avg complexity e max complexity e max depth e percent comments e (3.3 ) a S a,low S a,high 2 t Cohen s d 11 t 31

33 9: SourceMonitor 2 (M c,low > M c,high ) Cohen s d 10 S 0.4,low S 0.4,high RQ2-b: LD [8] l u,p,i := u p i i+1 LD l u,p,i := l u,p,i

34 10: 0.4 l max,u,p := max j<su,p j=0 l u,p,j ( u p l u,p,i ) l med,u,p := medianj<su,p j=0 l u,p,j ( u p l u,p,i ) L max,a,low := l max,u,p u p a L med,a,low := l med,u,p u p a L max,a,high := l max,u,p u p a L med,a,high := l med,u,p u p a L func,a,low L func,a,high (func {max,med}) t Cohen s d LD / LD LD LD / p 1.0 5% 33

35 11: a p Cohen s d e e e e e LD RQ3: GumTreeDiff [4] GumTreeDiff

36 11: L max,0.4,low L max,0.4,high (a) L med,0.4,low L med,0.4,high (b) expr name block RQ RQ2 35

37 12: L max,0.4,low L max,0.4,high a p Cohen s d e e e e e RQ3 1. (expr) name block (1) (2) (3) 36

38 13: L med,0.4,low L med,0.4,high a p Cohen s d e e e e e Codeforces GumTreeDiff 37

39 12:

40 5 Codeforces / 39

41 40

42 [1] E. T. Chen. Program complexity and programmer productivity. IEEE Trans. Softw. Eng., Vol. SE-4, No. 3, pp , [2] Jacob Cohen. Statistical Power Analysis for the Behavioral Sciences, 2nd edition. Lawrence Erlbaum Associates, [3] Arpad E Elo. The rating of chessplayers, past and present. Arco Pub., [4] Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, and Martin Monperrus. Fine-grained and accurate source code differencing. In Proc. of ASE 2014, pp , [5] Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In Proc. of ICSE 2012, pp. 3 13, [6] Quinn Hanam, Fernando S. de M. Brito, and Ali Mesbah. Discovering bug patterns in javascript. ACM SIGCSE Bulletin, pp , [7] T. C. Jones. Measuring programming quality and productivity. IBM Systems Journal, Vol. 17, No. 1, pp , [8] Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10, pp , [9] Thomas J McCabe. A complexity measure. IEEE Trans. Softw. Eng., Vol. 2, No. 4, pp , [10] Mikhail Mirzayanov. Codeforces rating system. entry/102, [11] Mikhail Mirzayanov. Codeforces: Statistics entry/22618, [12] Jordi Petit, Omer Giménez, and Salvador Roura. Jutge.org: An educational programming judge. In Proc. of SIGCSE, pp ,

43 [13] Miguel A Revilla, Shahriar Manzoor, and Rujia Liu. Competitive learning in informatics: The uva online judge experience. Olympiads in Informatics, Vol. 2, pp , [14] Hao Zhong and Zhendong Su. An empirical study on real bug fixes. In Proc. of ICSE 2015, pp ,

解きながら学ぶC++入門編

解きながら学ぶC++入門編 !... 38!=... 35 "... 112 " "... 311 " "... 4, 264 #... 371 #define... 126, 371 #endif... 369 #if... 369 #ifndef... 369 #include... 3, 311 #undef... 371 %... 17, 18 %=... 85 &... 222 &... 203 &&... 40 &=...