> I imagine you get to linear time without much loss by heuristically throwing out chunks of the table where i is far from j.
I originally tried a delete as you go approach to the hash map where you remove entries that were no longer needed, such as when both values (counts) for a given key reached 0. My thinking was that this would improve execution speed over the space of a very large table by gradually reducing the key space and thus reducing look up times. This thinking proved false against two 1.7mb code samples. Removing this set of instructions reduced execution time from an average of 0.95 seconds to an average of 0.71 seconds (on my machine and browser). It is simply more efficient to read from a large hash map than it is modify that hash map to improve reading efficiency.
A better approach, which I have not tried, would be to reduce writes to the hash map at the time of running through the second code sample, because you have already gone through the first code sample and not yet performed your formal analysis. To be efficient enough for a valid performance improvement though the analysis at this point would have to be tiny and yet somehow benefit for the formal analysis coming in the next step. The underlying assumption is that having a smaller hash map means fewer writes to memory. To be helpful to the next step of formal analysis the loop would have to achieve fewer iterations.
> The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file?
As a code author I cannot predict user behavior and do not try. Instead I make assumptions upon that behavior and execute to these assumptions, whether or not they are valid. My assumption is that if a user wishes to compare unrelated things the number of differences sky-rockets, which means a bit more computation and temporary data. I suspect that if a user does this it is probably for some exploratory reason and thus are better prepare for the trivial increase in processing.
I originally tried a delete as you go approach to the hash map where you remove entries that were no longer needed, such as when both values (counts) for a given key reached 0. My thinking was that this would improve execution speed over the space of a very large table by gradually reducing the key space and thus reducing look up times. This thinking proved false against two 1.7mb code samples. Removing this set of instructions reduced execution time from an average of 0.95 seconds to an average of 0.71 seconds (on my machine and browser). It is simply more efficient to read from a large hash map than it is modify that hash map to improve reading efficiency.
A better approach, which I have not tried, would be to reduce writes to the hash map at the time of running through the second code sample, because you have already gone through the first code sample and not yet performed your formal analysis. To be efficient enough for a valid performance improvement though the analysis at this point would have to be tiny and yet somehow benefit for the formal analysis coming in the next step. The underlying assumption is that having a smaller hash map means fewer writes to memory. To be helpful to the next step of formal analysis the loop would have to achieve fewer iterations.
> The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file?
As a code author I cannot predict user behavior and do not try. Instead I make assumptions upon that behavior and execute to these assumptions, whether or not they are valid. My assumption is that if a user wishes to compare unrelated things the number of differences sky-rockets, which means a bit more computation and temporary data. I suspect that if a user does this it is probably for some exploratory reason and thus are better prepare for the trivial increase in processing.