Back to Questions
3.7k
views5
comments
Check bitArray for "Equal"
f#

Dear All:
I want to write a function to compare some 8 bytes binary data.
++++++++++++++++++++++++++++++++++++
#light
open System
open System.Collections

let bits64Zero : BitArray = new BitArray( 64, false )
let A1 : BitArray = new BitArray( 64, false )
let A2 : BitArray = new BitArray( 64, false )
let A3 : BitArray = new BitArray( 64, true )
let mutable bytes : byte[] = Array.zeroCreate 8

let Test1 = A1.Xor(A2)
Test1.CopyTo(bytes, 0)
if (Test1.Equals(bits64Zero) = true) then
printfn "Equal"
printfn "Done"
++++++++++++++++++++++++++++++++++++

I am thinking that if A1 and A2 are the same, so all the 64 bits are the same, then if I do an XOR for A1 and A2, then the result will be a 64-bit number with all 64 bits are 0; if I don't know how to judge all 64 bits without using a loop to search each bit; the built-in function in F# seems not working, as my above code did NOT show "Equal", the result is "NOT" Equal. Since the compare will be performed millions of times in my program, so I need "fast" version. (A1 and A3 are different, so the XOR result has some '1' inside, not all '0's)
Anyone can find a better way, please show me your code.
Thanks,

.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

open System
open System.Collections

let A1 : BitArray = new BitArray( 64, false )
let A2 : BitArray = new BitArray( 64, false )
let A3 : BitArray = new BitArray( 64, true )
let Test1 = A1.Xor(A2)

type BitArray with
    member this.IsSameAs (b:BitArray) =
           let toArray (b:BitArray) = 
                [|0 .. b.Length - 1 |]
                |> Array.map (fun i -> b.[ i])
           (this|> toArray) = ( b|> toArray)

printfn "%A" <|Test1.IsSameAs( Test1)
printfn "%A" <|Test1.IsSameAs( A3 )

 
By on 11/19/2010 5:21 PM ()

Given that he's executing this "millions of times", he can try the below. These versions do not create two temporary arrays, and they stop when as soon as we know the bitarrays are not equal: 

1
2
3
4
5
6
7

 

type BitArray with 
    member this.Equals( b:BitArray) =
        this.Length = b.Length &&
        seq { 0 .. this.Length - 1 } |> Seq.forall( fun i -> this.[ i] = b.[ i] )

For even better perf, try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

let inline bitarEq (b1:BitArray) (b2:BitArray) =
    if b1.Length <> b2.Length then 
        false
    else 
        let mutable i = 0
        let mutable eq = true
        let len = b1.Length
        while eq && i < len do
            eq <- b1.[ i] = b2.[ i]
            i <- 1 + i
        eq

 

if Test1.Equals(bits64Zero) then
    printfn "Equal1"
if bitarEq Test1 bits64Zero then
    printfn "Equal2"
printfn "Done"
By on 11/19/2010 7:43 PM ()

Of course for perf, you should write your own bit vector from scratch so that you have access to the implementation and can compare whole words at a time as much as you can...

By on 11/19/2010 11:22 PM ()

The problem appears to be that BitArray does <i>not <i>provide an implementation (override) for Equals (ick), so the one in Object is being used, and as F# doesn't know about BitArrays, reference equality is being used. (IOW, this should also not work in C#.) If you Google "bitarray equals" you'll see that you're not the only one to be bitten by this. >Since the compare will be performed millions of times in my program, so I need "fast" version Well, in this case you're probably better off writing your own anyway - shouldn't take you too long. If you do it in F#, you can use <b>inline</b>, etc., to make things fast. Enough people don't do the Equals contract correctly, that I always wished that every class also supply it's own type-specific version equality, then then call that in the Equals overload - something like class T { ... static bool SameAs(T t1, T t2) {...} ...} So if I see SameAs(), I <i>know <i>I'm getting the structural equality semantics for equal types that I want.

By on 11/19/2010 2:24 PM ()

Hi,
Thank you very much for your reply.
But I cannot figure out anything useful.
If you have any good idea, can you show me your code?
Thanks,

By on 11/19/2010 2:28 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper