P9: Löschen

syntax
Nichts ist wie es scheint
Beiträge: 23
Registriert: 26. Okt 2005 17:42

P9: Löschen

Beitrag von syntax »

Wie soll man das Löschen realisieren?
Mit der Funktion getElementPosition() kann die Position eines Elementes getestet werden. Die Funktion würde ja unterschiedliche Werte liefern, wenn ich das Löschen durch Markieren, Auflösung der Kollisionen oder rehashen implementiere.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

implementier halt eine methode die dir gefällt und probier aus ob du passed kriegst oO wird schon klappen, wenn nix gesagt wurde ist entweder alles erlaubt oder halt die methode aus den folien (einfach als gelöscht markieren bzw umsortieren bei verlinkten slots) die ich sowieso nehmen würde weil die eigentlich am einfachsten ist..

Benutzeravatar
HerrDerFlammen
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 16. Okt 2006 17:30
Wohnort: Dreieich
Kontaktdaten:

Beitrag von HerrDerFlammen »

als gelöscht amrkieren wird wohl nicht gehen, weil man nicht davon ausgehen kann, dass das IHashObject der Testcase ne isRemoved Flag oder sowas hat
Das Lehren soll so sein, dass das Dargebotene als wertvolles Geschenk und nicht als saure Pflicht empfunden wird.
(Albert Einstein)

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Doch, das geht. Du musst die Gelöscht-Flags halt separat speichern. Entweder kapselst du die zu speichernden Objekte, oder du legst z. B. separat noch ein boolean-Array oder sowas an.

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Beitrag von sonothar »

wieso wollt ihr das nur als gelöscht markieren???
macht doch einfach hashTable[index] = null und das ding is weg
Bild

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

suchst du dann in O(n) laufzeit weil du alle elemente der HashTable durchsuchst?

Wenn du nen Key einfach löschst, besteht kein zusammenhang mehr zwischen mehreren Kollidierten Werten.

Wenn du zum Beispiel 10, 100, 1000 hast, mod 10 als sehr schlechten Modfaktor (is aba einfacher zu erklären ^^), dann müssten ya alle 3 werte auf die adresse 0, durch die Kollisionsfunktion werden je nach einfüge reihenfolge z.B. 100 und 1000 wo anders hingehauen.
Wenn du nu die 100 einfach auf null setzt, dann besteht beim suchen kein zusammenhang mehr zwischen der 10 und der 1000 -> du landest wenn du die 1000 suchst vorzeitig bei einem Null object in deiner HashTable un brichst ab, obwohl du die 1000 eigentlich drin hast

deshalb musste entweder Kettung machen und die Verweise anpassen, oder halt ein element einfach nur als gelöscht markieren

maikg2
Mausschubser
Mausschubser
Beiträge: 95
Registriert: 18. Okt 2005 22:29
Wohnort: Darmstadt

Beitrag von maikg2 »

Wenn man das als gelöscht markiert speichert bekommt man aber eventuell Probleme mit der getElementPosition(key). Je nachdem wie die Testcases sind.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

naja, das wäre dann aber nicht gerade die feine Art im Skript / vorlesung zu sagen das löschen durch markierung oft der einfachere / effizientere weg is un das dann in einem Praktikum - ohne Angabe wie ein Key zu löschen is - zu verbieten.
Von daher schätz ich mal das das erlaubt is

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Beitrag von Hyst »

problem dabei ist, nehmen wir an, man markiert nur als gelöscht. UND man lässt (wie in der vorlesung besprochen) nicht ein neues element den platz einnehmen, sondern nur das element was gelöscht worden ist...
wenn ich jetzt einiges lösche, dann bleiben die element ja noch in der liste... (ist ja erstmal nicht schlimm)

wenn ich jetzt jedoch elemente hinzufüge dann muss ich die hashtable erweitern, bevor der belegungsfaktor wirklich die 75% erreicht hat....

glaubt ihr das wird in den cases berücksichtigt?

mein tutor sagte nämlich: ne lösch-flag ist ok

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

ya, is schon irgendwie unsauber un hat auch wärend der vorlesung ziemlich für Diskussion gesorgt, aber da das als Lösung des Lösch Problems besprochen wurde, sollte man wohl zu 100% davon ausgehen können das der Weg dann auch im Prak erlaubt is, wenn nich geh ich mit dir streiken ^^ (obwohl ich Kettung implementiere)
Wieso lernen wir das alles dann, wenn wirs nich einsetzen dürfen (ohne das ausführlich gesagt wird das mans nich einsetzen darf)

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Beitrag von Hyst »

najaaaa... das problem ist ja:
du WEISST nicht ob du es einsetzten darfst oder nicht. weil (wie immer) die aufgabenstellung soooo unsauber formuliert ist, dass man sich denkt: "wenn ich das jetzt so mache... wollen die das? oder bin ich dann gleich wieder failed?"

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

UND man lässt (wie in der vorlesung besprochen) nicht ein neues element den platz einnehmen, sondern nur das element was gelöscht worden ist...
?? Welchen Sinn soll das denn machen? Der einzige Grund, warum du eine Position überhaupt als gelöscht markieren musst, ist, um sie von einer leeren Position unterscheiden zu können, um also sagen zu können, ob du nach einer leeren Position noch weiter nach einem Element suchen musst oder nicht. Wenn du die Position aber mit einem neuen Element (egal welchem, es muss halt nur direkt oder per Kollision an diese Stelle gelangen), dann entfällt dieses Problem. Die Stelle explizit zu reservieren macht imho gar keinen Sinn.

(Aber vielleicht gibt's dafür ja auch eine tolle Begründung, ich war nicht in der Vorlesung...)

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

ein neues element darfst du nur da hinsetzen wenn du die kollisionskette komplett durchgegangen bist und somit weißt, dass das element sonst nirgends drinsteht. Wenn du sobald du ein gelöschtes feld entdeckst dein element dort hinschreibst kanns passieren, dass du elemente duplizierst.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Stop, das eine hat mit dem anderen nichts zu tun. Natürlich gehe ich die Kollisionskette durch (gerade dafür brauche ich ja die Markierung), aber wenn die Suche negativ verläuft, kann ich das Element an die erste mögliche Position setzen, was zukünftigen Suchen definitiv zugute kommt.

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Beitrag von Hyst »

das hat ja auch in der vorlesung für diskussionen gesorgt....
im grunde darf man das... du kannst ein anderes element hinschreiben (WENN du es nicht duplizierst)
dann musst du dir aber den index des gelöschten elements zwischenspeichern, und weitersuchen.. und bei einer negativen suche dein neues element dort einfügen...
Laut Gallenbacher "macht man es aber nicht so"
einfacher ist es die kollisionsfunktion solange anzuwenden bis man auf ein freies feld kommt.

ist ja auch egal was besser ist was nicht...
mir geht es darum, dass: in der Vorlesung wurde uns DIES als methode vorgestellt.. jedoch stellt sich nun das problem mit den "leichen" und dem belegungsfaktor. Dass man, wenn man die methode benutzt, die tabelle erweitert obwohl der belegungsfaktor < 75% ist.
(mit leichen aber >= 75%)
und wie gesagt: ich hoffe das wird bei den testcases beachtet... *g*

Antworten

Zurück zu „Archiv“