--work-properly

[reading: Jean Hugard & Frederick Braue, "The Royal Road to Card Magic (revised edition)"; recently Henning Nelms, "Magic and Showmanship: A Handbook for Conjurers"]

Today's --work-properly option: adding -rdynamic (a.k.a. --export-dynamic) to a GCC link line will mean that any dlopened libraries are able to bind to the symbols in the running executable.

Bogo-Permute

So here's today's random question, apropos of, er, nothing. What's the performance of the following incredibly-poor algorithm for randomly permuting a list of numbers?

def bogo_permute(in_list):
    N = len(in_list)
    out_list = []
    # Keep track of whether we have dealt with each element of the input list
    seen = [False] * N
    for iteration in range(N):
        while True:
            which = randrange(N)
            if not seen[which]:
                out_list.append(in_list[which])
                seen[which] = True
                break
    return out_list

There are N selections needed for the output list. The first time through, the randomly selected entry from the input list will definitely not have been processed already, so it can be transferred across to the output list. The second time through, there's a chance that the random selection process will select the same entry again; for later iterations, this chance of selecting something that has already been selected will get higher and higher. So, on average, how many of these repeated picks are needed?

Given a coin that comes up heads with probability p (and so tails with probability q=1-p), what's the average number of coin tosses needed before the first heads comes up?

As an example, imagine that the first head turns up on the fourth toss. This means that the sequence of tosses is TTTH. The probability of this sequence of coin tosses is then q³p = (1-p)³p. This is easy to generalize:

Number of Tosses	Sequence	Probability
1	H	p
2	TH	qp
3	TTH	q2p
4	TTTH	q3p
⋮	⋮	⋮
m	T…TH	qm-1p

We want the average number of tosses needed to get a head, also known as the expected value. This is a sum of the each possible value multiplied by the probability of that value occurring. In other words, the average number of tosses needed is:

(1*(probability of heads on first toss) + 2*(probability of first heads on second toss) + 3*(probability of heads on third toss) + …)

Put into maths, this means that the average number is an infinite sum: Σ_m=1^∞ m (q^m-1p). From a trusty binomial expansion, the Σ_m=1^∞ m q^m-1 part pops out as (1-q)^-2, and since q=1-p this means that the whole thing simplifies down to just 1/p.

(This seems reasonable: for a fair coin, it takes an average of 2 throws to get a head; for a coin that only comes up heads one time in a hundred, it takes an average of a hundred throws.)

So back to the original problem. For the i-th selection (with i running from 1 to N), the chance of picking an array entry that is still there is p=(N+1-i)/N, and so the average number of picks needed is N/(N+1-i). The first selection needs N/N = 1 attempt, the second selection needs N/(N-1) attempts, the third selection needs N/(N-2) attempts, …, the last selection needs N/1 = N attempts (on average).

Taken together, this means that the average number of random picks for the whole process is Σ_i=1^N N/(N+1-i). Rearranging (with j=N+1-i) this is the same as N Σ_j=1^N1/j, which includes a partial sum of the harmonic series, known as a harmonic number H_N. In the large N limit, the harmonic numbers tend to H_N ≈ ln(N) + γ (where γ is a constant), and so the asymptotic behaviour of the algorithm is O(N ln(N)).

