I'm finding it rather amusing to have had a conversation about what Unix commands would feel best when tongued through a proposed lingerie/tablet computer combination device today. The notion of interconnecting such devices to form a network using cat69 cable was mentioned.

GOP freshmen help derail Patriot Act extension [Washington Post]

Holy crap, the Tea Partiers actually turned out to be useful for something. Not that it'll matter in the long run; they've still got 19 days to renew it, and easily enough support to do so even they can't fast-track it. Still, a bit of a surprise.

Python compiles source files to byte code automatically whenever a module is imported; to save itself time, it does this only if the bytecode file (.pyc) does not exist or has an mtime older than the corresponding source file.

Reasonable enough so far; now here's the stupid: if the corresponding source file no longer exists but the bytecode file has been left in place, python will silently use the bytecode. Suppose we have script.py and module.py in one directory, and another module.py elsewhere on the search path, so the local module.py overrides the other one. Now suppose, after this has been run at least once and module.pyc has been created in the local directory, module.py is deleted; in the work-related example I'm thinking of, module.py was a different implementation of uuid, and the silliness that motivated it eventually went away.

It turns out that, in this case, Python check if the mtime on the source file is newer than the mtime on the bytecode file, but fails to check for the continued existence of the source file, leading me to some mysterious exceptions, a wasted fifteen minutes of bafflement and a large *facepalm*.

What an utterly depressing thing this was to read:

A Typical Day for PFC Bradley Manning

The guards are required to check on PFC Manning every five minutes by asking him if he is okay. PFC Manning is required to respond in some affirmative manner. At night, if the guards cannot see PFC Manning clearly, because he has a blanket over his head or is curled up towards the wall, they will wake him in order to ensure he is okay.

That sounds bad enough, and, depending on how vigilant they are about waking him in the night, awfully damn close to sleep deprivation of the type the Stasi used to use.

At 5:00 a.m. he is woken up (on weekends, he is allowed to sleep until 7:00 a.m.). Under the rules for the confinement facility, he is not allowed to sleep at anytime between 5:00 a.m. and 8:00 p.m. If he attempts to sleep during those hours, he will be made to sit up or stand by the guards.

In combination with this, it really does start to sound like torture via sleep deprivation: he's unable to get an uninterrupted sleep at night, and then forced to remain awake (and what could there conceivably be to wake up *for*?) fifteen hours a day.

He is allowed to receive letters from those on his approved list and from his legal counsel. If he receives a letter from someone not on his approved list, he must sign a rejection form. The letter is then either returned to the sender or destroyed.

That sounds like such a little thing, but I think it sent chills down my spine more than anything else: it's not enough for them to interfere with his correspondence in that fashion; he must be made to sign personally, as if it were his rejection rather than his captors'.

They can do this much to someone for such a fundamentally heroic, noble act, and they can do it without charging him with anything for seven months, and the mainstream media raises not a word of protest. The bleating masses presumably are in the main supportive of it, quivering with vindictive glee as they watch the State annihilate this man who has stood up against it and thus shown the rest of them for the slavish cowards they are. This culture has turned so much toward this mood of vicarious sadism, more and more over the years; 'fascist' is far overused as a generic political epithet, but that more than anything else must be its defining characteristic.

This comment seems to sum it up perfectly:

Why am I not surprised? Put to a vote, I'm almost certain over 50% of Americans today would say PFC Manning is getting off easy, and many would vote to hang him with no trial.

This is the new America we're witnessing, and it will no doubt worsen as we slide from world leader to world leper. This isn't the America of my youth. It is not the America that reached out to a destroyed Europe and helped it rebuild.

I've really got to find a way out of here soon. It can only get worse from this point.

You're either with us, or you're with WikiLeaks [Marc A. Thiessen; Washington Post]

If "one guy with a laptop" can shut down WikiLeaks even temporarily, imagine what the 1,100 cyber-warriors at U.S. Cyber Command could do. While the United States sits on the sidelines, the New York Times reported Saturday that WikiLeaks had come under assault "from armies of zombie computers in Europe, Russia and Asia." This flood of attacks creates the perfect cover for the United States to deliver the coup de grace to WikiLeaks secretly, with no fingerprints, if it chose to do so.

Some say attacking WikiLeaks would be fruitless. Really? In the past year, the Iranian nuclear system has been crippled by a computer worm called "Stuxnet," which has attacked Iran's industrial systems and the personal computers of Iranian nuclear scientists. To this day, no one has traced the origin of the worm. Imagine the impact on WikiLeaks's ability to distribute additional classified information if its systems were suddenly and mysteriously infected by a worm that would fry the computer of anyone who downloaded the documents. WikiLeaks would probably have very few future visitors to its Web site.

Such abject failure of clue speaks for itself, really. It certainly confirms my previous opinion on the technical competence of anyone uttering the phrase 'cyber-warrior'. One imagines he's expecting that the Cyber-Warriors (gods, I can feel my IQ dropping just typing that) will just re-route a few encryptions, override a password or two and type something like rm -rf wikileaks, and then there'll be a flashing red countdown before their servers explode. Mr. Thiessen, of course, has a long history of saying cluelessly authoritarian things on this subject, as I've previously commented on.

This is why, in the long run, we're going to win: everyone on the other side is operating with a model of the world so grossly at odds with reality that they'll expend most of their effort shooting themselves in the foot to slay hallucinatory enemies. I'd be happier to watch it all end in fire from a safer distance, though.

Additional observation on the subject: using a random sample of 50 cables released by Wikileaks in a tarball compressed with bzip2, they seem to average around 4.1 kilobytes compressed per cable. This comes to only 998 megabytes for the complete set of 251,287 cables. The insurance.aes256 file is too large by almost half to contain just the unredacted cables. There's something more in there yet to come.

So, I've had a chance to get away from Python and do something more interesting in C++ at work for the last couple days. I will describe the problem, with details abstracted away to protect the aesthetically guilty.

There is a certain class, which I will refer to as ItemList, which stores a list of items and allows it to be queried with the following operations: several getItemByX() methods which return the first item in the list matching the provided value of X, for different properties X of the items, and a getNthItem() method which retrieves items by an integer position. This class allows the list to be modified by a push_back() method which, following the STL naming convention, appends an item to the end of the list, a sort() method which sorts the list according to a particular order, one removeItem() method which searches by one of the values X queryable by the getItemByX() methods, and a removeOffendingItems() method which takes an arbitrary boolean test and removes all matching items.

This class uses an STL vector to store refcounting pointers to items, so we have a declaration something like this:

class ItemList {
    public:
        Item * getItemByID(UUID id) const;
        Item * getItemByName(std::string name) const;
        // etc.

        Item * getNthItem(int n) const;

        void push_back(Pointer<Item>& new_item);

        void removeItem(UUID id);
        void removeOffendingItems(ItemTest& test);

        void sort(void);
    protected:
        std::vector<Pointer<Item> > mItemList;
};

These are all implemented in the obvious way, by iterating over the vector. The getItemByX() methods take O(n), the getNthItem() and push_back() methods take O(1), the removeItem() and removeOffendingItems() method take O(n), and the sort() method takes O(n*log(n)).

A certain piece of code which calls this class needs to iterate through the list of items, and then replace some of them (which match particular UUIDs) with different items, possibly renaming said replacements (to preserve uniqueness of names). The test for non-uniqueness of name takes O(n) with this implementation, and it needs to be done for some fixed proportion of all items, so the entire process takes O(n^2), which has proven unacceptably slow.

The solution, naturally, is to speed up getItemByX() to a more sensible O(log(n)), so this whole loop only needs O(n*log(n)). Unfortunately, the existence of more than one getItemByX() method, together with getNthItem() and its implied semantics about the constancy of the order of items makes the simplest option, replacing the vector with an STL map with Pointer as the value and UUID or std::string as the key, impossible. The next best option is to add an additional STL map for each value of X, indexing the vector. Thus, getItemByX() only needs O(log(n)), push_back() method now takes O(log(n)) for the index updates, and the other methods retain their original asymptotic performance.

It occurred to me, however, that to have such an index available and still do removeItem() by searching the entire vector was a bit silly. Using an STL vector still makes deletions take O(n), but if I could find the item to be deleted using the index, I could save one pass through the vector, at least. One needs an iterator to delete an item from an STL container, however, so to do it that way I would have to store iterators in the indices rather than additional refcounting pointers.

That won't work, though, because iterators into an STL vector refer to a particular index in the vector, and don't point to the same value after an insertion or deletion before that value. To get stable iterators, I would have to replace the vector with a list, and then I could put iterators in the indices and do removeItem() in O(log(n)), but at the cost of making getNthItem() take logarithmic time, which would violate the constraint of not slowing down any other operations by more than a factor of log(n). Thus, I'm going to leave the vector and just accept an O(n) removeItem() that can't use the indices, as silly as that seems.

If I were feeling really effortful there would be a better solution, though, which is the real point of this post: a data structure with the semantics of a doubly linked list (a sequence of items in a stable, unsorted order, insertions and deletions permitted at any point) and the performance characteristics of a balanced tree (all operations take O(log(n))). Consider a tree where each node has a pointer to its parent and its two children, a value and a count of all the nodes, including itself, in the subtree rooted at that node. Now provide tree rotation operations which adjust the counts accordingly, and use them to keep the tree balanced. You can insert and delete in arbitrary positions in O(log(n)), iterate forward or backward from any node in O(log(n)), so it's no more than log(n) worse than a doubly linked list, but you could also binary-search down the tree using the node counts to find the nth node in O(log(n)), so the integer index lookup is no more than log(n) slower than an array.

