Array / Zahlen vergleichen - Lösungsansatz

nuts

Hi Leute ich bräuchte man eine schlaue Idee wie ich mein folgendes Problem lösen kann (Pseudo-Code oder Hinweis reicht hoffentlich).

Ich habe 2 1D Arrays (unterschiedlich groß) jeweils gefüllt mit verschiedenen Zahlen.
z.B.
Array1=[10, 20, 20, 100, 100, 100, 100]
Array2=[20, 20, 100, 100, 50]

Gesucht werden jetzt alle Zahlen, die in einem Array vorkommen, aber im anderen Array nicht vorhanden sind.

Im Beispiel wäre das gewünschte Ergebnis: 10, 100, 100, 50
Zahlen können durchaus mehrfach vorkommen und da im Beispiel die "100" viermal in Array1 und nur zweimal in Array2 vorhanden ist, gehört die "100" zweimal zum gewünschten output.

Ich hoffe ich habs halbwegs verständlich dargestellt. Also gesucht werden alle Zahlen für die sich kein Paar im anderen Array finden lässt.
Ich loop hier ohne Plan durch die Arrays und krieg kein vernünftiges Ergebnis raus.

Danke & Gruß

nuts

**Oscar**

Hier mal mein Versuch:

AutoIt

#include <Array.au3>
Global $Array1 = [10, 20, 20, 100, 100, 100, 100]
Global $Array2 = [20, 20, 100, 100, 50]


For $i = UBound($Array1) - 1 To 0 Step -1
	For $j = UBound($Array2) - 1 To 0 Step -1
		If $Array1[$i] = $Array2[$j] Then
			_ArrayDelete($Array1, $i)
			_ArrayDelete($Array2, $j)
			ExitLoop
		EndIf
	Next
Next


_ArrayConcatenate($Array1, $Array2)
_ArrayDisplay($Array1)

Alles anzeigen

**Kanashius**

Wenn ich dich richtig verstanden habe: Alle die in beiden sind entfernen (Je vorkommen 1x), rest zusammenfügen, dann ist das hier, was du haben möchtest:
Ist etwas Komplexer, müsste aber schneller sein, als das von Oscar (nur bei großen Datenmengen nützlicher)

AutoIt

#include <array.au3>


local $Array1=[10, 20, 20, 100, 100, 100, 100]
local $Array2=[20, 20, 100, 100, 50]
$arRes=getAr($Array1,$Array2)
_ArrayDisplay($arRes)


Func getAr(ByRef $Array1, ByRef $Array2)
	local $arResult[ubound($Array1)+ubound($Array2)]
	local $count=0
	for $i=0 to UBound($Array2)-1 step 1
		local $found=false
		for $j=0 to UBound($Array1)-1 step 1
			if $Array1[$j]=$Array2[$i] then
				$found=true
				$Array1[$j]="d"
				ExitLoop
			EndIf
		next
		if $found then
			$Array2[$i]="d"
		endif
	next
	for $i=0 to UBound($Array1)-1 step 1
		if $Array1[$i]<>"d" then
			$arResult[$count]=$Array1[$i]
			$count+=1
		endif
	next
	for $i=0 to UBound($Array2)-1 step 1
		if $Array2[$i]<>"d" then
			$arResult[$count]=$Array2[$i]
			$count+=1
		endif
	next
	ReDim $arResult[$count]
	return $arResult
EndFunc

Alles anzeigen

Edit: Wenn die beiden Eingabe-Arrays später noch gebraucht werden, sollte das ByRef beim Aufruf rausgenommen werden. Sonst könnte durchaus witziges passieren

MfG Kanashius

nuts

Das ging ja fix, danke.

Auf Geschwindigkeit kommt es zum Glück nicht wirklich an und daher sind die _Array Schweinereien wohl akzeptabel.
Eigentlich wollt ich ohne auskommen, aber daran bin ich gescheitert.

eidt\ Ah noch eine Lösung. Werds mir anschauen, danke Kanashius!

**autoBert**

in Pseudocode tue ich mich schwer, also gleich AutoIt:

Code

#include <Array.au3>


