Pythonのお勉強 Part75 (968ﾚｽ)
上下前次1-新
417: (ﾜｯﾁｮｲ d701-1LxV) 07/04(金)22:35 ID:qssSI6rZ0(1) AAS
初めまして
418: (ﾜｯﾁｮｲ b754-1VI2) 07/07(月)23:09 ID:Fgzb82LA0(1/2) AAS
deque()にappendするとO(1)だけど、listだとO(n)になる
とネットで読んだのでそれはいいことを聞いたと比較してもなんも変わらん
listもO(1)に改良された?
419: (ﾜｯﾁｮｲ d707-LERx) 07/07(月)23:23 ID:FJRRFujO0(1/2) AAS
メモリ確保で再配置が発生するのは環境にもよるし稀だからそこをゼロとみなすと
どっちもO(1)じゃね？
420: (ﾜｯﾁｮｲ b754-1VI2) 07/07(月)23:27 ID:Fgzb82LA0(2/2) AAS
listがリスト構造になってて、先頭から末尾まで辿らないといけないならO(n)
でもlistなんてappendでしか作らないんだし、そんな非効率なことせんやろと思えばO(1)
421: (ﾜｯﾁｮｲ f701-J1F0) 07/07(月)23:39 ID:OMOKcj7b0(1) AAS
prependとかの間違いじゃね？
appendleft, popleftように先頭への追加・先頭からの取得がdequesはO(1)だけどlistはO(n)
末尾への追加・末尾からの取得(append/pop)はlistもO(1)
422: (ﾜｯﾁｮｲ d707-LERx) 07/07(月)23:50 ID:FJRRFujO0(2/2) AAS
418はlistの実態が配列(vector)とわかってないだけ
コンテナで末尾要素保持してるリストだと思ってる
423(1): (ﾜｯﾁｮｲ b754-1VI2) 07/08(火)06:15 ID:Qj3wdBkS0(1) AAS
ネットに書いてあった、というのはこれ
外部ﾘﾝｸ:note.nkmk.me
確かによく読むと、listでappendがO(n)とは書いてない
> リストでは(中略)O(n)のコストを必要とするが、
> dequeでは先頭・末尾の要素を追加・削除するappend(), appendleft(), pop(), popleft()がすべてO(1)で実行できる。
dequeだとappend()だとO(1)だと自慢するからには、listはそうじゃないのかと騙された
先頭への挿入だと桁違いにdeque有利
でもそんなデータの持ち方しないので、今ひとつ使い所が無い
424: (ﾜｯﾁｮｲ ff10-6EkQ) 07/08(火)08:17 ID:p5eoB2uL0(1/2) AAS
自分もlistで足りるような小さなプログラムしか書かないからdeqを実際に使ったことはないんだけれど、キューみたいなFILOのデータ構造を作るにはcollections.deqは便利なんだと思うよ。というか、そのnoteにもちゃんと書いてあるじゃない。（中略）のところに。
425: (ﾜｯﾁｮｲ ff10-6EkQ) 07/08(火)08:21 ID:p5eoB2uL0(2/2) AAS
失礼、deqじゃなくてdequeか。
426: (ﾜｯﾁｮｲ 57b8-6EkQ) 07/08(火)09:14 ID:o+j4YzbQ0(1) AAS
FILOじゃなくてLILOだね。ごめん、今日はちょっと寝ぼけ過ぎだわ。
427: (ﾜｯﾁｮｲ 9fca-5AH1) 07/08(火)09:46 ID:cPzLVtg40(1) AAS
なぁに、どんまい
いつものことだ
428: (ﾜｯﾁｮｲ f701-9mUg) 07/08(火)10:52 ID:KWb1fHfq0(1) AAS
>>423
その直後の公式リファレンスの引用箇所に「pop(0) や insert(0, v)はO(n)」って書いてる
>list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
429: (ｽﾌｯ Sdbf-zcFv) 07/08(火)11:06 ID:Lf/Jcjxkd(1/2) AAS
pythonでlistは命名を間違ったんだろ
430: (ｽﾌｯ Sdbf-zcFv) 07/08(火)11:07 ID:Lf/Jcjxkd(2/2) AAS
426
FIFOとLILOの違いを解説してくれ
FILOじゃなく
431: (ﾜｯﾁｮｲ f7b1-5AH1) 07/08(火)12:17 ID:oRmRKSqt0(1) AAS
ロリに見えたひと先生怒らないから手を揚げなさい
432: (ﾜｯﾁｮｲ f701-Gm4U) 07/08(火)13:13 ID:+FhuPDAr0(1) AAS
FIFOかLIFOやろ
FILOもLILOもstackやqueueの文脈では使われない
433: (ﾜｯﾁｮｲ 9f6d-6EkQ) 07/08(火)14:30 ID:Ibve/xnR0(1) AAS
FIFO = LILO …… キューとか
FILO = LIFO …… スタックとか
ただ、432のようにFOという書き方を好む人が多いみたいね。
434: (ﾜｯﾁｮｲ 9ffd-h4ne) 07/08(火)15:07 ID:WMpsyBaN0(1) AAS
そりゃそうだろ
435(1): (ﾜｯﾁｮｲ b754-1VI2) 07/08(火)19:09 ID:/6/LIdXs0(1/2) AAS
なるほど、FIFOバッファ作るのに向いてるのか
そういう必要に迫られたら、バッファサイズ固定でリングバッファの発想しか無いな
dequeも似たようなことやってるんだろうけど、バッファサイズが動的に変えられる
中のメモリどうなっとんねん
436: (ﾜｯﾁｮｲ 9f20-p46g) 07/08(火)20:01 ID:yBGpSZNW0(1/2) AAS
>>435
そこはlist(いわゆる動的配列)と同じで、配列が満杯になったら大きな配列を確保し直して全コピするだけだよ
もちろんその際はO(N)、魔法はない
437(1): (ﾜｯﾁｮｲ b754-1VI2) 07/08(火)20:08 ID:/6/LIdXs0(2/2) AAS
音声データ出力とかさせたらブチブチ切れそうだな
438: 436 (ﾜｯﾁｮｲ 9f20-p46g) 07/08(火)20:52 ID:yBGpSZNW0(2/2) AAS
すまん訂正する
dequeueは配列ではなく双方向リンクリストで実装されているため、バッファの再確保は発生しないようだ
一般にリンクリストは動的配列に比べてゴミのように遅いが、そもそもPythonインタプリタ自体がゲロ遅いため>>437の懸念の通り安定性の方を取ったのだろう
439: (ﾜｯﾁｮｲ ff9c-sH2C) 07/09(水)09:53 ID:9mJpZcLF0(1) AAS
最初っからデータが連続してなくて個別に管理してるだけでしょ
そうすりゃデータ量が毎回変わっても、同じアルゴリズムで使える
その代わり、常に個別のアドレスをすべて管理して比較して並べ替えするから遅いわな
440: (ﾜｯﾁｮｲ 9f80-4Q3H) 07/10(木)17:20 ID:qeCO91fI0(1) AAS
AMDが画像生成AI「Nitro-T」をリリース、32基のInstinct MI300Xでゼロから1日未満でトレーニング可能
外部ﾘﾝｸ:gigazine.net
441: (ﾜｯﾁｮｲ b754-1VI2) 07/10(木)19:08 ID:TwB+vwVm0(1) AAS
端っこしかアクセスしません、というのが前提みたいなものだな
100番目見たいんだけどとか、100番目に挿入したいんだけどと言われたら絶望する
442: (ﾜｯﾁｮｲ 576b-4VWQ) 07/10(木)21:24 ID:pWdjbLc50(1) AAS
map「ぼくをつかえ！」
443: (ｽﾌｯ Sdbf-zcFv) 07/11(金)14:40 ID:zLrVPFvnd(1) AAS
mapでもorderedmapでもN番目って概念が間違ってる
添字を通し番号のインデックスと観るかkeyvalueのkeyと観るかで
印象は変わるかも知れんがそれは君が観てる幻
444(1): (ﾜｯﾁｮｲ 9fa9-xq8W) 07/11(金)16:18 ID:vGvii7eb0(1) AAS
（昔の？）JavaScriptのArrayは、整数添字だけど内部的にはkey-value構造じゃなかったっけ？
Pythonについては、dictは（今は要素の挿入順序を記憶するけれども）概念的には要素の順番を観念しないことになっているのに、「next」でイテレーションするというのはよく考えると微妙にひっかかかりを感じなくもない。もっとも、かといって代わる語も思いつかないけどね。
445(1): (ｱｳｱｳｳｰ Sa9b-zcFv) 07/12(土)11:15 ID:Q8STCu4ga(1) AAS
要素の順番は大小が定義できてるかどうかだけで
N番目の要素と言うからにはさらに別に
飛び番があるかどうか等の条件が増える
446: (ﾜｯﾁｮｲ bf01-6GxP) 07/12(土)15:14 ID:RGUHmfGg0(1) AAS
>>444
内部的にどういう構造を使うかはJavaScriptエンジンの最適化の範疇
飛び番が多いスパースなArrayの場合とそうでない場合で実装を変えるのも自由
>>445
添字Nでのアクセス == N番目の要素へのアクセスとは限らないというだけでしょ
順番は定義できてるのにN番目の要素は他の条件がなければ定義できないというのはどう考えてもおかしい
上下前次1-新書関写板覧索設栞歴
あと 522 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.020s