aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--notebooks/guile-recursion.ipynb36
-rw-r--r--posts/guile-recursion.md2
2 files changed, 19 insertions, 19 deletions
diff --git a/notebooks/guile-recursion.ipynb b/notebooks/guile-recursion.ipynb
index ed1678c..2e66111 100644
--- a/notebooks/guile-recursion.ipynb
+++ b/notebooks/guile-recursion.ipynb
@@ -68,7 +68,7 @@
},
{
"cell_type": "markdown",
- "id": "6198154b",
+ "id": "251c4f18",
"metadata": {},
"source": [
"### 再帰手続きの読み方\n",
@@ -362,7 +362,7 @@
},
{
"cell_type": "markdown",
- "id": "fa6ae93a",
+ "id": "276d0fd9",
"metadata": {},
"source": [
"予想通り `map-tail` の方が少し遅いという結果になりました(`map-tail` の実装に引数を破壊する版の `reverse!` を使った場合についても調べたところ、その場合は `map` とほぼ同じ計算時間になることを確認しています。計算時間が変わらないのであれば `map` の方が良いでしょう。また、[Guile のマニュアルの Stack Overflow の節](https://www.gnu.org/software/guile/manual/html_node/Stack-Overflow.html#Stack-Overflow)で `reverse!` を使うと継続安全(continuation-safe)が損なわれ、 `map-tail` の計算が終了した後に `f` の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。"
@@ -370,7 +370,7 @@
},
{
"cell_type": "markdown",
- "id": "23cb50bf",
+ "id": "3788886d",
"metadata": {},
"source": [
"## 自然な再帰だと計算量が爆発してしまうケース\n",
@@ -380,7 +380,7 @@
},
{
"cell_type": "markdown",
- "id": "92025e95",
+ "id": "770912a1",
"metadata": {},
"source": [
"### リストを反転する手続き\n",
@@ -391,7 +391,7 @@
{
"cell_type": "code",
"execution_count": 10,
- "id": "6a801cbb",
+ "id": "956af77d",
"metadata": {},
"outputs": [],
"source": [
@@ -403,7 +403,7 @@
},
{
"cell_type": "markdown",
- "id": "ef58ca96",
+ "id": "1126971d",
"metadata": {},
"source": [
"`reverse` の実行例:"
@@ -412,7 +412,7 @@
{
"cell_type": "code",
"execution_count": 11,
- "id": "22ca7753",
+ "id": "0cdaf6cc",
"metadata": {},
"outputs": [
{
@@ -434,7 +434,7 @@
},
{
"cell_type": "markdown",
- "id": "5e7cd66e",
+ "id": "ce6c6577",
"metadata": {},
"source": [
"この手続きは自然でたしかに正しいことはコードを読めば理解できるでしょう。ただし、一つ落とし穴があります。Lisp のリストは先頭に要素を追加する場合は `O(1)` の計算量でできるのに対してリストの最後に要素を追加する場合は `O(n)` かかるのです。\n",
@@ -444,7 +444,7 @@
{
"cell_type": "code",
"execution_count": 12,
- "id": "cb5d2be9",
+ "id": "63bedfe3",
"metadata": {},
"outputs": [
{
@@ -469,7 +469,7 @@
},
{
"cell_type": "markdown",
- "id": "e0338644",
+ "id": "65ee86fc",
"metadata": {},
"source": [
"これに対してリストの先頭に追加する操作しか行なわない `reverse-tail` を試してみましょう。"
@@ -478,7 +478,7 @@
{
"cell_type": "code",
"execution_count": 13,
- "id": "af106f5a",
+ "id": "94ab7202",
"metadata": {},
"outputs": [],
"source": [
@@ -491,7 +491,7 @@
},
{
"cell_type": "markdown",
- "id": "5a09232e",
+ "id": "c184f8de",
"metadata": {},
"source": [
"`reverse-tail` の実行例"
@@ -500,7 +500,7 @@
{
"cell_type": "code",
"execution_count": 14,
- "id": "0ff1881a",
+ "id": "cd4cac47",
"metadata": {},
"outputs": [
{
@@ -522,7 +522,7 @@
},
{
"cell_type": "markdown",
- "id": "cc413390",
+ "id": "468a39bf",
"metadata": {},
"source": [
"`reverse-tail` の実行時間の計測:"
@@ -531,7 +531,7 @@
{
"cell_type": "code",
"execution_count": 15,
- "id": "929e14f1",
+ "id": "57eb603c",
"metadata": {},
"outputs": [
{
@@ -556,17 +556,17 @@
},
{
"cell_type": "markdown",
- "id": "9983766e",
+ "id": "17b08877",
"metadata": {},
"source": [
- "大きい値では `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。\n",
+ "リストが長い場合は `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。\n",
"\n",
"このように自然な再帰では計算に時間がかかり過ぎてしまう場合もあります。これは末尾再帰かどうかという話ではなくて、アルゴリズムが異なるために生じている違いであり今回の再帰手続きを末尾再帰の手続きに直す必要性の有無とは少しずれた話ではあります。こういう重い計算をしていてそれが問題となる場合には別のアルゴリズムを検討する必要があります。"
]
},
{
"cell_type": "markdown",
- "id": "6c955b77",
+ "id": "ca0c0a7d",
"metadata": {},
"source": [
"## おわりに\n",
diff --git a/posts/guile-recursion.md b/posts/guile-recursion.md
index 4dab8ec..e0863b8 100644
--- a/posts/guile-recursion.md
+++ b/posts/guile-recursion.md
@@ -378,7 +378,7 @@ clock utime stime cutime cstime gctime
-大きい値では `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。
+リストが長い場合は `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。
このように自然な再帰では計算に時間がかかり過ぎてしまう場合もあります。これは末尾再帰かどうかという話ではなくて、アルゴリズムが異なるために生じている違いであり今回の再帰手続きを末尾再帰の手続きに直す必要性の有無とは少しずれた話ではあります。こういう重い計算をしていてそれが問題となる場合には別のアルゴリズムを検討する必要があります。