Ordine di streaming efficiente

Question

Prendi in considerazione l'attività seguente: abbiamo un input di righe N+1, in cui la prima riga contiene n - numero di elementi, quindi abbiamo n righe, ognuna contiene un elemento, che è una tupla (numero numero, numero m), ID <10^9, m <100. Dobbiamo eseguire un tipo stabile su questa sequenza e stampare il risultato.

Input del campione:

8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4

Esempio di output:

3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1

La mia attuale implementazione ingenua era solo allocare il vettore della dimensione N, riempirlo e quindi eseguire qualsiasi alhoritmo di ordinamento stabile su di esso. Nel seguente esempio (tutti gli esempi sono scritti in ruggine) sto solo aggiungendo il numero di riga come parte del tasto di ordinamento e quindi eseguire l'ordinamento rapido:

use std::io::{self, BufRead};
use std::cmp::Ordering;

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();
        tuples.push((id, m, i));
    }

    tuples.sort_unstable_by(|a, b| {
        let cmp = b.1.cmp(&a.1);
        match cmp {
            Ordering::Equal => a.2.cmp(&b.2),
            other => other
        }
    });

    for (id, m, ..) in tuples {
       println!("{} {}", id, m);
    }
}

La mia seconda implementazione utilizzata BTreeSet, ma non è stato un successo e ci è voluto molto più tempo di quello ingenuo.

La mia terza idea è stata quella di usare Idea dal tipo di inserimento per mantenere l'Array ordinato da zero. Quando otteniamo un altro elemento dal flusso, cerchiamo semplicemente la posizione in cui dovrebbe essere posizionata e poi inseriamo lì dentro. Quando tutti gli elementi vengono elaborati, abbiamo già un array finale. Ecco un'implementazione di esempio:

use std::io::{self, BufRead};
use std::cmp::Ordering;

struct TeamResult {
    id: u32,
    m: u8,
}

impl TeamResult {
    pub fn new(id: u32, m: u8) -> Self {
        Self {
            id,
            m
        }
    }
}

impl Ord for TeamResult {
    fn cmp(&self, other: &Self) -> Ordering {
        other.m.cmp(&self.m)
    }
}

impl PartialOrd for TeamResult {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

impl PartialEq for TeamResult {
    fn eq(&self, other: &Self) -> bool {
        self.m.eq(&other.m)
    }
}

impl Eq for TeamResult { }

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();

        let item_to_insert = TeamResult::new(id, m);
        let index_to_insert = search_pos(&tuples[0..i], &item_to_insert);
        tuples.insert(index_to_insert, item_to_insert);
    }

    for x in tuples {
        println!("{} {}", x.id, x.m);
    }
}

fn search_pos<T: Ord>(a: &[T], value: &T) -> usize {
    let len = a.len();

    if len == 0 {
        return 0;
    }

    if value < &a[0] {
        return 0;
    }

    if value > &a[len - 1] {
        return len;
    }

    let mut lo = 0;
    let mut hi = len - 1;

    while lo < hi {
        let mid = (hi + lo) / 2;

        match value.cmp(&a[mid]) {
            Ordering::Less => hi = mid - 1,
            Ordering::Greater => lo = mid + 1,
            Ordering::Equal => {
                lo = mid;
                break;
            }
        };
    }

    while lo <= hi && value >= &a[lo] {
        lo += 1
    }

    lo
}

Tuttavia, era anche più lento di uno Btree e timeo.

Mi chiedo cosa siano implementazioni ottimali teoriche e pratiche? Voglio dire, cosa in teoria Btree dovrebbe essere più veloce in questo compito, ma in pratica la semplice ordinamento dell'array lo batte.