Principiante de óxido implementando algún tipo -- beginner campo con rust camp codereview Relacionados El problema

Rust beginner implementing some sorts


6
vote

problema

Español

Estoy empezando a aprender a óxido. Después de leer hasta el capítulo 13 de el libro de óxido , i He ido e implementado un puñado de algoritmos de clasificación para la práctica con el idioma.

Me encantaría aprender más experiencias de las consejos de Rustacean sobre formas de hacer que este código sea más idiomático. Tengo algunas dificultades particulares con mergesort - No estoy seguro de cómo hacer algunas copias innecesarias sin cambiar la firma de la función de Vec<u32> &[u32] .

  use std::collections::HashMap;  pub fn bubble_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     if vec.len() == 0 {         return vec;     }      let mut swap_seen = true;     while swap_seen {         swap_seen = false;         for mut i in 0..(vec.len() - 1) {             while (i < (vec.len() - 1)) && (vec[i] > vec[i + 1]) {                 let (a, b) = (vec[i], vec[i + 1]);                 vec[i + 1] = a;                 vec[i] = b;                 swap_seen = true;                 i += 1;             }         }     }     vec }  pub fn selection_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     if vec.len() == 0 {         return vec;     }      for i in 0..(vec.len()) {         let mut smallest_idx = i;         for j in (i + 1)..(vec.len()) {             if vec[j] < vec[smallest_idx] {                 smallest_idx = j;             }         }         let (a, b) = (vec[i], vec[smallest_idx]);         vec[i] = b;         vec[smallest_idx] = a;     }     vec }  pub fn counting_sort(vec: &mut Vec<u32>) -> Vec<u32> {     if vec.len() == 0 {         return vec![];     }      // The type matters. HashMap implements its methods using traits, and if you don't pick     // the right types the traits won't apply and the methods won't show up.     let mut counts: HashMap<&u32, u32> = HashMap::new();      for val in vec.iter() {         // Interesting usage note. This doesn't work:         //         // match counts.get(val) {         //     Some(n_val) => counts.insert(val, n_val + 1),         //     None => counts.insert(val, 1),         // };         //         // Why not?         // counts.get(val) is an immutable borrow of the counts hashmap.         // counts.insert(val) is a mutable borrow of the counts hashmap.         // This violates the constraint that only one mutable or any number of immutable         // borrows may be live at a time. However, it only throws a warning, not an error, for         // some reason. Ref:         // https://discord.com/channels/442252698964721669/448238009733742612/763950019681583152         //         // That brings us to this working code. The "entry API" is specifically designed to avoid         // this problem. In general, many APIs in Rust are designed around such concerns.         *counts.entry(val).or_default() += 1;     }      let mut sorted: Vec<u32> = vec![];      for digit in 0..=9u32 {         let digit_ref = &digit;         let digit_count = counts.get(digit_ref);          match digit_count {             Some(count) => {                 for _ in 0..(*count as i32) {                     sorted.push(digit);                 }             },             None => (),         }     }      sorted }  pub fn insertion_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     // usize is Rust's "architecture-dependent integer size". It is u32 on 32-bit systems and     // u64 on 64-bit systems. usize is used in certain places in Rust lang where this low-level     // detail matters, e.g. if indexing into memory. It's used to represent array sizes I guess     // because array length maximum is the architecture's word size.     for i in 0..(vec.len()) {         for j in 0..i {             if vec[j] > vec[i] {                 let (a, b) = (vec[i], vec[j]);                 vec[j] = a;                 vec[i] = b;             }         }     }     vec }  pub fn quicksort(vec: Vec<u32>) -> Vec<u32> {     if vec.len() <= 1 {         return vec;     }      let pivot_idx = ((vec.len() as f32) / 2.0).floor() as usize;     let pivot_val = vec[pivot_idx];     let mut left: Vec<u32> = Vec::new();     let mut right: Vec<u32> = Vec::new();     for val in ([&vec[..pivot_idx], &vec[(pivot_idx + 1)..]].concat()).into_iter() {         if val < pivot_val {             left.push(val);         }         else {             right.push(val);         }     }      let mut result = quicksort(left);     result.push(pivot_val);     let mut right = quicksort(right);     result.append(&mut right);     result }  pub fn mergesort(vec: Vec<u32>) -> Vec<u32> {     let join = |left: Vec<u32>, right: Vec<u32>| -> Vec<u32> {         let (mut j, mut k) = (0, 0);         let mut result: Vec<u32> = vec![];         while j < left.len() && k < right.len() {             if left[j] < right[k] {                 result.push(left[j]);                 j += 1;             }             else {                 result.push(right[k]);                 k += 1;             }         }         while j < left.len() {             result.push(left[j]);             j += 1;         }         while k < right.len() {             result.push(right[k]);             k += 1;         }          result     };      if vec.len() <= 1 {         return vec;     }     // Nit: eliminate this additional base case.     if vec.len() == 2 {         if vec[0] < vec[1] {             return vec;         } else {             return vec![vec[1], vec[0]];         }     }      // TODO: how do I eliminate this copy without changing the function signature from Vec<u32>     // to &[u32]?     let pivot = (((vec.len() as f32) / 2.0).floor()) as usize;     let mut left: Vec<u32> = Vec::new();     left.extend_from_slice(&vec[..pivot]);     let mut right: Vec<u32> = Vec::new();     right.extend_from_slice(&vec[pivot..]);      let left = mergesort(left);     let right = mergesort(right);      join(left, right) } ```   
Original en ingles

I'm starting to learn Rust. After reading through chapter 13 of the Rust Book, I've gone and implemented a handful of sorting algorithms for practice with the language.

Would love to learn some more experiences Rustacean's tips on ways to make this code more idiomatic. I have some particular difficulties with mergesort -- I am not sure how to making some unnecessary copies without changing the function signature from Vec<u32> to &[u32].

use std::collections::HashMap;  pub fn bubble_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     if vec.len() == 0 {         return vec;     }      let mut swap_seen = true;     while swap_seen {         swap_seen = false;         for mut i in 0..(vec.len() - 1) {             while (i < (vec.len() - 1)) && (vec[i] > vec[i + 1]) {                 let (a, b) = (vec[i], vec[i + 1]);                 vec[i + 1] = a;                 vec[i] = b;                 swap_seen = true;                 i += 1;             }         }     }     vec }  pub fn selection_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     if vec.len() == 0 {         return vec;     }      for i in 0..(vec.len()) {         let mut smallest_idx = i;         for j in (i + 1)..(vec.len()) {             if vec[j] < vec[smallest_idx] {                 smallest_idx = j;             }         }         let (a, b) = (vec[i], vec[smallest_idx]);         vec[i] = b;         vec[smallest_idx] = a;     }     vec }  pub fn counting_sort(vec: &mut Vec<u32>) -> Vec<u32> {     if vec.len() == 0 {         return vec![];     }      // The type matters. HashMap implements its methods using traits, and if you don't pick     // the right types the traits won't apply and the methods won't show up.     let mut counts: HashMap<&u32, u32> = HashMap::new();      for val in vec.iter() {         // Interesting usage note. This doesn't work:         //         // match counts.get(val) {         //     Some(n_val) => counts.insert(val, n_val + 1),         //     None => counts.insert(val, 1),         // };         //         // Why not?         // counts.get(val) is an immutable borrow of the counts hashmap.         // counts.insert(val) is a mutable borrow of the counts hashmap.         // This violates the constraint that only one mutable or any number of immutable         // borrows may be live at a time. However, it only throws a warning, not an error, for         // some reason. Ref:         // https://discord.com/channels/442252698964721669/448238009733742612/763950019681583152         //         // That brings us to this working code. The "entry API" is specifically designed to avoid         // this problem. In general, many APIs in Rust are designed around such concerns.         *counts.entry(val).or_default() += 1;     }      let mut sorted: Vec<u32> = vec![];      for digit in 0..=9u32 {         let digit_ref = &digit;         let digit_count = counts.get(digit_ref);          match digit_count {             Some(count) => {                 for _ in 0..(*count as i32) {                     sorted.push(digit);                 }             },             None => (),         }     }      sorted }  pub fn insertion_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     // usize is Rust's "architecture-dependent integer size". It is u32 on 32-bit systems and     // u64 on 64-bit systems. usize is used in certain places in Rust lang where this low-level     // detail matters, e.g. if indexing into memory. It's used to represent array sizes I guess     // because array length maximum is the architecture's word size.     for i in 0..(vec.len()) {         for j in 0..i {             if vec[j] > vec[i] {                 let (a, b) = (vec[i], vec[j]);                 vec[j] = a;                 vec[i] = b;             }         }     }     vec }  pub fn quicksort(vec: Vec<u32>) -> Vec<u32> {     if vec.len() <= 1 {         return vec;     }      let pivot_idx = ((vec.len() as f32) / 2.0).floor() as usize;     let pivot_val = vec[pivot_idx];     let mut left: Vec<u32> = Vec::new();     let mut right: Vec<u32> = Vec::new();     for val in ([&vec[..pivot_idx], &vec[(pivot_idx + 1)..]].concat()).into_iter() {         if val < pivot_val {             left.push(val);         }         else {             right.push(val);         }     }      let mut result = quicksort(left);     result.push(pivot_val);     let mut right = quicksort(right);     result.append(&mut right);     result }  pub fn mergesort(vec: Vec<u32>) -> Vec<u32> {     let join = |left: Vec<u32>, right: Vec<u32>| -> Vec<u32> {         let (mut j, mut k) = (0, 0);         let mut result: Vec<u32> = vec![];         while j < left.len() && k < right.len() {             if left[j] < right[k] {                 result.push(left[j]);                 j += 1;             }             else {                 result.push(right[k]);                 k += 1;             }         }         while j < left.len() {             result.push(left[j]);             j += 1;         }         while k < right.len() {             result.push(right[k]);             k += 1;         }          result     };      if vec.len() <= 1 {         return vec;     }     // Nit: eliminate this additional base case.     if vec.len() == 2 {         if vec[0] < vec[1] {             return vec;         } else {             return vec![vec[1], vec[0]];         }     }      // TODO: how do I eliminate this copy without changing the function signature from Vec<u32>     // to &[u32]?     let pivot = (((vec.len() as f32) / 2.0).floor()) as usize;     let mut left: Vec<u32> = Vec::new();     left.extend_from_slice(&vec[..pivot]);     let mut right: Vec<u32> = Vec::new();     right.extend_from_slice(&vec[pivot..]);      let left = mergesort(left);     let right = mergesort(right);      join(left, right) } ``` 
     

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

En general, tu código de óxido se ve bien conmigo. Usted realiza el uso adecuado de la biblioteca estándar y las características del idioma como los cierres. Nada se destaca como especialmente unidomático; Incluso el formato se ve bien.

Dicho esto, por supuesto, siempre hay cosas que podrían mejorarse.

Observaciones generales

  • Si no está usando rustfmt , comience ahora. Su formato es básicamente idéntico al rustfmt Predeterminado, pero una herramienta de formato automatizada tiene la ventaja de encontrar el error ocasional, además de hacer que el código se vea bonita.
  • a excepción de counting_sort y mergesort , estos algoritmos son todos en el lugar y trabajan en rodajas, por lo que deben aceptar 9988777665544338 en lugar de < Código> &mut Vec<u32> . Esto hace posible ordenar matrices y otras estructuras de datos similares a la matriz, así como term == 10 Tors.
  • Devolviendo term == 11 de la función Ordenar Permite que se use como term == 12 ( 99887766555443313 recibirá la matriz ordenada). Sin embargo, esto puede ser engañoso porque la función 99887766555443314 muta term == 15 , que se puede pasar por alto fácilmente si ocurre en medio de una expresión más complicada. Es mejor para las funciones que mutan sus argumentos NO también para devolverlos, por lo que el código de llamada es más obvio ( 99887776655443316 ). La biblioteca estándar term == 17 Funciones no devuelve nada.
  • Usa la silla term == 18 Método para intercambiar dos elementos por índice (que no debe confundirse con la función 99887766555443319 , que intercambia los contenidos de cualquier dos fibonacciBinet()0 referencias).
  • Con la excepción de fibonacciBinet()1 , todas estas funciones ordenan los elementos comparándolos, por lo que deberían funcionar tan bien con las rebanadas de cualquier tipo que se pueda comparar con fibonacciBinet()2 < / Código> ¹ - No solo fibonacciBinet()3 . No hay nada de malo en escribir una función que solo ordena fibonacciBinet()4 998877766555443325 ) puede ayudarlo a evitar los errores que resultan de En exceso enfoque en una implementación particular ( fibonacciBinet()6 ).
  • Hay una función fibonacciBinet()7655443327 en las rodajas que puede usar en lugar de fibonacciBinet()8 .
  • Tenga en cuenta que fibonacciBinet()9 y var phi = (1 + math.Sqrt(5)) / 2; 0 tiene la más baja precedencia de cualquier operador, excepto los operadores de asignación. Por lo tanto, no necesita paréntesis, a menos que le resulte útil para la legibilidad.
  • No escriba var phi = (1 + math.Sqrt(5)) / 2; 1 o var phi = (1 + math.Sqrt(5)) / 2; 2 . El var phi = (1 + math.Sqrt(5)) / 2; 33 Llamadas de bucle var phi = (1 + math.Sqrt(5)) / 2; 4 implícitamente. Use var phi = (1 + math.Sqrt(5)) / 2; 5 y var phi = (1 + math.Sqrt(5)) / 2; 6 en su lugar.

Tipo de burbuja

La respuesta de Coyotte508 ya sugirió una solución para esto, pero el bucle anidado hace algunas comparaciones innecesarias porque 99887766555443337 no aumenta monótonamente. Probablemente se esperaba que después de que se terminó el bucle 998877766554433338 , el bucle 998877665554443339 se detendría donde lo dejaba con el valor actual de rustfmt0 , pero rustfmt1 Los bucles no funcionan así en óxido.

99887766555443342 también hace un trabajo adicional cuando el final de la matriz ya está ordenado. Durante una especie de burbuja, hay una sección de la matriz que ya está clasificada, y cada iteración del bucle externo crece esa sección por lo menos 1 (pero a veces más). Puede explotar este hecho haciendo un seguimiento del índice del último intercambio realizado. Al final de cada iteración del bucle externo, el índice del último valor intercambiado es el comienzo de la porción ordenada de la matriz, que nunca necesita volver a ordenarse, para que pueda usar ese índice en lugar de rustfmt3 como un límite para el bucle interno y salga del bucle exterior cuando la longitud de la parte "no clasificada" cae a 1 (ya que una matriz de longitud 1 es ordenar D ya). Como una bonificación, si la inicializa con la longitud de la rebanada, puede evitar la verificación inicial contra rustfmt4 .

Finalmente, es una cosa menor, pero puede reducir el número de rustfmt5 S y rustfmt6 s por ithering de rustfmt7 en lugar de < Código> rustfmt8 .

Con todas estas cosas en mente, aquí es como podría escribir rustfmt9 :

  rustfmt0  

Selección Sort

Este es un libro de texto bastante. IMO No hay mucho que mejorar más allá de las cosas generales que mencioné anteriormente, y que el 99887766555443351 al principio es innecesario porque el bucle 99887766655443352 volverá a revisarlo de inmediato.

  rustfmt3  

Clasificación de inserción

de nuevo, bonito libro de texto. Puede iniciar el bucle externo en rustfmt4 porque nunca hay nada que hacer en rustfmt5 .

  rustfmt6  

Cuento de conteo

Este no se puede hacer genérico, y no se puede hacer fácilmente en el lugar. Sin embargo, dado que solo tiene que trabajar en las claves enteras con un rango limitado, hay otras formas en que podría mejorarse.

primero, ya que no está en el lugar, no necesita mutilar su entrada; Podemos hacerlo aceptar rustfmt7 . (En realidad, es aún más general que eso: ¡puede ordenar cualquier secuencia de valores enteros, incluso los que son demasiado grandes para que se ajusten a la memoria a la vez! Pero por el momento vamos a seguir con rustfmt8 ).

Siguiente Acerca del rustfmt9 : Esta es una opción impar por un tipo de conteo porque elegir un 99887766555443360 sobre un counting_sort1 o incluso solo una simple counting_sort2 (indexado por counting_sort3 ) Sugiere que está preocupado por perder el espacio para un montón de cubos de conteo vacíos. Pero, por lo general, use un tipo de conteo porque espera counting_sort4 (tamaño de la entrada) para ser mucho más grande que counting_sort5 (número de cubos), que solo coincidiría con allí. Un montón de cubos vacíos si los datos se concentran en mucho menos que counting_sort6 cubos. Probablemente el 98% del tiempo que está escribiendo un tipo de conteo, desea una matriz de cubos o un 99887776555443367 de cubos. Pero supongamos que estamos en el 2%. Todavía podemos reemplazar el counting_sort8 con un counting_sort9 , que es más compacto, probable, ² y, naturalmente, mantiene las claves en orden. También copiaremos la clave en lugar de tomar una referencia a ella, ya que es un pequeño entero.

Uso de mergesort0 También nos permite esquivar uno de los problemas molestos de las clases de conteo: ¿Qué sucede si una de las entradas está fuera de rango? Puede resolver este problema por mergesort1 Los valores están siempre en rango, o al restringir el tipo de entrada a uno que solo permite los valores 99887776655443372 , pero eso no siempre es conveniente. Con mergesort3 La salida siempre es correcta. En el peor de los casos, con insumos totalmente arbitrarios, el algoritmo se degrada al tipo de árbol (un pobre optimizado), que sigue siendo mergesort4 .

Verificación de si la entrada está vacía al principio de la función Probablemente no hace nada útil. La función aún hace lo mismo sin él, por lo que lo mejor que puede esperar es que le ahorre un puñado de instrucciones ( 99887766555443375 no se asigna), a expensas de agregar una rama inevitable al principio de cada llamada. No lo pondría a menos que los perfiles mostraron un efecto no despreciable.

Para ayudarme a no perder la pista de qué mergesort66 s son datos y cuáles son los conteos, voy a agregar un tipo de alias mergesort7 .

Finalmente, este bucle en el original ofrece la oportunidad de usar una magia del iterador:

  mergesort8  

Esto no es solo una pieza tediosa de la placa de la caldera, sino que también puede ser lento porque mergesort9 puede tener que reasignar el &mut [u32]0 varias veces. Puede llamar a &mut [u32]1 de antemano, pero en su lugar reemplace todo con &mut [u32]2 , que se puede leer casi como inglés: "extender 99887776655443383 con repetido COPIAS DE &mut [u32]4 HAY TO &mut [u32]5 Times ".

Después de hacer todos esos cambios, aquí está lo que acumulé:

  &mut [u32]6  

Quicksort

De acuerdo, fui un poco por la borda con la crítica de la crítica , así que no haré una reescritura completa de Quicksort. Esto es lo que noté.

&mut [u32]7 es algo que nunca debe escribir. En primer lugar, truncando &mut [u32]8

a &mut [u32]9 pierde mucha precisión. Esto no dará el resultado correcto para grandes rebanadas. Realmente no importa la corrección del algoritmo en este caso, sino que es algo consciente de su conocimiento en general, y puede afectar el desempeño. En segundo lugar, las operaciones de punto flotante suelen ser significativamente más lentas que las operaciones de enteros comparables. Por ambas razones, siempre debe hacer matemáticas enteras con enteros. &mut Vec<u32>0 DIVISIÓN SIEMPRE RONDAS Hacia cero, por lo que la expresión completa debe ser &mut Vec<u32>1 .

TAMBIÉN, &mut Vec<u32>2 y &mut Vec<u32>33 No necesite tipos explícitos; Se pueden inferir.

Mergesort

en gran parte ya cubierto por coyotte508.

Otros ejercicios para el lector

  • Implementar &mut Vec<u32>4 Uso de una matriz en lugar de un &mut Vec<u32>5

  • implementar &mut Vec<u32>6 Con esta firma:

      &mut Vec<u32>7  
  • Implementar &mut Vec<u32>8 usando un algoritmo en el lugar.

  • implementar &mut Vec<u32>9 .


¹ ¿Por qué term == 100 y no term == 101 ? Técnicamente, term == 102 también compilará, pero todos los algoritmos de clasificación de libros de texto asumen que los elementos son comparables, es decir, cada elemento es mayor que, menor que, o igual al elemento. Los valores que son incomparables a otros valores, ya que term == 103 permite, tiende a causar estragos en algoritmos de clasificación.

² El análisis de rendimiento no es trivial. Un árbol B a menudo es más rápido que un hashtable cuando (1) comparando las claves es mucho más barato que los has logrado y (2) se necesitan las llaves en orden. Ambos son verdaderos aquí. Sin embargo, el almacenamiento en caché también desempeña un papel importante y podría influir en el resultado, especialmente si se compara con un hasher rápido, como FNV. Si mira solo el rendimiento asintótico, term == 104 WINS ( term == 105 9988777665544331066554433106 ), pero no estoy convencido de que haya ningún valor de < CÓDIGO> term == 107 y term == 108 para el term == 109 en realidad tiene el mayor sentido. Francamente, también solo quería escribirlo con term == 110

para hacerlo más conciso. Si estaba escribiendo este código en un escenario de programación "Mundo real", querrías conocerlo en lugar de simplemente adivinar.

 

On the whole, your Rust code looks good to me. You make appropriate use of the standard library and language features like closures. Nothing stands out as especially unidiomatic; even the formatting looks nice.

That said, of course there are always things that could be improved.

General observations

  • If you're not using rustfmt yet, start now. Your formatting is basically identical to the rustfmt defaults, but an automated formatting tool has the advantage of finding the occasional mistake as well as making code look pretty.
  • Except for counting_sort and mergesort, these algorithms are all in-place and work on slices, so they should accept &mut [u32] instead of &mut Vec<u32>. This makes it possible to sort arrays and other array-like data structures as well as Vectors.
  • Returning &Vec<u32> from the sort function allows it to be used like foo(sort(&mut xs)) (foo will receive the sorted array). However, this can be misleading because the sort function actually mutates xs, which can be easily overlooked if it occurs in the middle of a more complicated expression. It's better for functions that mutate their arguments not to also return them, so the calling code is more obvious (sort(&mut xs); foo(&xs)). The standard library sort functions do not return anything.
  • Use the slice swap method to swap two elements by index (not to be confused with the std::mem::swap function, which swaps the contents of any two &mut references).
  • With the exception of counting_sort, all of these functions order the elements by comparing them, so they ought to work just as well with slices of any type that can be compared with Ordxc2xb9 -- not just u32. There's nothing wrong with writing a function that only sorts u32s, and in some cases that may even be desirable (for type inference, for example); however, it's nearly as easy to be generic as not, and even if you never expect to use the function with more than one type, coding to an interface (T: Ord) can help you avoid bugs that result from over-focusing on a particular implementation (u32).
  • There is an .is_empty() function on slices you can use in place of .len() == 0.
  • Note that .. and ..= have the lowest precedence of any operator except the assignment operators. So you don't need to parenthesize, unless you find it helpful for readability.
  • Don't write for r in vec.iter() or for v in vec.into_iter(). The for loop calls into_iter() implicitly. Use for r in &vec and for v in vec instead.

Bubble sort

coyotte508's answer already suggested a fix for this, but the nested loop does some unnecessary comparisons because i does not increase monotonically. You probably expected that after the while loop was finished, the for loop would pick up where it left off with the current value of i, but for loops don't work like that in Rust.

bubble_sort also does extra work when the end of the array is already sorted. During a bubble sort, there's a section of the array that's already sorted, and each iteration of the outer loop grows that section by at least 1 (but sometimes more). You can exploit this fact by keeping track of the index of the last swap performed. At the end of each iteration of the outer loop, the index of the last value swapped is the beginning of the sorted portion of the array, which never needs to be sorted again - so you can use that index instead of vec.len() as a bound for the inner loop, and exit the outer loop when the length of the "unsorted" portion drops to 1 (since an array of length 1 is sorted already). As a bonus, if you initialize it with the length of the slice, you can avoid the initial check against 0.

Finally, it's a minor thing, but you can reduce the number of + 1s and - 1s by iterating from 1 instead of 0.

With all these things in mind, here's how you might write bubble_sort:

pub fn bubble_sort<T: Ord>(vec: &mut [T]) {     let mut unsorted_len = vec.len();     while unsorted_len > 1 {         let mut last_swap = 0;         for i in 1..unsorted_len {             if vec[i - 1] > vec[i] {                 vec.swap(i - 1, i);                 last_swap = i;             }         }         unsorted_len = last_swap;     } } 

Selection sort

This one is pretty textbook. IMO there's not much to improve beyond the general stuff I mentioned earlier, and that the if vec.len() == 0 at the beginning is unnecessary because the for loop will immediately check it again.

pub fn selection_sort<T: Ord>(vec: &mut [T]) {     for i in 0..vec.len() {         let mut smallest_idx = i;         for j in (i + 1)..vec.len() {             if vec[j] < vec[smallest_idx] {                 smallest_idx = j;             }         }         vec.swap(i, smallest_idx);     } } 

Insertion sort

Again, pretty textbook. You can start the outer loop at 1 because there's never anything to do at i = 0.

pub fn insertion_sort<T: Ord>(vec: &mut [T]) {     for i in 1..vec.len() {         for j in 0..i {             if vec[j] > vec[i] {                 vec.swap(j, i);             }         }     } } 

Counting sort

This one can't be made generic, and it can't easily be made in-place. However, since it only has to work on integer keys with a limited range, there are some other ways it could be improved.

First, since it isn't in-place, it doesn't need to mutate its input; we can make it accept &[u32]. (It's actually even more general than that: it can sort any sequence of integer values, even ones that are too large to fit in memory at once! But for the moment let's stick with &[u32].)

Next about the HashMap: this is an odd choice for a counting sort because choosing a HashMap<&u32, u32> over a Vec<u32> or even just a plain [u32; 10] (indexed by *val) suggests you're concerned about wasting space for a bunch of empty count-buckets. But usually you use a counting sort because you expect n (size of the input) to be much larger than k (number of buckets), which would only coincide with there being a lot of empty buckets if the data is concentrated into much fewer than k buckets. Probably 98% of the time you're writing a counting sort, you want either an array of buckets or a Vec of buckets. But let's suppose we're in the 2%. We can still replace the HashMap with a BTreeMap, which is more compact, likely faster,xc2xb2 and naturally keeps the keys in order. We'll also copy the key instead of taking a reference to it, since it's a small integer.

