Algo zum Finden der kleinsten nichtverwendeten Zahl

volkard

jesters ding mit dem sortieren sehr schön, wenn man nix weiter über die zahlen weiß. und wenn sie ins ram passen.
geht es nur darum, eindeutige IDs zu vergeben, kann man auch parallel zu den eigentlichen daten eine liste der freien IDs mitführen. dann ist id-vergabe immer in O(1) mit leichten mehrkosten beim löschen von datensätzen. oder man nimmt einfach ne zufallszahl so lange, bis man eine findet, die nicht schon weg ist. dazu müßte es wesentlich mehr mögliche ids als vergebene ids geben.
wenn man nicht alles sortieren mag, sagen wir mal, es sind sehr viele daten und lesen ist noch ok, aber die 1000MB dreißgmal zu schreiben, wäre unhübsch. sagen wir mal die mäglichen ids sind 32-bittige ints. dann recht auch mehrstufiges zählen. man macht int count[256]={0}; und läuft durch die daten und macht immer ++count[erstesByte(aktuellerSatz.id)]. ist der bereich, wo 17 das erste byte ist, voll bestückt, dann ist count[17]==256*256*256. finde also den ersten bereich, der nicht voll bstückt ist. bearbeite bei dem bereich dann das zweite byte. so mußte dann die gesamten daten viermal ganz lesen, was schnuckeliger ist, als eine komplette sortierung.
ach, platz für 65536 ints haben wir im ram. also mach's nur zweistufig.

volkard

frosty schrieb:

Wenn ichs richtig verstehe, willst Du von kleinsten Element x die Zahl x-1 finden. Da würde ich nur alle Elemente durchgehen und den kleinsten Wert im Array speichern. Und nach durchlaufen des Array einfach ne 1 abziehen. Brauch insgesamt nur O(n).

ich denke, normalerweise ist x-1 keine gültige zahl.

Danke euch dreien.

Werd's dann wohl so machen, dass ich ab einer bestimmten Listengröße borher sortiere und dann nach der ersten Lücke schauen.

Volkards Weg schau ich mir morgen nochmal ausgeruht an

Die Elementanzahl liegt wohl zumeist bei 5000-100000 und die Werte sind ULONGs wobei die ersten Lücken enstehen, wenn ca. die Zahl 1000 vergeben wurde und dann schätz ich gibt es so alle 500-1000 eine neue Lücke.

Naja, sooo zeitkritisch ist es jetzt auch wieder nicht, wollte nur nicht bei der Grobklotzmethode bleiben.

otze

wodurch entstehen denn die lücken?
wenn sie beim löschen von einträgen entstehen, kannst du ja eine queue mit den entfernten ids führen. wenn die Liste leer ist, erstellst du einfach als id eine zahl mit der anzahl deiner elemente als wert

if(!idQueue.empty()){
     id=idQueue.front();
     idQueue.pop();
}
else
{
    id=elements.size();
}

volkard

oder nimmst immer ne zufallszahl. macht bei 100000 benutzen ids und 4Mrd möglichen ids ne wahrscheinlichkeit von 1 zu 40000, daß du ne besetzte getroffen hast. also fast immer nur einmal durchlaufen, um zu sehen, ob die id frei ist. ganz selten zweimal, extrem extrem selten dreimal usw.

@otze: ich denke, die frei-liste liegt nicht im ram, sondern muss auf der platte liegen. klang irgendwie danach.

edit: nee. so dicht, wie die ids bei fortlaufender vergabe sind, kann man sie als array-indezes verwenden. also dicht machen.

maximAL

volkard schrieb:

frosty schrieb:

Wenn ichs richtig verstehe, willst Du von kleinsten Element x die Zahl x-1 finden. Da würde ich nur alle Elemente durchgehen und den kleinsten Wert im Array speichern. Und nach durchlaufen des Array einfach ne 1 abziehen. Brauch insgesamt nur O(n).

ich denke, normalerweise ist x-1 keine gültige zahl.

wieso?

volkard

maximAL schrieb:

volkard schrieb:

frosty schrieb:

Wenn ichs richtig verstehe, willst Du von kleinsten Element x die Zahl x-1 finden. Da würde ich nur alle Elemente durchgehen und den kleinsten Wert im Array speichern. Und nach durchlaufen des Array einfach ne 1 abziehen. Brauch insgesamt nur O(n).

ich denke, normalerweise ist x-1 keine gültige zahl.

wieso?

wegen

Mir fällt nix bessres ein, als mit 1 anzufangen, in allen Elementen nachzuschauen, und wenn die Zahl drin vorkommt, um eins hochzuzählen.

dein algo würde immer nur 0 sagen. außer, die 0 ist auch belegt. dann vielleicht unsigned(-1). und das immer, obwohl unsigned(-1) belegt ist. ungültig im sinne deines verfahrens.

PeterTheMaster

was soll denn das mit den zufallszahlen?
warum nicht einfach maximum finden und um 1 hochzaehlen? dann hat man zusaetzlich noch einen anhaltspunkt, wie alt die datenbank ist. und dann noch einen extraknopf zum ueber nach kompaktifizieren, falls man sich mit dem maximum gefaehrlich dem datentyp maximum naehert.

volkard

PeterTheMaster schrieb:

was soll denn das mit den zufallszahlen?
warum nicht einfach maximum finden und um 1 hochzaehlen? dann hat man zusaetzlich noch einen anhaltspunkt, wie alt die datenbank ist. und dann noch einen extraknopf zum ueber nach kompaktifizieren, falls man sich mit dem maximum gefaehrlich dem datentyp maximum naehert.

kompaktifizieren kann aufwendig zu programmieren werden, wenn viele andere tabellen sich auf die id beziehen.

TGGC

Jester schrieb:

Alternativ kannst Du auch ein Array von Bits nehmen, alle auf 0 setzen und dann die Liste durchgehen und wenn Du die Zahl k findest, dann kippst Du das Bit an Stelle k von 0 auf 1. Kostet O(n). Danach einfach noch ein Bit suchen, daß noch 0 ist. Dann haste auch ne Zahl gefunden, kostet ebenfalls nochmal O(n). Kann aber dafür, wenn auch sehr große Zahlen vorkommen viel Speicher brauchen.

Nein, du brauchst nur soviel Bits, wie Einträge in der Liste sind. Größere Zahlen als n sind uninteressant.

Bye, TGGC

volkard

TGGC schrieb:

Nein, du brauchst nur soviel Bits, wie Einträge in der Liste sind. Größere Zahlen als n sind uninteressant.

sagen wir mal ein bitfeld mit 32000byte ist nie ein problem, also 262000 bits. drüber könnte sein, daß der cache nicht mehr das ganze bitfeld abdeckt. aber was soll's, ist immernoch schneller als die dazen zweimal lesen. wenn's nicht gerade viele millionen werden, ist das bitfeld gar nicht so teuer. und bei größeren mengen ist das bitfeld immernoch die beste endstufe zu mehrstufigen zählen.

auf platte kann die frei-id-liste leicht gehalten werden. der erste int sagt, wie lang die datei ist und der rest wird als stack interpretiert.

frosty

volkard schrieb:

ich denke, normalerweise ist x-1 keine gültige zahl.

dein algo würde immer nur 0 sagen. außer, die 0 ist auch belegt. dann vielleicht unsigned(-1). und das immer, obwohl unsigned(-1) belegt ist. ungültig im sinne deines verfahrens.[/quote]

Das Verfahren liefert eine gültige Zahl. Nämlich das Infimum der Array-Elemente.

TGGC

volkard schrieb:

auf platte kann die frei-id-liste leicht gehalten werden. der erste int sagt, wie lang die datei ist und der rest wird als stack interpretiert.

Dateigrösse geteilt durch 4 gibt auch die Länge.

Bye, TGGC

volkard

frosty schrieb:

Das Verfahren liefert eine gültige Zahl. Nämlich das Infimum der Array-Elemente.

witz komm raus.
die elemente sind bezüglich des "-1"-rechnes zyklich, aber bezüglich des vergleichs mit < eine kette.
also wenn x das minimum aller elemete ist, dan muß x-1 noch lange nicht kleiner als alle elemente sein. denn es ist nicht sicher, daß x-1 kleiner als x ist.

frosty

volkard schrieb:

frosty schrieb:

