Run-length encoding: Difference between revisions
→{{header|Picat}}
(Rescued TMG entry.) |
|||
Line 4,157:
echo decode('12W1B12W3B24W1B14W'), PHP_EOL;
?></lang>
=={{header|Picat}}==
Three different approaches:
* plain while loop: rle/1
* using positions of different chars: rle2/1
* recursion: rle3/1
Encode and decode (only using rle3/1):
<lang Picat>
go =>
S = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA",
println(S),
RLE = rle3(S),
println(rle=RLE),
D = rl_decode(RLE),
println(D),
if D == S then
println(ok)
else
println(not_ok)
end,
nl.
%
% While loop. Quite slow.
%
rle(S) = RLE =>
RLE = "",
Char = S[1],
I = 2,
Count = 1,
while (I <= S.len)
if Char == S[I] then
Count := Count + 1
else
RLE := RLE ++ Count.to_string() ++ Char.to_string(),
Count := 1,
Char := S[I]
end,
I := I + 1
end,
RLE := RLE ++ Count.to_string() ++ Char.to_string().
%
% Using positions of different chars. Much faster than rle/1.
%
rle2(S) = RLE =>
Ix = [1] ++ [I : I in 2..S.len, S[I] != S[I-1]] ++ [S.len+1],
Diffs = diff(Ix),
RLE = [Diffs[I].to_string() ++ S[Ix[I]].to_string() : I in 1..Diffs.len].join('').
% Recursive approach. The fastest version.
rle3(S) = RLE =>
rle3(S.tail(),S[1],1,[],RLE).
rle3([],LastChar,Count,RLE1,RLE) =>
RLE = (RLE1 ++ [Count.to_string(),LastChar.to_string()]).join('').
rle3([C|T],LastChar,Count,RLE1,RLE) =>
C == LastChar ->
rle3(T,C,Count+1,RLE1,RLE)
;
rle3(T,C,1,RLE1++[Count.to_string()++LastChar.to_string()],RLE).</lang>
{{out}}
<pre>WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA
rle = 12W1B12W3B24W1B14W1A
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA
ok
</pre>
Benchmark on a larger string (30_000) clearly shows that rle3/1 is the fastest.
<lang Picat>% Benchmark on larger strings
go2 =>
_ = random2(),
Alpha = "AB",
Len2 = Alpha.len,
_ = random2(),
S = [Alpha[random(1,Len2)] : _ in 1..30_000],
if S.len < 200 then println(s=S) end ,
println("rle/1:"),
time(_=rle(S)),
println("rle2/1:"),
time(_=rle2(S)),
println("rle3/1:"),
time(_=rle3(S)),
nl.</lang>
{{out}}
<pre>rle/1:
CPU time 4.02 seconds.
rle3/1:
CPU time 2.422 seconds.
rle3/1:
CPU time 0.812 seconds.</pre>
=={{header|PicoLisp}}==
| |||