Using BTreeMap also lets us sidestep one of the annoying problems of counting sorts: what happens if one of the inputs is out of range? You could solve this problem by asserting the values are always in range, or by restricting the input type to one that only allows the values 0..=9, but that's not always convenient. With BTreeMap the output is always correct. In the worst case scenario, with totally arbitrary inputs, the algorithm degrades to (a poorly-optimized) tree sort, which is still O(n log n).

Checking whether the input is empty at the beginning of the function probably does nothing useful. The function still does the same thing without it, so the best you can hope for is it saves you a handful of instructions (BTreeMap::new does not allocate), at the expense of adding an unavoidable branch at the beginning of every call. I wouldn't put it in unless profiling showed a non-negligible effect.

To help myself not lose track of which u32s are data and which are counts, I'm going to add a type alias Count.

Finally, this loop in the original offers a chance to use some iterator magic:

                for _ in 0..(*count as i32) {                     sorted.push(digit);                 } 

This is not just a tedious piece of boilerplate, but it may also be slow because push might have to reallocate the Vec several times. You could call reserve_exact beforehand, but instead let's replace the whole thing with sorted.extend(std::iter::repeat(digit).take(count)), which can be read almost like English: "extend sorted with repeated copies of digit up to count times".

After making all those changes, here's what I came up with:

pub fn counting_sort(vec: &[u32]) -> Vec<u32> {     type Count = u32;          let mut counts: BTreeMap<_, Count> = BTreeMap::new();     for val in vec {         *counts.entry(*val).or_default() += 1;     }      let mut sorted: Vec<Count> = vec![];     for (digit, count) in counts {         sorted.extend(std::iter::repeat(digit).take(count as _));     }     sorted } 

Quicksort

Okay, I went a little overboard with critiquing counting sort, so I won't do a full rewrite of quicksort. Here's what I noticed.

((vec.len() as f32) / 2.0).floor() as usize is something you should never write. In the first place, truncating vec.len() to f32 loses a lot of precision. This will not give the correct result for large slices. It doesn't really matter to the correctness of the algorithm in this case, but it's a thing to be aware of in general, and it can affect performance. Secondly, floating-point operations are usually significantly slower than comparable integer operations. For both these reasons you should always do integer math with integers. usize division always rounds towards zero, so the whole expression should just be vec.len() / 2.

Also, left and right don't need explicit types; they can be inferred.

Mergesort

Largely already covered by coyotte508.

Further exercises for the reader

  • Implement counting_sort using an array instead of a BTreeMap

  • Implement counting_sort with this signature:

    fn counting_sort(impl IntoIterator<Item = u32>) -> impl Iterator<Item = u32>; 
  • Implement quicksort using an in-place algorithm.

  • Implement heapsort.


xc2xb9 Why Ord and not PartialOrd? Technically PartialOrd will also compile, but all textbook sorting algorithms assume that the items are comparable -- that is, each item is either greater than, less than, or equal to each other item. Values that are incomparable to other values, as PartialOrd allows, tend to wreak havoc in sorting algorithms.

xc2xb2 The performance analysis is non-trivial. A B-tree is often faster than a hashtable when (1) comparing the keys is much cheaper than hashing them and (2) the keys are needed in order. Both are true here. However, caching also plays a large role and could sway the result, especially if you compare against a fast hasher such as FNV. If you look at only the asymptotic performance, HashMap wins (O(n + k) vs. O((n + k)log(k))), but I'm not convinced there's any value of n and k for which HashMap actually makes the most sense. Frankly, I also just wanted to write it with BTreeMap to make it more concise. If you were writing this code in a "real world" programming scenario, you'd want to profile it rather than just guessing.

 
 
 
 
4
 
vote

Esta respuesta es solo sobre Mergesort

No veo por qué no quiere que Mergesort tome term == 111 como argumento: ¡hace que la función sea más genérica! Leí en el Libro de óxido que los rusticantes prefieren usar term == 112 en lugar de term == 113 como un argumento por esa razón;)

Soy nuevo en óxido, ¡lo siento! - Y decidimos probar mi mano en esto.

Casos de borde

Mi primer comentario no es específico de óxido (todos los demás son) esto:

  term == 114  

Se puede reescribir así:

  term == 115  

Pivot

  term == 116  

Al dividir un INT positivo por otro INT positivo, el resultado es el mismo que en C / C ++: no obtiene lo que es después del punto flotante. Solo puedes hacer:

  term == 117  

Cambio de firma

Vamos a estudiar la firma de su función y cambiarla:

  term == 118  

Toma un term == 119 - No como referencia, por lo que mueve los datos en la función. El argumento se vuelve inutilizable por la persona que llama de la función. Luego devuelve un nuevo term == 120 .

Por ejemplo, este código no funcionará, ya que se movió term == 121 , no se puede usar en el term == 122 :

  term == 123  

Dado que, no hay una desventaja para usar term == 124 como el tipo, y reorden en su lugar:

  term == 125  

ahora term == 126 Perspulsión de una rebanada mutua.

Ahora probablemente tenga muchos errores :)

Veamos la última parte:

  term == 127  

Dado que term == 128 toma una referencia mutable, puede cambiar a:

  term == 129  

Función de unión

Así que ahora debemos cambiar la firma de term == 130 , para tomar dos rebanadas como parámetros. En realidad, me gustaría hacer esto, y me gustaría reescribir las rebanadas en su lugar:

  term == 131  

