--- Log opened Wed Mar 10 00:00:24 2010 |
00:00 | < celticminstrel> | ...of course, it doesn't actually work. |
00:01 | | You're now known as TheWatcher[zZzZ] |
00:49 | < celticminstrel> | Wait, I don't need to escape Unicode characters! |
00:49 | < celticminstrel> | This'll make the code look a little nicer... |
01:51 | | Attilla [Attilla@FBC920.174237.E2DF5D.3AFA0A] has quit [Connection reset by peer] |
02:36 | <@ToxicFrog> | Reiver: how go the linked lists? |
02:36 | <~Reiver> ToxicFrog: Poorly. |
02:36 | <~Reiver> Although I suspect I need to master compression first. |
02:42 | | * gnolam raises an eyebrow quizzically. |
02:55 | <@ToxicFrog> | ...why? |
02:55 | <@ToxicFrog> | Also, seriously, if you're having trouble with them ask me, I like explaining recursive data structures |
02:58 | <@ToxicFrog> | (did you mean "learning compression algorithms is currently higher priority", or "learning compression is a prerequisite for learning linked lists"? Because if it's the latter, it really isn't.) |
03:08 | | MyCatVerbs [mycatverbs@Nightstar-58acb782.cable.virginmedia.com] has quit [Ping timeout: 121 seconds] |
03:33 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has quit [[NS] Quit: Z?] |
03:36 | | Zed__ [Zed@Nightstar-d0088b95.or.comcast.net] has quit [Ping timeout: 121 seconds] |
03:44 | | Zed [Zed@Nightstar-d0088b95.or.comcast.net] has joined #code |
04:59 | | * Orthia explodes. |
05:00 | < Orthia> | Got our first assignment today: Implement the LZW alograthm for arbitary data, with bitpacking, maximum trie size, and commandline scripts to compress and decompress files, and the ability to ... pipe? ... the things to each other. |
05:00 | < Orthia> | Due 28th March. |
05:00 | | * Orthia has decided that maybe he should be learning about trees, um, right now? >_> <_< |
05:02 | < celticminstrel> | Trees aren't that much more complex than lists, really... unless you want to balance them. |
05:03 | | Orth [orthianz@Nightstar-0bfb2cb9.xnet.co.nz] has joined #code |
05:04 | | Searh [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
05:04 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has quit [Client closed the connection] |
05:04 | | Orthia [orthianz@Nightstar-993ef087.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
05:11 | <@ToxicFrog> | Orth: grab me sometime tomorrow and we can go over linked lists and then trees. |
05:16 | <@ToxicFrog> | (LLs first because they're simpler and share a lot of concepts with trees) |
05:23 | < Orth> | ToxicFrog: AWesome, thank you. |
05:24 | <@ToxicFrog> | I'll probably be around from 0900 your time onwards, since that's when I get out of lab. |
05:36 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has quit [[NS] Quit: *hums* Can't stay now!] |
05:42 | < Orth> | Well, you can safely assume you'll have a few hours to do what you need to, so, y'know, feel free to not stress too much about rushing home~ |
--- Log closed Wed Mar 10 05:47:10 2010 |
--- Log opened Wed Mar 10 05:47:20 2010 |
05:47 | | TheWatcher[zZzZ] [chris@Nightstar-b4529b0c.zen.co.uk] has joined #code |
05:47 | | Irssi: #code: Total of 10 nicks [3 ops, 0 halfops, 0 voices, 7 normal] |
05:47 | | mode/#code [+o TheWatcher[zZzZ]] by Reiver |
05:47 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
05:47 | | Tarinaky [Tarinaky@Nightstar-985e55f2.adsl.virginmedia.net] has joined #code |
05:47 | | Zed [Zed@Nightstar-d0088b95.or.comcast.net] has joined #code |
05:47 | | SmithKurosaki [Smith@Nightstar-1a7d4505.dsl.teksavvy.com] has joined #code |
05:47 | | Rhamphoryncus [rhamph@Nightstar-8931f88f.abhsia.telus.net] has joined #code |
05:48 | | Irssi: Join to #code was synced in 48 secs |
05:50 | | DiceBot [Reiver@Nightstar-019bfb55.xnet.co.nz] has joined #code |
05:50 | | Orthia [orthianz@Nightstar-0bfb2cb9.xnet.co.nz] has joined #code |
05:50 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
05:50 | | mode/#code [+o ToxicFrog] by Reiver |
05:50 | | Syloq [Syloq@NetworkAdministrator.Nightstar.Net] has joined #code |
05:52 | | Syloq is now known as Syloqs-AFH |
05:52 | | PinkFreud [WhyNot@NetworkAdministrator.Nightstar.Net] has joined #code |
06:01 | | * Orthia shanghais Vorn, puts him to work in the Java mines |
06:01 | | * Orthia then feasts apon his tender, java-filled brainmeats for sustinence. |
06:01 | <@Vornicus> | ;_; |
06:01 | <@Vornicus> | and it's "sustenance" |
06:08 | | AnnoDomini [annodomini@Nightstar-f9a479fd.adsl.tpnet.pl] has joined #code |
06:08 | | mode/#code [+o AnnoDomini] by Reiver |
06:18 | < Orthia> | So, yeah, I got my assignment today |
06:18 | < Orthia> | It is a touch worrying. |
06:19 | <@Vornicus> | tell me more |
06:25 | < Orthia> | http://www.cs.waikato.ac.nz/~tcs/COMP317/Assignments/assign1-2010.html - oh, you know. Just a little thing, nothing more than five minutes work... |
06:26 | <@Vornicus> | I've never done LZW |
06:26 | | * Serah patpats Reiver. |
06:26 | <@Vornicus> | So this is gonna be interesting. |
06:26 | <@Vornicus> | Fortunately: three weeks! |
06:28 | < Orthia> | Two, really. |
06:28 | < Orthia> | Well, two and change. |
06:32 | <@Vornicus> | Unfortunately right now I need to wash dishes and go to bed, so I'll look at it properly when I get home tomorrow. |
06:34 | < Orthia> | niVorn! |
06:46 | < Serah> | Yeah, me too. Except I already did the dishes (here). |
06:51 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has quit [Ping timeout: 121 seconds] |
07:20 | | Orth [orthianz@Nightstar-4f04433b.xnet.co.nz] has joined #code |
07:21 | | Orthia [orthianz@Nightstar-0bfb2cb9.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
07:44 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
08:05 | | Zed_ [Zed@Nightstar-d0088b95.or.comcast.net] has joined #code |
08:07 | | Zed [Zed@Nightstar-d0088b95.or.comcast.net] has quit [Ping timeout: 121 seconds] |
08:19 | | Orth [orthianz@Nightstar-4f04433b.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
08:19 | | Orthia [orthianz@Nightstar-878857d4.xnet.co.nz] has joined #code |
09:18 | | You're now known as TheWatcher |
09:57 | | Orth [orthianz@Nightstar-e3be6dfe.xnet.co.nz] has joined #code |
09:58 | | Orthia [orthianz@Nightstar-878857d4.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
10:40 | | Attilla [Attilla@FBC920.174237.E2DF5D.3AFA0A] has joined #code |
10:40 | | mode/#code [+o Attilla] by Reiver |
10:50 | | Orthia [orthianz@Nightstar-b411272f.xnet.co.nz] has joined #code |
10:51 | | Orth [orthianz@Nightstar-e3be6dfe.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
11:15 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
11:35 | | Orthia [orthianz@Nightstar-b411272f.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
11:37 | | Orthia [orthianz@Nightstar-3c2966db.xnet.co.nz] has joined #code |
11:38 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has joined #code |
11:41 | | Beaver [guest@583787.CAD79E.827218.F171EB] has joined #code |
11:42 | < Beaver> | www.search2.net (new search engine) |
11:43 | | Beaver [guest@583787.CAD79E.827218.F171EB] has left #code [] |
11:52 | | Tarinaky [Tarinaky@Nightstar-985e55f2.adsl.virginmedia.net] has quit [Ping timeout: 121 seconds] |
12:05 | | mode/#code [+b *!*@583787.CAD79E.827218.F171EB] by Attilla |
12:06 | | Tarinaky [Tarinaky@Nightstar-2edcf1a1.adsl.virginmedia.net] has joined #code |
12:50 | | Orthia [orthianz@Nightstar-3c2966db.xnet.co.nz] has quit [Client closed the connection] |
12:56 | | Zed_ [Zed@Nightstar-d0088b95.or.comcast.net] has quit [Ping timeout: 121 seconds] |
13:03 | | Orthia [orthianz@Nightstar-3725aade.xnet.co.nz] has joined #code |
13:31 | | Tarinaky [Tarinaky@Nightstar-2edcf1a1.adsl.virginmedia.net] has quit [Ping timeout: 121 seconds] |
13:45 | | Tarinaky [Tarinaky@Nightstar-b684ad27.adsl.virginmedia.net] has joined #code |
14:25 | | Bobsentme [Bobsentme@Nightstar-79f8b1cd.livnmi.sbcglobal.net] has quit [Ping timeout: 121 seconds] |
14:52 | | Tarinaky [Tarinaky@Nightstar-b684ad27.adsl.virginmedia.net] has quit [Ping timeout: 121 seconds] |
15:06 | | Tarinaky [Tarinaky@Nightstar-18f9e938.adsl.virginmedia.net] has joined #code |
16:41 | | Serah [Z@3A600C.A966FF.5BF32D.8E7ABA] has joined #code |
16:52 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
16:53 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
16:53 | | mode/#code [+o ToxicFrog] by Reiver |
17:31 | | Serah [Z@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
17:34 | | Serah [Z@3A600C.A966FF.5BF32D.8E7ABA] has joined #code |
18:50 | <@AnnoDomini> | What was the "\n"-equivalent in assembler? |
18:54 | <@McMartin> | Most assemblers will accept that in string literals |
18:54 | <@AnnoDomini> | 0Ah,0Dh,24h? |
18:55 | | * AnnoDomini thought he had a problem with this. The problem turned out to be a mis-performed copy/paste in class. |
18:55 | <@McMartin> | It's generally \r\n, not the other way around |
18:56 | <@McMartin> | On UNIX it really is a bare 0Ah |
18:56 | <@McMartin> | On older micros it's a bare 0Dh |
18:56 | <@AnnoDomini> | Well, this happens to work for me. :) |
19:00 | | * AnnoDomini tries to find out how to determine whether the processor has PSE, PAE, PSE-36 and 3DNow! from assembly. |
19:01 | <@McMartin> | cpuid isntruction. |
19:01 | <@AnnoDomini> | Will the method vary depending on whether it's an AMD or Intel processor? |
19:03 | <@McMartin> | No, there's an instruction in x86 that says "tell me what you do" |
19:03 | <@AnnoDomini> | Cool. |
19:03 | <@McMartin> | If you don't *have* to use assembly, though, the Win32 function IsProcessorFeatureSupported or some such is much better. |
19:04 | <@AnnoDomini> | I have to use assembly. |
19:06 | | Zed_ [Zed@Nightstar-d0088b95.or.comcast.net] has joined #code |
19:07 | <@AnnoDomini> | If I understand this AMD PDF correctly, it's telling me that I should load EDX with 00000001h, then call CPUID. (The header for the table containing the stuff I want says "CPUID Fn0000_0001_EDX Feature Identifiers".) |
19:15 | < gnolam> | http://www.gearlog.com/2010/03/hands_on_fake_intel_core_i7-92_1.php |
19:15 | < gnolam> | The fan is the best part. Magritte would have been proud. |
19:21 | <@AnnoDomini> | This is some good forgery handiwork. |
19:22 | <@AnnoDomini> | Except the spelling. |
19:23 | <@AnnoDomini> | Remind me, during an interrupt, the contents of registers shouldn't be altered, right? |
19:24 | < gnolam> | That's something that puzzles me too. It's the same as with phishing - people go to an enormous amount of trouble to copy websites, official e-mails and, in this case, an i7 box, but they don't bother to double check their handiwork? Or even run it through a spell checker? |
19:25 | <@AnnoDomini> | If they could spell, their CVs would get them accepted into legitimate professions. |
19:26 | <@AnnoDomini> | As it is, without the ability to spell, they are forced into a life of crime. |
19:28 | <@AnnoDomini> | !roll 2^17 |
19:28 | < DiceBot> | [AnnoDomini] 2^17 = 131072. |
19:33 | <@AnnoDomini> | BTW, is it likely that my processor here doesn't have PSE, PAE or PSE-36? |
19:38 | <@AnnoDomini> | Ah, I'm doing it wrong. |
19:43 | <@AnnoDomini> | Yay. I think I've done this. |
19:47 | | Orthia [orthianz@Nightstar-3725aade.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
20:26 | <@AnnoDomini> | Today, the lecturer made an offhand comment that in the past, people used to write viruses that switched out the interrupt pointer table for their malicious purposes. I found that amusing. |
20:43 | | MyCatVerbs [mycatverbs@Nightstar-58acb782.cable.virginmedia.com] has joined #code |
20:43 | | mode/#code [+o MyCatVerbs] by Reiver |
20:45 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
21:05 | | Serah is now known as Eden |
21:23 | | Eden [Z@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
21:28 | | Orthia [orthianz@Nightstar-d7e9f968.xnet.co.nz] has joined #code |
21:55 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
22:30 | < gnolam> | http://abstrusegoose.com/249 |
22:32 | | * Orthia arises from the depths, wavies vaugely in ToxicFrogs direction. |
22:43 | <@ToxicFrog> | Yo |
22:45 | | * ToxicFrog offers Orthia a candied function closure |
22:50 | | * Orthia chews it thoughtfully, but without much flavor. |
22:50 | < Orthia> | So, hey, you want to see the excitement that is my next two weeks? |
22:50 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
22:50 | < Orthia> | http://www.cs.waikato.ac.nz/~tcs/COMP317/Assignments/assign1-2010.html - Just a little thing, nothing more than five minutes work... |
22:52 | | * ToxicFrog seasons it with upvalues |
22:53 | <@ToxicFrog> | Assuming that the LZW algorithm isn't too evil, that doesn't look too bad as long as you don't let it slide |
22:58 | <@ToxicFrog> | You will, however, need to understand trees! |
22:59 | < Orthia> | The LZW alograthm is made of black magic |
22:59 | <@ToxicFrog> | Got a link? |
23:01 | < Orthia> | You output nothing but a series of numbers and from this magically infer what number you just compressed. (Not quite that bad; just a fairly hefty bit of logic puzzle to figure it out.) |
23:01 | < Orthia> | Wiki has a pretty terrible one, hang on |
23:04 | <@ToxicFrog> | Read it. That's not so bad. |
23:04 | < Orthia> | http://marknelson.us/1989/10/01/lzw-data-compression/ - that kind of works, though I was looking for one with the nice example of the tree that forms. |
23:04 | <@ToxicFrog> | In fact I think this is the same algorithm System Shock uses for compressed data. |
23:05 | < Orthia> | LZW is in fact what is used for .zip |
23:05 | < Orthia> | And well a whole crapload of other things. |
23:05 | < Orthia> | It's a little bit famous, you might say. |
23:05 | <@ToxicFrog> | Trees are not in fact mandatory for this algorithm. |
23:06 | | * Orthia scratches his head |
23:07 | < Orthia> | It's how it was explained to us. He spent half the lecture going on about k-way multiway trees. |
23:07 | < Orthia> | Which are a conceptual abstraction from a whole mess of binary trees themselves. |
23:08 | <@ToxicFrog> | The idea is that you use the tree to store the string table |
23:09 | <@ToxicFrog> | This lets you quickly search it to see if the input you're looking at is already in it. |
23:10 | <@ToxicFrog> | Personally I would use a hash table, but that doesn't really help teach you how to use trees~ |
23:14 | < Orthia> | And given he explained how to do it in trees, I think he'd notice if I just hash tabled the compressor as well as the decompressor~ |
23:15 | <@ToxicFrog> | Proooobably. |
23:16 | < Orthia> | OK, so, trees then |
23:16 | < Orthia> | Once I compherehnd the tree I may be able to comprehend the LZW logic puzzle that is the compressor. |
23:18 | < Orthia> | (Also, apologies about showing up so late. Today has turned out to be more hectic than anticipated.) |
23:18 | <@ToxicFrog> | LLs first, because once you have those trees are (usually) really easy to explain. |
23:18 | < Orthia> | Hrn, OK. |
23:19 | <@ToxicFrog> | (also, understanding trees or not doesn't matter at all to understanding LZW; you can implement the same algorithm with a hash table, a really large array, a linked list...) |
23:19 | <@ToxicFrog> | (of course, some of those have performane implications.) |
23:19 | <@ToxicFrog> | So. Linked lists. |
23:20 | <@ToxicFrog> | First of all, some rationale. |
23:20 | <@ToxicFrog> | What first comes to mind when you need to store a list of things? |
23:21 | | * Orthia wonders if he's meant to play stupid and say "An array", or "A list." The latter may be self defeating. |
23:23 | <@ToxicFrog> | Er. I meant "you need to store a list of things; you don't have LLs yet or we wouldn't be having this conversation. What data structure do you use?" |
23:23 | <@ToxicFrog> | And "an array" is pretty much what I was expecting. |
23:23 | < Orthia> | In that case, yeah, an Array. |
23:23 | <@ToxicFrog> | Arrays have some advantages, most notably constant-time access and update. |
23:24 | <@ToxicFrog> | However, they also have some disadvantages: |
23:25 | < Orthia> | Can't make 'em bigger without elderitch madness. can't delete from the middle. ???. Profit!. |
23:25 | <@ToxicFrog> | - every element in the array needs to be the same size |
23:25 | <@ToxicFrog> | - can't make them bigger without a realloc |
23:25 | <@ToxicFrog> | - inserting or deleting stuff in the middle is really slow |
23:25 | <@ToxicFrog> | - needs a contiguous memory region |
23:26 | <@ToxicFrog> | - needs storage for the whole array no matter how many things you actually store in it. |
23:26 | <@ToxicFrog> | Linked lists solve basically all of these at the tradeoff of having O(n) access and update instead of O(1). |
23:27 | < Namegduf> | Plus lots and lots of little allocations, which can be bad. |
23:27 | <@ToxicFrog> | Yes. |
23:27 | <@ToxicFrog> | The basic way this is accomplished is this. |
23:27 | < Orthia> | Right. |
23:28 | <@ToxicFrog> | An array just has a start point and a size, and to get a given element you start at the start point, add the index and there you go. |
23:28 | <@ToxicFrog> | An LL, in contrast, is made of lots of ndividual objects - list nodes. |
23:31 | < Orthia> | hrn, ok |
23:31 | <@ToxicFrog> | (sorry for delays here, juggling eggs) |
23:31 | <@ToxicFrog> | A list node stores two pieces of information: |
23:31 | <@ToxicFrog> | - one item in the list |
23:31 | <@ToxicFrog> | - a reference to the next list node |
23:32 | <@ToxicFrog> | In Java, a very simple list node might look something like: |
23:32 | <@ToxicFrog> | class ListNode { |
23:32 | <@ToxicFrog> | public Object data; |
23:32 | <@ToxicFrog> | public ListNode next; |
23:32 | <@ToxicFrog> | } |
23:32 | < Orthia> | hrn. OK, I think. |
23:32 | <@ToxicFrog> | Anything you want clarification on? |
23:37 | < Orthia> | Yeah. What the heck that does. >_> |
23:38 | <@ToxicFrog> | Well, you use it like so. |
23:39 | <@ToxicFrog> | You store somewhere a reference to the list head - the first node in the list. |
23:39 | <@ToxicFrog> | Then when you want to examine the list, you do something like this: |
23:39 | <@ToxicFrog> | ListNode node = head; |
23:39 | <@ToxicFrog> | while (node != null) { |
23:39 | <@ToxicFrog> | /* do something with node.data */ |
23:39 | <@ToxicFrog> | node = node.next; |
23:39 | <@ToxicFrog> | } |
23:40 | < Orthia> | ... hum. |
23:40 | < Orthia> | OK, am going to paste that to myself and then have a go at it. |
23:40 | <@ToxicFrog> | Basically, in any given node, "data" holds one entry in the list and "next" holds a reference to the next node in the list; if next is null, you're at the end of the list. |
23:40 | < Orthia> | Will transfer computers first to save having to do it halfway through in an hour or two. |
23:41 | <@ToxicFrog> | kk. |
23:41 | < Orthia> | That's... kind of the first time it's made sense. Thank you. :) |
23:41 | <@ToxicFrog> | Will hold until you've transferred. |
23:42 | < Orthia> | (I may be a while. Walking to university for a start.) |
23:44 | <@ToxicFrog> | Aah. |
23:45 | <@ToxicFrog> | Well, poke me when you've done so. |
23:45 | <@ToxicFrog> | (you can't remote into the university computers, or get at your home machine from university?) |
23:46 | < Orthia> | nein, alas. They block SSH. |
23:46 | < Orthia> | 'Security reasons'. *stab* |
23:46 | < Orthia> | They used to allow it |
23:46 | <@ToxicFrog> | Incoming and outgoing? o.O |
23:46 | < Orthia> | In the compsci dept at least |
23:47 | < Namegduf> | Orthia: Do they allow HTTPS through? :P |
23:47 | < Orthia> | Then some bright spark set up a massive DDoS attack from university machines, and the jig was up. |
23:47 | <@ToxicFrog> | The CIS undergrads here would burn shit down if we couldn't remote access the lab machines |
23:47 | < Namegduf> | They require us to remote into their servers (not the individual workstations, but the UNIX servers) to test our stuff here. |
23:47 | < Orthia> | They do that at uni too |
23:47 | < Namegduf> | Minor issues with them are reasons for deadline extensions. |
23:47 | <@ToxicFrog> | If they still allow SSH out - or anything out, for that matter - you could always run an sshd on one of your home machines and access your stuff from the lab that way |
23:47 | < Orthia> | But you have to be at a uni machine to do it. >.< |
23:48 | < Orthia> | I could, but I also run windows~ |
23:48 | < Orthia> | Anyway, running a bit late now. You got me distracted into frothing over the moronic new IT department. >_> |
23:48 | < Orthia> | (They outsourced. Everything went to hell. We're giving it another year or so before they go 'what we we smoking' and change back. Alas, I'm here for the next year or two. >.<) |
23:51 | <@ToxicFrog> | There are windows sshds. |
23:51 | | AnnoDomini [annodomini@Nightstar-f9a479fd.adsl.tpnet.pl] has quit [[NS] Quit: YAWN.] |
23:51 | <@ToxicFrog> | Although I can't in good conscience recommend running them~ |
--- Log closed Thu Mar 11 00:00:25 2010 |