pythonのしくみ

Divij Bindlish

python の　listはどのように実装されているでしょうか？

配列とlinked listのいいとこ取り、と聞いたことがあるが真相はいかに。

基本はarrayですね。するとreadはO(1)です。appendは配列のresizeが必要ですが、そこはバッチで行って節約 (how python list is implemented)

stackoverflowの解答(how-is-pythons-list-implemented)ではdynamic arrayを使っていますというシンプルな解答です。

jythonのlistの実装がlinkedlistで非常に残念という、面白いですし、あー、そいうものは使いたくないなーと思わせる情報も書いてくれていいます。

基本的には上の記事と内容は同じです。

ということでpythonのlistの実装はdynamic arrayです

関連する内容としてpython wikiから実行時間の一覧表はこちらです。ちなみにpythonのinsertのコストがO(N)であることに気づかせてくれた問題はこちら【アルゴリズム脳トレ】leetcode easy 107 binary tree level order traversal ii

python-wikiにもそうある。

上図出典:https://wiki.python.org/moin/TimeComplexity

参考stackoverflow: what-is-the-cost-complexity-of-insert-in-list-at-some-location

python の　list extend の実行時間(time complexity)は？

（binary tree level order traversal）

・・・

python の set の実装は？

hash mapだと思います。

how is set implemented? stackoverflow, geeksforgeek, quora

hashtableやね(サイソンcpython, ソース見てみぃsetobject.c )

あとdiffereceやintersectionとかの関数を早くするためにsorted linked listっぽいｋともしてるかも　by geeksforgeek

まぁ、hashmapとかhashtableということで間違いないです　※1

※1) こういうjavaのhashmap, hashtable違いには今は気にしないで, pythonの世界だから。

（python-wikiによるとsetはほぼdictと同じ実装だとあるが、そのページにdictの詳しい実装については書かれていない。）

pythonのhashmapいわゆる辞書の実装は？

javaだと

ハッシュテーブル(HashSet, HashMap)の実装 を見てハッシュの原始的な実装は

hash関数 からバケット割り出して、その値を入れておく

という基本を抑えた上で、実際のjavaの実装に近い実装を抑えるとよい。

pythonの実装方法はというと

オープンアドレスでバケットサイズは慣例で2^Nになるように取られるようだ

するとhash(x) & (bucket_sz -1 )のような技が使えるからだ

http://dsas.blog.klab.org/archives/python-dict-internal.html

pythonのheapの実装は？

配列をつかってbinary treeを表現することで最後のノードがどこなのか把握できるようにしている。heapの実装はこの最後がどこ？っていう情報を常にO(1)でアクセスできるようにするのが肝だと思うんで。

https://docs.python.org/ja/3/library/heapq.html

あと、このheapq.nsmallestのtime complexityは？

https://github.com/python/cpython/blob/master/Lib/heapq.py によるとだいたい O(k * log N)よりすこし太いくらいで、最悪のケースでO(k * (n-k))とのことです。

実例: find median from data stream

python3ではintが無限ってどうやって実装されてるの？

短い解答としてNumericはintegerの集まりでメモリの許す限り拡張可能です。

というもの、詳細は以下

stackoverflow why-integers-do-not-have-size-limit-in-python-3 では

In python 3, there is no limit on the value of integers, as mentioned in this post
Can someone explain to me why python 3 does not have a limit on integer size, and how do they do it (under the hood)

とありまして、解答としては

内部では結局32bitか64bitがアサインされるとのこと。訳せるとおもうのですがいろいろ見てみてた結果私は次のように理解することにしました。

サーバーシステムの物理的なCPUのfull adderの制約には変わりないということですね。それをpythonはソフト的に arbitrary precision を実現してくれています。

arbitary precisonというのはintでもlongでも大きさによって自動で変換してくれまっせ、というもの。さらにmemoryでbytesベースで数字を保持しているので、メモリーが許す限りどこまでも拡張できるとのこと。数字の表現は内部的なintegerの集まりで（本家のNumbers are created by numeric literals or as the result of built-in functions and operators. Unadorned integer literals yield integersとう表現よりそう解釈）、その内部はシステム依存でCで実装されている部分で32bit, 64bits intergerという訳で最初の説明とつながる。

https://mortada.net/can-integer-operations-overflow-in-python.html

疑問のソース:

pythonのgeneratorって何よ

一言で言えば「generatorとはlistと違ってメモリO(1)で反復できる(statefulな)オブジェクト」

くわしはこちらpythonのgeneratorをちゃんと理解する日がきました

pythonのdictへのデータ大量投入は処理速度が遅いことについて

dictに数百万単位のデータ投入は数秒のコストと心得よ

