Recent blog entries for fejj

And here it is, your Moment of Zen:

Those who assume the worst in other people, are by their very nature among the worst people.

Those who assume the best in other people, are by their very nature among the best people.

-- Jeffrey Stedfast

5 Mar 2007 (updated 6 Mar 2007 at 04:56 UTC) »
fzort: I think you mean Binary Insertion Sort and not Bubble Sort. The idea would be to use another in-place sorting algorithm that doesn't get hit hard when attempting to sort a segment that may already be pre-sorted. No reason to use anything slower than you have to, and so Binary Insertion Sort fits nicely.

For historical reasons, a Binary Insertion Sort was probably also used to eliminate recursive function call overhead as well as stack overflows.

Note that while the binary search portion of the Binary Insertion Sort algorithm is recursive, since it is tail recursive, it can be implemented in such a way as to even avoid having to use an internal stack.

See the last implementation discussed here for an example on how to do that.

Thanks for the link too, btw, I will be sure to check that out later when I get home from work!

4 Mar 2007 (updated 4 Mar 2007 at 22:26 UTC) »

haruspex: Hence my comment above that line,

If your program makes heavy use of a sorting routine, you may want to consider implementing a tailored sort function rather than just using qsort().

By no means do I suggest writing your own low-level routines for no reason... but if your program is spending a lot of time sorting, then you might consider writing a tailored sort routine. Obviously this wouldn't make sense if sorting is barely even on the radar as far as time spent in your program.

Hopefully this clarifies my position and the intent of my wording (which I admit may have been unclear).

Note, also, that all of my entries in my blog series on sorting start off with an unoptimized version of the sort routine, implementing them as closely to the description of the algorithm as I can. From there, in each entry, I went on to describe my mode of thinking on how to achieve better performance (largely as an educational challenge to myself) - e.g. I never suggest pre-optimizing.

Update: more on sorting here.

4 Mar 2007 (updated 1 Apr 2011 at 19:43 UTC) »

Update: this article was moved: Quick Sort

4 Mar 2007 (updated 4 Mar 2007 at 14:50 UTC) »

I came across something cool the other day that I thought I'd share: a 25-byte long integer sort routine (that is to say, the routine itself is only 25 bytes long).

Here it is:


;---------------------------------------------------------------
; Sorts an array of ints. C-callable (small model). 25 bytes.
; void sort (int n, int a[]);
;
; Courtesy of David Stafford.
;---------------------------------------------------------------

.model small .code public _sort

top: mov dx,[bx] ; swap two adjacent ints xchg dx,[bx+2] xchg dx,[bx]

cmp dx,[bx] ; in the right order? jl top ; no, swap them back

inc bx ; go to the next integer inc bx loop top

_sort: pop dx ; get return address (entry point) pop cx ; get count pop bx ; get pointer push bx ; restore pointer dec cx ; decrement count push cx ; save count push dx ; save return address jg top ; if cx > 0

ret

end

fzort: Ah, thank you for the explanation :)

I was just about to note that expanding on my previous estimation, a slightly better one would be:

r = (x >> 1) - (x >> 2) - (x >> 3) + (x >> 6)

And then of course I could perhaps expand on the (x >> 6) in a similar fashion to get an even more accurate result.

Anyways... kind of an interesting problem.

1 Feb 2007 (updated 1 Feb 2007 at 10:50 UTC) »

Interesting interview questions:

Q: What's a fast way to divide an integer by 7 using the bit shift operator? (apparently asked by an EA Sports interviewer)
A: I thought about this for a bit and came up with the following estimation:

r = (x >> 2) - (x >> 3) + (x >> 6);

I mostly mention this because I had my own interview today where I felt... well, less than adequate. Suffice it to say, my ability to figure out the Big-O notation for algorithms was less than stellar. I was also unable to come up with a solution for his webcrawler scenario, which was along the lines of "if you've got some huge number of pages to crawl, how could you prevent the crawler from scanning the same page multiple times?" to which I had to admit to him, I hadn't the slightest idea how to go about it (the prelude to this question had been "the simplest way to do such a thing if memory was not an issue" to which I replied I'd use a hash table, using the page urls as the key).

Been listening to Drivin' Too Fast lately, really has a nice groove to it.

Amazing what a break from looking at code can do to help you fix a bug.

Back in 2004, I had been writing articles explaining different sorting algorithms, how they worked, and how to implement them in C (and in most cases, how to implement them more efficiently than the "standard textbook way"). Well, I had gotten distracted around the time I had been working on an article for Quick Sort and never got around to finishing it. I remember having a bug in my QuickSort routine somewhere that I wasn't able to find after a few nights of looking at it and having had more pressing things to attend to, set it aside for later (but not before documenting a few test cases that failed and how they failed).

Well, yesterday, after coming across that code, I opened it up in my trusty Emacs editor and in just a few minutes had a solution... it was basically a simple one-off bug.

Not long after, I got a call from someone at Google who had seen my resume and repeatedly told me they found it "interesting". I have no idea what that means, exactly, but I take it that it's a Good Thing(tm) :)

23 Jan 2007 (updated 24 Jan 2007 at 15:16 UTC) »

Thanks to Ross's blog for informing me about Dave Cridland's Push-IMAP projects (Polymer, Telomer) and the Lemonaide specs. This was quite an interesting read... I've been wanting something like this for years, it's really exciting stuff.

Despite what pvanhoof claims in his own response to this news, offline functionality is not the hardest part of implementing an IMAP client.

169 older 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!