Data Structure
Human greed in a limitless grid
Last updated
Human greed in a limitless grid
Last updated
The data structure employed by a standard exchange is purposefully designed to be highly flexible and scalable. This versatile data structure plays a pivotal role within the context of a greedy algorithm, facilitating data organization through a set of interconnected linked lists. This sorting mechanism efficiently paves the way for achieving optimized outcomes in the algorithmic process.
A linked list is a fundamental data structure in computer science used to store and manage collections of data in a linear, one-dimensional manner. Unlike arrays, which have a fixed size, linked lists are dynamic and can grow or shrink as data is added or removed. This flexibility makes linked lists suitable for handling data of varying sizes.
One intriguing aspect of linked lists is their capacity to accommodate a theoretically infinite amount of data, at least in theory. This notion is rooted in the concept of Aleph zero (ℵ₀), which represents the lowest level of infinity in mathematics. Aleph zero is the cardinality of the set of natural numbers (1, 2, 3, ...), and it signifies a countable infinity.
In practical terms, a linked list's length is not truly infinite, as it is limited by the available memory of the computer. However, the dynamic nature of linked lists means they can continue to grow as long as memory allows. This property aligns with the concept of Aleph zero, where the linked list can handle a countable number of data elements.
To put it succinctly, linked lists serve as a data structure capable of accommodating an ever-expanding amount of data in a linear fashion. While not truly infinite, their dynamic nature allows them to reach sizes constrained only by the practical limitations of computer memory. The reference to Aleph zero underscores their capacity to handle a countable infinity of data elements, mirroring the lowest level of infinity in mathematics.
Cardinality in set theory, serves to establish a concept of equality of size between two countably infinite sets. Consider two infinite sets representing the base asset (B) and the quote asset (Q) within a given trading pair. Within these sets, individual elements, denoted as 'b' and 'q,' exhibit a one-to-one correspondence, and their associated prices are computed as follows:
When both sets have the same cardinality, their sizes are identical. This means that you can pair up every element from one set with a unique element from the other set without leaving any elements unmatched.
Countably infinite data sets in base and quote align with another countably infinite data structure within the range of 0 to 2^256 - 1 storing bid and ask order. Bid order keeps the deposit of quote asset, and Ask order keeps the deposit of base asset from the user.
Each base and quote asset possesses a two-dimensional grid orderbook structured as sorted linked lists, optimizing data organization for seamless trading experiences.
