#1 14.10.2005 14:10:56

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Doppelte Elemente verhindern

Ich habe eine doppelt verkettete Liste von Pointern.
Größenordnung: Etwa 500 bis 1000 Objekte.

(Es handelt sich um eine std::list<CFrame*> aus der C++ STL um genau zu sein. Wobei CFrame eine Klasse in meinem Objektsystem ist.)

Wie kann ich (effzient) verhindern, dass ich ein Element (also einen Pointer) doppelt zur Liste hinzufüge?

1. Man könnte zwar innerhalb des CFrame-Objektes einfach ein Attribut hinzufügen, das speichert ob das Objekt schon drin ist oder nicht. Dazu müsste ich aber die Schnittstelle ändern. Und da CFrame nicht von mir geschrieben wird, sondern von meinem Komolitonen ist das nicht ganz so einfach, wenn auch nicht unmöglich.

2. Dann könnte man bei jedem hinzufügen, sämtliche Objekte durchgehen und so testen ob es schon drin ist. Aufwand: O(n^2)  wenn auch mit recht guten Konstanten.

3. Einfach alles hinzufügen und anschließend die Liste sortieren. (ich habe keinen RandomAccess!!!) Während des sortierens kann man die doppelten entfernen.

4. In einer Hash-Tabelle speichern welche Objekte schon drin sind.

5. Keine verkettete Liste benutzen? Ich muss allerdings später noch weitere Objekte aus der Liste löschen. Also ein dynamisches Array (std::vector) ist auch nicht so das wahre...

andere Ideen?

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#2 14.10.2005 15:52:07

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Doppelte Elemente verhindern

Ich würde 4. machen, auch wenn ich´s nicht proggen will.
Mußt Du das bei jedem Element-Hinzufügen machen?
Oder reicht´s, 1000 Elemente zuzufügen und danach alle doppelten rauszuschmeißen? Würde auch quadratischen Aufwand haben, denke ich. Vielleicht schafft man das Quicksort zu sortieren aber - ach, ich weiß auch nicht. Viel Glück!  big_smile

Offline

 

#3 14.10.2005 16:43:54

LarsMiddendorf
ProMember
Registriert: 24.01.2005
Beiträge: 103

Re: Doppelte Elemente verhindern

Andere Idee:
Man speichert keine CFrame* in der Liste sondern ein eigenes Objekt, dass den eigentlichen CFrame* und noch beliebige weitere Attribute speichert.

Offline

 

#4 14.10.2005 17:18:02

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Doppelte Elemente verhindern

Zitat:

Andere Idee:
Man speichert keine CFrame* in der Liste sondern ein eigenes Objekt, dass den eigentlichen CFrame* und noch beliebige weitere Attribute speichert.

Hatte ich auch überlegt.
Ich mache mir eine großes array von boolean, also für jedes CFrame im System ein bool-Wert.
Neben dem CFrame* wird in der Liste dann auch noch ein Pointer auf den zugehörigen bool-Wert gespeichert.
Problem: Ich müsste bei jedem Render-Durchgang sämtliche Bool-werte zurücksetzen.

Naja ich muss noch ein bisschen drüber denken....


My software never has bugs. It just develops random features.

Offline

 

#5 14.10.2005 17:26:44

LarsMiddendorf
ProMember
Registriert: 24.01.2005
Beiträge: 103

Re: Doppelte Elemente verhindern

Das Zurücksetzen kann man sich sparen wenn man statt bool einen int speichert und dann beim nächsten Frame einfach einen "globalen" Zähler hochsetzt. Falls der gespeicherte int dem int aus dem Objekt entspricht gilt es als true. Dadurch werden dann alle Werte automatisch auf einmal "false".

Offline

 

#6 14.10.2005 18:21:26

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Doppelte Elemente verhindern

Hm, tolle Idee. Fast genauso krank wie "Lazy Initialization", aber ich werd mal drüber denken... :mrgreen:

Für die Unwissenden:
"Lazy Initialization" braucht für jeden Wert im Array zusätzlich zwei Integer.
Vorteil: Man braucht den Speicher nicht initzialisieren.
Nachteil: Will man z.B. nur ein Byte (also ein Bool) speichern, braucht man das 9 fache an Speicher. (zwei Integer = 8 Byte)

Coolcat


My software never has bugs. It just develops random features.

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson