| --- Log opened Mon Feb 17 00:00:07 2014 |
| 00:21 | | Derakon[AFK] is now known as Derakon |
| 00:22 | | himi [fow035@Nightstar-q9amk4.ffp.csiro.au] has joined #code |
| 00:22 | | mode/#code [+o himi] by ChanServ |
| 00:58 | | You're now known as TheWatcher[T-2] |
| 01:07 | | You're now known as TheWatcher[zZzZ] |
| 01:25 | | Derakon [Derakon@Nightstar-cb57nb.ca.comcast.net] has quit [Client exited] |
| 03:27 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has quit [[NS] Quit: Program Shutting down] |
| 04:06 | | Turaiel[Offline] is now known as Turaiel |
| 04:39 | | Kindamoody[zZz] is now known as Kindamoody |
| 04:46 | | celticminstrel [celticminst@Nightstar-mhtogh.dsl.bell.ca] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 04:57 | | Derakon [Derakon@Nightstar-cb57nb.ca.comcast.net] has joined #code |
| 04:58 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 05:13 | | Derakon is now known as Derakon[AFK] |
| 05:16 | | Harlow [harlow@Nightstar-9hnfdm.il.comcast.net] has joined #code |
| 06:09 | | RichyB [RichyB@Nightstar-c6u.vd5.170.83.IP] has quit [[NS] Quit: Gone.] |
| 06:13 | | RichyB [RichyB@Nightstar-c6u.vd5.170.83.IP] has joined #code |
| 06:27 | | AverageJoe [evil1@Nightstar-fb1kt4.ph.cox.net] has joined #code |
| 06:32 | | Kindamoody is now known as Kindamoody|afk |
| 06:34 | | himi [fow035@Nightstar-q9amk4.ffp.csiro.au] has quit [Ping timeout: 121 seconds] |
| 06:59 | | Harlow [harlow@Nightstar-9hnfdm.il.comcast.net] has quit [[NS] Quit: BED] |
| 07:10 | | Kindamoody|afk is now known as Kindamoody |
| 07:18 | | Thaqui [Thaqui@Nightstar-h0v.euv.99.121.IP] has joined #code |
| 07:58 | | Erik [8f610223@Nightstar-fsq7h2.mibbit.com] has joined #code |
| 07:59 | | AverageJoe [evil1@Nightstar-fb1kt4.ph.cox.net] has quit [[NS] Quit: Leaving] |
| 08:07 | | Turaiel is now known as Turaiel[Offline] |
| 08:30 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 08:30 | | mode/#code [+o himi] by ChanServ |
| 08:42 | | Kindamoody is now known as Kindamoody|out |
| 09:31 | | You're now known as TheWatcher |
| 10:01 | | Red_Queen [Z@Nightstar-484uip.cust.comxnet.dk] has joined #code |
| 10:05 | | Thaqui [Thaqui@Nightstar-h0v.euv.99.121.IP] has quit [[NS] Quit: Leaving] |
| 10:25 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has joined #code |
| 12:44 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 12:50 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has joined #code |
| 13:30 | | Reiv_ [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has quit [Ping timeout: 121 seconds] |
| 14:41 | | Erik [8f610223@Nightstar-fsq7h2.mibbit.com] has quit [[NS] Quit: http://www.mibbit.com ajax IRC Client] |
| 14:56 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 15:02 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection reset by peer] |
| 15:08 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has joined #code |
| 15:26 | | celticminstrel [celticminst@Nightstar-mhtogh.dsl.bell.ca] has joined #code |
| 15:26 | | mode/#code [+o celticminstrel] by ChanServ |
| 15:56 | | Red_Queen [Z@Nightstar-484uip.cust.comxnet.dk] has quit [[NS] Quit: If the world didn't suck, we'd all fall off.] |
| 16:03 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 16:16 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 16:16 | | mode/#code [+o himi] by ChanServ |
| 16:33 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 16:38 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has joined #code |
| 17:20 | | Syka [the@Nightstar-qhd.0e5.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 17:32 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 17:32 | | Turaiel[Offline] is now known as Turaiel |
| 17:47 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 17:47 | | mode/#code [+o himi] by ChanServ |
| 18:09 | | Turaiel is now known as Turaiel[Offline] |
| 18:14 | | Derakon[AFK] is now known as Derakon |
| 18:18 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has joined #code |
| 18:31 | <&ToxicFrog> | What is a good data structure for a set of tens to hundreds of millions of 20-byte values? Intended use is adding individual items to the set, then testing individual items for set membership. |
| 18:32 | < jeroud> | ToxicFrog: Bloom filter? |
| 18:32 | <&ToxicFrog> | We were actually just talking about that, yeah. |
| 18:32 | <&ToxicFrog> | Ideally we'd like something deterministic but a bloom filter remains plan B. |
| 18:34 | < jeroud> | Is a bloom filter not deterministic? |
| 18:34 | <&ToxicFrog> | Nope. |
| 18:34 | <&ToxicFrog> | It can have false positives (i.e. an item reports as present in the set when it actually isn't) |
| 18:34 | <&ToxicFrog> | That is actually acceptable for this usage, although false negatives are not. |
| 18:35 | < jeroud> | Ah. |
| 18:36 | < jeroud> | Bloom filters don't have false negatives. |
| 18:36 | <&ToxicFrog> | Yes, I know. |
| 18:36 | <&ToxicFrog> | That's why they're plan B. |
| 18:37 | < ErikMesoy> | "Bloom filter" always makes me imagine a photoshop filter that adds illumination. |
| 18:41 | <@Azash> | ToxicFrog: What about a normal bucketed hash? |
| 18:43 | <&ToxicFrog> | Azash: I'd like this to take <1GB of memory. |
| 18:44 | <&ToxicFrog> | Looks like a bloom filter accepting a 1% FP rate would be around ~128MB for 100M items, which would be fantastic. |
| 18:45 | <@Azash> | Not bad at all |
| 18:45 | <&ToxicFrog> | And of course it's tunable |
| 18:47 | | * Azash starts wondering about ways to modify values and shove them into a secondary filter to lower the FP rate from p to p^2 |
| 19:06 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 19:08 | | Turaiel[Offline] is now known as Turaiel |
| 19:12 | <&ToxicFrog> | Azash: I think you're better off just adding more bits to the filte.r |
| 19:13 | <@Azash> | Probably, but that doesn't make it less of an interesting though |
| 19:19 | <&ToxicFrog> | That said, if you want stacked filters, that's trivial - initialize another filter with the same parameters except for different hash functions. |
| 19:21 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 19:21 | | mode/#code [+o himi] by ChanServ |
| 19:25 | | Turaiel is now known as Turaiel[Offline] |
| 20:41 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 20:51 | | Kindamoody|out is now known as Kindamoody |
| 20:56 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 20:56 | | mode/#code [+o himi] by ChanServ |
| 20:58 | <&McMartin> | ToxicFrog: Union-Find |
| 21:03 | < AnnoDomini> | I wonder: Does C++ allow you to attempt to call an object property that doesn't exist? |
| 21:03 | < AnnoDomini> | When using a pointer, that is. |
| 21:05 | <&ToxicFrog> | McMartin: Union-Find? |
| 21:05 | <&ToxicFrog> | AnnoDomini: no, it won't typecheck. |
| 21:06 | < AnnoDomini> | Meaning yes, it will allow me to attempt it and fail? |
| 21:07 | | Red_Queen [Z@Nightstar-484uip.cust.comxnet.dk] has joined #code |
| 21:07 | <&McMartin> | ToxicFrog: That's what CLR calls it |
| 21:07 | <&McMartin> | Let me see if I can find a summary |
| 21:07 | <&McMartin> | But it's O(inverse Ackermann) in complexity |
| 21:08 | <&McMartin> | http://en.wikipedia.org/wiki/Union-find_algorithm |
| 21:08 | <&McMartin> | Specifically union-by-rank and path-compression |
| 21:20 | <&ToxicFrog> | The problem I'm trying to solve is not time but space complexity; 100M sha1 hashes is Large. |
| 21:21 | <&McMartin> | Binary decision diagrams, then. |
| 21:21 | <&McMartin> | That said, to the degree that BDDs help, SHA1 is a bad algorithm~ |
| 21:24 | <&ToxicFrog> | So, the root problem I am trying to solve is "I have a git repo containing tens of millions of objects and a few hundred gigabytes of data. git gc" |
| 21:24 | <&ToxicFrog> | git-gc(1), of course, dies messile |
| 21:25 | <@Tamber> | Fire. Lots of fire. |
| 21:27 | < Shiz> | AnnoDomini: it will fail. |
| 21:27 | < Shiz> | at compile time |
| 21:28 | <&ToxicFrog> | AnnoDomini: no, I mean it will not pass type checking. It will not compile. |
| 21:28 | < AnnoDomini> | Right. |
| 21:29 | | Kindamoody is now known as Kindamoody[zZz] |
| 21:29 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 21:32 | <&ToxicFrog> | McMartin: anyways, this means I don't get the choose the hash algorithm - objects are identified by sha1 hash. Given (the ability to get) the set of all reachable object hashes and the set of all object hashes, I need to get the set of unreachable object hashes and then use that to guide a repack. |
| 21:46 | < AnnoDomini> | Anyone know if there's a working Nintendo 3DS emulator yet? |
| 21:58 | < Shiz> | tons |
| 21:58 | < Shiz> | oh, 3DS |
| 21:58 | < Shiz> | well, I know one exists |
| 21:58 | < Shiz> | but I also know you probably won't be able to get access to it |
| 22:01 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has joined #code |
| 22:02 | < AnnoDomini> | Explain. |
| 22:03 | < Shiz> | part of the official 3DS SDK |
| 22:04 | < AnnoDomini> | Pff. Heh. |
| 22:09 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 22:18 | | Red_Queen [Z@Nightstar-484uip.cust.comxnet.dk] has quit [Ping timeout: 121 seconds] |
| 22:24 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has joined #code |
| 22:43 | | ErikMesoy is now known as ErikMesoy|sleep |
| 22:55 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 23:13 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has quit [Ping timeout: 121 seconds] |
| 23:32 | | Syka [the@Nightstar-ils.cjd.159.1.IP] has joined #code |
| 23:44 | | Derakon [Derakon@Nightstar-cb57nb.ca.comcast.net] has quit [Client exited] |
| --- Log closed Tue Feb 18 00:00:22 2014 |