[考察] PHP ソート系列関数の C 実装ではどのソート アルゴリズムが使用されていますか?

ext/standard/php_array.h

https://github.com/php/php-src/blob/master/ext/standard/php_array.h

#ifndef PHP_ARRAY_H
#define PHP_ARRAY_H

PHP_MINIT_FUNCTION(配列);
PHP_MSHUTDOWN_FUNCTION(配列);

PHP_FUNCTION(ksort);
PHP_FUNCTION(krsort);
PHP_FUNCTION(natsort);
PHP_FUNCTION(natcasesort);
 PHP_FUNCTION(asort);
PHP_FUNCTION(arsort);
PHP_FUNCTION(sort);
PHP_FUNCTION(rsort);
PHP_FUNCTION(usort);
PHP_FUNCTION(uasort);
PHP_FUNCTION(uksort);
...

上記で定義された並べ替え関数:

arsort -- インデックスの関係を維持しながら、配列を逆順にソートします。 asort – インデックス関係を維持しながら配列をソートする krsort -- 配列をキー名で逆順にソートします。 ksort -- 配列をキーでソートする natcasesort -- 「自然ソート」アルゴリズムを使用して、大文字と小文字を区別しない方法で配列をソートします。 natsort -- 「自然ソート」アルゴリズムを使用して配列をソートします。 rsort -- 配列を逆順にソートします sort -- 配列を並べ替えます uasort – ユーザー定義の比較関数を使用して配列内の値を並べ替え、インデックスの関連付けを維持します uksort -- ユーザー定義の比較関数を使用して配列内のキーを並べ替えます。 usort – ユーザー定義の比較関数を使用して配列内の値を並べ替えます

簡単にするために、sort 関数のみを分析します: https://github.com/php/php-src/blob/master/ext/standard/array.c

{/ *{{Proto Bool Sort (Array & Array_arg [, Int Sort_flags])

 long sort_type = p Hp_sort_ Regular

 if (zend_parse_parameters(ZEND_NUM_ARGS( ) TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
 RETURN_FALSE;
 }

 php_set_compare_func(sort_type TSRMLS_CC);

 if (zend_hash_sort(Z_ARRVAL_P(array), zend_q sort, data_compare、1 TSRMLS_CC) == 失敗) {
 RETURN_FALSE;
 }
 RETURN_TRUE;
}
/* }}} */



コードをコピー

クイックソートを使用する可能性が高い。

分析を続けます。

Zend/zend_hash.c

https://github.com/php/php-src/blob/master/Zend/zend_hash.c

(*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);

 ht->pInternalPointer = ht->pListHead;

 arTmp[0]->pListLast = NULL;
 if (i > 1) {
 arTmp[0]->pListNext = arTmp [1];
 for (j = 1; j  arTmp[j]->pListLast = arTmp[j-1];
 arTmp[j]->pListNext = arTmp[ j+1];
 }
 arTmp[j]->pListLast = arTmp[j-1];
 arTmp[j]->pListNext = NULL;
 } else {
 arTmp[0]->pListNext = NULL;
 }
 ht->pListTail = arTmp[i-1];

 pefree(arTmp, ht->persistent);
 HANDLE_UNBLOCK_INTERRUPTIONS();

 if (renumber) {
 p = ht->; pListHead;
 i=0;
 while (p != NULL) {
 p->nKeyLength = 0;
 p->h = i++;
 p = p->pListNext;
 }
 ht-> nNextFreeElement = i;
 zend_hash_rehash(ht);
 }



コードをコピー

スペースを時間と交換する

)

どのようなphpが使用されましたか