Dim $Array1[]=[10, 20, 20, 100, 100, 100, 100]
Dim $Array2[]=[20, 20, 100, 100, 50]


For $i=UBound($Array2) -1 to 0 Step -1
	$iFound=_ArraySearch($Array1,$Array2[$i])
	ConsoleWrite($i&': '&$iFound&@CRLF)
	If $iFound <> -1 Then
		_ArrayDelete($Array1,$iFound)
		_ArrayDelete($Array2,$i)
	EndIf
Next
_ArrayConcatenate($Array1,$Array2)
_ArraySort($Array1)
_ArrayDisplay($Array1)

Alles anzeigen

idealerweise sollte immer durch das kleinere Array gelaufen werden

**Xorianator**

@Oscar na, so eine Lösung ist doch aber in besser als |A1| * |A2| (Worst-Case) zu realisieren

Hier mal die Realisierung in n*log n Laufzeit:

AutoIt

#include <Array.au3>
Global $Array1 = [10, 20, 20, 100, 100, 100, 100]
Global $Array2 = [20, 20, 100, 100, 50]
Local $arr = _GiveArrayWithSingleElements($Array1, $Array2)
_ArrayDisplay($arr)
Func _GiveArrayWithSingleElements($aCompare1, $aCompare2)
	;Sicherstellen, dass $aCompare1 das größere Array ist
	If (UBound($aCompare1) < UBound($aCompare2)) Then
		Return _GiveArrayWithSingleElements($aCompare2, $aCompare1)
	EndIf
	_ArraySort($aCompare1)	;O(|A1|*log |A1|) ||
	_ArraySort($aCompare2)	;O(|A2|*log |A2|) <=> O(n*log n)
	Local $elemCounter1 = 0
	Local $elemCounter2 = 0
	Local $AList = ObjCreate("System.Collections.ArrayList") ; Um die Laufzeit von _ArrayAdd zu umgehen
	While (($elemCounter1 < UBound($aCompare1)) and ($elemCounter2 < UBound($aCompare2))); O(|A1| + |A2|) <=> O(n)
		;Element wird nur genau dann eingefügt, wenn es echt kleiner ist.
		If $aCompare1[$elemCounter1] < $aCompare2[$elemCounter2] Then
			$AList.add($aCompare1[$elemCounter1])
			$elemCounter1 += 1
			ContinueLoop
		EndIf
		If $aCompare2[$elemCounter2] < $aCompare1[$elemCounter1] Then
			$AList.add($aCompare2[$elemCounter2])
			$elemCounter2 += 1
			ContinueLoop
		EndIf
		$elemCounter1 += 1
		$elemCounter2 += 1
	WEnd


	For $i = $elemCounter1 to UBound($aCompare1) - 1 Step 1; O(|A1| - |A2|) <=> O(n)
		$AList.add($aCompare1[$i])
	Next
	;Summe: O(n * log n + n) <=> O(n * log n)
	Return $AList.ToArray
EndFunc   ;==>_GiveArrayWithSingleElements

Alles anzeigen

€: Um an solchen Stellen "Array Schweinereien" zu vermeiden hat @AspirinJunkie mal einen super Thread gepostet, in dem er die Implementierung von "alternativen" (sollten eigentlich auch mal AutoIt nativ werden, will z.B. Listen (wie hier genutzt) nicht missen) aufzeigt: Hier zu finden.

€2: Ich sehe gerade, dass das "gewünschte Ergebnis" unsortiert sein soll. Ist es ein Problem, wenn es sortiert ist? Für unsortiert würde mir auch keine bessere Lösung als das von Oscar einfallen, sofern die Reihenfolge eine Rolle spielt.

**Oscar**

Wenn es sich um große Arrays handelt und um _ArrayDelete zu umgehen, könnte man auch so vorgehen:

AutoIt

#include <Array.au3>
Global $Array1 = [10, 20, 20, 100, 100, 100, 100]
Global $Array2 = [20, 20, 100, 100, 50]




For $i = UBound($Array1) - 1 To 0 Step -1
	For $j = UBound($Array2) - 1 To 0 Step -1
		If $Array1[$i] = $Array2[$j] Then
			$Array1[$i] = -1
			$Array2[$j] = -1
			ExitLoop
		EndIf
	Next
