PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

StringPool

https://www.purebasic.fr/german/viewtopic.php?t=17853

Seite 1 von 2

StringPool

Verfasst: 06.10.2008 21:49
von cxAlex
Hier ist ein kleiner String-Pool den ich unter anderem auch in PX verwende.

Der Pool erweitert sich dynamisch, erkennt doppelt verwendete Strings und kann auch Teilstrings anderer Strings verwenden um Speicher zu sparen.

zb.: Wenn man "weder" im Pool gespeichert und "der" im Pool speichern will kann der Pool erkennen das "der" schon in "weder" vorkommt und verwendet nur diesen Teilstring und legt nicht mehr Speicher an.

Der ganze Pool kann exportiert und z.b. in einer Datei gespeichert werden und wieder importiert werden.

Das schreiben in den Pool ist sehr viel langsamer als das lesen:
String Pool:
1.000.000 Schreiben : 10,87 Sek (ohne Tiefensuche)
1.000.000 Lesen : 16 ms

String Array:
1.000.000 Schreiben : 125 ms
1.000.000 Lesen : 78 ms
Für mich ist die Schreibgeschwindigkeit irrelevant da ich nur am anfang in den Pool schreibe und danach nur noch lese.

Wers braucht:


// EDIT: Neuer Code, kleiner Bug im alten

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; String-Pool
; Beliebig großer dynamischer String Pool
; ------------------------------------------------------------------------------------

Structure _SP_Entry
  Pos.l
  Size.l
EndStructure

Structure _SP_Array
  Entry._SP_Entry[0]
EndStructure

Global *_SP_Info._SP_Array, *_SP_Data, _SP_Size = 0, _SP_Count = 0

; Startwerte setzen
*_SP_Data = AllocateMemory(1)
*_SP_Info = AllocateMemory(1*SizeOf(_SP_Entry))
; Leere Strings abfangen
*_SP_Info\Entry[0]\Pos = 0
*_SP_Info\Entry[0]\Size = 0

Procedure _FindInMem(*Mem1, *Mem2, len1, len2)
  epos = len1-len2-1
  For i = 0 To epos
    If CompareMemory(*Mem1 + i, *Mem2, len2)
      ProcedureReturn i
    EndIf
  Next
  ProcedureReturn -1
EndProcedure

; Gibt den ganzen Speicher frei und stetzt alle Zähler zurück.
Procedure SP_Reset()
  FreeMemory(*_SP_Data) : *_SP_Data = AllocateMemory(1)
  FreeMemory(*_SP_Info) : *_SP_Info = AllocateMemory(1*SizeOf(_SP_Entry))
  *_SP_Info\Entry[0]\Pos = 0
  *_SP_Info\Entry[0]\Size = 0
  _SP_Size = 0
  _SP_Count = 0
EndProcedure

; Exportiert den Stringpool + Index in einen Speicher und gibt die Adresse darauf zurück
Procedure SP_Export()
  _SP_Info_Size = (_SP_Count + 1)*SizeOf(_SP_Entry)
  *ExportMem = AllocateMemory(_SP_Info_Size + _SP_Size + 2*SizeOf(LONG))
  PokeL(*ExportMem, _SP_Count)
  CopyMemory(*_SP_Info, *ExportMem + SizeOf(LONG), _SP_Info_Size)
  PokeL(*ExportMem + SizeOf(LONG) + _SP_Info_Size, _SP_Size)
  CopyMemory(*_SP_Data, *ExportMem + 2*SizeOf(LONG) + _SP_Info_Size, _SP_Size)
  ProcedureReturn *ExportMem
EndProcedure

; Importiert einen mit Sp_Export() erstellten Speicher
Procedure SP_Import(*Mem)
  FreeMemory(*_SP_Data)
  FreeMemory(*_SP_Info)
  _SP_Count = PeekL(*Mem)
  _SP_Info_Size = (_SP_Count + 1)*SizeOf(_SP_Entry)
  *_SP_Info = AllocateMemory(_SP_Info_Size)
  CopyMemory(*Mem + SizeOf(LONG), *_SP_Info, _SP_Info_Size)
  _SP_Size = PeekL(*Mem + SizeOf(LONG) + _SP_Info_Size)
  *_SP_Data = AllocateMemory(_SP_Size)
  CopyMemory(*Mem + 2*SizeOf(LONG) + _SP_Info_Size, *_SP_Data, _SP_Size)
  FreeMemory(*Mem)
EndProcedure

