Skip to content

XCTAssertUnorderedEqualSequences: Improve algorithmic complexity when elements are Hashable #176

Open
@mdznr

Description

@mdznr

In the (only) implementation of XCTAssertUnorderedEqualSequences (where elements are Equatable), it converts the sequence into an Array. Then it iterates through the second sequence, calling firstIndex(of:) on the first array (O(n)), which totals to O(n2). If a Set were used (when the elements are Hashable), then getting the index of an element is O(1), which would make the total algorithmic complexity O(n).

Expected behavior

XCTAssertUnorderedEqualSequences is O(n) when Element: Hashable

Actual behavior

XCTAssertUnorderedEqualSequences is O(n2) when Element: Hashable

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions