vector-search
Comparing approaches for searching an element in a vector.
Science Score: 41.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
✓Academic publication links
Links to: zenodo.org -
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (4.2%) to scientific vocabulary
Repository
Comparing approaches for searching an element in a vector.
Basic Info
Statistics
- Stars: 0
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 1
Metadata Files
README.md
Comparing approaches for searching an element in a vector.
Comparing Linear vs Binary search
This experiment (compare-linear-vs-binary) was for finding when is linear
search faster than binary search. Both approaches were attempted on a no.
of elements ranging from 10 to 1000. For each no. of elements a random
int list of that size was generated, and sorted. 5 million random numbers
were searched in the list with each approach, and the total time taken was
measured.
Binary search is faster than linear search when the sorted list has
atleast 120 elements. Unfortunately, performing a hybrid search (linear
search for few elements, and binary search for many elements) does not help.
Maybe this is because of the added conditional switch? A naive implementation
of hybrid search also performs worse, indicating std::lower_bound has some
additional optimizations. Results for hybrid search are not included here.
Owner
- Name: puzzlef
- Login: puzzlef
- Kind: organization
- Website: https://puzzlef.github.io/
- Repositories: 10
- Profile: https://github.com/puzzlef
A summary of experiments.
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: Sahu
given-names: Subhajit
orcid: https://orcid.org/0000-0001-5140-6578
title: "puzzlef/search-linear-vs-binary: Comparing when is linear search faster than binary search"
version: 1.0.0
doi: 10.5281/zenodo.6717443
date-released: 2022-06-24
GitHub Events
Total
- Push event: 1
Last Year
- Push event: 1