2011-12-30
David R. Hedges

Source/Prefix List Merge Readme
-------------------------------

Forward:
--------
My first implementation was done in Python, now titled mergeClassic, largely because my pseudocode commonly isn't too far off from Python code.
I then verified this with a brute force, but not quite as efficient "unit test" implementation, found in mergeTest.py, complete with a number of source and prefix lists, some of which were specifically designed to exercise certain code branches, and others randomly generated or scraped from wordlists to identify potential unanticipated issues.

Following the initial implementation and test code, I took a slightly different path, and thought it'd be fun to implement the algorithm visually in a browser. A very basic server-side php page handles user list input and unsorted display, while the actual merging takes place in javascript, in order to easily provide the user with visual feedback of the merge. Source items getting merged become colored "salmon," while prefix items being merged become purple. Although the actual merge happens very quickly, artificial delays are introduced in the coloration/display of list items in order to make the visual experience easier to follow.

Lastly, I thought it would be interesting to take advantage of the parallelizability of solving this problem, and the multiple cores present on nearly all machines these days, so wrote a multi-threaded implementation of the algorithm. While additional complexity was introduced here, I decided to avoid the considerably higher complexity that would have been required to support more than two threads operating on the list concurrently.

Especially in the multi-threaded implementation, some code complexity could be reduced by increasing the space and possibly time-complexity requirements of the algorithm (e.g. by using a hash instead of a sorted list). Additionally, it became evident during the course of the multi-threaded implementation that decisions and assumptions made during the initial implementation for the sake of efficiency didn't hold up as well when iterating backward through the list, so the maintainability could be improved there with a different approach.


How to run:
----------
On a system with python installed, extract pyMergeLists. Set the execute permission on the files, if necessary (chmod +x *py). If a python interpreter is not located in /usr/bin/python , the first line of the files should be updated to point to the correct location.

From the pyMergeLists extracted directory, you can either run ./main.py (or python main.py) to execute a single run (and modify the source and prefix list contained therein) and see the result, or run ./mergeTest.py to execute a fully battery of tests and see the results (true/false for pass/fail).


Web-based:
---------
Place mergeLists.php and merge.js in the same directory on a web server configured to execute PHP scripts, and then navigate to that page from a browser (or visit http://p14nd4.com/code/mergeLists/web/mergeLists.php ). Enter a space-separated list for the source and prefix, click submit, and on the resulting page, click 'Merge'.