26.8.05

 

hmmm

i gave my mailing machine a name: mercury, because it has a mercurial temperament.
---
first comment spam!
if you're looking for some guaranteed easy money you should try investing in timber, apparently.
---
"human decisions are becoming increasingly random as a result of desire"
something someone once said to me.
---
further crime against nature: mayonnaise in a cheese and ham sandwich.
a few years ago they didn't even have mayonnaise in chip shops and now they're even putting it on kebabs.

23.8.05

 

Quicksort

i may have mentioned that i came up with my own variant of Quicksort. i usually use it when i'm sorting a bunch of stuff into alphabetical order by first letter only, so there are lots of items starting with the same letter which can be in any order in relation to each other, and the frequency of the different letters is kind of randomly distributed.

Quicksort is a very good way of sorting that starts to become much faster than simpler, more 'intuitive' ways above about 20 items. I usually use it when I have at least thirty or so files. it works like this:

choose a file at random, say the one on top

then sort all the others into two piles; the ones that go before it or after it.

put the first pile on the left, and the second pile on the right

then you can add the file you chose at random to either pile, it doesn't matter, although putting it on the smaller pile is a good choice.

now pick up the pile on the left and start again doing exactly the same thing

put the two piles you split that one into back down with the first one on the left, both to the left of the other pile

you'll notice your stacks of files are in order, in the sense that all the files in a stack to the left will come before anything in a stack further to the right, but within each individual pile, nothing will be ordered

keep on doing the same thing to each pile, splitting it into a stack that comes before the top file {or some other randomly chosen one} and a pile that comes after, then putting the two stacks back next to each other in the same place in your row.

eventually, you'll be left with stacks which only contain one file. since the stacks themselves are in order, you have sorted all your files. just combine all your one-element stacks, starting of course from the left [earlier] side.

[OR if you're slightly impatient like me, when you have a pile with only a few files in it, you can sort it 'by hand' by any quick method you choose, since further subdividing say, four files into different piles isn't necessarily the quickest way to do it. then combine your sorted stacks.]

as i mentioned earlier, i often use this to sort things only by first letter, so i simply stop as soon as i have a pile only containing one letter of the alphabet.

the reason this can be so efficient is that the thing you spend most of your time doing is just choosing one of 2 stacks to add the file in your hand to. so if you start by picking mr keown's file at random {lucky you}, all you have to do with all the rest is decide whether they come before or after 'keown' in alphabetical order. unless the name starts with 'k', this is very quick and simple. even if it does start with 'k', it's not too hard to choose the right stack. then, since you {roughly} halve the size of your stacks each time, they get small pretty fast.

the drawback is as follows: mr able's file {or mr zanzibar's} might be on top, or be the one you choose at random some other way. then you're going to spend a lot of time flicking through a bunch of files, and all you're going to get out of it is having 'able' {and possibly 'aardvark'} put to one side, and a massive, unsorted stack of everything which comes after able on the other side.

there are a few ways round this. one solution is to choose 3 files, and sort them. then put the first one on the left, the last one on the right, and use the middle one as your 'splitting point'. this at least guarantees that you won't choose the first or last file to split the rest with.

another way is to try and guess what letter {or number, or whatever} might come in the middle. if you chose keown at random, you were definitely luckier than if you chose able, since the optimum is to split the stack into two that are as equal in size as possible. there's usually a similar number of a-k's and l-m's. however, this method relies on you making a good choice, not just at this early and easy stage, but also later, when you've already got a few smaller stacks, and you have to guess where the middle point of 'roberts' to 'williams' might be. halfway through s? halfway through t?

my own variation goes as follows. take the top two files {or two random ones}. put the earlier one on the left, and the later one on the right. suppose you've chosen F and T. F goes on the left, and T on the right. then as you work through the rest, put anything starting A-F {or 'before F'} on the left, and anything starting T-Z {or 'after T'} on the right. until you get to something that starts with a letter G-S, say I. put this on the smaller stack, say it's the 'after T' one, and change that stack to the 'after I' stack. you now have somewhere to put A-F and I-Z, so continue until you reach a G or a H, and put that on the stack that's now smaller. say A-F is smaller, so you put G there and change it to A-G. eventually your 'before' and 'after' letters will meet up in the middle, and you'll just be dividing into A-H and I-Z or something like that.

with your smaller stacks, you do exactly the same thing. you'll have two piles something like R-T and W-Z, but this doesn't matter. you only need to remember 'before T' and 'after W' and it wont matter whether the 'before T' stack starts with A or some other letter.

this method seems to offer a good way of roughly finding the midpoint, even when you have quite a random distribution of letters, since it adapts itself to the distribution as you go along, adding more letters to the smaller stack. until the two stacks meet up in the middle, the algorithm is still adjusting itself to make them as equal as possible. all it requires is for you to have a good way of comparing the size of your stacks [i do - my thumb and forefinger], and to remember 2 'pointers' to Quicksort's one {'before F' and 'after T' instead of 'before and after K'}. the drawback, similar to above, is of course when your first 2 files are A and B or something like that, so your 2 stacks become A and B-Z. this means it's not very good for files that are already sorted, or almost sorted.

i haven't looked into the subject much but to my knowledge it is original, although i would be surprised if someone hadn't come up with it, or something remarkable similar before.


19.8.05

 

(some) mailing machine error messages

Envelope feeder empty
Jam at envelope feeder
Cover open
Envelope missing from insert area
Stuffer jam at insert area
Cascading feeders 1/2 empty
Jam at feeder 1
Jam at feeder 2
Feeder 2 incorrect length
Feeder 2 double detect
Envelope stuff jam
Closer jam
Fold plate 1 jam
Jam at closer track

18.8.05

 

Operation Margarine

"To instil into the Established Order the complacent portrayal of its drawbacks has nowadays become a paradoxical but incontrovertible means of exalting it."
from Mythologies, by Roland Barthes

5.8.05

 

imagine

imagine that some time back in the early nineties you used to live in los angeles and you went out with this canadian girl for a while, she reckoned she was a singer songwriter but actually worked as a waitress and anyway she was a bit nuts and kind of obsessed over you a bit much and had a kind of whiny voice and wasn't such great shakes as she thought she was either as a singersongwriter or a girlfriend and so anyway you were kind of seeing this other girl most of that time anyway so well basically you broke up with her after only about three weeks or something and then she goes even more nuts and actually starts to scare you a little bit and not only does she start making obscene phone calls when you're hanging out with your new girl and then she breaks into your house while you're at work and goes through your underwear drawer and shit like that and now you're actually starting to get worried that she's dangerous or something but then she records a whole album of spurious allegations of things you supposedly did to her and stuff like that and what an evil guy you are etcetera and the album for some fucking reason sells thirty million copies worldwide even though none of her other albums sold jack no it would be the one about you wouldn't it and becomes some sort of fucking anthem of women who think some guy shouldn't have broken up with them or did them some kind of wrong when they broke up with them and all these songs talking about your own personal shit that happened to you well however much of it actually was true anyway are being played on the radio day and night for about six fucking years and people you know even people who live in new york are like phoning you up asking you about i heard it was about you and did that stuff in that song really happen and then guess what ten years later is she finally over you? has she moved on? do you ever get the chance to forget about some alleged misdemeanours you made about a decade ago? no of course not she's releasing a fucking acoustic version of all the same songs all over again

that would be kind of a jagged little pill to swallow

3.8.05

 

today

i was thinking about good ways to sort into order a bunch of pieces of paper that are already almost in order, with nowhere to put down a stack of paper except on my knee.
a good way is probably Insertion Sort. everybody knows this, it's what you usually do if you sort some cards in your hand. you start at the left, going through the cards to the right, each time taking one and putting it in the correct position among the ordered cards to the left of it. so you constantly have a pile of cards on the left which are in the right order, and a bunch to the right which are in the order they started in, and you just keep moving individual cards from the right side to the left.
the weird thing is, lots of people when they first start learning to program, instead of using this pretty simple, pretty fast algorithm which they know already, instead use something a little bit more boneheaded: Bubble Sort.
Bubble Sort involves repeatedly going through your cards from left to right, swapping around any pair that are in the wrong order. it's really not a very good way to sort, for aesthetic and practical reasons. it's not quite the same as, but involves the exact same number of operations as if you used Insertion Sort, but moved a card from the right of your hand to the left by swapping pairs of cards all the way along until it got to the right place, instead of just pulling it out and putting it back where you want it. it doesn't use any less space then Insertion Sort. it's not really any easier to understand. it's easy to see that its not a very good method of sorting if you try it for 7, let alone 13 playing cards.
i think people think quickly about sorting, and associate it straight away with swapping pairs of elements.
this is why it's good to try out algorithms by hand. also why it's good to think about the way we do things in real life. those traditional wisdom methods are usually pretty good.

1.8.05

 

a subset of the real line

take the interval (0,1)
throw away the middle closed interval of length 1/2, leaving two open intervals
throw away the middle closed interval of length 1/3 that of the whole interval, from each of those two
leaving four shorter open intervals
throw away the middle closed interval of 1/4 of the length from each of those
then the middle 1/5 (closed; including endpoints) from the eight open intervals you have left
and so on
for 1/6, 1/7 ...

the points you have left are an uncountable, nowhere dense set of measure zero which isn't open, but is density open. which means each point of the set is a density point of the set. which is the purpose of the exercise.

 

six days

in a country where they nod their head to mean 'no', and shake it to mean 'yes'.

 

on the way to the electronics shop

i walk past a shop called MOBILE CAR ALARMS.

 

crimes against nature

-the coke machine at work, which obviously reads this blog, giving me diet coke instead of the real thing.
-a post office without a copy of the pamphlet 'mailing abroad: price guide'
-they now sell bags of monosodium glutamate in the supermarket
-and 'pepsi max twist' in the 99p store. but no real pepsi, w or w/o twist.
-and they don't have any 'branston pickle', britains most popular pickle (probably) at all in the other supermarket, except some abortion of a marketing gimmick that is pickle in a squeezy bottle.


God it drives me crazy when I know exactly what I want and I can't find it anywhere! It's like does anyone want my money!? I mean what the fuck!?
- Enid in Ghost World


This page is powered by Blogger. Isn't yours?