C vs C++ vs Rust Part.2

**デフォルトの名無しさん** · 2021/12/15(水) 12:35:50.91

競え
※前スレ
C++ vs Rust
https://mevius.5ch.net/test/read.cgi/tech/1619219089/

**デフォルトの名無しさん** · 2021/12/18(土) 03:05:51.15

>>84
例えばCのfor文などと比較すると、
その変化していく変数は構造体の中だが大元の関数のスタック上すなわちローカル変数と同じだからCと変わらん
あとinline展開指定されてるものなどで関数呼び出しオーバーヘッドも消えて前後のコードが繋がって最適化されるパターンもある
だから気にせずに使っても誤差範囲

**デフォルトの名無しさん** · 2021/12/18(土) 03:17:03.48

RustってC++に似てるな
ゲロみたいな構文だ

**デフォルトの名無しさん** · 2021/12/18(土) 03:38:45.07

>>85
結局メソッドチェーンとは別問題として
一般的にVecやStringなどのヒープ使うものがループ内にあると注意やな
あとcollectでスタック使うArrayVecやArrayStringを指定する手もあるな

**デフォルトの名無しさん** · 2021/12/18(土) 04:55:38.30

>>69
> 配列 [4, 9, 3, 7, 1, 8, 5] から文字列 "9-8-7-5-4-3-1" への変換
> a.iter().sorted().rev().map(|n| n.to_string()).join("-")

このコード自体は他言語との類似比較のために冗長に書かれていて無駄がある
join("-")はDisplay実装あれば通るから事前のto_string()は不要
つまりa.iter().sorted().rev().join("-")でOK

さらにsorted()はヒープに結果Vecを確保する
もし元を書き換えていいならヒープ確保をjoin()でのString一つだけで済む

let mut a = [4, 9, 3, 7, 1, 8, 5];
a.sort();
assert_eq!("9-8-7-5-4-3-1", a.iter().rev().join("-"));

このrev()を無くすためにa.sort_by(|x, y| y.cmp(x))にするとcmp関数でやや不利
一方でrev()使用は配列やVec相手ならDoubleEndedIterator実装があるからコストかからない
現実にはこのコードが核心部分でなければそこまで気にしなくていいけどな

**デフォルトの名無しさん** · 2021/12/18(土) 05:17:14.76

一つだけアドバイスしとくけど、ジェームス・ボンドが日本人だったら、大木・凡人だからね。

**デフォルトの名無しさん** · 2021/12/18(土) 08:35:30.45

>>74
Rustを使ってればカッコイイという錯覚で、何も分かってないのに汚物のようなコードと意味不明な長文をまき散らす…
あんなに単純な初期のJavaやC#でさえスパゲッティコードだらけなのに、日本語の説明さえも気持ち悪い

**デフォルトの名無しさん** · 2021/12/18(土) 10:28:10.29

>>91
こじらせてんな
ゲロコード君とは違う方向性だが

**デフォルトの名無しさん** · 2021/12/18(土) 11:41:10.36

長文二人は属性が似過ぎだろ
こんなのが二人もいればRustスレが気持ち悪くなるわな

**デフォルトの名無しさん** · 2021/12/18(土) 16:44:21.13

顔真っ赤で根拠も反論もない「こじらせてんな」マンが永遠と長文や短文を書き、本Rustすれに代わりキチガイを集めるスレ

**デフォルトの名無しさん** · 2021/12/18(土) 17:42:36.78

延々とな
ガイジそう

**デフォルトの名無しさん** · 2021/12/18(土) 18:08:14.57

元々rustスレの隔離スレなんだから大成功でしょ

**デフォルトの名無しさん** · 2021/12/18(土) 20:19:16.51

>>91
>あんなに単純な初期のJavaやC#でさえスパゲッティコードだらけなのに、日本語の説明さえも気持ち悪い

文の前半と後半のつながりが全くわからないので解説頼む

**デフォルトの名無しさん** · 2021/12/18(土) 21:02:25.05