listもおんなじかなー、つまりは大量のデータの場合space のcomplexityは　time complexityに影響するということ。

こうなると、データ量がめっちゃ大きいパターンはgeneratorをつかうほうがいい、と理解できる。まぁ、どうしてもデータを保存しなければならない場合は、結局配列とかに保存してしまうのだろうが、stream的に処理できるなら、それからgeneratorでいいだろう、という考え。

事例：15 3 sum

pythonのdequeってなに？リストとどう使い分けるか

まずはdequeとは？ メリっとは両端へのアクセスでデメリは両端以外へのアクセス。リストとの違いをおさえよ。

Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと、データをキューやスタック、デック（両端キュー）として効率的に扱うことができる。collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント

標準のリストをキューやスタック、デック（両端キュー）として使うことも可能だが、リストでは先頭の要素に対する削除や追加（挿入）は処理速度が遅いためdequeのほうが効率的。なお、dequeには、両端以外の要素へのアクセスが遅いというデメリットもあるので注意。

出典: https://note.nkmk.me/python-collections-deque/

かんたんに使ってみとQueue()より扱いやすい。俺はこっちの好きだ。

しかもdequeは　queue(FIFO)としても、stack(FILO)としても、deque(double-ended両端queue）としても使えるし

公式ではスレッドセーフって書いてあるし、queue.Queueより良いじゃん！と思いましたが違いは、queue.Queueは真にスレッドセーフを謳っていて、dequeはappend, popはスレッドセーフとしかドキュメントには書かれていないのです。

stackoverflow, is-this-deque-thread-safe-in-pythonでも似たような、質問がありましたし、このブログ記事でもQueueはスレッドセーフとありましたので、

私もdequeはシングルスレッドでPOC的にはこれ。もちろん、dequeとして両端アクセスのみのときは、listsより、Queueより、dequeを使うぞー、さらにスレッドセーフにlock実装とかすれば本番でも十分dequeつかえるんじゃない。普通にLIFOをマルチスレッドで扱いたいときは、Queueね。と、そういう理解をしました。

事例：【アルゴリズム脳トレ】leetcode medium 127 word ladderでdequeを扱ったコードを紹介していて、そこで初めて学んだ。

pythonのlru_cache (Least Recency Used Cache)を使いたい関数にlistを渡しているとunhashableで怒られる

https://stackoverflow.com/questions/49210801/python3-pass-lists-to-function-with-functools-lru-cache

それは表題の通り

pythonのlru_cache (Least Recency Used Cache)を使いたい関数にlistを渡しているとunhashableで怒られる

はそのままでpythonではlistはhashableではないので、やりたいならimmutableでhashableなtupleに変換するとか、そもそも

signitureとしてlistを省くとかを考えましょう。

ちなみに、

functools.pyのlru_cacheもlinked listを使って実装されている。https://github.com/python/cpython/blob/3.8/Lib/functools.py#L530

このあたりはOrderedDictやLRU_Cacheなどを眺めても似たようにlinkedlistが鍵になってくる。lru_cacheではthredsafeに作られているのも特徴

pythonのOrderedDictの順序記憶の仕組みはdoubly linked listで実装

OrderedDictはダブルリンクリストで実装されているようです

https://leetcode.com/problems/lru-cache/いう問題を解くとより理解が深まります。

You can read the implementation in CPython's source code: Lib/collections/__init__.py as OrderedDict is implemented in Python.

It is using a doubly linked list to maintain the order of elements in the dictionary.

stackoverflow: https://stackoverflow.com/questions/34496582/is-ordereddict-a-tree

実はfunctools.pyのlru_cacheもlinked listを使って実装されている。けどもうちょっと高級　https://github.com/python/cpython/blob/3.8/Lib/functools.py#L530

python のthreadingは意味ないの？GIL?

結論からいうと

pythonではGIL(Global Interpreter Lock)が常に1つのthreadのみが稼働することを保証しています。

よって、thread1, thread2を定義しても高速にContextSwitchが発生していますが、実際はシーケンシャルに処理されています。

なので

本当に並列実行させたい！という意味では意味がありませんが(I/O処理では一役買っているが、それくらい）、

徐々に実行させたいという意味では意味があります。

また、

このGILの制約を取り除きたい場合は方法が２つあります。

１つ目は、複数プロセスでなら並列できます。理由はGILはプロセス毎に存在するからです。だからmultipthreadingといモジュールがあるのです。

２つ目は、他のthrading関数ライブラリを使う方法が考えられ、Jpythonやpypyがその一例です。

参考動画：Multithreading Python Programming Tutorial

参照

本家でcpythonの実装についてまとめあられている、唯一無二のソース；https://wiki.python.org/moin/TimeComplexity