[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: What is the runtime complexity of $(filter )?
From: |
Philip Guenther |
Subject: |
Re: What is the runtime complexity of $(filter )? |
Date: |
Fri, 8 Jan 2010 10:29:18 -0800 |
On Fri, Jan 8, 2010 at 9:33 AM, Peng Yu <address@hidden> 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