ソート済みv: Vec<EventHandler<T>>で、ソートしたまま要素を挿入したい。そうするための最も効率的な方法は何ですか？Rustにはそれを行うための組み込みの方法がないようです。
EventHandler<T> 以下のとおりであります：
struct EventHandler<T: Event + ?Sized> {
priority: i32,
f: fn(&mut T),
}
並べ替えの仕組みのため、挿入と並べ替えは非効率的であり、O(n log n)時間と2*n割り当てコストがかかります。
タスクは2つのステップで構成されています：で挿入位置を見つけるbinary_searchとVec::insert()：で挿入します。
match v.binary_search(&new_elem) {
Ok(pos) => {} // element already in vector @ `pos`
Err(pos) => v.insert(pos, new_elem),
}
ベクトルに重複する要素を許可し、既存の要素を挿入する場合は、さらに短く書くことができます。
let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e);
v.insert(pos, new_elem);
ただし、これには実行時の複雑さがO（n）であることに注意してください。中央に挿入するには、ベクトルは挿入位置の右にあるすべての要素を1つ右に移動する必要があります。
したがって、サイズが小さくないベクトルに複数の要素を挿入するために使用しないでください。特に、この挿入ソートアルゴリズムはO（n²）で実行されるため、このメソッドを使用してベクトルをソートしないでください。
このBinaryHeapような状況では、Aの方が適している可能性があります。各挿入（push）の実行時の複雑さは、O（n）ではなくO（log n）だけです。ソートにあなたも、それを変換することができますVecしinto_sorted_vec()、あなたがそう望むならば、。ヒープを変換する代わりに、引き続き使用することもできます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加