Vergleich zweier Objekte durch "Hashfunktion"

[Boolesche]

Ahoi Miteinander,

ich benötige eine Möglichkeit Eigenschaften zweier Objekte schnell zu vergleichen:
z.B.:

Objekt eins mit den Eigenschaften:
A = 12;
B = 0;
C = 123;
...

Objekt zwei mit den Eigenschaften:
A = 12;
B = 1;
C = 0;
...

Wenn man die Eigenschaften als "Füllstände" betrachtet, wäre meine Fragestellung zu dem Problem z.B. entsprechen die Füllstände von Objekt zwei mindestens dem von Objekt eins. (in dem Fall nein da: eins.C > zwei.C)

Da es sehr viele Eigenschaften gibt (>60) und eine Abarbeitung über Schleifen mühselig und Zeitaufwändig ist, hatte ich folgende Idee:

Alle Eigenschaften der Objekte in ein BitSet überführen und diese Sets zu vergleichen:

z.B. eins: 110001111011 zwei: 110010000000

Wichtig wäre auch die Information welche Eigenschaft nicht passt.

Ist dieser Ansatz sinnvoll, gibt es evtl. schon Hauslösungen in Java?

Beste Grüße

 

[nrg]

welche datenhaltung hast du denn? BitSet klingt interessanter als es letzendlich ist.. da mach es in den meisten Fällen auch eine klasse mit einem boolean-array und paar methoden was auch meistens deutlich perfomanter ist.

edit: bei 'ner Map würde sich vllt sowas anbieten:

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class FillLevels {
	
	private Map<String, Integer> levels;
	
	public FillLevels() {
		this.levels = new HashMap<String, Integer>();
	}
	
	public void add(String name, int fillLevel) {
		levels.put(name, fillLevel);
	}
	
	public boolean atLeastThan(FillLevels fl) {
		for (Entry<String, Integer> e : levels.entrySet()) {
			Integer i = fl.levels.get(e.getKey());
			if (i != null && e.getValue() < i) return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		FillLevels fl1 = new FillLevels();
		fl1.add("A", 12);
		fl1.add("B", 0);
		fl1.add("C", 123);
		
		FillLevels fl2 = new FillLevels();
		fl2.add("A", 12);
		fl2.add("B", 1);
		fl2.add("C", 0);
		
		System.out.println(fl2.atLeastThan(fl1));
	}
}

 

[bERt0r]

Wie willst du Objekte mit hilfe eines Hash codes vergleichen, ausser auf gleichheit? Hash funktionen sind dafür ausgelegt, eben keinen Rückschluss auf die Inputdaten zu liefern.

Wenn du nur auf Gleichheit prüfen willst kannst du die equals Funktion deiner Objekte mit einer Hash-Funktion überschreiben, und die Hashwerte vergleichen.

Falls du für einen größer/kleiner Vergleich einfach nur die Summe deiner Eigenschaften vergleichen willst, kannst du die ja nochmal extra in deiner Klasse speichern, und bei jedem set neu berechnen. Dann kannst du schnell die zwei Summen vergleichen, ohne sie neu zu berechnen. Mit Hash hat das dann aber wie gesagt nix zu tun, und Objekt1(0,0,10) ist dann gleich groß wie Objekt2(5,5,0)

 

[Ariol]

Wenn wir was über die Datenhaltung erfahren wirst du sicher konstruktivere Vorschläge bekommen.

z.B. für Arrays:

Arrays.equals(array1,array2);

Wo liegt überhaupt das Problem mit der Geschwindigkeit? 60 Objekte gegeneinander zu vergleichen sollte je nach Struktur kein Problem sein. Erst recht nicht wenn es sich um primitive Datentypen wie int, long, double, boolean usw. handelt.

 

[bERt0r]

@Ariol
Naja so ein equals wird intern doch auch über eine Schleife geregelt, und bei ein paar tausend Objekten mit ja 60 Vergleichen pro compare würde man die Performance schon merken. Bei kleineren Mengen hast du natürlich recht.

 

[Ariol]

@Ariol
Naja so ein equals wird intern doch auch über eine Schleife geregelt, und bei ein paar tausend Objekten mit ja 60 Vergleichen pro compare würde man die Performance schon merken. Bei kleineren Mengen hast du natürlich recht.

Jop, es kommt eben auf den Anwendungsfall an. Solange vom Threadersteller nichts kommt bleibt wohl erstmal nir mutmaßen.

Eventuell ließe sich auch was mit Serialisierung machen, wobei dass sich bei 60 Objekten/Attributen/Werten wohl kaum lohnen wird.???:L

 

[nrg]

er will doch gar kein equals sondern ein "mindestens so groß wie"...

 

[Boolesche]

Vielen Dank für die schnellen Antworten!

Bilder sagen mehr als tausend Worte…ich habe mal ein Pseudo-UML mit einer Abstraktion des Konstruktes angefügt.

Ihr habt es schon vermutet es handelt sich um mehrere tausend Objekte -> um ein konkretes Beispiel zu nennen: EndObject bis 30k ZwischenObject mehrere hundert (siehe Anlage)…

Die Objekte sind in einer Art Baumstruktur hierarchisch geordnet: StammObjecte haben ZwischenObjecte und diese wiederum können EndObjecte aufnehmen. (Die original Baumstruktur ist noch etwas größer und verschachtelter).

• Die Eigenschaften können ordinal, nominal Skaliert oder eben int/float sein.
• Die EndObjekte werden über die die Methode addEndObject() eingefügt und dann nach unten weitergereicht wenn die Eigenschaften des Übergeordneten Objektes größer, oder gleich, etc. dem des Endobjektes sind und schließlich an das ZwischenObject gehängt. Wenn die Eigenschaften nicht passen, soll es nach Möglichkeit eine Info geben welche Eigenschaft der Engpass war (nur die Erste)

Die Idee (angelehnt an deinem Vorschlag nrg) wäre jetzt ein 2dimensionales Speicherkonstrukt zu nehmen (String, String) -> (Typ, Wert) dort alle Eigenschaften zu Speichern und dann über eine Schleife und einer Weiche wenn Typ X auftaucht einen cast des Wertes auf das eigentlichen Format vorzunehmen um anschließend die passende Vergleichsoperation vorzunehmen. Leider scheint mir dieser Ansatz wenig elegant, nur leider kann sich die Anzahl und Typen der Eigenschaften je nach Anwendungsfall unterscheiden…

 

[Ariol]

Hab jetzt grade keine solchen Datenmengen hier.
Hier eine Art DeepCompare zweier Objekte:

@SuppressWarnings({ "unchecked", "rawtypes" })
	public static int compare(Object o1, Object o2)
	{
		int result = 0;
		Field[] fields1 = o1.getClass().getDeclaredFields();
		for (int i = 0; i < fields1.length; i++)
		{
			Field f1 = fields1[i];
			System.out.println("Testing " + f1.getName());

			if (Modifier.isStatic(f1.getModifiers()))
			{
				System.out.println(" Field " + f1.getName() + " is static");
				continue;
			}

			Field f2 = null;
			try
			{
				f2 = o2.getClass().getDeclaredField(f1.getName());
			} catch (SecurityException e)
			{
				System.err.println(" Field " + f1.getName() + " not accessible");
				continue;
			} catch (NoSuchFieldException e)
			{
				System.err.println(" Field " + f1.getName() + " doesn't exist");
				continue;
			}

			if (!f1.isAccessible())
				f1.setAccessible(true);
			if (!f2.isAccessible())
				f2.setAccessible(true);

			Object v1, v2;
			try
			{
				v1 = f1.get(o1);
				v2 = f2.get(o2);
			} catch (Exception e)
			{
				System.err.println(" Getting value of field " + f1.getName() + " failed");
				continue;

			}

			if (v2 instanceof Comparable && v1 instanceof Comparable)
			{
				System.out.println(" Comparing " + v1 + " with " + v2);
				int compResult = ((Comparable) v1).compareTo(v2);

				if (compResult != 0)
					result = compResult;

				if (compResult == 1)
				{
					System.err.println("  Field " + f1.getName() + " is too low");
					break;
				} else
				{
					System.out.println("  Result was " + compResult);
				}
			} else
			{
				result=compare(v1, v2);
			}
			System.out.println("--------------------");
		}
		System.out.println("Compare finished with " + result);
		return result;
	}

Vielleicht hilft dir das ja...
Ist natürlich noch verbesserbar (Abfrage nach null, Hash-Vergleich, usw...) und die Debug-Ausgaben sind sicherlich auch etwas hinderlich, aber vielleicht hilft es dir ja auch so.

EDIT: v1 und v2 müssen auch auf null getestet werden!!!

 

[Boolesche]

Große Klasse dieses Forum! Danke Ariol ich werde deinen Ansatz am Wochenende in mein Modell einbauen. Auf die Idee die Objekte quasi nach ihren Variablen "zu fragen" bin ich überhaupt nicht gekommen...

 

[Boolesche]

Ahoi Miteinander,

es hat leider aus Zeitmangel etwas gedauert, nun habe ich eine Quick&Dirty Version erstellt, die soweit funktioniert. Im Grunde wird jetzt eine Attribut-Objekt erzeugt und diese mit zwei Strings befüllt. Dabei wird der Name in der entsprechenden HashMap durch ein korrespondierendes enum Objekt (mit den Infos zum Datenformat) ersetzt und der eigentliche Wert eingefügt. Bei Positivem Test zweier Objekte wird das Hauptobjekt mit neuen Werten befüllt, sonst eben nicht.
Performant ist das ganze irgendwie nicht dafür sehr flexibel, ich muss bei neuen Attributen lediglich die Enum-Klasse anpassen.

Habt Ihr Ideen wie man das ganze Testen und Vergleichen eleganter gestalten könnte?

import java.util.HashMap;
import java.util.Map.Entry;

public class RestrictionAttributes {
	
	HashMap<ObjektAttributes, String> restrMap;
	
	
	RestrictionAttributes(){
		restrMap = new HashMap<ObjektAttributes, String>();
	}
	
	
	public void checkFit(RestrictionAttributes restrA){
		
		HashMap<ObjektAttributes, String> map = new HashMap<ObjektAttributes, String>();
		boolean fit = true;
		
		for (Entry<ObjektAttributesObjektAttributes, String> e : restrMap.entrySet()) {
			
			String objA = restrA.restrMap.get(e.getKey());
			
			if(objA != null){
				
				String valueType = e.getKey().getValueType();
				
				//TODO unbedingt verbessern
				
				int result = 0;
				String newValue = "";
				
				if(valueType == "Integer"){
					
					result = Integer.parseInt(e.getValue()) - Integer.parseInt(objA);
					newValue = Integer.toString(result);
					
				} else if(valueType == "String"){

					result = ((Comparable) e.getValue()).compareTo(objA);
					newValue = e.getValue();
					
				} else if(valueType == "Float"){
					
					float flo = Float.parseFloat(e.getValue()) - Float.parseFloat(objA);
					newValue = Float.toString(flo);
					result = (int) Math.ceil(flo*10000);
					
				} else {
					System.out.println("Unbekanntes Format");
				}
				
				if(result < 0){
					System.out.println(e.getKey()+" zu klein");
					fit = false;
					//TODO Fehlerliste fuellen
				} else {
					System.out.println("easy");
					map.put(e.getKey(), newValue);
				}

			}
        }
		
		if(fit != false){
			updateRestiction(map);
			System.out.println("Update Restriction");
		}
	}
	
	
	
	public void updateRestiction(HashMap<ObjektAttributesObjektAttributes, String> map){
		
		for (Entry<ObjektAttributesObjektAttributes, String> e : map.entrySet()) {
			restrMap.put(e.getKey(), e.getValue());
		}
	}
	
	public void setRestriction(String name, String value){
			
		ObjektAttributesObjektAttributes[] attr = ObjektAttributesObjektAttributes.values();
		
		for (ObjektAttributesObjektAttributes staAtt : attr) {
			if(staAtt.getName() == name){
				restrMap.put(staAtt, value);
				break;
			}
		}
		
		
	}
	
	public void ausgabe(){
		for (Entry<ObjektAttributesObjektAttributes, String> e : restrMap.entrySet()) {
			System.out.println(e.toString());
		}
		
	}
	
	// Test
	public static void main(String[] args) {
		
		RestrictionAttributes tes1 = new RestrictionAttributes();
		tes1.setRestriction("name", "tester");
		tes1.setRestriction("number", "12");
		tes1.setRestriction("height", "1.6");
		tes1.setRestriction("rotation", "1.6");
		
		RestrictionAttributes tes2 = new RestrictionAttributes();
		tes2.setRestriction("name", "tester");
		tes2.setRestriction("number", "10");
		tes2.setRestriction("height", "1.0");

		tes1.checkFit(tes2);
		tes1.ausgabe();
	}
	

}

public enum ObjektAttributes {
	
	  NAME("name", "String"), 
	  NUMBER("number", "Integer"),
	  ROTATION("rotation", "String"), 
	  HEIGHT("height", "Float");
	  
	  private String valueType;
	  private String name;

	  private ObjektAttributes(String name, String valueType){
		  this.valueType = valueType;
		  this.name = name;
	  }
	  
	  public String getName(){
		  return name;
	  }
	  
	  public String getValueType(){
		  return valueType;
	  }
	  
}

 

[SlaterB]

muss man das vorherige alles gelesen haben? erkläre doch worum es geht, was die Aufgabe von checkFit usw. ist,

Strings mit == zu vergleichen ist immer schlecht, wobei bei Enum das gerade so schön leicht geht und du verzichtest draus,
schreibe doch

ObjektAttributesObjektAttributes key = ..;
if (key == ObjektAttributesObjektAttributes.NUMBER) {
} else..

oder noch besser:
switch (key) {
  case NUMBER:
  ..

  ..
  default: unknown
}

 

[Boolesche]

Nein muss man nicht. Es geht im Kern darum eine flexible Möglichkeit Attribute verschiedener Objekte miteinander zu vergleichen zu können:

-> Objekt1.checkFit(Objekt2): Es soll getestet werden ob Objekt das Objekt2 aufnehmen kann, daher ob die Restriktionen (Objekt1.Restriktionen - Objekt2.Restriktionen = Neue Objekt1.Restriktionen) >0 oder bei String = sind

-> updateRestiction(): Wenn die Prüfung aus checkFit() erfolgreich war daher fit = true, wird diese Methode ausgeführt und die Änderungen bzw. neuen Werte für Objekt1 geupdated.

-> setRestriction(): Füllt die Restriktionen der Objekte ganz zu Anfang