(Algorithmus) Finden Sie, ob zwei unsortierte Arrays gemeinsame Elemente in O (n) Zeit haben, ohne zu sortieren?
8 Antworten
Sie haben das Berechnungsmodell nicht definiert. Angenommen, Sie können nur O (1) -Bits in O (1) -Zeit lesen (alles andere wäre ein eher exotisches Modell der Berechnung), kann kein Algorithmus das Problem in O (n) worst-case-Zeitkomplexität lösen.
Proof Skizze: Jede Zahl in der Eingabe benötigt O (log (n ^ 100)) = O (100 log n) = O (log n) Bits. Der gesamte Eingang enthält daher O (n log n) Bits, die nicht in O (n) Zeit gelesen werden können. Jeder O (n) -Algorithmus kann daher nicht die gesamte Eingabe lesen und somit nicht reagieren, wenn diese Bits wichtig sind.
Hashtable wird Sie speichern. Wirklich, es ist wie ein Schweizer Messer für Algorithmen.
Geben Sie einfach alle Werte aus dem ersten Array ein und überprüfen Sie dann, ob ein Wert aus dem zweiten Array vorhanden ist.
Antwort auf Neil: Da Sie am Anfang wissen, was Ihr N ist (zwei Arrays der Größe N), können Sie einen Hash mit der Array-Größe 2 * N * some_ratio erstellen (zum Beispiel: some_ratio = 1.5). Bei dieser Größe bieten fast alle einfachen Hash-Funktionen eine gute Verteilung der Entitäten.
Sie können find_or_insert auch implementieren, um nach vorhandenen Dateien zu suchen oder eine neue Datei bei derselben Aktion einzufügen. Dadurch werden die Hash-Funktion und die Vergleichsaufrufe reduziert. (c ++ stl find_or_insert ist nicht gut genug, da es Ihnen nicht sagt, ob das Objekt schon einmal da war oder nicht).
Linearitätstest
Verwenden der Mathematica-Hash-Funktion und Ganzzahlen mit beliebiger Länge.
Getestet bis n = 2 ^ 20 , Zufallszahlen werden erzeugt bis (2 ^ 20) ^ 100 = (ca. 10 ^ 602)
Nur für den Fall ... das Programm ist:
%Vor%Setzen Sie die Elemente des ersten Arrays in eine Hash-Tabelle und prüfen Sie, ob das zweite Array durchsucht werden kann. Dies gibt Ihnen eine Lösung in O (N) Durchschnittsfall.
Wenn Sie eine echte O (N) Worst-Case-Lösung wünschen, verwenden Sie anstelle einer Hash-Tabelle ein lineares Array im Bereich 0-n ^ 100. Beachten Sie, dass Sie nur ein einzelnes Bit pro Eintrag verwenden müssen.
Haben Sie versucht, counting sort zu testen? Es ist einfach zu implementieren, verwendet O (n) Raum und hat auch eine \ theta (n) Zeitkomplexität.
Basierend auf den bis heute veröffentlichten Ideen. Wir können die Integer-Elemente eines Arrays in einer Hash-Map speichern. Die maximale Anzahl verschiedener Ganzzahlen kann im RAM gespeichert werden. Hash-Map hat nur eindeutige Integer-Werte. Duplikate werden ignoriert.
Hier ist die Implementierung in Perl Sprache.
%Vor%Ich hoffe, es hilft.
Was ist der Unterschied zwischen IEnumerator und IEnumerable?
Jasons Antwort ist gut, aber ich dachte, ich würde nur hinzufügen, wie ich darüber denke. Stellen Sie sich vor, Sie haben eine Sequenz:
%Vor%Stellen Sie sich nun vor, Sie haben einen Pfeil, der auf eine Position dieser Sequenz zeigt:
%Vor%Ein "Pfeil" ist ein Objekt, das zwei Dinge tun kann. Erstens kann es dir das geben, auf das es zeigt. Zweitens kann es sich bei der nächsten Sache zeigen.
IEnumerator ist ein Pfeil. Es hat eine Eigenschaft, Current, die dir das gibt, auf das es zeigt. Es hat eine Methode, MoveNext (), die sich bei der nächsten Sache zeigt.
Wie bekommen Sie überhaupt einen Pfeil? Du brauchst eine Pfeilfabrik. Sie fragen die Fabrik nach einem Pfeil und Sie erhalten einen Pfeil, der auf das erste Element in der Sequenz zeigt.
IEnumerable ist eine Pfeilfabrik. Es hat eine Methode, GetEnumerator, die Ihnen einen Pfeil zum ersten Element der Sequenz gibt.
Eine nette Eigenschaft dieses Schemas ist, dass Sie mehrere Pfeile haben können, die auf verschiedene Stellen in derselben Reihenfolge zeigen.
Welche Vorteile bietet die Implementierung der generischen Schnittstelle IEnumerable anstelle von IEnumerable?
Angenommen, die Folge besteht aus ganzen Zahlen. Wenn Sie %code% implementieren, dann sagen Sie
%Vor%was das tatsächlich tut, ist, das int in der Sequenz in ein Objekt zu konvertieren, die Ganzzahl zu boxen und dann das Objekt sofort wieder auf integer zu setzen, was eine völlig unnötige Speicherzuweisung zu jeder einzelnen Operation hinzufügt. Wenn der Compiler weiß, dass die Sequenz aus ganzen Zahlen besteht, kann er die unnötige Boxoperation überspringen.
Angenommen, die Sequenz besteht aus Strings. Wenn Sie %code% implementieren, können Sie sagen:
%Vor%Wenn nicht, dann müssen Sie
sagen %Vor%was unnötig und fehleranfällig ist. Anstatt den Compiler über eine Umwandlung anzuweisen, dass der Typ eine Zeichenfolge ist, können Sie garantieren , dass der Typ eine Zeichenfolge ist, indem Sie das Typsystem verwenden.
Ich verwende den folgenden Code, um myClass foreach zu aktivieren. Aber ich bin ziemlich neu in der Programmierung und habe einige Schwierigkeiten, den folgenden Code zu verstehen. Ich habe meine Probleme in den Kommentaren beschrieben. Ich wäre dankbar für die Bereitstellung von Informationen.
%Vor%1) Was ist IEnumerator für?
IEnumerator ist der echte Arbeitsteil mit den MoveNext () - und Current-Mitgliedern.
Was ist der Unterschied zwischen IEnumerator und IEnumerable
?
IEnumerable ist die Schnittstelle für eine Sammlung, um zu signalisieren, dass sie über einen GetEnumerator () verfügt.
2) [nicht generischer GetEnumerator] Wozu dient es? Es ruft nur die obige Methode auf
Die nicht-generische Methode dient nur der Abwärtskompatibilität. Beachten Sie, dass es durch Verwendung der expliziten Implementierung so weit wie möglich außer Sichtweite verschoben wird. Implementieren Sie es, weil Sie müssen und dann vergessen.
3) Zu guter Letzt, welche Vorteile mir die Implementierung der genetischen Schnittstelle bringt IEnumerable statt nur IEnumerable
Bei Verwendung mit %code% ist der Vorteil klein, da foreach die Looping-Variable eingibt. Sie können %code% in der foreach verwenden:
%Vor%Aber mit %code% haben Sie auch eine typsichere Schnittstelle zu anderen Bereichen, insbesondere LINQ:
%Vor%Dies ist die Deklaration für %code% :
%Vor%Sie haben keine andere Wahl, als Sie die nicht-generische IEnumerable-Schnittstelle zu implementieren. Sie erhalten einen Kompilierungsfehler, wenn Sie die IEnumerable.GetEnumerator () - Implementierung auslassen. Dies ist Gepäck, das von den .NET 1.x-Tagen übrig geblieben ist, an denen noch keine Generics verfügbar waren, und der Übergangsphase für .NET 2.0, bei der Interop mit .NET 1.x-Assemblys unterstützt werden musste. Wir sind dran.
%code% gibt es bereits seit der Einführung von Generika in die Sprache, um nicht bereits vorhandenen Code zu unterbrechen. Die Standardmethode ruft die generische Implementierung auf.
Bei einer generischen Aufzählung muss der Consumer Ihrer Klasse beim Iterieren nicht jedes Element in eine Zeichenfolge umwandeln.
1) Wofür ist %code% ? Was ist der Unterschied zwischen %code% und %code% ?
%code% ist eine Schnittstelle, die Methoden darstellt, mit denen Sie eine Sequenz aufzählen können. Der Unterschied zwischen %code% und %code% besteht darin, dass ersteres den Vertrag für Objekte darstellt, mit denen Sie eine Sequenz aufzählen können, und letzteres den Vertrag für Objekte darstellt, die eine Sequenz sind, die überzählig sein kann.
%Vor%2) Wozu dient es? Es ruft nur die obige Methode auf.
Ersteres repräsentiert eine Implementierung der Methode %code% auf dem Vertrag %code% . Letzteres stellt eine explizite Implementierung der Methode %code% auf dem Vertrag %code% dar. Das Problem ist, dass beide Verträge eine Methode namens %code% haben, aber unterschiedliche Rückgabetypen haben, so dass eine Methode nicht beide Verträge gleichzeitig erfüllen kann (jede Klasse, die %code% implementiert, muss auch %code% als %code% implementieren). Letzteres ruft die Implementierung von %code% auf, da dies eine sinnvolle Implementierung ist, die ein %code% als %code% zurückgibt.
3) Welche Vorteile habe ich von der Implementierung der generischen Schnittstelle %code% anstelle von %code% ?
Starkes Tippen. Sie wissen, dass die Elemente in einer Sequenz %code% alle Instanzen von %code% sind, während Sie für %code% nicht wissen und am Ende versuchen könnten, ein Element des Letzteren in eine Instanz von %code% zu verwandeln kann nicht sein.
Zur dritten Frage (warum Generika verwenden?) hier sind einige Antworten:
Sollten wir Generic Collection verwenden, um die Sicherheit zu verbessern und Leistung?
Kurz gesagt, verwenden Sie so oft wie möglich generische Sammlungen.