So it's bad, but not quite as bad as I'd expected (I'd guessed it would be O(N²)).

inline_related_objects

[Edit, Feb 2008: fixed typo—changed extra_content to extra_context]

Today's neat Django trick: getting the create_update generic views for a model to display entries from a subsidiary model in-line—like the admin interface does when you add edit_inline=models.TABULAR.

The (oldforms) Form object that gets generated by the create_update view already has most of the required gubbins inside it; we just need a few extra steps to get at it:

1. In urls.py, set an extra_context argument for the view to be a dictionary that contains inline_related_objects:

    {'inline_related_objects': model._meta.get_followed_related_objects(None) } 

2. In the template, include a loop to pull in all of the related objects:

    {% for related_object in inline_related_objects %}{% edit_inline related_object %}{% endfor %} 

   within the <form> tag.
3. Since the edit_inline template tag is not a built-in Django tag, the template also needs to load up the admin_modify extension:

    {% load admin_modify %} 

4. Make local copies of the relevant admin templates (such as admin/edit_inline_tabular.html and widget/foreign.html) and tweak appropriately.

Of course, I didn't figure this out until after I'd spent a couple of hours dismantling the admin interface code with a view to stealing the relevant bits. Roll on the Django book.

The Joy of UNIX

UNIX credo: you can do anything from a single command line (as long as the line is allowed to be arbitrarily long).

Case in point: generating a white noise audio file

sox -t sl -r 44100 -c 2 /dev/zero \
-r 44100 -c 2 -w whitenoise.wav synth 10:00 whitenoise vol 0.6 fade q 10 10:00 10

Django Su

It's always a sign of good design when adding a new feature turns out to be easy.

In the Django authentication system, I wanted a way for an administrator to view the site as if they were a particular user; effectively an equivalent to su in UNIX-land.

The first easy step was to invent a URL to correspond to this action, which gets encoded in urls.py:

  (r'^su/(?P<username>.*)/$', 'qlockweb.accounts.views.su', {'redirect_url': '/qlockdata/'}),   

That done, the second and final step is to write some view code.

  @user_passes_test(lambda u: u.is_staff)
  def su(request, username, redirect_url='/'):
      su_user = get_object_or_404(User, username=username)
      if su_user.is_active:
          request.session[SESSION_KEY] = su_user.id
      return HttpResponseRedirect(redirect_url)

Seven lines of code and we're done (modulo a bunch of import statements).

Expanding what's going on here:

(r'^su/(?P<username>.*)/$', 'qlockweb.accounts.views.su', {'redirect_url': '/qlockdata/'}), 

• When an HTTP request arrives at the framework, Django goes through its list of URLs until it finds a match. In this case, going to http://mysite/accounts/su/fred/ ends hitting the urls.py line above; the /(?P<username>.*)/ part of the regexp pulls out "fred" and this gets passed as a parameter named username into the function su in qlockweb/accounts/views.py. This function also gets passed a parameter called redirect_url with value '/qlockdata/'.

@user_passes_test(lambda u: u.is_staff)

• Actually, we need to rewind one step before we get into the su function. The line before the function definition is a Python decorator: some extra code wrapping the function that gets executed just before the function itself is executed. This decorator needs some expansion of its own:

  @user_passes_test(lambda u: u.is_staff)

  • The @ sign is the syntactic sugar that indicates that this line is a decorator for the function that comes immediately afterwards.

  @user_passes_test(lambda u: u.is_staff)

  • This is the decorator function (from contrib/auth/decorators.py); its first argument test_func is a function that does the test. This test function is given a single parameter: the current User. If the test function returns true, the wrapped view code is called; if not, then the user gets redirected to a login page.

  @user_passes_test(lambda u: u.is_staff)

  • More syntactic sugar. We want a function is_this_a_staff_user(u) that checks whether its argument u is an administrator. However, as this is the only place that the function is used, we don't bother to give it a name—we just use a lambda expression to give the definition right here and now.

  @user_passes_test(lambda u: u.is_staff)

  • Finally, the body of the lambda expression just uses the method of the User class that indicates whether the user is an administrator or not.

def su(request, username, redirect_url='/'):

• So now we're in the su function itself, and if we've got this far we're guaranteed that the person viewing the page is logged in as an is_staff user. The function has the username and redirect_url parameters mentioned earlier; it also has a request parameter that holds all of the information about the original web request (in a HttpRequest object).

  su_user = get_object_or_404(User, username=username)

• The next line of code gets a User object for the username that was specified—fred in other words. If there isn't a user called fred, then a Http404 exception gets raised, which will percolate up the stack and display a (surprise, surprise) 404 page.

  if su_user.is_active:

• This particular version of our code only allows impersonation of active users, helpfully provided by the is_active field in the standard User model.

    request.session[SESSION_KEY] = su_user.id

• The next line of code is the one that actually does the work. The requesting user's session is modified so that its user ID is the impersonated user's.

  return HttpResponseRedirect(redirect_url)

• The final line of code redirects the web browser off to the redirect_url page.

(Statutory disclaimer: I am not a security expert, nor do I play one on TV. Adding this to a production system is probably not a good idea.)

---

Another Django snippet: I finally discovered that the follow argument to the standard Manipulators allows you to list fields in the model that the form should leave untouched. Very helpful: the end result is more compact and less brittle than the code I'd put together to manually override all of the hidden fields.

[A:37385 B:3278 C:346 D:9187 E:62544 Total:112740]

*knolp*

[reading: William Faulkner, "As I Lay Dying"; recently Neil Strauss & Bernard Chang, "How To Make Money Like a Porn Star"]

Now that I've got Django installed and running, I've been setting up my first web application with it.

I spent a bunch of time yesterday trying to figure out how to get extra parameters passed through a generic view; in the end I had to UTSL to get a method that worked.

So of course today I find a nice page that concisely and coherently explains it, rather more quickly than the couple of hours it took me to figure out.

Perhaps I can suggest *knolp* (the reverse of *plonk*) as the sound of an RSS feed hitting my aggregator. (It looks like I'm not the first person to think of this.)

[A:37385 B:3278 C:346 D:9187 E:46320 Total:96516]

How do I exit thee? Let me count the ways

[reading: Tom Holt, "Alexander at the World's End"]

Today I've been trying to sort out the interactions between the various different mechanisms for generating and catching errors in Windows. With the help of a noddy test program, I ended up with:

Type	No handler	atexit	signal	catch (...)	set_terminate	__except (EXCEPTION_EXECUTE_HANDLER)	__except (EXCEPTION_CONTINUE_EXECUTION)	SetUnhandledExceptionFilter
exit(0)	No message	Hit
abort()	Visual C++ Runtime Error dialog		Hit (SIGABRT)
c=*(char*)0	'Encountered a problem and needs to close' dialog		Hit (SIGSEGV)	Hit		Hit	Hit, generates infinite loop	Hit
i=1/0	'Encountered a problem and needs to close' dialog			Hit		Hit	Hit, generates infinite loop	Hit
raise()	No message		Hit, execution continues from the raise
throw	Visual C++ Runtime Error dialog			Hit	Hit			Hit
RaiseException(0xE0000001,EXCEPTION_NONCONTINUABLE, 0, NULL)	'Encountered a problem and needs to close' dialog			Hit		Hit	Hit	Hit
RaiseException(0xE0000001, 0, 0, NULL)	'Encountered a problem and needs to close' dialog			Hit		Hit	Hit, execution continues from the RaiseException	Hit

Other key points to note:

• All catchers only see errors from the same thread, with the exception of the SEH unhandled exception filter set by SetUnhandledExceptionFilter().
• For (say) a null dereference, the order that various handlers get to see things is:
• Vectored Exception Handler (VEH)
• C++ exception handler or Structured Exception Handler (SEH), whichever has the narrower enclosing scope
• SIGSEGV signal handler /* FALLTHRU */
• SEH unhandled exception filter installed by SetUnhandledExceptionFilter
• C++ unhandled exception handler installed by set_terminate
• I've no idea why a null dereference does appear as a C++ exception in a catch (...) block, but doesn't hit the unhandled-C++-exception-handler installed by set_terminate.

Day 328

A trifle bizarre. After a bunch of investigation, I eventually narrowed down a synchronization problem to the following mini test program:

#include <time.h>
#include <stdio.h>
int main()
{
  time_t tv = time(NULL);
  struct tm *tms = localtime(&tv);
  printf("%02d:%02d:%02d DST:%d\n", 
         tms->tm_hour, tms->tm_min, 
         tms->tm_sec, tms->tm_isdst);
}

When I ran on Mac OS X:

~:date
Mon Mar 27 14:12:29 BST 2006
~:a.out
14:12:30 DST:1

But when I ran on my main Windows XP box:

c:\>time /t
14:13
c:\>localtime.exe
13:13:03 DST:0

Now, I'm usually happy to believe the worst of Microsoft, but it stretches even my credibility to think that their C runtime doesn't get the 1989 ANSI standard right (particularly as a quick web search didn't turn up any complaints).

Investigating further, when I ran the same code on a different Windows XP machine, I get the right answer:

c:\>time /t
14:15
c:\>localtime.exe
14:15:24 DST:0

So I checked MSDN and found some mutterings about "localtime corrects for the local time zone if the user first sets the global environment variable TZ...TZ is a Microsoft extension and not part of the ANSI standard definition of localtime. Note: The target environment should try to determine whether daylight saving time is in effect."

Running echo %TZ% from the command line showed up as GMT. So I tried changing the timezone to EST, but echo %TZ% was still reading GMT. Odd.

Eventually, I discovered that my login had TZ=GMT hard-coded into the environment (Control Panel, System, Advanced, Environment Variables). Not sure how it got that way, but finding it and making it not so has just taken a couple of hours.

[A:35029 B:3218 C:346 D:9187 Total:47780]

Day 74

[reading: Scott Meyers, "Effective C++ (3rd edn.)"]

I'm reading "Effective C++" again, with the publication of a new edition, and I'm struck by an observation. It's startling how much of the advice in early parts of the book boils down to: Understand how the compiler works. (Items 2, 4, 5, 7, 9, 10, 16 and 17 out of 18 so far)

This is an approach that I've got a lot of sympathy with; I really got to grips with Microsoft Word when I stopped observing the phenomonology of its peculiar behaviour, and instead sat down for half an hour to think about how it might be implemented internally. After that (even though I'm sure I didn't even get close to the true internals), I could cope with and predict the vagaries of the program much more effectively.

However, it does seem to me that one of the points of higher-level computer languages is so that programmers don't have to understand the details of the implementation. I guess if you just memorize the Effective C++ items and forget their explanations, then you can achieve that blissful state of ignorance—but it's safer and better to know the why and the how, which is why Scott's books sell so well.

But this does lead back to my underlying concern: that C++ is too complicated for mere mortal programmers. All of the individual features are there for a good reason, but taken as a whole the language is too big. A top-flight C++ programmer pretty much needs to know the whole of:

• Bjarne Stroustrup: C++ Programming Language (868 pages)
• Scott Meyers: Effective C++ (272 pages)
• Josuttis: The C++ Standard Library (744 pages)

That's 1884 pages in total. Even Common Lisp: The Language only weighs in at 971 pages.

I just about trust myself to write C++, but that's only because I know I'll avoid the parts of C++ that I don't understand fully. I've only ever met half a dozen people that I'd completely trust to write C++ (one of them being Scott), which makes for a hard time supporting C++ code.