Map in Structuren werden nicht sortiert

Für allgemeine Fragen zur Programmierung mit PureBasic.
Cardian
Beiträge: 40
Registriert: 15.11.2004 01:24

Map in Structuren werden nicht sortiert

Beitrag von Cardian »

Code: Alles auswählen

; eine Structure enthält eine Map:
Structure structRecord
  Map Test.s()
EndStructure

; diese Map ist Bestandteil einer größeren Map:
Global NewMap Records.structRecord()
Define i.l

; die 'Ober-Map' wird angelegt:
AddMapElement(Records(), "A")
; in die 'Unter-Map' werden 200 Einträge mit zufälligen Keys gemacht:
For i = 0 to 200
  AddMapElement(Records()\Test(), Str(100 + Random(800)))  ; so wird alles dreistellig
Next

End   ; <- diesen Befehl mal stoppen
Nun kontrolliere man im VariablenDebugger die Keys der untergeordneten Map.

Normalerweise sollten die Keys einer Map immer sortiert sein,
aber die Keys sind nicht sortiert. Insbesondere je mehr Einträge gemacht werden.
Somit bedeutet dies das Maps nicht in Structuren unterstützt werden.

Man kann allerdings eine Teilsortierung entdecken, darum vermute ich einen Bug.

OS: XP
PureBasic: 4.50 & 4.51
Edit: einige Korrekturen
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8679
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Map in Structuren werden nicht sortiert

Beitrag von NicTheQuick »

Maps sind normalerweise nie sortiert. Sie funktionieren mit Hashs. Und Hashs haben keine Ordnung bezüglich der Keys.
Bild
Nino
Beiträge: 1300
Registriert: 13.05.2010 09:26
Wohnort: Berlin

Re: Map in Structuren werden nicht sortiert

Beitrag von Nino »

Cardian hat geschrieben:Normalerweise sollten die Keys einer Map immer sortiert sein
Blödsinn. Eventuell vorhandene Teilsortierungen sind reiner Zufall.

2NicTheQuick:
Du hst natürlich völlig Recht. Da Du auch Moderator bist, könntest Du bitte diesen Thread aus dem Bugforum herausnehmen und woanders hinschieben?

Danke und Grüße, Nno
Cardian
Beiträge: 40
Registriert: 15.11.2004 01:24

Re: Map in Structuren werden nicht sortiert

Beitrag von Cardian »

Naja ich kenne das von C++. Map ist der Ausdruck einer Karte, in der der Suchaufwand möglichst gering sein soll (log n)
und der Key üblicherweise eindeutig ist (gibt auch Multimap). Ab einer gewissen Größe geht da nämlich richtig Performance drauf.

Aber wenn PureBasic Hashs als Maps bezeichnet, dann sorry (ich habs nochmal in der Hilfe nachgelesen, ihr habt natürlich recht).
Warum wird dies eigentlich nicht als Hash benannt? *echt grübel*

Bedeutet das nun daß jedesmal wenn ich einen Wert sortiert einlesen will, weil ich ihn dann sortiert benötige, ich müßte jedesmal
eine Umsortierung (zB. SortStructuredList, SortArray u.ä.) durchführen oder eine eigene Sortierfunktion entwickeln? :roll:

Naja kann man wohl nix machen ... :cry:
Nino
Beiträge: 1300
Registriert: 13.05.2010 09:26
Wohnort: Berlin

Re: Map in Structuren werden nicht sortiert

Beitrag von Nino »

Cardian hat geschrieben:Naja ich kenne das von C++. Map ist der Ausdruck einer Karte, in der der Suchaufwand möglichst gering sein soll (log n)
und der Key üblicherweise eindeutig ist (gibt auch Multimap). Ab einer gewissen Größe geht da nämlich richtig Performance drauf.

Aber wenn PureBasic Hashs als Maps bezeichnet, dann sorry (ich habs nochmal in der Hilfe nachgelesen, ihr habt natürlich recht).
Warum wird dies eigentlich nicht als Hash benannt? *echt grübel*
In C++ ist mit "Map" keine Karte gemeint. :freak: Und auch in C++ sind Maps nicht sortiert.
Wikipedia hat geschrieben:Das assoziative Datenfeld (englisch „associative array“) ist eine Datenstruktur, die – anders als ein echtes Feld (englisch „array“) – nichtnumerische Schlüssel (zumeist Zeichenketten) verwendet, um die enthaltenen Elemente zu adressieren; diese liegen in keiner festgelegten Reihenfolge vor. Idealerweise werden die Schlüssel so gewählt, dass eine für die Programmierer nachvollziehbare Verbindung zwischen Schlüssel und Datenwert besteht. Mathematisch betrachtet wird durch die Wertezuordnungen im assoziativen Array eine Funktion mit endlichem Wertebereich beschrieben. Eine Implementierung ist mit Bäumen möglich, die bei weitem häufigste Umsetzung ist jedoch die Hashtabelle.

Programmiersprachen, die assoziative Felder unterstützen, sind zum Beispiel Lua, Perl, PHP, Python, Ruby, LISP, Tcl, Smalltalk, C++, C#, Objective-C (als Klasse der Standardbibliothek), D, Java, Delphi (als Array-Property), PostScript, GNU Bourne-again shell (ab Version 4.0), PL/SQL und Visual Basic. Statt von einem assoziativen Array spricht man auch von einem Dictionary (Smalltalk, Python, Objective-C, PostScript, C#), einer Map (C++, Java), einem Hash (Perl, Ruby), einem Objekt (Javascript) oder einer Hashtable/Hashmap (Java, Windows PowerShell).
Cardian hat geschrieben:Bedeutet das nun daß jedesmal wenn ich einen Wert sortiert einlesen will, weil ich ihn dann sortiert benötige, ich müßte jedesmal
eine Umsortierung (zB. SortStructuredList, SortArray u.ä.) durchführen oder eine eigene Sortierfunktion entwickeln? :roll:
siehe z.B. http://forums.purebasic.com/german/view ... 13#p279813
Cardian
Beiträge: 40
Registriert: 15.11.2004 01:24

Re: Map in Structuren werden nicht sortiert

Beitrag von Cardian »

Na dann hab ich ja richtig Glück mit den C++-Maps, die bei mri seit vielen Jahren IMMER sortierten Zugriff zu haben.

Die Ablage im Speicher ist uninteressant, aber die jeweiligen Keys sind sortiert 'organisiert'.

"Eine Sortierung der map ist nicht notwendig, um eine sortierte Ausgabe zu erhalten."
Bjarne Stroustrup (Die C++ Programmiersprache, S.67)

"Eine map setzt vorraus, daß für den Schlüssel der kleiner-als-Operator existiert {nötig damit es sortiert werden kann},
und sortiert die Elemente so, daß eine Iteration {prev oder next} alle Elemente aufsteigend durchläuft." (S.510)
(geschweiftes von mir)

Suchfunktionen sind eine ganz häufige Anforderungen in Programmen (sollte euch nichts neues sein), aber auch das Einfügen und Entfernen
von Elemente sind ganz wichtige Anforderungen. Schon aufgrund des Entfernen ist eine physikalisches Sortierthalten völlig unsinnig, weil
dann entweder 'Löcher' im Speicherbereich (ungenutzte Sätze) entstehen würden oder der Speicher jedesmal neu umkopiert werden müsste.
Das eine ist Speichervergeudung, das andere ist eine teuere Operation. Darum ist es egal, wo der Datensatz im Speicher liegt!
Wichtig ist allerdings eine sortierte Datenhaltung ... das ist je nach Sprache und Implementation auch unterschiedlich gelöst und muß den
Programmierer auch nicht kümmern.

