18 Oct 2008 tampe   » (Journeyer)

Gardening

The background, we have a sequence X1,X2,... and by some strange reason want to sort them incrementally and use functionals of the generated sorted sequences as output. So what tricks do exists?

Try explore (linearity), (monotonisity), (associativity and commutativity), (locallity) and (permutational invariance).

One of the simplest functionals are a basic sum of the sequence and of cause for this you just don't care to sort it in the first place.

S is sorted incrementally, now consider a linear filtering of that sequence and we are just interested in the end result. Most certainly you can use locality to improve performance here but you can also use the following. When sorting you will define a subtree, at each junction point. There define the value of the output (the state of the filter) of the sequence related to this part of the tree as a linear function of the input state of the filter. Doing this means that each new value will demand about log(n) operations in order to update at an insertion in the tree. So this is actually n log(n) - the same complexity as sorting a tree but with a bigger constant in front and memory requirements. Still I found this little trick kind of neat. Noting this approach can be generalized to other kinds of operations like some class of logical ones by abstracting this idea gave some coolness and it is a good little pattern to remember.

So there is a family of tricks you can do. The criteria for these tricks is quite restrictive and it is easy to get out of the n log n domain and into the n**2 domain. The interesting thing though is that this class of functionals are composable, but cannot mix well with point wise operations, the thing is that ones you have issued one of these filters you cannot in general then do point-wise operations on it and after that issue one of these kind of filters again for that to work you need it to be some kind of linear pointwise operation.

So The conclusion is that there are some nice tricks but most probably you will be bound to n**2 complexity.

I'm off make for some weird abstractions, or in other words Good Night!

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!