https://github.com/biojulia/kwaymerges.jl
Implementation of k-way merge algorithms in Julia
Science Score: 26.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
○Academic publication links
-
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (14.7%) to scientific vocabulary
Repository
Implementation of k-way merge algorithms in Julia
Basic Info
- Host: GitHub
- Owner: BioJulia
- License: mit
- Language: Julia
- Default Branch: master
- Size: 22.5 KB
Statistics
- Stars: 4
- Watchers: 1
- Forks: 0
- Open Issues: 2
- Releases: 1
Metadata Files
README.md
KWayMerges.jl
Implementation of k-way merge.
This package exports the function kway_merge.
It constructs a KWayMerger - a stateful, lazy iterator of the elements in an iterator of iterators.
The elements of the inner iterators will be yielded in order, as specified by the optional ordering (default: Forward).
Therefore, if the inner iterators are sorted by the order, the yielded elements of the KWayMerger is also guaranteed to be sorted.
The primary purpose of kway_merge is to efficiently merge N sorted iterables into one sorted stream.
The iterator yields @NamedTuple{from_iter::Int, value::T}, where the value field has the next element of one of the iterators, and the from_iter field contains the 1-based index of the iterator that yielded the value:
```julia julia> it = kway_merge([[2, 3], [1, 4]]);
julia> first(it) (from_iter = 2, value = 1)
julia> println(map(Tuple, it)) [(1, 2), (1, 3), (2, 4)] ```
The function peek can be used to check the next element without advancing the iterator:
```julia julia> it = kway_merge([1]);
julia> peek(it) (from_iter = 1, value = 1)
julia> first(it) (from_iter = 1, value = 1)
julia> peek(it) === nothing true ```
Documentation
This package's public functionality are the kway_merge function, the (unexported) KWayMerger type, and its Base.peek method.
See their docstrings for more details.
Performance
When merging I iterables:
* A KWayMerger allocates O(I) space upon construction
* Producing each element takes O(log(I)) time
Therefore, merging I sorted iterables with N total elements using kway_merge takes O(N * log(I)) time.
This is similar to the O(N * log(N)) time taken for comparison-based sorts.
That's no co-incidence: One can take a list with N elements, separate it into N 1-element lists, then merge them with a kway-merge. That is a variant of merge sort.
However, compared to a comparison-based sort like quicksort, using a kway merge has the following differences: * Usually, we have I << N, and therefore, kway merge is usually faster. * For large I, quicksort is faster in practice because its overhead per element is smaller.
Note that Julia uses radix sort for integers, which sorts in O(N), and therefore usually beats a k-way merge.
Contributing
We appreciate contributions from users including reporting bugs, fixing issues, improving performance and adding new fea oftentures.
Take a look at the contributing files detailed contributor and maintainer guidelines, and code of conduct.
Questions?
If you have a question about contributing or using BioJulia software, come on over and chat to us on the Julia Slack workspace, or you can try the Bio category of the Julia discourse site.
Owner
- Name: BioJulia
- Login: BioJulia
- Kind: organization
- Website: https://biojulia.dev
- Repositories: 79
- Profile: https://github.com/BioJulia
Bioinformatics and Computational Biology in Julia
GitHub Events
Total
- Create event: 4
- Commit comment event: 4
- Release event: 1
- Issues event: 1
- Watch event: 1
- Delete event: 2
- Issue comment event: 2
- Push event: 8
- Pull request event: 2
Last Year
- Create event: 4
- Commit comment event: 4
- Release event: 1
- Issues event: 1
- Watch event: 1
- Delete event: 2
- Issue comment event: 2
- Push event: 8
- Pull request event: 2
Committers
Last synced: 11 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Jakob Nybo Nissen | j****n@g****m | 8 |
Issues and Pull Requests
Last synced: 10 months ago
All Time
- Total issues: 2
- Total pull requests: 3
- Average time to close issues: 7 days
- Average time to close pull requests: about 5 hours
- Total issue authors: 1
- Total pull request authors: 1
- Average comments per issue: 0.5
- Average comments per pull request: 1.0
- Merged pull requests: 2
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 2
- Pull requests: 3
- Average time to close issues: 7 days
- Average time to close pull requests: about 5 hours
- Issue authors: 1
- Pull request authors: 1
- Average comments per issue: 0.5
- Average comments per pull request: 1.0
- Merged pull requests: 2
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- jakobnissen (2)
Pull Request Authors
- jakobnissen (5)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
- Total downloads: unknown
- Total dependent packages: 0
- Total dependent repositories: 0
- Total versions: 2
juliahub.com: KWayMerges
Implementation of k-way merge algorithms in Julia
- Documentation: https://docs.juliahub.com/General/KWayMerges/stable/
- License: MIT
-
Latest release: 0.2.0
published 12 months ago
Rankings
Dependencies
- actions/checkout v3 composite
- julia-actions/julia-buildpkg latest composite
- julia-actions/julia-docdeploy latest composite
- actions/checkout v3 composite
- codecov/codecov-action v4 composite
- julia-actions/julia-processcoverage latest composite
- julia-actions/julia-runtest latest composite
- julia-actions/setup-julia latest composite