Comments (7)
So this begs the question, when do we know it's sorted? We could sort it every time the method is called. But probably, we'd want to have a variable in array_c called "is_sorted" that is only ever set to true when the array_sort() is called, and set to false when any alteration to the array is made, yeah?
from collections-c.
Yeah, sorting on each search is way worse that just doing a linear search. We definetly want to just mark the array when it's sorted.
I think it's best to implement bsearch as an internal optimization instead of a function that the user can call. For example if the user calls something like array_index_of
, it can use bsearch internally if the array is marked as sorted instead of a linear search to speed up the search.
from collections-c.
Bsearch won't work in that instance, because bsearch only returns if a given item is in the array, not the first index as "index_of" normally returns. We could then just go backwards till we get first item, but then that's basically the same as linear search.
from collections-c.
There's no need to use the libc bsearch. It's trivial to implement a bsearch to return the index of the matching element.
from collections-c.
I mean the bsearch algorithm, not just the libc implementation, isn't guaranteed to return the first element in a sorted array which matches, just returns true if it does find it. Which means we'd then have to search for it ourselves, going backwards.
from collections-c.
I see what you mean. It doesn't match the spec of finding the first match in the sequence. But we should still be able to get better performance if we mix bsearch and linear search than with plain linear search, because on average, once we find the match through bsearch, we won't have to go too far backwards to find the first element.
from collections-c.
This idea is good, but there is only problem, we need a comparator, as i saw the array implementation, the pointer to the comparator function is not stored in the array struct, so it could be easy if there was a pointer, as if the array was sorted then we could determine if the new element when added will result the array to remain sorted or not in O(1) time, and it would be easy to do bin search, in the function array_index_of function, as bin search will req a comparator, and it would not be wise to give the comparator every time in array_index_of function while searching
from collections-c.
Related Issues (20)
- How about adding AVL or Red Black tree data structure? HOT 4
- (deque.c): inline function upper_pow_two only valid for 32 bit size_t HOT 3
- PQueue heap-overflow HOT 1
- deque_remove_at error
- cc_array_reverse() fails when element count is even HOT 1
- Implementation error in `cc_array_reverse` and `cc_deque_reverse`
- cmake configuration failed on latest MSYS2 HOT 1
- document is inaccurate about key_compare function
- Is "stdio.h" necessary? HOT 1
- The call to mem_alloc in cc_array_subarray() is unsafe
- How about adding Bloom Filter data structure? HOT 2
- cc_list.c (index > list1->size)maybe is wrong
- file: cc_list.c function:static INLINE void merge(……) HOT 1
- File: cc_list.c Function: cc_list_iter_add
- Feature Request: provide release versioning HOT 1
- RFC: Distro specific packages HOT 1
- What happened to macros such as: DEQUE_FOREACH? HOT 1
- when make occurs error HOT 1
- Segfault when calling tree_min or tree_max with a sentinel node
- Treetable: Segfault when calling get_successor_node on root if it is the greatest key HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from collections-c.