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

fix typo + faster is_sorted #1

Merged
merged 3 commits into from Oct 6, 2022
Merged

fix typo + faster is_sorted #1

merged 3 commits into from Oct 6, 2022

Conversation

Wireless4024
Copy link
Contributor

@Wireless4024 Wireless4024 commented Oct 5, 2022

  • Fix typo : InmutableLessSwap -> ImmutableLessSwap

  • IndexSort::is_sorted2()
    This is an improved version of IndexSort::is_sorted.
    I didn't replace internal function with is_sorted2 because I'm not sure about its behavior,
    If you want to replace original function with this new implementation, do it manually (or tell me to do so).

    worst case scenario: O(N/2)

    This implementation compare element at head and tail in same loop (visualize below)

    len = 13
    iter 1: less(1, 0), less(12, 11)
    iter 2: less(2, 1), less(11, 10)
    iter 3: less(3, 2), less(10, 9)
    iter 4: less(4, 3), less(9, 8)
    iter 5: less(5, 4), less(8, 7)
    iter 6: less(6, 5), less(7, 6)
    

    if len is even it will compare middle element twice (less(7, 6) will run twice if len=14)

    result from cargo bench

     is_sorted(10k)          time:   [8.9054 µs 8.9057 µs 8.9059 µs]
     1 (1.00%) low severe
     2 (2.00%) high mild
     2 (2.00%) high severe
    
     is_sorted2(10k)         time:   [6.1242 µs 6.1258 µs 6.1283 µs]
     1 (1.00%) low severe
     2 (2.00%) low mild
     1 (1.00%) high mild
     8 (8.00%) high severe
    
     is_sorted(100m)         time:   [115.44 ms 117.43 ms 119.60 ms]
     1 (1.00%) high mild
    
     is_sorted2(100m)        time:   [84.528 ms 84.769 ms 84.978 ms]
     5 (5.00%) low severe
     3 (3.00%) low mild
     1 (1.00%) high mild
    

@al8n al8n merged commit c36038f into al8n:main Oct 6, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants