Aktuelle Zeit: 23.02.2020 00:21

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 14 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 02:49 
Offline

Registriert: 15.11.2004 01:24
Code:
; 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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 04:11 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Maps sind normalerweise nie sortiert. Sie funktionieren mit Hashs. Und Hashs haben keine Ordnung bezüglich der Keys.

_________________
Ubuntu Gnome 19.04 LTS x64, PureBasic 5.71 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50, 5.60)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 07:30 
Offline

Registriert: 13.05.2010 09:26
Wohnort: Berlin
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

_________________
Dieser Satz ist falsch.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 07:46 
Offline

Registriert: 15.11.2004 01:24
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:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 08:07 
Offline

Registriert: 13.05.2010 09:26
Wohnort: Berlin
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

_________________
Dieser Satz ist falsch.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 19:51 
Offline

Registriert: 15.11.2004 01:24
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 22.06.2011 20:16 
Offline
Kommando SG1
Benutzeravatar

Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Ich habe das gefühl du verwechselst hier die PB-Map mit PB-LinkedList

Für den konkreten Fall:
Zitat:
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/viewtopic.php?p=279813#p279813

Eine sortierte Map (PB-Map) gibt es nicht, weil eine Map keine Liste ist, sonden nur ein Index

_________________
Bild
 
BildBildBild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 23.06.2011 13:23 
Offline

Registriert: 15.11.2004 01:24
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:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 01.12.2019 08:31 
Offline
Benutzeravatar

Registriert: 11.06.2017 20:25
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.

Zitat:
Code:
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:
 
  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̡̡̡̡.___٩(- ̮̮̃-̃)۶


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Map in Structuren werden nicht sortiert
BeitragVerfasst: 01.12.2019 13:07 
Offline
Benutzeravatar

Registriert: 24.11.2004 13:12
Wohnort: Germany
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 / OPC-Helper DLL
PB v3.30 / v5.4x - OS Mac Mini OSX 10.xx / Window 10 Pro. (X64) /Window 7 Pro. (X64) / Window XP Pro. (X86) / Ubuntu 14.04
Downloads auf My Webspace


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 14 Beiträge ]  Gehe zu Seite 1, 2  Nächste

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: Google [Bot] und 6 Gäste


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye