[erlang-questions] Library proposal: O(N+M) suffix/2
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 ).
Since this is a compatible change, we will include it R13A.
Björn Gustavsson, Erlang/OTP, Ericsson AB
More information about the erlang-questions