| --- Log opened Mon Dec 27 00:00:15 2010 |
| 00:08 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 00:09 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 00:17 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Client closed the connection] |
| 00:17 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 00:17 | | mode/#code [+o Attilla] by Reiver |
| 00:26 | | celticminstrel [celticminst@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 00:31 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Connection closed] |
| 00:31 | | SmithKurosaki [smith@9FC3E4.1754D9.7F5AF8.2FBA23] has quit [Ping timeout: 121 seconds] |
| 00:35 | | Derakon[AFK] is now known as Derakon |
| 00:35 | <@Derakon> | Cookies made. |
| 00:41 | <@McMartin> | \o/ |
| 00:42 | | * Rhamphoryncus steals Derakon's cookies |
| 00:43 | <@Derakon> | They haven't cooled yet... |
| 00:43 | <@Derakon> | So, enjoy your melted chocolate layer, I guess. |
| 00:44 | | celticminstrel [celticminst@Nightstar-f8b608eb.cable.rogers.com] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 00:46 | < Rhamphoryncus> | Chocolate? |
| 00:46 | | * Rhamphoryncus gives them back |
| 00:46 | <@Derakon> | This is what you get for not looking at what you steal. |
| 00:46 | <@Derakon> | Also I see you're one of the rare few who doesn't like the god-candy. Why not? |
| 00:46 | <@McMartin> | But it's shiny! |
| 00:47 | <@McMartin> | AND |
| 00:47 | < Rhamphoryncus> | I had the element of surprise. I would have been a fool not to use it |
| 00:47 | <@McMartin> | It's not nailed down. |
| 00:47 | <@McMartin> | Taking it is mandatory. |
| 00:47 | <@McMartin> | We'll need it three screens later to solve a puzzle! |
| 00:47 | < Rhamphoryncus> | I dunno why not. I liked it as a kid, but at some point as a teenager I stopped being able to stomach them |
| 00:47 | <@Derakon> | Tried dark choc? |
| 00:47 | < Rhamphoryncus> | Yes. Even the smell of chocolate gets to me |
| 00:47 | <@Derakon> | Milk chocolate can be pretty nasty stuff, but the dark is nice. |
| 00:47 | <@Derakon> | Hunh. |
| 00:48 | <@Derakon> | Just one of those things, then. |
| 00:48 | < Rhamphoryncus> | I might be unable to digest something in it. Or I overdosed when I was sick and my brain associated the two |
| 00:48 | <@McMartin> | I've started running into it. |
| 00:48 | <@McMartin> | (Also, god-food, not god-candy~) |
| 00:48 | <@Derakon> | Heh. |
| 00:49 | <@McMartin> | (Sadly, when declined, it turns into "god-smells-like-male-goats") |
| 00:49 | <@McMartin> | (Curse you, Greek!) |
| 00:49 | <@Derakon> | ...? |
| 00:50 | <@McMartin> | "theobromine" is a diferent version of theobroma/theobrosia - food of the gods. |
| 00:50 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 00:50 | <@McMartin> | "Bromine", the element, is named "stuff that smells like male goats" |
| 00:50 | <@Derakon> | Heh. |
| 00:50 | <@Derakon> | Okaiy. |
| 00:50 | <@Derakon> | Er, okay. |
| 00:50 | < Namegduf> | XD |
| 00:51 | <@McMartin> | Meanwhile, and in not entirely unrelated news, my occasional use of the "Bromide" handle is more "long, boring story that goes nowhere and can be used as a sedative"~ |
| 00:52 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 00:52 | | mode/#code [+o Attilla] by Reiver |
| 01:05 | <@Derakon> | Ah ha. Bisqwit of TASVideos found the bug that was keeping this from being proper Conway life. |
| 01:05 | <@Derakon> | The copy of the grid I was using to compute the next step was actually the current grid. |
| 01:05 | <@Derakon> | bar = list(foo) only works properly if foo is one-dimensional. |
| 01:06 | <@Derakon> | Otherwise you get a copy of the list of references to lists that foo is. |
| 01:07 | <@McMartin> | "This"? |
| 01:07 | <@McMartin> | Also, may I note that it's awesome that you're using the TASVideos guys to test your cellular automata~ |
| 01:08 | <@Derakon> | Ehh, I just made a thread in the off-topic forum, and Bisqwit's a total coding geek. |
| 01:08 | <@Derakon> | "This" is my half-hour attempt to replicate Conway's Game of Life in Python, because I was bored. |
| 01:08 | <@Derakon> | Ended up taking rather longer because the cellular automata I got behaved much more interestingly~ |
| 01:09 | <@Derakon> | Here's the code (Python/Pygame): http://paste.ubuntu.com/547818/ |
| 01:10 | <@McMartin> | I'm actually more of a fan of the Cyclic Cellular Automaton. |
| 01:10 | <@McMartin> | I'm not sure I have a handy copy of it though |
| 01:10 | | * McMartin did a 50-line version of it in C/SDL at one point to test out a new IDE. |
| 01:32 | | Derakon is now known as Derakon[AFK] |
| 02:09 | | cpux is now known as cpux[snowman] |
| 02:22 | | Derakon[AFK] [Derakon@Nightstar-e3bda6c6.ca.comcast.net] has quit [[NS] Quit: This computer has gone to sleep] |
| 02:37 | | Derakon[AFK] [Derakon@Nightstar-e3bda6c6.ca.comcast.net] has joined #code |
| 03:11 | | cpux[snowman] is now known as cpux[SuxAtSSF4] |
| 03:13 | | Taki^ [Taki@Nightstar-0816732d.consolidated.net] has joined #code |
| 03:56 | | Derakon[AFK] is now known as Derakon |
| 04:42 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 04:43 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 04:59 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 04:59 | | mode/#code [+o Attilla] by Reiver |
| 04:59 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 05:07 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 05:10 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 05:10 | | mode/#code [+o Attilla] by Reiver |
| 05:15 | | Derakon [Derakon@Nightstar-e3bda6c6.ca.comcast.net] has quit [[NS] Quit: Leaving] |
| 05:35 | | Kindamoody is now known as Kindamoody[zZz] |
| 05:47 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 05:48 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 05:48 | | mode/#code [+o Attilla] by Reiver |
| 05:55 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 05:56 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 05:56 | | mode/#code [+o Attilla] by Reiver |
| 06:00 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 06:03 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 06:03 | | mode/#code [+o Attilla] by Reiver |
| 06:05 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 06:08 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 06:52 | | Serah [Stalker@26ECB6.A4B64C.298B52.D80DA0] has quit [Ping timeout: 121 seconds] |
| 07:18 | | kwsn [lets_go_ave@4CA975.91A3EF.86948D.DEDAA8] has quit [Ping timeout: 121 seconds] |
| 07:52 | | Serah [Stalker@3A600C.A966FF.5BF32D.8E7ABA] has joined #code |
| 08:20 | | Anno[Laptop] [annodomini@Nightstar-4e919274.adsl.tpnet.pl] has joined #code |
| 08:42 | | Serah [Stalker@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
| 09:20 | < simon_> | does anyone here know something about compressing hashtables or search trees while preserving some operations? |
| 09:24 | <@Vornicus> | What operations? |
| 09:24 | < simon_> | well, preferrably most. :) most importantly searching, but insertion, too. |
| 09:25 | <@Vornicus> | Hash tables often can't really be "compressed" because you have to trade off between the size of the table itself (memory overhead) and the number of in-bin comparisons you have (processing overhead) |
| 09:25 | < simon_> | yeah |
| 09:25 | < simon_> | I'd go with a tree myself. only reason to go with a hash is because of the O(1) lookups. |
| 09:25 | <@Vornicus> | Search trees can be rejiggered to have maximum density or optimal add/delete balance. |
| 09:26 | <@Vornicus> | Except they're not /really/ O(1) lookups if your table is too small. |
| 09:26 | < simon_> | Vornicus, I'm thinking of memory need. |
| 09:26 | < simon_> | Vornicus, for a well-balanced one, I mean. I suppose, depending on the keys, you could do some pre-analysis and make a good hash function, right? |
| 09:27 | <@Vornicus> | Well. ...sort of, but hash functions are Really Hard. |
| 09:28 | < simon_> | what do you mean? |
| 09:28 | <@Vornicus> | Once you have a hash function there's not that much you can /do/ with it to change the way it lines up. |
| 09:28 | < simon_> | the ones I looked at in CLRS were all remainder-based. |
| 09:28 | < simon_> | ahh |
| 09:28 | < simon_> | yeah |
| 09:29 | < simon_> | I can't even think of how I would compress a hashtable, so in that sense, a tree is probably better. :) |
| 09:30 | <@Vornicus> | So you generally go with one of the Known Good hash functions, you know, the ones that Very Smart People have spent long hours improving their usefulness and efficiency. |
| 09:31 | < simon_> | come to think of it, I don't even know how a hash function in an actual compression library looks like. |
| 09:31 | <@Vornicus> | As far as trees go, your best bet is a b-tree. HTey're not hard to make -- around here somewhere I have a javascript implementation -- and you can have a "crush" function that all it does is crush your tree down to as few layers as possible. |
| 09:31 | <@Vornicus> | (I don't know how to build the crush function) |
| 09:32 | <@McMartin> | URGGZOB IS TEN MATHEMATICIANS |
| 09:32 | <@Vornicus> | Then, since you're still working with a perfectly valid b-tree, all your standard functions still work... |
| 09:33 | <@Vornicus> | And then when you feel like compressing it again, you can do that. |
| 09:35 | <@Vornicus> | B trees also have little memory overhead in themselves, especially if you increase the width, but they do have a higher proc overhead because you're doing multiple comparisons at each level. |
| 09:35 | < simon_> | McMartin, sounds Lovecraftian. |
| 09:36 | <@McMartin> | Urggzob is the half-orc fighter/barbarian from Let's Play Icewind Dale 2 |
| 09:36 | <@Vornicus> | Urggzob is a character from, um. I forget, Icewi... |
| 09:36 | <@McMartin> | He like a SMALL COUNTRY whose primary exports are PAIN AND CRUSHING |
| 09:36 | <@Vornicus> | And in the SA LP of it, he often says stuff like that. or Urggzob is TEN linguists! |
| 09:36 | <@McMartin> | ("That's surprisingly erudite for you, Urggzob." "Poli Sci was Urggzob's minor at Crushing College.") |
| 09:36 | < simon_> | haha |
| 09:36 | < Rhamphoryncus> | simon_: a hash table should only be 2 or 4 times larger than an array, and that's just at the low point just after resizing |
| 09:38 | <@Vornicus> | This is true - your typical hash table, once you get down to it, resizes to 50% efficiency if it ever hits 33% or 67% efficiency, or so. |
| 09:39 | <@Vornicus> | (the actual parameters depend on the implementation and can actually be set in some implementations.) |
| 09:40 | < Rhamphoryncus> | So you should be considering what exactly you're storing, both key and value, and if they can be optimized |
| 09:42 | <@Vornicus> | Yeah. Your typical language-side dictionary has been optimized to hell and back already. You don't need to build your own. On the other hand you do want to make sure that your information is as little as you can get away with. |
| 09:44 | < simon_> | the hash-table naturally compresses the key, but not the value, right? |
| 09:44 | <@Vornicus> | ....sorta. |
| 09:44 | | Serah [Stalker@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
| 09:44 | <@Vornicus> | A hash table crushes the key into a hash, which is stored in a list in a table bin. |
| 09:44 | <@Vornicus> | Well, in its own associative array in a table bin. |
| 09:45 | <@Vornicus> | Or something like that. |
| 09:45 | < Rhamphoryncus> | A hash table needs to store the key in addition to the hash though |
| 09:45 | < simon_> | right, and the size of that hash is dependent on your estimations, so in a sense you've compressed it as much as it is deemed sensible. |
| 09:45 | <@Vornicus> | hashmod -> key -> (hash, value) |
| 09:45 | < Rhamphoryncus> | Either directly or as a pointer (such as for a string) |
| 09:46 | <@Vornicus> | Your hash lookup, then, mods the hash value according to the size of the table, looks in that bin, compares the hash itself to the key's hash, and if /that/ works tries to compare keys directly. |
| 09:46 | <@Vornicus> | If the keys compare equal, then that's the key it's looking up. |
| 09:47 | | Kindamoody[zZz] is now known as Kindamoody |
| 09:47 | < simon_> | right. I've seen some pretty neat schemes on top of that that reduce collisions. |
| 09:48 | < simon_> | I like the one with two functions so that a key gets store in its second place if the first one is taken. |
| 09:50 | < Rhamphoryncus> | Now if you actually want to store the key in the container you should look at a trie instead |
| 09:50 | < simon_> | well, my keys are semi-random N-bit numbers (already hashes), and my values are small and alphanumeric. |
| 09:50 | < simon_> | Rhamphoryncus, what's a trie? |
| 09:50 | < simon_> | I found it. |
| 09:51 | < Rhamphoryncus> | n-bit, any size limit? |
| 09:51 | < Rhamphoryncus> | Or does it just tend to be small? |
| 09:51 | < simon_> | sorry, K-bit. |
| 09:51 | < simon_> | or C as one would say in english. ;) |
| 09:52 | < simon_> | they're 160-bit. |
| 09:53 | < Rhamphoryncus> | Alright. And you do have a value associated with each? |
| 09:53 | < simon_> | yup. |
| 09:54 | < Rhamphoryncus> | How big? |
| 09:54 | < simon_> | not exceeding 32 bytes. |
| 09:55 | < Rhamphoryncus> | hrm |
| 09:58 | < Rhamphoryncus> | So if you don't store the hash (fairly easy to recalculate on the fly or even make it all 160 bits) then you've got 52 bytes per entry and an average 50% fill rate |
| 09:59 | < Rhamphoryncus> | That assumes open addressing like CPython uses |
| 10:00 | < Rhamphoryncus> | Should actually be 56 bytes due to alignment of the key |
| 10:01 | < simon_> | even better: I could squeeze it to 128-bits + 10 bytes. |
| 10:02 | < Rhamphoryncus> | how so? |
| 10:02 | < Rhamphoryncus> | You'd want to expand the 10 bytes up to 16 btw, for alignment |
| 10:02 | < simon_> | right |
| 10:04 | < simon_> | well, I'm toying with a rainbow table format. I'd like to do both md5 and sha1, but separately. so the md5 version shouldn't take more if I settle with a subset of passwords. |
| 10:04 | < simon_> | (I wouldn't be able to calculate all the longer ones anyway.) |
| 10:04 | < Rhamphoryncus> | ah |
| 10:08 | | * simon_ looks into the RainbowCrack fileformat for inspiration. |
| 10:58 | | You're now known as TheWatcher |
| 11:04 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 11:04 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 11:04 | | mode/#code [+o Attilla] by Reiver |
| 11:07 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 11:13 | | Vornicus is now known as Vornicus-Latens |
| 11:42 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 11:43 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 11:43 | | mode/#code [+o Attilla] by Reiver |
| 11:56 | | Rhamphoryncus [rhamph@Nightstar-473f8685.abhsia.telus.net] has quit [Client exited] |
| 11:56 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 12:02 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 12:02 | | mode/#code [+o Attilla] by Reiver |
| 12:15 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Connection closed] |
| 12:20 | | Tar_Web [50e51fec@Nightstar-36f67fd0.mibbit.com] has joined #code |
| 12:22 | | Kindamoody is now known as Kindamoody|work |
| 12:32 | | Anno[Laptop] is now known as AnnoDomini |
| 13:18 | < simon_> | on another subject: what is a distributed "sloppy" hash table? |
| 17:50 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 17:51 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 17:51 | | mode/#code [+o Attilla] by Reiver |
| 18:00 | | Attilla_ [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 18:01 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 18:26 | | Kindamoody|work is now known as Kindamoody |
| 18:44 | | jeroid [jerith@687AAB.5E3E50.0F1DEC.DFBB0E] has joined #code |
| 19:20 | | SmithKurosaki [smith@Nightstar-8ff23d84.dsl.teksavvy.com] has joined #code |
| 19:23 | | Vornicus-Latens is now known as Vornicus |
| 19:23 | | Rhamphoryncus [rhamph@Nightstar-473f8685.abhsia.telus.net] has joined #code |
| 19:37 | | Attilla_ is now known as Attilla |
| 19:40 | | kwsn [lets_go_ave@Nightstar-5a8951e9.res.rr.com] has joined #code |
| 19:46 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 19:59 | | jeroid [jerith@687AAB.5E3E50.0F1DEC.DFBB0E] has quit [[NS] Quit: Bye] |
| 20:49 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 20:49 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 20:49 | | mode/#code [+o Attilla] by Reiver |
| 20:54 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 20:59 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 20:59 | | mode/#code [+o Attilla] by Reiver |
| 21:58 | | Tar_Web [50e51fec@Nightstar-36f67fd0.mibbit.com] has quit [[NS] Quit: http://www.mibbit.com ajax IRC Client] |
| 22:02 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 22:04 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 22:06 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 22:06 | | mode/#code [+o Attilla] by Reiver |
| 22:10 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 22:14 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 22:14 | | mode/#code [+o Attilla] by Reiver |
| 23:10 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has quit [Ping timeout: 121 seconds] |
| 23:16 | | Attilla [Obsolete@FBC920.687A28.48203D.E79AC2] has joined #code |
| 23:16 | | mode/#code [+o Attilla] by Reiver |
| 23:23 | | Serah [Stalker@26ECB6.A4B64C.298B52.D80DA0] has quit [Ping timeout: 121 seconds] |
| 23:30 | | Orthia [orthianz@Nightstar-9e6c0588.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
| 23:35 | | Orthia [orthianz@Nightstar-7bc8f1c1.xnet.co.nz] has joined #code |
| 23:49 | | AnnoDomini [annodomini@Nightstar-4e919274.adsl.tpnet.pl] has quit [[NS] Quit: Sleep.] |
| --- Log closed Tue Dec 28 00:00:17 2010 |