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

Question

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?

Are your arrays (slices, actually!) always sorted (as in the example)? Do you need to preserve the original slices or may these be altered? — ain, Aug 31 '18 at 17:54
Insert the data of both slices into a map and then check for occurrences of a element which will tell you which element is common. — Himanshu, Aug 31 '18 at 18:02
That depends on the size and the distribution of values. Spend some time in the library. The questions as stated is unrelated to Go. — Volker, Aug 31 '18 at 21:26
Does this answer your question? [How to get intersection of two slice in golang?](https://stackoverflow.com/questions/44956031/how-to-get-intersection-of-two-slice-in-golang) — dikkini, Jun 03 '20 at 11:36

peterSO · Accepted Answer · 2018-08-31T18:48:02.277

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.

Awesome! I'm not too familiar with bitwise operators. Can you explain what this does: `for _, k := range a { m[k] |= (1 << 0) } for _, k := range b { m[k] |= (1 << 1) }` and this `a := v&(1<<0) != 0 b := v&(1<<1) != 0` — ziyadparekh, Aug 31 '18 at 18:15
I like this answer, but what if the slices were `[]struct{}`. Can this still be used? — ziyadparekh, Aug 31 '18 at 18:22
@ziyadparekh `struct`s can be map keys if everything in them can be a map key. Otherwise you probably want an approach that starts with sorting the arrays. — twotwotwo, Aug 31 '18 at 18:31
(Correcting my earlier comment (too late to edit it), the approach if you can't hash could just start with sorting *one* array depending on how you want to do it.) — twotwotwo, Aug 31 '18 at 18:40
Here's code that hashes or sorts `a` to get you `a&b` (intersection) and `a-b` (difference). (For b-a you could run the same code with `a` and `b` swapped.) https://play.golang.org/p/FcX8OIAGVH4 — twotwotwo, Aug 31 '18 at 18:51
@ziyadparekh: See my revised anwer for answers to the questions in your comments. — peterSO, Aug 31 '18 at 18:56

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

1 Answers1