c++ - How to optimize binary search of a vector? -

-

i trying implement find method on sorted vector of key value pairs. right performing slower map.find(key). theoretically should faster because vector can take better advantage of cpu caching because of contiguous memory. i'm wondering if there wrong implementation , if there way can optimize it? don't think using standard algorithm option here, because closest possible option lower_bound , incur overhead of checks have perform verify whether or not found anything. beyond that, lower_bound require me construct pair (plus wrapper put around it) give value i'm searching for, incurring more unnecessary overhead.

flatmap<key, value, comparator>::findimp(const key_type &key) {     typename vectortype::iterator lower = d_elements.begin();     typename vectortype::iterator upper = d_elements.end();     typename vectortype::iterator middle;     while(lower < upper) {         middle = lower + (upper-lower)/2;         if(d_comparator(middle->data().first, key)){             lower = middle;             ++lower;         } else if(d_comparator(key, middle->data().first)){             upper = middle;         } else {             return middle;         }     }     return d_elements.end(); }

note d_elements vector of pairs (the pairs in wrapper):

vector<flatmap_element<key, value> >  d_elements;

the wrapper holds pair data member , magic assignment shouldn't affect search:

template <class key, class value> class flatmap_element {     bsl::pair<const key, value> d_data;     ...     pair<const key, value>& data();     pair<const key, value> const& data() const; };

i know business wrapper not source of slowdown, beaucse have tested algorithm on vector or pairs without wrapper , had same performance.

any suggestions tweaks appreciated.

your version use twice m_comparator result loop whereas std::lower_bound use 1 comparaison.

so may use like: (c++03)

template <typename key, typename value, typename keycomparator> struct helper_comp {     bool operator (const std::pair<const key, value>& lhs, const key& rhs) const {         return comp(lhs.first, rhs);     }     keycomparator comp; };  template <typename key, typename value, typename keycomparator> typename std::vector<std::pair<const key, value>>::const_iterator my_find(const std::vector<std::pair<const key, value>>& v, const key& key) {     auto = std::lower_bound(v.begin(), v.end(), key, helper_comp<key, value, keycomparator>());     if (it != v.end() && it->first == key) {         return it;     }     return v.end(); }

or use lambda instead of external struct helper_comp(c++11) (https://ideone.com/snztru)


Comments

Post a Comment

Popular posts from this blog

c++ - OpenCV Error: Assertion failed <scn == 3 ::scn == 4> in unknown function, -

-
i read alot other solution still confused should mine... #include <opencv2/objdetect/objdetect.hpp> #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> #include <iostream> #include <stdio.h> using namespace std; using namespace cv; int main(int argc, const char** argv) { //create cascade classifier object used face detection cascadeclassifier face_cascade; //use haarcascade_frontalface_alt.xml library face_cascade.load("haarcascade_frontalface_alt.xml"); //setup video capture device , link first capture device videocapture capturedevice; capturedevice.open(0); //setup image files used in capture process mat captureframe; mat grayscaleframe; //create window present results namedwindow("outputcapture", 1); //create loop capture , find faces while (true) { //capture new image frame capturedevice >> captureframe; ...
Read more

php - render data via PDO::FETCH_FUNC vs loop -

-
i've been using 2 methods render data. the first one: function name($id,$name){ return '<div id="'.$id.'">'.$name.'</div>'; } echo implode($pdo->query("select id,name user")->fetchall(pdo::fetch_func,'name')); the second one: $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); foreach($users $user){ echo name($user->id,$user->name); } i don't understand how pdo::fetch_func works. tried figure out. however, not well-documented. could please explain fetch mode? , also, 1 performs better? thank you. both methods wrong , have learn how use templates , how separate business logic presentation logic. $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); tpl::assign('users', $users); is code business logic part. then in template <?php foreach $users $row): ?> <div id="<?=$...
Read more

The canvas has been tainted by cross-origin data in chrome only -

-
uncaught securityerror: failed execute 'getimagedata' on 'canvasrenderingcontext2d': canvas has been tainted cross-origin data i getting above error in chrome. code(following) works fine in mozilla. have not corss domain issue. why above error in chrome? var wheel_canvas, wheel_context, can_w, can_h, wheel_grd; var large_radius = 160; var small_radius = 120; var wheel_canvas = document.getelementbyid('wheel_canvas'); var wheel_context = wheel_canvas.getcontext('2d'); var can_w = $(wheel_canvas).width(); var can_h = $(wheel_canvas).height(); var centerx = can_w / 2, centery = can_h / 2; var wheel_grd = null; test('#ff0000'); function test(hex) { $('#clrpicker').css({'left': 210, 'top': 210 }); inverted = hexbw(hex); $('#color_val_show').val(hex); current_color_hex_val_selected = hex; $('#color_val_show').css({'color':inverted,'background':hex}); fillgradient...
Read more