¡Pero no es posible tomar prestadas dos referencias mutables al mismo tiempo!

Lo siguiente mejor, para mí, es:

  • term == 132 Persheet Dos referencias inmutables y devuelven un 998877766554433133
  • Luego, asigne el contenido del term == 134 a la rebanada

Así que aquí está la firma:

  term == 135  

Ahora solo tenemos que cambiar unirme;)

Primero esto:

  term == 136  

Se puede cambiar a:

  term == 137  

ahora esto:

  term == 138  

No creo que aumenten los índices está en la filosofía de óxido, preferiría usar los iteradores:

  term == 139  

Lamentablemente, esto no es posible, porque solo queremos avanzar un lado a la vez. Bueno, hay una función 9988777665544331440 para verificar el siguiente valor sin llamar term == 141 , lo que le da en su lugar para term == 142 :

  term == 143  

No estoy seguro de si hacer que un iterador sea escondido sea todo lo que es genial, sin embargo. ¡Pero ahora podría incluso cambiar la firma de term == 144 para tomar dos 998877666554433145 como parámetros!

Aquí hay otra versión con solo rebanadas:

  term == 146  

Tenga en cuenta que hice los argumentos mutables, podría haber hecho esto en su lugar:

  term == 147  

Versión final

  term == 148  

También es fácil recuperar la firma original, si realmente desea:

  998877665544 3149  

BONIFICACIÓN: BUBLE_SORT

Sin cambiar la firma de la función ( 998877766554433150 podría usarse), aquí se transforma:

  term == 151  

 

This answer is only about mergesort

I don't see why you don't want mergesort to take &[u32] as an argument - it makes the function more generic! I read in the rust book that rustaceans prefer to use &str instead of &String as an argument for that reason ;)

I'm new to Rust as well - sorry! - and decided to try my hand at this.

Edge cases

My first comment is not rust-specific (all the others are) this:

    if vec.len() <= 1 {         return vec;     }     // Nit: eliminate this additional base case.     if vec.len() == 2 {         if vec[0] < vec[1] {             return vec;         } else {             return vec![vec[1], vec[0]];         }     } 

It can be rewritten like this:

    if vec.len() == 2 && vec[0] > vec[1] {         return vec![vec[1], vec[0]];     }     if vec.len() <= 2 {         return vec;     } 

pivot

    let pivot = (((vec.len() as f32) / 2.0).floor()) as usize; 

When dividing a positive int by another positive int, the result is the same as in C / C++: you don't get what's after the floating point. You can just do:

    let pivot = vec.len() / 2; 

Signature change

Let's study the signature of your function - and change it:

pub fn mergesort(vec: Vec<u32>) -> Vec<u32>; 

It takes a Vec<u32> - not as a reference, so it moves the data into the function. The argument becomes unusable by the caller of the function. It then returns a new Vec<u32>.

For example, this code won't work, since vec was moved, it can't be used in the println!:

fn main() {   let vec = vec![2,1,0,4,5];   let sorted = mergesort(vec);    println!("Original: {:?}, sorted: {?:}", vec, sorted); } 

Given that, there is no downside to use &mut [u32] as the type, and reorder in place:

pub fn mergesort(vec: &mut [u32]); 

Now mergesort borrows a mutable slice.

Now you probably have plenty of errors :)

Let's look at the last part:

    let mut left: Vec<u32> = Vec::new();     left.extend_from_slice(&vec[..pivot]);     let mut right: Vec<u32> = Vec::new();     right.extend_from_slice(&vec[pivot..]);      let left = mergesort(left);     let right = mergesort(right);      join(left, right) 

Since mergesort takes a mutable reference, it can change to:

    mergesort(&mut vec[..pivot]);     mergesort(&mut vec[pivot..]);      join(???) 

join function

So now we must change the signature of join, to take two slices as parameters. Actually, I'd like to do this, and have join rewrite the slices in place:

   join (&mut vec[..pivot], &mut vec[pivot..]); 

But it's not possible to borrow two mutable references at the same time!

The next best thing, to me, is:

  • join borrows two immutable references and returns a Vec
  • Then assign the content of the Vec to the slice

So here's the signature:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {         // ...     };      let pivot = vec.len() / 2;      mergesort(&mut vec[..pivot]);     mergesort(&mut vec[pivot..]);      let result = join(&vec[..pivot], &vec[pivot..]);     vec.copy_from_slice(&result[..]) 

Now we just have to change join ;)

First this:

        while j < left.len() {             result.push(left[j]);             j += 1;         }         while k < right.len() {             result.push(right[k]);             k += 1;         } 

It can be changed to:

        result.extend_from_slice(&left[j..]);         result.extend_from_slice(&right[k..]); 

Now this:

        let (mut j, mut k) = (0, 0);         let mut result: Vec<u32> = vec![];         while j < left.len() && k < right.len() {             if left[j] < right[k] {                 result.push(left[j]);                 j += 1;             }             else {                 result.push(right[k]);                 k += 1;             }         } 