Next


_ArrayConcatenate($Array1, $Array2)
Global $sResult = ""
For $val In $Array1
	If $val <> -1 Then $sResult &= $val & '|'
Next
Global $aResult = StringSplit(StringTrimRight($sResult, 1), '|', 2)
_ArrayDisplay($aResult)

Alles anzeigen

**AspirinJunkie**

Oha jetzt wird hier schon auf Laufzeitverhaltensebene diskutiert.

Auch wenn ich mal wieder viel zu spät bin mal meine Idee dazu in den Raum geworfen (sollte ein lineares Laufzeitverhalten aufweisen wenn ich mich nicht irre):

AutoIt

#include <Array.au3>


Global $Array1 = [10, 20, 20, 100, 100, 100, 100]
Global $Array2 = [20, 20, 100, 100, 50]


$a_Diff = _getArrDiffs($Array1, $Array2)
_ArrayDisplay($a_Diff)




Func _getArrDiffs(ByRef $A, ByRef $B)
	Local $dic_A = ObjCreate("Scripting.Dictionary"), $dic_B = ObjCreate("Scripting.Dictionary")


	For $i In $A
		$dic_A($i) += 1
	Next
	For $i In $B
		$dic_B($i) += 1
	Next


	Local $aRet[UBound($A) + UBound($B)], $j = 0, $dA, $dB, $dDiff


	For $i In $dic_A.Keys
		If Not $dic_B.Exists($i) Then
			$aRet[$j] = $i
			$j += 1
		Else
			$dA = $dic_A($i)
			$dDiff = $dic_B($i) - $dA
			If $dDiff > 0 Then
				For $y = 1 To $dDiff
					$aRet[$j] = $i
					$j += 1
				Next
			EndIf
		EndIf
	Next


	For $i In $dic_B.Keys
		If Not $dic_A.Exists($i) Then
			$aRet[$j] = $i
			$j += 1
		Else
			$dB = $dic_B($i)
			$dDiff = $dic_A($i) - $dB
			If $dDiff > 0 Then
				For $y = 1 To $dDiff
					$aRet[$j] = $i
					$j += 1
				Next
			EndIf
		EndIf
	Next


	ReDim $aRet[$j]
	Return $aRet
EndFunc   ;==>_getArrDiffs

Alles anzeigen

4ern

[Blockierte Grafik: http://i1.kym-cdn.com/photos/images/newsfeed/000/353/279/e31.jpg]

**Xorianator**

@AspirinJunkie sehr schöne Idee, auf das Dictionary hätte ich auch kommen können, in dem Beispiel nehmen wir uns aber (meines Blickes nach) nichts. €: Von der Laufzeit der gezählten Schritte her. Aber offensichtlich scheine ich doch zu irren, nach den Messungen. Dass die Operationen wesentlich schneller sind, darüber sei mal hinweg zu sehen.
In dem Dictionary können wir das suchen in maximal O(log n) realisieren, wenn mich nicht alles täuscht.
Das führt dazu, dass du mit Zeile 23 |A1| * log(|A2|) und durch Zeile 39 |A2| * log(|A1|) hast, oder irre ich? (Was dann letztendlich dem _ArraySort mit Quicksort gleich kommt))

€: Hussa! Das nenne ich mal eine Zeit, nicht schlecht, ich ziehe den Hut vor der Geschwindigkeitsverbesserung. Deshalb an der Stelle die Frage: Wie schnell wird in dem Dictionary gesucht? Ich meine eine der schnellsten Datenstrukturen sei der Rot-Schwarz Baum, mit dem wir alles in O(log n) erledigen können.

Hab mal ne Messung angestellt:

€: Ich würde auch aufgrund von 8 Elementen und entsprechendem Ergebnis auf logarithmische Laufzeit tippen.

Spoiler anzeigen

Zitat

