Adding retain_unsorted or similar

language design
1

Just thought it was odd that there was no retain equivalent that uses swap_remove under the hood. Why not add something like this?

fn retain_unordered<T, F>(vec: &mut Vec<T>, mut keep: F)
where
    F: FnMut(&T) -> bool,
{
    let mut i = 0;

    while i < vec.len() {
        if keep(&vec[i]) {
            i += 1;
        } else {
            vec.swap_remove(i);
        }
    }
}

Thank you for your time.

2

I'd be curious if that has significant performance benefit.. and if so, how much.

Of course the precise results could also depend on the complexity of the predicate's logic, size of the item datatype, proportion (and pattern?) of values to be removed... etc. Nonetheless have you already benchmarked this? (Or if not, could you maybe try that?)

From an asymptotic point of view, the run time is going to be basically linear w. r. t. the number of elements either way (because you ultimately need to visit every single element).[1] Notably retain is much much more efficient already than what a loop with calls to remove would be. (The latter would actually use time quadratic w. r. t. the number rof elements in most cases.)

  1. But who knows it it's still worth it for good constant factor speedup :man_shrugging:t2: ↩︎

2 Likes
3

Sorry, I did not perform any benchmaks.

Using this vs. the standard retain implementation would not lead to any useful results either way, since that uses a way more efficent method to achieve the compaction (which I only found out after posting).

The question was ultimately unqualified, I did not know that the low level implementation is as optimized as it is - instead imagining something similar to the same simplistic logic as in my proposed example.

1 Like
4

For cases where you're keeping most elements, I could see the unordered version being significantly faster.

1 Like
5

Huh. There was already an accepted ACP for this

2 Likes
6

Oh, that's neat. All we have to do is to wait for it to actually be implemented. :smiley:

Thank you for letting me know!

7

Or submit a PR yourself :wink:

1 Like
8

Someone already has:

2 Likes
9

Guess I'll have to search harder next time. Can someone close this?

10

The PR was submitted yesterday, possibly as a reaction to this very thread :slight_smile: You should be able to mark the thread as resolved by selecting some message as "the answer". Or was that only on urlo?

2 Likes
11

Wow, I didn't actually check the PRs date. Guess it was a good idea to ask about this after all.

The only option seems to wait for the thread to be inactive for a year, though I'll stop 'watching'.

12

We only have the topic-resolve feature enabled only on users.rust-lang.org, not here, so you can't find that; sorry for any confusion.

I will shorten the auto-close interval so this topic is closed sooner.

2 Likes