Collections Schnellster Container für 4Byte vergleiche

[Letters90]

Hi,

Ich bin derzeit daran nen Crawler als Teil eines größeren Programmes zu schreiben, dabei kommt es vor das man mal gerne über eine Seite ca. 40.000-3.000.000 verschiedene URLS hat, damit diese nicht mehrfach abgefragt werden habe ich sie in ner ArrayList abgespeichert, dann über Contains(Object) auf die Equals methode eine Hashvergleich über einen 4byte integer.

synchronized (synchronizeON) {
      isInside = (Visited.contains(item) || toVisit.contains(item));
    }

  public boolean equals(Object obj) {
    if (obj == null) {
      return false;
    }
    if (!(obj instanceof mrURL)) {
      return false; // different class
    }
    if (this.Hashcode == ((mrURL) obj).Hashcode) {
      return true;
    }
    return false;
  }

Die Suchzeiten steigen aber nunman wie erwartet nach ner gewissen laufzeit und containergröße an, das geht bei 50.000 Elementen mit ca. 120ms aufwärts.

Jetzt bin ich aber in java nicht so gewandt das ich alle möglichen guten container kenne, kennt jemand von euch einen container mit dem ich da mehr geschwindigkeit bei wachsender datenmenge rausholen könnte? random access brauche ich dabei nicht.

( binärbaum könnte ich mir da gut vorstellen, wie heißen die in java 😀 ? )

 

[Spacerat]

Vergiss die ArrayList, vergiss equals... Hashcode ist der einzige Ansatz den du brauchst aber halt ein ganz spezieller, nämlich der Instanzhashcode bzw. die Identität der URLs. Diese kannst du in einer zum Set "kastrierten" IdentityHashMap<URL, Boolean> sammeln.
Hinzufügen per [c]visited.put(visitedUrl, Boolean.TRUE);[/c], abfragen über [c]visited.containsKey(url);[/c]

 

[Letters90]

Ich test das gerade mal durch, sieht aber schonmal nicht schlecht aus. Danke 🙂

Gott stell ich mich wieder dämlich an, bis ich grad verstanden warum du in deinem beispiel als value boolean drinne hast tz... ( für die die genauso dämlich sind, es ist ne reduzierung auf die überprüfung des keys da die daten selbst nicht gebraucht werden, desshalb kleinst möglichen datentyp: boolean )

Ich krieg die Identity Hashmap partout nicht dazu auf die hashCode() methode zuzugreifen.

Ich habs jetzt mit ner HashMap implementiert und werd mal schauen wie gut ich die capacity anpassen kann.

Aber danke schonmal, hab jetzt schonmal soweit nen performance gain das er er nach 10% nicht bei 150kbyte/s rumgammelt sondern noch an 6mbyte/s bleibt.

 

[faetzminator]

Statt einer Map tuts ein Set auch 😉

 

[Spacerat]

Ach so ist das. gleiche URLs haben nicht die selbe Identität? Dann sag' das doch 😳. Dann nimm TreeSet. Ein TreeSet steigt bei ungleichen Objekten evtl. schon vor equals aus hashcode, das müsste man testen.
ABER: Da man sich bei der Auswahl der Interfaces einer URL anscheinend geirrt hat, implementiert eine solche Serializable statt Comparable. Eine URL ist deswegen zur Sortierung nicht geeignet, weswegen man selber einen Comparator bauen müsste. In diesem Fall genügt glücklicherweise ein allgemeiner TO_STRING_COMPARATOR:

public static final Comparator<Object> TO_STRING_COMPARATOR = new Comparator<Object>() {
		@Override
		public int compare(Object o1, Object o2) {
			if (o1 == null) {
				return (o2 == null) ? 0 : -1;
			} else if (o2 == null) {
				return 1;
			}
			return o1.toString().compareTo(o2.toString());
		}
	};

Ein simpler Vergleich über Hashcodes könnte dazu führen, dass zwei verschiedene URLs als gleich angesehen werden. Eine Equals-Hashcode-Rekursion sollte nicht zuletzt nur deswegen vwrmieden werden.
@faetzminator: Jep... von der Identity-Reihe gibt es aber leider kein Set. Die "Kastration" einer Map zu einem solchen ist aber recht einfach wie man sieht.

 

[Letters90]

String compares will ich zwingend vermeiden, die sind einfach zu langsam. Hab jetzt bei ca. 2,5mio elementen ( wären mindestens 30byte vergleiche auf strings ) ne Suchlaufzeit von 5ms durch die Hashmap, bin damit also ganz gut zufrieden. Doppelte elemente sind unwarscheinlich, sollte es doch vorkommen dann werd ich die datenmenge für den hash nochmal begrenzen dann sind die ausgeschlossen. ( 1% doppelte elemente begrenzen die funktionalität auch nicht )

Also bin so wies ist zufrieden, schneller kann ichs zurzeit nicht testen da meine Leitung nicht mehr hergibt, aber da es end user programm werden soll ist das auch vollkommen ausreichend
( toVisit hat größen zwischen 20-200 da ist ArrayList vertretbar)

public class URLTracer {

  private static HashMap<mrURL, Object> Visited = new HashMap<mrURL, Object>(3500000);
  // Hashmap capacity wird noch in den config files hinterlegt
  private ArrayList<mrURL> toVisit;
  private static final Object synchronizeON = new Object();

  public URLTracer() {
    toVisit = new ArrayList<mrURL>();
  }

  public boolean isEmpty() {
    return toVisit.isEmpty();
  }

  public boolean insert(mrURL item) {
    boolean isInside;
    synchronized (synchronizeON) {
      isInside = (toVisit.contains(item) || Visited.containsKey(item));
    }
    if (isInside == true) {
      return false;
    }
    toVisit.add(item);
    return true;
  }

  public mrURL pop() {
    if (!isEmpty()) {
      synchronized (synchronizeON) {
        Visited.put(toVisit.get(0), null);
      }
      mrURL Temp = toVisit.get(0);
      toVisit.remove(0);
      return Temp;
    }
    return null;
  }

  static public int getVisitedSize() {
    return Visited.size();
  }
}

optimierungen werde ich wohl noch einige dran machen ^^ aber jetzt kann ich mich wieder mehr auf die datenbankanbindung konzentrieren 🙂

 

[Spacerat]

Okay... Das was du noch sofort optimieren könntest wäre die HashMap durch ein HashSet (wie es faetzminator schon vorgeschlagen hat) zu ersetzen. Obwohl... HashSet ist auch nichts anderes, als das, was du aus der Map gemacht hast, nur ein "put(Object, null);" ist immer ungünstig, denn <Map>.containsValue() würde undefinierte Ergebnisse liefern, wenn man sie ausversehen mal benutzen sollte. Mach' ein konstantes Objekt (z.B. "PRESENT") draus.

 

[faetzminator]

@faetzminator: Jep... von der Identity-Reihe gibt es aber leider kein Set. Die "Kastration" einer Map zu einem solchen ist aber recht einfach wie man sieht.

Warum meinst du denn, dass du zwingend eine IdentityHashMap benötigst?

 

[Spacerat]

Warum meinst du denn, dass du zwingend eine IdentityHashMap benötigst?

Weil ich annahm, dass gleiche URLs halt identisch sind, weil's naheliegend wär. Tja, falsch gedacht 😳.

 

[nillehammer]

"Verwende Sets" ist schon geschrieben worden. Hiermit stellst Du sicher, dass keine Duplikate vorhanden sind und je nach Implementierung geht die contains-Prüfung beim adden auch wesentlich schneller als bei einer List. Auch brauchst Du dann keine eigenimplementierten hashCode-Klimmzüge mehr zu machen. Sowas gehört zu den sog. Infrastrukturmethoden, die jedes Objekt in Java bereits hat.

Zweiter wichtiger Ansatz zur Optimierung ist: "Vermeide URL und nimm URI". Bei URL wird nämlich in der equals-Methode ein DNS-Lookup gemacht. Das bremst richtig aus! Wahrscheinlich sogar noch mehr, als eine List iterativ zu durchlaufen.

 

[Letters90]

"Verwende Sets" ist schon geschrieben worden. Hiermit stellst Du sicher, dass keine Duplikate vorhanden sind und je nach Implementierung geht die contains-Prüfung beim adden auch wesentlich schneller als bei einer List. Auch brauchst Du dann keine eigenimplementierten hashCode-Klimmzüge mehr zu machen. Sowas gehört zu den sog. Infrastrukturmethoden, die jedes Objekt in Java bereits hat.

Zweiter wichtiger Ansatz zur Optimierung ist: "Vermeide URL und nimm URI". Bei URL wird nämlich in der equals-Methode ein DNS-Lookup gemacht. Das bremst richtig aus! Wahrscheinlich sogar noch mehr, als eine List iterativ zu durchlaufen.

Ich hab im Hashset quellcode nachgeschaut, ist ne ähnliche implementierung zu meiner. Bin trotzdem zur sauberkeit auf sets umgestiegen.

Eigenimplementierung vom hashCode ist mir wichtig, ich gehe über meine Implementierung sicher das der Hashcode nur einmal im konstruktor erzeugt wird, objekte von mrURL sind soft-final, URL equals wird in meinem Quellcode nicht verwendet aber vielen dank für den Tip.

( einmalige hashcode erzeugung ist mir wegen der datenmenge wichtig, bei ca. 2 Mio vergleiche für jeden string einen hashcode zu erstellen ( ich bin die hashcode methode des Strings nicht abgelaufen aber ich gehe vom worstcase aus ) würde mir performance entziehen )

warum sollten genau die sets duplikate ausschließen und auf welchem kriterium?

 

[faetzminator]

Siehe [c]if (e.hash == hash && ((k = e.key) == key || key.equals(k)))[/c] aus Java 6 ([c]HashMap#put()[/c] <-- [c]HashSet#add()[/c]).

 

[Letters90]

Interessant, wert einen Blick auf die implementierung und die Unterschiede zwischen Set und Map zu werfen !

HashMap Put:

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

HashSet Member:

private transient HashMap<E,Object> map;

HashSet add

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

Nicht allzu überraschend da ich da schonmal durch bin, aber erklärt nun warum mein key kein primärer datentyp sein kann. Identität und Gleichheit ist klar, habe mich bei der vorgerhenden Aussage wohl zu sehr auf meinen Code beschränkt oder es waren die ArrayLists für toVisit gemeint.

Werde bei toVisit wohl doch bei den Listen bleiben da hier die Zugriffsmethoden und die innere ordnung passender sind, zudem bleibt der container im garantiert schnellem bereich.

Vielen dank nochmal fürs darauf aufmerksam machen

 

[Spacerat]

Interessant, wert einen Blick auf die implementierung und die Unterschiede zwischen Set und Map zu werfen ...
Vielen dank nochmal fürs darauf aufmerksam machen

Nichts zu Danken... Hast du nun geringfügig 'ne Idee, wie ich auf die Art komme die IHM zu einem IHS zu "kastrieren"? Eben genau so. 😉