مصفوفات PHP - إزالة التكرارات (تعقيد الوقت)

Question

حسنًا، هذه ليست مسألة "كيفية الحصول على جميع العناصر الفريدة" أو "كيفية إزالة التكرارات من مصفوفتي في PHP".هذا سؤال حول تعقيد الوقت.

لقد اعتقدت أن array_unique هو إلى حد ما O(n^2 - n) وإليك تطبيقي:

function array_unique2($array) 
{ 
    $to_return = array(); 
    $current_index = 0;

    for ( $i = 0 ; $i < count($array); $i++ ) 
    { 
        $current_is_unique = true; 

        for ( $a = $i+1; $a < count($array); $a++ ) 
        { 
            if ( $array[$i] == $array[$a] ) 
            { 
                $current_is_unique = false; 
                break; 
            } 
        } 
        if ( $current_is_unique ) 
        { 
            $to_return[$current_index] = $array[$i];
        } 

    } 

    return $to_return; 
}

ولكن عند قياس هذا ضد array_unique حصلت على النتيجة التالية:

اختبار (array_unique2)...استغرقت العملية 0.52146291732788 ثانية.

اختبار (array_unique)...استغرقت العملية 0.28323101997375 ثانية.

مما يجعل array_unique أسرع مرتين، سؤالي هو، لماذا (كلاهما لهما نفس البيانات العشوائية)؟

و كتب لي أحد الأصدقاء ما يلي:

function array_unique2($a)
{
    $n = array();
    foreach ($a as $k=>$v)
        if (!in_array($v,$n))
            $n[$k]=$v;
    return $n;
}

وهو أسرع مرتين من المدمج في php.

أود أن أعرف، لماذا؟

ما هو التعقيد الزمني لـ array_unique و in_array؟

يحررلقد قمت بإزالة العد ($array) من كلتا الحلقتين واستخدمت للتو متغيرًا في الجزء العلوي من الوظيفة، والذي اكتسب ثانيتين على 100000 عنصر!

Answer 1

على الرغم من أنني لا أستطيع التحدث عن وظيفة array_unique الأصلية، إلا أنني أستطيع أن أخبرك أن خوارزمية أصدقائك أسرع للأسباب التالية:

1. إنه يستخدم حلقة foreach واحدة بدلاً من حلقة for() المزدوجة.
2. تميل حلقات Foreach إلى الأداء بشكل أسرع من حلقات foreach في PHP.
3. لقد استخدم كلمة if(!) مقارنة أثناء استخدام بنيتين if()
4. استدعاء الوظيفة الإضافية الوحيد الذي أجراه صديقك كان in_array بينما اتصلت بـ count() مرتين.
5. لقد قدمت ثلاثة إعلانات متغيرة لم يكن على صديقك القيام بها ($a، $current_is_unique، $current_index)

على الرغم من أن أيًا من هذه العوامل وحدها ليس كبيرًا، إلا أنني أستطيع أن أرى أين التأثير التراكمي الذي سيجعل الخوارزمية الخاصة بك تستغرق وقتًا أطول من أصدقائك.

Answer 2

التعقيد الزمني in_array() يكون على).ولرؤية ذلك، سنلقي نظرة على PHP كود المصدر.

ال in_array() يتم تنفيذ الوظيفة في ext/standard/array.c.كل ما يفعله هو الاتصال php_search_array(), ، والذي يحتوي على الحلقة التالية:

while (zend_hash_get_current_data_ex(target_hash, (void **)&entry, &pos) == SUCCESS) {

    // checking the value...

    zend_hash_move_forward_ex(target_hash, &pos);
}

ومن هنا تأتي الخاصية الخطية.

هذه هي الخاصية العامة للخوارزمية، لأن zend_hash_move_forward_ex() لديه سلوك ثابت:انظر الى Zend/zend_hash.c, ، نرى أنه في الأساس مجرد

*current = (*current)->pListNext;

---

أما بالنسبة للتعقيد الزمني array_unique():

• أولاً، سيتم إنشاء نسخة من المصفوفة، وهي عملية باستخدام خطي صفة مميزة
• ثم، مجموعة C من struct bucketindex سيتم إنشاؤه وسيتم وضع المؤشرات في نسخة المصفوفة الخاصة بنا في هذه المجموعات - خطي مميزة مرة أخرى
• ثم، bucketindex-سيتم فرز المصفوفة باستخدام الفرز السريع - ن log ن في المتوسط
• وأخيرًا، سيتم السير على المصفوفة التي تم فرزها وستتم إزالة الإدخالات المكررة من نسخة المصفوفة الخاصة بنا - يجب أن يكون هذا خطي مرة أخرى، بافتراض أن الحذف من المصفوفة لدينا هو عملية زمنية ثابتة

