Grundsätzlich habe ich etwa 1.000.000 Strings, für jede Anfrage muss ich prüfen, ob ein String zur Liste gehört oder nicht.Schnellste Möglichkeit zu überprüfen, ob eine Liste <String> einen eindeutigen String enthält
Ich mache mir Sorgen über die Leistung, also, was ist die beste Methode? ArrayList? Hash?
Verwenden Sie am besten eine HashSet und überprüfen Sie, ob eine Zeichenfolge im Set über die -Methode existiert. HashSets sind für den schnellen Zugriff durch Verwendung der Objektmethoden hashCode() und equals() gebaut. Die Javadoc HashSet heißt es:
Diese Klasse konstante Zeitleistung für die Grundfunktionen bietet (Hinzufügen, Entfernen, enthält und Größe),
HashSet stores objects in hash buckets die, dass der Wert von der zurück sagen hashCode Methode bestimmt, in welchem Bucket ein Objekt gespeichert ist. Auf diese Weise wird die Anzahl der Gleichheitsüberprüfungen, die HashSet über die equals()-Methode ausführen muss, auf nur die anderen Objekte im selben Hash-Bucket reduziert.
Um HashSets und HashMaps effektiv zu verwenden, müssen Sie den equals und hashCode Vertrag umrissen in the javadoc entsprechen. Im Fall von java.lang.String wurden diese Methoden bereits implementiert, um dies zu tun.
Was noch? Es hat O (1) für add und enthält. –
danke @Andreas_D, habe ich das Zitat aus dem Javadoc hinzugefügt, die besagt, dass es konstante Zeit Leistung hat. – krock
Der lustige Teil kommt, wenn die Millionen Strings nicht mehr in den Hauptspeicher passen. –
Ich würde eine Set verwenden, in den meisten Fällen HashSet ist in Ordnung.
Die Antwort von krock ist etwas besser, um das OP zu einer optimalen Lösung zu bringen: Ein TreeSet hat O (log2 (N)) Performance, während ein HashSet idealerweise O (1) hat. –
@Carl, unter der Annahme, dass sowohl equals als auch hashCode() O (1) sind, d. H. Zeichenkettenlängen werden nicht berücksichtigt. –
Wenn Sie so viele Strings haben, ist die beste Möglichkeit für Sie, eine Datenbank zu verwenden. Suchen Sie nach MySQL.
Im Allgemeinen stimme ich dir zu, aber er macht sich Sorgen um die Lookup-Leistung - bringt das nicht viel Overhead? – Rup
Netzwerklatenz wird hinzugefügt, aber Sie haben die volle Leistungsfähigkeit von SQL zur Verfügung. Eine andere Überlegung ist der Speicher - eine Million Strings mit 32 Zeichen bedeuten ~ 64 MB RAM. Es ist ein klassisches Verhältnis zwischen CPU und Speicher. Ich würde es vergleichen und sehen. – duffymo
@Rup: Absolut. Und viele Möglichkeiten für Fehler. Wenn die Daten in den Speicher passen (und sie müssen, wie sie es bereits eingepackt haben), sollte es im Speicher gesucht werden. –
Im Allgemeinen wird Ihnen ein HashSet eine bessere Leistung bringen, da es nicht wie bei einer ArrayList jedes Element durchsehen und vergleichen muss, sondern in der Regel höchstens einige Elemente vergleicht, bei denen die Hashcodes gleich sind.
Allerdings kann die Leistung von HashSet für 1M Strings immer noch nicht optimal sein. Viele Cachefehlschläge verlangsamen das Durchsuchen des Sets. Wenn alle Strings gleich wahrscheinlich sind, ist dies unvermeidlich. Wenn jedoch einige Zeichenfolgen häufiger angefordert werden als andere, können Sie die allgemeinen Zeichenfolgen in ein kleines hashSet einfügen und das zuerst überprüfen, bevor Sie die größere Menge überprüfen. Der kleine Hash-Satz sollte so groß sein, dass er in den Cache passt (z. B. höchstens einige hundert K). Die Zugriffe auf das kleine Hashset sind dann sehr schnell, während die Zugriffe auf das größere Hashset mit einer durch die Speicherbandbreite begrenzten Geschwindigkeit ablaufen.
+1: Obwohl es mir vorkommt, dass, da Strings einzeln zugewiesen werden, es möglicherweise nicht besonders relevant ist, wie viele, insgesamt, in einer bestimmten hashmap sind, da eine Suche nur einen winzigen Prozentsatz von ihnen treffen wird. Relevanter könnte das tatsächliche Zuweisungsmuster der char-Arrays in den Strings selbst sein, über das der Java-Programmierer sowieso keine Kontrolle hat (und das ist eine gute Sache). –
@Software Monkey - die Absicht besteht darin, dass durch das Einfügen der am häufigsten gesuchten Strings in eine eigene Map ein hoher Grad an Treffern für diese Map erreicht wird. Eine kleinere Hash-Map mit häufig verwendeten Strings hat eine höhere Trefferrate im Cache als eine größere Map, da jede Cache-Zeile im Map-Backing-Array mehreren häufig verwendeten Strings entspricht.Natürlich, wie Sie sagen, hilft das nicht bei der Zuweisung der Strings selbst. Wenn das ein Problem ist, dann kann das Zuweisen der häufigsten Zeichenfolgen zu einem besseren Cache-Gebrauch führen, da die VM von der gleichen Region des Heaps zuordnen kann. – mdma
Bevor Sie weiter gehen, denken Sie bitte darüber nach: Warum sind Sie besorgt über die Leistung? Wie oft wird dieser Check aufgerufen?
Wie für mögliche Lösungen:
Wenn die Liste bereits sortiert ist, dann können Sie java.util.Collections.binarySearch verwenden, die die gleichen Leistungsmerkmale wie ein java.util.TreeSet bietet.
Andernfalls können Sie eine java.util.HashSet, die als Leistungsmerkmal von O (1) verwenden. Beachten Sie, dass die Berechnung des Hash-Codes für eine Zeichenfolge, für die noch keine Berechnung durchgeführt wurde, eine O (m) -Operation mit m = string.length() ist. Beachten Sie auch, dass Hashtabellen nur gut funktionieren, bis sie einen bestimmten Ladefaktor erreichen, d. H. Hashtabellen verwenden mehr Speicher als einfache Listen.Der Standardladefaktor, der von HashSet verwendet wird, ist 0.75, was bedeutet, dass intern ein HashSet für 1e6-Objekte ein Array mit 1.3e6-Einträgen verwendet.
Wenn das HashSet nicht für Sie funktioniert (z. B. weil es viele Hash-Kollisionen gibt, weil der Speicher knapp ist oder viele Einfügungen vorhanden sind), sollten Sie eine.verwenden. Das Nachschlagen in einer Trie hat eine Worst-Case-Komplexität von O (m), wobei m = string.length() ist. Ein Trie hat auch einige zusätzliche Vorteile, die für Sie nützlich sein könnten: z. B. kann es Ihnen die nächstgelegene passende für eine Suchzeichenfolge geben. Aber denken Sie daran, dass der beste Code kein Code ist, also rollen Sie nur Ihre eigene Trie-Implementierung, wenn die Vorteile die Kosten übersteigen.
Verwenden Sie eine Datenbank, wenn Sie komplexere Abfragen wünschen, z. Übereinstimmung für eine Teilzeichenfolge oder einen regulären Ausdruck.
-1: Er ist besorgt über die Leistung, weil er (a) einen riesigen Datenbestand hat, und (b) jeder halbwegs anständige Programmierer, der sein Geld wert ist, sollte immer berücksichtigen, ob die Leistungsmerkmale eines Algorithmus oder einer Datenstruktur für die Aufgabe. –
Nicht nur für String, können Sie Set für jeden Fall, dass Sie einzigartige Gegenstände müssen verwenden.
Wenn die Art der Elemente primitiv oder Wrapper ist, ist es Ihnen vielleicht egal. Aber wenn es eine Klasse ist, müssen Sie zwei Methoden außer Kraft setzen:
Mit einer so großen Anzahl von Strings, habe ich sofort von einem Trie denken. Es funktioniert besser mit einem begrenzten Satz von Zeichen (wie Buchstaben) und/oder wenn der Anfang von vielen Zeichenfolgen überlappt.
Manchmal möchten Sie prüfen, ob sich ein Objekt in der Liste/Menge befindet und gleichzeitig die Liste/das Set geordnet werden soll. Wenn Sie Objekte auch ohne Verwendung einer Aufzählung oder eines Iterators abrufen möchten, sollten Sie sowohl ArrayList<String> als auch HashMap<String, Integer> verwenden. Die Liste wird von der Karte unterstützt.
Beispiel von einer Arbeit, die ich vor kurzem tat
public class NodeKey<K> implements Serializable, Cloneable{
private static final long serialVersionUID = -634779076519943311L;
private NodeKey<K> parent;
private List<K> children = new ArrayList<K>();
private Map<K, Integer> childrenToListMap = new HashMap<K, Integer>();
public NodeKey() {}
public NodeKey(Collection<? extends K> c){
List<K> childHierarchy = new ArrayList<K>(c);
K childLevel0 = childHierarchy.remove(0);
if(!childrenToListMap.containsKey(childLevel0)){
children.add(childLevel0);
childrenToListMap.put(childLevel0, children.size()-1);
}
...
In diesem Fall Parameter K wäre ein String für Sie sein. Die Karte (childrenToMapList) speichert Strings, die in die Liste (children) als Schlüssel eingefügt wird, und die Kartenwerte sind die Indexposition in der Liste.
Der Grund für die Liste und die Karte ist, dass Sie indizierte Werte der Liste abrufen können, ohne eine Iteration über eine HashSet<String> zu machen.
Nachdem ich die Übung hier ausgeführt habe, sind meine Ergebnisse.
private static final int TEST_CYCLES = 4000;
private static final long RAND_ELEMENT_COUNT = 1000000l;
private static final int RAND_STR_LEN = 20;
//Mean time
/*
Array list:18.55425
Array list not contains:17.113
Hash set:5.0E-4
Hash set not contains:7.5E-4
*/
Ich glaube, die Zahlen sprechen für sich. Die Suchzeit des Hash-Sets ist viel schneller.
Vielleicht ist dies nicht für Ihren Fall erforderlich, aber ich denke, es ist nützlich zu wissen, dass es platzspar probabilistischer Algorithmus ist:
Eine gute Übung sowohl verschiedene Listen/Sätze sein würde, um zu versuchen/Karten und dann sehen, wenn Sie herausfinden können, warum Sie verschiedene Zeiten bekommen, indem Sie die Java-Dokumente für die Sammlungen lesen :) – willcodejavaforfood
Um sicher zu sein, dass Sie dieses Recht machen, lernen Sie, einen Profiler gut zu verwenden. Die niedrigste hängende Frucht ist die jvisvisualvm im JDK. –