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/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

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

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

わざわざ決まってる数列を順番に出力するイテレータ書くのにそんな記述が必要になるのか
ちょっと普通のループでいいからC言語で書いてみてよ

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

>>185
ベンチマークをとる前に実装が必要だな
その前に新たなアルゴリズムも必要か
エラトステネスの篩は「指定された整数以下の素数を求めるアルゴリズム」だからイテレーターとは相性が悪そうだ

**デフォルトの名無しさん** · 2021/12/24(金) 19:37:12.56

イテレータにすると、プログラミングの方向が変わるんですよ。
詳細を未来に先送りできるんです。
伝統ある手続き型の手法では、システムやライブラリを書く人が詳細を実装し、使う人は大まかな指示を出しましたよね。
イテレータ手法は、未来に詳細を決定する。
つまり使う人が細かいことを決める事になるんです。
そこらへんの詳しい話は、書籍クリーンアーキテクチャに載ってます。
この本に書かれてることがすべて正しいとは言いませんが、正しいことにしろ間違ってることにしろ、読んでおいて損はないです。

**デフォルトの名無しさん** · 2021/12/24(金) 19:43:08.10

イテレータ特有の話と言うより遅延評価全般の話に読めるが

**デフォルトの名無しさん** · 2021/12/24(金) 20:57:48.40

イテレータ万能説を唱えて長文するガチキチおじさんｗｗｗ
yieldはgeneratorをレイトバインド
for(range)はiteratorをレイトバインド
async/awaitはfutrueをレイトバインド
詳細を未来に先送り！キリッｗ

**デフォルトの名無しさん** · 2021/12/24(金) 21:06:12.59

>>190
さあご一緒に、キリツ！

**デフォルトの名無しさん** · 2021/12/24(金) 21:28:57.48

レイト「バインド」？

**デフォルトの名無しさん** · 2021/12/24(金) 21:44:54.12

クリーンアーキテクチャを出してるから遅延評価のことじゃなく
IoCの一例としての高階関数のことを言いたいんじゃないかな？

**デフォルトの名無しさん** · 2021/12/24(金) 22:01:56.18

昔は局所化して先送りにできることは素晴らしいことだと思ってた
でも最近そんなのは些末な事で、無能な働き者が気にすることだったなと考えを改めた
木を見て森を見ずと言うべきか

**デフォルトの名無しさん** · 2021/12/24(金) 22:55:30.83

>>188
ある意味その考え方も正しいかもしれませんが
イテレータは例えば大ざっぱに分けても5種類はあるので
自分が作る部分がどの部分かによってその立場も変わると思います
(1) 発信イテレータ … >>174で示しました素数生成、レンジ(0..n)、配列やVecに対するiter()などチェーンでは先頭に来るもの
(2) 仲介イテレータ … map()、filter()、enumerate()などチェーンでは中間に来るもの
(3) 受信イテレータ … find()、fold()、collect()などチェーンでは最後に来るもの
(4) 合成イテレータ … chain()、zip()、merge()など複数のイテレータを入力とするもの
(5) 創造イテレータ … unfold()などイテレータを生み出す汎用イテレータ
とりあえず(4)(5)は置いとくにしても自分が作る部分は用途によって(1)か(2)か(3)と変わるため大きく立場も異なります

>>189
一般的に遅延評価による先送りといえば主役はクロージャですね
上述したイテレータを作り出すunfold()もクロージャを渡すことで成立しています

>>190
futureは「未来に先送り」ではなく「未来を先取り」と捉えたほうがよくないでしょうか
そして遅延評価というよりも並行並列評価する形になりますね
したがって今回の話には適さないかなと思います

**デフォルトの名無しさん** · 2021/12/24(金) 23:02:03.16

>>186
> わざわざ決まってる数列を順番に出力するイテレータ書くのにそんな記述が必要になるのか