> この難しさを取り除くために、Rustは、C/C++の落とし穴を排除し、その過程で使いやすく役に立つ
> 洗練された一連のツールを提供します。低レベルな制御に「下がる」必要があるプログラマは、
> C/C++のクラッシュやセキュリティホールのリスクを負わず、気まぐれなツールチェーンのデリケートな
> 部分を学ぶ必要なくRustで同じことができます。さらにいいことに、 Rustは、スピードとメモリ使用の観点で
> 効率的な信頼性の高いコードへと自然に導くよう設計されています。

**デフォルトの名無しさん** · 2021/12/18(土) 21:05:46.31

顔真っ赤Rustオジサンの「＞」、やっぱ同一人物だったかｗ

**デフォルトの名無しさん** · 2021/12/18(土) 21:56:16.22

>>84
その、新しいオブジェクトを生成しまくってるんじゃないか、の意味が曖昧なので
自動的にヒープ領域から動的に新たなメモリ確保をすると解釈すると、それはないです
Rustでもプログラムで明示的に指定しない限り勝手にそういうことが起きることはありません

もちろん例えばVec型(伸長可能な配列)やString型(伸長可能な文字列)を新たに返す関数を使えば
それはプログラムで明示的に指定したことになり、当然ヒープ領域が使われます

一般的にイテレータの長い連鎖があっても各イテレータが返す(＝用いる)構造体は各1つで
それらはコンパイル時に静的に確定してスタック上にローカル変数と同様に領域が確保されます
したがってイテレータ連鎖で動的にヒープが使われうるのは例えば
(1) イテレータがクロージャを引数として取る場合にそのクロージャのコードがヒープを使うものである場合
(2) sorted()のように前イテレータから全要素を一旦受け取る必要がある途中のイテレータが一時格納場所としてヒープを用いる場合
(3) collect()のようにイテレータ連鎖の最後に全要素を収集してVecやStringなどを新たに生成する場合
いずれもそれらの関数やクロージャをプログラムで使用した時のみ、動的にヒープが使われます

**デフォルトの名無しさん** · 2021/12/18(土) 22:26:29.42

何が気持ち悪いかというと
自分も知らなかったことを調べてきてさも知ってたかのように上から目線でレスする精神
気持ち悪い

そしてその内容がいつも間違えてるからゲロ吐く気分になる

**デフォルトの名無しさん** · 2021/12/19(日) 08:59:28.05

多少の間違いがあっても要点をおさえて質問に正面から答えてるんならまだいいんだけどねー
困ったもんだ

**デフォルトの名無しさん** · 2021/12/19(日) 23:44:42.02

間違いがあれば俺が指摘修整してやるから安心しろ
おまえら雑魚はそれでいい

**デフォルトの名無しさん** · 2021/12/20(月) 01:37:10.75

おまえは間違ってるって主張だけだと数学100点の人と同じだぞ
せっかくだからどこが間違ってるか指摘してあげなよ

**デフォルトの名無しさん** · 2021/12/20(月) 01:50:44.40

そいつらは前スレからそんな感じだから放置されてる
ガイジとかゲロとか汚などの言葉を好む
具体的なコードや具体的な指摘は出来ないダメな連中

**デフォルトの名無しさん** · 2021/12/20(月) 13:09:41.04

プログラム勉強しはじめたんだけど、CとかC++よりもRUSTのほうがかっこよさげだからRUSTやってる

**デフォルトの名無しさん** · 2021/12/20(月) 17:47:27.57

意識他界系かよ

**デフォルトの名無しさん** · 2021/12/20(月) 18:01:18.12

CやLispからはじめるのが意識高い系
Rustからはじめるのはカッコつけたいだけの単なる無知

**デフォルトの名無しさん** · 2021/12/20(月) 18:21:17.98

C++から始めるのは何系？

**デフォルトの名無しさん** · 2021/12/20(月) 18:34:34.79

CがあるのにC++から始めるひとはガイジ系

**デフォルトの名無しさん** · 2021/12/20(月) 18:37:40.57

10年早い系

**デフォルトの名無しさん** · 2021/12/20(月) 19:11:56.15

ウッホウッホホ、マウンテンゴリラです。得意なのはドラミングで毎日ドコドコやってます

**デフォルトの名無しさん** · 2021/12/20(月) 19:19:22.55

