tag:blogger.com,1999:blog-2715968472735546962.post2040047568904743465..comments2023-12-14T02:21:18.222+01:00Comments on Bannalia: trivial notes on themes diverse: Traversing a linearized treeJoaquín M López Muñozhttp://www.blogger.com/profile/08579853272674211100noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-2715968472735546962.post-49995085278242941322015-07-16T18:32:28.140+02:002015-07-16T18:32:28.140+02:00One of the good data structure and algorithm quest...One of the <a href="http://java67.blogspot.com/2012/08/10-java-coding-interview-questions-and.html" rel="nofollow">good data structure and algorithm question</a> for Interviews. ThanksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-34163155097516514162015-06-29T00:40:05.963+02:002015-06-29T00:40:05.963+02:00Still, sometimes one does not care.
I would like...Still, sometimes one does not care. <br /><br />I would like to have:<br />- unsorted_begin()/unsorted_end()/unsorted() to get an unsorted view of the range with the same performance as flat set.<br />- unsorted insert operations that insert a single element in O(1), and m elements in O(m), that violate the invariants of the container. In debug mode the container can assert that the invariants are restored before any operation that needs them is performed. askdasndksadksaldjsahttps://www.blogger.com/profile/03116422407352079089noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-8771278221902454792015-06-28T03:03:09.159+02:002015-06-28T03:03:09.159+02:00I'm afraid lookup for levelorder_vector is wor...I'm afraid lookup for levelorder_vector is worse than for std::unordered_set. You can compare the following<br /> * <a href="http://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html" rel="nofollow">Cache-friendly binary search </a><br /> * <a href="http://bannalia.blogspot.com/2014/01/a-better-hash-table.html" rel="nofollow">A better hash table </a><br /><br />which are roughly comparable for MSVC. Lookup times for levelorder_vector range between 1 and 2 us, whereas for hashed sets these times are around 0.2-1 us.Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-9930150289834449062015-06-27T23:24:48.939+02:002015-06-27T23:24:48.939+02:00Here are my results https://gist.github.com/GraySh...Here are my results https://gist.github.com/GrayShade/a32a7e9ae777ccded639 .<br /><br />The distribution is Arch Linux x64, same as for the previous post. The i7 data might be noisy, as this is a laptop CPU and thermal throttling and/or Turbo Boost might have kicked in.GrayShadehttps://www.blogger.com/profile/08614811410089147863noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-54999043304244774382015-06-27T20:40:52.049+02:002015-06-27T20:40:52.049+02:00I'm betting on better performance than unorder...I'm betting on better performance than unordered_set, due to better locality of reference, and also reduced memory consumption (each bucket in unordered_set must, by inference from the interface, be a doubly linked list.)<br /><br />I think performance would be slightly worse than container_flat_set. You either have to ensure perfect balance after every insertion/removal, which has a cost, or handle unoccupied slots in iteration, which would have a cost.Björn Fahllerhttps://www.blogger.com/profile/05406277645240353094noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-57742400987921080152015-06-27T20:16:10.975+02:002015-06-27T20:16:10.975+02:00Traversing in stored order would result in exactly...Traversing in stored order would result in <i>exactly</i> the same performance as boost::container::flat_set, but the order produced would be of no particular use, and to the user would look as random as say that of a std::unordered_set. If we decided to do that, users would be better off using a std::unordered_set to begin with.Joaquín M López Muñozhttps://www.blogger.com/profile/08579853272674211100noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-17565310312840000922015-06-27T20:01:45.905+02:002015-06-27T20:01:45.905+02:00But, since you're developing a new set, not ju...But, since you're developing a new set, not just a new implementation of std::set, you're free to choose the semantics of iteration. You've chosen to iterate in sorted order, as std::set does, with more or less expected results. What if you instead allow iteration in stored order, like that of unordered_set? I bet you'd see performance very close to that of boost::container_flat_set.Björn Fahllerhttps://www.blogger.com/profile/05406277645240353094noreply@blogger.comtag:blogger.com,1999:blog-2715968472735546962.post-12320150491948448242015-06-27T18:39:11.322+02:002015-06-27T18:39:11.322+02:00Here are my results: Arch Linux 3.16 x86_64 Intel ...Here are my results: Arch Linux 3.16 x86_64 Intel Core i7 4790k @4.5GHz 16GB RAM<br /><br /><b>GCC 5.1 -Wall -pedantic -march=native -O3</b><br /><br />std::set;boost::container::flat_set;levelorder_vector<br />10000;0.0420321;0.000491979;0.014563<br />12000;0.0421156;0.000483647;0.0144815<br />14400;0.0422168;0.000480834;0.0145216<br />17280;0.0428365;0.000478953;0.0145598<br />20736;0.042634;0.000476514;0.0146061<br />24883;0.0425655;0.000478717;0.0146198<br />29859;0.0427637;0.000476505;0.0145363<br />35830;0.0426727;0.000479686;0.0145594<br />42995;0.0426188;0.000478767;0.0145501<br />51593;0.0428331;0.000526655;0.0146135<br />61910;0.0429622;0.000634265;0.0146206<br />74290;0.0430819;0.000689963;0.0146423<br />89146;0.0429906;0.000740952;0.0146404<br />106973;0.0435249;0.000741801;0.0146144<br />128365;0.0488695;0.000740464;0.0146262<br />154035;0.0592191;0.000736002;0.0145821<br />184839;0.0761611;0.000739294;0.0146332<br />221803;0.0897213;0.000738229;0.0146319<br />266159;0.0987045;0.00073572;0.0146533<br />319386;0.1116;0.000740789;0.0146558<br />383258;0.114196;0.0007371;0.0146298<br />459904;0.116994;0.000751267;0.015051<br />551879;0.115359;0.000736435;0.014638<br />662249;0.119005;0.00073486;0.0147561<br />794693;0.120097;0.000734039;0.0146452<br />953625;0.120747;0.000733416;0.0146262<br />1144343;0.118479;0.000740644;0.0146628<br />1373204;0.120768;0.000775856;0.0151388<br />1647837;0.120661;0.000772929;0.014735<br />1977396;0.121989;0.00103971;0.0148675<br />2372866;0.11892;0.00140741;0.0148716<br />2847430;0.120638;0.00166705;0.0151869<br /><br /><br /><b>Clang 3.6.1 -Wall -pedantic -march=native -O3 (GNU stdlibc++)</b><br /><br />std::set;boost::container::flat_set;levelorder_vector<br />10000;0.0417386;0.000341377;0.0168463<br />12000;0.0417399;0.000349159;0.0169027<br />14400;0.0423439;0.00031997;0.0168923<br />17280;0.0430543;0.00042511;0.0167483<br />20736;0.043264;0.000421114;0.0169363<br />24883;0.0432674;0.000421662;0.0169812<br />29859;0.0442487;0.000423517;0.0168891<br />35830;0.0432414;0.000342709;0.0168915<br />42995;0.0434866;0.000354699;0.0168187<br />51593;0.0440113;0.000402105;0.0168149<br />61910;0.0439409;0.000526146;0.0172682<br />74290;0.0435135;0.000601147;0.0169024<br />89146;0.0513623;0.000648336;0.0171129<br />106973;0.0546859;0.000718656;0.0168484<br />128365;0.0524283;0.000729523;0.0175893<br />154035;0.0764826;0.000700932;0.0171135<br />184839;0.0775115;0.000702296;0.0170045<br />221803;0.0906357;0.000701652;0.0169417<br />266159;0.0973642;0.000708999;0.0168062<br />319386;0.106956;0.000712729;0.0168548<br />383258;0.117187;0.000711961;0.016891<br />459904;0.115757;0.000710714;0.016868<br />551879;0.120767;0.000700052;0.0168105<br />662249;0.117556;0.000698999;0.0168786<br />794693;0.119222;0.000709851;0.0169199<br />953625;0.123675;0.000723752;0.0170072<br />1144343;0.120827;0.000715292;0.0168958<br />1373204;0.120367;0.000713977;0.0168934<br />1647837;0.120706;0.000758504;0.0169309<br />1977396;0.121796;0.000938414;0.0172851<br />2372866;0.120065;0.00122567;0.0174493<br />2847430;0.120253;0.00167049;0.0175354<br /><br /><br /><b>Clang 3.6.1 -Wall -pedantic -march=native -O3 (LLVM libc++)</b><br /><br />std::set;boost::container::flat_set;levelorder_vector<br />10000;0.0421094;0.000433572;0.0174907<br />12000;0.0416049;0.000429394;0.0174393<br />14400;0.0420245;0.000426524;0.0174684<br />17280;0.0436509;0.000332382;0.0175928<br />20736;0.0440515;0.000329182;0.0173394<br />24883;0.044052;0.000342822;0.0174632<br />29859;0.0438997;0.000341482;0.017644<br />35830;0.0442544;0.000425812;0.0178497<br />42995;0.0446459;0.000515587;0.0178085<br />51593;0.0441517;0.000483189;0.0177848<br />61910;0.044744;0.000567786;0.0178402<br />74290;0.044896;0.000601651;0.0176016<br />89146;0.0430186;0.000694245;0.017695<br />106973;0.0455896;0.000706889;0.0177571<br />128365;0.0526248;0.000692947;0.0175568<br />154035;0.0882242;0.000721327;0.0176997<br />184839;0.107886;0.000725102;0.017628<br />221803;0.122777;0.000719787;0.017623<br />266159;0.141874;0.000704827;0.0176322<br />319386;0.139417;0.00071619;0.0180853<br />383258;0.145941;0.000704596;0.0176367<br />459904;0.142815;0.000704553;0.0176681<br />551879;0.156851;0.000715048;0.0177817<br />662249;0.145418;0.000730398;0.0177499<br />794693;0.147788;0.000712339;0.0178183<br />953625;0.147059;0.000716288;0.0178217<br />1144343;0.157357;0.000704795;0.017893<br />1373204;0.152407;0.000739034;0.0187936<br />1647837;0.150415;0.000724018;0.0179466<br />1977396;0.151268;0.000907862;0.0180083<br />2372866;0.157685;0.00122255;0.0181203<br />2847430;0.148503;0.00171368;0.018334<br />Anonymoushttps://www.blogger.com/profile/05885986452155138099noreply@blogger.com