Archiv verlassen und diese Seite im Standarddesign anzeigen : Ultra schneller Hamming Algorithmus
Godmode
2005-10-18, 13:40:38
Ich muss einen verdammt schnellen Algorithmus programmmieren, der die Hammingfolge ermittelt.
Definition:
Zahl 1 ist das 1. Element der Folge
Wenn h ein Element der Folge ist, so sind auch 2h, 3h und 5h Elemente der Folge.
Keine andere Zahl ist Element der Folge
Unser Programm muss nun folgendes können: man gibt eine zahl ein, zb 2*10^9 und das Programm sollte dann die Folge bis dort hin berrechnen. Meine Lösung bis jetzt:
int HammingArray(unsigned long start)
{
if(start <= size)
{
arr[start]= '1';
if(2*start <= size)
{
if(arr[2*start] == '0')
HammingArray(2*start);
}
if(3*start <= size)
{
if(arr[3*start] == '0')
HammingArray(3*start);
}
if(5*start <= size)
{
if(arr[5*start] == '0')
HammingArray(5*start);
}
}
return 0;
}
int HammingHash(unsigned long start)
{
if(start <= size)
{
Insert(start);
if(2*start <= size)
{
if(Find(2*start) == 0)
HammingHash(2*start);
}
if(3*start <= size)
{
if(Find(3*start) == 0)
HammingHash(3*start);
}
if(5*start <= size)
{
if(Find(5*start) == 0)
HammingHash(5*start);
}
}
return 0;
}
Einmal mit Hashtable gelöst, einmal mit Array. Problem beim Array ist, dass große Zahlen nicht mehr möglich sind, da mir der Speicher ausgeht, deshalb hab ich dann auch noch einen mit Hashtable gemacht. Die Hashtable muss ich aber dann wieder sortieren, also auch nicht so toll. Jetzt frage ich mich ob ich gänzlich ohne Hashtable und Array auskommen kann, also bitte her mit euren Vorschlägen. Meine Variante läuft rekursiv, was mir eigentlich auch nicht so gut gefällt. Das Array und die HT brauche ich um überprüfen zu können, ob ein Wert schon existiert und ich ihn daher nicht mehr berechnen muss.
mfg bans3i
ps: es geht um C
Demirug
2005-10-18, 14:14:54
Wie brutal darf ich den sein?
Was willst du am Ende haben? Eine sortierte Liste mit allen Zahlen der Folge auf dem Bildschirm?
Muss es C sein oder darf es auch C++ sein?
Godmode
2005-10-18, 14:25:51
Wie brutal darf ich den sein?
Was willst du am Ende haben? Eine sortierte Liste mit allen Zahlen der Folge auf dem Bildschirm?
Muss es C sein oder darf es auch C++ sein?
Es solltes schon C sein, zur Zeitmessung zählt aber nur die Berechnung. Ja es sollte dann eine sortierte Liste sein. Von der Brutalität her: es sollte kein Assambler hack sein, sondern schon C, aber sonst kannst dich richtig austoben. Meine neue Idee wäre es in eine Liste sortiert einfügen.
Demirug
2005-10-18, 14:34:08
OK, dann noch eine Frage zu der Datenspeicherung der Liste. Wie soll die am Ende genau aussehen, oder ist das egal?
Und wo ist die Obergrenze für das Ende der Folge?
Godmode
2005-10-18, 14:52:09
Sie sollte halt sortiert sein, und die Obergrenze soll variabel sein, also ein meinem Algorithmus ist size die Obergrenze. Also 2*10^9 sollte er mindestens schaffen.
Demirug
2005-10-18, 14:55:07
Mir geht halt irgendwann der Adressraum aus wenn ich das als einen großen Block speichere und kein 64 Bit OS habe.
Wie schnell ist eigentlich der schnellste in eurer Klasse im Moment? ;)
Neomi
2005-10-18, 14:58:36
Die Folge kannst du stark vereinfachen (ohne sie zu verändern), indem du alle Zahlen dieser Form errechnest:
2^x * 3^y * 5^z
Dabei gilt:
x >= 0
y >= 0
z >= 0
Es gibt keine zwei Exponenten-Triple, die zur gleichen Zahl führen. Jetzt mußt du nur noch genügend Zahlen berechnen und sortieren.
Godmode
2005-10-18, 15:02:53
klingt schon mal interessant, werd ich mir dann ansehn.
Eine andere Formulierung:
Du suchst eine aufsteigende Aufzählung aller Zahlen <n mit Primfaktoren aus {2,3,5}.
Jede Zahl lässt sich schreiben als 2^x *3^y * 5^z, mit genug Speicher könntest du einfach alle (x,y,z) durchzählen und die Liste sortieren.
Kannst ja mal gucken ob du bei gegebenem (x,y,z) eine Funktion angeben kannst die das Tripel der nächstgrößeren Zahl herausfindet. Dann geht es sogar beliebig weit weil mit konstantem Speicher.
Neomi
2005-10-18, 15:11:10
klingt schon mal interessant, werd ich mir dann ansehn.
void Berechne (int iBasis, int iMul)
{
int iZahl = iBasis * iMul;
if (iZahl > iObergrenze)
return;
// iZahl in die Liste stopfen
if (iMul <= 2)
Berechne (iZahl, 2);
if (iMul <= 3)
Berechne (iZahl, 3);
Berechne (iZahl, 5);
return;
}
Wenn du eine leere Liste hast und "Berechne (1, 1);" startest, erhälst du quasi die Liste. Da du das sortieren willst, empfiehlt sich ein AVL-Baum. Die Obergrenze muß natürlich bekannt sein.
Godmode
2005-10-18, 17:03:08
Mir geht halt irgendwann der Adressraum aus wenn ich das als einen großen Block speichere und kein 64 Bit OS habe.
Wie schnell ist eigentlich der schnellste in eurer Klasse im Moment? ;)
Der aktuelle Rekord liegt anscheinend bei 0,01 sec bei 2*10^9 und den sollten wir topen, ich arbeite jetzt gerade an einer Variante mit einer sortierten Liste.
Senior Sanchez
2005-10-18, 17:10:02
Der aktuelle Rekord liegt anscheinend bei 0,01 sec bei 2*10^9 und den sollten wir topen, ich arbeite jetzt gerade an einer Variante mit einer sortierten Liste.
Das wird dann bald im Rahmen der Messungenauigkeit liegen, meint ihr nicht?
Mal ne Frage, auf was für einem System wurde das erreicht?
Weil, man könnte bestimmt mithilfe von BrookGPU oder so noch die GPU einer Grafikkarte einspannen und das die bei solchen Dingen ziemlich abgehen könnten, dürfte wohl klar sein ;)
Godmode
2005-10-18, 17:23:58
[code]
Wenn du eine leere Liste hast und "Berechne (1, 1);" startest, erhälst du quasi die Liste. Da du das sortieren willst, empfiehlt sich ein AVL-Baum. Die Obergrenze muß natürlich bekannt sein.
geht schon mal ganz gut, nur bekomme ich ab ca 1Mrd einen Stackoverflow ;D
Der aktuelle Rekord liegt anscheinend bei 0,01 sec bei 2*10^9 und den sollten wir topen, ich arbeite jetzt gerade an einer Variante mit einer sortierten Liste.
Es gibt nur 1848 Hamming Zahlen <= 2^32, einfach alle als Konstanten im Programmcode ablegen und fertig ;)
Senior Sanchez
2005-10-18, 17:57:58
Es gibt nur 1848 Hamming Zahlen <= 2^32, einfach alle als Konstanten im Programmcode ablegen und fertig ;)
rofl, das is natürlich DIE variante *gg* ich glaube das dürfte mit abstand das schnellste sein ;)
EDIT:
Wobei mir auffällt, dass 1848 in der Quersumme 21 ist und wenn man betrachtet das diese kleiner 2^32 sind, wobei sowohl die basis als auch der exponent vielfache der primzahl 2 sind, muss man die 2 noch darauf addieren und kommt auf 23!!! :eek: Ich denke wir wissen alle, was das heißt.
Godmode
2005-10-18, 18:11:51
rofl, das is natürlich DIE variante *gg* ich glaube das dürfte mit abstand das schnellste sein ;)
EDIT:
Wobei mir auffällt, dass 1848 in der Quersumme 21 ist und wenn man betrachtet das diese kleiner 2^32 sind, wobei sowohl die basis als auch der exponent vielfache der primzahl 2 sind, muss man die 2 noch darauf addieren und kommt auf 23!!! :eek: Ich denke wir wissen alle, was das heißt.
nein? Illuminten? ;D
Senior Sanchez
2005-10-18, 18:20:32
nein? Illuminten? ;D
Ja, verdammt, die Illuminaten hängen da drin! Die haben eh überall ihre Finger drin.
Godmode
2005-10-18, 19:12:07
Was könnte ich gegen den Stackoverflow machen?
Neomi
2005-10-18, 20:31:24
Was könnte ich gegen den Stackoverflow machen?
Einen Stackoverflow darf es eigentlich nicht geben, zumindest nicht durch die Programmlogik selbst. Schon im 2er-Pfad wächst die Zahl sehr schnell. Nach 33 Aufrufen kann der Stack niemals voll sein, aber Variablen können überlaufen.
Beispiel 5er-Pfad, ziemlich am Ende des 2er-Pfades:
Die Grenze liegt bei 2147483648 (2^31), man ist bei 2^30 angelangt. 1073741824 * 5 ist 5368709120, paßt aber nicht mehr in einen 32 Bit Integer. Ein vorzeichenloser 32 Bit Integer geht nur bis 4294967295. Also wird das erste Bit abgeschnitten, übrig bleibt 1073741824. Diese Zahl ist wieder 2^30 und wird wieder mit 5 multipliziert, da sie kleiner als die Obergrenze ist. Es ist eine Endlosschleife entstanden, die dann sehr schnell den Stack zumüllt.
Es gibt mehrere Möglichkeiten. Du kannst z.B. die Obergrenze auf weniger als 1/5 des durch den Datentyp darstellbaren Maximalwertes beschränken oder den Datentyp vergrößern. Nachdem du die Zahl errechnet hast, kannst du sie auch wieder durch den Multiplikator teilen und prüfen, ob sie identisch zur Basis ist. Wenn sie das nicht ist, fand ein Überlauf statt. Alle Lösungen haben Nachteile, ob nun Flexibilität oder Geschwindigkeit.
Godmode
2005-10-18, 21:00:45
so jetzt gehts, für 10 Trilliarden brauch ich jetzt ca 0,985 Sekunden, das ist echt sau schnell!
Demirug
2005-10-18, 21:06:37
0,5 ms für 2^32. Allerdings noch in C#.
Senior Sanchez
2005-10-18, 21:13:11
0,5 ms für 2^32. Allerdings noch in C#.
0,5 ms???
Alter Schwede, kann man das überhaupt so genau messen? *g*
Demirug
2005-10-18, 21:15:08
0,5 ms???
Alter Schwede, kann man das überhaupt so genau messen? *g*
Ich habe es 1000 mal hintereinader in der Messschleife laufen lassen. Ich rechne BTW übrigens mit 64 Bit (32 BIT OS) wegen den dämlichen Überläufen.
Senior Sanchez
2005-10-18, 21:23:30
Ich habe es 1000 mal hintereinader in der Messschleife laufen lassen. Ich rechne BTW übrigens mit 64 Bit (32 BIT OS) wegen den dämlichen Überläufen.
Naaaaja, kann man dann so einfach durch 1000 teilen? Vllt schwirrt da noch was in den caches rum oder so?
Godmode
2005-10-18, 21:24:02
Ich habe es 1000 mal hintereinader in der Messschleife laufen lassen. Ich rechne BTW übrigens mit 64 Bit (32 BIT OS) wegen den dämlichen Überläufen.
Ist der Algorithmus recht optimiert oder nur gut überlegt? BTW wie speicherst du die Zahlen ab? Das mit dem AVL-Baum hat mir schon recht gut gefallen, wie siehst du das?
Demirug
2005-10-18, 21:30:44
Naaaaja, kann man dann so einfach durch 1000 teilen? Vllt schwirrt da noch was in den caches rum oder so?
Da kann nichts mehr im Cache sein weil ich komplett alles neu rechne.
Senior Sanchez
2005-10-18, 21:35:19
Da kann nichts mehr im Cache sein weil ich komplett alles neu rechne.
Ok, war eigentlich auch mehr ne rhetorische Frage, da ich mir eigentlich schon gedacht habe, dass dir son Fehler net unterläuft ;)
Demirug
2005-10-18, 21:39:22
Ist der Algorithmus recht optimiert oder nur gut überlegt? BTW wie speicherst du die Zahlen ab? Das mit dem AVL-Baum hat mir schon recht gut gefallen, wie siehst du das?
Besonders optimiert ist er nicht. Ich nutze nur das aus was Neomi schon geschrieben hat.
Ich habe einfach ein Array genommen dann kann ich nämlich den QSort von .Net (bzw. C) benutzten. C# habe ich benutzt weil dort die 64 Bit Werte schon eingebaut sind. Unter C war mir das zu viel gefummel ohne 64 Bit Compiler. Allerdings bin ich derzeit auf 200000 Werte begrenzt. Das reicht aber bis 1*10^18.
Senior Sanchez
2005-10-18, 21:51:02
Besonders optimiert ist er nicht. Ich nutze nur das aus was Neomi schon geschrieben hat.
Ich habe einfach ein Array genommen dann kann ich nämlich den QSort von .Net (bzw. C) benutzten. C# habe ich benutzt weil dort die 64 Bit Werte schon eingebaut sind. Unter C war mir das zu viel gefummel ohne 64 Bit Compiler. Allerdings bin ich derzeit auf 200000 Werte begrenzt. Das reicht aber bis 1*10^18.
Was hastn fürn System? Ich denke, die Frage sollte man vllt auch klären *gg*
Eventuell nen 64 Bit System? Merkste da Geschwindigkeitsmäßig nen Unterschied?
Demirug
2005-10-18, 21:58:38
Was hastn fürn System? Ich denke, die Frage sollte man vllt auch klären *gg*
Eventuell nen 64 Bit System? Merkste da Geschwindigkeitsmäßig nen Unterschied?
Ist ein A64 3000 läuft aber derzeit mit dem 32 Bit Windows XP. Die 64 Bit CPU nützt hier also nichts.
Godmode
2005-10-19, 10:47:44
Hab jetzt auch einen QSort integriert und komme nun bei 10Trilliarden auf 0,00000 Sek, ich brauche jetzt mal einen besseren Timer :)
#include <time.h>
#include "timer.h"
static clock_t ticks; /*global used in all functions*/
void startTimer() {
ticks = clock();
} /*startTimer*/
double interim() {
return (double)(clock() - ticks) / CLOCKS_PER_SEC;
} /*interim*/
void stopTimer() {
ticks = clock() - ticks;
} /*stopTimer*/
double elapsed() {
return (double)ticks / CLOCKS_PER_SEC;
} /*elapsed*/
ScottManDeath
2005-10-19, 11:40:18
Hab jetzt auch einen QSort integriert und komme nun bei 10Trilliarden auf 0,00000 Sek, ich brauche jetzt mal einen besseren Timer :)
#include <timers.h>
#ifdef WIN32
# include <windows.h>
static LARGE_INTEGER pc_freq;
static LARGE_INTEGER pc_t;
#elif defined ( __ia64__)
# include <altix_timer.h>
#else
# include <time.h>
#endif
void InitTimer()
{
#ifdef WIN32
QueryPerformanceFrequency(&pc_freq);
#elif defined (__ia64__)
altixtimer_init();
#endif
}
float GetTime()
{
#ifdef WIN32
QueryPerformanceCounter(&pc_t);
return (float)( (double)(pc_t.QuadPart)/(double)( pc_freq.QuadPart));
#elif defined (__ia64__)
return (float)altixtimer_currentSeconds();
#else
return (float) ( clock() ) /(float)(CLOCKS_PER_SEC);
#endif
}
Hatte ich gerade im Clipboard ;)
Demirug
2005-10-19, 11:43:09
#include <timers.h>
#ifdef WIN32
# include <windows.h>
static LARGE_INTEGER pc_freq;
static LARGE_INTEGER pc_t;
#elif defined ( __ia64__)
# include <altix_timer.h>
#else
# include <time.h>
#endif
void InitTimer()
{
#ifdef WIN32
QueryPerformanceFrequency(&pc_freq);
#elif defined (__ia64__)
altixtimer_init();
#endif
}
float GetTime()
{
#ifdef WIN32
QueryPerformanceCounter(&pc_t);
return (float)( (double)(pc_t.QuadPart)/(double)( pc_freq.QuadPart));
#elif defined (__ia64__)
return (float)altixtimer_currentSeconds();
#else
return (float) ( clock() ) /(float)(CLOCKS_PER_SEC);
#endif
}
Hatte ich gerade im Clipboard ;)
Aber nicht auf CuQ Systemen einsetzen.
Godmode
2005-10-19, 12:58:47
Aber nicht auf CuQ Systemen einsetzen.
kk, gut zu wissen
zeckensack
2005-10-19, 18:16:59
Aber nicht auf CuQ Systemen einsetzen.Was denn sonst?
Und das hat auch nicht direkt mit CnQ zu tun, sondern mit Microsofts Unfähigkeit beim Schreiben des Mehrprozessorkernels. Auf einem Single-CPU-System gibt's mit QPC und C'n'Q überhaupt keine Probleme. Die gibt's nur auf Multi-CPU-Systemen, liegt einzig und allein an Microsofts Unfähigkeit, und kann durch /usepmtimer behoben werden.
Mit C'n'Q direkt hat das rein garnichts zu tun. Multi-CPUs ohne SpeedStep/C'n'Q (oder halt deaktiviert) sind doch genauso betroffen.
Ich sehe derzeit keine bessere Möglichkeit als bei QPC zu bleiben und den "Kunden" zu sagen sie müssen /usepmtimer setzen. Wenn Microsoft so simple Sachen nicht patchen will, muss man sich eben selbst helfen.
edit:
@Topic,
die Hamming-Zahlen bis n sind abzählbar. Die Lösung schenke ich mir jetzt, weil wegen der dazu nötigen Integerdivision/-modulo sicher keine besonders schnelle Ausführungzeit für die ganze Reihe erreicht wird.
Aber nicht auf CuQ Systemen einsetzen.Mit /usepmtimer schon.
Edit: Zu spät.
Demirug
2005-10-19, 18:46:59
Was denn sonst?
Und das hat auch nicht direkt mit CnQ zu tun, sondern mit Microsofts Unfähigkeit beim Schreiben des Mehrprozessorkernels. Auf einem Single-CPU-System gibt's mit QPC und C'n'Q überhaupt keine Probleme. Die gibt's nur auf Multi-CPU-Systemen, liegt einzig und allein an Microsofts Unfähigkeit, und kann durch /usepmtimer behoben werden.
Mit C'n'Q direkt hat das rein garnichts zu tun. Multi-CPUs ohne SpeedStep/C'n'Q (oder halt deaktiviert) sind doch genauso betroffen.
Ich sehe derzeit keine bessere Möglichkeit als bei QPC zu bleiben und den "Kunden" zu sagen sie müssen /usepmtimer setzen. Wenn Microsoft so simple Sachen nicht patchen will, muss man sich eben selbst helfen.
Das Problem tritt leider auch bei Single CPUs auf weil sich durch CuQ die Frequenz verändern kann.
Man muss zyklisch von Zeit zu Zeit QueryPerformanceFrequency aufrufen um dem Problem zu entgehen.
zeckensack
2005-10-19, 19:01:51
Das Problem tritt leider auch bei Single CPUs auf weil sich durch CuQ die Frequenz verändern kann.
Man muss zyklisch von Zeit zu Zeit QueryPerformanceFrequency aufrufen um dem Problem zu entgehen.Also bei mir nicht.
Die Frequenz liegt bei mir immer bei konstant 1,19318MHz. A64, VIA-Chipsatz.
Demirug
2005-10-19, 19:06:35
Also bei mir nicht.
Die Frequenz liegt bei mir immer bei konstant 1,19318MHz. A64, VIA-Chipsatz.
Ist mir bei einem Kunden passiert. Chipsatz weiß ich leider nicht aber es war auf jeden Fall eine Singelcore CPU.
Jo, es gibt manche Pfusch-Chipsätze mit defektem HPT. So zerstört man effektiv ein gutes Konzept.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.