>>108
なんでrustからだとあかんの？

**デフォルトの名無しさん** · 2021/12/20(月) 19:54:01.15

マルチパラダイムだからでは。

**デフォルトの名無しさん** · 2021/12/20(月) 20:10:25.93

>>114
よく知りもせんなら黙ってろや

**デフォルトの名無しさん** · 2021/12/20(月) 20:22:01.28

最近c++勉強始めたんだが、cとかmapも使えないじゃん
どうしてんの？

**デフォルトの名無しさん** · 2021/12/20(月) 20:29:53.40

mapを作るための言語がCだから。

**デフォルトの名無しさん** · 2021/12/20(月) 21:00:54.00

RustはコンパイラもライブラリもRustで書かれているね

**デフォルトの名無しさん** · 2021/12/20(月) 21:10:35.52

>>116
昔はアルゴリズムの教本を参考にして全部1からつくってた

**デフォルトの名無しさん** · 2021/12/20(月) 21:56:05.64

今も必要があれば車輪の再発明をする能力を持つ人と持たない人にプログラマーは二分される
前者は新たな枠組みを作ることも可能な生産者
後者は既存の枠組みを使うだけの消費者

**デフォルトの名無しさん** · 2021/12/20(月) 23:37:11.43

俺には検討もつかんわ
所詮俺は消費者か…

**デフォルトの名無しさん** · 2021/12/20(月) 23:37:21.66

見当

**デフォルトの名無しさん** · 2021/12/20(月) 23:47:18.19

コンシューマーって言えばカッコよくなるよ。

**デフォルトの名無しさん** · 2021/12/21(火) 02:18:43.99

プロデューサーとコンシューマーと呼ぶと両方存在して初めて意味を持ちそうな感じがするな

**デフォルトの名無しさん** · 2021/12/21(火) 02:38:28.55

この場合の生産者は、制作者(プロデューサー)ではなくて創造者(クリエイター)の方が近い

**デフォルトの名無しさん** · 2021/12/21(火) 08:29:08.29

もっともらしく言ってるけど
新たな枠組みを作ることができるかどうかに
車輪の再発明をする能力は関係ないよ

**デフォルトの名無しさん** · 2021/12/21(火) 08:37:17.38

プログラミングにおいて車輪の再発明すら出来ない人が
プログラミングにおいて新たな枠組みを作るのは無理

**デフォルトの名無しさん** · 2021/12/21(火) 08:59:49.41

ザッカーバーグとかツールレベルでいえばあるもの使ってただけだがな。

**デフォルトの名無しさん** · 2021/12/21(火) 09:42:52.55

クイックソートくらいは自作してみたほうがいい
最初混乱するだろうけど、ああなるほど！となった時に必ず経験値に加算される筈だ

**デフォルトの名無しさん** · 2021/12/21(火) 10:37:29.68

>>128
そりゃ彼はプログラミングにおいて新たな枠組みを作ったわけではないからな

**デフォルトの名無しさん** · 2021/12/21(火) 12:47:53.03

新たな枠組みって例えば何？
フレームワークのことではなさそうだけど

**デフォルトの名無しさん** · 2021/12/21(火) 13:12:13.10

例えば画像データの取り扱いでbitmapをそのまま処理していたような時代にpngやjpgなどのアルゴリズムをはじめて考え出して
実装したようなプログラマが新たな枠組みを作ることが出来る人
既存のライブラリ使って画像処理や表示のアプリを実装しているようなプログラマが枠組みを使うだけの人

**デフォルトの名無しさん** · 2021/12/21(火) 13:13:16.14

もちろん例としてプログラミングのフレームワークでもいいんじゃね？
例えばそのザッカーバーグの例ならば
Facebook社はプログラミングにおいて新たな枠組みとして世間にも広まるほどのReactを作った
一方でザッカーバーグ自体はReactを今から車輪の再発明すらできないしプログラミングにおいて新たな枠組みを作れないだろう

**デフォルトの名無しさん** · 2021/12/21(火) 14:51:21.09

枠組みに限らず何か新しいもの自力で作るには
その対象レイヤーのものを作れる能力は必要
それは当たり前

