1376132 - The sameElements function in the Array extension file is highly innefficient-O(n^2)

Status: RESOLVED FIXED

(Firefox for iOS :: General, defect, P2)

Description

[bereket6725]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/602.4.8 (KHTML, like Gecko) Version/10.0.3 Safari/602.4.8

Steps to reproduce:

While browsing the source code I noticed that the sameElements function in the Array extension file was very slow. I believe in the original version someone had also commented that it was inefficient but worked, so I figured I'd help make faster :) 


Actual results:


This was the original algorithm, arr.contains(...) is a linear search that calls a function that does another linear search at each step. The operation ends up being O(n^2)

// Laughably inefficient, but good enough for a handful of items.
    func sameElements(_ arr: [Element], f: (Element, Element) -> Bool) -> Bool {
        return self.count == arr.count && every { arr.contains($0, f: f) }
    }

    func contains(_ x: Element, f: (Element, Element) -> Bool) -> Bool {
        for y in self {
            if f(x, y) {
                return true
            }
        }
        return false
    }


Expected results:

You can compare two unsorted collections and make it a nlog(n) operation by sorting them both and comparing them.

Comment 1

[bereket6725]

Attachment: PR optimizing sameElements function in Array extension file

Comment 2

[bereket6725]

forgot to add the "every" function so you can see the sameElements in its proper context: 

public extension Sequence {
    func every(_ f: (Self.Iterator.Element) -> Bool) -> Bool {
        for x in self {
            if !f(x) {
                return false
            }
        }
        return true
    }
}

Comment 3

[bereket6725]

headsup, sent a pull request with a fix with the Bug # and title

Comment 4

[Farhan Patel [:farhan]]

master https://github.com/mozilla-mobile/firefox-ios/commit/ce460e2d1aa8bca22c535410c30ca36733a52a1b