أتمنى أن يساعدك هذا ؛)

Answer 3

جرب هذه الخوارزمية.إنه يستفيد من حقيقة أن البحث عن المفتاح أسرع من in_array():

function array_unique_mine($A) {
    $keys = Array();
    $values = Array();
    foreach ($A as $k => $v) {
        if (!array_key_exists($v, $values)) {
            $keys[] = $k;
            $values[$v] = $v;
        }
    }
    return array_combine($keys, $values);
}

Answer 4

غابرييل إجابة لديه بعض النقاط الرائعة حول سبب تفوق طريقة صديقك على طريقتك.مفتون بالمحادثة التالية كريستوف إجابة, قررت إجراء بعض الاختبارات بنفسي.

لقد جربت ذلك أيضًا بأطوال مختلفة من السلاسل العشوائية وعلى الرغم من أن النتائج كانت مختلفة، إلا أن الترتيب كان هو نفسه.لقد استخدمت 6 أحرف في هذا المثال للإيجاز.

لاحظ أن array_unique5 يحتوي فعليًا على نفس المفاتيح الأصلية، 2 و3، ولكنه يُخرج فقط بترتيب مختلف.

نتائج...

Testing 10000 array items of data over 1000 iterations:
array_unique6:  1.7561039924622 array ( 9998 => 'b',    9992 => 'a',    9994 => 'f',    9997 => 'e',    9993 => 'c',    9999 => 'd',    )
array_unique4:  1.8798060417175 array ( 0 => 'b',   1 => 'a',   2 => 'f',   3 => 'e',   4 => 'c',   5 => 'd',   )
array_unique5:  7.5023629665375 array ( 10 => 'd',  0 => 'b',   3 => 'e',   2 => 'f',   9 => 'c',   1 => 'a',   )
array_unique3:  11.356487989426 array ( 0 => 'b',   1 => 'a',   2 => 'f',   3 => 'e',   9 => 'c',   10 => 'd',  )
array_unique:   22.535032987595 array ( 0 => 'b',   1 => 'a',   2 => 'f',   3 => 'e',   9 => 'c',   10 => 'd',  )
array_unique2:  62.107122898102 array ( 0 => 'b',   1 => 'a',   2 => 'f',   3 => 'e',   9 => 'c',   10 => 'd',  )
array_unique7:  71.557286024094 array ( 0 => 'b',   1 => 'a',   2 => 'f',   3 => 'e',   9 => 'c',   10 => 'd',  )

و الكود...

set_time_limit(0);
define('HASH_TIMES', 1000);

header('Content-Type: text/plain');

$aInput  = array();
for ($i = 0; $i < 10000; $i++) {
    array_push($aInput, chr(rand(97, 102)));
}

function array_unique2($a) {
    $n = array();
    foreach ($a as $k=>$v)
        if (!in_array($v,$n))
            $n[$k]=$v;
    return $n;
}

function array_unique3($aOriginal) {
    $aUnique = array();

    foreach ($aOriginal as $sKey => $sValue) {
        if (!isset($aUnique[$sValue])) {
            $aUnique[$sValue] = $sKey;
        }
    }

    return array_flip($aUnique);
}

function array_unique4($aOriginal) {
    return array_keys(array_flip($aOriginal));
}

function array_unique5($aOriginal) {
    return array_flip(array_flip(array_reverse($aOriginal, true)));
}

function array_unique6($aOriginal) {
    return array_flip(array_flip($aOriginal));
}

function array_unique7($A) {
    $keys = Array();
    $values = Array();
    foreach ($A as $k => $v) {
        if (!array_key_exists($v, $values)) {
            $keys[] = $k;
            $values[$v] = $v;
        }
    }
    return array_combine($keys, $values);
}

function showResults($sMethod, $fTime, $aInput) {
    echo $sMethod . ":\t" . $fTime . "\t" . implode("\t", array_map('trim', explode("\n", var_export(call_user_func($sMethod, $aInput), 1)))) . "\n";
}

