Array Schnittmenge performant ermitteln

r.pakosch

Mitglied
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):
Java:
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
 
S

SlaterB

Gast
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]
 
Zuletzt bearbeitet von einem Moderator:

r.pakosch

Mitglied
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.
 
S

SlaterB

Gast
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 ;)
 
Zuletzt bearbeitet von einem Moderator:

r.pakosch

Mitglied
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!
 
S

SlaterB

Gast
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

Gesperrter Benutzer
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:
Java:
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

Mitglied
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!
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
Fynn29 Liste sortieren ohne Array und ohne vorgegebene Sortierung Allgemeine Java-Themen 24
LucasGlockner Effizienter byte-Zugriff auf ein long[]-Array Allgemeine Java-Themen 8
8u3631984 Frage Performance bei Linked List und Array List Allgemeine Java-Themen 5
M Queue mit einem Array implemetieren Allgemeine Java-Themen 16
M Array Rang eines Elements Allgemeine Java-Themen 4
TheSepp Java bestimmtes Array auf den Wert 0 setzen Allgemeine Java-Themen 32
TheSepp Wie kann man Leerzeichen aus einer Array liste entfernen? Allgemeine Java-Themen 10
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
noah1407 Array Allgemeine Java-Themen 3
D Methoden Teil-Array mit Maximalwert bestimmen Allgemeine Java-Themen 23
N einem Array Objekte hinzufügen die ihr Array position gespeichert haben Allgemeine Java-Themen 34
N zweidimensionalen Array in dreidimensionalen Array speichern Allgemeine Java-Themen 4
N Schnellste Methode, ein Array durchzugehen? Allgemeine Java-Themen 9
T Objekt Array Aufgabe mit Busdatenbank Allgemeine Java-Themen 2
L Array und Index Allgemeine Java-Themen 26
L die 3 größten Zahlen im Array Allgemeine Java-Themen 1
G jToggleButton in Array/ArrayList Allgemeine Java-Themen 12
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
Willi.We Array sortieren Allgemeine Java-Themen 5
gotzi242 Array Summe bestimmen tipps? Allgemeine Java-Themen 14
H Matrix ohne Array erstellen Allgemeine Java-Themen 9
Aboya Char Array rekursiv vergleichen Allgemeine Java-Themen 15
V4ll3.Wff Array in Java Allgemeine Java-Themen 4
Noahscript Aus einem byte Array Steuerungszeichen und Code bekommen und ersetzen Allgemeine Java-Themen 3
H Array Sportschütze Allgemeine Java-Themen 6
Sumo_ow "ArrayIndexOutofBoundsException: 2" Array Problem Allgemeine Java-Themen 6
xGh0st2014 Problem mit Java Array Allgemeine Java-Themen 1
M Array verändern Allgemeine Java-Themen 1
A JavaFX 2 dimensionales array Allgemeine Java-Themen 1
LimDul Direktes return eines Array geht nicht Allgemeine Java-Themen 20
S Array dynamisieren oder ArrayList verwenden? Allgemeine Java-Themen 17
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
H Array mit dem Datentype String[] initializieren Allgemeine Java-Themen 7
L ArrayList mit String Arrays in ein Array umwandeln Allgemeine Java-Themen 1
H Elemente aus ArrayList in Array speichern Allgemeine Java-Themen 8
E Datentypen Wie kann ich die Längen der unterschiedlichen Ebenen aus einem Objekt lesen von dem ich weiß, dass es ein mehrdimensionaler Array ist? Allgemeine Java-Themen 3
N Byte Array in Java "dekomprimieren" Allgemeine Java-Themen 3
parrot Array Aufgabe Allgemeine Java-Themen 3
N String Array Eingabe Allgemeine Java-Themen 6
R Warum wird mir in der Konsole das "Standard Array" ausgegeben? Allgemeine Java-Themen 2
N Variablen Array Länge ändern. Allgemeine Java-Themen 8
D Kgv aller Paare aus einem Array mit n integer berechnen Allgemeine Java-Themen 5
W Enumeration ein Array/List als Eigenschaft mitgeben - warum geht das nicht? Allgemeine Java-Themen 0
kodela Problem mit strukturiertem Array Allgemeine Java-Themen 18
A Array Problem Allgemeine Java-Themen 8
Drachenbauer Wie stelle ich fest, ob ein Objekt in meinem Array vorkommt? Allgemeine Java-Themen 5
F Datei in String-Array einlesen Allgemeine Java-Themen 8
L Objekt aus Objekt-array "löschen" Allgemeine Java-Themen 2
I Array Parameter mit 2 Klassen - NullPointerException Allgemeine Java-Themen 3
X Größten Werte in meinem Array löschen? Allgemeine Java-Themen 16
E Angabe wie groß Array sein soll und in for-schleifen diesen Array füllen Allgemeine Java-Themen 3
F 3 Dimensionales Array mit Allgemeine Java-Themen 9
M Steueralgorithmus verwandelt Array in Anfangszustand Allgemeine Java-Themen 9
W Array vs. ArrayList vs. HashMap Allgemeine Java-Themen 20
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
T Objekt in Array packen Allgemeine Java-Themen 6
M Zahlen in Array anordnen Allgemeine Java-Themen 8
M Eclipse Unvollständigen Array ansteuern Allgemeine Java-Themen 2
D Erste Schritte Im Array Werte tauschen Allgemeine Java-Themen 5
Xge For/Array Error: IndexOutOfBounds Allgemeine Java-Themen 4
M Wie kann ich ein int[] Array in einer Methode benutzen? Allgemeine Java-Themen 6
FRI3ND Datentypen Date-Array sortieren - Text mitnehmen? Allgemeine Java-Themen 7
D Integer-Array variabler Größe mit Zahlen befüllen (Schleifen) Allgemeine Java-Themen 0
J Variablen Array ertellen bei model.put Allgemeine Java-Themen 13
S Eindimensionales Array in zweidimensionales Array speichern Allgemeine Java-Themen 5
R convert 2d array list to 2d array Allgemeine Java-Themen 1
J json Array würfel Spalten durcheinander Allgemeine Java-Themen 9
MiMa Array umbau oder Alternative? Allgemeine Java-Themen 5
L Datentypen 3D Array Allgemeine Java-Themen 3
M 2D Array mit unterschiedlichen Längen erstellen und befüllen Allgemeine Java-Themen 11
Mario1409 Methoden JSON Array von URL Allgemeine Java-Themen 8
E Swing Array mit Bildern in GUI darstellen Allgemeine Java-Themen 2
P Array einer abstrakten Klasse Allgemeine Java-Themen 4
H Zweidimensionales Array - Zellen der Tabelle verbinden Allgemeine Java-Themen 2
M Zweidimensionales Array mit Binärzahlen füllen Allgemeine Java-Themen 8
M Array aus Thread Objekten erstellen Allgemeine Java-Themen 2
kodela Dynamisches Array in einer Klasse Allgemeine Java-Themen 5
G Array ohne Aufzählungszeichen ausgeben Allgemeine Java-Themen 6
J Wie kann ich ein Java Array als Säulendiagramm ausgeben? Allgemeine Java-Themen 2
Z 2D Array Pixels reparieren Allgemeine Java-Themen 2
S Algorithmus welcher True-Werte in einem Array findet und auswertet. Allgemeine Java-Themen 5
B Polibios Array erweitern Allgemeine Java-Themen 1
R Index in einem Array löschen Allgemeine Java-Themen 10
R Index in einem Array löschen Allgemeine Java-Themen 2
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
J Array-List Bubble-Sort Allgemeine Java-Themen 12
4 Variablen Int-Array Int Zuweisen Allgemeine Java-Themen 7
J Array Allgemeine Java-Themen 8
Z Array mit unterschiedlichen Werten Allgemeine Java-Themen 1
L sortiertes Array im main aufrufen klappt nicht. Allgemeine Java-Themen 3
O Mein JButton Array funktioniert nicht Allgemeine Java-Themen 3
A Mit dem letzten bis zum ersten Wert aus Array rechnen Allgemeine Java-Themen 15
A Vector Strings in Array splitten Allgemeine Java-Themen 6
I Muster in Array suchen Allgemeine Java-Themen 10
RalleYTN Datentypen Herausfinden ob Object ein Array ist ohne den Typen des Arrays zu kennen? Allgemeine Java-Themen 12
S Variablen String[] Array per schleife in int[] einlesen Allgemeine Java-Themen 8
B Zahlen manuell eingeben und in Array Speichern Allgemeine Java-Themen 2
R Wärmeleitung, 3d-Array Allgemeine Java-Themen 2
T Java Array in Methoden Allgemeine Java-Themen 1
D Erste Schritte Array von einer forschleife nach ausserhalb trasferieren Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben