Füllung einer Zahlenliste

[egal]

Sorry für den blöden Titel, aber was besseres fällt mir nicht ein.
Ich hab ein folgendes Problem: ich habe eine sortierte Liste mit Zahlen, z.B. 1,2,5,100,203,999, bis 999. In diese Liste muss ich neue Zahlen schreiben. Wenn diese Zahl gibt's in dieser Liste nicht, dann schreibe ich sie einfach rein und sortiere. Aber wenn diese Zahl schon vergeben ist, z.B. 100, dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.
Und jetzt die Frage, wie kann ich diese kleinere noch nicht besetzte Zahl schnell finden? Ich habe ein Paar Gedanken, aber das ist alles total langsam.
Danke.

[leddl]

Mir fällt spontan nur ein, die Listbox von vorne durchzugehen und zu prüfen, ob die Zahl am entsprechenden Index Index+1 ist. Ist das nicht der Fall, kannst du Index + 1 einfügen. (Vorausgesetzt, du startest mit 1, und nicht mit 0)
Also:

Delphi-Quellcode:

For i := 0 To ListBox1.Items.Count - 1 Do
  If StrToInt(ListBox1.Items[i]) > i+1 Then
    break;
//i+1 ist die Zahl, die eingefügt werden muß
//i ist der Index, bei dem eingefügt werden muß

Sollte aber auch so funktionieren.

Delphi-Quellcode:

i := 0;
While (i <= ListBox1.Items.Count - 1) and (StrToInt(ListBox1.Items[i]) = i+1) Do
  inc(i);
//i ist die Zahl, die eingefügt werden muß
//i-1 ist der Index, bei dem eingefügt werden muß

Ist aber jetzt alles nur aus dem Kopf schludrig hingeschrieben und kann noch Denkfehler beinhalten. ;)

//Diverse Edits :roll:
Kleinere Schreibfehler gefixt und Kleinigkeiten eingefügt :stupid:

[Sharky]

Zitat:

Zitat von egal

... dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.

Hai egal,
wenn ich das richtig lese musst Du nicht die kleinere sondern die kleinste nicht "besetzte" Zahl einfügen oder?

[egal]

Zitat:

Zitat von Sharky

Zitat:

Zitat von egal

... dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.

Hai egal,
wenn ich das richtig lese musst Du nicht die kleinere sondern die kleinste nicht "besetzte" Zahl einfügen oder?

jo, hast du Recht

[leddl]

OK, aber meine Antwort wird ignoriert... :shock:

[Sharky]

Zitat:

Zitat von leddl

OK, aber meine Antwort wird ignoriert... :shock:

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll :stupid:

@egal:
Wo ist denn das Hauptproblem? Bei herausfinden ob eine Zahl schon in deiner sortierten Liste (wie ist diese eigentlich aufgebaut) vorhanden ist oder beim bestimmen der kleinsten nicht vorhandenen Zahl?

[egal]

Zitat:

Zitat von leddl

Mir fällt spontan nur ein, die Listbox von vorne durchzugehen und zu prüfen, ob die Zahl am entsprechenden Index Index+1 ist. Ist das nicht der Fall, kannst du Index + 1 einfügen. (Vorausgesetzt, du startest mit 1, und nicht mit 0)
Also:

Delphi-Quellcode:

For i := 0 To ListBox1.Items.Count Do
  If StrToInt(ListBox1.Items[i]) > i+1 Then
    break;
//i+1 ist die Zahl, die eingefügt werden muß
//i ist der Index, bei dem eingefügt werden muß

Sollte aber auch so funktionieren.

Delphi-Quellcode:

i := 0;
While (i <= ListBox1.Items.Count - 1) and (StrToInt(ListBox1.Items[i]) = i+1) Do
  inc(i);
//i ist die Zahl, die eingefügt werden muß
//i-1 ist der Index, bei dem eingefügt werden muß

Ist aber jetzt alles nur aus dem Kopf schludrig hingeschrieben und kann noch Denkfehler beinhalten. ;)

Danke, kannst du mir auch sagen, welche Lösung schneller ist? Da brauche ich jede Mikrosekunde :-D

[leddl]

Zitat:

Zitat von Sharky

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll :stupid:

:shock: Wie bitte? :gruebel: Er wollte wissen, wie er an die erste nicht besetzte Zahl kommt, und genau das machen doch die beiden Codeschnipsel. Da die Listbox sortiert ist, kann man von vorne aus prüfen, welche Zahlen vorhanden sind. Man fängt also beim ersten Item (Index = 0) an und prüft, ob der Wert dort 1 ist. Was kleineres als 1 kann da nicht stehen, also ist es entweder 1 oder größer als 1. Steht eine 1, muß das nächste Item geprüft werden. Steht keine 1, hat man seine gesuchte Zahl und den Index (der natürlich immer "einzufügende Zahl -1" ist)
Inwiefern löst das das Problem nicht? :gruebel:

Zitat:

Zitat von egal

Danke, kannst du mir auch sagen, welche Lösung schneller ist? Da brauche ich jede Mikrosekunde

:roll: Testen... Ich hab hier kein Delphi um es für dich zu machen. Aber laut meinem Verständnis sollte es ziemlich gleich schnell sein, da ja eigentlich bei beiden Varianten genau das selbe passiert.

//Edit:
Aber ganz wichtig: Die For-Schleife muß bis ListBox1.Items.Count - 1 gehen. Das is mit durchgerutscht!

[egal]

Zitat:

Zitat von Sharky

Zitat:

Zitat von leddl

OK, aber meine Antwort wird ignoriert... :shock:

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll :stupid:

@egal:
Wo ist denn das Hauptproblem? Bei herausfinden ob eine Zahl schon in deiner sortierten Liste (wie ist diese eigentlich aufgebaut) vorhanden ist oder beim bestimmen der kleinsten nicht vorhandenen Zahl?

Das Problem ist, wie finde ich die kleinste nicht vorhandene Zahl. Wie ist die Liste aufgebaut, es hängt von mir ab. Das kann eine ListBox oder ein Array sein. Die Liste ist sortiert.

[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á! ;)

Bei einem Array müsstest du in meinem Code eben einige kleinere Änderungen machen (zB. "ListBox1.Items.Count - 1" gegen "Length(MyArray) - 1" austauschen).

[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.

[egal]

Zitat:

Zitat von leddl

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. ;)

Danke für Info, von Insert habe ich nicht gewusst.

[leddl]

Passt scho.
Ist aber ein interessantes Problem. Wenn ich nachher noch Muse finde, werde ich mich mal dranhocken und spaßeshalber ne rekursive Version schreiben. ;)

Aber nochmal zurück zum Problem:
Wie genau machst du es?
Liest du die DB einmal beim Start des Programmes ein und schließt die DB erst am Ende wieder?
Oder liest du für jedes Einfügen eines neuen Items die DB komplett neu in das Programm ein?
Im zweiten Fall kommst du nämlich um das ständige Sortieren der Daten wohl nicht rum. Wenn du allerdings die Indizes nur einmal holst und sie danach in der ListBox behältst (Durch das Einfügen der neuen Indizes in die ListBox bleibst du ja aktuell), kannst du dir das Neusortieren sparen. Entweder, du stellst die Eigenschaft Sorted der ListBox auf true (dann wird jedes Item automatisch richtig einsortiert - was das an Zeit schluckt, weiß ich allerdings nicht) oder du fügst jedes Item mit Insert direkt an der richtigen Stelle ein (diese Stelle sollte je in deinem Fall - wie gesagt - in einer ListBox immer "Zahl-1" entsprechen). Bei einem Array müßtest du dir die Insert-Funktion erst selbst implementieren, was aber auch kein Problem sein sollte.

//Edit:
Insert ist eine Methode der ListBox, der du wie bei Add den String, aber zusätzlich noch den Index, an dem eingefügt werden soll, als Parameter übergibst. Soviel nur mal zur Erläuterung. ;)

[egal]

Zitat:

Zitat von leddl

Passt scho.
Ist aber ein interessantes Problem. Wenn ich nachher noch Muse finde, werde ich mich mal dranhocken und spaßeshalber ne rekursive Version schreiben. ;)

Aber nochmal zurück zum Problem:
Wie genau machst du es?
Liest du die DB einmal beim Start des Programmes ein und schließt die DB erst am Ende wieder?
Oder liest du für jedes Einfügen eines neuen Items die DB komplett neu in das Programm ein?
Im zweiten Fall kommst du nämlich um das ständige Sortieren der Daten wohl nicht rum. Wenn du allerdings die Indizes nur einmal holst und sie danach in der ListBox behältst (Durch das Einfügen der neuen Indizes in die ListBox bleibst du ja aktuell), kannst du dir das Neusortieren sparen. Entweder, du stellst die Eigenschaft Sorted der ListBox auf true (dann wird jedes Item automatisch richtig einsortiert - was das an Zeit schluckt, weiß ich allerdings nicht) oder du fügst jedes Item mit Insert direkt an der richtigen Stelle ein (diese Stelle sollte je in deinem Fall - wie gesagt - in einer ListBox immer "Zahl-1" entsprechen). Bei einem Array müßtest du dir die Insert-Funktion erst selbst implementieren, was aber auch kein Problem sein sollte.

//Edit:
Insert ist eine Methode der ListBox, der du wie bei Add den String, aber zusätzlich noch den Index, an dem eingefügt werden soll, als Parameter übergibst. Soviel nur mal zur Erläuterung. ;)

Ich werde ListBox verwenden, mit Array verliere ich mehr Zeit, da muss man entweder 2 Arrays verwenden, oder einen immer neu sortieren.
Wie es alles abläuft, da habe ich noch nicht bis zum Ende gedacht. Es sieht eigentlich so aus. Es gibt in der DB viele Tabellen, bei manchen Tabellen muss ich bei allen Datensätzen den Inhalt von 2 Feldern: Index und Beschreibung in eine andere Tabelle schreiben. Wenn Index schon da ist, aber die Beschreibung anders ist, dann speichere ich in einem Array den Schlüssel von diesem Datensatz. Wenn ich mit der Tabelle fertig ist, dann gucke ich, ob Array nicht leer ist. Wenn leer ist, dann gehe ich zu einer anderen Tabelle, wenn aber nicht, dann muss ich den Satz mit möglichst kleinem Index abspeichern. Und danach muss ich diesen neuen Index in 3-4 anderen Tabellen ändern.
Und hier weiß ich noch nicht. Entweder soll ich zuerst alle Sätze schreiben, neue Indizien abspeichern und dann in anderen Tabellen ändern oder nur einen Satz speichern, in anderen Tabellen den Index ändern und zu anderem Arrayelement gehen. Da muss ich noch gucken, was schneller ist.

[alzaimar]

Wie man über so ein kleines Problemchen so viel schreiben kann...
Hier

Delphi-Quellcode:

Function FindSmallestGap (aArray : Array Of Integer) : Integer;
Var
  l,h,m : Integer;

Begin
  l := 0; h := Length (aArray) - 1;
  While l<h do begin
    m := (l+h) div 2;
    if aArray[m] = m+1 Then
      l := m + 1
    else
      h := m - 1;
    End;
  Result := l+1;
End;

Findet die kleinste Lücke im Array. Bedingung: Zahlen von 1...n. Ich habe es rudimentär getestet, es sollte aber funktionieren.
Es liefert die Zahl I, die an der Stelle aArray [I-1] eingefügt werden muss.