Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
【Go言語】map
Search
Tomoki Ota
August 16, 2024
Programming
0
16
【Go言語】map
mapについて解説しています
Tomoki Ota
August 16, 2024
Tweet
Share
More Decks by Tomoki Ota
See All by Tomoki Ota
【Go言語】イテレータ
tomo1227
0
5
【Go言語】エラーハンドリング
tomo1227
0
8
AIに淘汰されないようにするには?
tomo1227
0
12
range.pdf
tomo1227
0
5
【Go言語】break
tomo1227
0
5
【Go言語】反復処理
tomo1227
0
4
【Go言語】値の比較
tomo1227
0
17
【Go言語】値レシーバ v.s. ポインタレシーバ
tomo1227
0
16
【Go言語】名前付き戻り値
tomo1227
0
13
Other Decks in Programming
See All in Programming
Modular Monolith Go Server with GraphQL Federation + gRPC
110y
1
580
Regular Expressions, REXML, Automata Learning
makenowjust
0
210
いつか使える ObjectSpace / Maybe useful ObjectSpace
euglena1215
2
130
状態管理ライブラリZustandの導入から運用まで
k1tikurisu
3
460
RAGの回答精度評価用のQAデータセットを生成AIに作らせた話
kurahara
0
240
Android開発以外のAndroid開発経験の活かしどころ
konifar
2
700
Rustではじめる負荷試験
skanehira
5
1.2k
LangGraphでのHuman-in-the-Loopの実装
os1ma
3
1k
GenU導入でCDKに初挑戦し、悪戦苦闘した話
hideg
0
150
意外とフォントが大事だった話 / Font Issues on Internationalization
fumi23
0
100
僕が思い描くTypeScriptの未来を勝手に先取りする
yukukotani
9
2.3k
Jakarta EE meets AI
ivargrimstad
1
350
Featured
See All Featured
The Cost Of JavaScript in 2023
addyosmani
42
5.2k
Music & Morning Musume
bryan
46
6k
No one is an island. Learnings from fostering a developers community.
thoeni
18
2.9k
Navigating Team Friction
lara
183
13k
RailsConf 2023
tenderlove
28
800
Web development in the modern age
philhawksworth
204
10k
The Brand Is Dead. Long Live the Brand.
mthomps
53
37k
Adopting Sorbet at Scale
ufuk
73
8.9k
Practical Orchestrator
shlominoach
185
10k
Designing for Performance
lara
604
68k
10 Git Anti Patterns You Should be Aware of
lemiorhan
653
58k
Into the Great Unknown - MozCon
thekraken
29
1.4k
Transcript
Tomoki Ota ʲGoݴޠʳmap
mapͱ? 2
mapͱʁ 3
mapͱʁ 4
mapͱʁ GoͰɺmapϋογϡςʔϒϧͷσʔλߏʹجͮ͘ 5
mapͱʁ ෦తʹϋογϡςʔϒϧɺόέοτͷϙΠϯλͷྻ ֤όέοτΩʔͱͷϖΞΛ8ͭ࣋ͭ 6
mapͷϋογϡςʔϒϧ map[string]intͷόέοτ0ʹͨ͠ϋογϡςʔϒϧදݱͷྫ 7 hash(“two") = 0
ཁૉͷૠೖ 8 ผͷཁૉͷ map[string]intͷόέοτ0ʹͨ͠ϋογϡςʔϒϧදݱͷྫ
ཁૉͷૠೖ(όέοτ͕͍ͬͺ͍ͷͱ͖) 9
ಡΈग़͠ɺߋ৽ɺআͷܭࢉྔ 10 Λόέοτͷ૯ͱ͢Δͱɺ (σϑΥϧτ1ɺΦʔόϑϩʔ࣌ෳͷόέοτ) p ࠷ѱ࣌ؒܭࢉྔ ͱͳΔ O(p)
ॳظԽ
ॳظԽ
100ສݸͷཁૉͷՃ Ϛοϓ͕ࣗಈͰ֦େͯ͠ɺόέοτΛอ࣋͢Δྻ͕2ഒͱͳΔ
Ϛοϓ͕֦େ͢Δ݅ ྻͷཁૉ͝ͱʹόέοτ͕อ࣋͢Δཁૉͷฏۉ(Load Factor)͕ ͋Δఆ(ݱঢ়6.5ɻ80%)ΑΓେ͖͍ͱ͖ Φʔόʔϑϩʔ͍ͯ͠Δྻͷཁૉ͕ͱͯେ͖͍ͱ͖
Ωʔͷૠೖͷܭࢉྔ 15 Ϛοϓ͕֦େ͢Δͱ͖ɺશͯͷΩʔ͕શͯͷόέοτ࠶ஔ͢Δɻ ΛϚοϓͷཁૉͷ૯ͱ͢Δͱ n ࠷ѱ࣌ؒܭࢉྔ ͱͳΔ O(n)
ॳظԽ 16 makeͰॳظԽ͢Δ
ॳظԽ 17
ॳظԽ 18 αΠζnΛࢦఆ͢ΔͱɺGoϥϯλΠϜʹগͳ͘ͱnݸͷཁૉΛ อ࣋Ͱ͖ΔϚοϓΛׂΓͯΔΑ͏ʹཁٻ͢Δɻ ❌ ࠷େnݸͷཁૉΛ࣋ͭϚοϓΛ࡞Δ
mapͱϝϞϦʔϦʔΫ
mapͱϝϞϦʔϦʔΫ
mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓͯΔ 2. 100ສݸͷཁૉΛՃ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓͯΔ 2. 100ສݸͷཁૉΛՃ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
mapͱϝϞϦʔϦʔΫ 1. ۭϚοϓΛׂΓͯΔ 2. 100ສݸͷཁૉΛՃ͢Δ 3. શͯͷཁૉΛऔΓআ͍ͯɺGCΛ࣮ߦͤ͞Δ 4. ֤εςοϓͷޙɺώʔϓͷେ͖͞(Mb)Λදࣔ
GoͷϚοϓruntime.hmapߏମͷϙΠϯλɻ ͜ͷߏମʹɺϚοϓͷόέοτΛࣔ͢BϑΟʔϧυͳͲෳͷϑΟʔϧυ͕͋Δɻ mapͱϝϞϦʔϦʔΫ
mapͱϝϞϦʔϦʔΫ
100ສݸͷཁૉΛՃ͢Δ → Bͷ18ɺ όέοτͱͳΔ 100ສݸͷཁૉΛऔΓআ͘ → B18ͷ··ɻΏ͑ʹɺϚοϓ·ͩಉ͡ͷόέοτΛอ࣋͢Δ 218 = 262144
mapͱϝϞϦʔϦʔΫ
mapͱϝϞϦʔϦʔΫ 1࣌ؒͷσʔλΛอଘ͢Δͱ͢ΔɻେنͳϓϩϞʔγϣϯΛߦ ͏߹ɺ1࣌ؒޙʹɺඦສਓͷ͓٬༷͕γεςϜʹଓ͢Δ͔ ͠Εͳ͍ɻ͔͠͠ɺϓϩϞʔγϣϯͷޙɺϐʔΫ࣌ͱಉ ͡ͷόέοτ͕Ϛοϓʹอ࣋͞Εͨ··ʹͳΔɻ͜ͷΑ͏ͳγ φϦΦͷ߹ɺϝϞϦͷফඅྔ͕େ෯ʹݮগͤͣɺϝϞϦͷফඅ͕ ଟ͘ͳΔɻ
ݱࡏͷϚοϓͷίϐʔΛఆظతʹ࠶࡞͢Δ mapܕ͕ྻͷϙΠϯλΛอ࣋͢ΔΑ͏ʹมߋ͢Δ ख࡞ۀͰ࠶ىಈͨ͘͠ͳ͍߹
͓·͚
͓·͚ όέοτʹ8ݸ·Ͱ֦େ͞Ε͍ͯΔͱ͜Ζʹɺ্ͷΑ͏ʹΞαΠϯ͢Δ߹Λߟ͑Δ
͓·͚
͓·͚
͓·͚ 1. ϋογϡͷੜ 2. ֨ೲ͢Δόέοτͷબ 3. tophashͷੜ 4. tophashΛར༻ͯ͠ॻ͖ࠐΉ͖ϝϞϦҐஔΛಛఆ 5.
৽͍͠όέοτͷՃͱνΣʔϯ
ϋογϡͷੜ
֨ೲ͢Δόέοτͷબ
tophashͷੜ
tophashͷੜ
tophashΛར༻ͯ͠ॻ͖ࠐΉ͖ϝϞϦҐஔΛಛఆ
৽͍͠όέοτͷՃͱνΣʔϯ