public
Last active

Longest Common Prefix in Erlang

  • Download Gist
LCP.pm
Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
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;
erl shell session
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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
Erlang
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
-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).
lpc.pl
Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#!/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/

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.