怎么在没有标准库的情况下旋转一个向量?

huangapple go评论71阅读模式
英文:

How to rotate a vector without standard library?

问题

我正在同时学习Rust和Arduino。

在Arduino语言中,我编写了程序来通过顶部字符列旋转显示一个长字符串。意味着:每秒钟我将所有字符向前移动一个位置并显示新的字符串。

这在Arduino语言中相当复杂,特别是因为我必须在编译时知道字符串的大小(考虑到我的有限知识)。

由于我希望长期使用Rust,我很好奇是否可以在现代语言中更轻松地实现这个目标。但实际上并没有那么容易。

经过数小时的实验,我想出了以下代码:

#![no_std]

extern crate alloc;

use alloc::{vec::Vec};

fn main() {
}

fn rotate_by<T: Copy>(rotate: Vec<T>, by: isize) -> Vec<T> {
    let real_by = modulo(by, rotate.len() as isize) as usize;
    Vec::from_iter(rotate[real_by..].iter().chain(rotate[..real_by].iter()).cloned())
}

fn modulo(a: isize, b: isize) -> isize {
    a - b * (a as f64 /b as f64).floor() as isize
}

mod tests {
    use super::*;

    #[test]
    fn test_rotate_five() {
        let chars: Vec<_> = "I am the string and you should rotate me!   ".chars().collect();

        let res_chars: Vec<_> = "the string and you should rotate me!   I am ".chars().collect();

        assert_eq!(rotate_by(chars, 5), res_chars);
    }
}

我的问题是:

  • 你能提供这个函数的优化版本吗?我知道已经有Vec::rotate,但它使用了不安全的代码,可能会出现错误,我想避免这种情况(通过返回一个Result)。
  • 请解释一下是否可以在不使用不安全代码的情况下实现原地旋转(我失败了)。
  • Vec<_> 是最高效的数据结构吗?我努力尝试使用[char],我认为它可能更高效,但接着我必须在编译时知道大小,这几乎行不通。我认为Rust数组会类似于Java数组,可以在运行时设定大小,但一旦创建后大小就固定了,但它们似乎有很多限制。
  • 还有,如果我在一个无效的索引处索引一个向量会发生什么?会导致错误吗?我能做得更好吗?是否可以在不“手动”检查切片索引的有效性的情况下做到这一点?

我意识到这是很多问题,但我很困惑,这让我很烦恼,所以如果有人能帮我搞清楚就会非常感激!

英文:

I'm getting into Rust and Arduino at the same time.

I was programming my LCD display to show a long string by rotating it through the top column of characters. Means: Every second I shift all characters by one position and show the new String.

This was fairly complex in the Arduino language, especially because I had to know the size of the String at compile time (given my limited knowledge).

Since I'd like to use Rust in the long term, I was curious to see if that could be done more easily in a modern language. Not so much.

This is the code I came up with, after hours of experimentation:

#![no_std]

extern crate alloc;

use alloc::{vec::Vec};

fn main() {
}

fn rotate_by&lt;T: Copy&gt;(rotate: Vec&lt;T&gt;, by: isize) -&gt; Vec&lt;T&gt; {
    let real_by = modulo(by, rotate.len() as isize) as usize;
    Vec::from_iter(rotate[real_by..].iter().chain(rotate[..real_by].iter()).cloned())
}

fn modulo(a: isize, b: isize) -&gt; isize {
    a - b * (a as f64 /b as f64).floor() as isize
}

mod tests {
    use super::*;

    #[test]
    fn test_rotate_five() {
        let chars: Vec&lt;_&gt; = &quot;I am the string and you should rotate me!   &quot;.chars().collect();

        let res_chars: Vec&lt;_&gt; = &quot;the string and you should rotate me!   I am &quot;.chars().collect();

        assert_eq!(rotate_by(chars, 5), res_chars);
    }
}

My questions are:

  • Could you provide an optimized version of this function? I'm aware that there already is Vec::rotate but it uses unsafe code and can panic, which I would like to avoid (by returning a Result).
  • Explain whether or not it is possible to achieve this in-place without unsafe code (I failed).
  • Is Vec&lt;_&gt; the most efficient data structure to work with? I tried hard to use [char], which I thought would be more efficient, but then I have to know the size at compile time, which hardly works. I thought Rust arrays would be similar to Java arrays, which can be sized at runtime yet are also fixed size once created, but they seem to have a lot more constraints.
  • Oh and also what happens if I index into a vector at an invalid index? Will it panic? Can I do this better? Without "manually" checking the validity of the slice indices?

