Summe der Teiler Summationsfunktion mit Erathosthenes 'Sieb

7

Ich bin auf das folgende Problem von einer Online-Problembank gestoßen: Es gibt bis zu Abfragen, von denen jede die Berechnung der Summe mit ist die Summe der Teiler von . Es ist gegeben, dass . 105 

k=L.R.σ(k)
σ(k)k1L.R.5106

Meine Lösung (unten beschrieben) basiert auf dem Erathosthenes-Sieb. Ich habe es in C ++ implementiert und es funktioniert im Durchschnitt in etwa Sekunden, was zu langsam ist. Ich weiß, dass dieses Problem mindestens zweimal schneller gelöst werden kann, weiß aber nicht wie.0,9

Hier ist meine Lösung (Arrays basieren auf 0):

M = 5 * 1e6
M = array of zeroes of size M + 1
A[1] = 1
for (k = 2; k <= M; k += 1)
    for (j = k; j <= M; j += k)
        A[j] += k

Ich berechne über jedes Erathosthenes-Sieb vorσ(k)kunter dem maximal möglichen Wert. Wenn die Hauptschleife erreichtk, EIN[k]] behält den Wert von σ(k). Dann ordne ich neuEIN[k]] sein ich=1kσ(ich). Nach einer solchen Vorverarbeitung können alle Abfragen in berechnet werdenÖ(1) Zeit durch Rechnen EIN[R.]]- -EIN[L.- -1]].

Wie kann ich es schneller machen? Ich kenne zwei Formeln:

(ein)     σ(p1ein1pseins)=ich=1spicheinich+1- -1pich- -1
(b)     k=1nσ(k)=k=1nknk

Das Problem mit (a) ist, dass die Berechnung (zumindest in meiner Implementierung) langsamer ist als oben angegeben. Das Problem mit (b) ist, dass ich nicht verstehe, wie man die Präfixsumme mit einem solchen Ansatz schneller berechnet als inÖ(n2) Zeit.

Gibt es einen effizienteren Algorithmus für dieses Problem?

(Die Problembank schreibt die ursprüngliche Quelle des Problems als 2012 Kharkiv, Winterschule, Tag von Sergey Kopelovich, Problem H. gut.)

Igor
quelle
Wenn ich richtig verstehe, erstellen Sie eine große LookUp-Tabelle und beantworten dann Abfragen, alles zur Laufzeit, und der Engpass berechnet LookUp? Es gibt zwei Dinge: Könnten Sie Ihre Loops neu anordnen und die Arbeit anders aufteilen? Wenn Speicher und Zeit begrenzt sind, aber nicht die Programmgröße, können Sie einen Teil der Tabelle offline schalten?
Evil
Du verstehst richtig. Ich weiß nicht, wie man Schleifen neu anordnet, aber jetzt denke ich, dass lineares Sieb und Berechnung mit Formel (a) schneller sein könnten.
Igor
Ist dies ein Problem der "realen Welt" oder (anscheinend) "erfunden", z. B. für einen Programmier- oder Mathematikwettbewerb? Hier gibt es eine echte Frage, wie die Tabelle am effizientesten berechnet werden kann, aber selbst eine relativ einfache Implementierung kann die gesamte "moderate" Größe berechnen106Tabelle in nur wenigen Sekunden oder weniger, und dann (anscheinend aus der Beschreibung) sind alle nachfolgenden Abfragen nur O (1) Tabellensuchen. Also, was ist das Problem damit? Wie auch immer, wenn es erfunden ist, mag es anscheinend nicht, dass einige der frühen Problemeinstellungen zu Beginn versuchen, es wie ein echtes Problem klingen zu lassen. seine im Grunde angewandte Zahlentheorie ...
vzn
Schlagen Sie für das erfundene Problem vor, dass es keine endlichen Grenzen für den Tisch gibt und stattdessen neu formuliert / fokussiert wird, um nach den O (f (n)) -Effizienzen verschiedener Ansätze zu fragen, dh "ein einfacher Ansatz benötigt O (f1 (n)) -Zeit dies auf O (f2 (n)) Zeit verbessert werden? ". Versuchen Sie es trotzdem mit Computer Science Chat für weitere Analysen
vzn
@vzn Vielen Dank für die Aufmerksamkeit auf meine Frage. Der Ursprung des Problems wird in Frage gestellt und ist nicht "real". Es geht nicht um ultraschnelle wissenschaftliche Berechnungen, sondern um einfache und mäßig effiziente Algorithmen.
Igor

