Füllung einer Zahlenliste

[Sharky]

Hai leddl,

ich habe das geschrieben weil ja noch nicht 100% klar war welche Zahl er nun einfügen möchte. Die nächstkleinere oder die kleinstmögliche ;-)

Noch ein Vorschlag für die Geschwindigkeit:
Wenn in der Liste zum Beispiel 10000 Zahl stehen und die Zahlen 1 bis 5000 am Stück vorhanden sind bedeutet dies ja automatisch das alle Zahlen bis 5000 ihrer Position in der Liste (-1) enstprechen.

[egal]

Es geht eigentlich um eine DB-Tabelle. Da gibt's ein Feld 'Index', das maximal 999 sein darf. In der Tabelle gibt's schon einige Sätze. Und wenn ich den neuen Satz schreiben soll, dann muss ich das Feld 'Index' vergleichen. Wenn solcher Index schon vorhanden ist, dann muss ich den kleinsten nicht besetzten Index suchen und mit diesem Index den Datensatz in die Tabelle schreiben.
Deswegen habe ich so ausgedacht, alle vorhanden Indizien in einer Liste zu speichern, sortieren und da die kleinste nicht besetzte Zahl rausfinden und mit deiser Zahl al Index in der DB speichern. Als DB wird MS-Access 2000 verwendet, die Struktur darf ich nicht ändern.

[egal]

Zitat:

Zitat von Sharky

Hai leddl,

ich habe das geschrieben weil ja noch nicht 100% klar war welche Zahl er nun einfügen möchte. Die nächstkleinere oder die kleinstmögliche ;-)

Noch ein Vorschlag für die Geschwindigkeit:
Wenn in der Liste zum Beispiel 10000 Zahl stehen und die Zahlen 1 bis 5000 am Stück vorhanden sind bedeutet dies ja automatisch das alle Zahlen bis 5000 ihrer Position in der Liste (-1) enstprechen.

Kannst du mir bitte erklären, wo ist in meinem Fall der Unterschied zwischen nächstkleinere und kleinstmögliche :roll:

[leddl]

Zitat:

Zitat von Sharky

Hai leddl,

ich habe das geschrieben weil ja noch nicht 100% klar war welche Zahl er nun einfügen möchte. Die nächstkleinere oder die kleinstmögliche ;-)

Achso, darum gings dir. Das habe ich seinem Psot entnommen. Für mich sah das ganz so aus, als wollte er die kleinstmögliche. Du hast mich ganz schon geschafft, Herr Hai! :lol: Hatte schon an mir oder zumindest dir gezweifelt. ;)

Zitat:

Zitat von Sharky

Noch ein Vorschlag für die Geschwindigkeit:
Wenn in der Liste zum Beispiel 10000 Zahl stehen und die Zahlen 1 bis 5000 am Stück vorhanden sind bedeutet dies ja automatisch das alle Zahlen bis 5000 ihrer Position in der Liste (-1) enstprechen.

:gruebel: Und wie hilft das? das weiß er ja nicht, sondern muß es trotzdem noch prüfen. Bzw er weiß es vielleicht, aber das Programm nicht ;)
Aber wie gesagt, eine andere, schnellere Lösung als meine sehe ich nicht, insofern sollte es passen.

Zitat:

Zitat von egal

Deswegen habe ich so ausgedacht, alle vorhanden Indizien in einer Liste zu speichern, sortieren und da die kleinste nicht besetzte Zahl rausfinden und mit deiser Zahl al Index in der DB speichern. Als DB wird MS-Access 2000 verwendet, die Struktur darf ich nicht ändern.

Ja, das sollte doch eigentlich passen. Die Frage, die sich jetzt noch stellt wäre: Gibt es evtl eine Funktion in ACCESS, die das direkt macht? :stupid: Da kenn ich mich nicht aus, wäre aber doch möglich, immerhin ist diese Idee nicht so abwegig.

Was passiert, wenn bereits alle Zahlen von 1 bis 999 vergeben sind?

Zitat:

Zitat von egal

Kannst du mir bitte erklären, wo ist in meinem Fall der Unterschied zwischen nächstkleinere und kleinstmögliche

• nächstkleinere
  Du schaust, welche Zahl kleiner als die einzufügende ist, und am nächsten an ihr dranliegt.
• kleinstmögliche
  Du beginnst von vorne und schaust, welche die kleinste Zahl ist, die du einfügen kannst

zB: [1,3,5,7,8,9] Einzufügen ist 7. Kleinstmögliche ist 2, Nächstkleinere ist 6

[Sharky]

Zitat:

Zitat von egal

... Kannst du mir bitte erklären, wo ist in meinem Fall der Unterschied zwischen nächstkleinere und kleinstmögliche

Wenn die Zahl

Code:

1
3
4
5
6
7
9
10

vorhanden sind und du wolltest die 10 Eintragen ist die nächstkleinere die 8 und die kleinstmögliche die 2.

[Sharky]

Zitat:

Zitat von leddl

Und wie hilft das? das weiß er ja nicht, sondern muß es trotzdem noch prüfen.

Mal im Kopf gedacht:
Es gibt 10 000 Zahlen. Die Zahlen 1 bis 5000 sind am Stück vorhanden.
Dann muss also Listbox1.Items[5000-1] = '5000' sein.
Ich muss also nur die Items von Index 5000 bis Count-1 prüfen.
Wenn die Bedingung nicht zutrifft muss ich nur Index 0 bis 5000-1 prüfen.
Ich habe also durch eine Rechenoperation den Raum der möglichen "Felder" halbiert.
So, und das macht man jetzt immer so weiter bis man nur noch zwei Zahlen hat.

