Ich versuche, das Produkt von Ziffern jeder Zahl einer Zahlenfolge zu berechnen, zum Beispiel:
21, 22, 23 ... 98, 99 ..
wäre:
2, 4, 6 ... 72, 81 ..
Um die Komplexität zu reduzieren, würde ich nur die [ fortlaufenden Nummern ] in einer begrenzten Länge von Ziffern berücksichtigen, wie z von 001 bis 999 oder von 0001 bis 9999 .
Wenn die Sequenz jedoch groß ist, z. B. 1000000000 , wiederhole die Ziffern und multipliziert für jede Zahl, wäre das ineffizient.
Die Grundidee besteht darin, die aufeinanderfolgenden Nullen zu überspringen, auf die wir bei der Berechnung stoßen werden, etwa so:
%Vor%Dies ist nur für die Aufzählung von Zahlen, um zu vermeiden, dass Zahlen, die Nullen enthalten, zuerst berechnet werden, die Ziffernprodukte sind noch nicht durch den Code gegeben; aber erzeugen Sie die Ziffernprodukte, indem Sie einen Delegierten zur Verfügung stellen, um die Berechnung durchzuführen, dauert noch Zeit.
Wie berechnet man die Ziffernprodukte der fortlaufenden Nummern effizient?
EDIT: Die "Start von überall, erweiterter Bereich" Version ...
Diese Version hat einen deutlich erweiterten Bereich und gibt daher IEnumerable<long> anstelle von IEnumerable<int> zurück - multiplizieren Sie genug Ziffern und überschreiten Sie int.MaxValue . Es geht auch bis zu 10.000.000.000.000.000 - nicht ganz die volle Bandbreite von long , aber ziemlich groß :) Du kannst überall anfangen, wo du willst, und es wird von dort bis zu seinem Ende weitergehen.
EDIT: Leistungsanalyse
Ich habe die Leistung in Detail nicht betrachtet, aber ich glaube, dass der Großteil der Arbeit an diesem Punkt einfach nur über eine Milliarde Werte iteriert. Eine einfache for -Schleife, die nur den Wert selbst zurückgibt, dauert über 5 Sekunden auf meinem Laptop, und das Iterieren über die Ziffernprodukte dauert nur etwas mehr als 6 Sekunden, also glaube ich nicht, dass es viel mehr Platz für Optimierung gibt - wenn Sie wollen von Anfang an gehen. Wenn Sie (effizient) von einer anderen Position aus starten möchten, sind weitere Anpassungen erforderlich.
Okay, hier ist ein Versuch, der einen Iteratorblock verwendet, um die Ergebnisse zu erhalten, und die ersten tausend Ergebnisse vorberechnet, um die Dinge etwas schneller zu machen.
Ich habe es bis zu 150 Millionen getestet, und es ist soweit korrekt. Es geht nur die erste Milliarde Ergebnisse zurück - wenn Sie mehr als das brauchten, könnten Sie einen anderen Block am Ende hinzufügen ...
%Vor%Ich habe das getestet, indem ich es mit den Ergebnissen einer unglaublich naiven Version verglichen habe:
%Vor%Ich hoffe, dass diese Idee von Nutzen ist ... Ich weiß nicht, wie sie mit den hier gezeigten in Bezug auf die Leistung verglichen wird.
BEARBEITEN: Erweitern wir dies etwas, um einfache Schleifen zu verwenden, bei denen wir wissen, dass die Ergebnisse 0 sind, haben wir weniger Bedingungen, um die wir uns kümmern müssen, aber aus irgendeinem Grund ist es tatsächlich etwas langsamer. (Das hat mich wirklich überrascht.) Dieser Code ist länger, aber möglicherweise ein wenig einfacher zu folgen.
%Vor%Sie können dies in einer dp-ähnlichen Weise mit der folgenden rekursiven Formel tun:
%Vor% wobei a[n] das Ergebnis der Multiplikation der Ziffern von n ist.
Dies führt zu einem einfachen Algorithmus O(n) : Wenn Sie f(n) unter der Annahme berechnen, dass Sie f(·) für kleinere n bereits berechnet haben, können Sie einfach das Ergebnis aller Ziffern verwenden, aber das letzte multipliziert mit der letzten Ziffer.
Du kannst die teure Multiplikation loswerden, indem du einfach a[n - 1] + a[n / 10] für Zahlen hinzufügst, bei denen die letzte Ziffer nicht 0 ist.
Der Schlüssel zur Effizienz besteht nicht darin, die Zahlen aufzuzählen und die Ziffern zu extrahieren, sondern Ziffern aufzuzählen und die Zahlen zu generieren.
%Vor% Es liegt an dem Aufrufer, die Ergebnisse zu ignorieren, die kleiner als min sind.
Hier ist eine Low-Space-Version mit der Branch-bound-Prune-Technik:
%Vor%Da die Zahlen aufeinanderfolgend sind, können Sie in den meisten Fällen ein Produkt aus dem vorherigen generieren, indem Sie nur den Einheitenplatz überprüfen.
Zum Beispiel:
12345 = 1 * 2 * 3 * 4 * 5 = 120
12346 = 1 * 2 * 3 * 4 * 6 = 144
Aber sobald Sie den Wert für 12345 berechnet haben, können Sie 12346 als (120/5) * 6 berechnen.
Dies funktioniert natürlich nicht, wenn das vorherige Produkt Null war. Es funktioniert beim Umbrechen von 9 auf 10, weil die neue letzte Ziffer Null ist, aber Sie könnten diesen Fall sowieso optimieren (siehe unten).
Wenn Sie mit vielen Ziffern arbeiten, führt diese Vorgehensweise zu einer beträchtlichen Einsparung, auch wenn es sich um eine Teilung handelt.
Wenn Sie die Werte durchlaufen, um die Produkte zu generieren, wissen Sie, dass das Produkt Null ist, sobald Sie auf eine Null stoßen.
Wenn Sie beispielsweise bei vierstelligen Zahlen 1000 erreichen, wissen Sie, dass die Produkte bis 1111 alle null sind, also müssen Sie diese nicht berechnen.
Wenn Sie bereit sind oder können, alle Werte im Voraus zu speichern, können Sie sie in O (1) abrufen. Da es sich um einmalige Kosten handelt, ist in diesem Fall die Effizienz des Algorithmus, den Sie verwenden, weniger wichtig.
Ich habe am Ende sehr einfachen Code wie folgt:
Code:
%Vor% msd ist die höchstwertige Ziffer , sie ist wie höchstwertiges Bit im Binärformat .
Der Grund, warum ich das Iterator-Muster nicht gewählt habe, ist, dass es länger dauert als der Methodenaufruf. Der vollständige Code (mit Test) steht hinter dieser Antwort.
Beachten Sie, dass die Zeile default(R)!=(digitProd=default(R))?default(R): ... nur für die Zuordnung von digitProd gilt, da der Delegat nicht vor der Zuweisung verwendet werden kann. Wir können es tatsächlich schreiben als:
Alternative Syntax:
%Vor%Der Nachteil dieser Implementierung ist, dass sie nicht von einer bestimmten Nummer gestartet werden kann, sondern von der maximalen Anzahl an ganzen Ziffern.
Es gibt ein paar einfache Ideen, die ich löse:
Rekursion
Der Delegat ( Action ) R ist eine rekursive Delegatendefinition, die als Tail Call Rekursion verwendet wird. sowohl für den Algorithmus als auch für den Delegaten, der das Ergebnis von digit product erhält.
Und die anderen Ideen unten erklären warum Rekursion.
Keine Aufteilung
Bei fortlaufenden Nummern wird die Verwendung der Division zum Extrahieren jeder Ziffer als geringe Effizienz betrachtet, und daher entschied ich mich, die Ziffern direkt mit der Rekursion in einer Abwärtszählung zu bearbeiten.
Beispiel: Mit 3 Ziffern der Zahl 123 ist es eine der 3 Ziffern, die von 999 :
9 8 7 6 5 4 3 2 [1] 0 - die erste Rekursionsebene
9 8 7 6 5 4 3 [2] 1 0 - die zweite Rekursionsebene
9 8 7 6 5 4 [3] 2 1 0 - die dritte Rekursionsebene
Cache nicht speichern
Wie wir sehen können, dass diese Antwort
Wie man jede Ziffer in einem multipliziert effizient nummerieren
vorgeschlagen, den Mechanismus der Zwischenspeicherung zu verwenden, aber für die fortlaufenden Nummern, wir nicht, da es ist der Cache.
Für die Zahlen 123, 132, 213, 231, 312, 321 sind die Ziffernprodukte identisch. Daher können wir für einen Cache die zu speichernden Elemente reduzieren, die nur die gleichen Ziffern mit unterschiedlicher Reihenfolge (Permutationen) haben, und wir können sie als denselben Schlüssel betrachten.
Das Sortieren der Ziffern erfordert jedoch auch Zeit. Mit einer HashSet implementierten Sammlung von Schlüsseln zahlen wir mehr Speicherplatz mit mehr Artikeln; Selbst wenn wir die Items reduziert haben, verbringen wir immer noch Zeit damit, Gleichheit zu vergleichen. Es scheint keine Hash-Funktion zu geben, die besser ist als Verwenden Sie den Wert für die Gleichheit beim Vergleichen und das ist nur das Ergebnis, das wir berechnen. Zum Beispiel, außer 0 und 1, gibt es nur 36 Kombinationen in der Multiplikationstabelle von zwei Ziffern.
Solange die Berechnung effizient genug ist, können wir daher davon ausgehen, dass der Algorithmus selbst ein virtueller Cache ist, ohne einen Speicher zu kosten.
Reduzieren Sie die Zeit bei der Berechnung von Zahlen enthalten Null (s)
Für die Ziffernprodukte der fortlaufenden Nummern werden wir folgendes finden:
1 Null pro 10
10 aufeinanderfolgende Nullen pro 100
100 aufeinanderfolgende Nullen pro 1000
und so weiter. Beachten Sie, dass es immer noch 9 Nullen gibt, auf die wir mit per 10 in per 100 stoßen werden. Die Anzahl der Nullen kann mit folgendem Code berechnet werden:
Für n ist die Anzahl der Ziffern, r ist die Radix. Die Nummer wäre eine Power-Serie , die aus einem geometrische Reihe und plus 1 für 0 .
Zum Beispiel die Zahlen von 4 Ziffern, die Nullen werden wir begegnen:
(1) + (((1 * 9) +11) * 9 + 111) * 9 = (1) + (1 * 9 * 9 * 9) + (11 * 9 * 9) + (111 *) 9) = 2620
Bei dieser Implementierung überspringt nicht die Berechnung von Zahlen wirklich mit Null. Der Grund dafür ist das Ergebnis einer flachen Rekursionsebene, die mit der rekursiven Implementierung wiederverwendet wird und die wir als cached betrachten können. Der Versuch der Multiplikation mit einer einzelnen Null kann erkannt und vermieden werden, bevor sie ausgeführt wird, und wir können eine Null direkt an die nächste Rekursionsstufe übergeben. Allerdings wird die Multiplikation nur wenig Auswirkungen auf die Leistung haben.
Der vollständige Code:
%Vor% Im Code, doNothing , countOnly , printProd sind was zu tun, wenn wir das Ergebnis von digit product bekommen, können wir jede von ihnen an digitProd weitergeben, die den vollständigen Algorithmus implementiert haben. Zum Beispiel würde digitProd(countOnly, power) nur count erhöhen, und das Endergebnis wäre dasselbe wie CountOfZeros zurückgibt.
Ich würde ein Array erstellen, das die Dezimalziffern einer Zahl darstellt, und diese Zahl dann genau so erhöhen, wie Sie es im wirklichen Leben tun würden (d. h. bei einem Überlauf erhöht sich die höherwertige Zahl).
Von dort würde ich eine Reihe von Produkten verwenden, die als kleine Nachschlagetabelle verwendet werden können.
z. die Zahl 314 würde zu dem Produkt-Array führen: 3, 3, 12 die Zahl 345 würde das Produkt-Array ergeben: 3, 12, 60
Wenn Sie nun die Dezimalzahl erhöhen, müssen Sie nur das righter-Produkt neu berechnen, indem Sie es mit dem Produkt auf der linken Seite multiplizieren. Wenn eine zweite Ziffer geändert wird, werden nur zwei Produkte neu berechnet (das zweite von rechts und das äußere rechte Produkt). Auf diese Weise werden Sie nie mehr als unbedingt notwendig berechnen und Sie haben eine sehr kleine Nachschlagetabelle.
Wenn Sie also mit der Zahl 321 beginnen und dann erhöhen:
%Vor%Hier ist ein Beispiel, um die Idee zu zeigen (nicht sehr guter Code, aber nur als Beispiel):
%Vor%Auf diese Weise wird das Produkt für 1000 Zahlen im Milliardenbereich fast so schnell berechnet wie für die Zahlen 1 bis 1000.
Übrigens bin ich sehr neugierig, wofür Sie all das verwenden wollen?
Abhängig von der Länge Ihrer Zahlen und der Länge der Sequenz würde für einige Optimierung gehen.
Da Sie die maximale Größe der Zahl begrenzen können, können Sie über die Zahl selbst über einen steigenden Modul iterieren.
Nehmen wir an, Sie haben die Nummer 42:
%Vor%Sie können diese Operation in eine nette Schleife packen, die wahrscheinlich klein genug ist, um in die Caches der Prozessoren zu passen und über die ganze Zahl zu iterieren. Da Sie keine Funktionsaufrufe vermeiden, ist dies wahrscheinlich auch ziemlich schnell.
Wenn Sie Nullen als Abbruchkriterium behandeln wollen, ist die Implementierung dafür offensichtlich ziemlich einfach.
Matthew sagte bereits : Ultimative Leistung und Effizienz werden mit einer Nachschlagetabelle erzielt.Je kleiner der Bereich Ihrer Sequenznummern ist, desto schneller ist die Nachschlagetabelle; weil es aus dem Cache und nicht aus dem langsamen Speicher abgerufen wird.
Tags und Links language-agnostic c# math