Someone must have invented something like this before, but I hadn't ever encountered it, so I thought I'd write it down for future reference. I'm not going to do it for this particular task; it's overkill, and balanced trees are a pain to implement, to say nothing of balanced trees with the interface of an STL container.

I've been experimenting with high dynamic range imaging a bit, using J.D. Smith's exposure-blend GIMP plugin. Some examples:

On the basis of Seattle's traditional reaction to snow, I'm predicting glaciers by mid-afternoon.

Apropos of nothing, a painting of a donkey mounting a giraffe:

Aside from their peculiar taste in art, the restaurant (warning: website is a gibbering horror of Flash from beyond space and time) in question is actually pretty good.

Family waits to see if mother, accused of blasphemy, will be hanged [CNN]

Pakistan has never executed someone convicted of blasphemy but in Bibi's village public opinion was unanimous.

"Yes, she should be hanged," a group of villagers cried out.

The town cleric, who made the initial complaint against Bibi, called her death sentence one of the happiest moments of his life.

"Tears of joy poured from my eyes," Qari Salim told CNN.

Well, I just got at least ten times my recommended daily allowance of misanthropic depression from reading that. I want to move to the moon and not have to share a gravity well with several billion psychotic, bloodthirsty primates.

I think that it is only by willfully ignoring most of the world that anyone with any trace of compassion at all can ever hope to function in life.

Government harassing and intimidating Bradley Manning supporters [Gleen Greenwald; Salon]

Between this and the recent shift in TSA policy toward yet more groping, I'm having a rather uncomfortable resurgence of the feeling of living in a bad sequel to the Weimar republic. It would be really nice to be able to travel without having to worry about some means of transportation coming only in a "buy one, get one molestation free" package deal.

This year for Halloween I attempted to do the femme version of Alex from A Clockwork Orange. I think it was overall a success, but I have a very hard time looking like I'm capable of ultra-violence. I should have played up the excessively cute angle, maybe spattering myself with some fake blood or something and contrasting it against my rather innocuous appearance. Either that, or actually killed someone to get into character.

I got hglancer to style my hair last night; I rather like how these came out:

I've just had a rather impromptu but surprisingly good night out seeing the Legendary Pink Dots, with Legion Within opening, at El Corazon. I should do spontaneous things like that more often, I suppose; I hadn't planned on it but Lancer (hglancer) wanted to go since we know the lead singer from Legion Within, and we only found out about it at the last minute.

I do have a few (rather bad, cell phone) pictures of LPD:

Democratic party ad against Rand Paul and for drug prohibition [The American Prospect]

Leave it to the Democrats to criticize a war-mongering thug by picking one of the things he's actually sensible about. I'll be so glad when this election season is over.

I've just gotten my hair dyed purple-black and cut in a sort of bob; I haven't had short hair in quite a while and now I'm rather enjoying it.

I'm experimenting with switching to Dreamwidth now, I think. Random servers in Russia downloading images only linked to in my locked posts is just too damn creepy. I've got the same username over there.

Courtesy of Fail Blog

What, they just hand you a length of rope and large bill?

Somehow I always suspected Oliver Wendell Holmes, Jr. would bring about the downfall of civilization, albeit after a considerable delay and from beyond the grave:

Justice Breyer on the Unconstitutionality of Koran Burning [Reason]

Breyer told me on "GMA" that he's not prepared to conclude that -- in the internet age -- the First Amendment condones Koran burning.

"Holmes said it doesn’t mean you can shout 'fire' in a crowded theater," Breyer told me. "Well, what is it? Why? Because people will be trampled to death. And what is the crowded theater today? What is the being trampled to death?"

I thought Breyer was supposed to be one of the more liberal justices, but I guess they've fallen pretty far from "I do not agree with what you say but I will defend to the death your right to say it." I do wish people who quote that stupid 'fire in a crowded theater' line would bother to look up the original context for it and think long and hard about whether this is really an idea they want to be supporting.

Google Scribe is making me feel like the singularity just jumped a little bit closer. It amounts to automatic writing from the collective unconscious. A sample sentence, produced in about fifteen seconds with a combination of spontaneous choices suggested by both Google and my own mental entropy source (which doesn't seem to function well without being mixed with outside noise like this): "Colorless monkey was violated with an asterisk and squelched the frotz."

Why, with a little practice, it could be like having James Joyce's brain in a vat...

Now I want to try this on acid.