Spielen mit long

hi liste,

in der elektrotechnik-uni von meinem mitbewohner wurde heute folgende
aufgabe gestellt.

ziel ist es, einen c-code zu entwickeln, welcher in einer datei, welche
4000000000 longs enthält (alles verschiedene), den kleinsten fehlenden
long findet.
mich würde interessieren ob jemand der mathe gurus unter euch eine
ahnung hat, wie dieses problem zu lösen wäre, natürlich nur wenn jemand
zeit und lust dazu hat.

mfg
lukas

: lukas pitschl | dressy vagabonds

Hallo Lukas,

darf es auch statistisch, und nicht mathematisch sein? Dann ist es LONG_MIN;
diese Zahl hat naemlich eine grosse Wahrscheinlichkeit, die gesuchte Zahl zu
sein. (SCNR)

Ok, die Zahl ist mit Sicherheit in [LONG_MIN, LONG_MIN + 4e9].
Wenn du diesen Wertebereich in ein bitmap zwaengst, wobei jedes Bit fuer eine
Zahl steht, kommst du auf 4e9/8 = 500e6 Bytes (< 500MB).

unsigned char bitmap[SIZE]; // steht fuer den Wertebereich [min, min + 8 *
SIZE -1]
Die Adresse einer beliebigen Zahl X ist dann: (X - min) / 8,
und das Bit hat die Nummer (X - min) % 8.

Fuer jede gelesene Zahl im File setzt du das betreffende Bit auf 1. Am Ende
des Files suchst du nach dem dem ersten char, der nicht den Wert 255 hat.
Wenn ein bitmap von ca. 500MB zu gross ist, definiere SIZE ein wenig kleiner,
und baust eine Schleife um den ganzen Krempel, mit min = LONG_MIN, LONG_MIN +
8 * SIZE, LONG_MIN + 2 * 8 * SIZE, usw. Das heisst, du musst die Datei
mehrmals einlesen. Die Schleife kannst du beenden, sobald die erste Zahl
gefunden ist.

Ob das die schoenste Loesung ist, weiss ich nicht, aber wahrscheinlich ist es
die einfachste zu implementieren :slight_smile:
Diesen Algorithmus in C zu giessen, sei dann Hausaufgabe deines Mitbewohners.

HTH,
Thomas

PS:
Schwerer ist es, denke ich, das File mit 4000000000 _verschiedenen_
_zufaelligen_ Zahlen zu erstellen. *g*

Ich würde das so angehen.

Es gibt einige sorting algorithms, z.B. Quick Sort, die mit einer
"Grössenordnung" von n*log(n) arbeiten. Damit erhält man einen Array mit
allen longs, der Größe nach geordnet.
Dann müsste man diesen Array mit einem kompletten Array, der alle Longs
zwischen 0 und dem Maximum erhält, vergleichen. (-> "Größenordnung" n)

Das erste Feld, das nicht übereinstimmt, ist der kleinste fehlende long.

Zeitbedarf:

T(n) = C + n*log(n) + 3*n

PS: ich hoffe ich hab da nichts vergessen, müsste aber funktionieren.
Den "Spass", das in C zu schreiben, überlass ich gern jemand anderem :wink:

Deinen Rechner moechte ich haben! *g*
Der Speicherverbrauch dieses Algorithmus' betraegt
2 * 4000000000 * sizeof(long)
also ca. 32GB (bei long = 32bit), ungefaehr das 8-fache an Speicher, was ein
32-Bit-Rechner theoretisch adressieren kann.
Nun ist mir endlich klar, wozu man heutzutage 64 bit "braucht"...

Nichts fuer ungut,
Thomas

Vielen Dank für die Lösungen, wird sofort in tat umgesetzt :smiley:

mfg
lukas

: lukas pitschl | dressy vagabonds

das könnte bei einer 16gb file (so gross soll das file mit den
4000000000 werden) sehr sehr lange dauern, seh ich das richtig?

: lukas pitschl | dressy vagabonds

Ist ziemlich wahrscheinlich. Ausserdem darfst du nicht auf die
standard-funktion lseek() zurueckgreifen. Siehe auch
http://www.suse.de/~aj/linux_lfs.html

Thomas

Ich würde, um die Korrektheit des Programms zu überprüfen, mit einer kleinen
Zahl z.B. 20 longs anfangen, wo man händisch überprüfen kann, ob das stimmt.

Die Komplexität, die ich so über den Daumen berechnet habe, ist für worst
case, in best case wäre es
T(n)=C1 + n*log(n) + C2

:slight_smile: