質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

  • ソート

    91questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • Rust

    50questions

    Rustとは、Mozilla(モジラ)製の実験的な並列かつマルチパラダイムのプログラミング言語です。

Rustで挿入ソート 配列を受け取り、配列を返す関数を作りたい

受付中

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 735

Rust初心者です。基本的なアルゴリズムを実装してみようと考え、ソートアルゴリズム(挿入ソート)の実装にトライしました。しかし、タイトル通り、配列を受け取って配列を返す関数が上手く作れません。ライフタイムの関係でエラーが発生しているのは分かっているのですが、インターネットで調べたりドキュメントを読んだりしても全く解決しません。

fn insert<'a, T: Ord+Clone>(x: T, v: &'a [T]) -> &'a [T] {
    if v.len() == 0 {
        &[x]
    }else {
        if x < v[0] {
            let res = [&[x], v].concat();
            &res
        }else {
            let res = [&[v[0].clone()], insert(x, &v[1..])].concat();
            &res
        }
    }
}

fn isort<T: Ord+Clone>(v: &[T]) -> &[T] {
    if v.len() == 0 {
        &[]
    }else {
        let x = v[0].clone();
        insert(x, isort(&v[1..]))
    }
}

&[x]の部分でtemporary value does not live long enough&resの部分でborrowed value does not live long enoughというエラーが発生しています。insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか?

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+4

最初に知っておいてほしいのは、&[T]はスライス型であって、配列型ではないことです。配列型は[T; 10]のように、要素の型と要素数が入った型になります。

insert()関数は任意の長さ(Nとします)の配列を引数に取り、長さN + 1の配列を返しますが、Rustではそのような関数は定義できません。

// コンパイルエラーになる
fn insert()<T: Ord+Clone>(x: T, v: [T; N]) -> [T; N + 1] {

// これならコンパイルできるが、引数に長さ1の配列しか取れない
fn insert()<T: Ord+Clone>(x: T, v: [T; 1]) -> [T; 2] {

次にご質問のコードでなぜスライス&[T]を返せないかですが、

insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか? 

スライスは型に参照&が現れているように、それ自体は値の実体を持たず、別の場所にある実体(配列、Vecなど)を参照します。スライスは実体なしには存在できません。つまりスライスのライフタイム(生存期間)は実体のライフタイムよりも短くなければなりません。

ではご質問のコードでそれらの実体はどこにあるでしょうか? 以下のようになっています。

  • &[x]では[x]が実体。[T; 1]型の配列
  • [&[x], v].concat()では[&[x], v]が実体。[&[T]; 2]型の配列

insert()関数のスコープを抜けると、これらの実体のライフタイムが尽きます(メモリ領域が解放されます)。それらの実体を参照するスライスを返そうとしているので、スライスの方がライフタイムが長くなってしまいエラーになるわけです。

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

残念ながら、このプログラムですと配列またはスライスを返すことはできません。

  • 最初の理由により、任意の長さの配列を返す関数が書けない
  • 2番目の理由により、関数内で作った実体を参照するスライスは戻り値として返せない

すでにされているようにVecを返すことならできます。

fn insert<'a, T: Ord + Clone>(x: T, v: &[T]) -> Vec<T> {
    if v.is_empty() {
        vec![x]
    } else {
        if x < v[0] {
            let mut res = vec![x];
            res.extend_from_slice(v);
            res
        } else {
            let mut res = vec![v[0].clone()];
            res.append(&mut insert(x, &v[1..]));
            res
        }
    }
}

fn isort<T: Ord + Clone>(v: &[T]) -> Vec<T> {
    if v.is_empty() {
        Vec::new()
    } else {
        let x = v[0].clone();
        insert(x, &isort(&v[1..]))
    }
}

なお上の実装では、insert()関数が呼ばれるたびに新しいベクタを作るため効率はよくありません。これはもし配列が使えたとしても効率の面では同じです。

もしisort()insert()が引数にとったスライス(&mut [T])をその場で変更してもよいのなら、効率の良い実装もできます。(その場合はかなり違ったプログラムになるので例は割愛します)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか

このエラー自体の理解はそれで合っています。

より根本的な原因として、関数シグネチャからこれがほぼ無理なことがわかります。どちらの関数も入力スライスと出力スライスに同じライフタイムを使っています(というか、ほぼそうするしかないんですが)。後者の関数の場合はlifetime elisionという規則で、同じライフタイムが使われると解釈されます。また、スライス型 [T] は連続したメモリ領域を指しますから、これらの関数の戻り値は、入力されたスライスの連続した一部分しか(ほとんど)ありえないということになります。

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

Rust用語でいう配列は長さが決まってしまっているので、スライスのこととして説明します。確かにスライスはVecより低コストなので「できるだけ」スライスを使うべきですが、できないときはあります。(スライスで何でもできるわけではないからこそ、Vecがあります。)Vecのコストは他の多くの言語では常に支払っているようなコストなので、慣れないうちはあまり気にせずVecを使ってしまっていいと思います。

さて、最初のほうで説明したように、スライスを受け取ってスライスを返す方法では部分列しか返せませんから、この場合はスライスを受け取ってVecを返すのが妥当です。しかし、Vecを使わない方法もあります。可変スライスを受け取り、それ自体をその場でソートするインターフェースにすればよいです。標準ライブラリのsortメソッドはそのようなインターフェースになっています。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • ソート

    91questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • Rust

    50questions

    Rustとは、Mozilla(モジラ)製の実験的な並列かつマルチパラダイムのプログラミング言語です。