; Holt den String: Index
Procedure.s SP_Get(Index)
  If Index< = _Sp_Count
    ProcedureReturn PeekS(*_SP_Data + *_SP_Info\Entry[Index]\Pos, *_SP_Info\Entry[Index]\Size)
  EndIf
EndProcedure

; Speichert einen String im Pool und gibt einen Index darauf zurück
Procedure SP_Add(String.s, Search = 0, DeepSearch = 0)
  *SMem = @String
  Slen = MemoryStringLength(*SMem)
  
  ; Doppelte finden
  If Search
    For i = 0 To _SP_Count
      If *_SP_Info\Entry[i]\Size = Slen ; Zuerst nur Länge vergleichen
        If CompareMemory(*_SP_Data + *_SP_Info\Entry[i]\Pos, *SMem, Slen) ; Dann ganzen String
          ProcedureReturn i
        EndIf
      ElseIf DeepSearch And *_SP_Info\Entry[i]\Size>Slen ; String in anderen Strings finden
        tpos = _FindInMem(*_SP_Data + *_SP_Info\Entry[i]\Pos, *SMem, *_SP_Info\Entry[i]\Size, Slen)
        If tpos<> -1
          _SP_Count + 1
          *_SP_Info = ReAllocateMemory(*_SP_Info, (_SP_Count + 1)*SizeOf(_SP_Entry))
          *_SP_Info\Entry[_SP_Count]\Pos = *_SP_Info\Entry[i]\Pos + tpos
          *_SP_Info\Entry[_SP_Count]\Size = Slen
          ProcedureReturn _SP_Count
        EndIf
      EndIf
    Next
  EndIf
  _SP_Count + 1
  If Slen
    *_SP_Data = ReAllocateMemory(*_SP_Data, _SP_Size + Slen)
    *_SP_Info = ReAllocateMemory(*_SP_Info, (_SP_Count + 1)*SizeOf(_SP_Entry))
    CopyMemory(*SMem, *_SP_Data + _SP_Size, Slen)
    *_SP_Info\Entry[_SP_Count]\Pos = _SP_Size
    *_SP_Info\Entry[_SP_Count]\Size = Slen
    _SP_Size + Slen
    ProcedureReturn _SP_Count
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Verfasst: 06.10.2008 23:30
von HeX0R
Sehr nützlich :allright:

Ich habe mir mal erlaubt ein paar Veränderungen einzufügen, z.B. ging das nicht wirklich mit Unicode und es ist eine wahre Performancebremse nach jedem neuen String Speicher neu zu reservieren.

Das speichern sollte nun erheblich schneller gehn, keine Ahnung, ob ich irgendwo noch was falsch gemacht habe, zum Hardcoretesten fehlt mir noch ein Projekt ;)

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; String-Pool
; Beliebig großer dynamischer String Pool
; ------------------------------------------------------------------------------------
#PoolSize  = $4000
#ArraySize = 100

Structure _SP_Entry
	Pos.l
	Size.l
EndStructure

Structure _SP_Array
	Entry._SP_Entry[0]
EndStructure

Structure _SP_Globals
	*Info._SP_Array
	*Data
	Size.i
	Count.i
	PoolSize.i
	ArraySize.i
EndStructure

Macro SP_Init
	_SPG_\PoolSize           = #PoolSize
	_SPG_\Data               = AllocateMemory(_SPG_\PoolSize)
	_SPG_\ArraySize          = #ArraySize
	_SPG_\Info               = AllocateMemory(_SPG_\ArraySize * SizeOf(_SP_Entry))
	_SPG_\Info\Entry[0]\Pos  = 0
	_SPG_\Info\Entry[0]\Size = 0
	_SPG_\Size               = 0
	_SPG_\Count              = 0
EndMacro

Global _SPG_._SP_Globals

; Startwerte setzen
SP_Init

; Gibt den ganzen Speicher frei und stetzt alle Zähler zurück.
Procedure SP_Reset()

	FreeMemory(_SPG_\Data)
	FreeMemory(_SPG_\Info)
	SP_Init
EndProcedure

; Exportiert den Stringpool + Index in einen Speicher und gibt die Adresse darauf zurück
Procedure SP_Export()
	Protected Info_Size  = (_SPG_\Count + 1) * SizeOf(_SP_Entry)
	Protected *ExportMem = AllocateMemory(Info_Size + _SPG_\Size + 2 * SizeOf(LONG))

	PokeL(*ExportMem, _SPG_\Count)
	CopyMemory(_SPG_\Info, *ExportMem + SizeOf(LONG), Info_Size)
	PokeL(*ExportMem + SizeOf(LONG) + Info_Size, _SPG_\Size)
	CopyMemory(_SPG_\Data, *ExportMem + 2 * SizeOf(LONG) + Info_Size, _SPG_\Size)

	ProcedureReturn *ExportMem
