Detailed description
Description
I would like to contribute an implementation of the Reservoir Sampling algorithm to this repository.
Motivation
Reservoir Sampling is a randomized algorithm that allows selecting k uniformly random elements from a stream or dataset of unknown or very large size while using only O(k) additional memory.
It is widely used in streaming systems, online algorithms, and large-scale data processing. Adding this implementation would provide learners with another useful randomized algorithm.
Proposed Contribution
I plan to:
- Implement Reservoir Sampling in modern C++.
- Add clear documentation explaining the algorithm.
- Include time and space complexity analysis.
- Add self-tests using
assert.
- Follow the project's coding style and contribution guidelines.
I would be happy to work on this contribution if it aligns with the repository's goals.
Thank you!
Context
I searched the repository, open issues, and open pull requests but could not find an implementation of Reservoir Sampling. Since the repository aims to provide educational implementations of algorithms, I believe adding this algorithm would be a useful contribution for learners interested in randomized algorithms and streaming techniques.
Possible implementation
I plan to add a new C++ implementation of the Reservoir Sampling algorithm that will include:
A well-documented implementation using modern C++.
Explanation of the algorithm.
Time and space complexity analysis.
Self-tests using assert to verify correctness.
Compliance with the repository's coding style and contribution guidelines.
Additional information
Time Complexity: O(n)
Space Complexity: O(k)
The implementation will support selecting k random elements from an input sequence while ensuring that every element has an equal probability of being included in the final sample.
Detailed description
Description
I would like to contribute an implementation of the Reservoir Sampling algorithm to this repository.
Motivation
Reservoir Sampling is a randomized algorithm that allows selecting k uniformly random elements from a stream or dataset of unknown or very large size while using only O(k) additional memory.
It is widely used in streaming systems, online algorithms, and large-scale data processing. Adding this implementation would provide learners with another useful randomized algorithm.
Proposed Contribution
I plan to:
assert.I would be happy to work on this contribution if it aligns with the repository's goals.
Thank you!
Context
I searched the repository, open issues, and open pull requests but could not find an implementation of Reservoir Sampling. Since the repository aims to provide educational implementations of algorithms, I believe adding this algorithm would be a useful contribution for learners interested in randomized algorithms and streaming techniques.
Possible implementation
I plan to add a new C++ implementation of the Reservoir Sampling algorithm that will include:
A well-documented implementation using modern C++.
Explanation of the algorithm.
Time and space complexity analysis.
Self-tests using assert to verify correctness.
Compliance with the repository's coding style and contribution guidelines.
Additional information
Time Complexity: O(n)
Space Complexity: O(k)
The implementation will support selecting k random elements from an input sequence while ensuring that every element has an equal probability of being included in the final sample.