[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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]