Supportnet Computer
Planet of Tech

Supportnet / Forum / Anwendungen(Java,C++...)

Riesige dynamische Liste in C++ und Speicherverbrauch





Frage

Hi Leute Ich programmiere zur Zeit ein Prog. das alle Primzahlen bis 5 Millionen ausgeben soll. Dazu generiere ich eine verkettete Liste aus folgenden Elementen [b]struct[/b] zahl { [b]bool[/b] prim_ok; [b]struct[/b] zahl *next; }; Das Problem ist nun, daß er für die 5 Millionen Elemente in der Liste meine Auslagerungsdatei auf 450 MByte erhöht obwohl ich eh schon 512 MByte RAM habe. Auf gut deutsch: ein mörderischer Speicherverbrauch. Gibt es eine Möglichkeit, sowas speicherschonend zu programmieren, so daß ich auch bis 10 Millionen testen kann??? Ich habe es schon mit einem Array versucht, aber das steigt er bei 1 Mio. Elementen mit einem Ausnahmefehler komplett aus. Klingt vielleicht etwas heikel, aber ich hoffe es kann mir trotzdem jemand helfen! Andi

Antwort 1 von silvershadow

Hi Andi!

Was willst du damit erreichen? Ein Proggie nistet sich zur Laufzeit nunmal im Speicher ein und bei 5 Millionen Listenelementen...

Wenn du nur einfach die Zahlen berechnen willst und ne grösse Festplatte hast (und viel Zeit für das öffnen des Textfiles :-), dann würde ich einfach nur die Primzahlen in ein Textfile schreiben.

Das hättest du sicher auch selber gemacht, doch die Frage ist eben, was du mit der Liste willst?
Dein Rechner an den Rand des Wahnsinns treiben?? :-))))

Gruss
Chris

Antwort 2 von Harald Boehm

Hallo,

wieviel Primzahlen gibt es denn ungefähr in diesem Wertebereich bis 5 Millionen? Kann man das abschätzen oder irgendwo nachlesen?

Hier bieten sich doch eigentlich malloc() und free() an.

Du testest lediglich auf eine Primzahl, wenn es eine ist, bleibt sie in der Liste, falls nicht, wird das entsprechende Element aus der Liste entfernt. Dynamische Speicherverwaltung.

Gruß,

Harald







Antwort 3 von Rudi13

Hi Andi222!

Schon mal daran gedacht, daß mit Ausnahme der "2" nur ungerade Zahlen Primzahlen sind ? Also brauchst Du höchstens 2,5 Mio. Elemente oder anders ausgedrückt kannst Du mit rund 5 Mio. Elementen die Primzahlen bis 10 Mio. speichern.
Also erst überlegen, dann programmieren!
Q&D (Quick AND Dirty) sollte ausgedient haben.
Wenn Microsoft solche Programmier-Spezialisten wie dich beschäftigt, wundert mich nicht mehr warum Windows XP soviel Speicherplatz und Ressourcen frißt :-))
Und das mit den geraden Zahlen ist nur ein Beipiel!

Antwort 4 von Andi222

Danke für Eure Antworten.

Vielleicht sollte ich daß Prinzip etwas erläutern:
Es nennt sich "Sieb des Erastothenes"

Man erzeugt eine Liste und belegt den Wert jedes Elementes mit 1.
Dann zählt man einfach die Vielfachen von 2,3,5,7,11 u.s.w. ab und ändert den Wert der Vielfachen zu 0.

Alle Elemente in der Liste, die am Ende noch den Wert 1 haben, sind Primzahlen. Die Primzahl ergibt sich also nur aus der Position in der Liste.

Mich wudert eben, daß bei 5 Millionen Elementen ca, 900MByte vollgeballert werden, da pro Element doch nur ein Byte für BOOL und 8 Byte für die Adressen benötigt werden sollten.
Das dürfte nur 45 MByte belegen !?

@Silvershadow: Das mit dem Textfile klingt gut.
Allerdings ist die Liste aller Primzahlen bis 5 Mio. schon 3.6 MByte groß. Somit könnte sich daß Problem dann nur auf das Dateiöffnen verlagern.
Ich werd's mal versuchen.