決まってる数列ではなく毎回算出するんですよ
記述については各々のイテレータはそれぞれ何らかの構造体にすぎないので >>176に示しましたように
「(a) イテレータとなる構造体の型宣言」「(b) その構造体の初期値定義 new()」「(c) 今回は自分と子と孫がいるためその関係記述」
があってようやく、>174に示しました「(d) イテレータ自体の毎回の算出コード」がそこに加わります
一般的にも今回の特殊な用途(c)を除いた3つ(a)(b)(d)は必要です
さらに>>195でいうところの仲介型イテレータはそれらの記述に加えて
「(e) 他のイテレータのメソッドとなりチェーンできるようにするための宣言」がさらに必要となります

上述(a)(b)(d)の部分の記述だけならば
お手軽にイテレータを生成できる itertools::unfold() を使えるケースだと
例えばフィボナッチ数列を返すジェネリックなイテレータは
以下のように初期値と処理クロージャを1つunfold()に与えてやればイテレータを作れます

fn fibonacci<T>() -> impl Iterator<Item=T>
　where T: Clone + num::Zero + num::One + num::CheckedAdd + std::cmp::PartialEq,
{
　itertools::unfold((T::one(), T::one()), |(m, n)| {
　　if *m == T::zero() {
　　　// overflow
　　　return None;
　　}
　　// shift: ret <- m <- n <- next
　　let next = m.checked_add(&*n).unwrap_or(T::zero());
　　let ret = m.clone();
　　*m = n.clone();
　　*n = next;
Some(ret)
})
}

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

>>185
そのためにもぜひ異なるアルゴリズムの実装を作ってくださるとベンチ比較できますね
いまのところ足し算で素数生成するイテレータの実装は以前に作った明らかに非常に遅い>>62と
今回作った動作O(N log log N)でメモリ使用量O(√N / log N)となる>>174の2つしかないのです

>>187
そうなんですよ
エラトステネスのふるいは最初に上限数を指定するためそのままではイテレータと相性がよくないです
またメモリ使用量も大きくなってしまいます
そのため試行錯誤のうえ新たなアルゴリズムが生まれたのが今回の実装です
もっと良い方法を考えついた方は教えていただけるとうれしいです

**デフォルトの名無しさん** · 2021/12/24(金) 23:17:20.90

より良い方法に興味があるんなら、普通に既存実装を研究してみたらいいんじゃない？
例えばRubyの標準添付ライブラリにも Prime.each があるよ
ソースはここ https://github.com/ruby/prime

おれはそこまで素数のアルゴリズム自体には興味ないから考えないけど

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

>>197
CかC++で書いて

**デフォルトの名無しさん** · 2021/12/25(土) 04:20:39.50

C/C++/Rustならどの言語も理解できないほどの特異な書き方や奇妙な省略もなくどれも似たようなもんだ
どれか一つで書かれていれば普通のプログラマーなら読めるだろう
それでもわからない部分があれば質問したら皆が教えてくれるぞ

**デフォルトの名無しさん** · 2021/12/25(土) 06:09:26.55

>>195
ええその通りです。
ですから使いどころを間違っていると思うのです。

**デフォルトの名無しさん** · 2021/12/25(土) 09:05:26.62

>>200
普通のプログラマじゃなくて雑魚なんで
Rustで書かれたコードはわからないしRustの説明が欲しいわけじゃない
C/C++で書かれてれば説明無用だから全部わかるならC/C++で書いてくれない？

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

Ruby の無限generator は、遅延評価する。lazy

普通に、メソッドチェーンを左から処理していくと、
無限に処理できないので、右から処理していく

素数は、6 で割って余りが、1 か5

余りが3なら、3で割り切れる。
余りが2, 4なら、2で割り切れる

**デフォルトの名無しさん** · 2021/12/25(土) 13:31:00.64

素数に2,3が含まれるの忘れてる？

**デフォルトの名無しさん** · 2021/12/25(土) 13:54:13.44

if (25 % 6 == 1) {
//25は素数？
}

**デフォルトの名無しさん** · 2021/12/25(土) 14:02:33.11

