Algo zum Finden der kleinsten nichtverwendeten Zahl
-
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.
-
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.
-
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
-
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.
-
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.
-
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
-
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.
-
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!
-
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 1014-1-1014==0. komisch, gell?
-
Tja, dann hättest Du aber mal besser im Studium aufpassen sollen. Dann hättest Du jetzt Ahnung von dem Du da schreibst.
-
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?
-
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.
-
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
-
@Jester: ich habe damit nicht angefangen und laß mich nicht beleidigen.
-
@frosty: Du hast angefangen und im Gegensatz zu volkard wurdest du nicht beleidigt!
Edit: Außerdem wurde beiläufig von der kleinsten Zahl geredet, und da es (mathematisch) keine kleinste ganze Zahl gibt, ist es wahrscheinlich, dass es um unsigned geht, aber auch andernfalls besteht das Problem mit dem Unterlauf, wie volkard es dir schon wiederholt zu erklären versucht hat.
-
Jester schrieb:
Jo, das ist ein geiler Trick!
Typisch ich.
frosty geh heulen.
Bye, TGGC
-
-
frosty schrieb:
Tja, das ist mir eigentlich viel zu doof dir jetzt ne Nachhilfe in Mathe und technischer Informatik zu geben.
kein bedarf, fürchte ich.
((außer, du hast es drinend nötig, dann erkläre mir, warum man vom minimum über alle zahlen noch eins abziehen muß, um zum infimum zu kommen. laut üblicher definitionen ist das gar nicht nötig. mit welcher meet-verknüpfung kannste das verhalten widerspruchsfrei auf natürlichen zahlen erzeugen?))Und auch darüber in den Ursprungspost was rein zu interpretieren was da nicht steht.
ok. wir zählen mal nicht, daß kurze zeit später gegeben wird "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." und damit dein verfahren sehr, sehr schnell doppelzahlen ausspuckt.
wir schauen einfach mal, was du in deinem ersten posting geschrieben hast. "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).".
aha! du wolltest durch ein array laufen. nicht zufällig ein array of int? also lassen wir doch erstmal gelten, daß du an ein computerprogramm dachtest und daß es extrem wahrscheinlich ist, dort bei gegebener aufgabenstellung richtig zu liegen, wenn man unsigned int (oder wenigstens int) annimmt. nehmen wir mal nicht int an, sondern einen ganzzahltyp, der keine untere grenze hat. huge numbers, also innendrin arrays, die können *sehr* groß und klein werden. fast wie natürliche zahlen. wie schafft dein verfahren dann O(n)? du hast also selber angenommen, einen üblichen maschinentypen zu benutzen und die im array zu halten. und dann machste haarspaltereien, dein verfahren könne unter umständen funktionieren, wen man von diesen und jeden annahmen ausginge (die ebenfalls nicht im ursprungsposting standen), vertrittst komische thesen, längst nachdem die aufgabe präzisiert wurde. er klappte natürlich nicht, mich mit dem gewichtigen wort "Infimum" umzuwerfen. ich kenne den begriff natürlich. meine mathe-scheine liefen auf die begriffliche wissenverarbeitung hinaus, da sind verbände grundlage zu. hab den bergiff nicht benutzt, weil er hier nicht angemessen wäre (minimum reicht). die lustige behauptung, das infimum sei nicht element des arrays, ist grausam. nachzulesen als "Das Verfahren liefert eine gültige Zahl. Nämlich das Infimum der Array-Elemente." oft liegt das infimum drin in der menge der argumente. nehmen wir für das infimum die innere verknüpfung meet als min(a,b), wobei min(a,b) immer definiert sein soll und das kleinere element ausgibt, dann ist das infimum(a,b,...,x) schlicht min(a,b,...,x). eigentlich ein wichtiger anwendungsfall des infimums, so daß du den kennen müßtest. deshalb sah ich auch sofort, daß du "infimum" nur als blendwort verwendet hast, um intellektuell zu tun. würdes du wie jester manchmal aus versehen hochmathematisch werden, würden das ganz anders klingen.
also sei lieb, und sag, daß es dir leid tut, so auf's falsche pferd gesetzt zu haben.
