PFDS 10.1.2
1 like642 views
The document describes an update to the binary random-access list data structure presented in section 9.2.1. The update allows updating elements in the list by passing a function, rather than a new value, to avoid re-traversing the list on each update. This improves the time complexity of the update operation from O(log^2 n) to O(log n).
More Related Content
Similar to PFDS 10.1.2 (20)
PFDS 10.1.2
- 1. PFDS 10.1.2 Binary Random-Access List Revisited @rf0444
- 2. a Seq = NIL | CONS of a * (a * a) Seq NIL CONS 1 NIL CONS 1 (CONS (2, 3) NIL) CONS 1 (CONS (2,3) (CONS ((4,5),(6,7)) NIL))
- 3. a Seq = NIL | CONS of a * (a * a) Seq NIL 0 CONS 1 NIL 1 CONS 1 (CONS (2, 3) NIL) 3 CONS 1 (CONS (2,3) (CONS ((4,5),(6,7)) NIL)) 7
- 4. a Seq = NIL | CONS of a * (a * a) Seq CONS 1 (CONS (2,3) (CONS ((4,5),(6,7)) NIL)) 1 2 4 a a*a (a * a) * (a * a)
- 5. 9.2.1 Binary Random-Access Lists a Tree = LEAF of a | NODE of a Tree * a Tree a Digit = ZERO | ONE of a Tree a RList = a Digit list ONE ZERO ONE 1 2 3 4 5
- 6. 9.2.1 Binary Random-Access Lists 侏だけると和の撹もできるようにえる ONE ZERO ONE サイズが 5 1 2 おかしい 3 4 頼畠じゃない
- 7. 10.1.2 Binary Random-Access Lists Revisited a Seq = NIL | ZERO of (a * a) Seq | ONE of a * (a * a) Seq ((a * a) * (a * a)) * ((a * a) * (a * a)) Seq ONE ZERO ONE 1 ((2, 3), (4,5)) a a*a (a * a) * (a * a)
- 8. head, tail 寄悶 9.2.1 と揖じ
- 9. lookup lookup 5 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 10. lookup lookup 5 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) lookup 4 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 11. lookup lookup 4 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) lookup 2?の恣 ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 12. lookup lookup 2?の恣 ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) lookup 1?の恣 ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 13. lookup lookup 1?の恣 ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) lookup 0?の嘔?の恣 ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 14. lookup lookup 0?の嘔?の恣 ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) lookup 0?の恣?の嘔?の恣 ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 15. lookup lookup 0?の恣?の嘔?の恣 ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) (((4, 5), (6, 7)), ((8, 9), (10, 11))) ?の恣?の嘔?の恣 ((4, 5), (6, 7)) ????の嘔?の恣 (6, 7) ???????の恣 6
- 16. update update 5 20 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 17. update update 5 20 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . update 4 20 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 18. update cons 1 . update 4 20 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . update 2 (20, 7) ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 19. update cons 1 . ZERO . update 2 (20, 7) ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . update 1 (20, 7) ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 20. update cons 1 . ZERO . cons (2, 3) . update 1 (20, 7) ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . update 0 ((4, 5), (20, 7)) ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 21. update cons 1 . ZERO . cons (2, 3) . ZERO . update 0 ((4, 5), (20, 7)) ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . ZERO . update 0 (((4, 5), (20, 7)), ((8, 9), (10, 11))) ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 22. update cons 1 . ZERO . cons (2, 3) . ZERO . ZERO . update 0 (((4, 5), (20, 7)), ((8, 9), (10, 11))) ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . ZERO ONE (((4, 5), (20, 7)), ((8, 9), (10, 11)))
- 23. update cons 1 . ZERO . cons (2, 3) . ZERO . ZERO ONE (((4, 5), (20, 7)), ((8, 9), (10, 11))) ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (20, 7)), ((8, 9), (10, 11)))
- 24. update 枠^勣殆が ZERO のrに飴 lookup が恠る Y惚、update は O(log^2 n) 筝する､任呂覆、筝するv方を局すよ うにする
- 25. update update 5 20 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) fupdate (fn _ -> 20) 5 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 26. update fupdate (fn _ -> 20) 5 ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . fupdate (fn _ -> 20) 4 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 27. update cons 1 . fupdate (fn x -> 20) 4 ZERO ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . fupdate (fn (x, y) -> (20, y)) 2 ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 28. update cons 1 . ZERO . fupdate (fn (x, y) -> (20, y)) 2 ONE ZERO ONE (2, 3) (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . fupdate (fn (x, y) -> (20, y)) 1 ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 29. update cons 1 . ZERO . cons (2, 3) . fupdate (fn (x, y) -> (20, y)) 1 ZERO ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . fupdate (fn (w, (x, y)) -> (w, (20, y))) 0 ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 30. update cons 1 . ZERO . cons (2, 3) . ZERO . fupdate (fn (w, (x, y)) -> (w, (20, y))) 0 ZERO ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . ZERO . fupdate (fn ((w, (x, y)), z) -> ((w, (20, y)), z)) 0 ONE (((4, 5), (6, 7)), ((8, 9), (10, 11)))
- 31. update cons 1 . ZERO . cons (2, 3) . ZERO . ZERO . fupdate (fn ((w, (x, y)), z) -> ((w, (20, y)), z)) 0 ONE (((4, 5), (6, 7)), ((8, 9), (10, 11))) cons 1 . ZERO . cons (2, 3) . ZERO . ZERO ONE (((4, 5), (20, 7)), ((8, 9), (10, 11)))
- 32. update cons 1 . ZERO . cons (2, 3) . ZERO . ZERO ONE (((4, 5), (20, 7)), ((8, 9), (10, 11))) ONE ONE ZERO ONE 1 (2, 3) (((4, 5), (20, 7)), ((8, 9), (10, 11)))