5 ms·
Production algorithm tricks anyone?
For solving the problem of proportioned distribution of ads into sites at internet-scale, we had used a random number generator within a segmented number range. It was elegant and distributed synchronization and such complexities.
Any more of such elegant tricks in production software?
- NathanKP 10y ago99% of the cool, elegant "tricks" I've seen have been applications of the following computer science concepts: https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Paxos_(computer_science) https://en.wikipedia.org/wiki/Paxos_(computer_science)
- tjalfi 10y agoSPITBOL/370 is a SNOBOL4 implementation for IBM mainframes. The following Dr. Dobbs articles describe some of the tricks used in the code. Elegant is the wrong word but both of these techniques are clever hacks. http://www.drdobbs.com/cpp/misusing-floating-point-arithmetic-for-f/232300544 http://www.drdobbs.com/cpp/misusing-floating-point-arithmeti... http://www.drdobbs.com/cpp/some-programs-are-poorly-designed-on-pur/232300070 http://www.drdobbs.com/cpp/some-programs-are-poorly-designed...
- bogomipz 10y ago>"we had used a random number generator within a segmented number range." Could you describe your current implementation and its elegance?
- kartiksura 10y agoAd 1 has to be shown 30% of the traffic Ad 2 has to be shown 40% of the traffic Remaining has to be given to RTB generate a random number between 0:100 if the number is 0-30 the Ad 1 has to be shown if the number is 30-70 the Ad 1 has to be shown else RTB is to be called The servers can be now independent and no need to share the state, or have a lock based counter. For large number of requests, and with a good random number generator, you will get good results.
- packersfan0000 10y agoNot to be a hater, but that seems like by far the most obvious way to do that, right?
- kartiksura 10y agoYes. It is intuitive to some. But I never learnt it from a text book. Thats why I was curious about such other tricks.
- borplk 10y agoYeah not to be an ass but that's pretty standard. And cool too I admit.
- bogomipz 10y ago>"Yeah not to be an ass but that's pretty standard." Pretty standard in what context? Can you elaborate? Is there a name for the algorithm?
- kartiksura 10y agoIt might seem standard among some circles. And i have learnt them on the floor. But could never find a book or blog which describes some more examples. I was curious if others had any ideas to share.
- bogomipz 10y ago>"40% of the traffic Remaining has to be given to RTB" What is RTB?
- kartiksura 10y agoReal time bidding. It is used to trade ads with exchanges. When you dont have your own ads from your sales team.
- bogomipz 10y ago
- lgas 10y agoFor scaling view counters on the pages of popular videos Youtube increments the counter by N views with 1/N probability for each actual view. Or so I've been told.
- ageitgey 10y agoI've seen similar approaches used to enforce rate limit checks on APIs that get lots of traffic and are distributed amongst many different servers.
- kartiksura 10y agoThis is really neat. You need to take only 1/N of the locks. Maybe the N can be started small and changed gradually as the views increase.
- shaftway 10y agoI've always been a fan of the Fast Inverse Square Root hack. float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y; } https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
- anon263626 10y agoThere's a bunch in Hacker's Delight. One that comes to mind is XOR-swap. It's cute, but it's likely slower than using a temp var. Some of the integer population count algos (1's counting) are clever. Also, original Doom source has some neat tricks.
- kartiksura 10y agoAah finally a good clue about reading material. Thanks a ton.
- Arcten 10y agoUsing the HyperLogLog algorithm to estimate the number of unique elements in huge datasets: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali... Very cool algorithm used in (among other things) redis.