Eindeutige IDs als Longs erstellen

[NicTheQuick]

Nur zwei kleine Procedures, die IDs "erstellen", die man wieder "freigeben" kann. (Die Anführungszeichen sind beabsichtigt)

Einen Nachteil gibt es aber, der aber nicht weiter ins Gewicht fallen sollte: Wenn man eine ID mehrmals freigibt oder welche freigibt, die noch nicht mit [c]GetID()[/c] erstellt wurden, tauchen diese doppelt oder noch öfter wieder auf.

Code: Alles auswählen

NewList ID_free.l()

Procedure GetID()
  Static ID_pos.l
  Protected ID.l
  If FirstElement(ID_free())
    ID = ID_free()
    DeleteElement(ID_free())
    ProcedureReturn ID
  Else
    ID_pos + 1
    ProcedureReturn ID_pos
  EndIf
EndProcedure

Procedure FreeID(ID.l)
  If AddElement(ID_free())
    ID_free() = ID
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure


;/ Beispiel

For a.l = 1 To 10 ; 10 neue IDs holen
  Debug GetID()
Next

Debug "---"
For a.l = 3 To 7 ; 5 IDs wieder freigeben
  FreeID(a)
Next

For a.l = 1 To 7 ; 7 neue IDs holen
  Debug GetID()
Next

Würde man die Nachteile "rausprogrammieren" würde das System sicherlich langsamer funktionieren, außer jemand weiß wie man es dennoch annähernd so schnell lässt wie es bisher der Fall ist.

[Danilo]

@NicTheQuick:
Diesen Weg finde ich ziemlich komisch. Wenn man so z.B.
10.000 IDs anfordert ist alles OK. Sobald man diese IDs
aber dann freigibt werden Diese an eine Linkedlist angehangen,
wodurch der Speicherverbrauch des Programmes dann ansteigt.

Andersrum wäre es wohl logischer: Angeforderte IDs in eine
LinkedList eintragen, freigemachte IDs wieder aus der LL löschen.

[Mischa]

@Danilo:
Ich finde diese Methode keineswegs komisch. Denn Du mußt bei
Deinem Vorschlag schließlich immer erst die betreffende ID suchen,
oder nicht? Bei Nics Methode ist das nicht nötig.
Zwar verbraucht das mehr Speicher, dürfte aber schneller sein.

NicTheQuick:
Um Deine Frage zu beantworten. Ich habe diese von Dir hier
vorgestellte Methode letztes Jahr irgendwann im alten Forum
geposted, kann aber darauf zur Zeit nicht verlinken, da das Archiv
scheintot ist.
Doch gefunden:

Code: Alles auswählen

http://www.robsite.de/php/pureboard-archiv/viewtopic.php?t=3550&highlight=mischa

Also in wenigen Worten.
Du kannst eine Identifizierungsnummer ja nicht getrennt von dem
zu identifizierenden Objekt betrachten.
Diese Methode macht ja insbesondere, wenn nicht sogar ausschließlich
Sinn im Zusammenhang mit Arrays.

Wenn ich also ein Array von sagen wir 5000 Elementen habe und dieses
entsprechend strukturiert ist, kann ich doch problemlos eine Flag setzten,
ob das Element aktiv ist, bzw. existiert und infolgedessen gelöscht werden
kann.

Beispiel:

Code: Alles auswählen

Structure object
  exist.l
  typ.l
  bitmap.l
  ...
EndStructure

Beim erstellen setzte ich 'exist' auf 1, beim löschen auf 0.
Alternativ kann ich aber auch die Existenz über die z.B. Bitmap-ID
prüfen, um mir eine zusätzliche Flag zu sparen.
'bitmap' setze ich dann einfach auf 0, oder so ähnlich.

In jedem Fall ist zumindest eine Kontrolle dieser Art unvermeidbar und
als Alternative zum 'Durchgehen' der Löschliste wohl sehr viel schneller.

Gruß,
Mischa

[Danilo]

Ich finde diese Methode keineswegs komisch.

Ich schon.

Ich mußte Nics Code echt 5mal lesen bis ich verstanden habe
was das soll - und das passiert mir eigentlich sonst nicht.
Ein Element hinzuzufügen, wenn man eigentlich etwas freigeben
will, ist absolut unlogisch.

Denn Du mußt bei Deinem Vorschlag schließlich immer erst
die betreffende ID suchen, oder nicht?

Nicht unbedingt:

Code: Alles auswählen

NewList IDs.l()

Procedure GetID()
  LastElement(IDs())
  If AddElement(IDs())
    ProcedureReturn @IDs()
  EndIf
EndProcedure

Procedure FreeID(ID)
  If ID
    ChangeCurrentElement(IDs(),ID)
    DeleteElement(IDs())
  EndIf
EndProcedure



Dim a(10)

For a = 0 To 9
  a(a) = GetID()
  Debug a(a)
