code logs -> 2010 -> Wed, 10 Mar 2010< code.20100309.log - code.20100311.log >
--- 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
code logs -> 2010 -> Wed, 10 Mar 2010< code.20100309.log - code.20100311.log >