【Go言語】map

mapについて解説しています

Transcript

1. Tomoki Ota ʲGoݴޠʳmap
2. mapͱ͸? 2
3. mapͱ͸ʁ 3
4. mapͱ͸ʁ 4
5. mapͱ͸ʁ GoͰ͸ɺmap͸ϋογϡςʔϒϧͷσʔλߏ଄ʹجͮ͘ 5
6. mapͱ͸ʁ ಺෦తʹϋογϡςʔϒϧ͸ɺόέοτ΁ͷϙΠϯλͷ഑ྻ ֤όέοτ͸Ωʔͱ஋ͷϖΞΛ8ͭ࣋ͭ 6
7. mapͷϋογϡςʔϒϧ map[string]intͷόέοτ0ʹ஫໨ͨ͠ϋογϡςʔϒϧදݱͷྫ 7 hash(“two") = 0
8. ཁૉͷૠೖ 8 ผͷཁૉͷ map[string]intͷόέοτ0ʹ஫໨ͨ͠ϋογϡςʔϒϧදݱͷྫ
9. ཁૉͷૠೖ(όέοτ͕͍ͬͺ͍ͷͱ͖) 9
10. ಡΈग़͠ɺߋ৽ɺ࡟আͷܭࢉྔ 10 Λόέοτͷ૯਺ͱ͢Δͱɺ (σϑΥϧτ͸1ɺΦʔόϑϩʔ࣌͸ෳ਺ͷόέοτ) p ࠷ѱ࣌ؒܭࢉྔ͸ ͱͳΔ O(p)
11. ॳظԽ
12. ॳظԽ
13. 100ສݸͷཁૉͷ௥Ճ Ϛοϓ͕ࣗಈͰ֦େͯ͠ɺόέοτΛอ࣋͢Δ഑ྻ͕2ഒͱͳΔ
14. Ϛοϓ͕֦େ͢Δ৚݅ ഑ྻͷཁૉ͝ͱʹόέοτ͕อ࣋͢Δཁૉ਺ͷฏۉ਺(Load Factor)͕ ͋Δఆ਺஋(ݱঢ়͸6.5ɻ໿80%)ΑΓ΋େ͖͍ͱ͖ Φʔόʔϑϩʔ͍ͯ͠Δ഑ྻ಺ͷཁૉ͕ͱͯ΋େ͖͍ͱ͖
15. Ωʔͷૠೖͷܭࢉྔ 15 Ϛοϓ͕֦େ͢Δͱ͖ɺશͯͷΩʔ͕શͯͷόέοτ΁࠶഑ஔ͢Δɻ ΛϚοϓͷཁૉͷ૯਺ͱ͢Δͱ n ࠷ѱ࣌ؒܭࢉྔ͸ ͱͳΔ O(n)
16. ॳظԽ 16 makeͰॳظԽ͢Δ
17. ॳظԽ 17
18. ॳظԽ 18 αΠζnΛࢦఆ͢ΔͱɺGoϥϯλΠϜʹগͳ͘ͱ΋nݸͷཁૉΛ อ࣋Ͱ͖ΔϚοϓΛׂΓ౰ͯΔΑ͏ʹཁٻ͢Δɻ ❌ ࠷େnݸͷཁૉΛ࣋ͭϚοϓΛ࡞Δ
19. mapͱϝϞϦʔϦʔΫ
20. mapͱϝϞϦʔϦʔΫ
21. mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓ౰ͯΔ 2. 100ສݸͷཁૉΛ௥Ճ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
22. mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓ౰ͯΔ 2. 100ສݸͷཁૉΛ௥Ճ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
23. mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓ౰ͯΔ 2. 100ສݸͷཁૉΛ௥Ճ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
24. GoͷϚοϓ͸runtime.hmapߏ଄ମ΁ͷϙΠϯλɻ ͜ͷߏ଄ମʹ͸ɺϚοϓ಺ͷόέοτ਺Λࣔ͢BϑΟʔϧυͳͲෳ਺ͷϑΟʔϧυ͕͋Δɻ mapͱϝϞϦʔϦʔΫ
25. mapͱϝϞϦʔϦʔΫ
26. 100ສݸͷཁૉΛ௥Ճ͢Δ → Bͷ஋͸18ɺ όέοτͱͳΔ 100ສݸͷཁૉΛऔΓআ͘ → B͸18ͷ··ɻΏ͑ʹɺϚοϓ͸·ͩಉ͡਺ͷόέοτΛอ࣋͢Δ 218 = 262144 mapͱϝϞϦʔϦʔΫ
27. mapͱϝϞϦʔϦʔΫ 1࣌ؒ෼ͷσʔλΛอଘ͢Δͱ͢Δɻେن໛ͳϓϩϞʔγϣϯΛߦ ͏৔߹ɺ1࣌ؒޙʹ͸ɺ਺ඦສਓͷ͓٬༷͕γεςϜʹ઀ଓ͢Δ͔ ΋͠Εͳ͍ɻ͔͠͠ɺϓϩϞʔγϣϯͷ਺೔ޙ΋ɺϐʔΫ࣌ͱಉ ͡਺ͷόέοτ͕Ϛοϓʹอ࣋͞Εͨ··ʹͳΔɻ͜ͷΑ͏ͳγ φϦΦͷ৔߹ɺϝϞϦͷফඅྔ͕େ෯ʹݮগͤͣɺϝϞϦͷফඅ͕ ଟ͘ͳΔɻ
28. ݱࡏͷϚοϓͷίϐʔΛఆظతʹ࠶࡞੒͢Δ mapܕ͕഑ྻͷϙΠϯλΛอ࣋͢ΔΑ͏ʹมߋ͢Δ ख࡞ۀͰ࠶ىಈͨ͘͠ͳ͍৔߹
29. ͓·͚
30. ͓·͚ όέοτʹ8ݸ·Ͱ֦େ͞Ε͍ͯΔͱ͜Ζʹɺ্ͷΑ͏ʹΞαΠϯ͢Δ৔߹Λߟ͑Δ
31. ͓·͚
32. ͓·͚
33. ͓·͚ 1. ϋογϡ஋ͷੜ੒ 2. ֨ೲ͢Δόέοτͷબ୒ 3. tophashͷੜ੒ 4. tophashΛར༻ͯ͠ॻ͖ࠐΉ΂͖ϝϞϦҐஔΛಛఆ 5. ৽͍͠όέοτͷ௥ՃͱνΣʔϯ
34. ϋογϡ஋ͷੜ੒
35. ֨ೲ͢Δόέοτͷબ୒
36. tophashͷੜ੒
37. tophashͷੜ੒
38. tophashΛར༻ͯ͠ॻ͖ࠐΉ΂͖ϝϞϦҐஔΛಛఆ
39. ৽͍͠όέοτͷ௥ՃͱνΣʔϯ