On Fri, Jan 8, 2010 at 9:33 AM, Peng Yu <[email protected]> wrote: > I run $(filter ) with each argument of thousands of strings. It runs > slow. I'm wondering what the run time complexity of $(filter ) is. > Suppose I have n strings for each argument. Is the run time complexity > n*n or log(n)?
It's effectively of complexity O(n). The proportion of words actually matched affects it slightly, but at least on my box the effect seems to max out at about 10%. For example, when filtering a list of 1,000,000 words, if the filter matches *none* of them it takes 148 seconds, if it matches *all* of them it takes 165 seconds. 148/165 = ~90%. Philip Guenther _______________________________________________ Help-make mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-make
