[erlang-questions] Library proposal: O(N+M) suffix/2

Bjorn Gustavsson bgustavsson@REDACTED
Tue Feb 10 08:00:34 CET 2009


On Tue, Feb 10, 2009 at 4:11 AM, Richard O'Keefe <ok@REDACTED> wrote:
> The lists module in Erlang's standard library
> offers a function lists:suffix(Suffix, List)
> which takes O(|Suffix|.|Lists|) time.
> Most of this is spent inside the head testing
> whether List is equal to Suffix yet; the rest
> of the work is O(|List|).
>
> It is possible to implement this function in
> O(|Suffix| + |Lists|) time, and I propose that
> it should be done.  Here's the code:
>
> suffix(Suffix, List) ->
>     Delta = length(List) - length(Suffix),
>     ( Delta >= 0 andalso nthtail(Delta, List) =:= Suffix ).
>

Thanks!

Since this is a compatible change, we will include it R13A.

/Bjorn

-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB



More information about the erlang-questions mailing list