言語比較ベンチマーク（Dijkstra 実行速度）

こんにちは。
下記のオリジナルをそっくり拝借し、ほぼ同様の言語比較ベンチマーク（hyperfine 利用）を行いました。

• 「Python を Go に書き換えるとどれくらい速くなる？ 7つの言語で Dijkstra の実行速度を比較」

ベンチマーク結果

なお下記のようなbunの処理速度の課題点が見つかり、issue を上げました¹。

データ読み込みの部分

プログラムの作りは、オリジナルと同様に、データを標準入力から読み込み、グラフ構造へ格納します。そこの部分の実行時間を調べた結果です

• 現状の bun v.1.1.38 はここの処理速度が 顕著に遅く、課題点解消が望まれます。
  

経路探索

「データ読み込み ＋ Dijkstra 経路探索の 30 回繰り返し」の総実行時間の結果です。経路探索部の実行速度はcppとrustは拮抗するようです。

入力データの取得（事前）

事前準備として、入力データを下記のようにして取得します。オリジナルとは異なり、ノードIDを非負整数へ連番で採番する処理も合わせて行います。

$ ./get_edgelist.sh tokyo | gzip > edgelist_tokyo.csv.gz
$ gzcat edgelist_tokyo.csv.gz | wc -l
 1035446
$ gzcat edgelist_tokyo.csv.gz | head -n8
0,1,113876
0,2,1386
0,3,264898
0,4,56376
1,0,113876
1,5,40288
1,6,11473
5,1,40288

get_edgelist.sh

#!/bin/sh

city="$(echo "$1" | tr '[:upper:]' '[:lower:]')"
case "$city" in
  paris ) id=3663396 ;;
  washingtondc ) id=3663522 ;;
  tokyo | * ) id=3663336 ;;
esac
#https://figshare.com/articles/dataset/Urban_Road_Network_Data/2061897

url="https://figshare.com/ndownloader/files/$id"
tmpdir="$(mktemp -d "${TMPDIR:-/tmp/}"foo.XXXXXXXXX)"
zipfile="$tmpdir/$id.zip"

curl -L "$url" > "$zipfile" 2>/dev/null
city=$(unzip -ql "$zipfile" | perl -nle 'print $1 if /(\S+)_Edgelist.csv/')
edgelistfile="$city"_Edgelist.csv
echo "$edgelistfile" 1>&2

kilo=1000  # km
unzip -p "$zipfile" "$edgelistfile" | awk -F, -v kilo=${kilo} 'BEGIN{i=0}NR>1{if
(id[$3]=="")id[$3]=i++; if(id[$4]=="")id[$4]=i++; printf("%d,%d,%d\n",id[$3],id[
$4],$6*$kilo)}'

1. 問題報告を https://github.com/oven-sh/bun/issues へ上げました（confirmed bug のラベルがつきました）。 ↩