Tomorrow graphlib, Let us use everybody

PyCon JP 2025 Day 1 Talk

Transcript

1. ໌೔͔Β graphlibɺΈΜͳͰ࢖͓͏ Hayao Suzuki PyCon JP 2025 at International Conference Center Hiroshima September 26, 2025
2. Share it GitHub › https://github.com/HayaoSuzuki/pyconjp2025 Hashtag › #pyconjp #PyConJP2025 ɹ#pyconjp_3 2 / 34
3. Who am I ? ͓લ୭Α Name Hayao Suzukiʢླ໦ɹॣʣ ///////// Twitter X @CardinalXaro Work ιϑτ΢ΣΞΤϯδχΞ at ౦ژΨεגࣜձࣾ ౦ژΨεגࣜձࣾʹ͍ͭͯ › Ұ౎࿡ݝʹ౎ࢢΨεɾిؾͳͲͷΤωϧΪʔΛڙڅ͢Δձࣾ › ౦ژΨε͸ PyCon JP 2025 ͷ Gold εϙϯαʔͰ͢ › ιϑτ΢ΣΞΤϯδχΞΛઈࢍืूத https://www.tokyo-gas-recruit.com/career/ 3 / 34
4. Who am I ? ຋༁ › Effective Python ୈ 3 ൛ (O’Reilly Japan) New! › ϋΠύʔϞμϯ Python(O’Reilly Japan) › Python Distilled(O’Reilly Japan) ؂༁ɾ؂म › ϩόετ Python(O’Reilly Japan) › ೖ໳ Python 3 ୈ 2 ൛ (O’Reilly Japan) › Python ΫΠοΫϦϑΝϨϯε ୈ 4 ൛ (O’Reilly Japan) 4 / 34
5. Who am I ? աڈͷൃදʢൈਮʣ › Let’s implement useless Python objects(PyCon APAC 2023) › ૊ΈࠐΈؔ਺ pow ͷ஌ΒΕ͟ΔਐԽ (PyCon JP 2021) › ΠϯϝϞϦʔετϦʔϜ׆༻ज़ (PyCon JP 2020) › ܅͸ cmath Λ஌͍ͬͯΔ͔ (PyCon mini Shizuoka 2020) › Python ͱָ͠Ήॳ౳੔਺࿦ (PyCon mini Hiroshima 2019) › SymPy ʹΑΔ਺ࣜॲཧ (PyCon JP 2018) Ұཡ͸ https://xaro.hatenablog.jp/ Λࢀর͍ͯͩ͘͠͞ 5 / 34
6. Today’s Theme ໌೔͔Β graphlibɺΈΜͳͰ࢖͓͏ 6 / 34
7. Executive Summary ๩͍͠ਓ޲͚ͷཁ໿ › τϙϩδΧϧιʔτͱ͸ɺ༗޲ඇ८ճάϥϑͷ௖఺ू߹ͷઢܕॱংͰ͋Δ › graphlib ͸ɺτϙϩδΧϧιʔτ͕࣮૷͞Εͨඪ४ϥΠϒϥϦͰ͋Δ › graphlib ͸ɺ؆қతͳλεΫϥϯφʔͱͯ͠࢖͑Δ 7 / 34
8. άϥϑͬͯɺԿʁ ఆٛ (ແ޲άϥϑ) ༗ݶू߹ V ͓Αͼ V ˆ V ͷඇॱংର͔ΒͳΔू߹ͷ෦෼ू߹ E ͷ૊ G = (V; E) Λແ޲άϥϑͱݺͿɻ ఆٛ (༗޲άϥϑ) ༗ݶू߹ V ͓Αͼ V ˆ V ͷॱংର͔ΒͳΔू߹ͷ෦෼ू߹ E ͷ૊ G = (V; E) Λ༗޲άϥϑͱݺͿɻ › V Λ௖఺ू߹ɺE Λลू߹ͱݺͿɻ › V ͷཁૉΛ G ͷ௖఺ɺE ͷཁૉΛ G ͷลͱݺͿɻ 8 / 34
9. ແ޲άϥϑͷྫ 9 / 34
10. ༗޲άϥϑͷྫ 10 / 34
11. ͭ·ΓʜͲ͏͍͏͜ͱͩͬͯ͹Αʁ ʜͰɺͦͷάϥϑ͸౰ࣾͰಇ͘͏͑Ͱ ԿͷϝϦοτ͕͋Δͱ͓ߟ͑Ͱ͔͢ʁ 11 / 34
12. དྷ͍Αϕωοτʂ ఆٛͳΜ͔ࣺ͔͔ͯͯͬͯདྷ͍ʂ ๩͍͠ਓ޲͚ͷάϥϑ › άϥϑͱ͸ɺ ʮ΋ͷʯͱͦͷʮؔ܎ʯΛ਺ֶతʹϞσϧԽͨ͠΋ͷͰ͋Δ › ʮ΋ͷʯ͸ਓؒɺӺɺλεΫɺαʔόͳͲ › ʮؔ܎ʯ͸ਓؒؔ܎ɺઢ࿏ɺґଘؔ܎ɺωοτϫʔΫͳͲ 12 / 34
13. τϙϩδΧϧιʔτͬͯɺԿʁ ఆٛ (ೋ߲ؔ܎) ू߹ A ͷ௚ੵ A ˆ A ͷ෦෼ू߹ R Λೋ߲ؔ܎ͱݺͿɻ ·ͨɺ(a; b) 2 R Λ aRb ͱද͢ɻ ఆٛ (൒ॱংؔ܎) ҎԼͷੑ࣭Λຬͨؔ͢܎ R Λ൒ॱংؔ܎ͱݺͿɻ ൓ࣹ཯ 8a 2 A ʹରͯ͠ɺaRa Ͱ͋Δ ൓ରশ཯ a; b 2 A ʹରͯ͠ɺaRb ͔ͭ bRa ͳΒ͹ a = b Ͱ͋Δ ਪҠ཯ a; b; c 2 A ʹରͯ͠ɺaRb ͔ͭ bRc ͳΒ͹ aRc Ͱ͋Δ ൒ॱংؔ܎͸ɺେখؔ܎΍ൺֱͷ֓೦Λந৅ͨ͠΋ͷɻ 13 / 34
14. τϙϩδΧϧιʔτͬͯɺԿʁ ఆٛ (ઢܕॱং) ू߹ A ͷ൒ॱংؔ܎ R ʹ͓͍ͯɺ8a; b 2 A ʹରͯ͠ aRb ·ͨ͸ bRa ͕੒Γཱ ͭͳΒ͹ɺR ͸ઢܕॱংͰ͋ΔͱݺͿɻ ఆٛ (τϙϩδΧϧιʔτ) ༗޲άϥϑ G = (V; E) ͷτϙϩδΧϧιʔτͱ͸ɺV ͷઢܕॱং (V; ») Ͱɺ (u; v) 2 E ͳΒ͹ u » v Λຬͨ͢΋ͷͰ͋Δɻ 14 / 34
15. τϙϩδΧϧιʔτͬͯɺԿʁ ఆٛ (าಓ) άϥϑ G = (V; E) ͷ௖఺ u1 ͔Β uk ΁ͷ௕͞ k ͷาಓ W ͱ͸ɺ௖఺ͷྻ (u1 ; u2 ; : : : ; uk ) Ͱɺ(ui ; uj ) 2 E(1 » i < j » k) Λຬͨ͢΋ͷͰ͋Δɻಛ ʹɺu1 = uk ͷ৔߹ɺW ͸ด͍ͯ͡ΔͱݺͿɻ ఆٛ (ಓ) άϥϑ G = (V; E) ͷาಓ W ʹ͓͍ͯɺ௖఺͓Αͼล͕͢΂ͯҟͳΔ΋ͷ͸ಓͱݺ Ϳɻಛʹɺดͨ͡ಓΛด࿏ͱݴ͏ɻ ఆٛ (༗޲ඇ८ճάϥϑ) ༗޲άϥϑ G = (V; E) ʹ͓͍ͯɺด࿏Λؚ·ͳ͍΋ͷΛ༗޲ඇ८ճάϥϑͱݺͿɻ 15 / 34
16. τϙϩδΧϧιʔτͬͯɺԿʁ ໋୊ (τϙϩδΧϧιʔτՄೳ) ༗޲άϥϑ G ͕τϙϩδΧϧιʔτՄೳͰ͋ΔͨΊͷඞཁे෼৚݅͸ɺ ༗޲άϥϑ G ͕༗޲ඇ८ճάϥϑͰ͋Δ͜ͱͰ͋Δɻ 16 / 34
17. ָ͍͠ূ໌ίʔφʔ τϙϩδΧϧιʔτՄೳ ) ༗޲ඇ८ճάϥϑ. τϙϩδΧϧιʔτՄೳ͕ͩάϥϑ G ʹด࿏͕ଘࡏ͢ΔͱԾఆ͢Δɻ ͦͷด࿏Λ vi ; vj ; vk (i < j < k) ͱͯ͠ɺ͔ͭ vi » vj » vk ͱ͢Δɻ vi ; vj ; vk (i < j < k) ͸ด࿏ͳͷͰɺvk ͔Β vi ΁ͷล͕ଘࡏ͢Δɻ ͭ·Γɺvk » vi ͱͳΔ͕ɺͦΕ͸Ծఆ vi » vj » vk ʹໃ६͢Δɻ 17 / 34
18. ·ͩ·ͩଓָ͍ͧ͘͠ূ໌ίʔφʔ ิ୊ ༗޲ඇ८ճάϥϑʹ͸ೖ࣍਺ 0 ͷ௖఺͕ඞͣଘࡏ͢Δɻ ূ໌. ༗޲ඇ८ճάϥϑͷ࠷௕ͷಓ v1 ; : : : ; vk Λ 1 ͭબͿɻv1 ʹೖΔล͕ଘࡏ͢ΔͳΒ ͹ɺu; v1 ; : : : ; vk ͔ͭ (u; v1 ) 2 E ͷΑ͏ͳ௖఺ u ͕ଘࡏ͢Δ͜ͱʹͳΔ͕ɺ v1 ; : : : ; vk ͕࠷௕ͷಓͰ͋Δͱ͍͏Ծఆʹ൓͢ΔɻΑͬͯɺv1 ͷೖ࣍਺͸ 0 ͱͳ Γɺ༗޲ඇ८ճάϥϑʹ͸ೖ࣍਺ 0 ͷ௖఺͕ඞͣଘࡏ͢Δɻ 18 / 34
19. ͑ʁ ·ͩ͋ΔΜͰ͔͢ʁ ָ͍͠ূ໌ίʔφʔ ิ୊ ༗޲ඇ८ճάϥϑ G ͷ෦෼άϥϑ H ΋·ͨ༗޲ඇ८ճάϥϑͰ͋Δɻ ূ໌. ෦෼άϥϑ H ͕༗޲ඇ८ճάϥϑͰ͸ͳ͍ͱԾఆ͢ΔɻH ͷด࿏Λ C ͱͨ͠৔߹ɺ H ͸ G ͷ෦෼άϥϑͳͷͰɺด࿏ C ͸ G ʹ΋ଘࡏ͢Δ͜ͱʹͳΔɻ͔͠͠ɺͦΕ͸ G ͕༗޲ඇ८ճάϥϑͰ͋Δͱ͍͏Ծఆʹ൓͢Δɻ 19 / 34
20. ָ͍͠Αͳʂ ূ໌ίʔφʔ ༗޲ඇ८ճάϥϑ ) τϙϩδΧϧιʔτՄೳ. ༗޲ඇ८ճάϥϑ G ʹ͸ඞͣೖ࣍਺ 0 ͷ௖఺͕ඞͣଘࡏ͢ΔͷͰɺͦͷ௖఺͓Αͼͦ ͔͜Βग़ΔลΛऔΓআ͘ɻऔΓআ͍ͨάϥϑ΋·ͨ༗޲ඇ८ճάϥϑͳͷͰɺ௖఺͕ͳ ͘ͳΔ·ͰͦΕΛ܁Γฦ͢ɻऔΓআ͍ͨॱ൪ʹ௖఺Λฒ΂ͨ΋ͷ͕τϙϩδΧϧιʔ τͰ͋Δɻ ॏཁɿূ໌͕ΞϧΰϦζϜʹͳ͍ͬͯΔ͜ͱʹ஫ҙɻ 20 / 34
21. ࠓ೔͸ PyCon JP 2025 ͷ 1 ೔໨Ͱ͢ ཭ࢄ਺ֶͷߨٛͰ͸ͳ͘ɺ PyCon JP Ͱ͢Α 21 / 34
22. དྷ͍Αϕωοτʂ ূ໌ͳΜ͔ࣺͯͯʢ͈́ ๩͍͠ਓ޲͚ͷτϙϩδΧϧιʔτ › ൒ॱংؔ܎͸ɺେখؔ܎΍แؚؔ܎Λந৅Խͨ͠΋ͷ › ઢܕॱং͸ɺͲΕͰ΋ൺֱͰ͖Δ΍ͭɺ͙Β͍ͷཧղͰ › τϙϩδΧϧιʔτ͸ɺ༗޲άϥϑͷ௖఺Λ͍͍ײ͡ʹॱং෇͚ͨ͠΋ͷ › τϙϩδΧϧιʔτͱ༗޲ඇ८ճάϥϑ͸දཪҰମ › τϙϩδΧϧιʔτʹؔ͢Δূ໌͕ΞϧΰϦζϜʹͳ͍ͬͯΔ 22 / 34
23. τϙϩδΧϧιʔτͷ࢖͍ಓͱ͸ Q: ௖఺ΛλεΫɺลΛλεΫͷґଘؔ܎ͱ͢Δɻ Ͳͷॱ൪ͰλεΫΛ࣮ߦ͢Ε͹Α͍͔ʁ 23 / 34
24. τϙϩδΧϧιʔτͷ࢖͍ಓͱ͸ Ans: άϥϑΛτϙϩδΧϧιʔτͯ͠ɺͦͷॱ൪ʹ΍Ε͹Α͍ɻ A ˠ B ˠ D ˠ E ˠ C ˠ G ˠ F ˠ I ˠ M ˠ H ˠ J ˠ K ˠ L ˠ N 24 / 34
25. Ͳ͏΍ͬͨͷʁ ͢Ͱʹ graphlibɺ๻͸࢖ͬͨΑ 25 / 34
26. ਅଧొ৔ graphlibɿάϥϑߏ଄Λૢ࡞͢Δػೳ › ݱࡏ͸ TopologicalSorter ͷΈɺ୯७ͳඪ४ϥΠϒϥϦ › Python 3.9 Ͱ௥Ճ › https://github.com/python/cpython/issues/61207 Ͱٞ࿦ ͞Ε͍ͯͨɻ 26 / 34
27. graphlib ͷ࢖͍ํ τϙϩδΧϧιʔτͷ࣮ߦ from graphlib import TopologicalSorter graph = { "D": {"B", "C"}, "C": {"A"}, "B": {"A"}, } order = TopologicalSorter(graph).static_order() print(f"Topological order: {" ˠ ".join(order)}") # A ˠ C ˠ B ˠ D D B, D C ͷΑ͏ͳΠϝʔδͰఆٛ͢Δɻ 27 / 34
28. graphlib ͷ࢖͍ํ ༗޲ඇ८ճάϥϑͰ͸ͳ͍έʔε from graphlib import TopologicalSorter graph = { "A": {"C"}, "B": {"A"}, "C": {"B"} } order = TopologicalSorter(graph).static_order() print(f"Topological order: {" ˠ ".join(order)}") # graphlib.CycleError ͕ൃੜ͢Δ 28 / 34
29. ΑΓߴ౓ͳ࢖͍ํ graphlibɿґଘؔ܎ͷ͋ΔλεΫΛ࣮ߦ͢ΔλεΫϥϯφʔ › ฒྻ࣮ߦ͠΍͍͢ΞϧΰϦζϜ › υΩϡϝϯτʹͦΕͱͳ͘৮ΕΒΕ͍ͯΔ͕ɺෆे෼...ɻ › ੜ੒ AI ͷྗΛआΓͯͦΕͱͳ͘࡞ͬͯΈΑ͏ʂ 29 / 34
30. λεΫͷఆٛ dataclass ʹΑΔλεΫఆٛ @dataclass(frozen=True, slots=True) class Task: name: str action: Action deps: set[str] = field(default_factory=set) ௖఺͸ϋογϡՄೳͰ͋Δඞཁ͕͋ΔͷͰɺfrozen=True Λ࢖͏ɻ 30 / 34
31. λεΫϥϯφʔ άϥϑͷఆٛ def run(tasks, max_workers=None): by_name = {t.name: t for t in tasks} ts = TopologicalSorter({t.name: set(t.deps) for t in ts.prepare() results: dict[str, object] = {} ... 31 / 34
32. λεΫϥϯφʔ ฒߦॲཧɿεϨουʹ౤ೖ def run(tasks, max_workers=None): ... with ThreadPoolExecutor(max_workers) as pool: while ts.is_active(): ready = ts.get_ready() futs = {} for name in ready: print(f"run {name}") futs[pool.submit(by_name[name].action)] ... 32 / 34
33. λεΫϥϯφʔ ฒߦॲཧɿ׬ྃ଴ͪ def run(tasks, max_workers=None): ... with ThreadPoolExecutor(max_workers) as pool: while ts.is_active(): ... for fut in as_completed(futs): name = futs[fut] results[name] = fut.result() print(f"done {name}") ts.done(name) return results 33 / 34
34. ·ͱΊ ·ͱΊ › τϙϩδΧϧιʔτͱ͸ɺ༗޲ඇ८ճάϥϑͷ௖఺ू߹ͷઢܕॱংͰ͋Δɻ › ༗޲άϥϑ G ͕τϙϩδΧϧιʔτՄೳͰ͋ΔͨΊͷඞཁे෼৚݅͸ɺ ༗޲άϥϑ G ͕༗޲ඇ८ճάϥϑͰ͋Δ͜ͱͰ͋Δɻ › graphlib ͸ɺτϙϩδΧϧιʔτ͕࣮૷͞Εͨඪ४ϥΠϒϥϦͰ͋Δɻ › graphlib ͸ɺ؆қతͳλεΫϥϯφʔΛ࣮૷͢Δࡍʹɺ࣮ߦॱংΛܾఆ͢Δ ࢓૊Έͱͯ͠࢖͑Δɻ 34 / 34