@Rudi: Wenn ich jedes 2. Element nicht belege, tue ich mich schwer die restlichen Vielfachen einfach abzuzählen.
Außerdem bin ich kein Spezialist, ich fange gerade erst mit C an.
Trotzdem hast Du mit Deiner Vermutung bez. Microsoft wohl recht ;-)

Andi

P.S. Mein erstes Optimierungziel war, die Berechnugszeit zu verringern: von 7 Minuten auf 1.5 Sekunden bei Primzahlen bis 100000).

Antwort 5 von Rudi13

Hi!

natürlich kenne ich den Algorithmus "Sieb des Erathostenes", aber in der Literatur steht auch unter Nachteile: "Langsam und bei hohen Zahlenbereichen großer Speicherverbrauch".
Zugegeben, bei mir ist es schon etwas länger her, aber man kann doch auch nur von ungeraden Zshlen die Vielfachen bilden ?! Da die Multiplikation iner geraden Zahl mit einer ungeraden Zahl IMMER eine gerade Zahl ergibt, kann ish mir das ersparen. Also müßte es reichen, von ungeraden Zahlen die ungeraden Vielfachen zu bilden!
Habe leider keine Möglichkeit, dies zu testen hier im Büro, habe es aber bis 100 mal auf einem Zettel getestet :-)

Antwort 6 von draack

Hi!

Du kannst den Speicherverbrauch erheblich reduzierenn, indem Du etwas Bitlogik verwendest. Denn eigentlich musst Du Dir ja nur jede Zahl bis 5 Millionen markieren, ob es sich um eine Primzahl oder nicht handelt. Die Zahl selbst ergibt sich aus der Position des Bits. 5 Mio. Bits sind ca. 611 kByte - also kein Problem. Eine verkettete Liste ist hier einfach fehl am Platz.

Ciao!
Volker.


Antwort 7 von Harald Boehm

Lösungsvorschlag (allerdings nicht ganz der Aufgabenstellung entsprechend):

// Sieb des Eratosthenes (sde)

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

char * sde(unsigned long max)
{
long index, counter;
char *primzahl;

if (!(primzahl = new char[max+1]))
return 0;


for (counter = 3; counter <= max; primzahl[counter] = 1, counter += 2);


for (counter = 3; counter*counter <= max; counter+=2)

if (primzahl[counter])

for (index=counter*counter; index <= max; primzahl[index]=0, index+=(counter<<1));

return primzahl;
}

void ausgabe(char *primzahl, unsigned long max)
{
unsigned long index;


if (2 < max)
cout << 2 << endl;


for (index=3; index <= max; index+=2)
if (primzahl[index])
cout << index << endl;
}

int main()
{
unsigned long max=5000000;
char *primzahl;

if (!(primzahl = sde(max)))
cerr << "Ich brauche mehr RAM. Und zwar schnell!!" << endl;
else
{
ausgabe(primzahl, max);
delete [] primzahl;

}
return 0;
}

Antwort 8 von Andi222

Hi Leute, Ihr seid großartig!!!

@Harald
Danke, wenn ich etwas Zeit finde, schau ich mir das mal genauer an.

@Rudi13
Ja Du hast recht!
Allerdings reduziert sich das Problem dann nur um die Hälfte. Sollte mich mal der Wahnsinn packen und ich will alle Primzahlen bis 1 Mrd. testen, bringt es nicht wirklich Besserung.

