Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make uniqueItems fast #74

Open
ChALkeR opened this issue Jun 25, 2020 · 2 comments
Open

Make uniqueItems fast #74

ChALkeR opened this issue Jun 25, 2020 · 2 comments
Assignees
Milestone

Comments

@ChALkeR
Copy link
Contributor

ChALkeR commented Jun 25, 2020

Currently, uniqueItems on non-primitives is O(n^2) both here and in ajv.
It should be safe as complexityChecks catch unbounded uniqueItems.

But there is no reason for uniqueItems to be O(n^2), even when dealing with complex objects.

See implementation in https://github.com/ChALkeR/array-is-unique/blob/main/sorting.js -- that reaches O(n * log n).
That shouldn't exceed O(n * log n) even in worst-case on modern JS engines which use Timsort.

Also, sort-based implementation is faster than hash/set-based even on primitives, and has significantly lower memory consumption.

@ChALkeR ChALkeR self-assigned this Jun 25, 2020
@ChALkeR
Copy link
Contributor Author

ChALkeR commented Jun 25, 2020

That impl can be made faster in non-unique cases by stopping sorting of large arrays with a throw.

@ChALkeR ChALkeR added this to the v1.0.0 milestone Jul 14, 2020
@ChALkeR
Copy link
Contributor Author

ChALkeR commented Jul 22, 2020

Seems to be non-trivial due to certain limitations. Will revisit for 1.x

@ChALkeR ChALkeR modified the milestones: v1.0.0, v1.x Jul 22, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant