Autor Beitrag
Aya
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mi 12.01.05 08:19 
Hi,

ich hab ein kleines Problem... :)

Ich habe 10 Variablen von verschiedenem Typ... (z.B. 2x String, 4x Integer, 2x Float, 2x Boolean)

Diese 10 Variablen haben ständig verschiedene Werte.. und ich muß zu jeder zusammenstellung dieser 10 Werte einen String speichern.

So.. problem ist jetzt, wie mach ich das am geschicktesten??? Der String soll immer erst dann generiert werden wenn ich auf die konstellation der 10 Werte zugreife und noch kein String dafür existiert...

Wie speichere ich das ganze am sinnvollsten...??? Einfach in einem Array ist nicht das wahre.. denn wenn da erstmal genug konstellationen drin sind dauert das recht lange den Array zu durchsuchen...

Ich hatte es schon mit TBucketList (also einer HashListe) versucht.. aber geht auchnicht so gut da ich die Key-Objects ja irgendwie/irgendwo speichern muß was genauso auf einen Array hinauslaufen würde den ich nach dem passenden Key-Objekt durchsuche..

Eine Andere Idee war ein 10-Dimensionaler Array... würde soweit auf funktionieren.. nur mir scheint es nicht die beste lösung...

Hat da noch irgendwer eine andere Idee???

ein ansatz wäre es die 10Werte zu z.B. einer IntegerZahl zusammenzustellen um einen ZahlenKey zu erhalten mit dem ich den String irgendwie verbinde... hieße aber das ich einen ziemlich großen Array habe bei dem wohl ne menge felder leer bleiben...

Hoffe es hat jemand ne tolle idee :)

Au'revoir,
Aya~

_________________
Aya
I aim for my endless dreams and I know they will come true!
highhatcompy
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 190

Win2000,Win XP,Linux(SuSE9.2)
Delphi 5 Prof.
BeitragVerfasst: Mi 12.01.05 08:29 
Hallo,
wieso machst du das ganze nicht mit 'ner DB?

Viele Grüsse
HHC

_________________
Bist Du ein Programmierer, so wirst Du gegen Computer, Hardwarehersteller und Anwender verlieren. (Quelle: Murphy's Computer-Gesetz)
Aya Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mi 12.01.05 09:48 
Hi,

ok das ginge sogar... :)
Aber ist auch nicht direkt das allerbeste für meine zwecke :(

Ich brauche das ganze für meine GameEngine... da wird die abfrage dann später mehrere hundert mal in der Sekunde passieren..

a) Bin ich mir nicht wirklich sicher ob eine freeware DB das hinbekommt von der gewschwindigkeit

b) Mag ich ungern nen DB Server mitliefern müßen ;)

Au'revoir,
Aya~

_________________
Aya
I aim for my endless dreams and I know they will come true!
highhatcompy
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 190

Win2000,Win XP,Linux(SuSE9.2)
Delphi 5 Prof.
BeitragVerfasst: Mi 12.01.05 10:04 
Hallo,
Aya hat folgendes geschrieben:

Ich brauche das ganze für meine GameEngine... da wird die abfrage dann später mehrere hundert mal in der Sekunde passieren..

... Du hast recht mehrere hundert Zugriff sind ein wenig viel.




Aya hat folgendes geschrieben:
Hi,

Diese 10 Variablen haben ständig verschiedene Werte.. und ich muß zu jeder zusammenstellung dieser 10 Werte einen String speichern.


Mit welchen Datenmengen rechnest Du eigentlich? Wenn jede mögliche Kombination Deiner Variablen gespeichert werden sollen, dann wird das sicherlich auch ein Problen sein ! ? Oder?

Bis bald
HHC

_________________
Bist Du ein Programmierer, so wirst Du gegen Computer, Hardwarehersteller und Anwender verlieren. (Quelle: Murphy's Computer-Gesetz)
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Mi 12.01.05 10:09 
Moin,

Ich würde die 10 Werte in eine Klasse packen (im Einfachsten ein record), dies mit dem String verbinden und über ein Array mit dem ganzen Kram arbeiten:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
type TElementData = record
  // hier die Integer, Float, Boolean und String rein
end;

TElement = record
  V1: String;
  V2: TElementData;
end;

TAllElements = class
  private
    _allElements: Array of TElement;
    //...
  public
    function Gib_was_ich_will( key: String ): TElementData;
    //...
end;

Natürlich kann man das noch weiter kapseln und TElementData nur für die Klasse nutzbar halten. In diesem Fall brauchst Du nur mit einem Key arbeiten, der sagt, auf welches Element du zugreifen möchtest. Du must dann aber mit Referenzparametern arbeiten und die Funktion überladen.

Es kann auch sein, daß ich dem Extra-String zu viel Bedeutung beimesse, aber vielleicht reichen meine Denkansätze für irgendwas. :)

gegrüßt!
MitschL
Aya Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mi 12.01.05 10:16 
Hi,

highhatcompy hat folgendes geschrieben:
Mit welchen Datenmengen rechnest Du eigentlich? Wenn jede mögliche Kombination Deiner Variablen gespeichert werden sollen, dann wird das sicherlich auch ein Problen sein ! ? Oder?


Es wird nicht sooviele möglichkeiten geben.. da wohl nie absolut jede möglichkeit gebraucht wird :)

Zu MitschL:
Wenn ich dich jetzt richtig verstehe ist das die lösung mit dem Array den ich durchsuche in ner for-schleife.. ;)
Also ich packe alles in einen riesen Array und jedesmal wenn ich was brauche durchsuch ich den gesamten Array dannach... funktioniert zwar, ist aber auch ein wenig zu langsam denke ich.... :)

Ich bräuchte irgendeine lösung die ohne for-schleife auskommt (wie z.B. der 10Dim-Array oder die TBucketList)..

Au'revoir,
Aya~

_________________
Aya
I aim for my endless dreams and I know they will come true!
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Mi 12.01.05 10:29 
OK,

das Array ist nicht wirklich so groß, weil es aus einem String und einem Pointer besteht (der auf den passenden Record zeigt ). Wenn Du zu dem String etwas suchst, bist Du sofort bei den anderen Daten.
Außerdem kannst Du auf diese Weise eine mehrfache Zuordnung machen, falls ein String für mehrere Fälle(also TElementDatas) gültig ist.

Wenn Du noch ein bischen dazu erzählst, ist vielleicht eine Optimierung möglich. Ich denke da an so Sachen, daß außerhalb des ganzen nicht mit Strings, sondern mit Integers als Indizes gearbeitet wird, dann könntest du diese als Array-Indizes benutzen. Hängt halt von deinen Daten ab und dem Einsatz.
Wenn der Kram sortierbar wäre, würden sich ebenfalls Optimierungsmöglichkeiten bieten.

gegrüßt!
MitschL
Aya Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mi 12.01.05 10:44 
Hi,

MitschL hat folgendes geschrieben:
Wenn Du noch ein bischen dazu erzählst, ist vielleicht eine Optimierung möglich. Ich denke da an so Sachen, daß außerhalb des ganzen nicht mit Strings, sondern mit Integers als Indizes gearbeitet wird, dann könntest du diese als Array-Indizes benutzen. Hängt halt von deinen Daten ab und dem Einsatz.
Wenn der Kram sortierbar wäre, würden sich ebenfalls Optimierungsmöglichkeiten bieten.


das war ja das was ich meinte.. ich könnte einen Schlüsselwert aus den werten generieren den ich als ArrayIndex benutze... nur dieser Array wäre halt recht groß und hätte recht viele leere felder..

Zitat:
das Array ist nicht wirklich so groß, weil es aus einem String und einem Pointer besteht (der auf den passenden Record zeigt ). Wenn Du zu dem String etwas suchst, bist Du sofort bei den anderen Daten.


Der Array ist zwar datenmengen mäßig nicht sehr groß.. aber irgendwann hat er auch eine gewisse anzahl an feldern.. und die jedesmal wieder mit ner schleife zu durchsuchen dauert zu lang ;)

Au'revoir,
Aya~

_________________
Aya
I aim for my endless dreams and I know they will come true!
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 12.01.05 11:00 
Könnte man das Array nicht sortieren? Kommt darauf an, wie oft Werte hinzukommen. Das einfügen eines Wertes in ein sortiertes Array benötigt linear viele Schritte, aber das Suchen geht logarithmisch. Bei einem Array mit 1.048.576 (=2^20) Einträgen braucht man gerade mal 20 Schritte, um ein Element zu suchen und zu finden (wenn es denn drin ist)

Edit: Noch besser, aber etwas komplizierter: Du nimmst als Datenstruktur einen Suchbaum, genauer gesagt einen AVL-Baum. Da kannst du auch in Log-Zeit einfügen, und in Log-Zeit suchen. Ist aber eine nicht ganz triviale Sache, das zu implementieren.

_________________
We are, we were and will not be.
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Mi 12.01.05 11:24 
Tja,

wie willst du den Index berechnen? Durch einfache Zuordnung? : 'Die Erste Zusammenstellung, die ich habe kriegt den Index 1. usw.', dann solltest du außerhalb nur mit diesem Index arbeiten und hättest keine Leerräume.