ザッカーバーグだって掲示板システムを実装する能力があったからFacebookを作れたわけだが
それを「車輪の再発明する能力」と呼ぶのかどうか

「新しい枠組み」と「車輪の再発明をする能力」の定義が曖昧すぎて中身がない

**デフォルトの名無しさん** · 2021/12/21(火) 14:53:33.71

結局のところ
「低レイヤーの開発をするには低レイヤーの実装能力が必要」という主張でしかない

**デフォルトの名無しさん** · 2021/12/21(火) 15:02:25.60

そこは定義でもめるから深入りしない
例えば例に挙げたReactは自分の観点からは低レイヤーではなく高レイヤー
結局これでいいかね？

各分野のプログラミングにおいて車輪の再発明すら出来ない人が
その分野のプログラミングにおいて新たな枠組みを作るのは無理

**デフォルトの名無しさん** · 2021/12/21(火) 16:17:27.88

車輪の再発明って何
自身で模倣できる程度には理解しているということ？

**デフォルトの名無しさん** · 2021/12/21(火) 17:55:52.77

レイヤーは相対的なものだよ
低レイヤーで通じないなら下位レイヤーとでも言おうか

Reactのユーザーから見ればReactそのものの開発は下位レイヤー
Reactを作るために下位レイヤーのJavaScriptエンジンやレンダリングエンジンを再発明できる能力が必要か？

**デフォルトの名無しさん** · 2021/12/21(火) 19:16:57.14

話はシンプル
それぞれの分野で見ればよい

Reactの分野だったら
『自分でウェブフロントフレームワークを簡易なものでよいから作ったことあるか？あるいは作れるか？』
これだけの話

つまりReactの開発者たちと同じような立ち位置に立てるプログラマーなのか、
それともReactの消費者としてユーザーの立場のプログラマーなのか、の違い

**デフォルトの名無しさん** · 2021/12/21(火) 21:33:34.81

まとめると
「新しいウェブフロントフレームワークを作るには
ウェブフロントフレームワークを作る能力が必要」

そりゃそうだ
話はシンプルシンプル

**デフォルトの名無しさん** · 2021/12/21(火) 22:16:57.85

なんだよこれ遅っせーなー
意味分かんねーんだよこの挙動
俺のほうがもっとうまく作れる

**デフォルトの名無しさん** · 2021/12/21(火) 23:02:50.37

消費者プログラマーは色んな仕組みをわかっていなかったり理解できなかったりする人が多いね
そうなると車輪の再発明すらできないし車輪の改良もできない
もちろん車輪に代わる新たな仕組みを作り出すこともできない

**デフォルトの名無しさん** · 2021/12/21(火) 23:19:52.13

>>138
これ本気で言ってるのか

**デフォルトの名無しさん** · 2021/12/21(火) 23:37:27.40

元の話はmapの実装方法がわからない、だから、もっと深刻な状況なのか
プログラミングする上での基本的なことは
車輪の再発明であろうと自分でやってみて体験していくべき

**デフォルトの名無しさん** · 2021/12/22(水) 00:26:44.89

習熟のために必ずしも車輪の再発明が必要であるわけではないでしょ

**デフォルトの名無しさん** · 2021/12/22(水) 03:14:26.40

発明する必要はないけど何もないところから自分の力だけで車輪を組み立てられるようにはなっておいた方が良い

**デフォルトの名無しさん** · 2021/12/22(水) 04:06:02.73

Cをやるとそういう力が身に付く

**デフォルトの名無しさん** · 2021/12/22(水) 13:40:20.98

「フロントフレームワーク」なんて言い方するのかとググったら、まぁまぁ居たわ

**デフォルトの名無しさん** · 2021/12/22(水) 14:48:58.75

IPアドレスの正規表現を再発明してるやつがいたけど
ああいうのが"新しい枠組みを作ることも可能な生産者"だったのかw

**デフォルトの名無しさん** · 2021/12/22(水) 15:12:06.24

IPアドレスの仕組みも正規表現も別に目新しいものではないのでは？
何か特別な表現手法とかを導入する余地って残されていたか？

**デフォルトの名無しさん** · 2021/12/22(水) 15:54:00.21

