Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

schnelle suche bei großen Datenmengen

  • 1
  • 2

Werbeanzeige

Faule Socke

Community-Fossil

Beiträge: 1 915

Wohnort: Schreibtischstuhl

  • Private Nachricht senden

11

21.10.2008, 21:40

Also am schnellsten sind vectoren wenn du access über nen index hast. da du aber keinen index, sondern eher so ne art id hast, würde ich dir zu std::map raten. das benutzt binäre suchbäume, ist recht schnell, dot kann dir das mit sicherheit erklären ;-)

Ansonsten fällt mir auch nichts ein, ich hab mich auch schon mal gefragt wie man das in großen Datenbanksystemen macht.


Socke

hanse

Alter Hase

Beiträge: 472

Wohnort: Wien

  • Private Nachricht senden

12

22.10.2008, 01:19

Iirc haben Hashtabellen im optimalen Fall (also ohne Kollision) eine Suchzeit von O(1), um worst case (alles eine Kollision) ist es dann von der Datenstruktur abhängig die verwendet wird um die Kollision zu lösen.

Hashtabellen sind aber recht schwer zu handhaben (Passende Hashfunktion suchen, dimensionieren, etc.)

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

13

22.10.2008, 02:59

@dot naja eig stimmte deine Aussage glaube ich schon. Vergleichbasierende Suchen können nicht schneller aus log n sein (Stichwort Entscheidungsbaum). Aber natürlich gibt es Hashmaps welche im Idealfall O(1) haben und im Normalfall O(m/n) (oder so ähnlich. Halt der Besetzheit des Universums aller Schlüssel).
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

14

22.10.2008, 11:29

Zitat von »"Jonathan_Klein"«


Es gibt auch eine hashmap in der STL, das wäre wohl auch ein Blick wert.


Die Hash-Container sind aber nicht deil der C++ Standard Bibliothek.
@D13_Dreinig

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

15

22.10.2008, 12:21

OT: ist eigentlich abzusehen, dass es bald eine Hashmap als Teil des Standards geben wird? Weil manchmal wäre das echt praktisch.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

16

22.10.2008, 12:48

Zitat von »"Nox"«

OT: ist eigentlich abzusehen, dass es bald eine Hashmap als Teil des Standards geben wird? Weil manchmal wäre das echt praktisch.


Ja, die Hash-Container befinden sich ja bereits im TR1. :)
@D13_Dreinig

theNoob

Frischling

  • »theNoob« ist der Autor dieses Themas

Beiträge: 6

  • Private Nachricht senden

17

22.10.2008, 18:31

Danke für die vielen schnellen Antworten!

Werde mich für map entscheiden, da es für index-namen das "schnellste" ist :)
um nochmals auf die Suchzeit zurück zu kommen, sind die folgenden Rechnungen richtig ? (habe in der Schule leider kein logarithmisches rechnen gehabt)
n = 128 => 7
n = 65536 => 16

also müsste man bei einer normalen Liste im worst case bei n=65536 eben 65536 Elemente durchsuchen und bei einer map nur 16 ?

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

18

22.10.2008, 18:38

Zitat von »"theNoob"«


Werde mich für map entscheiden, da es für index-namen das "schnellste" ist


Das kannst du nicht so allgemein sagen. Bei einer Hashtabelle, oder einen Hashindex, kannst du im besten Fall sogar eine Komplexität von nur O(1) erreichen.
@D13_Dreinig

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

19

22.10.2008, 19:47

Zu der Rechnung: Es kommt immer drauf an welche Basis man zu Grunde legt. Ich gehe mal davon aus, dass du die Basis 2 gewählt hast. Und ja dann stimmen deine Aussagen.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Werbeanzeige

  • 1
  • 2