どちのほうがすきですか？

私の書いた

def fizzBuzz(self, n: int) -> List[str]:
res = []
for i in range(1, n + 1):
s = ''
if i % 3 == 0:
s += 'Fizz'
if i % 5 == 0:
s += 'Buzz'
if not s:
s += str(i)
res.append(s)
return res


いちばんはやいひとの

def fizzBuzz(self, n: int) -> List[str]:
fb_list = []
for i in range(1, n+1):
if (i % 15 == 0):
fb_list.append("FizzBuzz")
elif (i % 3 == 0):
fb_list.append("Fizz")
elif (i % 5 == 0):
fb_list.append("Buzz")
else:
fb_list.append(str(i))
return fb_list



たぶんstrの操作って計算コスト大きいて思うし if, elif, else の塊にまとめたほうが各iで入るのは一この条件だけなのでそっちのほうがはやいとおもいましたけど、どっちがよきですか？？
int nにたいしてindex n に FizzBuzzを格納している配列を返す問題です。

No.8 回答者： cametan_42 回答日時： 2024/03/31 00:46

あ、面白い事思いついたわ。

この質問、貴女のだよね?

パソコン用語ひとつもわかりません:
https://oshiete.goo.ne.jp/qa/13684756.html

丁度いい。余再帰を見せてあげるよ。

まずPythonで余再帰イテレータ、unfoldrを書く。定義はこんなカンジだ。

余再帰イテレータ/unfoldr:
https://www.ideone.com/vzLfU9

これは関数型言語、Haskellでのunfoldrの定義を借りてきている。

unfoldr(Haskell):
https://hackage.haskell.org/package/base-4.19.1. …

さて、「余再帰」ってのは厳しい言い回しなんだけど、実はやってる事は単純で、ザックリ言うと、unfoldrってのはrangeの高階イテレータ版だ。
Python.docではrangeの使用例が次のように紹介されている。

range:
https://docs.python.org/ja/3/library/stdtypes.ht …

unfoldrで同様な計算は次のようにして行う。

>>> list(unfoldr(lambda x: None if x >= 10 else (x, x + 1), 0))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(unfoldr(lambda x: None if x >= 11 else (x, x + 1), 1))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> list(unfoldr(lambda x: None if x >= 30 else (x, x + 5), 0))
[0, 5, 10, 15, 20, 25]
>>> list(unfoldr(lambda x: None if x >= 10 else (x, x + 3), 0))
[0, 3, 6, 9]
>>> list(unfoldr(lambda x: None if x <= -10 else (x, x - 1), 0))
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]
>>> list(unfoldr(lambda x: None if x == 0 else (x, x), 0))
[]
>>> list(unfoldr(lambda x: None if x >= 0 else (x, x + 1), 1))
[]

unfoldrは高階イテレータなんで、コールバック関数(上の例だとラムダ式)と初期値を引数を取る。

unfoldr(コールバック関数, 初期値)

コールバック関数は、停止条件を満たした時にNoneを返すように設計する。
そして停止条件を満たしてない時、タプルを返す。タプルの内情は左側が生成する値、右側が初期値をどう増やすか、を意味してる。
んで、上の例はrangeでの例に合わせて書いてて、「同じ結果を返す」のは分かるだろうけど、一方、コールバック関数を書くのがメンド臭いのは事実だ。「同じ結果ならrange使えばイイじゃない?」とか言われればグゥの音も出ない(笑)。いくらrangeの上位互換、って言われてもそりゃそうだ、って話になる。
一方、unfoldrがrangeに比べて強力なのは、リスト内包表記の基本機能とrangeの合わせ技をその身だけでやってのける事にある。

