Ben iki sırasız tamsayı dizileri var ve ben bu diziler ortak kaç tamsayılar bilmek gerekir

6 Cevap php

Ben bir lamba bir ortamda çalışıyorum, bu yüzden PHP dilidir; en azından ben pitonu kullanabilirsiniz.

Başlığı dedi i gibi iki sırasız tamsayı diziler var.

$array_A = array(13, 4, 59, 38, 9, 69, 72, 93, 1, 3, 5)

$array_B = array(29, 72, 21, 3, 6)

Ben bu dizi ortak kaç tamsayılar bilmek istiyorum; Eğer sonuç 2 görmek gibi. örnekte I (72, 3) gibi, ortak ne tamsayılar ilgilenmiyorum.

Ben dizi B her eleman almak ve dizi A'da olmadığını kontrol daha hızlı bir yöntem gerekir (O ​​(nxm))

Diziler (onlar bir sql sonucunda geldi) asort aracılığıyla veya sql sipariş ile sıralanabilir.

Bana geldi bir fikir tamsayı değeri 1 olur ve tamsayılar 0 olsun mevcut bir pozisyon her dizi için bir 'vektör' oluşturmaktır.

Yani, dizi A (pos 1 başlayarak)

(1, 0, 1, 1, 1, 0, 0, 0, 1, 0, ...)

Dizi B için aynı

(0, 0, 1, 0, 0, 1, ...)

Sonra bir devir ile iki vektör karşılaştırın. Sorun, bu şekilde vektör uzunluğu yaklaşık 400k olmasıdır.

6 Cevap

Basit şekilde olacaktır:

count(array_intersect($array_A, $array_B));

if I understand what you're after. Should be fast.

Veri (boyut) bağlı olarak) yerine array_intersect (ve array_intersect_key() kullanmak isteyebilirsiniz. Görünüşe array_intersect (test php 5.3) uygulanması herhangi bir optimizasyon / önbelleğe / olursa olsun kullanın ama dizi aracılığıyla döngüsü ve dizi A. her eleman için tek tek hashtable'a arama daha hızlı daha inanılmaz olan değerleri karşılaştırır değildir.

<?php
function timefn($fn) {
    static $timer = array();
    if ( is_null($fn) ) {
    	return $timer;
    }
    $x = range(1, 120000);
    $y = range(2, 100000);
    foreach($y as $k=>$v) { if (0===$k%3) unset($y[$k]); }

    $s = microtime(true);
    $fn($x, $y);
    $e = microtime(true);

    @$timer[ $fn ] += $e - $s; 
}

function fnIntersect($x, $y) {
    $z = count(array_intersect($x,$y));
}

function fnFlip($x, $y) {
    $x = array_flip($x);
    $y = array_flip($y);
    $z = count(array_intersect_key($x, $y));
}


for ($i=0; $i<3; $i++) {
    timefn( 'fnIntersect' );
    timefn( 'fnFlip' );
}

print_r(timefn(null));

prints

Array
(
    [fnIntersect] => 11.271192073822
    [fnFlip] => 0.54442691802979
)
which means the array_flip/intersect_key method is ~20 times faster on my notebook. (as usual: this is an ad hoc test. If you spot an error, tell me ...I'm expecting that ;-) )

Eğer diğerlerinden daha spesifik bir cevap alabilirsiniz yüzden PHP hakkında çok şey bilmiyorum, ama ben bir daha dil agnostik yaklaşım sunmak istiyorum.

B her elemana karşı A'da her unsurunu kontrol ederek, gerçekten O (n 2) [I diziler denklemleri sadeleştirmek burada aynı uzunlukta olduğunu varsayıyorum edeceğiz ama aynı mantık dizileri için yapacak of farklı uzunlukları].

Eğer her iki dizide de verileri sıralamak olsaydı, seçtiğiniz algoritma bağlı, O (n log n) ya da benzer zaman karmaşıklığını azaltabilir.

Ama karmaşıklığı sadece gerçekten büyük veri setleri için önemli hale akılda tutmak gerekir. Bu üzerinde size yeterli bir avantaj vermez sıralama - Eğer verdiğin iki dizileri boyutu tipik olsaydı, ben sadece "her şeyi ile her şeyi karşılaştırmak" yöntemini kullanın, sıralamak değil söyleyebilirim. 50 elemanlarının diziler hala size sadece 2.500 tekrarlamalar (verecekti ki PHP kabul olsun, ben bilmiyorum, kesinlikle C ve diğer diller için derlenmiş bir ördek geri su olurdu).

Herkes atlar ve sadece durumda daha büyük veri setleri için plan gerektiğini belirtiyor önce, bu erken optimizasyonu gibi gereksiz olarak, YAGNI bulunuyor. Sen never bunu gerekebilir hangi iyi yerde harcanan olurdu vakit harcadığım durumda. Bu bir sorun (tabii ki benim fikrim, diğerleri katılmıyorum) olunca o uygulamak için zaman olacaktır.

Veri setleri gerçekten O (n 2) işlemez yapmak için yeterince büyükse, ben paralel diziler yürürken sonra sıralama muhtemelen en iyi bahis olduğunu düşünüyorum.

Sayı aralığı çok büyük değilse Bir diğer olasılık - sonra booleans vektör sizin önerilen çözüm içindeki sabit yerlerde karşılaştırmaları takip vektör doldurmak hem diziler yürürken, o O (n) olacağından oldukça uygulanabilir İki vektör. Ama senin aralığı çok büyük veya zaten 400K gereksinimi söz konusu olmazdı olduğunu varsayarak yaşıyorum. Fakat yine de, veri setlerinin büyüklüğü bunu yapmaya değer olup olmadığını belirleyecektir.

Her iki diziler SQL geldiyse, bir iç sonucunuzu almak için veri 2 takım üzerinde birleşim ile bir SQL sorgusu yazamadım?

Sen array_intersect() fonksiyonunu istiyorum. Oradan sonucu sayabilirsiniz. Eğer bir sorununuz varsa bilmek kadar hızı endişe etmeyin. Yerleşik işlev PHP yazmak mümkün olacak şey çok daha hızlı yürütmek.

Ben İç veri düzeni PHP dize depolanan sıradan bir int32_t dizi vb sendika, kavşak, ikili arama gibi verimli set işlemleri için fonksiyonları sağlayan bir PHP uzantısı yazdım. Operasyon birleştirme algoritmaları dayanmaktadır.

Örnek:

    // Create two intarrays
    $a = intarray_create_from_array(array(1, 2, 3));
    $b = intarray_create_from_array(array(3, 4, 5));
    // Get a union of them
    $u = intarray_union($a, $b);
    // Dump to screen
    intarray_dump($u);

Burada mevcut bulunuyor: https://github.com/tuner/intarray

etiketler