コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > バックエンド開発 > PHPチュートリアル > [考察] PHP ソート系列関数の C 実装ではどのソート アルゴリズムが使用されていますか?

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

WBOY
リリース： 2016-07-25 08:46:31
オリジナル
1122 人が閲覧しました

ext/standard/php_array.h

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

  1. #ifndef PHP_ARRAY_H
  2. #define PHP_ARRAY_H
  4. PHP_MINIT_FUNCTION(配列);
  5. PHP_MSHUTDOWN_FUNCTION(配列);
  7. PHP_FUNCTION(ksort);
  8. PHP_FUNCTION(krsort);
  9. PHP_FUNCTION(natsort);
  10. PHP_FUNCTION(natcasesort);
  11. PHP_FUNCTION(asort);
  12. PHP_FUNCTION(arsort);
  13. PHP_FUNCTION(sort);
  14. PHP_FUNCTION(rsort);
  15. PHP_FUNCTION(usort);
  16. PHP_FUNCTION(uasort);
  17. PHP_FUNCTION(uksort);
  18. ...
コピーコード

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

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])
配列を並べ替える */
Php_function (sort) {
    zval *array;
  1. long sort_type = p Hp_sort_ Regular
  3. if (zend_parse_parameters(ZEND_NUM_ARGS( ) TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
  4. RETURN_FALSE;
  5. }
  7. php_set_compare_func(sort_type TSRMLS_CC);
  9. if (zend_hash_sort(Z_ARRVAL_P(array), zend_q sort, data_compare、1 TSRMLS_CC) == 失敗) {
  10. RETURN_FALSE;
  11. }
  12. RETURN_TRUE;
  13. }
  14. /* }}} */
  18. コードをコピー
コード内で、私は次のことを確認しました
if (zend_hash_sort(Z_ARRVAL_P(配列), zend_qsort, php_array_data_compare, ……
クイックソートを使用する可能性が高い。

分析を続けます。

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);

HANDLE_BLOCK_INTERRUPTIONS();
ht->pListHead = arTmp[0];
    ht-> pListTail = NULL;
  1. ht->pInternalPointer = ht->pListHead;
  3. arTmp[0]->pListLast = NULL;
  4. if (i > 1) {
  5. arTmp[0]->pListNext = arTmp [1];
  6. for (j = 1; j arTmp[j]->pListLast = arTmp[j-1];
  7. arTmp[j]->pListNext = arTmp[ j+1];
  8. }
  9. arTmp[j]->pListLast = arTmp[j-1];
  10. arTmp[j]->pListNext = NULL;
  11. } else {
  12. arTmp[0]->pListNext = NULL;
  13. }
  14. ht->pListTail = arTmp[i-1];
  16. pefree(arTmp, ht->persistent);
  17. HANDLE_UNBLOCK_INTERRUPTIONS();
  19. if (renumber) {
  20. p = ht->; pListHead;
  21. i=0;
  22. while (p != NULL) {
  23. p->nKeyLength = 0;
  24. p->h = i++;
  25. p = p->pListNext;
  26. }
  27. ht-> nNextFreeElement = i;
  28. zend_hash_rehash(ht);
  29. }
  33. コードをコピー
アルゴリズムの中で、クイックソートよりも速いのは間違いなく基数ソートです。アルゴリズムをざっと見てみると、それは基本的なソートの
ハッシュバケットソートかもしれません。 バケットソートが安定している バケット ソートは最も高速な一般的なソートであり、ほとんどの場合、クイック ソートよりも高速です。 バケットのソートは非常に高速ですが、多くのスペースも消費します (
スペースを時間と交換する

)

どのようなphpが使用されましたか
関連ラベル：
[讨论]php 排序系列的函数内部的C实现是用了哪种排序算法？
ソース：php.cn
前の記事：PHPモバイルインターネット開発(1) - 環境構築・設定 次の記事：PHP FTP操作クラス（アップロード、コピー、移動、ファイル削除/ディレクトリ作成）
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
function_exists() はカスタム関数を決定できません Function test () {return true;} if (function_exists ('test')) {echo "テストは関数です";
から 2024-04-29 11:01:01
0
3
2049
Google Chromeのモバイル版を表示する方法 こんにちは、先生、Google Chrome をモバイル版に変更するにはどうすればよいですか?
から 2024-04-23 00:22:19
0
11
2204
子ウィンドウは親ウィンドウを操作しますが、出力は応答しません。 最初の 2 つの文は実行可能ですが、最後の文は実装できません。
から 2024-04-19 15:37:47
0
1
1862
親ウィンドウには出力がありません document.onclick = function(){ window.opener.document.write('私は子ウィンドウの出力です');
から 2024-04-18 23:52:34
0
1
1749
CSS マインド マッピングに関するコースウェアはどこにありますか? コースウェア
から 2024-04-16 10:10:18
0
0
1770
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート