Hash table operations are probabilisticly O(1), degrading to O(N) in the worst case (many hash collisions).
Unmodified quick sort has expected complexity O(N log N), but worst case O(N**2), so if you pick your data carefully, you can get either solution to be O(N**2).
An interesting comparison, but its a comparison of Courier-IMAP vs UW IMAP, and not just Maildir vs mbox.
I once tried benchmarking Maildir vs mbox for my mail archives (mailboxes with ~3000 messages). On ext2 Maildir was a loss:
Mutt took twice as long to open a Maildir than mbox from cold cache.
Mutt still took a bit longer to open Maildir than mbox from hot cache.
On ext2 with 4K blocks mbox ate 13 MB of space, Maildir ate 21 MB.
Small UI degradation: Mutt wouldn't show the number of lines in a message from a Maildir, and it wouldn't show percent progress indicator while reading the Maildir.
Basically for my situation (read-only mail archives with large numbers of messages,
which are rarely in filesystem cache, ext2 and
constant disk space shortage) mbox was better.
But my situation (personal mosty static mail archives) is remarkably different from running IMAP server.
I did this test in 2000. I should probably try again some day with Reiserfs, but I heard various people telling me it doesn't improve Maildir performance. Can't say anything until I try myself.
I therefore recommend you to try it yourself and see if Maildirs really help in your situation.
That's not to say you should use OO for everything (e.g. you wouldn't want to represent each character in a document using a separate object).
Take a look at the Flyweight pattern in Design Patterns book. Yep, a model of a word processor where every single character is represented by a very light-weight reusable object. Interesting stuff, though I can't say it convinced me completely.
There are many improvements on the standard Quick Sort algorithm, like using a median-of-three method to avoid this already-sorted-data worst case. And insertion sort is O(N) when the data is in nearly sorted order.
BTW, SGI Standard Template Library now uses introsort which is O(N log N) in the worst case, and at least as fast as Quick Sort on the average. Personally I know nothing about it, except this reference given in STL documentation:
D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997
I think both GNOME and KDE have taken the beneficial parts of Microsoft's GUI and left out the parts that are either extraneous or just plain bloated.
Unfortunatelly, not all of them. Have you tried using GNOME apps without a mouse? Its possible (sometimes only with the help of XFree86 MouseKeys), but inconvenient. Can you place two or more toolbars in the same row (or a toolbar next to the menu) to save some screen real estate? Heck, some of the apps won't even let me switch on small toolbar icons and turn off the text. (Besides, GNOME/KDE copied Windows Explorer, which IMnsHO is a pure piece of unnecessary bloat. MC in an xterm is the way to go!:-)
OK, I'm ranting here. GNOME does look very nice. I only wish it would feel a little bit better. That's why I prefer plain IceWM over a desktop environment. IceWM's focus is on feel, not on the look. I still hope I can say the same thing about GNOME/KDE eventually.
Why are you accepting packages for crappy OSes??? An open-sourced package for a crappy OS is just an open-sourced package for a good OS that hasn't been ported yet...
And what about packages that simply cannot be ported? For example, there's fsdext2 -- an ext2 fs driver for Windows 9x. It is a very useful thing (it makes your Linux partition available to all applications with a drive letter, unlike Explore2fs/ltools/whatever), but it makes no sence to port it to a "good OS".(I'm assuming Slashdot's popular notions of "good OS" == "Linux/*BSD", and "crappy OS" == "Microsoft *".)
I've already notified the maintainer (who hasn't been actively developing fsdext2 for quite some time) about UFO.
There is a plugin for FAR (A very good quality shareware Win32 console mode Norton Commander clone) that allows one to nagivate the registry as if it were a filesystem. There are similair plugins for network browising, browsing resources in PE-COFF.EXE and.DLL files, etc.
I wish somebody wrote an ext2 plugin. FSDEXT2 does not work on NT (and doesn't support 4096K blocks...).
Of course this (like Midnight Commander's VFS) is available only for a single specific program.
Slashdot Mirror
Hash table operations are probabilisticly O(1), degrading to O(N) in the worst case (many hash collisions).
Unmodified quick sort has expected complexity O(N log N), but worst case O(N**2), so if you pick your data carefully, you can get either solution to be O(N**2).
My e-book reader (a Nokia 770) fits into my pocket. A paperback doesn't.
Nokia 770 has a 800x480 screen at 225 dots per inch. A lovely device that runs Linux.
Windows NT Resource Kit used to have vi.exe ("Microsoft VI"). I nearly fell off the chair laughing when I first saw it.
Don't know about SFU (when I have to use Win32 (about once in several months), Cygwin is enough), but what's wrong with using a Win32 port of VIM?
I once tried benchmarking Maildir vs mbox for my mail archives (mailboxes with ~3000 messages). On ext2 Maildir was a loss:
- Mutt took twice as long to open a Maildir than mbox from cold cache.
- Mutt still took a bit longer to open Maildir than mbox from hot cache.
- On ext2 with 4K blocks mbox ate 13 MB of space, Maildir ate 21 MB.
- Small UI degradation: Mutt wouldn't show the number of lines in a message from a Maildir, and it wouldn't show percent progress indicator while reading the Maildir.
Basically for my situation (read-only mail archives with large numbers of messages, which are rarely in filesystem cache, ext2 and constant disk space shortage) mbox was better. But my situation (personal mosty static mail archives) is remarkably different from running IMAP server.I did this test in 2000. I should probably try again some day with Reiserfs, but I heard various people telling me it doesn't improve Maildir performance. Can't say anything until I try myself.
I therefore recommend you to try it yourself and see if Maildirs really help in your situation.
Take a look at the Flyweight pattern in Design Patterns book. Yep, a model of a word processor where every single character is represented by a very light-weight reusable object. Interesting stuff, though I can't say it convinced me completely.
There is no 1.2 kernel tree that is secure from remote attack
-- Alan Cox on linux-kernel, 5 Nov 2001
Just FYI.
Actually, w3c itself mentions Konqueror's CSS2 support as impressive.
BTW, SGI Standard Template Library now uses introsort which is O(N log N) in the worst case, and at least as fast as Quick Sort on the average. Personally I know nothing about it, except this reference given in STL documentation:
Today I was browsing the archives again, and I found this. Seems on-topic?
Unfortunatelly, not all of them. Have you tried using GNOME apps without a mouse? Its possible (sometimes only with the help of XFree86 MouseKeys), but inconvenient. Can you place two or more toolbars in the same row (or a toolbar next to the menu) to save some screen real estate? Heck, some of the apps won't even let me switch on small toolbar icons and turn off the text. (Besides, GNOME/KDE copied Windows Explorer, which IMnsHO is a pure piece of unnecessary bloat. MC in an xterm is the way to go! :-)
OK, I'm ranting here. GNOME does look very nice. I only wish it would feel a little bit better. That's why I prefer plain IceWM over a desktop environment. IceWM's focus is on feel, not on the look. I still hope I can say the same thing about GNOME/KDE eventually.
And what about packages that simply cannot be ported? For example, there's fsdext2 -- an ext2 fs driver for Windows 9x. It is a very useful thing (it makes your Linux partition available to all applications with a drive letter, unlike Explore2fs/ltools/whatever), but it makes no sence to port it to a "good OS".(I'm assuming Slashdot's popular notions of "good OS" == "Linux/*BSD", and "crappy OS" == "Microsoft *".)
I've already notified the maintainer (who hasn't been actively developing fsdext2 for quite some time) about UFO.
I wish somebody wrote an ext2 plugin. FSDEXT2 does not work on NT (and doesn't support 4096K blocks...).
Of course this (like Midnight Commander's VFS) is available only for a single specific program.
I think the most complete story about this probe lost due to a computer bug can be found in the alt.folklore.computers FAQ.