>>205
さすがに必要条件と十分条件がわからないのはどうかと思う

**デフォルトの名無しさん** · 2021/12/25(土) 14:14:33.50

>>206
わからない
説明して

**デフォルトの名無しさん** · 2021/12/25(土) 14:21:15.89

>>194
その考え方がまさに木を見て森を見ず

**デフォルトの名無しさん** · 2021/12/25(土) 14:40:34.51

>>207
6で割って余りが1か5になるのは素数であることの必要条件や
xが素数⇒x%6=1,5

**デフォルトの名無しさん** · 2021/12/25(土) 15:29:54.15

その事実を利用してまずは数を6で割って余りが1 or 5のとき
改めて素数かどうかを判定する関数に通すってことか？
rem = X % 6
if ((rem == 1 || rem == 5) && is_prime(X)) {
// Xは素数
}
else {
// Xは合成数
}

**デフォルトの名無しさん** · 2021/12/25(土) 16:04:02.04

必要十分を理解してないエンジンは無価値

**デフォルトの名無しさん** · 2021/12/25(土) 16:50:37.75

電気モーターの時代だから。

**デフォルトの名無しさん** · 2021/12/25(土) 17:51:05.49

>>195
発信、受信、仲介、合成、創造？
コンピューターサイエンス分野を見てもRust公式を見てもそんな用語は１つもないけど
それってもしかしてあんたの個人的な思想ですか？それなら知りたくないのでウザいので黙っててもらえますか？
したがって今回のRustオジサンは気持ち悪い基地外だと思います

**デフォルトの名無しさん** · 2021/12/25(土) 17:58:00.70

>>213
気持ちはわかるけど最後の一文が個人的な気持ちになってて同じ穴の狢になってない？

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

>発信、受信、仲介、合成、創造
たしかにこの用語なんなん？どっから出てきたの？
どの界隈のコンセンサスで得てる言葉なの？

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

>コンサンサスで
じゃなくて、コンセンサスを

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

ワイもこの用語はわかんなかった

**デフォルトの名無しさん** · 2021/12/25(土) 19:07:03.87

仲介なんて不動産屋でしか聞いたことないわw

**デフォルトの名無しさん** · 2021/12/25(土) 19:14:05.00

イテレーターを作ったことがない初心者プログラマーには理解が難しいと思うが
命名はともかくイテレーターがそのように分類されることは俺でもわかるぜ

>(1) 発信イテレータ … >>174で示しました素数生成、レンジ(0..n)、配列やVecに対するiter()などチェーンでは先頭に来るもの

これはRustだとimpl Iterator for XXXのみ実装のイテレーター
つまり他者のnext()は利用せずに他者に対してnext()を提供

>(2) 仲介イテレータ … map()、filter()、enumerate()などチェーンでは中間に来るもの

これはRustだとimpl Iterator for XXXおよびimpl XXX for Iteratorと両方実装のイテレーター
つまり他者のnext()を利用しつつ別の他者に対してnext()を提供

>(3) 受信イテレータ … find()、fold()、collect()などチェーンでは最後に来るもの

これはRustだとimpl XXX for Iteratorのみ実装のイテレーター
つまり他者のnext()を利用するが他者に対してnext()を提供せず

以前に議論されていた消費者プログラマー(?)だと区別を一生気付かないままかもしれぬ

**デフォルトの名無しさん** · 2021/12/25(土) 19:17:12.81

本来の用語は何？

**デフォルトの名無しさん** · 2021/12/25(土) 19:46:48.90

>>218
デザインパターンのMediatorとかでは聞いたことあるのでは

>>220
2-4あたりをひっくるめてiterator adaptorというのはよく聞くけど細かい分類は >>195 の造語っぽい

**デフォルトの名無しさん** · 2021/12/25(土) 20:41:43.56

>>219
自演バレバレやぞｗ

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

>>220
知らん
しかしプログラマーとしてはそれらの違いは必須の知識
なんせ真逆だからな
impl Iterator for XXX
impl XXX for Iterator

>>222
わざわざ知らない役をやって同調するバカをおびき寄せてから知ってる役をしてるってか？
しねーよ

**デフォルトの名無しさん** · 2021/12/25(土) 21:22:55.51

足し算で素数を求めるアルゴリズムについて知りたいんだが誰かC/C++で書ける人いないの？

**デフォルトの名無しさん** · 2021/12/25(土) 21:41:11.69

独自に分類名を付けようとする試みは評価するが
チュートリアルに書いてるレベルの内容で
「初心者プログラマーには理解が難しいと思うが」とか言っちゃう初心者プログラマーはどうかと思う

**デフォルトの名無しさん** · 2021/12/25(土) 21:53:14.53

公式用語はsource、adapter、consumer

**デフォルトの名無しさん** · 2021/12/25(土) 22:31:39.88

イテレータはライブラリ作者と利用者の間でループをやり取りするには便利なものです。
しかし、それ以外で使ってもパッとしない。

**デフォルトの名無しさん** · 2021/12/25(土) 23:31:43.20

>>203 >>210
素数列の生成でそんな何度も割り算しまくるような無駄はしないはず
そんなことしていたら足し算平均2.5回のより遅くなってしまう

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

試し割り法で検索しろ

**デフォルトの名無しさん** · 2021/12/26(日) 00:33:01.70

>>228
素数が足し算平均2.5回程度で求まるアルゴリズムを説明してくれないか？

**デフォルトの名無しさん** · 2021/12/26(日) 02:08:18.89

Rustという世界最高の言語があるのに、なぜRubyを使うのが正しいのか。
リーン・スタートアップという本を読めばわかるよ。

**デフォルトの名無しさん** · 2021/12/26(日) 10:42:00.41

Ruby on Railsは、GitHub, Airbnb, Disney, Hulu, SoundCloud, Shopify といった世界的に有名な企業や、
日本国内でも、note、クックパッド、freee、マネーフォワード、Progate、Qiita などで使われている

2021年10月には、GitHubのコピーで、Railsを使い続ける宣言をしている、
GitLab が上場し、時価総額は約1.9兆円！

一方、GitHubはGo へ以降する

Railsを使う理由を端的に言えば、もうかるから

Ruby biz Grand prix 2020 大賞を受賞した、Ruby の女神・池澤あやかも言ってる。
他の言語では開発者を確保しにくいので、Railsに切り替えた

**デフォルトの名無しさん** · 2021/12/26(日) 10:47:24.01

Mediator は、空港の管制塔

**デフォルトの名無しさん** · 2021/12/26(日) 15:09:49.43

>>214
仲介手数料、信用創造、お前が同じ穴の狢、アホのRustオジサンです

**デフォルトの名無しさん** · 2021/12/26(日) 16:15:26.85

>>173
1億までの素数を全て生成するのに足し算2.5億回で済む理由がわかった
素数でなければ1万以下の素数が約数として必ずあるから順に最大素数9973まで調べるだけでよい
1億/2 + 1億/3 + 1億/5 + 1億/7 + 1億/11 + … + 1億/9973 = 約2.5億の足し算で原理的には済むはず

**デフォルトの名無しさん** · 2021/12/26(日) 21:21:30.44

>>224
ある数がある数で割れるかどうかのテストに足し算を使っているだけ。
例えば12を3で割れるかどうか調べる場合、0 3 6 9 12と足し算していって、12が見つかったので割れる。

**デフォルトの名無しさん** · 2021/12/26(日) 21:25:21.15

エラトステネスの篩、のことなのでは？
でも1億分のバッファとか、勿体ない気がしますね…

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

そこで区間篩ですよ

**デフォルトの名無しさん** · 2021/12/26(日) 22:31:44.15

発見済みの素数を使ってループして数Xが素数かどうかを調べてるだけだろ？
足し算平均2.5回って意味不明なんだが？

**デフォルトの名無しさん** · 2021/12/26(日) 22:57:15.49

>>239
1億までの素数列挙の場合が足し算平均2.5回なだけじゃね？
>>173を見る限り
100万までの素数列挙なら足し算平均2.2回
1万までの素数列挙なら足し算平均1.9回
足し算の回数はO(N log log N)とあるから多少増えていくのだろう

**デフォルトの名無しさん** · 2021/12/26(日) 23:11:50.20

そう書いていたら謎が解けた

>>235
＞ 1億/2 + 1億/3 + 1億/5 + 1億/7 + 1億/11 + … + 1億/9973 = 約2.5億の足し算で原理的には済むはず

これは1億✕(1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … )だから括弧内は素数の逆数の和でlog log N
1億がNだから足し算の回数はO(N log log N)なのか

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

>>239
素数かどうかを調べるのは>>236が書いているように足し算だけで可能です
必要となる足し算の数は>>241が書いているようにO(N log log N)です
足し算平均2.5回は1億まで素数を列挙した時の話であって>>240が書いているようにNに対してわずかですが増えていきます

**デフォルトの名無しさん** · 2021/12/27(月) 00:18:24.10

>>242
C言語でいいから加算で素数を求めるアルゴリズム書いてくれない？

**デフォルトの名無しさん** · 2021/12/27(月) 08:37:12.33

このスレで出てきているテレーターがよくわからんのだけど、wikipediaの定義と違うんかいな？
ttps://ja.m.wikipedia.org/wiki/%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF

**デフォルトの名無しさん** · 2021/12/27(月) 09:31:03.72

>>244
その日本語wikiは怪しいので英語のwikiを見るといい

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

100回繰り返すのと1億回繰り返すのとどっちがマヌケに見えるか、億という言葉を使えば賢く見えるのか？
億回繰り返さないと理解できないのか、汚コードRust相談室と化したC vs C++ vs Rustスレに未来はあるのか

**デフォルトの名無しさん** · 2021/12/27(月) 14:18:09.83

隔離スレに未来などあるわけあるか

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

>>244
実際のコード例で体験していくと理解が早い

例えばこの計算をしたいとする
>>235
> 素数でなければ1万以下の素数が約数として必ずあるから順に最大素数9973まで調べるだけでよい
> 1億/2 + 1億/3 + 1億/5 + 1億/7 + 1億/11 + … + 1億/9973 = 約2.5億の足し算で原理的には済むはず

コードは>>176の素数生成イテレータも使って以下のイテレータ4つの連鎖で求まる

let result: i32 = 素数生成::<i32>()
　.take_while(|&p| p < 10000)
　.map(|p| 100000000 / p)
　.sum();

途中のtake_while()は条件を満たす間だけ取るイテレータでこの場合は「1万未満」が条件
map()は変換するイテレータで「素数pを1億/p」へ変換している
最後にsum()で流れてきた1億/pを「全て足して」目的を達成

このように個々の単機能イテレータを複数組み合わせて連鎖させることでプログラミングできる

**デフォルトの名無しさん** · 2021/12/27(月) 21:02:50.96

まーたイテレータの定義をよくわかってないやつがヘンテコな説明しちゃう

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

ヘンテコなとこに気がつけなかったんだけど、どのへん？

**デフォルトの名無しさん** · 2021/12/27(月) 23:21:22.61

今どきの言語のイテレータは>>248で合っている
しかしC++のイテレータは低レベルでポインタを抽象化したものと考えたほうがいいので注意
C++にもようやくmap()に相当するものが入ったが他言語とは異なりtransform()という名前など使いにくい
今どきのプログラミングしたいなら素直にRustを使ったほうが便利

**デフォルトの名無しさん** · 2021/12/27(月) 23:38:31.34

>>250
イテレータとは何かを分かってない
用語の使い方見れば一目瞭然でしょ

分かってない人が書いた説明を読むよりもある程度査読されてる英語のwikiや各言語のリファレンス見たほうがいい

**デフォルトの名無しさん** · 2021/12/27(月) 23:39:05.80

この文中に>>入れる自作自演の同一人物の基地外Rustのくせはほんと気持ち悪い。また引用で > 使う

**デフォルトの名無しさん** · 2021/12/27(月) 23:41:50.94

伝統的には値を生成するものはジェネレータと呼ぶわな

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

>>253
はちみつ病だからスルーしてさしあげろ

**デフォルトの名無しさん** · 2021/12/27(月) 23:49:02.66

>>254
それは観点が違うな
値を生成するものであってもイテレータとして機能するものと機能しないものがある
つまり重要な点はイテレータとして機能するか否かのみ
Rustの1..nやこのスレの素数生成はイテレータとして機能しているから明白にイテレータ

**デフォルトの名無しさん** · 2021/12/28(火) 01:27:16.67

ジェネレータはみんなイテレータだから

**デフォルトの名無しさん** · 2021/12/28(火) 10:31:13.05

やっぱり頭がおかしいよ、1..nはRange { start: 1, end: n }と同じ。Rust公式でもイテレータじゃなく
単にRangeと言っているだけなのに、それが機能するかという観点ならfor inが無ければ機能しないから
イテレータじゃない。collect()がイテレータをコレクションに変換するように、for inで(暗黙)変換されるだけ。
こいつ、あちこちで暴れてる

**デフォルトの名無しさん** · 2021/12/28(火) 11:06:40.72

RangeはIterator実装してるからrustの定義ではイテレータではあるのでは

**デフォルトの名無しさん** · 2021/12/28(火) 11:57:32.05

汚コード厨まだ居るのか

**デフォルトの名無しさん** · 2021/12/28(火) 12:05:42.28

>>258
君もイテレータがわかってないお仲間さんなので仲良く勉強しとけ

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

プログラミング初心者でもないのにイテレータを理解してないやつがRustスレに多いのはなぜ？

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

ここ本スレではなく隔離スレ
スレ民の目的はただの冷やかし

**デフォルトの名無しさん** · 2021/12/28(火) 14:55:22.51

"仲介イテレータ"
約 2 件（0.26 秒）

すげー、全世界で、このスレにしかその言葉は存在しない

**デフォルトの名無しさん** · 2021/12/28(火) 15:25:43.05

厨怪イッテレータ

**デフォルトの名無しさん** · 2021/12/28(火) 15:44:45.74

>>262
一番レスの多い自演厨が理解してないから、そう見えるだけ

**デフォルトの名無しさん** · 2021/12/28(火) 16:37:20.65

イテレータには狭義のイテレータと広義のイテレータがある
広義のイテレータは狭義のイテレータとイテレータメソッドを合わせたものである

(A) イテレータ(狭義)
Rustで言えばtrait Iteratorを実装するもの
コード上で「impl Iterator for 各イテレータが返す型」となって現れる
各イテレータが返す型は通常structでありimpl Iterator<Item=T>を満たす
メソッドとしてnext()を持ちこれがOption<T>を返す

(B) イテレータメソッド
Rustで言えば上述イテレータ(狭義)のメソッドとなるもの
コード上では「impl 宣言用トレイト for Iterator」の中で現れる
各イテレータメソッドが返す型は任意でありfor_each()のように無しもある
対象となったイテレータ(狭義)のnext()を利用する側となる

>>195
| (1) 発信イテレータ … >>174で示しました素数生成、レンジ(0..n)、配列やVecに対するiter()などチェーンでは先頭に来るもの
| (2) 仲介イテレータ … map()、filter()、enumerate()などチェーンでは中間に来るもの
| (3) 受信イテレータ … find()、fold()、collect()などチェーンでは最後に来るもの

その分類で言えば
(1) ＝ (A) かつ not (B) ＝イテレータ(狭義)だがイテレータメソッドではない
(2) ＝ (A) かつ (B) ＝イテレータ(狭義)でありイテレータメソッドでもある
(3) ＝ not (A) かつ (B) ＝イテレータメソッドだがイテレータ(狭義)ではない