aleph_null @idanka-blog - Tumblr Blog

new website

I had some spare time a few days ago and decided to migrate out of Tumblr to a static generated website over at www.aleph.nu.

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

refresh browser when html or css changes

If you work regularly with web pages you know how tedious it is to go back and forth between your editor and browser and hitting refresh to see the changes.

This shell script finds the browser window of a given HTML file and refreshs it:

#!/bin/sh windowtitle=$(sed -ne "s/<title>$.*$<\/title>/\1/p" "$1") if [ $? != 0 ]; then echo "couldn't find <title> in file" $1 1>&2 exit 1 fi # get rid of leading/trailing whitespace windowtitle=$(echo -n $windowtitle) if [ -z "$windowtitle" ]; then echo "couldn't find <title> in file" $1 1>&2 exit 1 fi # oldid=$(xdotool getwindowfocus) id=$(xdotool search -title "$windowtitle") if [ $? != 0 ]; then echo 'window not found' 1>&2 exit 1 fi xdotool windowactivate $id xdotool key F5 $id # xdotool windowactivate $oldid

The first half of the script is basically just getting the <title> of the file so we can find the correct window to refresh. The rest is giving it focus and hitting F5.

The two commented lines are for those who have multiple monitors with the browser and editor visible at the same time. Then it makes sense to give focus back to the original window. Uncomment them if you'd like that.

Both of these snippets require xdotool, which can be found in any distro package manager (in Ubuntu/Debian sudo apt-get install xdotool).

This can be integrated into vim like this:

autocmd FileType html noremap <buffer><silent> K :update <Bar> \ execute 'silent !~/refresh.sh "%"'<CR><Esc>

Putting this in your .vimrc and hitting K will save the current file and run the script, assuming it's at ~/refresh.sh.

#bash #vim #html

solving the selection problem given the im/n smallest element

Given a black-box capable of finding the $ \left \lfloor \frac{in}{m} \right \rfloor$ smallest element in an array of length $n$, where $1 \leq i < m$ are constant, find the $k$-th smallest element in a given array using the black-box in linear time.

Suppose our black-box is capable of finding the median of an array of length $n$, how would we solve the same problem?

Find the median of $A[p..r]$ using the black-box.

Partition $A$ using the median as our pivot. Suppose the median's index after partitioning is $q$.

If $q-p+1 = k$ then $A[q]$ is the element we're looking for and we're done.

If $k < q-p+1$, recursively call our procedure on $A[p..q-1]$, otherwise call it on $A[q+1..r]$ with $k=k-(q-p+1)$.

Steps 1 and 2 take $\Theta(n)$ time. In step 4 we cut the array in half, so we can express the running time of our algorithm using this recurrence relation: \[ T(n)=T\left (\frac{n}{2} \right )+\Theta(n)\] Solving this gives us $ T(n)=\Theta(n) $.

Back to our original problem: if we use the exact same algorithm, except in step 1 find the $ \left \lfloor \frac{in}{m} \right \rfloor$ smallest element in $A[p..q]$ where $q-p+1=n$, it will still work.

The question that remains, is it still linear? It turns out the answer is yes. Let's prove it: \[ T(n)=T(\max (\left \lfloor \frac{in}{m} \right \rfloor-1, n-\left \lfloor \frac{in}{m} \right \rfloor-1))+\Theta(n) \]

Let $ an \in \Theta(n) $. Suppose there exists some $ c $ such that $ T(n) \leq cn $, then:

Since $ i/m < 1 $, let us denote $ q=\max ( \frac{i}{m} , 1-\frac{i}{m} ) < 1 $: \[ T(n) \leq cqn+an = cn - (1-q)cn+an = cn+(an-(1-q)cn) \] We are looking for $ c $ such that $ an-(1-q)cn \leq 0 $, any $ c \geq \frac{a}{1-q} $ will do.

#algorithms #selection algorithm

kth smallest element in union of sorted arrays

Given two sorted arrays A and B of length n, find the kth smallest element in the union of the two arrays (imagine the two arrays are merged into one sorted array of length 2n). Do so in $ \Theta (\lg n) $.

If we pick two elements, $A[i]$ and $B[j]$, and look at the bigger of the two, let it be $A[i]$, we know that it is at least the $i+j$ smallest element in $A \cup B$. Why? Because it is bigger than everything in $A[1..i-1]$ and $B[1..j]$, and the amount of elements in those two is equal to $i+j$.

What about the smaller of the two, $B[j]$? We can say that it's at most the $i+j-1$ smallest element in $A \cup B$. Why? Because $A[i+1..n], B[j..n]$ are all bigger than it.

Now if $k < i+j$, we can say for sure that our $k$th smallest element is not $A[i]$ or any of A's elements after it. Similarly, if $k \geq i+j$, that rules out $B[1..j]$.

