Ruby 2.4 のハッシュテーブル高速化を理解する

Transcript

1. 3VCZ
   
   ͷϋογϡςʔϒϧ
   ߴ଎ԽΛཧղ͢Δ
   
   /BP
   .JOBNJ
   !TPVUI

2. ࣗݾ঺հ

3. /BP
   .JOBNJ
   
   !TPVUI
   !NJOBNJP 4PGUXBSF
   FOHJOFFS
   
   !
   8BOUFEMZ
   *OD

4. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰

5. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰

6. 3VCZ
   Y

7. w ೥·Ͱʹ
   3VCZ
   ͸ഒ଎͘ͳΔ
   CZ
   !NBU[ 
   3VCZ
   ͱύϑΥʔϚϯε w .VMUJ
   5ISFBE
   +*5
   FUD
   w 3VCZ
   Y w

   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎Խ /&8

8. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰

9. 
   ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ

10. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ

11. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ w 36#:#&/$)
    w 
    ߴ଎Խ
    w ϝϞϦ࢖༻ྔ
    
    ࡟ݮ 1000000.times.map{|i| a={}; 8.times{|j|

    a[j]=j}; a} IUUQTSVCZCFODIPSHSVCZSVCZSFMFBTFT SFTVMU@UZQFIBTI@TNBMM

12. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ w QJDP@IUUQ@QBSTFS
    w 
    ߴ଎Խ IUUQLB[FCVSPIBUFOBCMPHDPNFOUSZ
    ྘
    ʜ
    3VCZ
    
    ੨
    ʜ
    3VCZ
    QSF

13. ܶతʹ଎͘ͳͬͯΔ

14. w 
    
    3VCZ
    ͱύϑΥʔϚϯε
    w 
    
    3VCZ
    
    Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
    w 
    
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
    w 
    
    ·ͱΊ ࠓ೔࿩͢಺༰

15. 
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ w ϋογϡςʔϒϧͷিಥ࣌ͷڍಈΛมߋ $IBJOJOH 0QFO
    "ESFTTJOH w ϙΠϯτ͸ʮσʔλͷہॴੑͷ޲্ʯ

16. 
    σʔλͷہॴੑ͸ͳͥॏཁ͔ w 1SPDFTTPS
    ʹ͸ଟஈΩϟογϡ͕ଘࡏ
    w Ωϟογϡʹ
    IJU
    ͢ΔͱύϑΥʔϚϯε޲্ $16 L# .BJO
    .FNPSZ -
    $BDIF -
    $BDIF

    -
    $BDIF .# (# L# #
    d
    
    OT IUUQTUBDLPWFSqPXDPNRVFTUJPOTBQQSPYJNBUFDPTUUPBDDFTTWBSJPVTDBDIFTBOENBJONFNPSZ d
    OT

17. 
    σʔλͷہॴੑ͸ͳͥॏཁ͔ w 1SPDFTTPS
    ʹ͸ଟஈΩϟογϡ͕ଘࡏ
    w σʔλͷہॴੑ͕ॏཁ $16 L# .BJO
    .FNPSZ -
    $BDIF -
    $BDIF

    -
    $BDIF .# (# L# #
    d
    
    OT IUUQTUBDLPWFSqPXDPNRVFTUJPOTBQQSPYJNBUFDPTUUPBDDFTTWBSJPVTDBDIFTBOENBJONFNPSZ d
    OT

18. 
    0QFO
    "ESFTTJOH
    Ͱσʔλͷہॴੑ্͕͕Δͷ͸ͳͥʁ w $IBJOJOH
    0QFO
    "ESFTTJOH
    ͭͷΞϧΰϦζϜΛൺֱ w ૬ҧ఺
    ϋογϡςʔϒϧͷিಥ࣌ͷڍಈ
    w $IBJOJOH
    
    ࿈݁ϦετΛḷͬͯ୳ࡧ
    w 0QFO
    "ESFTTJOH
    
    "SSBZ
    ্Ͱ
    JOEFY
    Λม͑ͯ୳ࡧ

    w ڞ௨఺
    w ϋογϡςʔϒϧ͸
    LFZ
    ͷ
    IBTI
    ஋
    Λ
    JOEFY
    ʹར༻

19. 
    $IBJOJOH
    ͷ࢓૊Έ w UBCMF
    ͸࿈݁Ϧετ΁ͷϙΠϯλΛอ࣋
    w ಉ͡
    IBTI
    Λ࣋ͭ৔߹͸ɺ࿈݁ϦετΛḷΔ IUUQXXXBMHPMJTUOFU%BUB@TUSVDUVSFT)BTI@UBCMF$IBJOJOH FOUSZ UBCMF LFZ

20. 
    $IBJOJOH
    ͷ໰୊఺ w ࿈݁ϦετͷFOUSZ͸ɺNFNPSZ্Ͱ཭Εͯ഑ஔ
    w σʔλͷہॴੑ͕௿͍ FOUSZ UBCMF LFZ

21. 
    3VCZ
    
    Ҏલͷ
    $IBJOJOH w ૒ํ޲Ϧετʹͳ͓ͬͯΓɺσʔλͷہॴੑ͕௿͍ ͚ͩͰͳ͘QSFW
    ϙΠϯλͳͲͷ෼͚ͩ
    FOUSZ
    ͷσʔ λ͕Ͱ͔͍ͷ΋໰୊ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT UBCMF FOUSZ FOUSZ FOUSZ

22. 
    3VCZ
    
    Ҏલͷ
    $IBJOJOH w ૒ํ޲Ϧετʹͳ͓ͬͯΓɺσʔλͷہॴੑ͕௿͍ ͚ͩͰͳ͘QSFW
    ϙΠϯλͳͲͷ෼͚ͩ
    FOUSZ
    ͷσʔ λ͕Ͱ͔͍ͷ΋໰୊ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT UBCMF FOUSZ FOUSZ FOUSZ

    ஗͍

23. 
    0QFO
    "ESFTTJOH
    ͷ࢓૊Έ w UBCMF
    ͸
    FOUSZ
    ΁ͷ
    QPJOUFS
    Λ௚઀อ࣋
    w ಉ͡
    IBTI
    Λ࣋ͭ৔߹͸ɺJOEFY
    ΛͣΒ͢ FOUSZ UBCMF LFZ IUUQXXXBMHPMJTUOFU%BUB@TUSVDUVSFT)BTI@UBCMF0QFO@BEESFTTJOH