>>> [x**2 for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> list(unfoldr(lambda x: None if x >= 10 else (x**2, x + 1), 0))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

多分これだけ、でもまだ不満かもしんない(笑)。「リスト内包表記とrangeの合わせ技ならそのまま使ってもいいんじゃない?」と。
その通りなんだけど、ここから黒魔術の話だ(笑)。
unfoldrはイテレータとして設計した。そして原則、コールバック関数には停止条件とその時の返り値Noneを仕込む。
しかし、停止条件とNoneが無かったらどうか?実はそれでも問題がないんだよ。
停止条件とNoneが無いと、一見無限ループするように思える。思えるが、イテレータとして設計した以上、「それは実行されない」。結果無限長のシーケンスが仮想的に入手出来る、って事になる。
これを(部分的に)遅延評価、と呼ぶ。

>>> unfoldr(lambda x: (x, x + 1), 0)
<__main__.unfoldr object at 0x7f11affd3730>

上は何だか変な返り値が返る。今まではlistを使ってリスト化してきたけど、ここでlistを被せないように。被せた途端、実体化して無限ループに陥る。
言い換えると上の「何だか分からない返り値」は0から1毎に増えた無限長の整数列の情報が入ってる、って事だ。「必要になるまで評価されない」んで、これを「遅延評価」って呼ぶわけだな。
実際は厳密には違うんだけど、一応概念的にはPythonのイテレータは遅延評価の、少なくとも部分的な実装、と捉える事が出来る。言っちゃえば同じイテレータのrangeも実は遅延評価のイテレータなんだ。
しかし、「情報が詰まってる」とか言われても、任意にその情報を取り出せないと画餅になるだろう。そのために、Pythonのitertoolsライブラリにはtakewhileと言う関数がある。

takewhile:
https://docs.python.org/ja/3/library/itertools.h …

>>> from itertools import takewhile
>>> list(takewhile(lambda x: x < 5, unfoldr(lambda x: (x, x + 1), 0)))
[0, 1, 2, 3, 4]

上の例だと、「無限長の整数列」から5以下の部分的なリストを取り出す例となっている。

さて、unfoldrは無限長の列の情報を詰め込める、って話をした。
って事は、だ。

>>> unfoldr(lambda x: ('FizzBuzz' if x % 15 == 0 else 'Fizz' if x % 3 == 0 else 'Buzz' if x % 5 == 0 else str(x), x + 1), 1)
<__main__.unfoldr object at 0x7f11affd3dc0>

これが無限長のFizzBuzzだ。
ちと、これから部分的にリストを取り出すのがメンド臭いんだけど、例えばenumerate辺りを使えばこうやって取り出す事が出来る。

enumerate:
https://docs.python.org/ja/3/library/functions.h …

>>> [v for k, v in takewhile(lambda x: x[0] < 15, enumerate(unfoldr(lambda x: ('FizzBuzz' if x % 15 == 0 else 'Fizz' if x % 3 == 0 else 'Buzz' if x % 5 == 0 else str(x), x + 1), 1)))]
['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8', 'Fizz', 'Buzz', '11', 'Fizz', '13', '14', 'FizzBuzz']

つまり、余再帰を利用した無限長のFizzBuzz列からn以下のリストを取り出す関数は次のように書ける。

遅延評価版FizzBuzz:
https://www.ideone.com/iDrxGH

とまぁ、これが「余再帰」だ。

この回答へのお礼

ごめんなさい T.T
読んで見てるけどぜんぜんむずかしいです..
なんとなくイテレータとか余さいきとかわかったけどぜんぜん私にはまだはやいとおもいました。。でもすごい全然知らないことがたくさんあるってわかって勉強になりました、ありがとうございます。
かめたんさんはなんでこんなに難しいことをいっぱういスラスラ知ってるんですか？めっちゃ何物なのっておもいます。科学者さんとかですか？？

お礼日時：2024/04/11 12:55

No.7 回答者： よっしーラボ 回答日時： 2024/03/30 19:37

この二つのコードだとelifの方です。

10,000回のループでみると、

質問者さんのコード
　if文評価：30,000回
　str処理：10,666回
　append処理：10,000回

後者のコード
　if文評価：26,001回
　str処理：0
　append処理：10,000回

となり、後者の方の処理が少ないということになります。

もっと少しいうと、同様のコードでも

for i in range(1, n+1):
　if (i % 3 == 0):
　　if (i % 15 == 0):
　　　fb_list.append("FizzBuzz")
　　else:
　　　fb_list.append("Fizz")
　elif (i % 5 == 0):
　　fb_list.append("Buzz")
　else:
　　fb_list.append(str(i))

にすれば、if文の実行回数は、%3のif文は、10,000回、%15のif文は、3,333回、%5のif文は、6,667回となり、20,000回に減ります。％3と%5のif文を替えたとしても、同様に20,000回になります。

ただし、これは、CPUのキャッシュ、CPUの投機的実行、メモリヒットによるパフォーマンスが異なってくるので、数回測定し平均化するのがいいですが、自分の環境で測定すると、1万回のループで、質問者さんのコードは、1.763ms, 速い人のコードは、1.647ms, 上のコードだと、1.486msでした

Pythonのリスト配列はpop(), push()メソッドから、パフォーマンス向上のため双方向のindexテーブルを持ったリスト構造だと思われるので、リスト配列の要素数が多い時、順次appendしていくと、ガベージコレクションが発生する可能性が非常に高いので、それを避けるため可能な限り初期化時に配列分のリストを確保することでパフォーマンスが改善されます。

ちなみに、もっと良い回答はあるとは思いますが、自分の環境で一番パフォーマンスが良かったのは、下記のコードです。自分の環境用なので質問者さんのコードとは若干コードが異なりますが、上記測定時の結果では818μsでした。100回のループ処理で他のコードでは、ほとんど差はありませんが、下記のコードだとやはり半分ほどの処理時間となります。

def fizzBuzz(n: int) -> list[str]:
　fb_list = [range(1,n+1)]
　for i in range(1, n+1):
　　if (i % 3 == 0):
　　　if (i % 15 == 0):
　　　　fb_list.append("FizzBuzz")
　　　else:
　　　　fb_list.append("Fizz")
　　elif (i % 5 == 0):
　　　fb_list.append("Buzz")
　return fb_list

これを分析すると、1万回のループでは
　if文評価：20,000回
　str処理：0
　append処理：4,667回

となり、append処理が減少しているのが明確です。

ループ処理は、反復処理を可能な限り減らすためのロジックを考えることと、初期化によってどの程度処理コストを下げられるか、そのバランス次第になるのが目に見えてわかる、良い問題だと思います。

この回答へのお礼

すごい詳しく分析してくれてありがとうございます :))
回数とかもっとこまかい分岐とかかんがえてくれてすごい勉強になりました