Next a

Debug "-----"
Debug Str(CountList(IDs())) + " IDs"
Debug "-----"


For a = 0 To 9
  FreeID(a(a))
  Debug CountList(IDs())
Next a

[Mischa]

@Danilo:

Ok, so kann man es auch machen, ist aber ca 30% langsamer:

Code: Alles auswählen

NewList IDs.l()

Procedure GetID()
  LastElement(IDs())
  If AddElement(IDs())
    ProcedureReturn @IDs()
  EndIf
EndProcedure

Procedure FreeID(ID)
  If ID
    ChangeCurrentElement(IDs(),ID)
    DeleteElement(IDs())
  EndIf
EndProcedure

Dim a(1000000)

time=timeGetTime_()
For b = 1 To 1000000
  a(b) = GetID()
Next b

For b = 1 To 1000000
  FreeID(a(b))
Next b
Debug timeGetTime_()-time




NewList ID_free.l()
Dim flag.l(1000000)

Procedure GetID2()
  Static ID_pos.l
  Protected ID.l
  If FirstElement(ID_free())
    ID = ID_free()
    DeleteElement(ID_free())
    flag(ID)=1
    ProcedureReturn ID
  Else
    ID_pos + 1
    flag(ID_pos)=1 
    ProcedureReturn ID_pos
  EndIf
EndProcedure

Procedure FreeID2(ID.l)
  If flag(ID)
    AddElement(ID_free())
    ID_free() = ID
    flag(ID)=0
  EndIf
EndProcedure

time=timeGetTime_()
For b.l = 1 To 1000000
  result=GetID2()
Next

For b.l = 1 To 1000000
  FreeID2(b)
Next
Debug timeGetTime_()-time

Abgesehen davon sprachst Du von unnötigem Speicherverbrauch.
Der ist bei Dir definitiv höher, wenn man annimmt, daß im Regelfall
mehr existierende Elemente als gelöschte vorhanden sind.
Aber na gut, das muß man wohl je nach Anwendung unterscheiden.

Gruß,
Mischa

[NicTheQuick]

Letztendlich kommt es wohl doch darauf an wie man es am liebsten hat oder was am vorteilhaftesten für das Programm ist.

Ich habe mal noch eine andere Methode umgesetzt, die nach dem Test sogar nochmal 13% schneller ist. Aber irgendwie bin ich mir nich ganz so sicher, ob diese Methode überhaupt richtig funktioniert. Aber ich hoffe doch schon, dass ich nicht schon zu viel getrunken habe.
Ich verschreibe mich zwar dauernd, aber naja.

Code: Alles auswählen

Procedure GetID()
  Static id_max.l
  Protected ID.l
  
  If CountList(ID_given()) = 0
    id_max + 1
    ProcedureReturn id_max
  Else
    FirstElement(ID_given())
    ID = ID_given()
    DeleteElement(ID_given())
    ProcedureReturn ID
  EndIf
  
EndProcedure

Procedure FreeID(ID.l)
  LastElement(ID_given())
  AddElement(ID_given())
  ID_given() = ID
EndProcedure

[Deeem2031]

Ich versteh irgendwie nich wozu das ganze gut sein soll.
Wenn ich eine ID brauch die sonst nicht verwendet wird reicht doch ein einfaches:

Code: Alles auswählen

Procedure GetID() 
  Static id.l 
  id + 1 
  ProcedureReturn id
EndProcedure

Wozu soll man die denn freigeben?

[Mischa]

@Deeem2031:

Ganz einfach: Wenn Du dynamisch Elemente verwalten willst
mit fester Adressierung, sprich Elemente löschen und/oder
neue erstellen, wird bei Deiner ID-Zuweisung der Counter
erbarmungslos immer höher und höher und höher gehen.

Wie eine Zeitbombe die tickt.
So was ist aber eventuell dann ganz nützlich für 'ne
Shareware-Version mit Zeitbegrenzung, da das Programm nach einer
unbestimmten Zeit einfach abschmiert.

Scherz beiseite. Beispiel: Arrays sind nunmal optimal wenns auf Geschwindigkeit
ankommt, fressen aber auch mehr Speicher, weil die Anzahl der
Elemente ja vorher festgelegt werden muß, ganz gleich wofür.
Wenn Du dann feste IDs brauchst, ist es notwendig ein freigebenes
Element mit z.B. ID 520 wiederzuverwenden und nicht den ID-Counter
fortlaufend zu erhöhen. Und diese 'freigewordenen' IDs muß man
sich ja irgendwie merken. Alles klar?

Gruß,
Mischa

[Deeem2031]

Ah, alles klar.
Frag ich mich nurnoch, ob es sinnvoll ist eine Linkedlist für die IDs eines Arrays zu erstellen, anstatt gleich eine Linkedlist zu nehmen.
Aber jedem das seine