Antworten:

5

Das ist nicht wirklich Informatik ...

Sie erstellen eine Tabelle d, in der Sie die Summe der Teiler von k für k = 1 bis M speichern, wobei M = 5· ·106. Das ist der Teil, der zeitkritisch ist. Dann erstellen Sie eine Tabelle s, in der Sie die Summe der Teiler für alle 1 ≤ j ≤ k speichern, für k = 1 bis M. Das ist einfach,s0=0, sk+1=sk+dk+1. Und dann ist f (L, R) =sR.- -sL.- -1.

Die erste Tabelle ist das Problem. Sie erledigen das inÖ(nLogn). Und du brauchst nur einen Faktor zwei, sagst du ...

Sie haben ein Array d mit 5 Millionen Einträgen, wahrscheinlich 4 Byte pro Eintrag = 20 Megabyte. Auf einem typischen Prozessor, den Sie in Ihrem Heimcomputer haben würden, passen 20 Megabyte nicht in einen Cache. Und Ihr Code führt viele Zugriffe auf Elemente dieses Arrays in quasi zufälliger Reihenfolge durch. Für jeden potentiellen Teiler k besuchen Sie alle Zahlen, die durch k teilbar sind, und erhöhen die Summe der Teiler um k.

Machen wir das mit weniger Besuchen: Wenn Sie j besuchen, das durch k teilbar ist, addieren Sie die beiden Teiler k und j / k. Aber wenn Sie das tun, beginnen Sie mitj=k2Fügen Sie nur k hinzu (weil k = j / k, und Sie möchten den Divisor nicht zweimal zählen), und fügen Sie dann k und j / k für weiteres j hinzu. Sie müssen nicht teilen, da j / k gleich k + 1, k + 2, k + 3 usw. ist. Wir initialisieren das Array für den Fall k = 1, dh setzen A [j] = 1 + j / 1 für j ≥ 2.

A [1] = 1
for (j = 2; j ≤ M; j += 1)
    A [j] = 1 + j

for (k = 2; k*k ≤ M; k += 1)
    j = k*k
    A [j] += k
    j += k
    s = k + (k + 1)
    while j ≤ M
        A [j] += s
        j += k
        s += 1 // s equals k + j / k

Sie speichern keine Operationen. Sie greifen jetzt jedoch viel regelmäßiger auf das Array A zu, sodass Sie Zeit sparen, da der Zugriff auf die Elemente schneller erfolgt. j ist kleiner, wodurch die Anzahl der Iterationen für jedes j größer wird, wodurch die Verzweigungsvorhersage besser funktioniert.

Zur weiteren Verbesserung würden Sie herausfinden, wie viele Array-Elemente in den Prozessor-Cache Ihres Computers passen, und dann den gesamten Code nur für Unterbereiche des Arrays ausführen (z. B. nur A [0] in A [99999] ändern und dann A ändern [100000] bis A [199999] und so weiter). Auf diese Weise greifen die meisten Speicherzugriffe nur auf den Cache-Speicher zu, der möglicherweise wesentlich schneller ist.