Beispiel:
Stellt euch vor, ihr benötigt eine Warteschlange von Druckaufträgen, deren Priorität und auch Existenz sich jederzeit ändern kann.
Die beste Variante ist die, dieser Warteschlange grundsätzlich einen sortierten Zugriff zu ermöglichen, damit z.B. der Auftrag mit der
höchsten Priorität zuerst abgearbeitet werden kann. Es kommen aber ständig neue Aufträge hinzu und es werden auch alte Aufträge
wieder entfernt (z.B. weil es ihnen zu lange dauert). Dazu kommt, daß diese Warteschlange sehr groß ist und sie immer aktuell gehalten
werden muß.
Dieses Problem mit Sortierfunktionen zu lösen, wann immer Einträge dazukommen oder gelöscht werden, ist viel zu teuer und damit zu
langsam. Es ist bedeutend effizienter der Warteschlange einen sortierten Zugriff zu spendieren (vornehmlich eine Baumsortierung),
was einen kostengünstigen Suchalgorithmus erlaubt.
Ein Eintrag dazu: -> Suche den Key der größer als Eintrag ist -> füge Eintrag davor ein -> fertig.
Ein Eintrag weg: -> Suche den Key der gleich Eintrag ist -> wenn gefunden, baumtechnisch herauslösen -> fertig
Ein Eintrag drucken: -> Geh zum ersten -> löse ihn heraus -> drucke ihn -> fertig
Ein Eintrag ändert seine Priorität: -> Suche den Key der gleich Eintrag ist -> wenn gefunden, baumtechnisch herauslösen ->
Priorität ändern -> Suche den Key der größer als Eintrag ist -> füge Eintrag davor ein -> fertig
Physikalisch wird hier nie was sortiert, aber die Organisation, der Zugriff über die Keys, ist effizient sortiert.

Aus diesem Grund hat man in C++ bzw. der STL map / multimap / set / multiset. Aber es gibt auch HashMap und Unordered_Map u.ä.
Hashs wurden in die STL damals wegen der Zeitknappheit nicht aufgenommen, was wirklich schade ist.
In Java gibt es extra auch eine TreeMap, weil bei denen Map im allgemeinen HashMap bedeutet.

Allerdings wird schon mal gedrängelt nach einer Sortierung der Werte (nicht des Keys). Dies leistet zumindest eine C++-Map nicht.

Weiß einer wie PureBasic seine Keys in Maps sucht? Ich vermute das ist ne schöne Assemblerschleife (der Aufwand müsste dann linear
ansteigen). Oder (was ich nicht zu hoffen wage) Fred hat eine interne Sortierung, die er uns nur nicht zugänglich macht. *böser Fred*

Zu dem Wikipedia-Artikel: der ist ... naja ... da stimmt vieles nicht. Kommt aber auch davon, weil viele Sprachen vorhandene Begriffe umdefinieren.
Zu dem Link: Ja das wäre die nächste Alternative, wenn es kein C++ gäbe.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6999
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Map in Structuren werden nicht sortiert

Beitrag von STARGÅTE »

Ich habe das gefühl du verwechselst hier die PB-Map mit PB-LinkedList

Für den konkreten Fall:
Ein Eintrag dazu: -> Suche den Key der größer als Eintrag ist -> füge Eintrag davor ein -> fertig.
Ein Eintrag weg: -> Suche den Key der gleich Eintrag ist -> wenn gefunden, baumtechnisch herauslösen -> fertig
Ein Eintrag drucken: -> Geh zum ersten -> löse ihn heraus -> drucke ihn -> fertig
Ein Eintrag ändert seine Priorität: -> Suche den Key der gleich Eintrag ist -> wenn gefunden, baumtechnisch herauslösen ->
Priorität ändern -> Suche den Key der größer als Eintrag ist -> füge Eintrag davor ein -> fertig
Nutzt "man" eine LinkedList, in der jedes Elemente Vorgänger und Nachfolger hat.

So halt man jederzeit eine festgelegte Reihenfolge (sortierung)

Falls nun noch ein direkter zugriff erwünscht ist, kann paralleldazu ein Index angelegt werden, ähnlcih wie es in Datenbanken der Fall ist.
Also entweder ein Array oder eine Map.

Ein Beispiel dazu habe ich schon mal geschrieben:
http://www.purebasic.fr/german/viewtopi ... 13#p279813

Eine sortierte Map (PB-Map) gibt es nicht, weil eine Map keine Liste ist, sonden nur ein Index
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Cardian
Beiträge: 40
Registriert: 15.11.2004 01:24

Re: Map in Structuren werden nicht sortiert

Beitrag von Cardian »

Ja, ich habs schon gelöst. Trotzdem danke an alle.
... und Schande über mich, denn in der Hilfe hätt ich das schon lesen müssen.

Schade das es in PureBasic kein permanent sortierten Modus gibt.
In C++ arbeite ich sehr häufig mit Maps, weil "hau rein", "hau raus", "nächsten",
"vorherigen", "suche", "verschieben" ... alles easy und schnell.
Hashs nutze ich nur, wenn es Sinn macht.