お礼日時：2024/04/11 11:55

No.6 回答者： ありものがたり 回答日時： 2024/03/29 23:28

これ、Cの質問？

私のCの知識はK&R2で止まってるので、最近のは解らないけど、
質問のコードは、さすがにCには見えない。

#include <string.h>

char** FizzBuzz(int strn, char **strv) {
　　int i, j;
　　char *s, **res;
　　static char fizz[] = "Fizz";
　　static char buzz[] = "Buzz";

　　if(strn <= 0) rerturn NULL;
　　res = malloc(sizeof(char*) * strn);
　　if(res == NULL) return NULL;

　　for(i = 0; i < strn; i++) {
　　　　s = malloc(strlen(strv[i])+1);
　　　　if(s == NULL) {
　　　　　　for(j = 0; j < i; j++) free(res[j]);
　　　　　　free(res);
　　　　　　return NULL;
　　　　}
　　　　strcpy(s,strv[i]);
　　　　res[i] = s;
　　}

　　for(i = 0; i < strn; i += 3) {
　　　　s = malloc(strlen(res[i])+1+sizeof(fizz));
　　　　if(s == NULL) {
　　　　　　for(j = 0; j < i; j++) free(res[j]);
　　　　　　free(res);
　　　　　　return NULL;
　　　　}
　　　　strcpy(s,res[i])
　　　　strcat(s,fizz);
　　　　free(res[i]);
　　　　res[i] = s;
　　}

　　for(i = 0; i < strn; i += 5) {
　　　　s = malloc(strlen(res[i])+1+sizeof(buzz));
　　　　if(s == NULL) {
　　　　　　for(j = 0; j < i; j++) free(res[j]);
　　　　　　free(res);
　　　　　　return NULL;
　　　　}
　　　　strcpy(s,res[i])
　　　　strcat(s,buzz);
　　　　free(res[i]);
　　　　res[i] = s;
　　}

　　return res;
}

この回答へのお礼

これはCですか？

お礼日時：2024/04/11 11:52

No.5 回答者： cametan_42 回答日時： 2024/03/29 23:16

> ぜんぜん言語の立ち位置みたいなのとかわかってないんですけどパイソンらしいものていう考えのとかもあるとおもいました

そう、あるんだ。
で、あれだろ?LeetCodeだろ?
やっぱダメだな、LeetCode(笑)。少なくとも貴女にはまだ早い。
プログラミング初心者がまず心がけなきゃなんないのは、「スタイルの確立」なんだよ。
貴女の書いたコードを見ると、まだスタイルが確立されてない。
スタイルが確立されてない状況で、「コードの実行速度」に心を奪われるのは、あまり良い教育環境ではないんだ。
ハッキリ言うけど、「速度が速いコードを書こう」とすると、スタイルがメチャクチャになる危険がいつも存在するんだ。
それだけじゃない。一般に、「速いコード」には危険が存在するか、あるいはバグを簡単に作り込む可能性がある。

一般的には、「実行速度が速い」コードはinsecureになる可能性が高い。
もちろん、Python自体はsecureな言語なんだけど、secureであるが故に遅い、って言い方も出来るんだ。
残念ながら、secureさと「実行速度の速さ」はある程度トレードオフの関係がある。
言い換えると、例えば実行速度が速い実行形式を作り出すC言語なんかでも、Python並のsecureなコードを書こうとしたら実行速度がPython並に落ちる事は良くあるんだわ。

もう一つの考え方はこうだ。もちろん、アルゴリズム的な観点で、「非効率なコード」を書くのは薦められない。やっぱコード的に無駄なモノを書くべきじゃないよね。
ただし、コード的に無駄なモノを排除したにせよ、速度が稼げなかったとする。
そういう場合は、基本的に「コンパイラ」とか「仮想マシン」の責任なんだよ(笑)。
実行させる側の責任じゃなくって、実行してる側のせいにする(笑)。
これがモダンな言語を使う側の発想だ(笑)。「遅いのは俺のせいじゃない」と(笑)。

こういうね、書いたプログラムの速度を上げるのを「最適化」(Optimization)って言うんだけど。
まず、「最適化し過ぎ」ってのはあんま良い結果を生まない、ってのが歴史的に分かってきてるんだわ。それはAと言うプログラムがプラットフォームαでは非常に高速で走るけど、プラットフォームβに移植しようとしても上手く行かない、とかあるいは移植しても高速で走らない、ってのが良く見かける現象なのね。
今はどうだか知らんけど、例えばGoogle Chrome。僕はWindows 7だった頃に使ってたんだけど、とにかく(度重なる改変で)重くて「マトモに使えるブラウザじゃない」って感想だった。とにかく重い。
ところが、Linuxで使うと軽いんだわ。これは元々Google ChromeってブラウザがLinux上で開発されてて、Linuxのメモリマネジメントに最適化した結果でしょう。ところがWindowsに移植した時点でその「最適化」が上手く働かないわけ。メモリ管理システムが違うからさ。
あと、古い話だとFinal Fantasy IIIってゲーム。ファミコンで高速で実行可能なように最適化したプログラムだった為、長い間ファミコン以降のゲーム機に移植不可能だったんだ。
このように「ある時点で」「あるCPUに於いて」「あるOSに対して」最適化すると「ロクな結果にならない」ってのが歴史的に分かってきてる。かつてあったホビーパソコン上で軽快に動いたプログラムが他のプラットフォームで上手く動かなくって廃れた、って例が山ほどあるのね。
だから最適化は必要なんだけど「やり過ぎは良くない」ってのを知らないとならない。そして今だと「最適化より可搬性(Portability)」の方が重要だ、って考えられてるんだ。
だからこそ、ソースコードを弄くりまくって最適化にアタマを悩ますより、ソースコードの持つ「可搬性」を重要視すべきだ、って事なの。そしてそのためには「スタイル構築」が何より大事なんだ。

んで、Pythonのリストに於けるappendなんだけど。これって原則、最適化の為の道具なんだよ。ジャーゴン的にコンシング、って言うんだけど、リストに対してフツーに演算すると、結果ガベージコレクタってのが走り回るのね。Pythonではガベージコレクタがあるお陰でラクにプログラムが書けるんだけど、逆にガベージコレクタのせいで実行速度が落ちるわけ。
appendってのはリスト要素を「破壊的変更」するお陰でガベージコレクタが出てこれないんだ。
ただし、最初からそれを狙ってプログラミングするのはダメだ。それはドナルド・クヌース(Donald Knuth)と言う計算機科学者が言ってた「早すぎる最適化は諸悪の根源」ってヤツだ。
とにかく最初は破壊的変更するようなプログラムは書かないようにする。プログラム全体が遅い、とかなった場合、本当にリストのコンシングとガベージコレクタが性能の低下を招いてるかどうかは分からんから、だ。
で、モダンな言語だと大体プロファイラってブツが同梱されている。Pythonでも付属している。

Python プロファイラ:
https://docs.python.org/ja/3/library/profile.html

遅いプログラムはこのプロファイラを用いて検査する。プロファイラは貴女が書いたプログラムの「どの部分が速度低下を招いているのか」教えてくれる。大体、速度低下は「貴女が予想しなかった場所」が原因だ(笑)。いや、貴女だけじゃない、大体プログラムを書いてる奴らの「想像の斜め上」が原因だったりするんだよ(笑)。
そういう「速度低下を招いてる局所」をボトルネック(bottle neck)と呼んだりする。いずれにせよ、一旦書いて完成したプログラム(第一ヴァージョン)はプロファイラを用いて精査しよう。そうすれば一体「どこを速く書き直せばいいのか(最適化すればいいのか)」が分かる。
それがモダンなプログラミング方針なんだ。

この回答へのお礼