echo 'Testing ' . (count($aInput)) . ' array items of data over ' . HASH_TIMES . " iterations:\n";

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique($aInput);
$aResults['array_unique'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique2($aInput);
$aResults['array_unique2'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique3($aInput);
$aResults['array_unique3'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique4($aInput);
$aResults['array_unique4'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique5($aInput);
$aResults['array_unique5'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique6($aInput);
$aResults['array_unique6'] = microtime(1) - $fTime;

$fTime = microtime(1);
for ($i = 0; $i < HASH_TIMES; $i++) array_unique7($aInput);
$aResults['array_unique7'] = microtime(1) - $fTime;

asort($aResults, SORT_NUMERIC);
foreach ($aResults as $sMethod => $fTime) {
    showResults($sMethod, $fTime, $aInput);
}

النتائج باستخدام كريستوف مجموعة البيانات من التعليقات:

$aInput = array(); for($i = 0; $i < 1000; ++$i) $aInput[$i] = $i; for($i = 500; $i < 700; ++$i) $aInput[10000 + $i] = $i;

Testing 1200 array items of data over 1000 iterations:
array_unique6:  0.83235597610474
array_unique4:  0.84050011634827
array_unique5:  1.1954448223114
array_unique3:  2.2937450408936
array_unique7:  8.4412341117859
array_unique:   15.225166797638
array_unique2:  48.685120105743

Answer 5

يتم تنفيذ صفائف PHP كجداول التجزئة، أي.تختلف خصائص أدائها عما تتوقعه من المصفوفات "الحقيقية".بالإضافة إلى ذلك، يتم تخزين أزواج القيمة الرئيسية للمصفوفة في قائمة مرتبطة للسماح بالتكرار السريع.

وهذا ما يفسر سبب بطء تنفيذك مقارنة بتنفيذ صديقك:بالنسبة لكل فهرس رقمي، يجب أن تقوم الخوارزمية الخاصة بك بإجراء بحث في جدول التجزئة، في حين أن أ foreach()سيتم تكرار -loop عبر قائمة مرتبطة.

يستخدم التنفيذ التالي جدول تجزئة عكسي وقد يكون الأسرع بين الجميع (التقليب المزدوج من باب المجاملة joe_mucchiello):

function array_unique2($array) {
    return array_flip(array_flip($array));
}

لن ينجح هذا إلا إذا كانت قيم $array هي مفاتيح صالحة، أي الأعداد الصحيحة أو السلاسل.

لقد قمت أيضًا بإعادة تنفيذ الخوارزمية الخاصة بك باستخدام foreach()-الحلقات.الآن، سيكون في الواقع أسرع من الحل الخاص بصديقك بالنسبة لمجموعات البيانات الصغيرة، ولكنه لا يزال أبطأ من الحل عبر array_flip():

function array_unique3($array) {
    $unique_array = array();

    foreach($array as $current_key => $current_value) {
        foreach($unique_array as $old_value) {
            if($current_value === $old_value)
                continue 2;
        }
        $unique_array[$current_key] = $current_value;
    }

    return $unique_array;
}

بالنسبة لمجموعات البيانات الكبيرة، الإصدار المدمج array_unique() سوف يتفوق على جميع الآخرين باستثناء التقليب المزدوج.أيضا، الإصدار باستخدام in_array() بواسطة صديقك سيكون أسرع من array_unique3().

كي تختصر:الكود الأصلي للفوز!

---

إصدار آخر يجب أن يحافظ على المفاتيح وترتيبها:

function array_flop($array) {
    $flopped_array = array();

    foreach($array as $key => $value) {
        if(!isset($flopped_array[$value]))
            $flopped_array[$value] = $key;
    }

    return $flopped_array;
}

function array_unique4($array) {
    return array_flip(array_flop($array));
}

هذا في الواقع enobrev'س array_unique3() - لم أتحقق من تنفيذاته بدقة كما ينبغي...

Answer 6

PHP أبطأ في التنفيذ من كود الآلة الخام (الذي يتم تنفيذه على الأرجح بواسطة array_unique).

تعتبر وظيفة المثال الثاني (التي كتبها صديقك) مثيرة للاهتمام.لا أرى كيف سيكون أسرع من التطبيق الأصلي، إلا إذا كان التطبيق الأصلي يزيل العناصر بدلاً من بناء مصفوفة جديدة.

Answer 7

سأعترف بأنني لا أفهم الكود الأصلي جيدًا، ولكن يبدو أنه ينسخ المصفوفة بأكملها، ويفرزها، ثم يكررها لإزالة التكرارات.في هذه الحالة، الجزء الثاني من التعليمات البرمجية الخاص بك هو في الواقع خوارزمية أكثر كفاءة، نظرًا لأن الإضافة إلى نهاية المصفوفة أرخص من الحذف من منتصفها.

ضع في اعتبارك أن مطوري PHP ربما كان لديهم سبب وجيه للقيام بذلك بالطريقة التي يقومون بها.هل يريد أحد أن يسألهم؟

Answer 8

وظيفة PHP الأصلية array_unique يكون تم تنفيذها في C.وبالتالي فهو أسرع من PHP، ويجب ترجمته أولاً.علاوة على ذلك، تستخدم PHP خوارزمية مختلفة عما تستخدمه أنت.كما أرى، PHP يستخدم لأول مرة فرز سريع لفرز العناصر ثم حذف التكرارات في عملية واحدة.

لماذا تنفيذ صديقه أسرع له؟لأنه يستخدم المزيد من الوظائف المضمنة التي تحاول إعادة إنشائها.