正規表現とか言ってもただの文字列だからな
数式やアルゴリズムに落とし込めないもので再発明も何も手の出しようがないだろ

**デフォルトの名無しさん** · 2021/12/22(水) 16:28:01.11

使ってる言葉を自分なりに定義できないやつは普段物事を深く考えてない
知性の程度を簡単に測れる物差し

**デフォルトの名無しさん** · 2021/12/22(水) 16:32:42.08

つまり…？

**デフォルトの名無しさん** · 2021/12/22(水) 18:46:01.74

>>151
えっ？
正規表現⊆アルゴリズム
じゃない？

**デフォルトの名無しさん** · 2021/12/22(水) 19:48:14.08

正規表現は文字列の集合を表すだけですよ。

**デフォルトの名無しさん** · 2021/12/22(水) 20:06:24.06

ある正規言語に対応する文字列やろ

**デフォルトの名無しさん** · 2021/12/22(水) 20:08:22.67

ただの検索や置換のためだけのメタ言語だよ
問題記述能力はない

**デフォルトの名無しさん** · 2021/12/22(水) 22:30:17.60

問題記述能力？

**デフォルトの名無しさん** · 2021/12/22(水) 23:57:26.44

>IPアドレスの正規表現を再発明してるやつがいたけど

再発明って具体的にどういうことやってたことを言っているんだろ

**デフォルトの名無しさん** · 2021/12/22(水) 23:58:38.64

そのケースはアルゴリズムではないな
一般的に自分で一から作れる人はその時々に応じて最適なアルゴリズムを見つけ出すだろう

**デフォルトの名無しさん** · 2021/12/23(木) 00:18:12.96

何がアルゴリズムで何がアルゴリズムでないか
ちゃんと境界値テストできてる？

**デフォルトの名無しさん** · 2021/12/23(木) 00:20:51.73

数式はアルゴリズムなのか？

**デフォルトの名無しさん** · 2021/12/23(木) 00:32:50.26

俺がすごいと思ったらすごいというのをいかに客観的評価のように見せるか議論しているようにしか見えない

**デフォルトの名無しさん** · 2021/12/23(木) 00:47:38.83

>>163
その通り
ついでに「俺すごい」アピールをしてる

まあ議論には全くなってないがな

**デフォルトの名無しさん** · 2021/12/23(木) 08:21:29.85

>>161
一般的には(決定性)チューリング機械で可能な処理のことだけどな。

なので一部の数式(無限大集合とか)は範囲外。

**デフォルトの名無しさん** · 2021/12/23(木) 10:21:26.98

無限大を数値計算で扱うために優秀なソフトエンジニア達の手によって、例えば離散フーリエ変換や離散ウェーブレット変換などのアルゴリズムが工夫され考え出された
これが新しい枠組みを作り出すということ

**デフォルトの名無しさん** · 2021/12/23(木) 10:33:51.13

無限大の連続量を有限の数値で扱う
フーリエ変換
https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

**デフォルトの名無しさん** · 2021/12/23(木) 11:37:52.36

>>167
FTは無限大集合を扱っている訳では無いだろ。実数とか扱えないし。

**デフォルトの名無しさん** · 2021/12/23(木) 12:01:15.99

周期信号のフーリエ級数展開なら有限だけど連続信号を扱うなら無限積分の計算が必要
FTは無限積分を数値計算するため分割統治のバタフライ演算に落とし込んで更に演算量を抑えるため各種のアルゴリズムが考案されてる

**デフォルトの名無しさん** · 2021/12/23(木) 12:32:25.74

で、新しい枠組みを作り出すことが C vs C++ vs Rust にどう関わってくるの

**デフォルトの名無しさん** · 2021/12/23(木) 12:46:22.58

枠組みを作ることは凡人には無理
殆どは枠組みを使う人
ただ枠組みの仕組みを知らないと使うことも出来ない

**デフォルトの名無しさん** · 2021/12/23(木) 12:56:14.10

最早スレチの話題に突っ込んで悪いけど、無限積分を回避できている気になっているのは気のせいであって、バタフライ演算とか関係ないからね(笑)

