As I worked on a better solution, I figured out a great use for the new JS Iterators & Generators, which I've been reading about. I spent probably 6 hours today fiddling with this solution, and it was worth every minute. You've got some formatting errors, but I'm going to focus completely on performance and leave the formatting to the other reviewers.
Running this against a big word will fry your machine
Ok, so maybe that's going a little too far, but seriously, this is an expensive function. I'm no math guru, so I asked this question on Math.SE.
The formula for calculating the number of possible combinations is extremely steep:
Think of it like this:
How many choices do you have for the first letter? Four: 4_ _ _ _.
For the second? Three: 4⋅3 _ _.
Continue like this and you find there are 4⋅3⋅2⋅1=4!=24 choices in total. - MrRicci
Running your function against the word "Encyclopedia" will result in a definite page crash if you run it client-side. So to fix that, I did some thinking.
Bear with me - This gets more and more relevant as you read.
I wanted to try generating real words (Having some fun with the codez)
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once - Wikipeda
When I think of an anagram, I think of the result being real words or phrases. Now, while the purpose of this code review isn't to change the functionality of your code, I couldn't help but want to have some fun with it. So I decided to search for a solution that would allow me to filter out and print any real word anagrams from the result.
Once I finally tracked down a plain text string of ~130,000 English Words to use as my word list, I then needed to convert this list into JS. So I built a function to slice the string at each space, and print out the structure for an object with keyed properties, so that I could very quickly test for the validity of any word via worldList['word'] -> returns true if word is valid.
Printing out a list of 130,000 words into the document body as a JSON string is, like your function, very expensive.
... And the relevance:
So here's where your problem meets the one that I invented for myself. How do you process a very expensive loop without crashing a webpage?
In experimenting with the possibilities, I actually discovered a way to allow my function to handle 130,000 words, and your function to sustain a word of any size, by balancing the workload over time.
Loops are sometimes too fast for their own good
Loops are made to be as fast as possible, which is perfect for most of the tasks we use them for in web pages. But if we ask them to handle too much, the browser can't handle it.
So I needed a solution that would allow me to distribute the work load over time, in order to allow the page to handle expensive loops without an issue.
My solution was to build a manual loop via a function that called itself x times, inserting a 1-2ms delay between iterations. This gave the page enough time to handle the loop, which, without the delay, processed words insanely fast until the C's before crashing each time. This worked great for generating my JSON word list structure.
But a delayed loop was extremely tricky to implement in your already recursive function.
I realized then that this is the perfect situation to utilize a solution that I recently read about for JavaScript...
JavaScript Iterators and Generators
So, here come JavaScript Iterators & Generators to the rescue.
Now, this review is already a risk of becoming a monster, so instead of explaining Generators, I'm going to quote this soon to be popular answer's one-liner:
TL;DR: the essence of [using a] generator is controlling the suspension of code execution.
And explain simply that generators are in improved way of implimenting iterators.
You can read the rest for yourself in the answer there. If that answer doesn't quite do it for you, you can improve your understanding via the following resources:
Now, Generators have big potential in the task of avoiding callback hell, but we're going to be using them here not for formatting & structure, but for performance, which is (in my performance-biased opinion) the most elegant reason to use them.
I'm not sure yet whether the generators are the best solution here, but they're the best idea that I have, and this is an excuse to try them out.
Your Code With Generators
Working on this solution still. It should work just fine, I just don't have time to finish just yet, and wanted to offer the improved code sooner rather than later. I'll post this solution soon.
And Finally, Since Generators are new and not supported everywhere yet.. An improved version of your code without them
Note: My formatting practices are generally my own readability preference rather than best practice. Don't feel obligated to format your code this way.
/* Improved Real Time Anagram Engine */
// Without generators, it's difficult to write this function
// with the capability of processing a word of any length without
// crashing the web browser, so this is written as the original,
// with non-controlled execution speed. Long (9+ char) words may
// crash browser.
function generateAnagrams(word) {
if (word.length < 2) {
return [word];
} else {
// By declaring all variables outside of the loop,
// we improve efficiency, avoiding the needless
// declarations each time.
var anagrams = [];
var before, focus, after;
var shortWord, subAnagrams, newEntry;
for (var i = 0; i < word.length; i++) {
before = word.slice(0, i);
focus = word[i];
after = word.slice(i + 1, word.length + 1);
shortWord = before + after;
subAnagrams = generateAnagrams(shortWord);
for (var j = 0; j < subAnagrams.length; j++){
newEntry = focus + subAnagrams[j];
anagrams.push(newEntry);
}
}
return anagrams;
}
}
var result = generateAnagrams(word);
By declaring variables outside of the loops, we save significantly, as you'll see in the results. Also, I believe word.slice() performed slightly better than word.substr(). between the two of those optimizations, this code performs better than your original code.
And Last but not Least, the performance results!
- "code", 4 chars : 24 results, ~1ms
- "coder", 5 chars : 120 results, ~1ms
- "codere", 6 chars : 720 results, ~6ms
- "coderev", 7 chars : 5040 results, ~11ms
- "coderevi", 8 chars : 40,320 results, ~75ms
- "coderevie", 9 chars : 362,880 results, page fail
- "codereview", 10 chars : 3,628,800 results, page fail
- "code", 4 chars : 24 results, ~0.5ms
- "coder", 5 chars : 120 results, ~0.5ms
- "codere", 6 chars : 720 results, ~1.5ms
- "coderev", 7 chars : 5040 results, ~8ms
- "coderevi", 8 chars : 40,320 results, ~53ms
- "coderevie", 9 chars : 362,880 results, ~556ms
- "codereview", 10 chars : 3,628,800 results, page fail
Real-Time with Generators
- "code", 4 chars : 24 results, TBA
- "coder", 5 chars : 120 results, TBA
- "codere", 6 chars : 720 results, TBA
- "coderev", 7 chars : 5040 results, TBA
- "coderevi", 8 chars : 40,320 results, TBA
- "coderevie", 9 chars : 362,880 results, TBA
- "codereview", 10 chars : 3,628,800 results, TBA
I used console.time() to achieve measurements accurate to the nearest millisecond, completing 3-5 trials each, and estimating a general average based on the results. These results will of course vary from machine to machine. The time comparisons are the key to reading benchmarks, not the speeds.
Tl;Dr Summary, as promised
Loops are an extremely powerful tool in programming, but they don't handle monster numbers of expensive iterations well in the web browser. Expensive looping functions like this perform perfectly, however, if you distribute the workload over time. One interesting way to do this is to use JS Generators, a new toy available in web stores today, but not necessarily in the local markets, so use with care until JS 2.0 is more widely implemented! By utilizing the power of JS generators, we can manage long-running expensive processes without seeing any performance issues.