Das Verfahren liefert eine gültige Zahl. Nämlich das Infimum der Array-Elemente.

witz komm raus.
die elemente sind bezüglich des "-1"-rechnes zyklich, aber bezüglich des vergleichs mit < eine kette.
also wenn x das minimum aller elemete ist, dan muß x-1 noch lange nicht kleiner als alle elemente sein. denn es ist nicht sicher, daß x-1 kleiner als x ist.

Die Mathematik sagt aber aber was gaaanz anderes. Das kleinste Element -1 ist bei einem Interger das Infimum. Das einzige Problem kann das sein das man min_int hat und somit ein Unterlauf vorkommt. in dem Fall kann man aber kein kleineres Element als das kleinste im Array finden.

Und man sollte schon in ersten Schuljahr gelernt haben, das eine Zahl kleiner wird wenn ich eins abziehe!

volkard

frosty schrieb:

Das einzige Problem kann das sein das man min_int hat und somit ein Unterlauf vorkommt.

davon rede ich doch die ganze zeit, du nase. nur, daß ich von unsigned int ausgehe. ist aber egal. gleiches problem. dein algo ist nicht zuverlässig.

in dem Fall kann man aber kein kleineres Element als das kleinste im Array finden.

und deswegen ist die suche nach einem unbelegten element nicht fein auf die suche nach dem kleinsten element zurückzuführen.

Und man sollte schon in ersten Schuljahr gelernt haben, das eine Zahl kleiner wird wenn ich eins abziehe!

und dann studiert man informatik und lernt, daß das nur ausnahmen sind, wo das immer gilt. selbst mein taschenrechner hört nach ca 10^14 mal "ein-abziehen" damit auf, dran zu glauben. also 10^14-1-1014==0. komisch, gell?

frosty

Tja, dann hättest Du aber mal besser im Studium aufpassen sollen. Dann hättest Du jetzt Ahnung von dem Du da schreibst.

volkard

frosty schrieb:

Tja, dann hättest Du aber mal besser im Studium aufpassen sollen. Dann hättest Du jetzt Ahnung von dem Du da schreibst.

sei x ein int.
dann ist (x-1)<x nicht immer wahr. hast du was anderes gelernt?

frosty

Tja, das ist mir eigentlich viel zu doof dir jetzt ne Nachhilfe in Mathe und technischer Informatik zu geben. Und auch darüber in den Ursprungspost was rein zu interpretieren was da nicht steht.

SeppSchrot schrieb:

Hallöle,

ich möchte aus einer ungeordneten Liste, deren Elemente aus jeweils einer ganzen Zahl bestehen, die kleinste Zahl finden, die nicht vorkommt.

Da steht nichts über den Wertebereich. Nur das er ganzzahllich ist. Die Sonderfälle müßen natürlich wie immer berücksichtigt werden. Das ist selbstverständlich.

Jester

TGGC schrieb:

Jester schrieb:

Alternativ kannst Du auch ein Array von Bits nehmen, alle auf 0 setzen und dann die Liste durchgehen und wenn Du die Zahl k findest, dann kippst Du das Bit an Stelle k von 0 auf 1. Kostet O(n). Danach einfach noch ein Bit suchen, daß noch 0 ist. Dann haste auch ne Zahl gefunden, kostet ebenfalls nochmal O(n). Kann aber dafür, wenn auch sehr große Zahlen vorkommen viel Speicher brauchen.

Nein, du brauchst nur soviel Bits, wie Einträge in der Liste sind. Größere Zahlen als n sind uninteressant.

Jo, das ist ein geiler Trick! Dadurch braucht man viel weniger Speicher. Man findet schön kleine Ids und wenn doch voll ist, dann gibt's keine Lücken. => Neue Zahl: Einfach n nehmen.

@frosty: Wo ist genau Dein Problem? Durch den beschränkten Wertebereich von Zahlentypen ist x-1 < x nicht immer wahr, egal ob signed, oder unsigned. Außerdem hat Deine Methode den Nachteil, daß sie keine Lücken ausfüllt. Insgesamt ist das also nicht gerade ein Grund vor lauter Zufriedenheit mit sich selbst auch noch beleidigend zu werden, oder?

MfG Jester