Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[PyConKR2017] Best-first search를 이용한 다차원 큐브 탐색

[PyConKR2017] Best-first search를 이용한 다차원 큐브 탐색

Jangsea Park

August 12, 2017
Tweet

More Decks by Jangsea Park

Other Decks in Programming

Transcript

  1. Much more numbers (A,) = 5 (A, B) = 25

    (A, B, C) = 125 … (A, B, …, G) = 5 ** 7 6.7B
  2. Multidimensional cube s: 427 r: 87 d: 122 s: 283

    r: 23 d: 124 s: 291 r: 19 d: 872 s: 123 r: 108 d: 503 s: 287 r: 13 d: 687 s: 987 r: 432 d: 1113 s: 293 r: 18 d: 983 s: 293 r: 2929 d: 7023 s: 111 r: 72 d: 982 s: 293 r: 199 d: 777 s: 28 r: 1 d: 134 s: 19 r: 0 d: 29 s: 100 r: 29 d: 89 s: 192 r: 19 d: 192 s: 293 r: 18 d: 298 s: 19 r: 1 d: 29 Region Gender Age The most efficient
  3. Restrictions 137,979 10 queries per second (QPS) per IP address

    10 concurrent requests per view (profile) 137,979 / 10 / 60 = 230min 10,000 requests per view (profile) per day
  4. Better way Gender Age Region / Campaign Usertype Gender, Region

    Age, Campaign Region, Usertype Region, Usertype, Gender Region, Usertype, Campaign Usertype, Age Region, Usertype, Gender, Age s: 427 r: 87 d: 122 s: 283 r: 23 d: 124 s: 291 r: 19 d: 872 s: 123 r: 108 d: 503 s: 287 r: 13 d: 687 s: 987 r: 432 d: 1113 s: 293 r: 18 d: 983 s: 293 r: 2929 d: 7023 s: 111 r: 72 d: 982 s: 293 r: 199 d: 777 s: 28 r: 1 d: 134 s: 19 r: 0 d: 29 s: 100 r: 29 d: 89 s: 192 r: 19 d: 192 s: 293 r: 18 d: 298 s: 19 r: 1 d: 29 Region Gender Age
  5. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier:
  6. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C
  7. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: C D E B
  8. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: D E B C F G
  9. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: D E B C F G H I
  10. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: D E B C F G H I J K
  11. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: D E B C F G H I J K L
  12. Breadth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: D E B C F G H I J K L
  13. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier:
  14. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C
  15. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D
  16. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H
  17. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H
  18. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H
  19. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J
  20. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J
  21. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J
  22. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J F G
  23. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J F G
  24. Depth-first search A B D H I E J K

    C F L M G N O A Explored: Frontier: B C E D I H K J F G
  25. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6
  26. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 5+10=15 4+12=16
  27. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 4+12=16 12+7=19 11+5=16
  28. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 8+6=14 12+7=19 11+5=16
  29. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 11+4=15 12+7=19 10+5=15
  30. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 11+4=15 12+7=19 12+4=16
  31. Best-first search A B C D E F G H

    I J K L M N O P 3 4 5 3 2 4 7 6 4 3 2 1 2 2 3 4 1 2 4 A: 15 B: 15 C: 10 D: 12 E: 12 F: 7 G: 11 H: 5 I: 5 J: 6 K: 4 L: 4 M: 0 N: 1 O: 4 P: 6 3+15=18 13+4=17 12+7=19 12+4=16 15+0=15
  32. More about Best-first search heapq — Heap queue algorithm https://docs.python.org/3.6/library/heapq.html#theory

    [AIMA] 3.5 INFORMED (HEURISTIC) SEARCH STRATEGIES [AIMA] 3.6 HEURISTIC FUNCTIONS
  33. Best-first search for GA API Gender Age Region / Camp

    Type S: 1000 R: 10000 Female S: 600 R: 8000 Male S: 400 R: 2000
  34. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type
  35. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 1.0 1.0 1.0 1.0 0.8 0.8 0.8 0.8 0.8
  36. Best-first search for GA API Gender Age Region / Camp

    Type 0.6 1.0 1.0 1.0 0.8 10s S: 100 R: 200 20s S: 500 R: 2000 30s S: 200 R: 6000 40s S: 100 R: 1000 50+ S: 100 R: 800
  37. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 1.0 1.0 1.0 0.48 0.8 0.8 0.8 0.8 Age Region Age Camp Age Type 0.6 0.6 0.6
  38. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 0.4 1.0 1.0 0.48 0.8 0.32 0.8 0.8 Age Region Age Camp Age Type 0.24 0.6 0.6
  39. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 0.4 1.0 1.0 0.48 0.8 0.32 0.8 0.8 Age Region Age Camp Age Type 0.24 0.6 0.6 Region Camp Region Type 0.4 0.4
  40. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 0.4 0.2 1.0 0.48 0.8 0.32 0.16 0.8 Age Region Age Camp Age Type 0.24 0.12 0.6 Region Camp Region Type 0.08 0.4 Camp Type 0.2
  41. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 0.4 0.2 0.5 0.48 0.8 0.32 0.16 0.4 Age Region Age Camp Age Type 0.24 0.12 0.3 Region Camp Region Type 0.08 0.2 Camp Type 0.1
  42. Best-first search for GA API Gender Age Region / Camp

    Type Gender Age Gender Region Gender Camp Gender Type 0.6 0.4 0.2 0.5 0.48 0.8 0.32 0.16 0.4 Age Region Age Camp Age Type 0.24 0.12 0.3 Region Camp Region Type 0.08 0.2 Camp Type 0.1
  43. Q&A