-----------
--Number 1-
-----------
Elements: 8
Xor: 10.5658792977436
Asp: 67.8625966069013
-----------
--Number 2-
-----------
Elements: 16
Xor: 0.657471192871694
Asp: 0.716562738115602
-----------
--Number 3-
-----------
Elements: 32
Xor: 1.17623275848663
Asp: 0.874865877742703
-----------
--Number 4-
-----------
Elements: 64
Xor: 2.41591117607725
Asp: 1.31089928001617
-----------
--Number 5-
-----------
Elements: 128
Xor: 4.94751737757942
Asp: 1.98267684699955
-----------
--Number 6-
-----------
Elements: 256
Xor: 10.2915701245588
Asp: 3.13496197925576
-----------
--Number 7-
-----------
Elements: 512
Xor: 21.8427231872113
Asp: 5.43020199978229
-----------
--Number 8-
-----------
Elements: 1024
Xor: 45.6643911238279
Asp: 9.91898238138927
-----------
--Number 9-
-----------
Elements: 2048
Xor: 94.6173822445457
Asp: 19.3303994899467
-----------
--Number 10-
-----------
Elements: 4096
Xor: 193.926633181458
Asp: 38.4782372059029
-----------
--Number 11-
-----------
Elements: 8192
Xor: 401.415398012658
Asp: 76.0281151352108
-----------
--Number 12-
-----------
Elements: 16384
Xor: 833.981059604709
Asp: 147.083832242213
-----------
--Number 13-
-----------
Elements: 32768
Xor: 1688.83822911969
Asp: 306.411121650831
-----------
--Number 14-
-----------
Elements: 65536
Xor: 3428.61616931283
Asp: 641.712721787675
-----------
--Number 15-
-----------
Elements: 131072
Xor: 7189.7155830625
Asp: 1440.26933304306
-----------
--Number 16-
-----------
Elements: 262144
Xor: 13762.3686379399
Asp: 2984.48504828401
-----------
--Number 17-
-----------
Elements: 524288
Xor: 27665.1453185501
Asp: 5371.01435302533
-----------
--Number 18-
-----------
Elements: 1048576
Xor: 55728.8783491688
Asp: 8498.24840219572
-----------
--Number 19-
-----------
Elements: 2097152
Xor: 111908.34839131
Asp: 13437.5063367907
-----------
--Number 20-
-----------
Elements: 4194304
Xor: 225666.373178659
Asp: 25571.1322251077

Alles anzeigen

**AspirinJunkie**

Zitat von Xorianator

Das führt dazu, dass du mit Zeile 23 |A1| * log(|A2|) und durch Zeile 39 |A2| * log(|A1|) hast, oder irre ich? (Was dann letztendlich dem _ArraySort mit Quicksort gleich kommt))

Ne eigentlich nicht. Ein Dictionary sollte durch die Indexberechnung per Hash für das Suchen in ihr ein Laufzeitverhalten von O(1) haben. Zumindestens in der Theorie. Also komplett unabhängig von der Größe des Dictionaries.

Hier mal ein kleines Testskript welches Messwerte für Excel raushaut (damit man sich das mal grafisch darstellen kann):

AutoIt

#include <Array.au3>


For $N = 1000 To 10000 Step 100
$iT = TimerInit()
;~ Global $N = 1e2
Global $Array1[$N], $Array2[$N]


For $i = 0 To $N -1
	$Array1[$i] = Random(1, $N / 20, 1)
	$Array2[$i] = Random(1, $N / 10, 1)
Next


$a_Diff = _getArrDiffs($Array1, $Array2)
ConsoleWrite($N & @TAB & StringReplace(TimerDiff($iT), ".", ",") & @CRLF)
Next




Func _getArrDiffs(ByRef $A, ByRef $B)
	Local $dic_A = ObjCreate("Scripting.Dictionary"), $dic_B = ObjCreate("Scripting.Dictionary")


	For $i In $A
		$dic_A($i) += 1
	Next
	For $i In $B
		$dic_B($i) += 1
	Next


	Local $aRet[UBound($A) + UBound($B)], $j = 0, $dA, $dB, $dDiff


	For $i In $dic_A.Keys
		If Not $dic_B.Exists($i) Then
			$aRet[$j] = $i
			$j += 1
		Else
			$dA = $dic_A($i)
			$dDiff = $dic_B($i) - $dA
			If $dDiff > 0 Then
				For $y = 1 To $dDiff
					$aRet[$j] = $i
					$j += 1
				Next
			EndIf
		EndIf
	Next


	For $i In $dic_B.Keys
		If Not $dic_A.Exists($i) Then
			$aRet[$j] = $i
			$j += 1
		Else
			$dB = $dic_B($i)
			$dDiff = $dic_A($i) - $dB
			If $dDiff > 0 Then
				For $y = 1 To $dDiff
					$aRet[$j] = $i
					$j += 1
				Next
			EndIf
		EndIf
	Next


	ReDim $aRet[$j]
	Return $aRet
