Question

Tamam, bu "php benim diziden çiftleri kaldırmak için nasıl" veya "tüm uniques nasıl" bir soru değildir. Bu zaman karmaşıklığı hakkında bir soru.

Ben array_unique biraz O (n ^ 2 - n) olduğunu düşündüm ve burada benim uygulaması bulunuyor:

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

Karşı bu kıyaslama Ancak array_unique i şu sonuç var:

Test (array_unique2) ... Operasyon ,52146291732788 s aldı.

Test (array_unique) ... Operasyon ,28323101997375 s aldı.

Hangi array_unique iki kat hızlı yapar, benim sorum, neden (Her ikisi de aynı rasgele veri vardı)?

Ve bir arkadaşım şöyle yazmıştı:

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

iki kat daha hızlı php birinde yerleşik olarak hangi.

Ben bilmek istiyorum, neden?

Array_unique ve İn_Array zaman karmaşıklığı nedir?

Edit I removed the count($array) from both loops and just used a variable in the top of the function, that gained 2 seconds on 100 000 elements!

Answer 1

Ben yerli array_unique işlevi için konuşamıyor, ben senin arkadaş algoritma daha hızlı olduğunu söyleyebilirim, çünkü:

O () döngü için double aksine tek bir foreach döngü kullanır.
Foreach döngüsü PHP döngüler için daha hızlı gerçekleştirmek için eğilimindedir.
Eğer () yapılar ise iki kullanılır ise o bir tek if (!) Karşılaştırma kullanılır
Sadece ek fonksiyon arkadaş aramak iki kez () Eğer sayım denir oysa in_array'in oldu yaptı.
Eğer arkadaşınız ($ a, $ current_is_unique, $ current_index) yoktu, üç değişken demeçleri

Yalnız bu faktörlerin hiçbiri büyük iken, ben kümülatif etkisi Algoritmanızın arkadaşlarınızla daha uzun sürer yapacak nerede görebilirsiniz.

Answer 2

in_array() dir zaman karmaşıklığı O(n). Bunu görmek için, PHP source code bir göz atacağız.

in_array() function ext/standard/array.c uygulanmaktadır. Bütün yaptığı aşağıdaki döngü içeren çağrı php_search_array(), bir:

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

    // checking the value...

    zend_hash_move_forward_ex(target_hash, &pos);
}

Doğrusal karakteristik nereden geldiğini budur.

zend_hash_move_forward_ex() sabit davranış vardır becaus Bu, algoritmanın genel özelliğidir: Zend/zend_hash.c, biz sadece temelde olduğunu görmek baktığımızda

*current = (*current)->pListNext;

Zaman karmaşıklığı gibi array_unique():

ilk olarak, dizinin bir kopyasını linear karakteristik bir işlemdir ki, oluşturulacak
sonra, struct bucketindex oluşturulan ve bizim dizinin kopya içine işaretçileri olacak bir C dizi bu kova koymak olacak - linear karakteristik tekrar
sonra, bucketindex-dizi usign quicksort sıralanmış olacak - n log n ortalama

ve son olarak, sıralanan dizi yürüdü olacak ve ve yinelenen girişleri bizim dizinin kopya silinecektir - Bu linear Yine, bizim diziden silinmesinin varsayarak bir sabit zamanlı operasyon olduğunu olmalı

Bu yardımcı olur umarım ;)

Answer 3

Bu algoritma deneyin. Bu anahtar arama İn_Array daha hızlı olduğu gerçeğinden yararlanır ():

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

Gabriel's answer arkadaşınızın yöntemi seninkini yener neden bazı büyük noktaları vardır. Aşağıdaki konuşma ilgisini Christoph's answer, benim kendi bazı testler verdi.

Ayrıca, rastgele dizeleri farklı uzunlukları ile bu denenmiş ve sonuç farklı olmasına rağmen, emir aynıydı. I Kısa olması için, bu örnekte 6 karakter kullanılabilir.

Aslında array_unique5 Bildirimi yerli, 2 ve 3 olarak aynı tuşlara sahiptir, ama sadece farklı bir sırayla çıktılar.

Sonuçlar ...

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',	)

Ve Kod ...

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'] = micr

Answer 5

Onların performans özellikleri size 'gerçek' dizilerindeki beklediğiniz farklı yani PHP'nin diziler, karma tablo olarak uygulanmaktadır. Bir dizinin anahtar-değer çiftleri ayrıca hızlı yineleme izin bağlantılı listesinde saklanır.

Lütfen uygulama arkadaşın karşılaştırıldığında çok yavaş neden bu açıklar: foreach()-döngü sadece bir bağlantılı liste üzerinde yineleme oysa her sayısal dizin için, algoritma, bir karma tablo arama yapmak için vardır.

Aşağıdaki uygulama ters karma tablosunu kullanır ve kalabalık (* joe_mucchiello * çift-saygısız nezaket) en hızlı olabilir:

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

Değerleri $array geçerli anahtarlar, yani tamsayı veya dizeleri ise bu sadece çalışır.

Ben de foreach()-döngüler kullanarak algoritma reimplemented. Şimdi, aslında arkadaşınızın küçük veri kümeleri için daha hızlı olacaktır, fakat yoluyla çözümün hala daha yavaş 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;
}

Büyük veri kümeleri için, yerleşik sürüm array_unique() çift saygısız biri hariç diğer tüm bulunuyor geride bırakacaktır. Ayrıca, arkadaşı tarafından in_array() kullanarak sürüm array_unique3() daha hızlı olacaktır.

Özetlemek gerekirse: kazanmak için Native kod!

Tuşları ve onların sıralamasını korumanız gerektiğini Yine başka bir versiyonu:

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

Bu aslında enobrev 's array_unique3() - Ben iyice ben olması gerektiği gibi kendi uygulamaları kontrol etmedi ...

Answer 6

PHP (büyük olasılıkla array_unique tarafından yürütülür) ham makine koduna göre yürütmek için yavaştır.

Sizin ikinci örnek fonksiyonu (bir arkadaşının yazdığı) ilginç. Ben yerli bir unsurları kaldırarak yerine yeni bir dizi inşa sürece, yerli uygulama daha hızlı olacağını nasıl görmüyorum.

Answer 7

Bu çiftleri kaldırarak döngü sonra, ben çok iyi bir yerel kod anlamıyorum kabul edeceğiz, ama tüm dizi kopyalama gibi görünüyor, bu sıralamayı. Bir dizinin sonuna ekleyerek bunun ortadan silinmesi daha ucuz olduğu için bu durumda kod ikinci parçası, aslında daha verimli bir algoritma.

PHP geliştiricileri muhtemelen bunu yaptıkları şekilde yapmak için iyi bir nedeni vardı aklınızda tutun. Herkes onlara sormak isteyen var mı?

Answer 8

Doğal PHP işlevi array_unique olan implemented in C. Bu nedenle, ilk olarak tercüme edilmesi gerekir ki, PHP daha hızlıdır. Dahası, PHP yapmanız daha bir farklı bir algoritma kullanır. Gördüğüm kadarıyla, PHP ilk kullanımları Quick sort elemanlarını sıralamak ve daha sonra bir vadede çiftleri siler.

Neden arkadaşının uygulaması kendi vardır hızlıdır? Onları yeniden çalışıyor ki daha yerleşik işlevselliğini kullanır çünkü.

PHP Diziler - çiftleri çıkarın (Zaman karmaşıklığı)

8 Cevap

etiketler