站長資訊網本篇文章帶大家了解一下遞歸，介紹一下PHP 7 中對遞歸的優化。
⒈ 遞歸
??遞歸因其簡潔、優雅的特性在編程中經常會被使用。遞歸的代碼更具聲明性和自我描述性。遞歸不需要像迭代那樣解釋如何獲取值，而是在描述函數的最終結果。
??以累加和斐波那契數列的實現為例：
- 迭代方式實現
// 累加函數 // 給定參數 n，求小于等于 n 的正整數的和 function sumBelow(int $n) { if ($n <= 0) { return 0; } $result = 0; for ($i = 1; $i <= $n; $i ++) { $result += $i; } return $result; } // 斐波那契數列 // 給定參數 n，取得斐波那契數列中第 n 項的值 // 這里用數組模擬斐波那契數列，斐波那契數列第一項為 1，第二項為 2，初始化數組 $arr = [1, 1]，則斐波那契數列第 n 項的值為 $arr[n] = $arr[n-1] + $arr[n-2] function fib(int $n) { if ($n <= 0) { return false; } if ($n == 1) { return 1; } $arr = [1, 1]; for ($i = 2, $i <= $n; $i ++) { $arr[$i] = $arr[$i - 1] + $arr[$i - 2]; } return $arr[$n]; }
- 遞歸方式實現
// 累加函數 function sumBelow(int $n) { if ($n <= 1) { return 1; } return $n + sumBelow($n - 1); } // 斐波那契數列 function fib(int $n) { if ($n < 2) { return 1; } return fib($n - 1) + fib($n - 2); }
??相比之下，遞歸的實現方式更簡潔明了，可讀性更強，更容易理解。
⒉ 遞歸存在的問題
??程序中的函數調用，在底層通常需要遵循一定的調用約定（calling convention）。通常的過程是：
- 首先將函數的參數和返回地址入棧
- 然后 CPU 開始執行函數體中的代碼
- 最后在函數執行完成之后銷毀這塊占空間，CPU 回到返回地址所指的位置
??這個過程在低級語言（例如匯編）中非常快，因為低級語言直接與 CPU 交互，而 CPU 的運行速度非常快。在 x86_64 架構的 Linux 中，參數往往直接通過寄存器傳遞，內存中的棧空間會被預加載到 CPU 的緩存中，這樣 CPU 反問棧空間會非常非常快。
??同樣的過程在高級語言（例如 PHP）中卻截然不同。高級語言無法直接與 CPU 交互，需要借助虛擬機來虛擬化一套自身的堆、棧等概念。同時，還需要借助虛擬機來維護和管理這套虛擬化出來的堆棧。
??高級語言中的函數調用過程相較于低級語言已經很慢，而遞歸會讓這種情況雪上加霜。以上例中的累加函數為例，每到一個 sumBelow，ZVM 都需要構造一個函數調用棧（具體調用棧的構造之前的文章已經講過），隨著 n 的增大，需要構造的調用棧會越來越多，最終導致內存溢出。相較于累加函數，斐波那契函數的遞歸會使得調用棧的數量呈現幾何級數式的增加（因為每一個調用棧最終會新產生兩個調用棧）。
⒊ 使用蹦床函數（trampoline）和尾調用（tail call）來優化遞歸
??① 尾調用
??尾調用指的是一個函數最后只返回對自身的調用，再沒有其他的任何操作。由于函數返回的是對自身的調用，因此編譯器可以復用當前的調用棧而不需要新建調用棧。
??將前述的累加函數和斐波那契函數改為尾調用的實現方式，代碼如下
// 累加函數的尾調用方式實現 function subBelow(int $n, int $sum = 1) { if ($n <= 1) { return $sum; } return subBelow($n - 1, $sum + $n); } // 斐波那契函數的尾調用實現 function fib(int $n, int $acc1 = 1, int $acc2 = 2) { if ($n < 2) { return $acc1; } return fib($n - 1, $acc1 + $acc2, $acc1); }
??② 蹦床函數
??累加函數相對簡單，可以很方便的轉換成尾調用的實現方式。斐波那契函數的尾調用實現方式就相對比較麻煩。但在實際應用中，很多遞歸夾雜著很多復雜的條件判斷，在不同的條件下進行不同方式的遞歸。此時，無法直接把遞歸函數轉換成尾調用的形式，需要借助蹦床函數。
??所謂蹦床函數，其基本原理是將遞歸函數包裝成迭代的形式。以累加函數為例，首先改寫累加函數的實現方式：
function trampolineSumBelow(int $n, int $sum = 1) { if ($n <= 1) { return $sum; } return function() use ($n, $sum) { return trampolineSumBelow($n - 1, $sum + $n); }; }
??在函數的最后并沒有直接進行遞歸調用，而是把遞歸調用包裝進了一個閉包，而閉包函數不會立即執行。此時需要借助蹦床函數，如果蹦床函數發現返回的是一個閉包，那么蹦床函數會繼續執行返回的閉包，知道蹦床函數發現返回的是一個值。
function trampoline(callable $cloure, ...$args) { while (is_callable($cloure)) { $cloure = $cloure(...$args); } return $cloure; } echo trampoline('trampolineSumBelow', 100);
??蹦床函數是一種比較通用的解決遞歸調用的問題的方式。在蹦床函數中，返回的閉包被以迭代的方式執行，避免了函數遞歸導致的內存溢出。
⒋ ZVM 中對遞歸的優化
??在 PHP 7 中，通過尾調用的方式優化遞歸主要應用在對象的方法中。仍然以累加函數為例：
class Test { public function __construct(int $n) { $this->sum($n); } public function sum(int $n, int $sum = 1) { if ($n <= 1) { return $sum; } return $this->sum($n - 1, $sum + $n); } } $t = new Test($argv[1]); echo memory_get_peak_usage(true), PHP_EOL; // 經測試，在 $n <= 10000 的條件下，內存消耗的峰值恒定為 2M
??以上代碼對應的 OPCode 為：
// 主函數 L0: V2 = NEW 1 string("Test") L1: CHECK_FUNC_ARG 1 L2: V3 = FETCH_DIM_FUNC_ARG CV1($argv) int(1) L3: SEND_FUNC_ARG V3 1 L4: DO_FCALL L5: ASSIGN CV0($t) V2 L6: INIT_FCALL 1 96 string("memory_get_peak_usage") L7: SEND_VAL bool(true) 1 L8: V6 = DO_ICALL L9: ECHO V6 L10: ECHO string(" ") L11: RETURN int(1) // 構造函數 L0: CV0($n) = RECV 1 L1: INIT_METHOD_CALL 1 THIS string("sum") L2: SEND_VAR_EX CV0($n) 1 L3: DO_FCALL L4: RETURN null // 累加函數 L0: CV0($n) = RECV 1 L1: CV1($sum) = RECV_INIT 2 int(1) L2: T2 = IS_SMALLER_OR_EQUAL CV0($n) int(1) L3: JMPZ T2 L5 L4: RETURN CV1($sum) L5: INIT_METHOD_CALL 2 THIS string("sum") L6: T3 = SUB CV0($n) int(1) L7: SEND_VAL_EX T3 1 L8: T4 = ADD CV1($sum) CV0($n) L9: SEND_VAL_EX T4 2 L10: V5 = DO_FCALL L11: RETURN V5 L12: RETURN null
??當 class 中的累加函數 sum 發生尾調用時執行的 OPCode 為 DO_FCALL ，對應的底層實現為：
# define ZEND_VM_CONTINUE() return # define LOAD_OPLINE() opline = EX(opline) # define ZEND_VM_ENTER() execute_data = EG(current_execute_data); LOAD_OPLINE(); ZEND_VM_INTERRUPT_CHECK(); ZEND_VM_CONTINUE() static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL ZEND_DO_FCALL_SPEC_RETVAL_USED_HANDLER(ZEND_OPCODE_HANDLER_ARGS) { USE_OPLINE zend_execute_data *call = EX(call); zend_function *fbc = call->func; zend_object *object; zval *ret; SAVE_OPLINE(); EX(call) = call->prev_execute_data; /* 判斷所調用的方法是否為抽象方法或已廢棄的函數 */ /* ... ... */ LOAD_OPLINE(); if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) { /* 所調用的方法為開發者自定義的方法 */ ret = NULL; if (1) { ret = EX_VAR(opline->result.var); ZVAL_NULL(ret); } call->prev_execute_data = execute_data; i_init_func_execute_data(call, &fbc->op_array, ret); if (EXPECTED(zend_execute_ex == execute_ex)) { /* zend_execute_ex == execute_ex 說明方法調用的是自身，發生遞歸*/ ZEND_VM_ENTER(); } else { ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP); zend_execute_ex(call); } } else if (EXPECTED(fbc->type < ZEND_USER_FUNCTION)) { /* 內部方法調用 */ /* ... ... */ } else { /* ZEND_OVERLOADED_FUNCTION */ /* 重載的方法 */ /* ... ... */ } fcall_end: /* 異常判斷以及相應的后續處理 */ /* ... ... */ zend_vm_stack_free_call_frame(call); /* 異常判斷以及相應的后續處理 */ /* ... ... */ ZEND_VM_SET_OPCODE(opline + 1); ZEND_VM_CONTINUE(); }
??從 DO_FCALL 的底層實現可以看出，當發生方法遞歸調用時（zend_execute_ex == execute_ex），ZEND_VM_ENTER() 宏將 execute_data 轉換為當前方法的 execute_data ，同時將 opline 又置為 execute_data 中的第一條指令，在檢查完異常（ZEND_VM_INTERRUPT_CHECK()）之后，返回然后重新執行方法。
??通過蹦床函數的方式優化遞歸調用主要應用在對象的魔術方法 __call 、__callStatic 中。
class A { private function test($n) { echo "test $n", PHP_EOL; } public function __call($method, $args) { $this->$method(...$args); var_export($this); echo PHP_EOL; } } class B extends A { public function __call($method, $args) { (new parent)->$method(...$args); var_export($this); echo PHP_EOL; } } class C extends B { public function __call($method, $args) { (new parent)->$method(...$args); var_export($this); echo PHP_EOL; } } $c = new C(); //$c->test(11); echo memory_get_peak_usage(), PHP_EOL; // 經測試，僅初始化 $c 對象消耗的內存峰值為 402416 字節，調用 test 方法所消耗的內存峰值為 431536 字節
??在對象中嘗試調用某個方法時，如果該方法在當前對象中不存在或訪問受限（protected、private），則會調用對象的魔術方法 __call（如果通過靜態調用的方式，則會調用 __callStatic）。在 PHP 的底層實現中，該過程通過 zend_std_get_method 函數實現
static union _zend_function *zend_std_get_method(zend_object **obj_ptr, zend_string *method_name, const zval *key) { zend_object *zobj = *obj_ptr; zval *func; zend_function *fbc; zend_string *lc_method_name; zend_class_entry *scope = NULL; ALLOCA_FLAG(use_heap); if (EXPECTED(key != NULL)) { lc_method_name = Z_STR_P(key); #ifdef ZEND_ALLOCA_MAX_SIZE use_heap = 0; #endif } else { ZSTR_ALLOCA_ALLOC(lc_method_name, ZSTR_LEN(method_name), use_heap); zend_str_tolower_copy(ZSTR_VAL(lc_method_name), ZSTR_VAL(method_name), ZSTR_LEN(method_name)); } /* 所調用的方法在當前對象中不存在 */ if (UNEXPECTED((func = zend_hash_find(&zobj->ce->function_table, lc_method_name)) == NULL)) { if (UNEXPECTED(!key)) { ZSTR_ALLOCA_FREE(lc_method_name, use_heap); } if (zobj->ce->__call) { /* 當前對象存在魔術方法 __call */ return zend_get_user_call_function(zobj->ce, method_name); } else { return NULL; } } /* 所調用的方法為 protected 或 private 類型時的處理邏輯 */ /* ... ... */ } static zend_always_inline zend_function *zend_get_user_call_function(zend_class_entry *ce, zend_string *method_name) { return zend_get_call_trampoline_func(ce, method_name, 0); } ZEND_API zend_function *zend_get_call_trampoline_func(zend_class_entry *ce, zend_string *method_name, int is_static) { size_t mname_len; zend_op_array *func; zend_function *fbc = is_static ? ce->__callstatic : ce->__call; ZEND_ASSERT(fbc); if (EXPECTED(EG(trampoline).common.function_name == NULL)) { func = &EG(trampoline).op_array; } else { func = ecalloc(1, sizeof(zend_op_array)); } func->type = ZEND_USER_FUNCTION; func->arg_flags[0] = 0; func->arg_flags[1] = 0; func->arg_flags[2] = 0; func->fn_flags = ZEND_ACC_CALL_VIA_TRAMPOLINE | ZEND_ACC_PUBLIC; if (is_static) { func->fn_flags |= ZEND_ACC_STATIC; } func->opcodes = &EG(call_trampoline_op); func->prototype = fbc; func->scope = fbc->common.scope; /* reserve space for arguments, local and temorary variables */ func->T = (fbc->type == ZEND_USER_FUNCTION)? MAX(fbc->op_array.last_var + fbc->op_array.T, 2) : 2; func->filename = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.filename : ZSTR_EMPTY_ALLOC(); func->line_start = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_start : 0; func->line_end = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_end : 0; //??? keep compatibility for "
主站蜘蛛池模板：
自拍偷自拍亚洲精品第1页|
国产亚洲欧美精品永久|
一色屋精品视频在线观看|
久久久久国产精品|
欧产日产国产精品精品|
久久国产成人亚洲精品影院|
久久国产精品99久久久久久老狼|
亚洲精品国产精品乱码不卡√|
精品无码综合一区|
久久99国产精品久久99|
久久久精品人妻一区二区三区蜜桃|
久久精品成人免费国产片小草|
亚洲国产精品婷婷久久|
国产亚洲色婷婷久久99精品|
一本色道久久综合亚洲精品
|
亚洲国产精品丝袜在线观看|
亚洲日本精品一区二区|
精品成人免费自拍视频|
2021最新国产精品网站|
久久er99热精品一区二区|
日韩精品一二三四区|
精品久久久久久国产牛牛app
|
久久成人国产精品一区二区|
99精品影院|
日本精品不卡视频|
久久99精品国产99久久6男男|
国产精品亚洲片在线|
久久久久成人精品无码中文字幕
|
人人妻人人澡人人爽欧美精品|
无码人妻精品一区二区三区99不卡|
精品国产午夜福利在线观看|
99久久精品无码一区二区毛片
|
完整观看高清秒播国内外精品资源|
国产成人精品亚洲精品|
老司机国内精品久久久久|
91精品国产福利在线导航|
精品人妻大屁股白浆无码|
亚洲av永久无码精品秋霞电影影院
|
国语自产精品视频|
黄床大片免费30分钟国产精品
|
精品国产第1页|