Ich kenne keine anderen Algorithmen, deshalb kann ich nicht sagen, ob das "Sieb" langsam ist. Bei mir (Athlon XP2000+ mit 266-DDR-Ram CL2) berechnet er alle Primzahlen bis 5 Mio. in 2 Minuten 20 Sekunden.
In meiner Naivität würde ich mal behaupten, daß das soo schlecht nicht ist ;-)
Der andere Nachteil ist genau mein Problem :-(

@Volker
Klingt sehr interesant.
Wie erzeugt man einen Typ mit 5 Mio. Bit?

Andi

Antwort 9 von semi


unsigned char *bitset = new unsigned char[625000];
...
...
delete [] bitset;


625000 * 8Bit = 5Mio. Bit

Antwort 10 von Andi222

Ist klar.

Kann man dann aber das 4 millionste Bit direkt auswählen??
Oder muß ich dann das n-te (0-7-te) Bit im x-ten Element des Arrays auswählen?

Im letzteren Fall wäre es doch besser, ein Array aus long zu erstellen, da dann erst nach 32 Bit der Sprung ins nächste Element kommt.
Oder gibt es da Einschränkungen??

Danke

Andi

Antwort 11 von Harald Boehm

Obiges Codebeispiel braucht circa 1 Minute.
Und hierbei noch ein seltsames Phänomen: startet man das Programm direkt nach dem Compilieren, braucht es grade mal 20 Sekunden?!

Probeweise habe ich es auch mit 50000000 Zahlen versucht, lief auch, habe es dann allerdings aus "naheliegenden" Gründen nach 10 Millionen Zahlen abgebrochen.

Compiler: GCC (MingW32) ohne irgendwelche Optimierungen in der Kommandozeile, BS WinXP, Rechner XP1800, 256 MB Ram.

Gruß,

Harald

Antwort 12 von semi

ca. 30 Sekunden bei K6 450MHz, Festplatte im PIO Mode!
Alle Primzahlen im Bereich [5..5000000]


#include <iostream.h>
#include <math.h>

int main() {

  long z=5L, rest, teiler, limit;
  while(z<5000000L) {
    for(;;) {
      limit = 1L+long(sqrt(double(z)));
      teiler = 1L;
      do {
        teiler += 2L;
        rest = z % teiler;
      } while (rest > 0L && teiler < limit);
      if(rest > 0L && teiler >= limit)
        break;
      z += 2L;
    }
    cout << z << endl;
    z += 2L;
  }

}


Kompilieren mit: cl dumpprim.cpp (Standardoptimierung)
Aufruf mit: dumpprim > out.txt

Die langsamsten Operationen hier sind sqrt, cout und die casts.

Wie schnell ist es auf Euren Rechnern?

Gruss,
Michael

Antwort 13 von Harald Boehm

@semi

12 Sekunden.

Gruß,

Harald

Antwort 14 von semi

Sch... ich brauche dringend einen neuen Rechner :-)


Antwort 15 von Andi222

ca. 9 Sekunden

@Semi
Sei froh, daß Du es nicht auf meine Weise versucht hast ;-)

Kann es sein, daß es an der Grenze des Wertebereiches (ca. 4 Mrd.) zu Rundungsfehlern beim Divisionsrest kommt??

Wen's interessiert:
Ich hab die Dynamische Liste rausgeschmissen (war eigentlich auch eher zwecks des Übens).
Ich schreibe jetzt Liste mit 1 Byte pro Element in einen Stream (quasi "Datei im RAM").
Dadurch wird pro Zahl nur 1 Byte verschwendet.
Aber wahnsinnig langsam ist es im Vergleich zu Semi's Lösung :-(

Aber wozu braucht man sonst einen XP2000+ ?? *gg*

Andi

Antwort 16 von semi

Wie wäre es mit 1 Bit pro Zahl, wie Volker vorgeschlagen hat?
Hier ein Beispiel eines Bitsets mit 2 Byte. Das kann man beliebig stappeln :-)

#include <iostream.h>

inline bool getBit(unsigned char *bs, int n) {
  return ((bs[int(n/8)] & 1<<(n%8)) > 0);
}

inline void setBit(unsigned char *bs, int n, bool v) {
  if(v) bs[int(n/8)] |= 1<<(n%8);
  else bs[int(n/8)] &= (255-(1<<(n%8)));
}

int main() {

  unsigned char *bs = new unsigned char[[b]2];

  bs[0]  = 255; // 1111 1111 <-lsb
  bs[1] =  128; // 1000 0000 <-lsb

  setBit(bs,  3, 0); // bs[0] ist 1111 0111
  setBit(bs,  7, 0); // bs[0] ist 0111 0111

  setBit(bs,  8, 1); // bs[1] ist 1000 0001
  setBit(bs, 12, 1); // bs[1] ist 1001 0001

  for(int i=0; i<16; i++)
    cout << "Bit:" << i << " = " << getBit(bs, i) << endl;

  delete [] bs;
  return 0;

}

Beachte dass Bit 1 an der Stelle 0 ist!