Sie führen N Suchvorgänge in einer Tabelle der Größe M durch. Wenn M wesentlich größer als N ist, sollten Sie wahrscheinlich über Ansätze nachdenken, die diese Tabelle nicht erstellen und die pro Suche möglicherweise viel langsamer sind, aber insgesamt schneller aufgrund von die geringe Anzahl von Suchvorgängen. Selbst in dem Fall, in dem N ≤ 100.000 und M = 5.000.000 ist, können Sie beispielsweise die Teiler 1, 2, 3, 4, j / 1, j / 2, j / 3, j / 4 in der Tabelle nicht zählen (was ergibt es ist etwas schneller zu bauen) und handhaben das während der Suche.

Oder Sie können die Summe der Teiler nur für ungerade Zahlen addieren und dann die Summe der Teiler für gerade Zahlen berechnen (wenn die Summe der Teiler eines ungeraden k s ist, beträgt die Summe für 2k 3s, für 4k 7s für 8k sind es 15s usw.), was fast einen Faktor 2 einsparen würde.

PS. Ich habe es gemessen ... wodurch der Algorithmus zum Zählen aller Summen von Teilern cachefreundlicher wurde, indem sowohl j als auch k / j addiert wurden, was die Geschwindigkeit verdoppelte. Wenn Sie zuerst die Summe der Teiler für ungerade k berechnen und dann gerade k aus den ungeraden Werten berechnen, ist dies insgesamt siebenmal schneller. Offensichtlich alles nur konstante Faktoren.

gnasher729
quelle
3

Lassen Sie mich Ihr Problem ein wenig neu ordnen: Die Verwendung eines Hauptsiebs sollte hilfreich sein, aber ein normales Erathostenes-Sieb ist nicht gut genug.

Was Sie brauchen, ist ein Hauptsieb, das in linearer Zeit arbeitet und jede Zahl nur einmal trifft.
Eine Beschreibung des linearen Zeitprimensiebs zeigt, wie jede Zahl nur einmal gekreuzt wird.
Was sind Vorteile? Wenn wir dort anstelle der Kreuzung von Zahlen die Summe der Teiler einfügen, haben wir einen schnellen Algorithmus zum Platzieren von Teilern (bitte denken Sie daran1 als Teiler).

Es gibt auch einen zusätzlichen Schritt, Primzahlen werden nicht berechnet. Wenn wir also auf einen stoßen, sollten wir den Divisor als diese Zahl + 1 schreiben.

Als nächstes sollte es einen kumulativen Durchgang geben (durch das Array gehen und das letzte Element hinzufügen, um die Summe aller vorherigen Teiler zu erhalten).

Auf diese Weise sollte jede Zahl genau einmal geschrieben werden, daher ist dies mit Sicherheit besser als der ursprüngliche Versuch.

Was könnte man noch tun?
Da es weniger Abfragen als Zahlen gibt, dachte ich, wir können vielleicht die Berechnung des gesamten Arrays weglassen?

Dies kann auf mindestens zwei Arten erfolgen: Es ist offensichtlich, dass ein Teil (oder sogar ein ganzes) Array offline geschaltet wird (nicht während der Zeitmessung), wodurch das Programm größer wird, aber es gab keine Größenbeschränkung.

Eine andere Möglichkeit besteht darin, eine ganze Reihe von kumulativen Teilern zu berechnen und dann einige Funktionen anzupassen, die Ergebnisse von Indizes abrufen.

Die Funktionen selbst können etwas kompliziert sein oder um das Denken zu erleichtern, können wir sie in Bereiche unterteilen - wodurch sie kürzer und leichter zu finden sind.
Die enorme Komplexität dahinter erfolgt offline, und zur Laufzeit wird nur die Zeit abgefragt, da es überhaupt kein Sieb gibt.

Böse
quelle
-1

Sie können vorberechnete Ergebnisse für Intervalle {L = 1, R = k * 10 ^ 4} und Brute-Force nur für etwa 2 * 10 ^ 4 Zahlen speichern

Kotomord
quelle
1
Das Problem ist, dass das Erstellen der vorberechneten Ergebnisse zu lange dauert.
Gnasher729
Warum sollte das ein guter Ansatz sein?
Raphael