Older blog entries for harrisj (starting at number 38)

It's Friday. My disk queue seems to be doing a wondrous job of reducing the memory usage. Large queues are mostly farmed out to disk instead of being stored in memory. After the first 1000 entries, I save files in a queue directory for each additional 1000 (appending new entries to the last file). When I exhaust the in-memory queue, I read it in from the first available file. I know that it might not seem like it would be that much of an improvement over VM, but it works much better (maybe because it has some intelligence about the contents of memory).

More on MacOSX Beta

Damn, it's sweet. It's hard to describe the excitement of running the MacOS and being able to pull up a terminal window running csh. Being able to run emacs is the icing on the cake. My girlfriend thinks I'm partially insane now I suppose... but she's somewhat used to me acting like Professor Frink now and again.

The visual effects of the dock are quite impressive too. Magnification and rescaling are smooth. And the way minimized apps shrink down towards the dock is fun. The support for display postscript also has me intrigued. I think I need to test out more apps with it. Waking up from sleep is also quite quick, atlhough some have complained about power consumption in sleep mode. I think there are still some difficulties to be worked out, since sleeping is a somewhat foreign concept to UNIX.

My only real complaint is that the beta doesn't include Airport support, so I can't use it on the wireless network at home (unless I disconnected the base station from the DSL modem). Maybe I'll get to try its networking out sometime at work today.

Read Extreme Programming Explained yesterday. It has some interesting points, but some parts (eg, pairwise programming) might be difficult for my company. It was enlightening to see some of the stuff we do in there though (although I guess some of it falls under CowboyCoding). The key challenge will be to keep communication channels open as we expand. If you are interested in this new programming methodology, check out the WikiWeb entry on ExtremeProgramming

MacOSX Beta

My copy of the MacOSX public beta finally arrived. Looking forward to installing it tonight. Unfortunately, it doesn't include Airport support, so I don't think I'll be able to test out its networking at home. Bummer.

Got my unlimited FIFO hack working after a few hours or so of coding. It's fun to play with. Soon, I'll see how much it reduces my memory consumption (although I must make sure there is enough disk space available). If you're curious about the details, ask me. It's a bit of a kluge, but it works.

Addendum

My DSL provider (Concentric) has merged with Nextlink and become XO Communications. What a bloody stupid name...

eskimoses has posted an interesting article. People should read and comment.

Otherwise, it is Friday again. Yay.

Richard II

Went to see Ralph Fiennes perform in a production of Shakespeare's "Richard II". Not one of his more popular plays (compared to say, Richard III), but it was amazing nonetheless. Great performances all around, and Ralph added an incredible depth to this study of the construction of Royalty and its downfall. The set design was nice: the entire stage was covered in turf. This was more than a gimmick, given all of the references to the ground and sacred earth of Mother England in the play. Worth seeing if you are in New York, although I think it is sold out by now.

The Brooklyn Academy of Music is a neat place. We're actually members, so I should go to more plays and movies there.

Random note: The director Steven Soderbergh was sitting in the audience just behind me to the left. Extra funny since my domain name is taken from one of his films.

Data Structures

I might potentially have the need for an unusual data structure. The idea is something like an unlimited FIFO*. That is, I have a queue of items to be processed. However this queue can get quite large and potentially consume large amounts of memory. What I would like to be able to do is to place most of the queue on disk if it gets to a sufficient size. Pushes can be appended as they occur, while pops can be done in batches (eg, the top 100 elements on the queue). I can think of how to abstract some of this (pushing is just appending to a file), except for how to remove the first 100 elements from a file of entries (the batch pop). Can anybody help me? Is there any code that does something like this? Is there a way to avoid rewriting the file? I'm sorry if it's a stupid question**, but I'm feeling a bit addled here right now.

* A FIFO does seem like a good thing for this job, except they have a rather limited size and block writes when they get full. I can't do that.

** As I like to say, "There are no stupid questions, just stupid people." ;)

Possible Solution?

I suppose one solution might be to split up the queue into N M-entry sized files. Push entries onto the Nth file. On pop, read the first file into memory and delete it. This can potentially produce a lot of files, but it might be the best I can do.

Theoretical Computer Science

Pseudonym: I don't know the answer to the NP-optimization question. Could you argue that in some cases it is not certifiable in P, since the only way to check would be to compute all of the solutions (NP task) and verify that the particular solution is optimal? Of course, I don't know if you can declare this for all NP-optimization problems, and it's making my head spin right now (I can only do this sort of math at certain times).

If anybody is curious about optimization problems, here is a Compendium of NP-Optimization Problems I found on the web.

Hacking

ghod: Hacking actually dates back to the early days of time-share systems at MIT. It was often used to denote crawling around in the innards of a program (eg, debugging code) or even a building (eg, exploring forgotten steam tunnels). It's still used in that way today at MIT (cf, The New Hacker's Dictionary). This is also where the phrase "a quick hack" comes from to indicate code thrown together to solve a problem quickly, but often in a confusing or inelegant way. No connotation of intent was implied, but it was generally done for good or at least neutral purposes. About 10-15 years ago, the meaning of the term began to shift to what it is today. Unfortunately, hacker has taken on a negative implication (because of a lot of bad behavior), causing people who don't hack maliciously to want a different term to describe themselves. Hence, "cracker".

Let's not get into the whole debate over "black hat" vs. "white hat" hackers, or even how much good a "white hat" hacking group like l0pht can do.

Pseudonym: Thanks for your answer. You are a veritable font of knowledge on the subject. I'm quite impressed.

I'm a bit rusty from when I took a class on theoretical computer science a few years back. Can you perhaps briefly describe some of the more interesting properties of EXPTIME. I'm particularly interested in verification time vs. calculation time. For instance, I know that an NP-time problem can be verified in P-time (I think this has been proven). Is this also true of EXPTIME problems, or is verification in a higher class, or is it simply unprovable.

EXPTIME measures execution in time, EXPSPACE measures execution in space. It is known that EXPTIME is a subset of EXPSPACE, but not known whether it is proper containment or not (all we know is that P != EXPTIME, right?). This is correct. I'm still trying to get an idea of what the "meaning" of EXPTIME is. Mainly, what is an example EXPTIME algorithm?

schoen: Thanks for your interesting points. It reminds me of a debate I had with a coworker here at work. I found the whole idea of morality being impossible without fear of divine authority a bit absurd. But whatever. People can believe in whatever they want, but I can't stand it when they pass judgement on me as a result.

schoen, Pseudonym, and yakk: Thanks for your input. I knew that factoring was in NP (although nobody is able to prove that there is NOT an algorithm in P). I was under the mistaken impression that it might be NP-complete as well. So finding a P algorithm for factoring won't show that P=NP as I erroneously suggested.

I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?

I have found that Sipser's "Introduction to the Theory of Computation" is a good primer for all of this, for those that are curious. Now to work on a provably EXPTIME-hard encryption method. I think I can bang one out this weekend. ;)