**デフォルトの名無しさん** · 2021/12/23(木) 17:57:47.72

以前に皆さま方からアドバイスをいただいて
『足し算のみで素数列を生成するジェネリックなイテレータの実装』
を当時O(N^3)という酷さでしたが、このたびほぼ O(N) の新たなアルゴリズムと実装が出来ましたのでご報告します

足し算の総回数を O(N log log N) すなわちほぼ O(N) 近くにすることに成功しました
具体的には 1億(＝10^8) までの素数生成に必要とする足し算の総回数が 2.5億回とリニアになりました
前回と異なりメモ化をしていますがこちらも工夫により配列の長さを O(√N / log N) に抑えることに成功しました
具体的には 1億(＝10^8) までの素数生成に必要とする配列の長さが 1231 と非常に小さな領域のみで実現できました

10^kまでの素数を順に生成時の足し算の総回数 O(N log log N)
10^1　4.70×10^1＝47
10^2　2.03×10^2＝203
10^3　1.90×10^3＝1903
10^4　1.95×10^4＝19508
10^5　2.12×10^5＝212715
10^6　2.27×10^6＝2278220
10^7　2.41×10^7＝24148110
10^8　2.54×10^8＝254082528

10^kまでの素数を順に生成時の配列の長さ O(√N / log N)
10^1　4
10^2　6
10^3　13
10^4　27
10^5　67
10^6　170
10^7　448
10^8　1231

メモリ使用もこの程度の少なさで
足し算を2.5億回とその比較だけで1億までの全ての素数を順に出力できるようになりました
このスレは数学が得意な方々が多いようなのでご検証よろしくお願いします

**デフォルトの名無しさん** · 2021/12/23(木) 18:08:00.97

今回は読みやすいようにループで記述しました
impl<T> Iterator for 素数生成Iterator<T>
　where T: Copy + num::Zero + num::One + num::CheckedAdd + std::cmp::PartialOrd,
{
　type Item = T;
　fn next(&mut self) -> Option<T> {
　　'次候補: loop {
　　　self.新素数 = self.新素数.checked_add(&T::one())?;
　　　if self.新素数 == self.倍数[self.上限] {
　　　　self.上限 += 1;
　　　　if self.子.is_some() {
　　　　　self.素数.push(self.子.as_mut()?.next()?);
　　　　}
　　　　self.倍数.push(二乗(self.素数[self.上限]));
　　　}
　　　for index in 1..self.上限 {
　　　　while self.倍数[index] != T::zero() && self.倍数[index] < self.新素数 {
　　　　　self.倍数[index] = self.倍数[index].checked_add(&self.素数[index]).unwrap_or(T::zero());
　　　　}
　　　　if self.倍数[index] == self.新素数 {
　　　　　continue '次候補;
　　　　}
　　　}
　　　break;
　　}
　　if self.子.is_none() {
　　　self.素数.push(self.新素数);
　　}
　　Some(self.新素数)
　}
}

**デフォルトの名無しさん** · 2021/12/23(木) 18:17:16.76

上述に「子」とあるのはメモリ節約のためのテクニックで
「子」と「孫」を再帰的に利用しているためです
「自分」だけで必要なメモリをNとすると
「子」を利用することでメモリが√Nで済むように設計しました

また、 self.上限が配列の長さで
self.新素数が1億(=10^8)まで進んだ時点で self.上限が 1231 です
self.上限が更新された時のみ、つまり1億までで1231回だけ
コードにあるように以下の二乗する関数が呼ばれます

fn 二乗<T>(n: T) -> T
　where T: Copy + num::Zero + num::One + num::CheckedAdd + std::cmp::PartialOrd,
{
　let mut count = T::one();
　let mut result = n;
　while result != T::zero() && count < n {
　　count = count.checked_add(&T::one()).unwrap();
　　result = result.checked_add(&n).unwrap_or(T::zero());
　}
　result
}

**デフォルトの名無しさん** · 2021/12/23(木) 18:20:15.44

fn main() {
　assert_eq!(vec![2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127], 素数生成::<i8>().collect::<Vec<_>>());
　assert_eq!(65521, 素数生成::<u16>().last().unwrap());
　assert_eq!(78498, 素数生成::<u32>().take_while(|&p| p < 1000000).count());
}

fn 素数生成<T>() -> 素数生成Iterator<T> where T: Copy + num::One + num::CheckedAdd {
　let 孫 = 素数生成Iterator::<T>::new(None);
　let 子 = 素数生成Iterator::<T>::new(Some(孫));
　素数生成Iterator::<T>::new(Some(子))
}

struct 素数生成Iterator<T> {
　素数: Vec<T>,
　倍数: Vec<T>,
　新素数: T,
　上限: usize,
　子: Option<Box<Self>>,
}

impl<T> 素数生成Iterator<T> where T: Copy + num::One + num::CheckedAdd {
　fn new(子指定: Option<Self>) -> Self {
　　let three = T::one().checked_add(&T::one()).unwrap().checked_add(&T::one()).unwrap();
　　Self {
　　　素数: vec![T::one()],
　　　倍数: vec![three],
　　　新素数: T::one(),
　　　上限: 0,
　　　子: 子指定.map(|子| Box::new(子)),
　　}
　}
}

**デフォルトの名無しさん** · 2021/12/23(木) 18:29:41.75

コードは以上です

今回はitertools::unfold()を用いなかったため、それにより省略できていた、
「イテレータ用構造体の宣言」「その初期化」「そのIteratorトレイト実装宣言」
などが今回は必要となりコードがその分だけ長くなっていますが
イテレータの実装本体部分は>>174のみです

足し算の総回数が O(N log log N)　例: 素数を1億までで2.5億回
メモリは配列の長さが O(√N / log N)　例: 素数を1億までで長さ1231使用
これらを足し算のみで実現できています
どうぞご検証よろしくお願いします

**デフォルトの名無しさん** · 2021/12/23(木) 18:41:40.03

嫌われ者Rusterのウザウザ全文貼り付け、見るのも嫌になる自己満足オナニー

**デフォルトの名無しさん** · 2021/12/23(木) 18:47:57.52

なんかやたら足し算のみで、って強調してるけど、
アルゴリズムはエラトステネスの篩だよね？
そう言ってくれたほうが理解しやすいよ

Rustはまだあんま良くわかってないのでコードは参考になるかも
でもテストケースに127が入ってるのはおかしくない？

**デフォルトの名無しさん** · 2021/12/23(木) 18:49:15.20

あ、おかしくなかった
すまん

**デフォルトの名無しさん** · 2021/12/23(木) 19:25:25.17

アルゴリズムに興味がある場合はCが読みやすいということがよくわかった

**デフォルトの名無しさん** · 2021/12/23(木) 20:59:20.34

1億までの素数を全て求めるのが2.5億回の足し算だけで出来るものなのか？？
メモリもエラトステネスだと1億必要だよな？

**デフォルトの名無しさん** · 2021/12/23(木) 23:06:13.63

一億たって100メガにすぎませんからね。

**デフォルトの名無しさん** · 2021/12/23(木) 23:52:41.64

>>182
1億回の素数判定を個別に考えると平均2.5回の足し算となりもちろん無理です
そこで過去の判定時で用いた足し算の結果を後の判定時に用いる方法で
結果的に平均2.5回の足し算で済ませています

また、単純にエラトステネスのふるいでは1億の長さの配列が必要となりますが
まず時間と空間を逆転させることで必要となる配列の長さを減らしています
さらに再帰的に子と孫のイテレータを活用することで
>>173の表のように1億(=10^8)まで判定時で配列の長さ1231に抑えています
その時点で子と孫では配列の長さ27となっています

>>183
そんなO(N)のペースでメモリを使用していくのはいずれ限界もありますし
メモリキャッシュヒットの観点からも望ましくないと思います

さらに今回は小さい方から順に素数を返すイテレータです
イテレータ利用者は1億を超えて素数を利用するかもしれませんし
逆にもっと少ない小さい数のみ利用するかもしれません
最初に上限が1億など決まって開始する古典的エラトステネスのふるいでは上手くいかないのです

**デフォルトの名無しさん** · 2021/12/24(金) 00:05:23.52

キャッシュヒット率の話するならベンチマークとってくれ