k-sunakoの技術ログ

My NumPy Year: Creating a DType for the Next Generation of Scientific Computing を読んだ。

• Numpy2.xの文字列のDTypeについて記載された記事である
• Python3はUnicode文字列を扱うため、Numpy1.xでは文字列の型は dtype='<U5' のようになる
  • アスキー文字でも4バイト使うため、メモリ効率が悪い
  • 文字列の操作が遅い
• Numpy1.xでは文字列の型は dtype=object としても表現できる
  • これはpandasの性能に大きな影響があった
  • また、astropyという天文学(?)関連のライブラリにも
• オブジェクトの配列でなくポインターの配列で実装した？
• Numpy2.xで文字列の型 np.dtype.StringDtype が導入された
• メモリ管理に「Arena Allocator（アリーナ・アロケーター）」 というものも使われている
  • [Zig] Arena Allocatorを使った “ふつうの” Zigプログラミング

Smolderingly fast b-trees を読んだ。

• 順序があるデータ構造(B-Tree)とハッシュマップの性能差を述べた記事である
• WASMではいくつかの制約が追加される
• 順序があるデータ構造とハッシュマップの性能差には人々の間で認識に隔たりがある
• rust と zig を使って、性能調査を実施している
  • ランダムな整数と文字列でのアクセス、順序のある整数と文字列のアクセスなど
• B-Treeの改善を低水準(CPU)で記載されている

(有理算術演算: 高精度数値計算のためのアルゴリズムとプログラミング 2023) を参考にして、連分数を計算するコードを書いた。

• 関数: get_continued_fraction で連分数展開 [a0, a1, …] を取得する
• 関数: get_approx_fraction で連分数展開から近似分数を計算する

import math
from fractions import Fraction

def get_continued_fraction(n):
    """入力は素数と仮定して、循環の最初の周期を返却する"""
    r = 0
    s = 1
    a = int(math.floor(math.sqrt(n)))
    a0 = a
    lst_a = [a]
    cnt = 100
    while 0 < cnt:
        _s = (n-(r-a*s)**2) / s
        _r = -(r-a*s)
        a = int(math.floor( (math.sqrt(n) + _r) / _s))
        r = _r
        s = _s
        cnt -= 1
        lst_a.append(a)
        if a == 2*a0:
            break
    return lst_a

def get_approx_fraction(cfrac):
    assert 0 < len(cfrac)

    if 1 == len(cfrac):
        return Fraction(cfrac[0], 1)
    elif 2 == len(cfrac):
        return Fraction(cfrac[0] * cfrac[1] + 1, cfrac[1])
    else:
        pi_1 = cfrac[0] * cfrac[1] + 1
        pi = cfrac[2] * pi_1 + cfrac[0]
        qi_1 = cfrac[1]
        qi = cfrac[2] * qi_1 + 1
        for ai in cfrac[3:]:
            pi, pi_1 = ai * pi + pi_1, pi
            qi, qi_1 = ai * qi + qi_1, qi
        return Fraction(pi, qi)

Jujutsu in practice を読んだ。

• Jujutsu は新しいバージョン管理ツールであるである
• 既存のgitレポジトリにも適用可能である
  • .jjというフォルダが作成される
• Jujutsu はブランチでなく、リビジョンを主に扱う
• Jujutsu には ステージング はない、リビジョンが全てである

ワークフローの全容はこの記事のみでは掴めなかった。次に作るプログラムで試してみようか？

githublog/2024/5/29/fast-inverse-sqrt.md at main · francisrstokes/githublog を読んだ。

• \(\frac{1}{\sqrt x}\) を高速に計算するC言語のコードを説明する記事である
• float(単精度浮動小数点、32bit)のbitの表現を利用している
  • 仮数(23bit)、指数(8bit)、符号(1bit)
• float型をlong型に変更して1bitシフトしてfloat型に変更すると、 log2 相当の処理になる
• さらにニュートン法を利用して、近似の精度を向上させている

Write your own Emacs Lisp macros – a short introduction を読んだ。

• Emacsの拡張言語である Emacs Lisp のマクロ機能の記事である
• cl-destructuring-bind を使った制御は始めて知った
• Rustのマクロ記事もあるようなのでそちらも読みたい
  • Declarative macros in Rust – a way of writing your own syntax

Analyzing New Unique Identifier Formats (UUIDv6, UUIDv7, and UUIDv8) を読んだ。この記事は2022年のもので少し内容が古いようだ。

• UUIDは 128 bit の識別子である
• UUIDv1は2005年にRFC4122として仕様が決定した
  • タイムスタンプとMACアドレスに関する欠点を指摘されている
• この記事はドラフト文書にある4つのバージョンが記載されている
  • UUIDv6, UUIDv7, UUIDv8, Max UUID

Exploring Typst, a new typesetting system similar to LaTeX – jreyesr’s blog を読んだ。

• TypstはLaTeXのような組版システムである
• TypstとLaTeXとMarkdownとの比較をしている
• LaTeXのtikzにはTypstのcetzが対応している
• Typstの構文はMarkdownに近い

かなり長い記事なので、もう一回読みたい。のこりは別の日に。 Emacsにもtypst用のパッケージもあったので試してみたい。

ThatGeoGuy – Reflecting on Transducers を読んだ。

• Transducers というプログラミングの概念/機能を紹介している。
• Rust/Scheme/Clojureが取り上げられる
• Rustの Iterator トレイトは型を使用して, map 等を実装している
• Scheme は動的型言語なのでRustのようには同様の機能を実装できない
• Scheme は SRFI-171 で Transducers を導入した
• ClojureのTranducerとはなにかが違う

半分程度しか読めていない。また時間を取ろう。

You don’t need a terminal emulator · Andrey Listopadov を読んだ。

• async-shell-command が有用であることを再発見した
• project-compile も使えそう

プログラミングでは端末とEmacsを交互に使っていたが、Emacsで済むことが増えそうだ。