I’ve had some free time lately and I finally got around to improving and polishing my Words with Friends anagram solver like I’ve been meaning to. I converted it from HTML + jQuery to GWT with a declarative UI, and it’s a lot nicer - both in terms of the codebase and the UI. Adding more of a split like that also allowed me to throw in some unit tests, which gave me the confidence to play around with my original algorithm.
I changed it to alphabetize the words before it adds them to the Trie (e.g. “dog” and “god” become “dgo” and are both stored at the same node). This will reduce the amount of time that it takes to look up any word by a significant margin. If you have the letters “dofga”, it will now alphabetize it to adfgo and then it only needs to look up adfgo, afgo, ago, ao, dfgo, dgo, do, etc. as opposed to every permutation of those letters.
There was a problem, though. It did significantly increase the speed of looking up words. However, any time where you specify necessary start, contains, or end strings it now needs to add all those letters to the word that is searched and filter the results at the end. This is a major use case and it is much slower, leading to an overall decrease in speed so that I had to revert all the changes.
After that, I decided that I wanted to persist the dictionary structure in the Datastore to reduce the long (~30s) wait times whenever Google App Engine needs to spin up a new instance. It took me a couple hours to get this set up (I’ve never worked with the Datastore before). I actually needed to rewrite a portion of my algorithm because the Datastore doesn’t support persisting any sort of map, which is what my Trie structure is based off. After I finally got all of that working, I found out that the object I was trying to store in the Datastore was too large, and I had to revert those changes too. Great.
No comments:
Post a Comment