On The Way From Sequence to RandomAccessCollection in Swift

We will look at the implementation of the function in collections in terms of the evolution of computational complexity from the basic protocol to the protocol. suffix Sequence RandomAccessCollection Before reading this article, get acquainted with the concept of computational complexity. Each Swift developer used features from the family of protocols. It comes from the Sequence protocol and includes , , , , and other protocols related to asynchrony, laziness, collection variability. Here, we'll look at the most basic protocols that provide read-only access: , , , and protocols. Sequence Sequence Collection BidirectionalCollection RandomAccessCollection Sequence Collection BidirectionalCollection RandomAccessCollection We use the functions and properties of collections (e.g., , , ) without thinking about internal implementation, although the implementation initially looks simple. However, a feature available at different levels of these protocols' hierarchy can be implemented differently and with diverse computational complexity. prefix sort count Each new protocol in the protocol hierarchy from to announces new basic capabilities. They allow you to implement new default functions in the protocol extension and optimize existing ones declared in inherited protocols. We'll see the evolution of implementation based on new functions at each level of the protocol hierarchy on the example of the standard implementation of the function for the , , , and . The function returns a subsequence of the last elements. Sequence RandomAccessCollection suffix Sequence Collection BidirectionalCollection RandomAccessCollection suffix k Sequence The is the base protocol in the hierarchy of collections. The primary ability is to iterate one by one element from some set due to the iterator. This set can be limited or unlimited, and an iteration of elements can be destructive or non-destructive. The protocol doesn't say anything about it. Sequence does not have property , but there is an property. On the simple principle of iterating elements, it becomes possible to write many amazing functions, such as , , , , , , , , , etc. The protocol has a default implementation for these functions. They may be suboptimal; for example, we cannot access an element using an index with computational complexity , based only on the principle of iterative elements. The simplicity of this protocol limits the ability to implement functions. We can only iterate the elements. That's it. Sequence count underestimatedCount prefix suffix contains first min max drop sorted map O(1) What about function 'suffix' in Sequence? Only one simple function allows us to iterate over a set of elements from start to finish at this protocol level. The only way to get the last elements is to enumerate every component, putting the current part into a ring buffer structure. The default implementation of this function defines with the capacity of elements. k Sequence RingBuffer k The first element from the is put into the first cell of the ring buffer. The second element puts to -nd cell, -th element puts to -th cell, -th puts to the -st cell of buffer (while previous items stay in their cells), and further every current piece rewrite an old one. Thus, when we get the last element of the sequence, all the last elements are in the ring buffer. The only thing we should do is cut and glue the result array from the buffer with the right index equal to . This function's computational complexity is since iterate over all the elements. Sequence 2 k k k+1 1 k (count of elements in the sequence+1) % k O(n) A code snippet of the current implementation Collection The protocol has the same capabilities as the protocol, but it declares non-destructive iteration of the elements multiple times and provides access to the items by index. Collection Sequence In addition, iteration over elements provides the same order as the elements when indexing. Iterating through the elements by an index is only available in one direction. You can get an element by index, calculate the following index, get the next item by this index, calculate the following index, and so on. However, you cannot calculate the index in reverse order. For example, for simplicity, suppose that we have a collection whose indices are numbers. To get the first element, we should use the property available in the protocol (also, there is ), which will be . Then we get the following index of our collection, next to the initial index — , will be . However, in , there is no way to define the index preceding index . adds this ability. Int startIndex endIndex 0 index(after: 0) 1 Collection 1 BidirectionalCollection What about function 'suffix' in Collection? In , we can call the subscript of a collection by range to get the elements we need, and it seems like a simple operation at first. We need to get the start index and call collection's subscript . The last function will work with complexity, but there is a problem with getting the start index of the last elements. We do not have a function for getting the -th index with complexity to obtain it. The protocol only provides the ability to get the next index in , — . To reach the -th index, first, we need to calculate , , and so on, and then up to our index . Collection [suffixStartIndex .. <endIndex] O(1) k i O(1) O(1) index(after:) i startIndex + 1 startIndex + 2 suffixStartIndex Thus, the function in has a different default implementation based on index calculation rather than iteration over all elements, but the complexity of this function remains . suffix Collection O(n) has complexity O(n) index(_: offsetBy: limitedBy) BidirectionalCollection A collection that has just one additional base function adds new features. For example, the property (computed as an item at the index preceding ) and reversed (returns another structure, passing our collection as a parameter to the initializer). index(before:) last endIndex ReversedCollection Yes, until now, we haven't been able to implement these functions in previous protocols because they would have been highly ineffective. For instance, we could iterate over all the elements on the protocol and take the last one. In reality, there is no such function, but if we call the function, such an algorithm will be used. Sequence suffix(1) What about function 'suffix' in BidirectionalCollection? The provides one new primary feature, which is to get the following index backward order. As we remember, in the protocol, the starting index of the required subsequence was calculated from the very beginning. BidirectionalCollection Collection However, implementing the function in the protocol uses the ability to compute the previous index; it calculates the index of the starting element of the subsequence, starting from the end. This approach can have its advantages, especially if is a small number. suffix BidirectionalCollection k It looks like it is possible to optimize the function here by calculating how profitable it is to go from start to end or end to start to compute the subsequence's starting index. But to make such a comparison, you need to call the property, which has complexity in this protocol. suffix count O(n) Therefore, the implementation assumes that the number of elements is less than half of . Otherwise, the function execution will not be the most efficient. k n has complexity O(k) and works in a reverse way: from the end to the beginning (it was not available in inherited protocols) index(_: offsetBy: limitedBy) RandomAccessCollection Each new protocol in the protocol hierarchy, in addition to new capabilities, provides more efficient implementations of the functions defined in the base protocols. The peculiarity of this protocol is that it doesn't offer new primary functions, but it defines the requirements for the complexity of working with indices; calculating the distance between the indices and getting the index at some distance from the given one must be implemented with complexity . O(1) In the previous protocol, the complexity of these functions could be , where is the number of indices between two given ones, but now these functions have a complexity of . Many functions can be significantly optimized based on this, for example, the property, which now has a computational complexity of . O(k) k O(1) count O(1) What about function 'suffix' in RandomAccessCollection? doesn't provide any new core functions, but it declares that the and functions must operate with complexity , which gives us the ability to calculate the starting index of our instantly. RandomAccessCollection index(_: offsetBy:) distance(from: to:) O(1) suffix Moreover, there is no need to invent any new algorithm or implementation. It’s enough to use the old implementation but of much greater complexity - . O(1) Conclusion With these simple examples, we've seen how the capabilities of the sequence protocols from to evolve. I hope you've raised your awareness of the protocol choices for your custom sequences, and you'll understand better the default implementations in these protocols and the logic of the functions based on the protocols' core capabilities. Sequence RandomAccessCollection