We start at $A[\lfloor \frac{n}{2} \rfloor], B[\lfloor \frac{n}{2} \rfloor]$, and depending on who's bigger, we use the above observations to rule out either the bottom or top half of one of the arrays. If we rule the top of an array, we go back to our original problem only one of the arrays has shrunk in half. If we rule out the bottom, we now have to find the $(k-$ number of elements thrown$)$ smallest element in the halved array and the untouched one.

We are done when one of the arrays is empty, then we simply return the $k$th element in the other one.

It should be fairly obvious why this takes $\Theta (\lg n)$. At each step of the algorithm we do a constant amount of work, and our recursion call loses half an array (similar to binary search).

#algorithms

sub-second precision is not enough

Turns out relying on st_mtime having sub-second precision is not reliable enough, as this small test demonstrates:

$ touch a b ; stat a b | grep Modify Modify: 2011-07-28 15:36:19.505160175 +0300 Modify: 2011-07-28 15:36:19.505160175 +0300

Opening one more process seems to delay enough to show a difference:

$ touch a ; touch b ; stat a b | grep Modify Modify: 2011-07-28 15:37:50.082659665 +0300 Modify: 2011-07-28 15:37:50.085158931 +0300

(test was done on a Debian Squeeze, ext4 fs). Not to mention that Python's underlying type for floats is only good for around sixteen digits. Taking out the ten digits before the decimal point, that leaves about six for sub-seconds. This test:

import os diffs = 0 for i in range(10000): f = open('x', 'w+') f.close() one = os.stat('x').st_mtime f = open('x', 'w+') f.close() two = os.stat('x').st_mtime if one != two: diffs += 1 print diffs, 'diffs out of 10000 iterations'

is giving me around ~30 per run, which is obviously not good enough. So the filecache decorator resorts to relying solely on st_ino and Mercurial's append only strategy to ensure the cache is reliable.

#mercurial #gsoc

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

the filecache decorator

The past week or so I've been working on a new decorator that tracks files under the .hg/ directory for changes. In short, you use it on a method and it turns it to a property with caching the result, like propertycache. But it also gives you the ability to invalidate the cached property, which triggers a stat(2) call that checks if the file behind the property changed since the last time it was read. I used it on the dirstate, changelog, manifest, bookmark files, and the tags cache in localrepo so far. What it means in practice is that a call to repo.invalidate() is significantly cheaper where some of the above haven't changed since the last time they were read. This is crucial so the command server's cached repository stays up-to-date where it changes by a different process than the server itself, i.e. via committing to it directly on the command line. The main issue with this approach is that we fail if we end up missing changes. For example, a filesystem that doesn't have subsecond precision, will cause our cache to lie in the following situation: time action 0 file x is modified 0.1 file x is read, inserted to the cache 0.2 file x is modified again, size remains the same We end up with file x from 0 in our cache. Now suppose we invalidate the cache, this triggers a stat('x'), in which st_mtime == 0, which according to our cache is the most recent version of x, hence no need to reread. But it was in fact modified afterwards, but our filesystem doesn't have the necessary precision to help us spot it. So we have to make sure our cache is reliable, and if we can't, we must fallback to reading the file every time the cache is invalidated. Luckily Mercurial's approach to writing files helps us here. Essentially most of the important files under .hg/ are either: 1) atomically replaced, 2) appended. If our filesystem is able to tell us a) if a file is replaced, or b) if it has subsecond precision, we're basically good to go. Because if we have (a) then (1) is covered, and (2) is covered because st_size changes on append. And if we have (b) it's obvious. The current plan is to use the above test to make sure our cache is reliable, otherwise read the file every time. In the future we can improve this by also noting when the file was read.

#mercurial #gsoc

Mercurial libraries

It's been a few weeks since 1.9 was released and a few libraries that use the command server are starting to appear:

JavaHg by the guys at aragost

a .NET library written by Tak

python-hglib written by myself (not public yet)

Watch the wiki page for updates.

#mercurial #gsoc

first poc

Yesterday I sent out an early version of the command server to the mailing list (patch queue), which included:

new option --cmdserver to `hg serve`.

a small Python wrapper, hglib, around the server that can connect to a repository and run commands. Also included is a sample of how real hg commands might look like in the lib, see status().

a shell that uses hglib and runs commands against a given repository.

last 2 patches are an attempt to integrate the command server to the test suite.

In the next few days I'll be working on:

Support for interactive commands.

Making more tests pass the testsuite using the command server.

Finalizing the command wire protocol and writing it down in a wiki page.

Feedback from other devs on the PoC.

#mercurial #gsoc

Trending Blogs

Last Seen Blogs

aleph_null