Macht Spass wieder etwas mit C++ rumzuspielen. Ich habe seit ziemlich langer Zeit nichts damit gemacht.
Sch... Java macht faul :-)

Gruss,
Michael

Antwort 17 von Jo

Die Idee, dass das Sieb des Erastothenes langsam sein soll, finde ich schon witzig.

Unter Berücksichtigung der Tatsache, dass die Divisions-Rest-Methode für jedes Element n (sqr(n)+1)Gleitkommaoperationen durchführen muss, und das Sieb im Prinzip mit Addition auskommt, kann man es wohl kaum als langsam bezeichnen.

Tatsache ist, das für grosse Zahlenbereiche das Initialisieren des Zahlenbereichs schon fast am längsten dauert.

Das Sieb ist etwa Faktor 5-10 schneller als die Divisions-Rest-Methode.

Das mit dem Speicherverbrauch stimmt.


Antwort 18 von semi

@Jo
Kannst Du ein Beispiel bringe, dass die gleiche Ausgabe macht, wie das aus Antwort 12? Wieviele Iterationen pro Zahl braucht es? Wieviele insgesamt?

Antwort 19 von Andi222

OK, ich hab mal meins reinkopiert.

Die Prüfung geht aber nur bis 1 Mio. damit es keine Speicherprobs. geben sollte.
Die Ausgabe erfolgt sowohl auf dem Screen als auch in eine Textdatei.

Die Zahl der Iterationen pro Zahl ist "Obergrenze durch Zahl" (500k für 2; 333.3k für 3; 200k für 5 u.s.w.)
Die Anzahl der gesamten Iterationen hängt von der Anzahl der Primzahlen im Testbereich ab, da nur die Vielfachen von Primzahlen durch das Sieb fallen, d.h. gelöscht werden.
Läßt sich schlecht abschätzen, aber Du könntest ein Programm schreiben ;-), daß die Textdatei ausliest, und Anhand der Anzahl die Iterationen pro Primzahl und die Gesamtiterationszahl berechnet...


#include<stdio.h>


void main()
{
	long vielfach = 1;
	const limit=1000000;
	FILE *prim;

/* Listenelement deklarieren */
	struct nr {
		char c;
		struct nr *next;
		  } *no,*first, *p;
		
/* Listenelemente der ANzahl limit erzeugen und mit 1 belegen */
	first=new nr;
	first->c='1';
	no=new nr;
	no=first;
	no->next=NULL;


	for(int i=0; i<limit;i++) 
	{
			p=new nr;
			p->next=NULL;
			no->c='1';
			no->next=p;
			no=p;
	}

/* Primzahlberechnung starten */
	for (;vielfach*vielfach <= limit;)	
	{
		no=first;
		vielfach++;
		for(int j=0;j<vielfach;j++) no=no->next;
		for (;no->c=='0';j++) no=no->next;
		 vielfach=j; 
                   printf("Teste Vielfache von %d\n",vielfach);
		
/* Vorlauf, um zu testende Zahl auszuschließen */
		no=first;
		for(j=0; j<vielfach; j++) no=no->next;

	/* Jede n-te Zahl wegstreichen */
		for(i=0; i<limit; i+=vielfach)
		{
		/* Liste im Wert n vorspringen */
			for(int j=0;j<vielfach && no->next!=NULL;j++) no=no->next;
			no->c='0';
		}

	}

/* --- output --- */

/* Ergebnisdatei öffnen */
prim = fopen( "prim.txt", "w" );
no=first;

for (i=0;i<limit;i++)
{
	if(i>1 && no->c=='1') 
	{
		printf("%d \n",i); 
		fprintf(prim, " %d \n",i );
	}
	no=no->next;
}
fclose( prim );
printf("Ausgabe der Primzahlen in die Datei \"prim.txt\"\n");
}


Andi

Antwort 20 von Andi222

Hi Leute, nochmal ich:

Das obere Beispiel könnt Ihr knicken.
Die Dynamische Liste muß in C++ einen Wahnsinnigen Overhead haben. Außerdem dauern die permanenten Adresszuweisungen ewig.

