9.5 配列指向プログラミングの限界
空間計算量がなんともならん！ という話を何か実例を使って。
あるいはどうやれば高速なプログラムが書けるかと言う話
- in-place updateは必須
- しかし引数をin-place updateできるか?
- 場合によっては対応手法を使う事が必要
と言う話を以下の数値を使っていつか書く予定。
in-place update必須
l ↩ l∾π
l ∾⟜π ↩
in-place updateになってない場合
l ∾⟜(⊑l) ↩
引数として使われるsubjectのin-place update問題
F ← {l‿k : l ∾⟜(k⊑l) ↩ ⋄ ⟨l,k+1⟩}
•_while_が絡んだ引数問題
x ← 1⊑{k‿l : l ∾⟜(k⊑l) ↩ ⋄ ⟨k+1, l⟩}•_while_(100>⊑)0‿⟨⟩
パターンマッチングが絡んだ引数問題
名前空間によるカプセル化(singleton化?)
!⟜(start_length⊸≡) ≠l ← start_length↑π
"update lst" util.Debug {{c‿m : l ↩ l∾π ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿⟨⟩}•_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place -" util.Debug {{c‿m : l ∾⟜π ↩ ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿⟨⟩}•_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"update arg" util.Debug {l ↩ 1⊑{c‿l : l ↩ l∾π ⋄ ⟨c+1,l⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place -" util.Debug {l ↩ 1⊑{c‿l : l ∾⟜π ↩ ⋄ ⟨c+1,l⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place 2" util.Debug {l ↩ 1⊑{c‿l : ⟨c+1,l∾π⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"wrap in ns" util.Debug {l ↩ {𝕩.vec}1⊑{c‿w : w.Add π ⋄ ⟨c+1,w⟩}•_while_(𝕩>⊑)0‿(List l)} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
m ← Longlist 100000
{m.Add π ⋄ 𝕩+1}•_while_(start_length⊸>)0
!⟜(start_length⊸≡) m.Size@
"indirect -" util.Debug {m ↩ 1⊑{c‿m : m.Add π ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿m} •_timed updates
!⟜((start_length+updates)⊸≡) m.Size@
# - update lst: 6.697469000000001
# - in-place -: 0.0014390000000000002
# - update arg: 6.643209000000001
# - in-place -: 6.647899000000001
# - in-place 2: 6.660026
# - wrap in ns: 0.0029370000000000004
# - indirect -: 0.002893
- init size/iteration/samples: ⟨ 1 200000 10 ⟩
| # | code | time (sec.) |
|---|---|---|
| 1 | {c‿m : l ↩ l∾π ⋄ ⟨c+1,m⟩}•_while_ (𝕩>⊑) 0‿⟨⟩ | 3.3718565 |
| 2 | {c‿m : l ∾⟜π ↩ ⋄ ⟨c+1,m⟩}•_while_ (𝕩>⊑) 0‿⟨⟩ | 0.0122643 |
| 3 | l ↩ l{𝕩 ↩ 𝕩∾π ⋄ 𝕩}´↕𝕩 | 3.2780491 |
| 4 | l ↩ l{𝕩 ∾⟜π ↩ ⋄ 𝕩}´↕𝕩 | 0.0053715 |
| 5 | l ↩ 1⊑{𝕩 ↩ 𝕩∾π ⋄ ⟨𝕨+1,𝕩⟩}´•_while_ (𝕩>⊑) 0‿l | 3.4005579 |
| 6 | l ↩ 1⊑{𝕩 ∾⟜π ↩ ⋄ ⟨𝕨+1,𝕩⟩}´•_while_ (𝕩>⊑) 0‿l | 0.0091961 |
| 7 | l ↩ 1⊑{w‿x : x ∾⟜π ↩ ⋄ ⟨w+1,x⟩}•_while_(𝕩>⊑) 0‿l | 3.3545225 |
| 8 | l ↩ 1⊑{⟨𝕨+1,∾𝕩._modify π⟩}´•_while_(𝕩>⊑) ⟨0,Ref l⟩ | 0.0139621 |
| 9 | l ↩ 1⊑{⟨𝕨+1,∾𝕩._modify π⟩}´•_while_(𝕩>⊑) ⟨0,Ref l⟩ | 0.0176845 |
| 10 | l ↩ (Ref l){∾𝕩._modify π}´↕𝕩 | 0.0102602 |
- substitute list object
- in-place update object
- subst. arg in fold loop
- in-place arg in fold loop
- subst. arg in •while
- in-place arg in •while
- in-place args in •while
- Ref._modify arg in while
- Ref._modify args in while
- Ref._modify arg in fold