Comment transformer un buffer circulaire en un vecteur dans O (n) sans allocation?

Question

J'ai un Vec qui est l'allocation pour un tampon circulaire. Supposons que le tampon est plein, donc il n'y a aucun élément dans l'allocation qui ne soit pas dans le tampon circulaire. Je veux maintenant transformer ce tampon circulaire en Vec où le premier élément du tampon circulaire est également le premier élément du Vec. À titre d'exemple, je cette (allocation) fonction:

fn normalize(tail: usize, buf: Vec<usize>) -> Vec<usize> { 
    let n = buf.len(); 
    buf[tail..n] 
     .iter() 
     .chain(buf[0..tail].iter()) 
     .cloned() 
     .collect() 
} 

Playground

Il est évident que cela peut aussi être fait sans allouer quoi que ce soit, étant donné que nous avons déjà une allocation qui est assez grand, et nous avons une opération swap échanger des éléments arbitraires de l'allocation.

fn normalize(tail: usize, mut buf: Vec<usize>) -> Vec<usize> { 
    for _ in 0..tail { 
     for i in 0..(buf.len() - 1) { 
      buf.swap(i, i + 1); 
     } 
    } 
    buf 
} 

Playground

Malheureusement, cela nécessite buf.len() * tail opérations de swap. Je suis assez sûr qu'il peut être fait dans buf.len() + tail opérations d'échange. Pour les valeurs concrètes de tail et buf.len() j'ai été en mesure de trouver des solutions, mais je ne suis pas sûr de savoir comment le faire dans le cas général.

Ma solution partielle récursive can be seen in action.

Answer 1

Cette opération est typiquement appelée une "rotation" du vecteur, par ex. la bibliothèque standard C++ a std::rotate pour ce faire. Il y a known algorithms pour faire l'opération, bien que vous deviez faire très attention lors du portage si vous essayez génériquement/avec des types non Copy, où swap s deviennent la clé, car on ne peut généralement pas lire quelque chose directement à partir de un vecteur.

Cela dit, il est susceptible d'être en mesure d'utiliser le code unsafe avec std::ptr::read/std::ptr::write pour cela, puisque les données vient d'être déplacé autour, et donc il n'y a pas besoin d'exécuter du code défini par l'appelant ou des préoccupations très complexes au sujet de la sécurité d'exception .

Un port du code C dans le lien ci-dessus (par @ker):

fn rotate(k: usize, a: &mut [i32]) { 
    if k == 0 { return } 

    let mut c = 0; 
    let n = a.len(); 
    let mut v = 0; 
    while c < n { 
     let mut t = v; 
     let mut tp = v + k; 
     let tmp = a[v]; 
     c += 1; 
     while tp != v { 
      a[t] = a[tp]; 
      t = tp; 
      tp += k; 
      if tp >= n { tp -= n; } 
      c += 1; 
     } 
     a[t] = tmp; 
     v += 1; 
    } 
} 

Answer 2

La solution la plus simple à utiliser 3 reprises, en effet c'est ce qui est recommandé dans Algorithm to rotate an array in linear time.

// rotate to the left by "k". 
fn rotate<T>(array: &mut [T], k: usize) { 
    if array.is_empty() { return; } 

    let k = k % array.len(); 

    array[..k].reverse(); 
    array[k..].reverse(); 
    array.reverse(); 
} 

Bien que ce soit linéaire, cela nécessite la lecture et l'écriture de chaque élément au maximum deux fois (inverser une gamme avec un nombre impair d'éléments ne nécessite pas de toucher l'élément central). D'autre part, le modèle d'accès très prévisible de l'inversion joue bien avec la pré-lecture, YMMV.