I realize that's a lot of questions, but I'm struggling and this is bugging me a lot, so if somebody could set me straight it would be much appreciated!

答案1

得分: 4

你可以使用slice::rotate_leftslice::rotate_right

#![no_std]

extern crate alloc;
use alloc::vec::Vec;

fn rotate_by<T>(data: &mut [T], by: isize) {
    if by > 0 {
        data.rotate_left(by.unsigned_abs());
    } else {
        data.rotate_right(by.unsigned_abs());
    }
}

我将其设计为原地旋转,因为这更有效率。如果你不想原地旋转,仍然可以选择首先克隆向量,因此这比函数创建新向量更灵活,因为在调用时不能取消这个选择。

注意,rotate_by接受可变切片,但你仍然可以传递可变引用给一个向量,这是因为deref coercion的缘故。

#[test]
fn test_rotate_five() {
    let mut chars: Vec<_> = "I am the string and you should rotate me!   ".chars().collect();
    let res_chars: Vec<_> = "the string and you should rotate me!   I am ".chars().collect();
    rotate_by(&mut chars, 5);
    assert_eq!(chars, res_chars);
}

这种方式移动char存在一些边界情况,因为某些有效的UTF-8包含由多个代码点(Rust中的char)组成的音素簇。当音素簇分割在字符串的开头和结尾时,会产生奇怪的效果。例如,将"abcdéfghijk"旋转5次会得到"efghijkabcd\u{301}",重音符号被孤立在其自己的位置,远离'e'

如果你的字符串都是ASCII字符,那就不用担心这个问题,但那样的话,你也可以将它们视为字节字符串:

#[test]
fn test_rotate_five_ascii() {
    let mut chars = b"I am the string and you should rotate me!   ".to_vec();
    let res_chars = b"the string and you should rotate me!   I am ";
    rotate_by(&mut chars, 5);
    assert_eq!(chars, res_chars.to_vec());
}
英文:

You can use slice::rotate_left and slice::rotate_right:

#![no_std]

extern crate alloc;
use alloc::vec::Vec;

fn rotate_by&lt;T&gt;(data: &amp;mut [T], by: isize) {
    if by &gt; 0 {
        data.rotate_left(by.unsigned_abs());
    } else {
        data.rotate_right(by.unsigned_abs());
    }
}

I made it rotate in-place because that is more efficient. If you don't want to do it in-place you still have the option of cloning the vector first, so this is more flexible than if the function creates a new vector, as you have done, because you aren't be able to opt out of that when you call it.

Notice that rotate_by takes a mutable slice, but you can still pass a mutable reference to a vector, because of deref coercion.

#[test]
fn test_rotate_five() {
    let mut chars: Vec&lt;_&gt; = &quot;I am the string and you should rotate me!   &quot;.chars().collect();
    let res_chars: Vec&lt;_&gt; = &quot;the string and you should rotate me!   I am &quot;.chars().collect();
    rotate_by(&amp;mut chars, 5);
    assert_eq!(chars, res_chars);
}

There are some edge cases with moving chars around like this because some valid UTF-8 will contain grapheme clusters that are made up of multiple codepoints (chars in Rust). This will result in strange effects when a grapheme cluster is split between the start and end of the string. For example, rotating &quot;abcdéfghijk&quot; by 5 will result in &quot;efghijkabcd\u{301}&quot;, with the acute accent stranded on its own, away from the &#39;e&#39;.

If your strings are ASCII then you don't have to worry about that, but then you can also just treat them as byte strings anyway:

#[test]
fn test_rotate_five_ascii() {
    let mut chars = b&quot;I am the string and you should rotate me!   &quot;.clone();
    let res_chars = b&quot;the string and you should rotate me!   I am &quot;;
    rotate_by(&amp;mut chars, 5);
    assert_eq!(chars, &amp;res_chars[..]);
}

huangapple
  • 本文由 发表于 2023年2月18日 09:01:24
  • 转载请务必保留本文链接:https://go.coder-hub.com/75490517.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定