Optimize the speed of the truncate_sequences function.
Author: ikkvix
Pull request: yes

# What does this PR do?

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

The truncate_sequences function uses a for loop to iteratively remove elements when truncation_strategy == TruncationStrategy.LONGEST_FIRST. However, when the length of ids or pair_ids is considerable, the time complexity of the removal process becomes O(n^2), which is unacceptable. By directly calculating the quantity to be removed, this portion of the code's time complexity can be reduced to O(n), resulting in a significant speed improvement.


## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [ ] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/main/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/main/docs#writing-source-documentation).
- [ ] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- text models: @ArthurZucker and @younesbelkada
- vision models: @amyeroberts
- speech models: @sanchit-gandhi
- graph models: @clefourrier

Library:

- flax: @sanchit-gandhi
- generate: @gante
- pipelines: @Narsil
- tensorflow: @gante and @Rocketknight1
- tokenizers: @ArthurZucker
- trainer: @muellerzr and @pacman100

Integrations:

- deepspeed: HF Trainer/Accelerate: @pacman100
- ray/raytune: @richardliaw, @amogkam
- Big Model Inference: @SunMarc
- quantization (bitsandbytes, autogpt): @SunMarc and @younesbelkada

Documentation: @stevhliu and @MKhalusova

HF projects:

- accelerate: [different repo](https://github.com/huggingface/accelerate)
- datasets: [different repo](https://github.com/huggingface/datasets)
- diffusers: [different repo](https://github.com/huggingface/diffusers)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Maintained examples (not research project or legacy):

- Flax: @sanchit-gandhi
- PyTorch: See Models above and tag the person corresponding to the modality of the example.
- TensorFlow: @Rocketknight1

 -->
@ArthurZucker and @younesbelkada


Comments:
@ArthurZucker  @younesbelkada  Could you give me any opinions or suggestions?

Hi @ikkvix thanks for your great work on this, I will let @ArthurZucker review the PR as he is much more familiar on tokenizers that I am

> LGTM, what kind of speedups are we looking at? (did you benchmark it?)

Thank you for the review! I conducted some experiments on my pc:

- When num_tokens_to_remove=10,000:
    The old method takes 0.2s in this section of the code, while the new method takes 1e-05s.

- When num_tokens_to_remove=100,000:
    The old method takes 18.94s in this section of the code, while the new method only takes 1.38e-05s.

- When num_tokens_to_remove=200,000:
    The old method takes 75.21s in this section of the code, while the new method only takes 1.81e-05s.

- When num_tokens_to_remove=300,000:
    The old method takes 176.97s in this section of the code, while the new method takes 2.10e-05s.

I didn't measure at the million level because it took too long. It's evident that with the increase in num_tokens_to_remove, the speed of the for loop removal becomes extremely slow, highlighting a massive difference in speed between these two methods.

Thanks for improving the truncation. This is mostly used in `prepare_for_model`  which is used in `encode` basically. A lot of model use this with `truncation=True`. Let me just run the slow tokenization tests to make sure everything is alright : `RUN_SLOW=1 pytest -n 8 tests/ -k test_tokenization_` 




No new failures in the slow tokenization tests, checking the `RUN_CUSTOM_TOKENIZERS` (most of them use truncate_sequence individually) and seems alright! 🪂 thanks