Der klassische Fall ist IMHO die Kapselung der Daten und einer Liste, die auf die Daten zeigt.
Es gibt auch die ein oder andere kleinere Optimierung bezüglich eines Durchlaufalgorithmus, was aber nur dazu führt, das lediglich die Schleifen-Befehle in gewisser Weise gespart werden (gute alte C64-Zeiten):

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
// ungetestet hier reingehackt
i := 0;
maxI := High(liste) div 4;
while i< maxI do
begin
  if liste[i].Wert = gesucht then 
  begin 
    Result := i 
    break; 
  end;
  if liste[i+maxI].Wert = gesucht then 
  begin 
    Result := i+maxI; 
    break; 
  end;
  if liste[i+maxI*2].Wert = gesucht then 
  begin 
    Result := i+maxI*2;
    break; 
  end;
  if liste[i+maxi*3].Wert = gesucht then 
  begin 
    Result := i+maxI*3;
    break; 
  end;
  Inc(i);
end;


Man spart 3x while do begin Inc end - aber ob sich sowas lohnt...
(Ich weis nicht mal, warum ich das da oben getippt habe, aber jetzt ist es schonmal da...)

gegrüßt!
MitschL

PS.: Ich erhebe keinen Copyright-Anspruch das phenomenale Werk. :rofl:
Lossy eX
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1048
Erhaltene Danke: 4



BeitragVerfasst: Mi 12.01.05 11:28 
Ich weiß zwar nicht was du bereits mit einem Hash gemacht hast allerdings laut deiner Aussage denke ich mal, dass du nicht ganz den Aufbau eines Hashes verstanden hast. Nicht böse gemeint. Aber klingt für mich so.

Ein Hash basiert auf einem Array wo an jedem Element eine einfach verkettete Liste anhängt. Mit der Hashmethode wird zum Beispiel aus einem einem Text ein Hashwert generiert. Dieser verweist auf einen Eintrag in dem Array und dort müsste dann lediglich nur noch die Item durchsucht werden die den selben Hashwert haben. Also die die in der Verketten Liste hängen. Wenn das Hash optimiert ist ist das nur noch ein Bruchteil von der Gesamtgröße. So viel zum Hash.

Die andere Lösung wäre eine Art binärer Baum. In dem könntest du deine 10 Werte unterbringen. Als die ersten beiden Ebenen würde ich die Booleans vorschlagen. Bei einer sinnvollen Verteilung könntest du deine zu durchsuchende Daten ziemlich schnell vierteln. Dann die Ints und so weiter. Vom Prinzip her wie bei einem Octree. Also, dass du deine vorhandenen Daten unterteils. Du weißt was ich meine. ;-)

Das sollte dann schnell genug sein um deine Daten zu durchsuchen. Allerdings stellt sich mir die Frage über was für eine Anzahl wir hier reden? 10? 20? 100? 1000? Noch mehr? Bei 10 oder 20 würde ich den Aufwand nicht betreiben und die einfach nu in eine Liste ablegen. Bei 100 würde eine Liste wahrscheinlich auch noch ausreichen, da du ja nicht alle Werte überprüfen musst sondern bei dem Ersten schon ausschließen kannst ob es sich um den gesuchten handelt oder nicht.

PS: Ganz ohne Schleife wirst du nicht auskommen, da du sonst gigantisch viel Speicher verbraten würdest. Alles andere muss halt durchsucht werden. Und das geht nun mal nur mit Schleifen. Da stellt sich nur die Frage wie häufig muss etwas dursucht werden. ;-)

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 12.01.05 11:43 
@MitschL: Sorry, wenn das jetzt blöd klingt, aber dein Algorithmus bringt prinzipiell gar nichts. Wenn das gesuchte Element das letzte in der Liste ist, oder am Ende eines "Viertels" der Liste steht, hast du nichts gespart. Du sparst zwar ein paar Schleifendurchläufe, hast aber pro Durchlauf mehr Arbeit.

Ich würde die Daten in einem AVL-Baum ablegen. Das ist eine Art Binärbaum. Aber an jedem Knoten wird das ganze Paket gespeichert (der String, der sich aus den einzelnen Daten zusammensetzt).

Eine Hashtabelle ist aber auch ne nette Idee. Man benötigt nur eine Hashfunktion, die für wenige Kollisionen sorgt, und die nicht übermäßig viele Werte annehmen kann.

_________________
We are, we were and will not be.
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Mi 12.01.05 13:03 
@Gausi
Ich sprach auch nicht von einer Wunderwaffe. Es werden lediglich, die für eine Schleife notwendigen Befehle minimiert, weil es einen Unterschied macht, ob ich ein Liste mit 1000 Elementen 1000 mal durchlaufe oder 250 mal. Mehr nicht.

Zurück zum Thema.
Ich würde schauen, ob die Daten zueinander in Beziehung stehen. Daraus läßt sich ein Baum kreiern, der zwar nicht binär ist, aber auch Optimierung bedeutet.

Ein wenig haarsträubender wäre die Frage, ob die Einzelwerte stets ihren gesamten Wertebereich ausschöpfen, oder lediglich wenige Werte (zwar über den gesamten Bereich abdenkend) annehmen können. Dann bietet sich u.U. ein Graph an, der ja viele Spielerein erlaubt. ich meine dabei nicht eine Liste als Graph, oder einen Baum als gerichteten Graphen, sondern viel allgemeiner. Ein Konstrukt, bei dem man schon etwas Arbeit investieren muß, wenn man Zyklen sucht. :twisted:

Aber aufgrund der Ungewißheit über die Datenmenge, bleibe ich bei meiner Klasse, die ein Array enthält.

gegrüßt!
MitschL
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 12.01.05 13:35 
Ob man eine Schleife mit einer Abfrage 1000 mal durchläuft, oder eine mit 4 Abfragen 250mal, ist in meinen Augen dasselbe. Evtl. ist die kurze Schleife etwas schneller, ewil da ein paar Takte eingespart werden.
Aber wenn statt 1000 mal inc "nur" 250 mal inc und zusätzlich 750 Multiplikationen und 750 Additionen durchgeführt werden, dann würde ich vermuten, dass die einfache Schleife doch schneller ist :roll:

_________________
We are, we were and will not be.
Lossy eX
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1048
Erhaltene Danke: 4



BeitragVerfasst: Mi 12.01.05 13:56 
Auf Assemblerebene sieht eine Schleife so aus, dass be jedem Durchlauf ein Register (CX) überprüft werden muss und dann im Code gesprungen werden muss. Allerdings hinkt der Quellcode ein bisschen. Man sollte man die Schleife um 4 erhöhen und die 4 nacheinander folgenden Elemente überprüfen. Dann muss man auch nicht aufwendig rechnen sondern lediglich 1, 2 oder 3 addieren. (Oder Idx pro Element um eines erhöhen). Man dürfte in dieser Schleife auch nur alle vollständigen 4er Gruppen überprüfen und die letzten 2 o. 3 dann in einer gesonderten Schleife abarbeiten. Wenn man dann in die Schleife noch eine Bereichprüfung einbauen müsste wäre der Geschwindigkeitsvorteil wieder futsch.

Aber im Endeffekt ist die ersparrte Rechnezeit zu gering um einen sinnvollen Anteil einer Optimierung auszumachen zu können. Aya muss im vornherein so viel wie möglich Einträge ausschließen um nur noch eine Hand von Elementen durchsuchen zu müssen. (Baum, Hash, etc)

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Mi 12.01.05 13:58 
Tja,

sind wohl doch keine C64-Zeiten mehr. (selbst, wenn man statt der weit auseinander liegenden Zugriffe, 4-er Blöcke, wie i, i+1, i+2, i+3 macht und statt dem Inc(i) ein i:=i+4 nutzt, oder man macht zwischen die Abfragen die Inc's umd sozusagen nur noch das Schleifenkonstrukt 750x zu sparen - OK. Ich laß es. :) )

gegrüßt!
MitschL


[edit] Mir kam noch ein Gedanke: Indexlisten. Wenn nach bestimmten Konstrukten gesucht wird, kann man doch mit Indexliste arbeiten. Ich stelle mir gerade vor, daß ich eine zweite Liste nutze, welche mir Auskunft darüber gibt, daß die Konstrukte hier bereits verändert wurden, oder gerade nicht, oder sonstwas.
Dan würde man mehrere Listen verwalten und nähme die, die am kurzesten und nützlichsten ist. ... oder so.
NeoInDerMATRIX
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 245

Win95, Win98(+se), WinNT, Win2000, WinME, WinXP(+pro), VISTA, Linux(SuSe), DOS [MultiMon(3)], Vista
D6 PeE + (FP 2.0l) + D3 Pe + D2005+ D2006 Arch
BeitragVerfasst: Mi 12.01.05 15:23 
Hi,

das speichern in eine art OccTree denke ich ist die einfachste möglichkeit. Daman damit die möglichkeit hat daten bequem auszuschließen. Auch das implementieren sonnte dabei nicht das problem darstellen.
Es kommt allerdings darauf an was das für daten sind und inwie weit eine aufteilung in einen Tree möglich ist. Da du von GameEngine redest denke ich das die daten auch mit Räumlichen daten zu tun haben, oder? Wenn dies der fall sein sollte ist der OccTree das beste denke ich!

Also
Cu
Neo