Hatte mal übrigens n Projekt in PB (noch vor den Maps), was eine permanent
sortierte Map enthielt. Hab das aber irgendwann nicht mehr weiterentwickelt
wegen irgendwelcher PB-Umstellungen.
War mal sone Überlegung der Community was zurückzugeben, denn die Leute
sind hier schon echt aktiv, nett, sachlich ... findet man nicht oft. :allright:
Benutzeravatar
GlassJoe
Beiträge: 108
Registriert: 11.06.2017 20:25
Computerausstattung: 2 x AMD Phenom II x4 945,2x Dell Latitude X300, Dell Latitude D410, Hp Compaq NC4400

Re: Map in Structuren werden nicht sortiert

Beitrag von GlassJoe »

Ich möchte einen fetten Dank an Cardian den Thread Ersteller ausrichten ! (der wesentlich einfallsreicher und abstrakter
denken kann als ich :lol: )
Seit ewigkeiten suche ich nach einer schnellen (also map) und speicherschonenden Möglichkeit
einem Map Element mehrere Einträge zuzuweisen..........die PB Hilfe hat mir vor 2 Stunden ^^ einen kleinen
Anhaltpunkt gegeben.

Code: Alles auswählen

Beispiel: Dynamisches Objekt

  Structure Person
    Name$
    Age.l
    List Friends$()
  EndStructure

  John.Person
  John\Name$ = "John"
  John\Age   = 23
  
  ; Jetzt fügen wir einige Freunde zu John hinzu
  ;
  AddElement(John\Friends$())
  John\Friends$() = "Jim"

  AddElement(John\Friends$())
  John\Friends$() = "Monica"
  
  ForEach John\Friends$()
    Debug John\Friends$()
  Next
Bin aber ums verrecken nicht darauf gekommen wie mann Structure erstellen könnte die eine Map enthält b.z.w diese
ansprechen könnte, und bin erst Recht nicht darauf gekommen das eine Map in einer Strukture eine Sub Map/Listhaben kann.

Ich hab locker eine Stunde alle möglichen Suchbegriffe probiert (map als Suchbegriff wird übrigends völlig von der Suche ignoriert)

Sachen wie B-Tree (das B- wird von der Suche ignoriert), Map mehreren, Map füllen, Map Dateiliste usw usw
brachte alles nichts (auch newmap in kombination mit füllen usw brachte nichts, nur zitausend treffer die nichts
damit zutun hatten) erst treemap gab 3 Treffer.

Und durch die Vorlage & Idee von Cardian konnte ich endlich etwas basteln, mit dem ich pro MapElement/Foldername
eine eigene Dateiliste speichern kann...........was mir (und ich denke mal vielen anderen auch) sehr hilft wenn
mann das braucht. z.B wenn mann einen Folder & File Index hat, der nicht auf der HD vorhanden ist, und mann will schnell
den Folder einer Map (nach einem Doppelklick) selektieren dessen Sub Filelist/FileMap dann eine Gadgetlist füllt)

Hier der Code den ich daraus basteln konnte (enthält Pseudo Input Daten, Hauptsache das Prinzip ist da)

