Ich habe zwei ungeordnete Integer-Arrays, und ich muss wissen, wie viele ganze Zahlen diese Arrays gemeinsam haben

Question

Ich arbeite in einer LAMP-Umgebung, so ist PHP die Sprache; Zumindest kann ich Python benutzen.

Wie der Titel sagte, habe ich zwei ungeordnete Integer-Arrays.

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

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

Ich möchte wissen, wie viele Integer diese Array gemeinsam haben; Im Beispiel sehen Sie, dass das Ergebnis 2 ist. Ich bin nicht daran interessiert, was ganze Zahlen gemeinsam haben, wie (72, 3).

Ich brauche eine schnellere Methode als jedes Element des Arrays B zu nehmen und prüfen, ob es in ist Array A (O (n · m))

Arrays durch asort sortiert werden können oder mit SQL-Ordnung (sie aus einem SQL-Ergebnis kam).

Eine Idee, die zu mir kam, ist ein ‚Vektor‘ für jedes Array zu erstellen, wobei die ganze Zahl eine Position, die Wert vorhanden bekommt 1 und ganzen Zahlen nicht 0

erhalten A Also, für Array (bei StartNr 1)

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

Das Gleiche gilt für Array B

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

und vergleichen diese zwei Vektoren mit einem Zyklus. Das Problem ist, dass auf diese Weise die Vektorlänge ungefähr 400k beträgt.

Answer 1

Der einfachste Weg wäre:

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

wenn ich verstehe, was Sie nach. Sollte schnell sein.

Answer 2

Wenn beide Arrays aus SQL stammen, könnten Sie keine SQL-Abfrage mit einem inneren Join auf den 2 Datensätzen schreiben, um Ihr Ergebnis zu erhalten?

Answer 3

Sie möchten die array_intersect() Funktion. Von dort können Sie das Ergebnis zählen. Machen Sie sich keine Gedanken über die Geschwindigkeit, bis Sie wissen, dass Sie ein Problem haben. Die eingebaute Funktion wird viel schneller ausgeführt als alles, was Sie in PHP schreiben können.

Answer 4

Ich weiß nicht viel über PHP, daher können Sie eine spezifischere Antwort von anderen erhalten, aber ich möchte Ihnen einen sprachunabhängigen Ansatz vorstellen.

Durch Überprüfung jedes Elements in A gegen jedes Element in B ist es tatsächlich O (n) [Ich nehme an, dass die Arrays hier die gleiche Länge haben, um die Gleichungen zu vereinfachen, aber die gleiche Argumentation gilt für Arrays unterschiedlicher Länge].

Wenn Sie die Daten in beiden Arrays sortieren, können Sie die Zeitkomplexität je nach gewähltem Algorithmus auf O (n log n) oder ähnliches reduzieren.

Aber Sie müssen bedenken, dass die Komplexität nur wirklich wichtig für größere Datensätze wird. Wenn diese beiden Arrays, die Sie angegeben haben, für die Größe typisch sind, würde ich sagen, dass Sie sie nicht sortieren sollen, sondern verwenden Sie einfach die Methode "alles mit allem vergleichen" - die Sortierung wird Ihnen diesbezüglich keinen ausreichenden Vorteil verschaffen. Arrays mit 50 Elementen würden Ihnen immer noch nur 2.500 Iterationen geben (ob das für PHP akzeptabel ist, ich weiß nicht, es wäre sicher Wasser für C und andere kompilierte Sprachen).

Und bevor irgendjemand herein springt und sagt, dass Sie für größere Datenmengen nur für den Fall planen sollten, ist das YAGNI, so unnötig wie eine vorzeitige Optimierung. Sie können nie brauchen es in diesem Fall haben Sie Zeit verschwendet, die woanders besser verbracht hätte. Die Zeit, das zu implementieren, wäre, wenn es ein Problem werden würde (das ist meiner Meinung nach natürlich, andere können nicht zustimmen).

Wenn die Datensätze wirklich groß genug sind, um das O (n) nicht praktikabel zu machen, denke ich, Sortierung dann durch die Arrays parallel gehen ist wahrscheinlich Ihre beste Wette. Eine andere Möglichkeit ist, wenn der Zahlenbereich nicht zu groß ist - dann ist Ihre vorgeschlagene Lösung eines Booleeschen Vektors ziemlich praktikabel, da dies O (n) wäre, indem beide Arrays durchlaufen werden, um den Vektor zu bevölkern, gefolgt von Vergleichen von feste Orte innerhalb der zwei Vektoren. Aber ich gehe davon aus, dass Ihre Reichweite zu groß ist, oder Sie hätten die 400K-Anforderung nicht bereits erwähnt. Aber auch hier wird die Größe der Datensätze entscheiden, ob es sich lohnt.

Answer 5

Abhängig von Ihren Daten (Größe) können Sie anstelle von array_intersect() array_intersect_key() verwenden. Offensichtlich verwendet die Implementierung von array_intersect (Testen von PHP 5.3) keine Optimierung/Caching/was auch immer, sondern durchläuft das Array und vergleicht die Werte eins für eins für jedes Element in Array A. Die Hashtabellensuche ist unglaublich schneller als das.

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

druckt

Array 
(
    [fnIntersect] => 11.271192073822 
    [fnFlip] => 0.54442691802979 
)

die die array_flip/intersect_key Methode bedeutet, ist ~ 20-mal schneller auf meinem Notebook. (wie üblich: das ist ein Ad-hoc-Test. Wenn Sie einen Fehler entdecken, sagen Sie mir ... Ich erwarte das ;-))

Answer 6

Ich habe eine PHP-Erweiterung geschrieben, die Funktionen für effiziente Set-Operationen wie bietet Union, Schnittpunkt, binäre Suche usw. Das interne Datenlayout ist ein gewöhnliches int32_t-Array, das in einer PHP-Zeichenfolge gespeichert ist. Operationen basieren auf Merge-Algorithmen.

Beispiel:

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

Es ist hier verfügbar: https://github.com/tuner/intarray