Equivalence_in_JS

This slide introduces "equivalence" and Set type in JavaScript

Transcript

1. 同じ、とは N.Shimizu (chikoski@gmail.com)
2. 2と10は同じ
3. 3と10は同じ
4. 2と30029は同じ
5. Set: 重複を許さない値の集まり DPOTU
   MJTU
   
   <
   
   
   
   
   
   
   
   
   >
   DPOTU
   T
   
   OFX
   4FU <
   
   
   
   
   
   
   
   
   > 
   TTJ[F
   
   MJTUMFOHUI
   
   GBMTF
   MJTUKPJO   
   
            
   "SSBZGSPN T KPJO   
   
      
   TIBT  
   
   USVF
   TIBT  
   
   GBMTF
6. 「同じ値」のオブジェクトなのに重複してしまう DMBTT
   1PJOU\
   
   
   DPOTUSVDUPS Y
   Z \UIJTY
   UIJTZ^
   ^
   DPOTU
   Q
   
   Y
   Z
   
   OFX
   1PJOU Y
   Z 
   DPOTU
   MJTU
   
   <Q 
   
   Q 
   
   Q 
   
   Q 
   
   Q 
   
   Q 
    >
   DPOTU
   T
   
   OFX
   4FU MJTU 
   TTJ[F
   
   MJTUMFOHUI
   
   USVF
   TIBT Q 
    
   
   GBMTF
7. Setにとって、「同じ」とは？
8. ECMAScriptに定義されている同値性比較* 利用しているJSの演算子 / 関数 Setが利用しているもの Abstract Equality Comparison  Strict Equality Comparison  SameValue 0CKFUJT SameValueZero "SSBZQSPUPUZQFJODMVEF ϧ * SameValueNonNumber もありますが、処理系内部での利用に限られるので割愛します
9. Y Z Y
   
   Z Y
   
   Z 0CKFDUJT Y
   Z 4BNF7BMVF;FSP Y
   Z VOEFGJOFE OVMM USVF GBMTF USVF GBMTF   USVF USVF GBMTF USVF /B/ /B/ GBMTF GBMTF USVF USVF VOEFGJOFE GBMTF USVF GBMTF GBMTF GBMTF \Y
   Z^ \Y
   Z^ GBMTF GBMTF GBMTF GBMTF \Y
   Z^ Y USVF USVF USVF USVF
10. Set.prototype.addの振る舞い DPOTU
    T
    
    OFX
    4FU 
    
    ╘Ә㗶൶Ӽਃᘻ
    TBEE /B/ 
    
    4FU </B/>
    TBEE /B/ 
    
    4FU </B/>
    TBEE VOEFGJOFE 
    
    4FU </B/
    VOEFGJOFE>
    TBEE OVMM 
    
    4FU </B/
    VOEFGJOFE
    OVMM>
    DPOTU
    Y
    
    \Y
    
    Z
    ^
    TBEE Y 
    
    4FU </B/
    VOEFGJOFE
    OVMM
    PCKFDU>
    TBEE Y 
    
    4FU </B/
    VOEFGJOFE
    OVMM
    PCKFDU>
    TBEE \Y
    Z
    ^ 
    
    
    TBEE Y 
    
    4FU </B/
    VOEFGJOFE
    OVMM
    PCKFDU
    PCKFDU>
    
11. 演算子のオーバロードができない
12. 継承によってSetの振る舞いを変える DMBTT
    .Z4FU
    FYUFOET
    4FU\
    
    
    BEE Y \
    
    
    
    
    JG UZQFPG
    YFRVBMT
    
    GVODUJPO
    
    
    
    
    
    
    
    
    
    <UIJT>GJMUFS J
    
    YFRVBMT J MFOHUI
    
     \
    
    
    
    
    
    
    
    SFUVSO
    UIJT
    
    
    
    
    ^
    
    
    
    
    SFUVSO
    TVQFSBEE Y 
    
    
    ^
    ^
13. DMBTT
    1PJOU\
    
    
    DPOTUSVDUPS Y
    Z \UIJTY
    UIJTZ^
    
    
    FRVBMT QPJOU \
    SFUVSO
    UIJTY
    
    QPJOUY
    
    UIJTZ
    
    QPJOUZ^
    ^
    DPOTU
    Q
    
    OFX
    1PJOU 
     
    DPOTU
    Q
    
    OFX
    1PJOU 
     
    Q
    
    Q
    
    GBMTF
    QFRVBMT Q 
    
    USVF
    DPOTU
    T
    
    OFX
    .Z4FU 
    TBEE Q 
    
    4FU <PCKFDU>
    TBEE Q 
    
    4FU <PCKFDU>
    
14. 評価用のコード DPOTU
    OFYU*OU
    
    NBY7BMVF
    
    .BUIGMPPS NBY7BMVF
    
    .BUISBOEPN 
    GVODUJPO
    N TFU
    UJNFT
    \
    
    
    MFU
    UPUBM
    
    
    
    
    GPS
    MFU
    U
    
    
    U
    
    UJNFT
    U
    \
    
    
    
    
    DPOTU
    TUBSU5JNF
    
    %BUFOPX 
    
    
    
    
    DPOTU
    Q
    
    OFX
    1PJOU OFYU*OU TFUTJ[F
     
    
    
    
    
    TFUBEE Q 
    
    
    
    
    UPUBM
    
    %BUFOPX
    
    TUBSU5JNF
    
    
    ^
    
    
    SFUVSO
    UPUBM
    
    UJNFT
    ^
    
15. 適当な評価結果：激遅い* ͢Ͱʹೖ͍ͬͯΔཁૉ਺ 4FU .Z4FU                * MacBook Pro 15inch 2016 / 2.7 GHz Intel Core i7 / 16 GB 2133 MHz LPDDR3 / N = 100
16. パフォーマンス測定結果 • MySet.prototype.addの半分はnextという処理に費やされている • Setから配列への変換に時間がかかっているものと思われる
17. 「同じ値を持つもの」の検索に時間がかかってる？ DMBTT
    .Z4FU
    FYUFOET
    4FU
    \
    
    
    BEE Y
    \
    
    
    
    
    JG
    UZQFPG
    YFRVBMT
    
    GVODUJPO
    
    
    
    
    
    
    
    <UIJT>GJMUFS J
    
    YFRVBMT J MFOHUI
    
    
    \
    
    
    
    
    
    
    SFUVSO
    UIJT
    
    
    
    
    ^
    
    
    
    
    SFUVSO
    TVQFSBEE Y 
    
    
    ^
    ^
    
18. ハッシュ関数を用意する DMBTT
    )BTI4FU
    FYUFOET
    4FU
    \
    
    
    DPOTUSVDUPS JUFSBCMF
    \
    
    
    
    
    TVQFS 
    
    
    
    
    UIJTIBTI7BMVFT
    
    OFX
    4FU 
    
    
    
    
    GPS
    DPOTU
    J
    PG
    JUFSBCMF
    \
    
    
    
    
    
    
    UIJTBEE J 
    
    
    
    
    ^
    
    
    ^
    
    
    BEE WBMVF
    \
    
    
    
    
    JG
    UZQFPG
    WBMVFIBTI
    
    GVODUJPO
    \
    
    
    
    
    
    
    DPOTU
    IBTI
    
    WBMVFIBTI 
    
    
    
    
    
    
    JG
    UIJTIBTI7BMVFTIBT IBTI
    \
    
    
    
    
    
    
    
    
    SFUVSO
    UIJT
    
    
    
    
    
    
    ^
    
    
    
    
    
    
    UIJTIBTI7BMVFTBEE IBTI 
    
    
    
    
    ^
    
    
    
    
    TVQFSBEE WBMVF 
    
    
    
    
    SFUVSO
    UIJT
    
    
    ^
    ^
    DMBTT
    1PJOU
    \
    
    
    DPOTUSVDUPS Y
    Z
    \
    
    
    
    
    UIJTY
    
    Y
    
    
    
    
    UIJTZ
    
    Z
    
    
    ^
    
    
    IBTI
    \
    
    
    
    
    SFUVSO
    A\UIJTY^ \UIJTZ^A
    
    
    ^
    
    
    FRVBMT Q
    \
    
    
    
    
    SFUVSO
    UIJTY
    
    QY
    
    UIJTZ
    
    QZ
    
    
    ^
    ^
    
19. 速くなった！* ͢Ͱʹೖ͍ͬͯΔཁૉ਺ 4FU .Z4FU )BTI4FU                     * MacBook Pro 15inch 2016 / 2.7 GHz Intel Core i7 / 16 GB 2133 MHz LPDDR3 / N = 100
20. あの、属性値変わった場合は…
21. ユニークさが保てなくなる 
     
     
     
     
     
     
     
     
     
     
     
    
22. 解決策 • 変更を見張って、Set自体を作り直す • コスト高？変更の頻度が高いとうまくいかないのでは • 削除された要素を参照しているオブジェクトがいる場合は？ • 集合の集合をつくる • 同じ値のグループをつくり、そのグループを管理 • 値が変更された、別のグループへ移す • コストは低い。メモリはよく使う。
23. 同じ、は難しいのう