| --- Log opened Fri Jul 10 00:00:25 2020 |
| 01:08 | | * McMartin looks at some of his old data structure code |
| 01:08 | <&McMartin> | There is a lot of copypasta here |
| 01:08 | <&McMartin> | I think this is a case where An Additional Layer Of Indirection saves the day |
| 01:09 | <&McMartin> | But also ew ick |
| 01:13 | | catalyst_ [catalyst@Nightstar-k4s6a1.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 01:17 | | Kindamoody is now known as Kindamoody[zZz] |
| 01:37 | | catalyst [catalyst@Nightstar-qpiu53.dab.02.net] has joined #code |
| 01:42 | | catalyst [catalyst@Nightstar-qpiu53.dab.02.net] has quit [[NS] Quit: -a- IRC for Android 2.1.56] |
| 02:07 | | bluefoxx [fuzzylombax@Nightstar-gmbj85.vs.shawcable.net] has quit [Ping timeout: 121 seconds] |
| 02:12 | | Pinkhair [user1@Nightstar-g7hdo5.dyn.optonline.net] has quit [Connection closed] |
| 02:12 | | bluefoxx [fuzzylombax@Nightstar-gmbj85.vs.shawcable.net] has joined #code |
| 02:13 | | Pink [user1@Nightstar-g7hdo5.dyn.optonline.net] has joined #code |
| 02:25 | <~Vornicus> | something something corner cases. guess it's not too bad; if I just kind of ... miss in the two directions then it's just "oh I must be on the corner" and done. |
| 02:25 | <~Vornicus> | also for some godforsaken reason I was just watching someone livestream manual decompression of a pokemon red sprite |
| 02:28 | <~Vornicus> | -- and writing his data into excel to do delta decoding automatically... https://imgur.com/2UntRUw |
| 02:33 | | Degi [Degi@Nightstar-bdfaat.dyn.telefonica.de] has quit [Ping timeout: 122 seconds] |
| 02:35 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 02:43 | <&McMartin> | Whee, I learned a new data structure |
| 02:43 | <&McMartin> | Not a useful one, but a cute one |
| 02:44 | <&McMartin> | "Treaps", which are basically a red-black tree that rolls dice instead of doing the whole red-black tree-ing stuff. |
| 02:45 | | Degi [Degi@Nightstar-h7q3sn.dyn.telefonica.de] has joined #code |
| 02:59 | <&Reiver> | ... what does rolling the dice do |
| 03:14 | <&McMartin> | Hm. |
| 03:14 | <&McMartin> | I probably need to start by explaining binary search trees? |
| 03:15 | <&McMartin> | The idea here is that you have a data blob where you can check if something's in it by playing 20 questions with it; "is this value in the set? Do I need to look amongst smaller or larger numbers?" |
| 03:15 | <&McMartin> | And then this lets you search 1000 elements with about 10 questions instead of about 1000, if you're looking for something. |
| 03:16 | <&McMartin> | But: that only works if it's possible for you to start in the middle, and the most direct way of doing this has no real mechanism for preserving that |
| 03:16 | <&McMartin> | And in particular, if you tell it about the things it should know about in order, that's the worst result and you're in 1,000 questions land. |
| 03:17 | <&McMartin> | So there are a variety of schemes for making it fork as frequently as possible, which makes the number of questions be more like "the number of digits it takes to write out the number of elements" rather than "the number of elements" |
| 03:17 | <&McMartin> | Most have various guarantees of how far off ideal they can be, balanced by how expensive they are to deal with at run-time, or how hard they are to actually make work |
| 03:17 | <&McMartin> | This one makes no *particular* guarantees, because it's doing that reforking, essentially, randomly. |
| 03:18 | <&McMartin> | Which means *in practice* it's probably going to be pretty OK, and it is quite a bit easier to actually write. |
| 03:18 | <&McMartin> | With me so far? |
| 03:19 | <&McMartin> | (The next step is to actuall explain what it means to "do it randomly") |
| 03:25 | <&McMartin> | OK, it's been five minutes. The core trick is that in addition to the data that you actually want to query, which is essentially kept sorted as you add or remove elements... |
| 03:25 | <&McMartin> | ... there is another set of data, of equal size, and completely random, organized in a way parallel to the main stuff that provides stronger guarantees about the "smaller" and "larger" sides of any point being roughly balanced. |
| 03:26 | <&McMartin> | Said data structure is called a "heap" (no relationship to the region of memory called "the heap" - we've been bad at naming things for almost a century now) and thus, it's a tree-heap, or treap. |
| 03:46 | | VirusJTG [VirusJTG@Nightstar-42s.jso.104.208.IP] has quit [Connection closed] |
| 03:46 | | VirusJTG [VirusJTG@Nightstar-42s.jso.104.208.IP] has joined #code |
| 03:46 | | mode/#code [+ao VirusJTG VirusJTG] by ChanServ |
| 05:31 | | Pink [user1@Nightstar-g7hdo5.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 07:34 | | Vorntastic [uid293981@Nightstar-h2b233.irccloud.com] has joined #code |
| 07:34 | | mode/#code [+qo Vorntastic Vorntastic] by ChanServ |
| 08:30 | | Kindamoody[zZz] is now known as Kindamoody |
| 09:42 | | Emmy [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has joined #code |
| 11:07 | | Kindamoody is now known as Kindamoody|afk |
| 12:21 | | VirusJTG [VirusJTG@Nightstar-42s.jso.104.208.IP] has quit [[NS] Quit: Leaving] |
| 13:17 | <@celmin|work> | Isn't a heap just a binary tree flattened out into an array? |
| 13:18 | | celmin|work is now known as celticminstrel |
| 13:34 | <~Vorntastic> | Correct that it is a binary tree, incorrect that it is not a binary search tree |
| 13:35 | <~Vorntastic> | Red black and other such trees are for searching, and heaps are terrible at that |
| 13:35 | <~Vorntastic> | (because the guarantee you have in a heap is that both children are higher than the parent) |
| 14:02 | <@sshine> | it's been soo long since a binary heap was the best choice of data structure for me. |
| 14:03 | <@sshine> | I actually used one in the last year. at my old job I found a good use for a priority queue, but the best version on CPAN (Perl) was old and insufficient; so I had to fork and alter it. |
| 14:05 | <@TheWatcher> | I trust you released the new fork on CPAN?~ |
| 14:15 | <@sshine> | nah, I didn't feel like it. |
| 14:16 | <@sshine> | Perl is a dying language. |
| 14:55 | <@TheWatcher> | Bah. That is not dead which can eternal lie. |
| 15:08 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 15:08 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 17:05 | | macdjord|slep [macdjord@Nightstar-rslo4b.mc.videotron.ca] has quit [Ping timeout: 121 seconds] |
| 17:06 | | macdjord [macdjord@Nightstar-rslo4b.mc.videotron.ca] has joined #code |
| 17:06 | | mode/#code [+o macdjord] by ChanServ |
| 17:12 | | macdjord [macdjord@Nightstar-rslo4b.mc.videotron.ca] has quit [Ping timeout: 121 seconds] |
| 17:14 | | macdjord [macdjord@Nightstar-rslo4b.mc.videotron.ca] has joined #code |
| 17:14 | | mode/#code [+o macdjord] by ChanServ |
| 17:14 | | Vorntastic [uid293981@Nightstar-h2b233.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 17:15 | | mac [macdjord@Nightstar-rslo4b.mc.videotron.ca] has joined #code |
| 17:15 | | mode/#code [+o mac] by ChanServ |
| 17:16 | | macdjord|slep [macdjord@Nightstar-rslo4b.mc.videotron.ca] has joined #code |
| 17:16 | | mode/#code [+o macdjord|slep] by ChanServ |
| 17:18 | | macdjord [macdjord@Nightstar-rslo4b.mc.videotron.ca] has quit [Operation timed out] |
| 17:19 | | mac [macdjord@Nightstar-rslo4b.mc.videotron.ca] has quit [Ping timeout: 121 seconds] |
| 17:24 | | macdjord|slep [macdjord@Nightstar-rslo4b.mc.videotron.ca] has quit [Ping timeout: 121 seconds] |
| 18:57 | | Kindamoody|afk is now known as Kindamoody |
| 20:28 | <&McMartin> | TheWatcher: Does this make Perl 7 the Stars Becoming Right |
| 20:29 | <&McMartin> | And yeah, heap is my go-to data structure for priority queues with deduplication, which comes up... a couple times a year, I guess. |
| 20:29 | <&McMartin> | Most recently, it's when I learned Python has Proper Batteries Included, with a heapq module. |
| 21:45 | | Reiv [NSkiwiirc@Nightstar-ih0uis.global-gateway.net.nz] has quit [[NS] Quit: http://www.kiwiirc.com/ - A hand crafted IRC client] |
| 21:49 | | Reiv [NSkiwiirc@Nightstar-ih0uis.global-gateway.net.nz] has joined #code |
| 21:49 | | mode/#code [+o Reiv] by ChanServ |
| 23:54 | | Emmy [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has quit [Ping timeout: 121 seconds] |
| --- Log closed Sat Jul 11 00:00:27 2020 |