What is the most efficient way to get the intersection and exclusions from two arrays/slices?

user_1122513 0
Viewed 3705

Given two arrays or slices for eg:

a := []int{1, 2, 3, 4, 5}
b := []int{3, 4, 5, 6, 7, 8, 9}

The slices may not be sorted and order doesn't matter.

What is the most efficient way to compute values such that you end up with the common elements of both slices, and the remainder of elements present in one but not the other i.e for the two arrays given above the return values would be:

common := []int{3, 4, 5}
inAButNotB := []int{1, 2}
inBButNotA := []int{6, 7, 8, 9}

Its easy to compute the intersection converting one slice into a map and then iterating over the one to see if values exist. Is there a way to compute the other two values within the same loop?

go slice arrays
1 Answers

O(len(a) + len(b)) is efficient. For example,

package main

import (
    "fmt"
)

func main() {
    a := []int{1, 2, 3, 4, 5}
    b := []int{3, 4, 5, 6, 7, 8, 9}
    fmt.Println(a)
    fmt.Println(b)

    m := make(map[int]uint8)
    for _, k := range a {
        m[k] |= (1 << 0)
    }
    for _, k := range b {
        m[k] |= (1 << 1)
    }

    var inAAndB, inAButNotB, inBButNotA []int
    for k, v := range m {
        a := v&(1<<0) != 0
        b := v&(1<<1) != 0
        switch {
        case a && b:
            inAAndB = append(inAAndB, k)
        case a && !b:
            inAButNotB = append(inAButNotB, k)
        case !a && b:
            inBButNotA = append(inBButNotA, k)
        }
    }
    fmt.Println(inAAndB)
    fmt.Println(inAButNotB)
    fmt.Println(inBButNotA)
}

Playground: https://play.golang.org/p/RvGaC9Wfjiv

Output:

[1 2 3 4 5]
[3 4 5 6 7 8 9]
[3 4 5]
[1 2]
[8 6 7 9]

The Go Programming Language Specification

&    bitwise AND            integers
|    bitwise OR             integers
^    bitwise XOR            integers
&^   bit clear (AND NOT)    integers

<<   left shift             integer << unsigned integer
>>   right shift            integer >> unsigned integer

We have 8 bits for uint8. Bit 0 (1 << 0, 1 shift left 0) is a and bit 1 (1 << 1; 1 shift left 1) is b. For uint8 bits, 00000001 is a, 00000010 is b, 00000011 is a and b, and 00000000 is nether a nor b. The | operator sets a bit, the & operator reads a bit.

The Go Programming Language Specification

Map types

A map is an unordered group of elements of one type, called the element type, indexed by a set of unique keys of another type, called the key type.

The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice. If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.

The algorithm works for any slice type whose elements can be a map key. The comparison operators == and != must be fully defined for operands of the key type.

user_2217000
Related