Was für nen Algo hat map?
-
knivil schrieb:
mapp0r schrieb:
oje, dann wirds ja richtig lahmarschig, bei einigen mega einträgen.muss ich mir wohl selber was coden.
Ach, und hast du nachgemessen? Auch sollte der Aufwand einer Hashfunktion nicht unterschaetzt werden. Desweiteren ist std::map kein Algorithmus, sondern eine Datenstruktur.
Nein, ich habe noch nicht nachgemessen. Und ich habe auch nicht geschrieben, das std::map ein Algorithmus ist.
-
Tachyon schrieb:
std::mapbasiert vielleicht auf einer Datenstruktur, aber es ist keine Datenstruktur sondern ein Container. Da gehört dann auch Algorithmik dazu.Für den Begriff "Datenstruktur" gibt es keine allgemeingültige Definition. Eine so detailierte Diskussion ist daher sinnlos.
Je nach Definition enthalten Datenstrukturen auch Algorithmen. Ich würde sogar sagen, dass das die am weitesten verbreitete Definition von "Datenstruktur" ist. Also, kann map auch bedenkenlos als Datenstruktur bezeichnet werden.
-
Mitleid schrieb:
Je nach Definition enthalten Datenstrukturen auch Algorithmen. Ich würde sogar sagen, dass das die am weitesten verbreitete Definition von "Datenstruktur" ist. Also, kann map auch bedenkenlos als Datenstruktur bezeichnet werden.
Eigentlich gibt es da schon gängige Definitionen. Siehe z.B. "The Art of Computer Programming" oder "Algorithms and Data Structures".
Eine Struktur ist auch erstmal eine Struktur. Das hat mit Algorithmen wenig zu tun. Es gibt allerdings Algorithmen, mit denen man bestimmte Datenstrukturen idealerweise gewährleisten kann.
-
Tachyon schrieb:
Eine Struktur ist auch erstmal eine Struktur.
Wer könnte da widersprechen?
-
Tachyon schrieb:
Eigentlich gibt es da schon gängige Definitionen. Siehe z.B. "The Art of Computer Programming" oder "Algorithms and Data Structures".
Hab mal im Buch vom alten Knuth nachgesehen, aber keine explizite Definition für den Begriff gefunden. "Struct" würde ich auch nicht als Datenstruktur übersetzen. Den zweiten Buchtitel kenne ich nicht, vielleicht müsstest du noch den Autor angeben.
Aber, als "gängig" würde ich z.B. die Definition im Duden Informatik bezeichnen, denn die findet sich bei den meisten (aktuellen) Autoren wieder. Deshalb glaube ich kaum, dass du die Aussage map sei keine Datenstruktur aufrechterhalten kannst.
-
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Ein Red-Black-Tree ist eine Datenstruktur.
Ein AVL-Baum ist eine Datenstruktur.
Eine std::map ist keine Datenstruktur, sondern eine Black-Box.
-
hustbaer schrieb:
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Das ist irrelevant bzw. erkläre mal was du genau damit meinst.
-
Mitleid schrieb:
Das ist irrelevant bzw. erkläre mal was du genau damit meinst.
Wahrscheinlich meint er, dass die konkrete Datenstruktur, die
std::mapverwendet, implementierungsabhängig ist.
-
Nexus schrieb:
Wahrscheinlich meint er, dass die konkrete Datenstruktur, die
std::mapverwendet, implementierungsabhängig ist.Weiß nicht, ob er das meint. Wenn ja, dann würde ich sagen er liegt falsch, denn die Schnittstelle definiert ja bereits die Datenstruktur.
-
hustbaer schrieb:
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Du würdest also sagen, die folgende Aussage ist falsch? "std::map ist eine assoziative Datenstruktur, die Schlüssel zu Werten zuordnet und logarithmische Zeit für Einfüge-,Lösch- und Suchoperationen benötigt."
Schon lustig. Ich würde sowas bedenkenlos jederzeit als Datenstruktur bezeichnen. Das Konzept eines "Containers" ist mir hingegen in der theoretischen Informatik noch nie über den Weg gelaufen.
btw stimmt die entsprechende Wikipedia-Seite Dir nicht zu. Dort wird als Datenstruktur auch ein Graph genannt -- ohne konkrete Implementierung.
Typischerweise würde ich eine Datenstruktur über die angebotenen Operationen und deren Semantik definieren. Gegebenenfalls könnte man noch Performance-Garantien dazunehmen.
-
Jester schrieb:
Du würdest also sagen, die folgende Aussage ist falsch? "std::map ist eine assoziative Datenstruktur, die Schlüssel zu Werten zuordnet und logarithmische Zeit für Einfüge-,Lösch- und Suchoperationen benötigt.
Ja, die Aussage ist falsch.
"Container" ist ein wohl definierter Begriff aus der Typen-Theorie in der Informatik. Einem Container liegt zwar immer eine bestimmte Datenstruktur zugrunde, aber ein Container ist keine Datenstruktur.
-
Mitleid schrieb:
Nexus schrieb:
Wahrscheinlich meint er, dass die konkrete Datenstruktur, die
std::mapverwendet, implementierungsabhängig ist.Weiß nicht, ob er das meint. Wenn ja, dann würde ich sagen er liegt falsch, denn die Schnittstelle definiert ja bereits die Datenstruktur.
Komisch. Ein Stack oder eine Queue haben auch eine bestimmte Schnittstelle, und trotzdem ist die Datenstruktur dahinter relativ wahlfrei.
-
Nochmal, du machst Aussagen über einen Begriff der sehr unterschiedlich verwendet wird. Schreib einfach dazu, was du unter "Datenstruktur" verstehst, bzw. gib eine Definition an.
Ich beziehe mich z.B. auf die Definition im Duden Informatik, die ich auch in verschiedenen anderen Werken angetroffen habe. Danach ist map eine Datenstruktur.
Deswegen, kannst du auch nicht unbedingt sagen eine Aussage sei falsch. Vielleicht ist sie falsch, wenn man deine Definition von Datenstruktur als Grundlage nimmt. Das solltest du aber dazusagen, denn nicht jeder redet bei "Datenstruktur" über das, was du meinst.
-
Jester schrieb:
Typischerweise würde ich eine Datenstruktur über die angebotenen Operationen und deren Semantik definieren. Gegebenenfalls könnte man noch Performance-Garantien dazunehmen.
Und das ist dann eine abstrakte Datanstruktur.
Manchmal sehe ich auch, daß man Implemetierung verrät. Neulich las ich ein Paper über einen Algorithmus, da stand, wenn man eine verkettete Liste nimmt, kann man eine bestimmte Zeitkomplexität O() zu erreichen. Weder die Schnittstelle noch Performance-Garantien wurden verraten, die Konkretisierung auf "verkettete Liste" sagte alles.
-
volkard schrieb:
Neulich las ich ein Paper über einen Algorithmus, da stand, wenn man eine verkettete Liste nimmt, kann man eine bestimmte Zeitkomplexität O() zu erreichen. Weder die Schnittstelle noch Performance-Garantien wurden verraten, die Konkretisierung auf "verkettete Liste" sagte alles.
Ja, weil eine "verkettete Liste" eine absolute Standard-Datenstruktur ist, die typischerweise bestimmte Operationen mit typischen Performance-Garantien anbietet.
-
Tachyon schrieb:
Jester schrieb:
Du würdest also sagen, die folgende Aussage ist falsch? "std::map ist eine assoziative Datenstruktur, die Schlüssel zu Werten zuordnet und logarithmische Zeit für Einfüge-,Lösch- und Suchoperationen benötigt.
Ja, die Aussage ist falsch.
"Container" ist ein wohl definierter Begriff aus der Typen-Theorie in der Informatik. Einem Container liegt zwar immer eine bestimmte Datenstruktur zugrunde, aber ein Container ist keine Datenstruktur.Komischwerweise ist bei Wikipedia der Container im Bereich Datenstruktur eingeordnet. Demnach ist also jeder Container eine Datenstruktur. Nach der Länge des Wikipedia-Artikels zu urteilen, scheint es sich wohl nicht gerade um ein allzu zentrales Konzept zu handeln. Zudem ist es mir wie gesagt noch nie begegnet.
Der Begriff Container mag in C++ eine wichtige Rolle spielen, weil es eine sehr zentrale Abstraktion in der STL ist, aber in der Informatik an sich eher nicht. Da spricht man eben doch häufiger über Datenstrukturen. Wo hast Du diese lustigen Ideen eigentlich her?
-
hustbaer schrieb:
Ein Red-Black-Tree ist eine Datenstruktur.
Ein AVL-Baum ist eine Datenstruktur.
Eine std::map ist keine Datenstruktur, sondern eine Black-Box.Du meinst vermutlich
http://de.wikipedia.org/wiki/Abstrakter_Datentyp
im Gegensatz zu
http://de.wikipedia.org/wiki/DatenstrukturLeider nimmt Wikipedia sofort die Luft aus den Segeln
Der Übergang von der Datenstruktur zu einem Abstrakten Datentyp ist dabei nicht klar definiert, sondern hängt einzig von der Betrachtungsweise ab.