そなんですね :o)
たしかに、速さばかりきにっさせさられる環境は良くないと思いました。
なんか早いと緑色で何％より早いですってでて
おそいとだめみたいな漢字なんでみんなはやくしようとするけど他の人も言ってたけどtime complexity の見積もりができればそれでいいと思いました。
かめたんさんのいうように実際のコードを各人たちはいちぶのゲームとか？なんかすごいspecefic な場面では速さがたいせつかもしれないけどふじ不不自然に削ってまで不自然なコードにするのはかめたんさんのいうようによくないし危険だと思いました

お礼日時：2024/04/11 11:51

No.4 回答者： だいぬ 回答日時： 2024/03/29 20:06

すみません。

先の回答に誤りがありました。
機械的に見て無駄なのはの部分ですが、3でも5でも割れる時に両方に入るのが無駄というのが正しいです。
毎回最後のifに入ることは無いですね。

この回答へのお礼

お礼日時：2024/04/11 11:47

No.3 回答者： だいぬ 回答日時： 2024/03/29 20:02

文字列の操作って別に気にするほど計算コストが高いと思わなくていいと思っています。

後者の方がより早いならifでの比較とジャンプの数のせいだと思います。
機械的に見て無駄なのは前者の方では1度ifに入ると必ず最後のifにも入るので無駄なジャンプを避けられません。
Pythonの仕様を詳しく知らないですが、文字列の結合も配列への追加もおそらくほとんど同じことを内部的に行うはずです。

ただ、私がより好きなのは前者です。
FizzBuzzはよりコードの記述量が少ないコードの方が優れているという考え方も有ります。
私が最初にたどり着いたのは空文字と文字結合をつかうことでした。

速さを考えるならPythonを使うべきじゃないだろと初見で思ったので、下の方には同意しておきます。

ちなみに、リスト内包表記が大嫌いで、個人的にPythonが嫌いな理由の一つです。

Pythonが全てオブジェクトだって考えに基づくなら、引数を1つとり、その値を判定してFizzかBuzzかFizzBuzzかその値そのものを返すようなメソッドを定義するのがいちばん美しい解なんじゃないですか。

ちなみにこの質問はFizzBuzzのルールを知らないと回答出来ないので、不親切な質問に思えます

質問文のindexが何かよく分からないですが、
1をFizz
2をBuzz
3をFizzBuzzにするとか、ビット演算でフラグを立てるとかでマッピングすれば直接文字列を持ってなくても文字列を参照したい時に、文字に置き換えればいいだけなんでなんとなく早いんじゃないですか。
どれで割っても余りが0じゃない時どうするかは考えないといけないけど、別に初期値の0ならインデックスを返すとかすればいいかな。

この回答へのお礼

ありがとうございます(´；ω；｀)
すごいわかりやすかったです。
いろいろかんがえてなかたからすごいお勉強になりました

お礼日時：2024/03/29 23:00

No.2 回答者： artoo 回答日時： 2024/03/29 19:48

好みの話でいいんですよね？

1つめは、if not s: が嫌ですね。条件は i に対してのチェックにしたい。
2つめは、強いて言うならifの条件を括弧で囲んでいるのが気持ち悪すぎです。
いずれにせよ、appendじゃなくて、内包表記かmapを使うべきでしょうね。

この2択でどっちか選べと言われると究極の選択みたいでいやです。

この回答へのお礼

お勉強になりました。ありがとうございます

お礼日時：2024/03/29 22:29

No.1 回答者： cametan_42 回答日時： 2024/03/28 23:24

どっちの方が好き?

好みの問題で言うなら「どっちもダメだ」(笑)。
Pythonでappend操作なんざやるもんじゃないよ。
そもそも、ハッキリ言っちゃうと、「速度が重要なら」Pythonを使うのが間違ってる(笑)。言語選択の時点で「間違ってる」んだわ(笑)。
自動車のレースに自転車で参加するようなモンだな。
Pythonって実はかなり「遅い」言語なんだよ。そもそもの設計、がね。

僕ならこう書く。

実装例:
https://www.ideone.com/4gap5L

チンタラforループ回して空リストに文字列appendして・・・なんかしないね。
それはC言語とかJavaのやり方、だ。
Pythonでの「望ましい」書法はリスト内包表記を使う事だ。
速度を犠牲にしても「短く書ける」のがPythonを使う旨味で、そうじゃなかったらPythonを使う必然性って無いと思うよ。

この回答へのお礼

にゃるほど。そのとおりですね。ぜんぜん言語の立ち位置みたいなのとかわかってないんですけどパイソンらしいものていう考えのとかもあるとおもいました

お礼日時：2024/03/29 22:29