le prospector

A couple of weeks ago I had an idea about sorting come unexpectedly into my mind, and it wasn't until last night that I'd had a look online to see what, if anything, anyone had written about the idea.

In 1995 (when I was in my first year at university) we were asked to implement any sorting algorithm we liked to sort an input stream of integers (I think in the range 1 to 1000). At the time I knew how to do a bubble sort, probably selection sort, and maybe something else, but nothing as fancy as quick sort or merge sort. As far as I recall, we were learning about asymptotic complexity ("big oh" notation), and the program I wrote wasn't really a sort, but a trick that occurred to me that would give the correct result for the given type of input. The lecturer docked me a mark (so I only received 9/10) saying that my method was not extensible (not that extensibility was stated as a requirement for the assignment, so I was pretty annoyed!).

And now, more than 10 years later, I find that the method I used is known as "Count Sort". Well, very nearly - my method involved creating an array of counts for each possible input value, but was single pass for the input - the output was obtained by checking each count and emitting count copies of the index, so was super fast. :o)

I don't know yet when "Count Sort" was first known, but my lecturer certainly didn't mention it, and I'm a bit miffed that I was led to believe (for 10 years!) that it was useless. In any case, for completely unknown reasons, while trying to get ready to leave home on a Friday morning this hacky sorting method was in my head and I started thinking about ways to make it more general. I soon ended up in a state, not quite panicking, but rather agitated at the notion that I might have stumbled across something new (and potentially extremely valuable!)... I paced around, unable to concentrate on things like putting on my shoes, and started getting worried about what the process is for protecting such an idea.

I SMS'ed a friend, paced around some more, tried to stay calm and work out how to put my shoes on. As far as I knew, quick sort was about as good as it gets, and O(nlogn) was the best you could do. But my idea was more like O(n) ... surely either someone had thought of this before, or the details in the implementation, or the last part of the algorithm, would force the complexity back to nlogn (or worse).

SMS wasn't good enough. I called the friend, interrupting whatever it was they were doing, to see if they knew what to do about intellectual property. I hadn't even sat down to see what the details might be. It was a very strange feeling - a sort of overwhelming emotion attached to a simple idea, and I still have no idea why I was thinking about it at all.

Since then I was in the library at Enmore TAFE (where I am currently a student), looking for a Photoshop tutorial book. Instead of what I was looking for, I noticed a booked that I had read about somewhere called "The Artist's Way", and near to that a very small book titled "A Technique for Producing Ideas" by James Webb Young. I picked it from between the neighboring books and started reading it right there. It was originally published in 1965, and I find it's contents to be very self-affirming, and very possibly explaining exactly the process by which I'd had this sorting idea.

Having now read about Count Sort, and some similar sorts (especially one originally called "histogram sort"), including a reference to something Knuth wrote about needing linked lists, I'm not sure that I want to go through the pain of pursuing the idea any further, but I would like to propose the following notion:

Sorting based on any simple integer-based key (strings of letters are "integers", but floating point values probably aren't!) can be done in O(n + k) time, where n is the number of input values, and k is related to the complexity of the key.

eg for my original program, the array of 1000 counts had to be scanned to produce the result. But give it a thousand, a million, or a billion input values to "sort", and there same array need only be scanned once. So if there are a lot more input values than possible unique keys, the O(k) can be thought of as a constant and ignored. Most sorts aren't on simple keys, though, so it is important to keep that "k" in consideration.

Basically, the idea is not to compare values with each other to determine the order, but rather to simply put each input value into "the right place" straight away. Just as you can place a mark on a grid at the right location from knowing the co-ordinates, you can link the a record with a given key to the right place in an array (or tree... or perhaps some other structure) without care for any other values. Once the keys are put in the right places, just pick them up in order from start to finish.

I wouldn't call it genius, but I'll settle for spark of brilliance! I didn't quite exclaim "Eureka!", but I think that's something like how I felt about it.

[px]

And even if you were a computer guy...

In response to "I'm A Programmer, Not A Compuer Guy"...

(NB: I'm new to blogging, please excuse my lack of blog/ping nouse)

There are a lot of issues here on several sides of the fence (some "multidimensional" fence). Brian's position is one that has formed from experience. I'm sure he, as most people do, started off quite happy being able to help people out. The problem comes when there have been an unreasonable number of requests for help, and little value paid by the people asking for it.

Professionals from any industry will be subject to friends/neighbours/etc asking/expecting help from them. Show me an accountant who doesn't get asked by everyone they know for help with their tax... I have a cousin who works for the taxation department, and he of course flatly refuses to have anything to do with anyone's tax.

I think there are a few differences in the situation for the "computer expert" (CE), be they coder, techie, network engineer, etc - anyone the "general populace" is likely to assume as having the ability to fix any computer/electronic problem.

Computers, as general tools for almost every business task, much education and home entertainment, generate a constant barrage of "problems" for pretty much everyone, on a daily if not hourly basis. Not just once a year at tax time. Not when they're building an extension on their house. Not when they've found a mysterious lump behind their ear. Not when they're trying to decide what car to buy. Every day.

That is probably the only fact that can't reasonably be changed. It wouldn't be so bad if people would not seek the CE as the first port of call all/most of the time. For example, the person sitting at the desk next to you probably knows how to make bullet points in Word - try asking them. That extends to more complex issues as well.

There have been a few comments above which mention money. Either straight out money, or some sort of barter is perhaps the best way for the CE to deal with the situation. "Mates rates" from a builder, plumber, car mechanic, etc will typically not be "free", and certainly not if there are a continuous stream of requests. However, for the CE, and perhaps many other people from "knowledge industries", the assumption is that the assistance will be with a smile, for no charge, and possibly also come with parts/etc supplied by the CE.

Large scale "help desk" operations operate in several tiers. The first level will be able to handle the vast majority of "problems". For something more complex, the issue may need some more careful consideration, and passed to another level where the staff have a different focus.

For example, according to an ex flatmate, first thing in the morning was a busy time of day at Sony (Sydney), with a large number of calls from people who had forgotten their password and couldn't log in... And, well, that help desk is there for people to call up with whatever problem. It's a full time job for them, and it is costing someone quite a bit of money for that support. Those same users might call again later in the day to ask how to change their login icon back into that cute little yellow duck. Help desk slaps their (own) head, but probably get around to helping out. Help desk will be the point of contact for more serious problems (server failures, network issues, etc), which could very possibly actually be dealt with by third parties, but often the user will consider the help desk contact as being the one who "got it fixed" - this is a perception issue

You'll note that working help desk is usually not particularly popular, and staff turnover is usually pretty high for exactly this reason - they reach the point of "I wouldn't do that if you paid me". And they were getting paid to do it, so they're really not making it up. Yet the expectation of the local CE is that they will help out, at no cost, and that they will be an actual expert with whatever particular question is asked or problem presented.

Without the intention of inciting flaming, I suggest that those who insist it is the CE's responsibility to at least give every "cry for help" a go (be that a Google search or whatever) are either selfless, tireless good samaritans, or have been in the (unusual?) position of not being hounded. People other than the local CE have access to Google, and can find the answer just as well.

The "interweb" has possibly reduced the pressure on a lot of other industries. People can (and I'm spposing do, in a lot of cases) look stuff up about medicine and health, share trading, tax tips, information about cars (which I know NOTHING about, so don't ask me), travel, ... pretty much anything. Now it is the CE's responsibility to help everyone find that information.

People deserve to be rewarded for their skills and efforts. For whaever reasons, people will call on the CE's time and skill, which they evidently treat as valuable (because they need to print their document, or whatever), but mostly do not reward the time or skill. That skill, consequently, often gained outside of the formal education of university, college, etc. Time spent dicking about with their home PC, reading books, online resources, etc, is what allows the CE to do all these amazing things. Time perhaps spent by other people reading gossip magazines about Brad & Jen's wedding/breakup/etc, watching the football and knowing every baseball player's stats (er, I don't know jack about sports, but you get the idea) - but the CE owes everyone (who doesn't know basic computing and who can't be bothered to read the help or manuals) everything they know.

I'd suggest a few reasons for this, but essentially it's cultural. That's just what has happened 'til now, and people expect it. People (generalisation) are stupid, lazy, greedy, unreasonable, unsympathetic, and a lot of other terrible things besides. Unless there is a massive push, public campaign, whatever, then the situation isn't likely to change for the CE any time soon. Other professions have "built in defences". Legal, financial, medical, engineering (and likely other) people are, in many cases, legally/ethically/morally obliged NOT to offer free advice, assistance, etc (at least not without some formal agreement). Hairdressers don't (generally, maybe some do) offer free haircuts to everyone they know, all their neighbours and their neighbours' friends. It would only cost them some time (and maybe have some scissors handy). Just the same as it would only cost the CE some time.

For the critic(s) who suggest that a programmer isn't worth their salt if they can't do XYZ "general computer tasks" is kidding themselves. Although they are helpful (perhaps essential, depending on the particular environment, additional support and general requirements of the task at hand), some (not all) programming tasks are based in mathematics, logic, reasoning and general design. Hard to find bugs are often found looking at code in hardcopy form - away from a computer - where a general spatial awareness of the logic, or a change in legibility/focus, can make all the difference. Very few designs start in a computer. They start in the mind, and often find their first representation on scraps of paper. The programmer's task is to produce some result (produce a program, probably!). Just as an account might use a spreadsheet / other computer tools to maintain "the books", sort out payroll, etc. Some programmers deal with operating systems, user inerfaces, device drivers, network protocols, mail clients, or whatever. Others don't. There have probably been more books written on the subject of computing (and doing various things with computers) than anything else in history (I just made that up - don't quote me on it), and it's only a new field, especially in terms of consumer involvement. It's hardly fair that someone be expected to know it all... even if they think they do. ;o)

Of course, this has been a more general gripe than Brian's, which was that people assume the CE really knows everything (for example how to sort out a Windows registry problem caused by dodgy software installed while searching for porn), and to find stuff out for them if you don't know.

I think, overall, the saying "I don't know" routine comes about from avoiding fronting people for payment or other compensation. My suggestion: as going from offering free help to saying "that'll be fifty bucks" could be a bit abrupt (something friends and family might not understand!), start small. Try something like "yeah, I've got time to come over for dinner and have a look at it for you", or "sure, can you (get me a drink / buy me some lunch / go to the postoffice for me / pick up my kids / do the dishes) while I look into it?".

If you are in a position where you have a lot of people around looking for help (say in the neighbourhood or extended family), start making it known that you will offer general compuer help at X dollars to start with an hourly rate. You can then negotiate "mates rates" from there, and maybe your "mates" will start to value your help a bit more.

My computing background... I've recently quit my job as an analyst programmer, which I was working full-time for six and a half years. From a young age I've always been asked to help with things ranging from setting clocks, tuning TVs, connecting audio / video equipment, fax and answering machines, and of course everything compuer related. I didn't even have an "IBM compatible" PC until third year uni, but used to tool about quite a bit on my Amiga (which arrived in the household just before I started highschool). In year six - before I even had a computer at home - I was my school's "computer expert". There was a lab next to my classroom with a buch of Microbee machines. I really didn't know anything much about them, but I would get called out of class to help other teachers with whatever they were doing for their class. Of course I loved it at the time, but it wasn't exactly beneficial to my education (after all, I was missing out on class). I don't consider myself to be an expert, though, by any means. I know how to use Windows pretty well, but I don't know how it works, certainly not in any detail. My programming job was for software running on Sun servers - mainly C programming with embedded SQL. When I first started at the company I had Tektronix X terminal on my desk. The X terminals were replaced by PCs, but still coding using an X server with a Solaris desktop (mail, web browsing and tooling about of course in Windows).

sub:text / pixel:text

.text created as an adjunct to .pixel - sub:text, or wordy posts, for sub:pixel.