24. 
    3VCZ
    
    ͷ
    0QFO
    "ESFTTJOH UBCMF FOUSJFT TUBSU CPVOE w UBCMF
    FOUSJFT
    ͕྆ํ
    "SSBZ
    ʹͳ͓ͬͯΓσʔλͷہॴ ੑ͕ߴ͘ɺ
    ͭͭͷ
    FOUSZ
    ͷσʔλαΠζ΋খ͍͞ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT

25. 
    3VCZ
    
    ͷ
    0QFO
    "ESFTTJOH UBCMF FOUSJFT TUBSU CPVOE w UBCMF
    FOUSJFT
    ͕྆ํ
    "SSBZ
    ʹͳ͓ͬͯΓσʔλͷہॴ ੑ͕ߴ͘ɺ
    ͭͭͷ
    FOUSZ
    ͷσʔλαΠζ΋খ͍͞ ߴ଎Խ

26. 
    3VCZ
    
    Ͱ͸ߋʹࡉ͔͘࠷దԽ w ݅਺͕গͳ͍࣌ͷ࠷దԽʢলϝϞϦɺߴ଎Խʣ
    w ݅਺͕গͳ͍࣌͸
    BSSBZ
    ͭͰ
    MJOFBS
    TFBSDI
    w ݅਺͕গͳ͍࣌͸
    CJU
    CJU
    ͳͲͰ
    JOEFY
    Λදݱ w 'VMM
    DZDMF
    MJOFBS
    DPOHSVFOUJBM
    HFOFSBUPS
    Λ
    

    TFDPOEBSZ
    IBTI
    ͱͯ͠ར༻
    w ߴ଎͔ͭ
    IBTI
    ͱͯ͠ͷੑೳ΋ྑ͍

27. w 
    
    3VCZ
    ͱύϑΥʔϚϯε
    w 
    
    3VCZ
    
    Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
    w 
    
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
    w 
    
    ·ͱΊ ࠓ೔࿩͢಺༰

28. 
    ·ͱΊ w 3VCZ
    
    ͸ϋογϡςʔϒϧ͕ܶతʹߴ଎Խɻ࣮ࡍ ʹΞϓϦέʔγϣϯ΋ߴ଎Խɻ
    w 3VCZ
    
    ʹͯ͠շదͳ
    3VCZ
    ϥΠϑΛૹΖ͏ʂ

29. ࢀߟϦϯΫ w 3VCZ
    
    ϦϦʔε
    w IUUQTXXXSVCZMBOHPSHKBOFXT SVCZSFMFBTFE
    w 'FBUVSF
    
    )BTI
    UBCMFT
    XJUI
    PQFO
    BESFTTJOH
    w IUUQTCVHTSVCZMBOHPSHJTTVFT
    

    w 5PXBSET
    'BTUFS
    3VCZ
    )BTI
    5BCMFT
    w IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSET GBTUFSSVCZIBTIUBCMFT