EndProcedure

; Importiert einen mit Sp_Export() erstellten Speicher
Procedure SP_Import(*Mem)
	Protected Info_Size

	FreeMemory(_SPG_\Data)
	FreeMemory(_SPG_\Info)
	_SPG_\Count     = PeekL(*Mem)
	Info_Size       = (_SPG_\Count + 1) * SizeOf(_SP_Entry)
	_SPG_\ArraySize = (Int(Info_Size / #ArraySize) + 1) * #ArraySize
	_SPG_\Info      = AllocateMemory(_SPG_\ArraySize)
	_SPG_\Size      = PeekL(*Mem + SizeOf(LONG) + Info_Size)
	_SPG_\PoolSize  = (Int(_SPG_\Size / #PoolSize) + 1) * #PoolSize
	_SPG_\Data      = AllocateMemory(_SPG_\PoolSize)
	CopyMemory(*Mem + SizeOf(LONG), _SPG_\Info, Info_Size)
	CopyMemory(*Mem + 2*SizeOf(LONG) + Info_Size, _SPG_\Data, _SPG_\Size)
	FreeMemory(*Mem)
EndProcedure

; Holt den String: Index
Procedure.s SP_Get(Index)
	If Index <= _SPG_\Count
		ProcedureReturn PeekS(_SPG_\Data + _SPG_\Info\Entry[Index]\Pos, _SPG_\Info\Entry[Index]\Size, #PB_UTF8)
	EndIf
EndProcedure

; Speichert einen String im Pool und gibt einen Index darauf zurück
Procedure SP_Add(String.s, Search = 0, DeepSearch = 0)
	Protected *SMem = @String
	Protected Slen  = StringByteLength(String, #PB_UTF8)
	Protected tpos, i

	; Doppelte finden
	If Search
		For i = 1 To _SPG_\Count
			If _SPG_\Info\Entry[i]\Size = Slen ; Zuerst nur Länge vergleichen
				If PeekS(_SPG_\Data + _SPG_\Info\Entry[i]\Pos, Slen, #PB_UTF8) = String ; Dann ganzen String
					ProcedureReturn i
				EndIf
			ElseIf DeepSearch And _SPG_\Info\Entry[i]\Size > Slen ; String in anderen Strings finden
				tpos = FindString(PeekS(_SPG_\Data + _SPG_\Info\Entry[i]\Pos, _SPG_\Info\Entry[i]\Size, #PB_UTF8), String, 1) - 1
				If tpos <> -1
					_SPG_\Count + 1
					If _SPG_\Count >= _SPG_\ArraySize
						_SPG_\ArraySize + #ArraySize
						_SPG_\Info = ReAllocateMemory(_SPG_\Info, _SPG_\ArraySize * SizeOf(_SP_Entry))
					EndIf
					_SPG_\Info\Entry[_SPG_\Count]\Pos  = _SPG_\Info\Entry[i]\Pos + tpos
					_SPG_\Info\Entry[_SPG_\Count]\Size = Slen
					ProcedureReturn _SPG_\Count
				EndIf
			EndIf
		Next
	EndIf
	_SPG_\Count + 1
	If Slen
		If _SPG_\Count >= _SPG_\ArraySize
			_SPG_\ArraySize + #ArraySize
			_SPG_\Info = ReAllocateMemory(_SPG_\Info, _SPG_\ArraySize * SizeOf(_SP_Entry))
		EndIf
		While _SPG_\PoolSize < _SPG_\Size + Slen + SizeOf(CHARACTER)
			_SPG_\PoolSize + #PoolSize
			_SPG_\Data = ReAllocateMemory(_SPG_\Data, _SPG_\PoolSize)
		Wend
		PokeS(_SPG_\Data + _SPG_\Size, String, -1, #PB_UTF8)
		_SPG_\Info\Entry[_SPG_\Count]\Pos  = _SPG_\Size
		_SPG_\Info\Entry[_SPG_\Count]\Size = Slen
		_SPG_\Size + Slen
		ProcedureReturn _SPG_\Count
	Else
		ProcedureReturn 0
	EndIf
EndProcedure

Verfasst: 07.10.2008 14:27
von cxAlex
Ja geht schneller. Allerdings bremst das UTF8 das lesen bei mir extrem aus, teilweise ums 10 fache. Ich hab das ganze jetzt wieder auf ASCII-only umgestellt, aber sonst verwende ich deine Verbesserungen. Danke! :D :D

Verfasst: 07.10.2008 15:34
von STARGÅTE
sry aber ich kann mir gerade unter einem StringPool nix vorstellen ...

könntest du mal kurz n Beispiel zur Anwendung posten, wäre nett danke ...

Verfasst: 07.10.2008 16:01
von Kiffi
@STARGÅTE: Hier ist ein StringPool

Grüße ... Kiffi

Verfasst: 07.10.2008 16:33
von cxAlex
@Kiffi: :lol: :lol: :lol: :lol:

@Stargate:

Das Funktioniert so:
Index1 = SP_Add("weder")
Index2 = SP_Add("der")

String1.s = SP_Get(Index1)
String2.s = SP_Get(Index2)
Relativ klar bis jetzt oder?
Nur das 'Index2 = SP_Add("der")' keinen neuen Eintrag erzeug sondern nur auf das "der" in "werder" zeigt. Spart Speicher und ist beim lesen schneller als ein String Array. oOder du legst mehrere Pools an z.B. mit verschiedenen Sprachen und lädst dann die jeweilige.

Verfasst: 07.10.2008 18:38
von HeX0R
cxAlex hat geschrieben:Ja geht schneller. Allerdings bremst das UTF8 das lesen bei mir extrem aus, teilweise ums 10 fache.
Ja, is logisch, da die Strings ja immer erst umgewandelt werden.
Ich habe UTF8 eigentlich deswegen genommen, damit der Byteverbrauch nicht unnötig groß wird (bei Unicode ja zwei Bytes pro Char).
Nur im Ascii-Modus is das Quark.

Hier eine bessere Variante:

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; String-Pool
; Beliebig großer dynamischer String Pool
; ------------------------------------------------------------------------------------
#PoolSize  = $4000
#ArraySize = 100

CompilerIf #PB_Compiler_Unicode
#_SP_MODE = #PB_UTF8
CompilerElse
#_SP_MODE = #PB_Ascii
CompilerEndIf

Structure _SP_Entry
	Pos.l
	Size.l
EndStructure

Structure _SP_Array
	Entry._SP_Entry[0]
EndStructure

Structure _SP_Globals
	*Info._SP_Array
	*Data
	Size.i
	Count.i
	PoolSize.i
	ArraySize.i
EndStructure

Macro SP_Init
	_SPG_\PoolSize           = #PoolSize
	_SPG_\Data               = AllocateMemory(_SPG_\PoolSize)
	_SPG_\ArraySize          = #ArraySize
	_SPG_\Info               = AllocateMemory(_SPG_\ArraySize * SizeOf(_SP_Entry))
	_SPG_\Info\Entry[0]\Pos  = 0
	_SPG_\Info\Entry[0]\Size = 0
	_SPG_\Size               = 0
	_SPG_\Count              = 0
EndMacro

Global _SPG_._SP_Globals

; Startwerte setzen
SP_Init

; Gibt den ganzen Speicher frei und stetzt alle Zähler zurück.
Procedure SP_Reset()

	FreeMemory(_SPG_\Data)
	FreeMemory(_SPG_\Info)
	SP_Init
EndProcedure

; Exportiert den Stringpool + Index in einen Speicher und gibt die Adresse darauf zurück
Procedure SP_Export()
	Protected Info_Size  = (_SPG_\Count + 1) * SizeOf(_SP_Entry)
	Protected *ExportMem = AllocateMemory(Info_Size + _SPG_\Size + 2 * SizeOf(LONG))

	PokeL(*ExportMem, _SPG_\Count)
	CopyMemory(_SPG_\Info, *ExportMem + SizeOf(LONG), Info_Size)
	PokeL(*ExportMem + SizeOf(LONG) + Info_Size, _SPG_\Size)
	CopyMemory(_SPG_\Data, *ExportMem + 2 * SizeOf(LONG) + Info_Size, _SPG_\Size)

	ProcedureReturn *ExportMem
EndProcedure

; Importiert einen mit Sp_Export() erstellten Speicher
Procedure SP_Import(*Mem)
	Protected Info_Size

	FreeMemory(_SPG_\Data)
	FreeMemory(_SPG_\Info)
	_SPG_\Count     = PeekL(*Mem)
	Info_Size       = (_SPG_\Count + 1) * SizeOf(_SP_Entry)
	_SPG_\ArraySize = (Int(Info_Size / #ArraySize) + 1) * #ArraySize
	_SPG_\Info      = AllocateMemory(_SPG_\ArraySize)
	_SPG_\Size      = PeekL(*Mem + SizeOf(LONG) + Info_Size)
	_SPG_\PoolSize  = (Int(_SPG_\Size / #PoolSize) + 1) * #PoolSize
	_SPG_\Data      = AllocateMemory(_SPG_\PoolSize)
	CopyMemory(*Mem + SizeOf(LONG), _SPG_\Info, Info_Size)
	CopyMemory(*Mem + 2*SizeOf(LONG) + Info_Size, _SPG_\Data, _SPG_\Size)
	FreeMemory(*Mem)
EndProcedure

; Holt den String: Index
Procedure.s SP_Get(Index)
	If Index <= _SPG_\Count
		ProcedureReturn PeekS(_SPG_\Data + _SPG_\Info\Entry[Index]\Pos, _SPG_\Info\Entry[Index]\Size, #_SP_MODE)
	EndIf
EndProcedure

; Speichert einen String im Pool und gibt einen Index darauf zurück
Procedure SP_Add(String.s, Search = 0, DeepSearch = 0)
	Protected *SMem = @String
	Protected Slen  = StringByteLength(String, #_SP_MODE)
	Protected tpos, i

	; Doppelte finden
	If Search
		For i = 1 To _SPG_\Count
			If _SPG_\Info\Entry[i]\Size = Slen ; Zuerst nur Länge vergleichen
				If PeekS(_SPG_\Data + _SPG_\Info\Entry[i]\Pos, Slen, #_SP_MODE) = String ; Dann ganzen String
					ProcedureReturn i
				EndIf
			ElseIf DeepSearch And _SPG_\Info\Entry[i]\Size > Slen ; String in anderen Strings finden
				tpos = FindString(PeekS(_SPG_\Data + _SPG_\Info\Entry[i]\Pos, _SPG_\Info\Entry[i]\Size, #_SP_MODE), String, 1) - 1
				If tpos <> -1
					_SPG_\Count + 1
					If _SPG_\Count >= _SPG_\ArraySize
						_SPG_\ArraySize + #ArraySize
						_SPG_\Info = ReAllocateMemory(_SPG_\Info, _SPG_\ArraySize * SizeOf(_SP_Entry))
					EndIf
					_SPG_\Info\Entry[_SPG_\Count]\Pos  = _SPG_\Info\Entry[i]\Pos + tpos
					_SPG_\Info\Entry[_SPG_\Count]\Size = Slen
					ProcedureReturn _SPG_\Count
				EndIf
			EndIf
		Next
	EndIf
	_SPG_\Count + 1
	If Slen
		If _SPG_\Count >= _SPG_\ArraySize
			_SPG_\ArraySize + #ArraySize
			_SPG_\Info = ReAllocateMemory(_SPG_\Info, _SPG_\ArraySize * SizeOf(_SP_Entry))
		EndIf
		While _SPG_\PoolSize < _SPG_\Size + Slen + SizeOf(CHARACTER)
			_SPG_\PoolSize + #PoolSize
			_SPG_\Data = ReAllocateMemory(_SPG_\Data, _SPG_\PoolSize)
		Wend
		PokeS(_SPG_\Data + _SPG_\Size, String, -1, #_SP_MODE)
		_SPG_\Info\Entry[_SPG_\Count]\Pos  = _SPG_\Size
		_SPG_\Info\Entry[_SPG_\Count]\Size = Slen
		_SPG_\Size + Slen
		ProcedureReturn _SPG_\Count
	Else
		ProcedureReturn 0
	EndIf
EndProcedure

Verfasst: 07.10.2008 21:15
von Kaeru Gaman
ich frag mich, warum ihr einen extra-stringpool bauen wollt, PB benutzt doch grundsätzlich einen.
das ist der grund, warum dynamische strings in strukturen nur einen pointer lang sind,
und warum das am anfang so ein tanz mit "Threadsafe" war.

Verfasst: 07.10.2008 21:48
von cxAlex
@Kaeru
Ich brauch den für meinen Interpreter, und hab einfach gedacht vieleicht braucht den ja sonst noch jemand, ich hab mir hier viele Tipps und Codes für PX geholt, geb ich auch mal was zurück.

@Hexor: ^^ genau so hab ich deine alte Version auch umgebaut!

Verfasst: 07.10.2008 21:55
von Kaeru Gaman
> Ich brauch den für meinen Interpreter

verstehe. für solche Projekte ist eine eigene Verwaltung natürlich nützlich/notwendig. :allright:
Alle Zeiten sind UTC+02:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de