Rechne mal aus was es bei 1 000 000 000 Zahlen passiert wenn die einzig nicht besetzte Zahl 999 999 999 ist ;-)
Mit deiner Schleife musst Du nun 999 999 999 Vergleiche machen.

[egal]

Zitat:

Zitat von leddl

Also sofern ich dein Problem wirklich richtig verstanden habe (Sharky macht mich da ganz wuschig ;)), sollte mein Code es absolut tun. Besonders viel schneller sollte es auch eigentlich nicht gehen, denn du hast ja nur 2 Möglichkeiten:

• Entweder, du prüfst jede Zahl von 1 bis 999 durch, ob sie vorhanden ist (das kann dann aber etwas länger dauern, da du bei einer ListBox dafür IndexOf aufrufen müsstest, das aber für jede Zahl [bis eine nicht vorhanden ist] alle Items bis zur gesuchten Zahl durchgehen müsste, und das kann sich ja summieren)
• oder du gehst ein Item nach dem anderen durch und prüfst, ob noch eine Zahl reinpasst. Und das sollte die deutlich schnellere Variante sein. Und genau das macht doch mein Code. Wenn die Liste sortiert ist und es keine Lücken gibt, muß doch jedes Element mit dem Index i den Wert i+1 (ListBox ist 0-basiert, bei 1-basiertem Array wäre es natürlich i) besitzen. Kleiner als i kann der Wert nicht sein, da wir ja mit natürlichen Zahlen rechnen. Ist der Wert am Index i größer als i+1 haben wir ne Lücke und damit die gesuchte Zahl. Voilá! ;)

Es wird eigentlich schon vorher abgefangen, ob diese Zahl schon vorhanden ist. Ich hatte am Anfang auch ähnliche Idee, eine Zahl mit nächster vergleichen und wenn Unterschied nicht 1 ist, dann weiß man, aha, da ist eine Lücke, da kann man eine Zahl reinschreiben. Ich kann auch noch prüfen, ob die letzte Zahl nicht gleich den Zahlenanzahl. Wenn so ist, dann brauche ich auch nichts machen. Mir stört noch, dass ich meine Liste, bzw. Array immer wieder sortieren soll.

Dann brauche ich auf jeden Fall die kleinstmögliche Zahl. Und wie gesagt, maximale Zahl ist 999.

[egal]

Zitat:

Zitat von leddl

Ja, das sollte doch eigentlich passen. Die Frage, die sich jetzt noch stellt wäre: Gibt es evtl eine Funktion in ACCESS, die das direkt macht? :stupid: Da kenn ich mich nicht aus, wäre aber doch möglich, immerhin ist diese Idee nicht so abwegig.

Das glaube ich aber nicht.

[leddl]

Zitat:

Zitat von Sharky

Mal im Kopf gedacht:
Es gibt 10 000 Zahlen. Die Zahlen 1 bis 5000 sind am Stück vorhanden.
Dann muss also Listbox1.Items[5000-1] = '5000' sein.
Ich muss also nur die Items von Index 5000 bis Count-1 prüfen.
Wenn die Bedingung nicht zutrifft muss ich nur Index 0 bis 5000-1 prüfen.
Ich habe also durch eine Rechenoperation den Raum der möglichen "Felder" halbiert.
So, und das macht man jetzt immer so weiter bis man nur noch zwei Zahlen hat.

Rechne mal aus was es bei 1 000 000 000 Zahlen passiert wenn die einzig nicht besetzte Zahl 999 999 999 ist ;-)
Mit deiner Schleife musst Du nun 999 999 999 Vergleiche machen.

Ja das is mir klar, wenn er sowas weiß ist das kein Problem. Nur wie sicher kann er denn jetzt sagen, bis zu welcher Zahl es keine Lücken gibt? Das meinte ich. Das könnte man natürlich gesondert speichern, aber ich denke bei Zahlen von 1 bis 999 lohnt sich das nur unmerklich.

//Edit: Schwachfug, natürlich hast du recht. Nich gründlich genug gelesen, was du geschrieben hast. Klar könnte man durch die Rekursion einen erheblichen Geschwindigkeitszuwachs bekommen. Allerdings stellt sich die Frage, wie viel das bei 999 Elementen bringt...

Zitat:

Zitat von egal

Es wird eigentlich schon vorher abgefangen, ob diese Zahl schon vorhanden ist. Ich hatte am Anfang auch ähnliche Idee, eine Zahl mit nächster vergleichen und wenn Unterschied nicht 1 ist, dann weiß man, aha, da ist eine Lücke, da kann man eine Zahl reinschreiben. Ich kann auch noch prüfen, ob die letzte Zahl nicht gleich den Zahlenanzahl. Wenn so ist, dann brauche ich auch nichts machen. Mir stört noch, dass ich meine Liste, bzw. Array immer wieder sortieren soll.

Brauchst es doch nicht immer wieder sortieren. Einmal am Anfang reicht. Und das kannst du ja eigentlich auch direkt in der DB erledigen lassen. Und dann fügst du die Zahlen direkt an der richtigen Stelle mit Insert (bei ner ListBox) ein und mußt danach nix mehr sortieren. ;)

Zitat:

Zitat von egal

Dann brauche ich auf jeden Fall die kleinstmögliche Zahl. Und wie gesagt, maximale Zahl ist 999.

Nochmal: Genau das macht mein Code. ;) Die Prüfung, ob die Zahl 0 oder größer 999 ist, mußt du natürlich evtl noch einbauen

[egal]

Zitat:

Zitat von leddl

Nochmal: Genau das macht mein Code. ;) Die Prüfung, ob die Zahl 0 oder größer 999 ist, mußt du natürlich evtl noch einbauen

Ich habe es für Sharky geschrieben.