Wednesday, March 19, 2014

It actually makes sense to implement your own sort

My mantra with algorithms is usually "somebody has probably already done it better." Why implement a sort algorithm if one already exists in your language?

With that it mind, it was a mere academic endeavor to implement Quicksort in JavaScript. I tried populating an array with a million random numbers, fully expecting Array.sort() to blow away my custom quicksort.

But guess what?

It didn't.

I ran some tests in node.js, and Array.sort() always came in last.
Array.sort() converts numbers to strings and then sorts them. For string sorting, it would probably blow away anything you could implement in JavaScript. However, for numbers, a custom sort wins.

Here are the times (in milliseconds) for sorting 1,000,000 integers

array sort (function(a,b) {return a-b;}): 518
quickSort: 235
array sort: 930

The native Array.sort() is the slowest. It returns invalid results with 999 showing up near 9996 since it is a text rather than numeric sort.

Ok, so if you are going to be sorting a huge number of integers, making your own quicksort is the way to go. But if you are looking at strings, the native sort is the way to go, right? Alas, no. For the next sample, I created 1,000,000 strings of 13 random uppercase characters and ran them through our three different scenarios. The quicksort could be used as is (the comparisons work on strings just as well.) The named sort function needed to modified slightly to handle the new sort:


function(a,b) {
if(a<b) { return -1; }
if(b<a) { return 1 };
return 0;
}


In this case, I'm just using capital letters. If there other characters involved (such as umlauts or accents), localeCompare should be used to get more appropriate results.

text sort of text array: 6625
quicksort sort of text array: 4091
named function sort of text array: 5007

Again, quicksort was the fastest, a custom function came in second, and the native sort was last. The percentage difference was not as great as with the integer sort, but the overall time difference was even greater.

The moral of this story: In most cases you will want to use your own sort function for both speed and accuracy. If you are sorting a small number of items, simply plugging a compare function into sort is probably all you need. If there are a large number of items, it would pay to implement your own sort code.

Tuesday, March 18, 2014

Data Structures and Algorithms with JavaScript

I was hoping this would be a nice advanced JavaScript programming book that would cover implementing common algorithms and data structures in JavaScript. Alas, it is instead geared towards the beginner college student. The coding examples all seem to "work" as stand alone exercises. However, they are coded in a global style that would not allow them to be extended. They use an "Easy to read" object-oriented style that flies in the face of best practices. Many also seem to reinvent the wheel. (Why create a meta-list structure that merely duplicates the pop and push operations found native on an array?)

The algorithms are also quite basic without going into great detail or even providing optimal implementations.

A much better place to look for algorithms and data structures in JavaScript is the Computer Science in JavaScript series of posts by Nick Zakas.

JavaScript Patterns

JavaScript Patterns focuses on patterns used to solve problems in JavaScript. The focus is on the language itself, with only a single chapter dedicated to browser. This is a "quality" book for advanced JavaScript programmers. It presents many of the appropriate patterns unique to doing things the "JavaScript way". It also contains a chapter on traditional object oriented design patterns in JavaScript. (These are covered in a chapter. Some are still useful in JavaScript, while others tend to be more of an academic exercise.) This book was written by somebody that knows their stuff.

High Performance JavaScript

Since this book was written in 2010, a lot has changed (and a lot has remained the same.) There are some small tweaks outlined that help gain a few microseconds here and there. Alas, many of these were already being "tweaked" out of the browser as this book was written and are now fairly irrelevant. (The applications that would benefit the most are probably not even going to be able to run in Internet Explorer 6, thus making some of these fixes totally moot.) Other bits are, however, still relevant. I'd put it more on a continuum. Some things are pretty much not worth your effort today. Others are absolutely worthwhile. And in between there are plenty of ideas that may be good in special cases.

The book includes chapters written by a number of different co-authors. Many of these authors were working at Yahoo! - back when Yahoo! was a strong innovative company. (There is still some innovation going on at Yahoo! Alas, it seems the ratio of innovation to "junk" has been decreasing.) Each author has his own style.

This book is a good candidate for a "new version" that spends some more time on algorithm enhancements, and particular areas of improvement.

The Book of A Thousand Nights and a Night (Arabian Nights), Volume 01

Excruciating is the best word to describe my experience listening to this. The librivox recording of the Burton translation was fairly well performed. There were some really good sections and no all-out-bad sections. However, the content seemed to meander through nowhere. There are a few stories that stick out. But, a lot of it seems like the work of a junior high student with a thesaurus. I think I'm going to skip the remainder of the volumes of this and opt for another translation.

The Power of Habit: Why We Do What We Do in Life and Business

I had thought I wrote about this book earlier. I guess I just have a habit of delaying. Hopefully this book will get me out of the bad habits.

The book is grounded in the science of how habits influence and control our lives. Even after severe brain trauma, some habits can remain, allowing us to perform tasks without thinking. These "automatic" behaviors are a result of the habits that we have developed. Typically, the behavior starts out as a planned action until it is gradually repeated enough to become an ingrained habit. These habits are often difficult to control or change. Sometimes the only way to alter damaging habits is to run "indirection". An alcoholic may seek alcohol after a stimulus. The drinking is the habitual activity used to produce the response. To rewire the brain an alternate activity needs to be habitually substituted for the negative one in order to provide the appropriate response. Often faith in a higher power is needed to help fully rewire the brain from addictive behavior.

Habits can also be beneficial. Professional football players perform better when they let their well-trained habits guide them rather than trying to over-analyze the situations. We can all create positive habits in our life to help us to achieve our goals.

While the title of the book includes "business", that appears to be habitually tagged on to drive sales. This is a book geared primarily towards the individual seeking to improve their life and fill it with good habits.

Monday, March 03, 2014

Physics of the Future

This book would make a great source of inspiration for science fiction novels. There are chapters here about energy from space, nuclear fusion, nanobots and all sorts of technology. The author even peppers the book with actual science fiction allusions. (Star Trek - money? What's that. Nanobots can make everything. However, an emotionless android would not be capable of being a good crew member. Honey I shrunk the Kids? Nope, physics would be totally different at the small level. Terminator? AI research is probably a long way off from getting a senscient computer.)

The book's fault is that it seems to be extremely optimistic towards the progress of science. It does acknowledge the "caveman principle" that we may like contact and physical stuff. Some inventions like the paperless office are doomed to fail because of this. (Or are they? Offices do seem to be getting more and more paperless. It is just not a sudden thing.) Face to face visits are still needed for all the personal contact. However, even beyond these there is the cost of the "Technology". Even if we could create technology to eliminate all our work, would we? If nanobots could produce anything for nothing, accumulation of "stuff" might be simple. But what about property? That is still scarce. We seem to be drowning in too much affluence. We could make automatic cars, but what about the roads? Where would we park all the cars? Reducing pollution might be a nice goal, but what about all the other impacts of cars? And what if medicine could cure just about every disease automatically through little chips. Would we simply become computers? Maybe our destiny is to design the new computers that will be our robotic progeny? Or perhaps a terrorist will use some of it to wipe out most of the earth, and send the world back into a dark age. Or we may even go the way of the dinosaurs.

I want to check out Jules Verne's Paris of the 20th century. I wonder how accurately his view of the future sounded. The problem with future predictions is that it never really goes forward linearly. Some new idea may disrupt the entire train of research. Or a physically inferior form of technology may get a huge amount of money behind it and inflict itself upon the market. Looking at what science can logically be able to do may be a good start. (I didn't realize we actually had fusion now, just not practical fusion.) However, things are never that linear in real life.

He also talks about the phases that things go through. At one time books were precious commodities. Then the price came down where everybody could afford them. Then everyone could afford a library. And now paper is a number one source of trash and books are often more about "fashion statements". He predicts computer chips will follow the same path. They will become embedded everywhere and eventually become a source of much trash. However, he predicts Moore's law will eventually collapse, bringing down much of Silicon Valley with it. (Ah, there is an issue. Silicon Valley has become more of an "innovation" and software hub than a chip producing location. Less rapid increases in processing may change some of the focus on computing, but probably wont be vary disastrous on the area as a whole. Even recently, focus has downshifted to the less powerful mobile devices. If hardware innovation slows, we can expect a lot more in the software innovation front.)

Discussion of economics also gets a little fuzzy. According to the author, all economic bubbles were caused by technological innovation. The previous generation's bubbles were forgotten and thus a new bubble. The bubble happens when the financiers of the new technology have more money than they know what to do with. The actual use of it happens later. The 19th century panics were caused by railroad money. However, the railroad was eventually expanded, providing the benefit. The real estate bubble was caused by internet money needing a place to go. This explanation makes sense on the surface, but seems a little too simplistic in practice.

This book does provide a good overview of technologies that are on the cusp of widespread commercialization. It has, perhaps, a little too much faith in its scientific predictive powers (especially when it veers into the social realm.) However, it still provides lots of fodder for futuristic immaginations.