Rust part20

**デフォルトの名無しさん** · 2023/03/03(金) 00:45:28.73

公式
https://www.rust-lang.org/
https://blog.rust-lang.org/
https://github.com/rust-lang/rust

公式ドキュメント
https://www.rust-lang.org/learn

Web上の実行環境
https://play.rust-lang.org

※Rustを学びたい人はまず最初に公式のThe Bookを読むこと
https://doc.rust-lang.org/book/

※Rustを学ぶ際に犯しがちな12の過ち
https://dystroy.org/blog/how-not-to-learn-rust

※Rustのasyncについて知りたければ「async-book」は必読
https://rust-lang.github.io/async-book/

※次スレは原則>>980が立てること

前スレ
Rust part19
https://mevius.5ch.net/test/read.cgi/tech/1673926892/

ﾜｯﾁｮｲスレ
プログラミング言語 Rust 4【ﾜｯﾁｮｲ】
https://mevius.5ch.net/test/read.cgi/tech/1514107621/

**デフォルトの名無しさん** · 2023/07/30(日) 00:24:01.50

マクロしらんの？

**デフォルトの名無しさん** · 2023/07/30(日) 00:24:09.72

>>848
すでに習得した言語の対比して新しい言語に挑戦するのは当たり前やろ？
Haskellの型システム理解するのにどれだけの時間をかけて教科書を読み、論文を読み、プログラミングを組んでみたか、その資産を使いたいとおもうのがそんなに悪いんか？
黙っといてくれよ

**デフォルトの名無しさん** · 2023/07/30(日) 00:24:40.66

>>852
悪いに決まってるだろ？
そんなこともわからんの？

**デフォルトの名無しさん** · 2023/07/30(日) 00:26:23.01

論文読まないとプログラム言語が理解できないんだから困ったやつだろ
推論システムが変

**デフォルトの名無しさん** · 2023/07/30(日) 00:29:41.31

まずは"真面目にRust学習"しろ
そして習得しろ
そして疑問を解決しろ

**デフォルトの名無しさん** · 2023/07/30(日) 00:32:06.97

>>854
すまんけどオレは論文なんか読まなくても理解できるような天才じゃないんだよ
君は論文なんぞ読まなくても何もかもわかる天才なのかもしれんけど世の中そんな天才ばかりじゃないんだよ
オレみたいに寝食忘れて努力に努力を重ねてやっと話しが分かる鈍才もいるんだよ
鈍才が悪あがきするの邪魔せんでくれ

**デフォルトの名無しさん** · 2023/07/30(日) 00:33:26.30

>>855
もうオレに関わらないで
その方が双方幸せじゃないか？

**デフォルトの名無しさん** · 2023/07/30(日) 02:16:35.97

大先生3人に共通するのは
自分は分かってるという根拠のない思い込みと
何度指摘されても全く反省せず同じことを繰り返す傍迷惑な行動

**デフォルトの名無しさん** · 2023/07/30(日) 02:39:34.14

>>847
consセルを使った簡易なリスト操作表記をRustは言語仕様レベルではサポートしていない
だからそのHaskellのmysumをその表現のまま移植するのは本質的ではないため
意味だけを重視してリストをイテレータで表現し再帰定義している点を尊重すると

use std::ops::Add;
use num::Zero;

fn mysum<T>(mut iter: impl Iterator<Item = T>) -> T
where
T: Zero + Add<Output = T>,
{
match iter.next() {
Some(n) => n + mysum(iter),
None => T::zero(),
}
}

一例としてこのようにmysumはジェネリックに書ける
mysumに最低限必要なトレイト境界(Zero + Add)のみを課している
もちろんこの関数だけで以下のように機能して計算結果も合う
assert_eq!(15, mysum([1, 2, 3, 4, 5].into_iter()));

**デフォルトの名無しさん** · 2023/07/30(日) 02:43:03.72

>>859のmysumでトレイト境界はZeroとAddさえ満たしていれば通常の数値でなくても構わないので
例えば以下のようなHoge型を定義して必要なトレイト境界(ZeroとAdd)を実装すると

#[derive(PartialEq, Debug)]
struct Hoge(usize);
impl Zero for Hoge {
fn zero() -> Self { Hoge(0) }
fn is_zero(&self) -> bool { self.0 == 0 }
}
impl Add for Hoge {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Hoge((1 << (self.0.trailing_ones() + rhs.0.trailing_ones())) - 1)
}
}

先程と同じように「15 = 1 + 2 + 3 + 4 + 5」をHoge型で表現することで
Hogeについてもmysum()は以下のようにきちんと計算できていることがわかる
assert_eq!(Hoge(0b111111111111111), mysum([Hoge(0b1), Hoge(0b11), Hoge(0b111), Hoge(0b1111), Hoge(0b11111)].into_iter()));

Haskellに全く詳しくないので逆に質問というか教えてほしい
このHoge型をHaskellで定義(実装)するにはどのようなコードになるのか？
そしてこのHoge型に対してもHaskell版>>839のmysumで使えるようにするにはどうするのか？
たぶん型クラスNumの代わりに型クラスZeroとAddを指定するだけで済むのだろうけど
もしHaskellに型クラスZeroやAddがなければそれを定義する形になるのだろうか？
よろしくお願いします

**デフォルトの名無しさん** · 2023/07/30(日) 10:57:59.43

>>860
Haskellではこうなります
https://ideone.com/PKy694

mysum [] = 0
mysum ( a : as ) = a + ( mysum as )

hogePlus a 0 = a
hogePlus a b | even b = 2 * (hogePlus a ( div b 2 ) )
hogePlus a b = 1 + 2 * (hogePlus a ( div b 2 ) )

data Hoge = H Integer deriving Show

instance Num Hoge where
( H x ) + ( H y ) = H ( hogePlus x y )
fromInteger = H

main = do
print $ mysum [ 1..5 ]
print $ hogePlus 3 7
print $ mysum [ H 1, H 3, H 7, H 15, H 31 ]

**デフォルトの名無しさん** · 2023/07/30(日) 10:58:19.77

この例だとmysumの型は
mysum :: ( Num a ) => [ a ] -> a
と推論されます
すなわちmysumは

　aがNum class に属する型aに対して[a]型の値に対してa型の値を返す関数の型

です
よってmysumをある型Hogeで利用するにはHogeにNumインスタンスを導入しなければなりません、すなわちRustでは
impl Num for Hoge { ... }
のように書く部分です( >> 860 のAdd,Zeroを実装してる部分に該当します)
本来はNumのminimal complete definition全部実装するべきでHaskell1990までは“定義が揃ってない”とおこられましたが。2010以降は必要な分だけ実装すれば良い、ただし実行時エラーは覚悟しろという風に変更されてるようです(未確認、コンパイラがエラー吐かなくなったので)

**デフォルトの名無しさん** · 2023/07/30(日) 12:33:59.93

>>861
RustのAddトレイト実装によって足し算(a + b)のみを他の型でも自由に使えるようにできる機能をHaskellは持っていないということ？
そのためHaskellではやむを得ない代替処置としてHoge型を型クラスNumへ入れてしまうことで解決したということ？

例えばRustではStringについてもAddトレイト実装があり
let s = String::from("abc");
assert_eq!(s + "xyz", String::from("abcxyz"));
といったこともできます
同様に自作の型に対しても足し算のみの実装が可能です
Haskellではこのようなケースでもオーバースペック気味にNumを使うしかないのでしょうか？

**デフォルトの名無しさん** · 2023/07/30(日) 12:37:15.22

>>862
Haskellでは実行時エラーを覚悟しろという点は非常に困りますね
今回のケースも無理やりにNumへ入れてしまったのに足し算しか実装していないから引き算や掛け算などで実行時エラーとなるわけですよね

ちなみにRustのnumクレートでは
trait Num: Zero + One + NumOps + PartialEq とトレイト境界があり
impl NumOps for T where T: Add + Sub + Mul + Div + Rem {} の実装があります
つまり自作の型で使う場合は全ての演算を実装した上で更に加えて
impl Num for Foo とするとようやくNumになれます
したがってRustでは不備があればコンパイル時エラーとなり安心して安全に使うことができます

**デフォルトの名無しさん** · 2023/07/30(日) 12:47:58.55

そろそろ隔離スレ行ってろカスども

**デフォルトの名無しさん** · 2023/07/30(日) 14:02:34.57

Haskell 的には演算子オーバーロードを目的として型クラスを使うことはしない。
Num な性質を持つ値の操作として + という名前の演算子もあるというだけで、
演算子として + を使いたいから型クラスの実装を定義するということはしないってこと。
それに、 Num はいくつかの演算子を使えるというだけではなく
それらの演算子の関係で満たさなければいけない性質があるので個々の演算子 (に結び付く型クラス) として分解できない。
https://hackage.haskell.org/package/base-4.18.0.0/docs/Prelude.html#t:Num

価値観が違う。

なんせ Haskell では記号を組み合わせていくらでも演算子を作ることが出来て
たとえば <$> とか >>= とかいう変な演算子を必要なだけ作れるので少ない演算子を取り合う必要がない。

Num の性質の中で + を使うってのと、
なんらかの足し算っぽい操作は別の名前で定義されているべきだし、
Haskell ではそれで困らない。

価値観が違う。

**デフォルトの名無しさん** · 2023/07/30(日) 18:06:30.12

新設の見慣れぬ演算子の種類を勝手に増やして各々が異なる意味付けすることは可読性を下げるのみで百害あって一利無し

>>862
コンパイラがエラーを吐かずに実行時エラーとなるのはマズいな
Haskellの価値観はよくない

**デフォルトの名無しさん** · 2023/07/30(日) 19:58:32.75

すいません、筆が滑りました
もちろんコンパイル時にエラー吐きます
以前のHaskellだと例えそのプログラムで使われてない場合でも実装しないとエラー吐いてました
しょうがないのでwhere句に使いもしないのに
_ * _ = undefined
signum _ = undefined
....
を書いてました
流石に無意味すぎて使わないのは書かなくて良いことになったようです
使ってるのに未実装はもちろんコンパイラが見つけてくれます

**デフォルトの名無しさん** · 2023/07/30(日) 20:06:02.24

どうでもいいけど signum という名前を見るとヴォルケンリッターを連想してしまう……

**デフォルトの名無しさん** · 2023/07/31(月) 08:16:09.72

どうでもいいなら・・・煽りたくなるな

**デフォルトの名無しさん** · 2023/07/31(月) 10:23:47.98

use Hoge::prelude::*; って良く観るがダサいなー

**デフォルトの名無しさん** · 2023/07/31(月) 10:35:07.69

でもまあ機能ごとにモジュールを整理しても
それとは別によく使う集合があるのも現実だし。

**デフォルトの名無しさん** · 2023/07/31(月) 11:07:00.50

global 禁止(キリっ

**デフォルトの名無しさん** · 2023/07/31(月) 12:25:28.59

>>871
preludeは邪道で非推奨
自動適用される標準ライブラリのprelude以外は使わない＆設けない
例えばtokio::preludeも廃止された

**デフォルトの名無しさん** · 2023/07/31(月) 12:34:21.81

Rustで、Vecに要素を追加したとき、メモリ不足で
メモリ確保に失敗した場合、どうなるんですか？
C++の場合は「例外」がthrowされますが。

**デフォルトの名無しさん** · 2023/07/31(月) 14:38:56.18

pqnic

**デフォルトの名無しさん** · 2023/07/31(月) 16:40:54.67

ﾋﾟｸﾆｯｸ?

**デフォルトの名無しさん** · 2023/07/31(月) 17:53:43.20

fn っていちいち略さなくても function でよくない？

書き込める変数の宣言に mut ってつけるのもダサい

**デフォルトの名無しさん** · 2023/07/31(月) 18:05:43.81

mutはガチでダサい
何かいい記号はなかったのかとｗ

**デフォルトの名無しさん** · 2023/07/31(月) 18:13:53.64

英語圏の人たちはmut見てcoolに感じるとか日本人と感性が違う可能性がある

**デフォルトの名無しさん** · 2023/07/31(月) 18:38:57.32

>>878
感性が古いよ

**デフォルトの名無しさん** · 2023/07/31(月) 18:48:05.02

今までミュートと読んでいた

**デフォルトの名無しさん** · 2023/07/31(月) 18:49:54.52

unicode解禁にして変にすればいい

**デフォルトの名無しさん** · 2023/07/31(月) 20:49:15.69

>>881
短い略語を使いたがるのはメモリ容量が少なかった昔の習性・感性だろ。
昔に作られた言語のFortranとPascalですらfunctionは略さなかったのに、
今になって変な略語を採用したRust開発者は工学的センスも美的センスもない。

比較的新しい言語のF#はmutと略さずにmutableと書く。

**デフォルトの名無しさん** · 2023/07/31(月) 21:15:27.96

BASICの頃はDEF FNと言うので関数を定義してた

**デフォルトの名無しさん** · 2023/07/31(月) 21:25:40.03

様々なプログラミング言語があって千差万別な中
大した問題ではないキーワード名やその多少の長さに文句をつける人はダメな仕事できないやつ
仕事できる人は文法とその意味論を比べる

**デフォルトの名無しさん** · 2023/07/31(月) 21:34:38.41

ダサいのはダサい

今後何があってもbegin end区切りの言語は使わないと思う
delphiやってた時もimplementationと言うのを見てクソダサいなと感じた
Objective-Cも二度と接することはないだろう

**デフォルトの名無しさん** · 2023/07/31(月) 22:59:44.59

kotlin や swift の前で同じこと言えるの？

**デフォルトの名無しさん** · 2023/07/31(月) 23:19:46.93

implementation　Point　{
public function ...
｝

**デフォルトの名無しさん** · 2023/08/01(火) 03:00:40.65

>>880
constより2文字も短い！かっけええぇぇぇ！！！
かもな
同意しないけど

**デフォルトの名無しさん** · 2023/08/01(火) 03:53:49.10

constは定数だからコンパイル時に静的に確定する
immutableかmutableかというのはconstとは無関係な概念で実行時の変数の値が書き換わるかどうか
つまりRustの非mut (immutable)は定数ではなく実行時に値が決まる変数

**デフォルトの名無しさん** · 2023/08/01(火) 11:16:59.87

let x : u32 = 1234;
と
const x : u32 = 1234;
は違うんですか？

**デフォルトの名無しさん** · 2023/08/01(火) 11:22:28.49

なるほど、const = の右辺値はconst 文脈で書かれていてコンパイル時に決定できないといけないけど let = の右辺はその制約がないのか

**デフォルトの名無しさん** · 2023/08/01(火) 17:52:49.94

constはコンパイル時に値が決まる定数となり定数名は大文字で書く
letは(mutの有無に関係なく)実行時に値が決まる変数となり変数名は小文字で書く
mutの有無はその変数の値が書き換えられるかどうかだけの違い

**デフォルトの名無しさん** · 2023/08/01(火) 18:49:11.32

自分は素人だけどそれじゃあ型に対する言及が抜けてないですか？

**デフォルトの名無しさん** · 2023/08/01(火) 20:27:35.06

型とは直交する概念なので型とは無関係
任意の型で成り立つ

**デフォルトの名無しさん** · 2023/08/01(火) 22:08:28.57

'static

**デフォルトの名無しさん** · 2023/08/01(火) 22:38:58.55

constはシャドーイングは行われない
変数と違い型を必ず明示しなくてはならない

**デフォルトの名無しさん** · 2023/08/02(水) 00:09:43.49

>>898
なんでですか？
constシャドーイングしてなんか不都合あります？

**デフォルトの名無しさん** · 2023/08/02(水) 00:12:43.58

>>892
constならROM領域に置ける

**デフォルトの名無しさん** · 2023/08/02(水) 00:12:59.71

あ、わかった
そりゃそうだ

**デフォルトの名無しさん** · 2023/08/02(水) 09:00:43.40

関数名というか関数を格納した変数？にもmut付けるときあるけど
動作中に関数を変えるのが目的？って表明以外の意味ある？

**デフォルトの名無しさん** · 2023/08/02(水) 13:19:46.95

関数ポインタかラムダ式（クロージャ）かで意味が変わりそうだな

関数ポインタの場合は途中で別の同型の関数に差し替えるときにmutが必要
クロージャの場合は途中で内部の変数が変更される（FnMutになる）ときにmutが必要
（クロージャは型の関係で別の関数に差し替えることはできないはず）

下の例だとf,gのどちらもmutがないと怒られる

fn print_foo() { println!("foo"); }
fn print_bar() { println!("bar"); }

fn main() {
let mut f: fn();
f = print_foo;
f();
f = print_bar;
f();

let mut i = 0u32;
let mut g = move || { println!("{i}"); i += 1; };

for _ in 0..5 { g(); }
}

**デフォルトの名無しさん** · 2023/08/02(水) 13:23:57.98

そこに置かれてる値（関数ポインタ or クロージャ）が変更されるという意味では同じか

**デフォルトの名無しさん** · 2023/08/02(水) 18:24:39.32

let mut hoge; じゃなくて

むしろ let hoge = 3; と mut hoge = 3; の二種類に分ければ美しくてよ

**デフォルトの名無しさん** · 2023/08/02(水) 19:02:02.79

static mut もあるし
letはパターンマッチ文だからlet (mut a, b) もあるし
if let Some((ref mut p, ref q)) もあるし

**デフォルトの名無しさん** · 2023/08/02(水) 20:18:56.34

>>905
それは無い

**デフォルトの名無しさん** · 2023/08/03(木) 07:43:41.06

速い！安全！ださい！

**デフォルトの名無しさん** · 2023/08/03(木) 08:17:38.34

>>906
mutを単独キーワードに分離したRustの設計方針の勝利だな

**デフォルトの名無しさん** · 2023/08/03(木) 10:00:57.61

かわいい
北朝鮮みたい

**デフォルトの名無しさん** · 2023/08/03(木) 21:15:21.47

こんなスレ見てるなんてダサいぞ！

**デフォルトの名無しさん** · 2023/08/04(金) 09:07:52.99

かわいい
埼玉県みたい

**デフォルトの名無しさん** · 2023/08/06(日) 17:59:34.17

任意長整数型演算の実装の演習してるんですけど

・和の時には下の桁から、大小の比較の時は上の桁から順次比較するので双方からのアクセスをO(1)で行いたい
・任意長なので加法のときにover flowしたときitemの追加ができないとダメ

この場合どのcollection型が有利ですか？
ソースが難しすぎてわかりません
情報お願いいたします

**デフォルトの名無しさん** · 2023/08/06(日) 19:27:39.64

自分ならVec使う

**デフォルトの名無しさん** · 2023/08/06(日) 19:29:40.12

>>913
何を問題にしているのかわからない
言語に関係なく連続体のデータ型(配列やベクタなど)の順次アクセスは
前から後ろから関係なくサイズNに対して総コストO(N)で1つあたりO(1)
それらのうち固定長ではなくサイズを伸ばせるデータ型(ベクタ)なら要素を追加できる
RustならVec

**デフォルトの名無しさん** · 2023/08/06(日) 20:21:24.84

>>915
各collectionの内部構造がよくわからないんですよ
ソース全部読めてなくて
vecってLinkedLustみたいな数珠繋ぎじゃないですよね？

**デフォルトの名無しさん** · 2023/08/06(日) 20:24:19.56

>>914
ありがとう
確かに片方だけ伸ばすならbecで良さそうなんですよね
しかし後でよくよく考えたら掛け算の時に一の位の方向にも伸ばせた方が便利な気もしてきて
でもそっちは絶対じゃないんですよね
なんせvecのソースがむずい

**デフォルトの名無しさん** · 2023/08/06(日) 20:32:19.03

ソースよりドキュメントを見なよ。
図つきで解説されてるから。
Vec は必要に応じて自動で再配置する配列ってかんじ。
要素は連続して配置される。

**デフォルトの名無しさん** · 2023/08/06(日) 20:50:29.31

>>918
https://doc.rust-lang.org/std/collections/index.html
とか読んだんですけどよくわからないんですよ
rust専用スレならstd::vec全部目を通せてる人いるかなと
連続して確保される領域の幅とかは指定できます？

**デフォルトの名無しさん** · 2023/08/06(日) 20:51:36.50

>>916
性質が重要なのであってよほどのことがないかぎり実装内部のソースを知る必要はない
LinkedListは極一部の用途を除きほとんどの用途で遅く不利になり今回も考える必要はない
これらは言語と関係なく一般的な話

**デフォルトの名無しさん** · 2023/08/06(日) 21:11:21.94

>>920
とりあえず今はガロアの連分数使って円周率の計算でもやってみようと思ってるんですけど、その場合計算する項のlog orderで桁数が増大していきます
でも例えばbinary splittingとかにすれば桁数の上昇具合が変わってきます
そういう用途に応じて適切なcollection型の使い分けできるようにしたいんですよ
あくまで練習なので
ソース読みはまぁ趣味みたいなもんなんですけどそもそもRustの自習が趣味なので

**デフォルトの名無しさん** · 2023/08/06(日) 21:11:35.12

>>919
だからドキュメント読めってば。
Vec はポインタとキャパシティと長さを管理する仕組みだと書いてある。
https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees
実体が配列だからスライスの形で扱うことも出来る。
もし C++ を知ってるなら設計理念的には vectorと同じ感じとおもっていいと思う。

**デフォルトの名無しさん** · 2023/08/06(日) 21:16:41.06

>>922
まぁ実はちょっと立場上普通の人より深く知ってる事を要求されることが多いんですよ
もちろんRustを並の人より知ってると言えるには後何年か修行しないといけないんでしょうけど、そもそもRustについては趣味なのでそこまで深く理解しなくてもいいとは思ってます
まぁ趣味なのでボチボチ読みます
ありがとうございます

**デフォルトの名無しさん** · 2023/08/06(日) 21:39:48.28

Haskell君と同じ臭いがしますね～w

**デフォルトの名無しさん** · 2023/08/06(日) 22:09:28.45

>>921
何度も書いて伝わっていると思うが各データ型の性質や各用途への向き不向きは使用言語と関係ない話
その適切なcollection型の使い分けというのが仮に必要だとしても各言語と関係なく抽象的なレベルで考えて可否を判断すべきこと
その上でベクタ型のデータ構造では何がいけないのかの問題点も見えてこない

**デフォルトの名無しさん** · 2023/08/06(日) 22:29:25.87

やっぱり>>913のようにサイズが不定である場合にはダメですね

The capacity of a vector is the amount of space allocated for any future elements that will be added onto the vector. This is not to be confused with the length of a vector, which specifies the number of actual elements within the vector. If a vector’s length exceeds its capacity, its capacity will automatically be increased, but its elements will have to be reallocated.

まぁ一般論ではなくて××桁まで計算するとか決めうちして使います
どのみち掛け算最終的にはFourier変換でやってみるつもりなのでその場合不定長だとメチャクチャ難しいし

**デフォルトの名無しさん** · 2023/08/06(日) 22:59:01.67

>>926
不定長なら再配置を含めてもVecが有利
再配置コストは例えば2^nから2^(n+1)へ広げる度にしか発生せず誤差となる
それよりも連続領域に配置されることによるメモリキャッシュ効果が絶対に効く

**デフォルトの名無しさん** · 2023/08/06(日) 23:14:54.40

>>927
そうなんですか？
でもドキュメントには続いて

For example, a vector with capacity 10 and length 0 would be an empty vector with space for 10 more elements. Pushing 10 or fewer elements onto the vector will not change its capacity or cause reallocation to occur. However, if the vector’s length is increased to 11, it will have to reallocate, which can be slow. For this reason, it is recommended to use Vec::with_capacity whenever possible to specify how big the vector is expected to get.

とありますよ？

**デフォルトの名無しさん** · 2023/08/06(日) 23:50:23.90

それを読んで再配置があった場合でも1回あたりO(1)で済んでいることが理解できないならば
Rustの勉強でもなくプログラミングの勉強でもなくCSなどの基礎から学ぶことをおすすめする
そういう基礎を理解しないままO(1)で行ないたいと最初の質問で書いていたのもヤバい
何度も伝えているが各言語と関係なく成り立つ話なのだから各言語に立ち入る前に理解を済ませておくべき

**デフォルトの名無しさん** · 2023/08/07(月) 00:14:34.21

>>929
>CSなどの基礎から学ぶことをおすすめする
任意長整数型演算の実装の演習をするような人ならCSで学ぶ程度の知識はあるんじゃなのか
当然、データ構造についても一通りの知識はあると思うが

**デフォルトの名無しさん** · 2023/08/07(月) 00:41:08.66

“amortized O(N)”を”1回あたりO(1)”に変換するあたりは流石オジ
でもCS基礎を学べというオジの主張に今回ばかりは同意するよ

**デフォルトの名無しさん** · 2023/08/07(月) 00:47:42.86

>>929なんでO(1)で済むんですか？
そもそもデータ全体を連続領域に確保するんでしょ？
その延長する部分のヒープがもう埋まってたらデータ全部丸写しするしかないんじゃないですか？
大体そもそもデータを連続領域に確保して前からも後ろからも関係なくアドレス1発でアクセスもできて、その上データの追加もO(1)でできるとかなら無敵じゃないですか？
そんな魔法のよなメモリ管理できるハズないのでは？

**デフォルトの名無しさん** · 2023/08/07(月) 00:48:41.30

Vecって単純過ぎてデータ構造では扱わなかったりするのかな
ならし解析では最初に出てきそうなネタだけど

**デフォルトの名無しさん** · 2023/08/07(月) 00:50:22.19

ああ、データの読み書きが一回あたりI(1)ですか
でも今データの追加は整数の桁数が一上がるごとに発生するんですよ？
あらかじめデータの桁数が不明でそれが難しいと言ってるじゃないですか
足し算のたびにコピー発生しますよ？

**デフォルトの名無しさん** · 2023/08/07(月) 00:53:46.05

こいつぅ
絶対わかってないやんw

**デフォルトの名無しさん** · 2023/08/07(月) 00:53:52.95

実際バイナリスプリッティングでマクローリン級数で足し算する場合とかどうやってあらかじめ必要桁数予言するの

**デフォルトの名無しさん** · 2023/08/07(月) 00:54:45.54

実際どんな用途かも具体的に書いてるのに

**デフォルトの名無しさん** · 2023/08/07(月) 02:21:35.00

2年くらい前の過去スレと今の状況見比べて泣いちゃった

**デフォルトの名無しさん** · 2023/08/07(月) 10:50:23.98

ここまでvecdeq無しとは

**デフォルトの名無しさん** · 2023/08/07(月) 18:18:54.25

VecDequeもその名の通りVec(正確にはどちらもRawVec)で作られていて
確保されている連続領域に対して未使用領域が末端か途中かの違いしかない

>>932は確保されている連続領域が埋まった時のコストを気にしているようだが
サイズNが埋まるまでの再配置の総コストは最悪ケースでもわずかN-1回の読み書きコストで済む

例えばサイズN/2が埋まった時にその倍のサイズNの新たな連続領域へ再配置するためにはN/2回の読み書きが発生
仮に最悪ケースでサイズ1からスタートしてもそれまでの累積の再配置コストはN/2+N/4+N/8+...+1 ＝ N-1が上限値となる
つまりサイズNが埋まるまでの再配置の総コストは最悪のケースで読み書きN-1回でありO(N)で済む

一方でサイズNが埋まるまでの再配置以外の読み書きが何回行われるかを今回のケースで考えると
次々とサイズが倍々に増えていく計算の場合は最小でも合計O(N)回の読み書きが起こり
次々とサイズがリニアに増えていく計算の場合は最小でも合計O(N^2)回の読み書きが起こり
もっと緩やかにサイズが増える場合や上述の増え方の場合でも普通に読み書きが多い計算なら合計O(N^2)を超える
現実のほとんどの計算においてVecの再配置コストO(N)は誤差となる

**デフォルトの名無しさん** · 2023/08/09(水) 00:49:09.66

>>930
＞当然、データ構造についても一通りの知識はあると思うが

今までのレス読んでそう思う？

**デフォルトの名無しさん** · 2023/08/09(水) 18:58:03.94

でも競プロでvec.insert(0, value)でタイムアウトしたけどvecdeque.pushfront(value)ではタイムアウトしなかった経験があるな

**デフォルトの名無しさん** · 2023/08/09(水) 19:31:59.29

VecDequeはring bufferだから連続性は保証されないね
VecみたいなDerefがないから&[T]に渡せない
slice未実装かと思ったら2つのsliceで返すas_slices()が実装されてて思ったより芸が細かかった

**デフォルトの名無しさん** · 2023/08/09(水) 22:17:02.23

>>942
そのinsertはずらすコピーが毎回O(N)かかるからサイズNになるまでの累計はO(N^2)になってしまう
一方で満杯になったときの自動再配置コピーコストの方は累計でO(N)だからさほど気にしなくていい

>>943
その時の状態配置に応じて最小コピーで連続領域にしてくれるmake_contiguous()で
連続1本になった&mut [T]を得られるのでVecDeque内でのsort()なんかもできちゃうね

**デフォルトの名無しさん** · 2023/08/10(木) 04:07:06.41

>slice未実装かと思ったら2つのsliceで返すas_slices()が実装されてて

He-

**デフォルトの名無しさん** · 2023/08/10(木) 04:08:51.37

vecdequeはlinkedlistじゃね

**デフォルトの名無しさん** · 2023/08/10(木) 06:08:17.32

vecdequeはもちろんvecで構成
linkedlistは他のデータ構造(vector, binary tree, hash table)と比較してほとんどの用途で遅く不利なため極限られた用途でしか用いられない
linkedlistが用いられる限られた用途でもlinkedlistの欠点を補うため同時にhash tableやbinary treeなどと組み合わせて用いられることも多い

**デフォルトの名無しさん** · 2023/08/11(金) 08:01:08.13

>>930
データ構造なんて知らなくてもできる
中学生の頃やってた

大学入った1年の前期でプログラム実習があってそこでも多倍長整数演算の計算をやった
配列で計算すんの
何も難しいことはない

**デフォルトの名無しさん** · 2023/08/11(金) 08:22:37.37

RustやるならCSでもまず計算モデル(特にスタックフレームモデル周辺)だろ。

**デフォルトの名無しさん** · 2023/08/11(金) 08:37:22.11

>>948
その配列というのが長さと場所を固定した連続領域を取るデータ構造なのよ
Vecは同じ連続領域だけど長さと場所は可変なデータ構造
VecDequeはVecを用いたリングバッファで連続領域を確保して使っているけど使用データ自体は最大二つの領域に分かれるデータ構造
LinkedListは連続領域を使わない連結リストといったようにいろいろあるデータ構造の中で質問者はどれを使うべきか悩んでるみたい

**デフォルトの名無しさん** · 2023/08/11(金) 11:19:59.50

最近おかしな議論が複数のスレにまたがって続いてるけど
多倍長整数というワードすら出てこないんだからなあ