feed-digest - #algorithms

発散定理を用いて三角形メッシュの体積をO(n)で高速計算する手法の解説。ベクトル場F=<x,0,0>を選び面積分に帰着させることで、三角形ごとの外積計算のみで体積を求める式（1/6ΣΔ1×Δ2の項）を導出し、数値積分や微分を必要としない軽量なアルゴリズムを示している。1トライアングルあたり11回の浮動小数点演算で済み、Raspberry Piでも毎フレーム3000万三角形程度を処理できると試算している。

CPython組み込み型（list、tuple、dict、set、str/bytes/bytearray、memoryview、range）の各操作について、時間計算量をBig O記法で一覧化した公式ドキュメント。追加・削除・検索・スライス等の操作コストと、それぞれの実装上の注意点（末尾操作の効率性、ハッシュ衝突時の劣化等）がまとめられている。