Array Schnittmenge performant ermitteln

[r.pakosch]

Hallo zusammen,

ich stehe bei der Implementierung einer Kommunikationsschnittstelle vor einem interessanten Problem:

Ich möchte eine große Menge von Bytes gegen eine kleine Menge unzulässiger Bytes prüfen. Da ich mir die Große Menge (mehrere Megabyte) gebuffert von einem Server hole, habe ich zwei Byte-Arrays in der Hand. Natürlich könnte ich jedes Byte einzeln prüfen, aber ich suche nach einer CPU freundlicheren Möglichkeit.

Ich weiß, dass java.util.Collection#retainAll(Collection c) so etwas bereits kann, aber da ich hochperformant bleiben will, möchte ich auf der Array-Ebene bleiben. Auch die Arrays.binarySearch(...)-Methoden scheinen nicht das Richtige zu sein.

Ein Beispiel mit mit der Methode, die mir zu umständlich ist (bei nur einem Megabyte sind es über 30 Millionen abfragen):

public class InvalidByteChecker {

	// Die invaliden Bytes (in meinem Fall 29 Stück)
	private static byte[] _invalidBytes;
	
	public static void initInvalidBytes() {
		// _invalidBytes Array Füllen
	}
	
	// Die Methode, die für jeden geladenen Buffer aufgerufen werden soll
	public static boolean allBytesValid(byte[] pBytes2Check) {
		for (byte b2c : pBytes2Check) {
			for (byte ib : _invalidBytes) {
				// Sobald ein invalides Byte vorkommt brauche ich gar nicht
				// weiter zu machen
				if (b2c == ib)
					return false;
			}
		}
		return true;
	}
}

Ich bin gespannt auf eure Vorschläge!

Ralf

 

[SlaterB]

wie kann man sich denn die beiden byte[] vorstellen? da es nur 256 verschiedene bytes gibt, wird doch wohl eines der Arrays maximal 256 lang sein, eher noch kürzer?
zwei ganz lange Arrays zu vergleichen scheint nicht sinnvoll,

jedenfalls brauchst du ein 256er boolean-Array, darin speicherst du für ein Array an Index 20 ob byte 20 enthalten ist usw.,
dafür reicht eine Schleife über das Array

danach brauchst du noch eine Schleife über das lange Array und zu jedem byte schaust du direkt nach ob
flags[byte] true oder false ist,
wenn negative bytes Ärger machen, dann +128 rechnen für Indexe, dann im int-Bereicht statt byte

Array-Zugriffe sind natürlich auch nicht allzu performant wenn man es extrem genau nimmt,
vielleicht 256 bzw. weniger finale boolean-Variablen anlegen?..
dann bräuchte es aber if/else oder switch:
[c]if (currentByte == 12 && !is12Ok) return false;[/c]

 

[faetzminator]

Wenn die Menge der zu suchenden Bytes sortiert ist, dann ist ein Binary Search in diesem Array allenfalls performanter.

 

[r.pakosch]

wie kann man sich denn die beiden byte[] vorstellen? da es nur 256 verschiedene bytes gibt, wird doch wohl eines der Arrays maximal 256 lang sein, eher noch kürzer?
zwei ganz lange Arrays zu vergleichen scheint nicht sinnvoll,

jedenfalls brauchst du ein 256er boolean-Array, darin speicherst du für ein Array an Index 20 ob byte 20 enthalten ist usw.,
dafür reicht eine Schleife über das Array

danach brauchst du noch eine Schleife über das lange Array und zu jedem byte schaust du direkt nach ob
flags[byte] true oder false ist,
wenn negative bytes Ärger machen, dann +128 rechnen für Indexe, dann im int-Bereicht statt byte

Array-Zugriffe sind natürlich auch nicht allzu performant wenn man es extrem genau nimmt,
vielleicht 256 bzw. weniger finale boolean-Variablen anlegen?..
dann bräuchte es aber if/else oder switch:
[c]if (currentByte == 12 && !is12Ok) return false;[/c]

Ich ziehe mir über TCP/IP eine große Datenmenge (im Fall von einem MB genau 1048576 Byte). Dabei möchte ich sicherstellen, dass unter den 1048576 Bytes kein "fehlerhaftes" Byte vorkommt. Die fehlerhaften Bytes habe ich in einem anderen Array (es sind genau 29 Stück von, wie du richtig gesagt hast, insgesamt 256 UNTERSCHIEDLICHEN Bytes).

Da ich die große Datenmenge gebuffert ziehe, entstehen Byte-Arrays mit der Größe von 1000-2000.

 

[SlaterB]

dass du 1048576 mit 29 kreuzt fandest du nicht erwähnenswert sondern sprachst quasi von zwei beliebigen Arrays?

na ich bin ja auch so drauf gekommen und habe alles dazu geschrieben was zu schreiben ist,
auf die Lösung bis du noch mit keinem Wort eingegangen, es gibt also nichts neues


spätes edit: ok, die 29 standen auch im Quellcode 😉

 

[r.pakosch]

dass du 1048576 mit 29 kreuzt fandest du nicht erwähnenswert sondern sprachst quasi von zwei beliebigen Arrays?

na ich bin ja auch so drauf gekommen und habe alles dazu geschrieben was zu schreiben ist,
auf die Lösung bis du noch mit keinem Wort eingegangen, es gibt also nichts neues

Mir kommt es vor, als würden wir aneinander vorbeireden, da deine Lösung nichts mit meinem Problem zu tun hat.

Ich habe momentan meine obere Lösung implementiert (die "umständliche"), diese aber als Thread neben dem eigentlichen Download der Daten laufen. Funktioniert fast ohne Zeitverlust, da der Download mein Flaschenhals ist. Ich werde das ganze gleich mal mit Arrays.binarySearch(byte[] a, int key) probieren und schauen, ob ein Unterschied bemerkbar ist!

 

[SlaterB]

wie du meinst,
ich bin zwar der Meinung dass sie dein Problem exakt auf die performanteste, wenn auch nicht unbedingt nicht-umständlichste Weise löst,
aber das muss ich dir ja nicht verkaufen

gegenüber Download kann in der Tat ziemlich egal sein, wie du dein Verfahren noch änderst

 

[faetzminator]

Man muss natürlich anmerken, dass SlaterB's Lösungsvorschlag mit dem boolean-Array schneller sein würde. Allerdings IMHO nicht so schön. Aber das würde - wie SlaterB bereits ansatzweise sage - etwa so aussehen:

private boolean[] isInvalid = new boolean[Byte.MAX_VALUE + 1];

protected void init(byte[] invalidBytes) {
    for (byte b : invalidBytes) {
        isInvalid[b] = true;
    }
}

public boolean check(byte[] someData) {
    for (byte b : someData) {
        if (isInvalid[b]) {
            return false;
        }
    }
    return true;
}

 

[r.pakosch]

Natürlich! Das ist sogar recht gefuchst! Sorry, dass ich der Lösung zunächst nicht viel Beachtung geschenkt habe! Ich werde das so ähnlich umsetzen!