Hier neues optimiertes Bsp.:
Testet bis 10 Mio.
Dauer bei mir (XP2000+): ca. 5 Sekunden (obwohl es auch die geraden Zahlen testet)
Ausgabe erfolgt in Datei: prim.txt

@Semi
Ich habe den Großteil Deines Codes aus Antwort 16 verwendet, ich hoffe, Du bist mir nicht böse!
Noch mal Danke!!!!!


#include <iostream.h>
#include<stdio.h>

inline bool getBit(unsigned char *bs, long n) 
{
	return ((bs[int(n/8)] & 1<<(n%8)) > 0);
}

inline void setBit(unsigned char *bs, int n, bool v) 
{  
	if(v) bs[int(n/8)] |= 1<<(n%8);
	else bs[int(n/8)] &= (255-(1<<(n%8)));
	return;
}

void main() 
{  
	FILE *prim;
	const limit=1250000;
	long vielfach=1;
    unsigned char *bs = new unsigned char[limit];
  
	/*Liste erzeugen und mit 1 vorbelegen */
	for(int i = 0; i< limit; i++) bs = 255;

	
	for(;vielfach*vielfach/64<=limit*8;)
	{
		do
		{
			vielfach++;
		}
		while (!getBit(bs, vielfach));

		printf("Teste Vielfache von %d \n", vielfach);
	/* Vielfache aussortieren*/
		for (i=2*vielfach;i<limit*8; i+=vielfach)
			setBit(bs, i, 0);
	}

	/*Ausgabe*/
 	prim = fopen( "prim.txt", "w" );
	printf("Schreibe Ausgabe in Datei \"prim.txt\"\n");
	
	for(i=2; i<limit*8; i++)    
  		if(getBit(bs, i)) 
			fprintf(prim,"%d\n", i);
	delete [] bs;
	fclose( prim );
}


Andi

Antwort 21 von semi

Ich habe da noch kleinen Verbesserungsvorschlag.
Die wesentlichen Änderungen sind fett hervorgehoben.

#include <stdio.h>
#include <string.h>

#define MAXINT 0xFFFFFFFF

inline bool getBit(unsigned int *bs, long n) {
  return ((bs[[b]n>>5] & 1<<(n%32)) > 0);
}

inline void setBit(unsigned int *bs, long n, bool v) {
  if(v) bs[[b]n>>5] |= 1<<(n%32);
  else bs[[b]n>>5] &= (MAXINT-(1<<(n%32)));
  return;
}

void main() {

  FILE *prim;
  const limit=312500L, ll=limit*32L;
  long vielfach=1L, i;

  unsigned int *bs = new unsigned int[limit];
  /*Liste erzeugen und mit 1 vorbelegen */
  memset((void *)bs, MAXINT, sizeof(unsigned int)*limit);
  //for(int i = limit-1; i>=0 ; i--) bs = MAXINT;


  for(;(vielfach*vielfach/64)<=ll;) {
    while(bs[vielfach]==0) vielfach += 32;
    do { vielfach++; } while(!getBit(bs, vielfach));

    printf("Teste Vielfache von %d \n", vielfach);
    /* Vielfache aussortieren*/

    for(i=(vielfach<<1);i<ll; i+=vielfach)
      setBit(bs, i, 0);

  }

  /*Ausgabe*/
  prim = fopen( "prim.txt", "w" );
  printf("Schreibe Ausgabe in Datei \"prim.txt\"\n");

  for(i=2; i<ll; i++)
    if(getBit(bs, i))
      fprintf(prim,"%d\n", i);
  fclose( prim );
  delete [] bs;
}


Ich glaube jetzt sollte es gut sein :-)

Gruss,
Michael

Antwort 22 von semi

Da habe ich wohl einen Fehler gemacht.

long v; // irgendwo am Anfang
...
...
v = vielfach>>5;
while(bs[v++]==0) vielfach += 32;

statt

while(bs[vielfach]==0) vielfach += 32;

Der Sinn des ganzen ist, alle 32Bit gleichzeitig zu prüfen, statt jedes einzeln. Sehr grossen Geschwindigkeitsunterschied bringt es aber nicht.


Ich möchte kostenlos eine Frage an die Mitglieder stellen:


Ähnliche Themen:


Suche in allen vorhandenen Beiträgen: