I’ve been trying to contribute to statrs recently, and one of the issues I’ve been running into is that I’m trying to have an iterator that returns items in sorted order without cloning the underlying data. I’m working this PR if you wanted to take a look at my code so far. I looked up this problem and found this StackOverflow post about this topic from years ago but, frankly, I don’t believe it. Assuming you’re iterating from a vector, mutating the underlying vector is akin to keeping state on the order of the vector. Why cant that happen in a separate data structure? Is there a more efficient way to represent ordinality other than a vector? Creating an iterator is simply tracking traversal through that structure, which I think could be done using a bloom filter to track which indices have not been traversed yet. That just leaves the traversal algorithm itself. What information would an iterator need to know to make the best decision? Could I adapt a sorting algorithm to be an iterator?
I’m asking a lot of questions because I’m a statistics guys, not an algorithms guy. Any starting point or input is much appreciated!
I haven’t looked at the code, so my two cents may be irrelevant, but it sounds like you could define a structure that borrows the vector, keeps a separate vector of indices into borrowed vector, and has a current element index.
struct SortFacadeIterator<'a, T: Ord> { data: &'a Vec<T>, indices: Vec<usize>, position: usize, }Then in new you would need to sort the original vector but instead of mutating it you would store indices of a resulting sorted elements from the original, i.e. when passed [“b”, “a”, “c”] you would create index storage of [1, 0, 2]. After that you can iterate both ways, returning an element by index:
impl<'a, T: Ord> SortFacadeIterator<'a, T> { fn current(&self) -> &T { self.data[self.indices[self.position]] } }I think, maybe sorting a vector could be done by enumerating original vector and sort_by a value, also I’m not sure you need a full ordering, but I don’t remember what a sort expects
Maybe a heap data structure is what you’re looking for. Depending on the usecase you might have to first turn an unsorted Vec into a heap (runtime in O(n), which is still faster than fully sorting it), at that point you can both insert new elements and remove the minimum element within a time in O(log n).
Wouldn’t that essentially clone all the data in the vector in the first place? I’m trying to minimize memory by having an iterator implementation rather than another presorted data structure that clones the underlying data.
You would have to either mutate the original vector or clone it, yes. If you really want to iterate through an immutable Vec with only constant memory usage, then you probably can’t get around O(n^2) runtime, but maybe there is some time-memory-tradeoff where a small memory usage can get some time reduction.
Not sure what you’re asking. If it’s about sorting without moving values of big structs around, maybe something like this?
That’s essentially where the code started, where the vector was presorted, then moved to a function to be used for a calculation. I want to have the caller be able to pass a borrow of a collection, for the purposes of this problem right now a fixed size vector, and not have to move the vector into the function. The function needs the sorted data, but doesn’t need to clone any of the data, just needs to run a calculation over it. Ideally the final implementation can a) take a borrow to a fixed size vector and b) not clone any of the underlying data in order to run its own calculations. The solution I’m toying with now is a sorted iterator, which shouldn’t clone the underlying vector’s data and should traverse the fixed size vector in a sorted order. Having an iterator whose
nextreturns sorted items from the fixed size vector would be the perfect solution to this issue.If I understand you correctly, same as above with minimal modifications.