EndFunc   ;==>_getArrDiffs

Alles anzeigen

Komme bei einer linearen Regression darauf auf ein R² von 0.989. Also wirklich lineares Laufzeitverhalten.

**Xorianator**

Zitat von AspirinJunkie

Ne eigentlich nicht. für das Suchen in ihr ein Laufzeitverhalten von O(1) haben. Zumindestens in der Theorie. Also komplett unabhängig von der Größe des Dictionaries.

Ha, stimmt, da gabs ja etwas das in O(1) alles findet.
Wir haben Hashtabellen leider so rudimentär angerissen, dass die mir nicht mal in den Sinn kamen. Ja klar, du hast völlig Recht. Ich sollte mich wohl privat mit Hashtabellen auseinander setzen. Danke dir!

**Oscar**

Es gibt noch eine Möglichkeit und zwar mit Strings.
Die StringReplace-Funktion ist ja auch recht schnell und so braucht man nur die äußere Schleife:

AutoIt

#include <Array.au3>
Global $Array1 = [10, 20, 20, 30, 30, 100, 100, 100, 100, 80, 60]
Global $Array2 = [5, 30, 20, 20, 100, 100, 50, 60, 80, 50]
Global $iTimer = TimerInit()
Global $s1 = _ArrayToString($Array1, ' '), $s2 = ' '
For $val In $Array2
	$s1 = StringReplace($s1, String($val), '', 1)
	If Not @extended Then $s2 &= $val & ' '
Next
$s1 = StringStripWS($s1 & $s2, 7)
Global $aResult = StringSplit($s1, ' ', 2)
ConsoleWrite(TimerDiff($iTimer) & @CR)
_ArrayDisplay($aResult)

Alles anzeigen

**Xorianator**

@Oscar bleibt bei |A1| * |A2|

Zitat

-----------
--Number 1-
-----------
Elements: 8
Xor: 12.7012611379788
Osc: 0.109474862767661
-----------
--Number 2-
-----------
Elements: 16
Xor: 0.654050103410204
Osc: 0.127513334473697
-----------
--Number 3-
-----------
Elements: 32
Xor: 1.08510737555787
Osc: 0.297323775016717
-----------
--Number 4-
-----------
Elements: 64
Xor: 2.34033619979162
Osc: 0.835989861134869
-----------
--Number 5-
-----------
Elements: 128
Xor: 4.77584088823923
Osc: 2.69146438179358
-----------
--Number 6-
-----------
Elements: 256
Xor: 9.90871911300481
Osc: 9.7062528185112
-----------
--Number 7-
-----------
Elements: 512
Xor: 21.4303264030354
Osc: 38.0991182919433
-----------
--Number 8-
-----------
Elements: 1024
Xor: 50.8787534794035
Osc: 143.037927441803
-----------
--Number 9-
-----------
Elements: 2048
Xor: 99.5801390206354
Osc: 574.294244794501
-----------
--Number 10-
-----------
Elements: 4096
Xor: 194.368575738256
Osc: 2145.83420156437
-----------
--Number 11-
-----------
Elements: 8192
Xor: 409.835010185516
Osc: 8366.30693392632
-----------
--Number 12-
-----------
Elements: 16384
Xor: 868.587867572737
Osc: 31049.3716080676

Alles anzeigen

nuts

Problem ist auf jeden Fall gelöst, danke für die vielen Hinweise und Skripte.

P.S. Das Thema auf *gelöst* setzen geht nicht mehr oder?

**Xorianator**

Doch, sollte noch gehen.

nuts

Habs geschafft.

Dürft aber natürlich gern weiterdiskutieren.