The minimum number of data passes is two, one for each submitted sample. The Pretty Diff algorithm, in the subject of this thread, uses three complete passes through data without any repetition. Therefore the number of iterations is simply: total number of lines of the first sample, total number of lines of the second sample, and the total number of lines of the smallest sample.
A more optimized approach is 2 complete passes and a partial third pass without repetition. Achieving that optimization requires more logic up front to populate a smaller central analysis store and a different means of iterating through that container.
Most approaches, as I have seen them, don't achieve a fully optimized approach. While they may not have complete passes through data (after the required initial two) they tend to have numerous smaller passes in order to derive edit distances. This could be more efficient if these smaller passes never pass through the same data indexes/keys more than once and achieve a reduced total number of iterations. These approaches seem less straight forward to me and are misleading in terms of total statements of execution/iterations.
The only way to guarantee greater execution efficiency is to run through a checklist like this and compare clock times in similar execution contexts:
A more optimized approach is 2 complete passes and a partial third pass without repetition. Achieving that optimization requires more logic up front to populate a smaller central analysis store and a different means of iterating through that container.
Most approaches, as I have seen them, don't achieve a fully optimized approach. While they may not have complete passes through data (after the required initial two) they tend to have numerous smaller passes in order to derive edit distances. This could be more efficient if these smaller passes never pass through the same data indexes/keys more than once and achieve a reduced total number of iterations. These approaches seem less straight forward to me and are misleading in terms of total statements of execution/iterations.
The only way to guarantee greater execution efficiency is to run through a checklist like this and compare clock times in similar execution contexts:
* total number of loop iterations
* fewer instructions
* instruction optimizations (compiler/interpreter dependent considerations)