Code: Alles auswählen

  
  EnableExplicit
  
  Define c.i
  
  Structure FileData
    Name.s
    Attrib.s
  EndStructure
  
  Structure StrucFiles
    Map FilesMap.FileData()
    List FilesLL.FileData()
  EndStructure
  
  NewMap DirMap.StrucFiles()
  
  AddMapElement(DirMap(), "C:\A\")
  For c = 0 To 19
    AddMapElement(DirMap()\FilesMap(), Str(c))
    DirMap()\FilesMap()\Attrib = "H"
    
    AddElement(DirMap()\FilesLL()) 
    DirMap()\FilesLL()\Name = Str(c) 
    DirMap()\FilesLL()\Attrib = "H"
  Next
  
  AddMapElement(DirMap(), "C:\B\")
  For c = 20 To 39
    AddMapElement(DirMap()\FilesMap(), Str(c)) 
    DirMap()\FilesMap()\Attrib = "H"
    
    AddElement(DirMap()\FilesLL()) 
    DirMap()\FilesLL()\Name = Str(c) 
    DirMap()\FilesLL()\Attrib = "H"
  Next
  
  AddMapElement(DirMap(), "C:\C\")
  For c = 40 To 59
    AddMapElement(DirMap()\FilesMap(), Str(c)) 
    DirMap()\FilesMap()\Attrib = "H"
    
    AddElement(DirMap()\FilesLL()) 
    DirMap()\FilesLL()\Name = Str(c) 
    DirMap()\FilesLL()\Attrib = "H"
  Next
  
  AddMapElement(DirMap(), "C:\D\")
  For c = 60 To 79
    AddMapElement(DirMap()\FilesMap(), Str(c)) 
    DirMap()\FilesMap()\Attrib = "H"
    
    AddElement(DirMap()\FilesLL()) 
    DirMap()\FilesLL()\Name = Str(c) 
    DirMap()\FilesLL()\Attrib = "H"
  Next
  
  Debug "---------"
  
  ;/ JETZT NOCH 60 bis 80 WEIL DAS ZULETZT GEADDETE AKTIV IST B.Z.W Der Key (C:\D\) von der DirMap() Map
  Debug "----DEBUG LINKED LIST"
  ForEach DirMap()\FilesLL()
    Debug DirMap()\FilesLL()\Name+" "+DirMap()\FilesLL()\Attrib 
  Next
  Debug "----DEBUG MAP"
  ForEach DirMap()\FilesMap()
    Debug MapKey(DirMap()\FilesMap())+" "+DirMap()\FilesMap()\Attrib
  Next
  
  Debug ""
  Debug "-B-" 
  If FindMapElement(DirMap(),"C:\B\")
    ForEach DirMap()\FilesLL()
      Debug DirMap()\FilesLL()\Name+" "+DirMap()\FilesLL()\Attrib  
    Next 
  EndIf
  
  Debug "" 
  Debug "-A-"
  If FindMapElement(DirMap(),"C:\A\")
    ForEach DirMap()\FilesLL()
      Debug DirMap()\FilesLL()\Name+" "+DirMap()\FilesLL()\Attrib  
    Next 
    
    Debug "-A-----> BUT NOW THE SUB MAP"
    ;/ DAS GEILSTE ! DIE UNTERMAP IST TROTZDEM SORTIERT ! UND NICHT WILD DURCHEINANDER WIE BEI DER OBERMAP
    ;/ WEIS DER GEIER WARUM
    If FindMapElement(DirMap()\FilesMap(),"5")
      Debug "FOUND 5"
      ForEach DirMap()\FilesMap()
        Debug MapKey(DirMap()\FilesMap())+" "+DirMap()\FilesMap()\Attrib 
      Next 
    EndIf
  EndIf
  
  Debug "" 
  Debug "-D-"
  If FindMapElement(DirMap(),"C:\D\")
    ForEach DirMap()\FilesLL()
      Debug DirMap()\FilesLL()\Name+" "+DirMap()\FilesLL()\Attrib  
    Next 
  EndIf
  
  Debug "" 
  Debug "-C-"
  If FindMapElement(DirMap(),"C:\C\")
    ForEach DirMap()\FilesLL()
      Debug DirMap()\FilesLL()\Name+" "+DirMap()\FilesLL()\Attrib  
    Next 
  EndIf 
Warum die SubMap sortiert ist weis ich auch nicht :bounce: aber egal, Hauptsache es funzt !
https://www.geek.com/tech/a-commodore-6 ... s-1672510/
٩(̾●̮̮̃̾•̃̾)۶ __̴ı̴̴̡̡̡ ̡͌l̡̡̡ ̡͌l̡*̡̡ ̴̡ı̴̴̡ ̡̡͡|̲̲̲͡͡͡ ̲▫̲͡ ̲̲̲͡͡π̲̲͡͡ ̲̲͡▫̲̲͡͡ ̲|̡̡̡ ̡ ̴̡ı̴̡̡ ̡͌l̡̡̡̡.___٩(- ̮̮̃-̃)۶
Benutzeravatar
mk-soft
Beiträge: 3701
Registriert: 24.11.2004 13:12
Wohnort: Germany

Re: Map in Structuren werden nicht sortiert

Beitrag von mk-soft »

GlassJoe hat geschrieben:Warum die SubMap sortiert ist weis ich auch nicht :bounce: aber egal, Hauptsache es funzt !
Schlechte Vorgehensweise. Nur weil es in diesen Fall zufällig funktioniert, kann man davon nicht ausgehen das es immer funktioniert.
Maps sind nicht sortiert...
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Antworten