BIBLIOGRAPHY
김정한. 2022. “효율적인 멀티 코어 프로그래밍을 위한 함수형 언어의 가변성 연구.” 한국정보과학회 학술발표논문집, June, 1631–32. https://www.dbpia.co.kr/Journal/articleDetail?nodeId=NODE11113773.
Bagwell, Phil, and Tiark Rompf. 2012. “Rrb-Trees: Efficient Immutable Vectors,” 6.
“Clojure’s Core.Rrb-Vector.” (2013) 2022. May 29, 2022. https://github.com/clojure/core.rrb-vector.
Steindorfer, Michael J. 2019. “Efficient Immutable Collections.”
Steindorfer, Michael J., and Jurgen J. Vinju. 2016. “Towards a Software Product Line of Trie-Based Collections.” In Proceedings of the 2016 Acm Sigplan International Conference on Generative Programming: Concepts and Experiences, 168–72. Amsterdam Netherlands: ACM. https://doi.org/10.1145/2993236.2993251.
Stucki, Nicolas, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. “Rrb Vector: A Practical General Purpose Immutable Sequence.” In Proceedings of the 20th Acm Sigplan International Conference on Functional Programming, 342–54. Vancouver BC Canada: ACM. https://doi.org/10.1145/2784731.2784739.
“Understanding Clojure’s Persistent Vectors.” 2013. 2013. https://hypirion.com/musings/understanding-persistent-vector-pt-1.
History
Clojure Persistent Vectors -
- 2022년도 관련 연구 조사한 것들 @기계인간 johngrib vim 블로그에 벡터 관련 내용도 있다.
관련노트
2022 관련연구 링크
효율적인 멀티 코어 프로그래밍을 위한 함수형 언어의 가변성 연구
(김정한 2022)
- 김정한 and 엄영익
- 김정한, 엄영익 | 한국정보과학회 학술발표논문집 | 2022.6
- 2022
Understanding Clojure’s Persistent Vectors
(“Understanding Clojure’s Persistent Vectors” 2013)
- 2013
RRB-Trees: Efficient Immutable Vectors
(Bagwell and Rompf 2012)
-
Bagwell, Phil and Rompf, Tiark
-
Immutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we extend the vector data type with a new underlying data structure, Relaxed Radix Balanced Trees (RRB-Trees), and show how this structure allows immutable vector concatenation, insert-at and splits in O(logN ) time while maintaining the index, update and iteration speeds of the original vector data structure.
-
2012
Efficient Immutable Collections
(Steindorfer 2019)
-
Steindorfer, Michael J.
-
2019
RRB Vector: a Practical General Purpose Immutable Sequence
(Stucki et al. 2015)
- RRB vector
- Stucki, Nicolas and Rompf, Tiark and Ureche, Vlad and Bagwell, Phil
- State-of-the-art immutable collections have wildly differing performance characteristics across their operations, often forcing programmers to choose different collection implementations for each task. Thus, changes to the program can invalidate the choice of collections, making code evolution costly. It would be desirable to have a collection that performs well for a broad range of operations. To this end, we present the RRB-Vector, an immutable sequence collection that offers good performance across a large number of sequential and parallel operations. The underlying innovations are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows efficient structural reorganization, and (2) an optimization that exploits spatio-temporal locality on the RRB data structure in order to offset the cost of traversing the tree.
- 2015
Towards a Software Product Line of Trie-based Collections
(Steindorfer and Vinju 2016)
-
Steindorfer, Michael J. and Vinju, Jurgen J.
-
Collection data structures in standard libraries of programming languages are designed to excel for the average case by carefully balancing memory footprint and runtime performance. These implicit design decisions and hard-coded trade-offs do constrain users from using an optimal variant for a given problem. Although a wide range of specialized collections is available for the Java Virtual Machine (JVM), they introduce yet another dependency and complicate user adoption by requiring specific Application Program Interfaces (APIs) incompatible with the standard library. A product line for collection data structures would relieve library designers from optimizing for the general case. Furthermore, a product line allows evolving the potentially large code base of a collection family efficiently. The challenge is to find a small core framework for collection data structures which covers all variations without exhaustively listing them, while supporting good performance at the same time. We claim that the concept of Array Mapped Tries (AMTs) embodies a high degree of commonality in the sub-domain of immutable collection data structures. AMTs are flexible enough to cover most of the variability, while minimizing code bloat in the generator and the generated code. We implemented a Data Structure Code Generator (DSCG) that emits immutable collections based on an AMT skeleton foundation. The generated data structures outperform competitive handoptimized implementations, and the generator still allows for customization towards specific workloads.
-
2016
Clojure’s core.rrb-vector
(“Clojure’s Core.Rrb-Vector” [2013] 2022)
-
RRB-Trees in Clojure
-
2022