[erlang-questions] Interleave binaries

[Jeff Schultz]

On Fri, Aug 05, 2011 at 10:26:16PM +0100, Bob Cowdery wrote:
> I'm wanting to interleave two binaries.
> 
> Bin1 = <<0,1>>,
> Bin2 = <<2,3>>,
> << <<A,B,C,D>> || <<A,B>> <= Bin1, <<C,D>> <= Bin2 >>.
> <<0,1,2,3>>
> 
> Bin1 = <<0,1,2,3>>,
> Bin2 = <<4,5,6,7>>,
> << <<A,B,C,D>> || <<A,B>> <= Bin1, <<C,D>> <= Bin2 >>.
> <<0,1,4,5,0,1,6,7,2,3,4,5,2,3,6,7>>
> 
> whereas I want:
> <<0,1,4,5,2,3,6,7>>
> 
> I know what it does is what the documentation says but is there a way to
> get a pure interleave efficiently. Perhaps there is a filter that would
> work or a way to reduce the binary after merging without stepping
> through the whole thing.

I'd go via an intermediate list:

25> Bin1 = <<0,1,2,3>>, Bin2 = <<4,5,6,7>>.
<<4,5,6,7>>
26> list_to_binary(
	[[binary:part(Bin1, I, 2), binary:part(Bin2, I, 2)]
	|| I <- lists:seq(0, byte_size(Bin1) - 1, 2)]).                                              
<<0,1,4,5,2,3,6,7>>

Makes O(N) garbage.


If you want a bit string comprehension, try

27> << <<P1/binary, P2/binary>>
    || I <- lists:seq(0, byte_size(Bin1) - 1, 2),
    P1 <- [binary:part(Bin1, I, 2)],
    P2 <- [binary:part(Bin2, I, 2)]>>.
<<0,1,4,5,2,3,6,7>>

(I may be missing some syntax trick here.  Ugly, isn't it.)

I have no idea how efficient that is.  The naive implementation would
be O(N^2).  Even a clever one would make O(N) garbage, though unlike
the list comprehension, it might not hang on to all of it at once.


    Jeff Schultz