Longest Common Prefix in Erlang

erl shell session

1> c(lcp).    
{ok,lcp}
2> lcp:test().
ok
3> lcp:bench().
ok
4> timer:tc(lcp,bench,[1000000]).
{6516280,ok}
5> 6.516280. % BEAM time in seconds
6.51628
6> 86.1727988666554/v(5). % perl vs BEAM
13.224232056734119
7> c(lcp, [native,{hipe,[o3]}]). 
{ok,lcp}
8> timer:tc(lcp,bench,[1000000]).
{3071970,ok}
9> 86.1727988666554/3.071970. % perl vs HiPE
28.051315236364744

lcp.erl

-module(lcp).

-export([lcp/1, test/0, bench/0, bench/1]).

lcp([]) -> [];
lcp([S]) -> S;
lcp(L) -> lcp_(L).

lcp_([[H|T]|R]) ->
  case strip(H, R, []) of
    false -> [];
    Ts -> [H|lcp_([T|Ts])]
  end.

strip(_, [], Ts) -> Ts;
strip(H, [[H|T]|R], Ts) -> strip(H, R, [T|Ts]);
strip(_, _, _) -> false.

test_data() -> [
    "file:///home/gms8994/Music/t.A.T.u./",
    "file:///home/gms8994/Music/nina%20sky/",
    "file:///home/gms8994/Music/A%20Perfect%20Circle/"].

test() ->
  [] = lcp([]),
  "abc" = lcp(["abc"]),
  [] = lcp(["abc", "xyz"]),
  "abcd" = lcp(lists:duplicate(16,"abcdefgh") ++ ["abcdxyz"]),
  "file:///home/gms8994/Music/" = lcp(test_data()),
  ok.

bench() -> bench(200000).

bench(0) -> ok;
bench(N) ->
  lcp(test_data()),
  bench(N-1).

LCP.pm

use strict;
use warnings;

package LCP;

sub LCP {
    return '' unless @_;
    return $_[0] if @_ == 1;
    my $i          = 0;
    my $first      = shift;
    my $min_length = length($first);
    foreach (@_) {
        $min_length = length($_) if length($_) < $min_length;
    }
INDEX: foreach my $ch ( split //, $first ) {
        last INDEX unless $i < $min_length;
        foreach my $string (@_) {
                last INDEX if substr($string, $i, 1) ne $ch;
        }
    }
    continue { $i++ }
    return substr $first, 0, $i;
}

# Roy's implementation
sub LCP2 {
    return '' unless @_;
    my $prefix = shift;
    for (@_) {
        chop $prefix while (! /^\Q$prefix\E/);
        }
    return $prefix;
}

1;

lpc.pl

#!/usr/bin/env perl

Test::LCP->runtests;

package Test::LCP;

use base 'Test::Class';
use Test::More;
use Benchmark qw(:all :hireswallclock);

sub test_use : Test(startup => 1) {
    use_ok('LCP');
}

sub test_lcp : Test(6) {
    is( LCP::LCP(),      '',    'Without parameters' );
    is( LCP::LCP('abc'), 'abc', 'One parameter' );
    is( LCP::LCP( 'abc', 'xyz' ), '', 'None of common prefix' );
    is( LCP::LCP( 'abcdefgh', ('abcdefgh') x 15, 'abcdxyz' ),
        'abcd', 'Some common prefix' );
    my @str = map { chomp; $_ } <DATA>;
    is( LCP::LCP(@str),
        'file:///home/gms8994/Music/', 'Test data prefix' );
    is( LCP::LCP2(@str),
        'file:///home/gms8994/Music/', 'Test data prefix by LCP2' );
    my $t = countit( 1, sub{LCP::LCP(@str)} );
    diag("LCP: ${\($t->iters)} iterations took ${\(timestr($t))}");
    $t = countit( 1, sub{LCP::LCP2(@str)} );
    diag("LCP2: ${\($t->iters)} iterations took ${\(timestr($t))}");
}

__DATA__
file:///home/gms8994/Music/t.A.T.u./
file:///home/gms8994/Music/nina%20sky/
file:///home/gms8994/Music/A%20Perfect%20Circle/