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
6
【Go言語】イテレータ
tomo1227
0
8
【Go言語】エラーハンドリング
tomo1227
0
10
AIに淘汰されないようにするには?
tomo1227
0
13
range.pdf
tomo1227
0
7
【Go言語】break
tomo1227
0
6
【Go言語】反復処理
tomo1227
0
6
【Go言語】値の比較
tomo1227
0
20
【Go言語】値レシーバ v.s. ポインタレシーバ
tomo1227
0
17
Other Decks in Programming
See All in Programming
実践Dash - 手を抜きながら本気で作るデータApplicationの基本と応用 / Dash for Python and Baseball
shinyorke
2
210
Micro Frontends for Java Microservices - dev2next 2024
mraible
PRO
0
180
RDBの世界をぬりかえていくモデルグラフDB〜truncus graphによるモデルファースト開発〜
jurabi
0
140
グローバルなソフトウェアテスト組織における課題と戦略 / Challenges and Strategies in a Global Software Testing Organization #mf_techday
imtnd
0
220
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
5
210
[PHPカンファレンス沖縄2024]「無理なくできるだけ安全に」テストもないレガシーコードをリファクタリングするテクニック
ikezoemakoto
3
110
NEWTにおけるiOS18対応の進め方
ryu1sazae
0
180
ビット演算の話 / Let's play with bit operations
kaityo256
PRO
3
140
ROS 2のZenoh対応とZenohのROS 2対応
takasehideki
2
240
The Efficiency Paradox and How to Save Yourself and the World
hollycummins
0
130
CDKを活用した 大規模コンテナ移行 プロジェクトの紹介
yoyoyopg
0
230
上手に付き合うコンポーネントテスト
quramy
3
1.2k
Featured
See All Featured
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
504
140k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
167
48k
GraphQLの誤解/rethinking-graphql
sonatard
65
9.9k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
230
17k
Building Flexible Design Systems
yeseniaperezcruz
327
38k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
45
4.9k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9k
Designing with Data
zakiwarfel
98
5.1k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
29
1.7k
A Modern Web Designer's Workflow
chriscoyier
692
190k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
37
1.7k
Code Reviewing Like a Champion
maltzj
519
39k
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Λར༻ͯ͠ॻ͖ࠐΉ͖ϝϞϦҐஔΛಛఆ
৽͍͠όέοτͷՃͱνΣʔϯ