I don't think increasing indexes is in rust philosophy, I'd rather like to use iterators:

        let mut left = left.iter();         let mut right = right.iter();         while let (Some(left), Some(right)) = (left.next(), right.next()) {            // ...         } 

Unfortunately this is not possible, because we only want to advance one side at a time. Well, there is a peekable function for iterators, to check the next value without calling next, which gives this instead for join:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {         let mut result: Vec<u32> = vec![];          let mut left = left.iter().peekable();         let mut right = right.iter().peekable();          while let (Some(left_val), Some(right_val)) = (left.peek(), right.peek()) {             if left_val < right_val {                 result.push(**left_val);                 left.next(); // only advance left             } else {                 result.push(**right_val);                 right.next(); // only advance right             }         }          result.extend(left);         result.extend(right);          result     }; 

I'm not sure if making an iterator peekable is all that great, however. But now you could even change the signature of join to take two mutable Iter as parameters!

Here's another version with just slices:

    let join = |mut left: &[u32], mut right: &[u32]| -> Vec<u32> {         let mut result: Vec<u32> = vec![];                  while left.len() > 0 && right.len() > 0 {             if left[0] < right[0] {                 result.push(left[0]);                 left = &left[1..];             } else {                 result.push(right[0]);                 right = &right[1..];             }         }         result.extend_from_slice(&left);         result.extend_from_slice(&right);          result     }; 

Note that I made the arguments mutable, I could have done this instead:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {         let mut left = left;         let mut right = right;          // ...     }; 

Final version

pub fn mergesort(vec: &mut [u32]) {     if vec.len() == 2 && vec[0] > vec[1] {         vec.swap(0, 1);     }     if vec.len() <= 2 {         return;     }      let join = |mut left: &[u32], mut right: &[u32]| -> Vec<u32> {         let mut result: Vec<u32> = vec![];          while left.len() > 0 && right.len() > 0 {             if left[0] < right[0] {                 result.push(left[0]);                 left = &left[1..];             } else {                 result.push(right[0]);                 right = &right[1..];             }         }         result.extend_from_slice(&left);         result.extend_from_slice(&right);          result     };      let pivot = vec.len() / 2;      mergesort(&mut vec[..pivot]);     mergesort(&mut vec[pivot..]);      let result = join(&vec[..pivot], &vec[pivot..]);     vec.copy_from_slice(&result[..]) } 

It's easy to get back the original signature as well, if you really want:

pub fn mergesort (vec: Vec<u32>) -> Vec<u32> {     mergesort_private(&mut vec[..]);     vec }  // Original mergesort function, renamed to mergesort_private fn mergesort_private(vec: &mut [u32]) {     // ... } 

Bonus: bubble_sort

Without changing the signature of the function (& mut[u32] could be used), here it is transformed:

pub fn bubble_sort(vec: &mut Vec<u32>) -> &Vec<u32> {     loop {         let mut swap_seen = false;          for i in 0..(vec.len() - 1) {             if vec[i] > vec[i + 1] {                 vec.swap(i, i + 1);                 swap_seen = true;             }         }          if !swap_seen {             break;         }     }     vec } 
 
 
   
   

Relacionados problema

7  Implementar una secuencia de Fibonacci genérica en óxido sin usar copia rasgo  ( Implement a generic fibonacci sequence in rust without using copy trait ) 
Estoy tratando de aprender a óxido y soy un principiante. ¿Cómo se hace frente a la implementación de una versión genérica de la secuencia FIBONACCI sin usar ...

1  La mejor implementación de la mejor búsqueda de primera búsqueda en óxido  ( Greedy best first search implementation in rust ) 
He implementado un codicioso algoritmo de primera búsqueda en Rust, ya que no pude encontrar una ya implementada en las cajas existentes. Tengo un pequeño pro...

3  Lista doblemente vinculada en óxido usando los punteros crudos  ( Doubly linked list in rust using raw pointers ) 
Estoy practicando la oxidación escribiendo una lista doblemente vinculada usando los punteros crudos, 9988776655544330 Para asignar datos en el montón, 998...

7  HMAC con SHA256 / 512 en óxido  ( Hmac with sha256 512 in rust ) 
He intentado lo mejor que puedo, para implementar HMAC como se especifica en la RFC 2104 < / a>. Este es también mi primer proyecto de óxido, por lo que las ...

5  Canción de 99 cervezas en óxido  ( 99 beers song in rust ) 
Estoy aprendiendo a Rust. Me parece que a veces se confuso en comparación con otros lenguajes de programación, especialmente cuando se trata de cadenas y re...

3  Aplicación singularidad e IPC unilateral en UNIX  ( Application uniqueness and unilateral ipc on unix ) 
este programa Detecta la singularidad de la aplicación, si la aplicación es una instancia única / primaria, lanza un servidor, de lo contrario, un cliente...

6  Utilidad X-up para EVE Online  ( X up utility for eve online ) 
Estoy aprendiendo a Rust. También interpreto a Eve Online: un videojuego sobre las naves espaciales de Internet. Decidí que sería divertido practicar el óxi...

8  Reemplace la cadena en el archivo  ( Replace string in file ) 
Este es mi primer módulo que escribí en el óxido. Soy nuevo en el idioma y no pude encontrar una manera de reemplazar fácilmente algunas palabras en un archiv...

6  Clasificación de palabras por frecuencia  ( Sorting words by frequency ) 
Estoy haciendo una tarea simple en óxido después de leer el Libro de óxido : Lea un archivo de texto dividirlo en Whitespace desinfectar palabras elim...

3  Base64 String ↔ Array flotante  ( Base64 string %e2%86%94 float array ) 
Necesito convertir move constructor8 matrices con una longitud de fix a base64 Representación y atrás. Mi código actual se ve así. Funciona, pero se sient...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos