Schnellste StringReplacer-Operation gesucht?

Tana´Ri · Beiträge: 230

Hi Leute,

Zur Info, ich habe eine THashStringList, in der ich die Daten INI äquvivalent bereitstelle. Eine Funktion, der ich die Liste und einen String übergebe, soll nun durch Start- und Endkennung die Bezeichner herausfiltern und durch das entsprechende Value ersetzen. Ich habe einige, wenn auch nur im Detail differenzierende Lösungswege eingeschlagen, da ich aber um jede Millisekunde feile (Minimaxing), hoffe ihr könnt meine Proceduren noch optimieren. Ich kopier einfach mal den Unit-
auszug der relevant ist.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:

{ **************************************************************************** }
{ VARIANT A1                                                                   }
{                                                                              }
{ Unter Verwendung der Delphi Pos Funktionen                                   }
{ 7444|7481|7591|7481 (ms) mit TStringlist                                     }
{ Mit THashStringList merklich schneller (ca. 3000)                            }
{                                                                              }
{ **************************************************************************** }

Procedure StrConstructorA1( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Value : string;
 Procedure SetPos;
  begin
   p1 := Pos(SEPERATOR,str);
   p2 := Pos(SEPERATOR,PChar(@str[p1+LenSeperator]))+p1+LenSeperator-1;
 end;
 begin
  SetPos;
  while p1 <> 0 do begin
   Value := IniList.Values[Copy(str,p1+LenSeperator,p2-p1-LenSeperator)];
   Delete(str,p1,p2-p1+2);
   Insert(Value,str,p1);
   SetPos;
  end;
end;


{ **************************************************************************** }
{ VARIANT A2                                                                   }
{                                                                              }
{ Unter Verwendung der Pos und StringReplace Funktion                          }
{ minimal schneller als A1                                                     }
{ **************************************************************************** }

Procedure StrConstructorA2( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Bez   : string;
 Procedure SetPos;
  begin
   p1 := Pos(SEPERATOR,str);
   p2 := Pos(SEPERATOR,PChar(@str[p1+LenSeperator]))+p1+LenSeperator-1;
 end;
 begin
  SetPos;
  while p1 <> 0 do begin
   Bez := Copy(str,p1+LenSeperator,p2-p1-LenSeperator);
   str := StringReplace(str,SEPERATOR+Bez+SEPERATOR,IniList.Values[Bez],[]);
   SetPos;
  end;
end;


{ END ************************************************************* VARIANTS A }


{ **************************************************************************** }
{ VARIANT B1                                                                   }
{                                                                              }
{ Ohne Verwendung der Pos Funktion                                             }
{ 7371|7330|7341|7331 (ms) mit TStringlist                                     }
{ Mit THashStringList merklich schneller (ca 3000)                             }
{ schneller als A Varianten                                                    }
{ **************************************************************************** }

Procedure StrConstructorB1( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Value : string;
 begin
  p1:=1;
  repeat
   while str[p1]+str[p1+1] <> SEPERATOR do if p1 < length(str) then inc(p1) else begin p1 := 0; break; end;
   if p1 <> 0 then begin
    p2:=p1+2;
    while str[p2]{+str[p2+1]} <> SEPERATOR[1] do if p2 < length(str) then inc(p2) else break;
    Value := IniList.Values[Copy(str,p1+LenSeperator,p2-p1-LenSeperator)];
    Delete(str,p1,p2-p1+LenSeperator);
    Insert(Value,str,p1);
   end;
  until p1 = 0;
end;


{ **************************************************************************** }
{ VARIANT B2                                                                   }
{                                                                              }
{ Unter Verwendung der StringReplace Funktion                                  }
{ minimal schneller als B1                                                     }
{ **************************************************************************** }

Procedure StrConstructorB2( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Bez   : string;
 begin
  p1:=1;
  repeat
   while str[p1]+str[p1+1] <> SEPERATOR do if p1 < length(str) then inc(p1) else begin p1 := 0; break; end;
   if p1 <> 0 then begin
    p2:=p1+2;
    while str[p2]{+str[p2+1]} <> SEPERATOR[1] do if p2 < length(str) then inc(p2) else break;
    Bez := Copy(str,p1+LenSeperator,p2-p1-LenSeperator);
    str := StringReplace(str,SEPERATOR+Bez+SEPERATOR,IniList.Values[Bez],[]);
   end;
  until p1 = 0;
end; 


{ **************************************************************************** }
{ VARIANT B3                                                                   }
{                                                                              }
{ Unter Verwendung der AnsiReplaceText Funktion                                }
{ minimal schneller als B2                                                     }
{ **************************************************************************** }

Procedure StrConstructorB3( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Bez   : string;
 begin
  p1:=1;
  repeat
   while str[p1]+str[p1+1] <> SEPERATOR do if p1 < length(str) then inc(p1) else begin p1 := 0; break; end;
   if p1 <> 0 then begin
    p2:=p1+2;
    while str[p2]{+str[p2+1]} <> SEPERATOR[1] do if p2 < length(str) then inc(p2) else break;
    Bez := Copy(str,p1+LenSeperator,p2-p1-LenSeperator);
    str := AnsiReplaceText(str,SEPERATOR+Bez+SEPERATOR,IniList.Values[Bez]);
   end;
  until p1 = 0;
end;


{ **************************************************************************** }
{ VARIANT B4                                                                   }
{                                                                              }
{ Unter Verwendung der AnsiReplaceStr Funktion                                 }
{ mal langsamer, mal schneller als B3                                          }
{ **************************************************************************** }

Procedure StrConstructorB4( var Str: String; IniList: TStringList);
 Const SEPERATOR = '##';
       LenSeperator = length(SEPERATOR);
 var   p1,p2 : dword;
       Bez   : string;
 begin
  p1:=1;
  repeat
   while str[p1]+str[p1+1] <> SEPERATOR do if p1 < length(str) then inc(p1) else begin p1 := 0; break; end;
   if p1 <> 0 then begin
    p2:=p1+2;
    while str[p2]{+str[p2+1]} <> SEPERATOR[1] do if p2 < length(str) then inc(p2) else break;
    Bez := Copy(str,p1+LenSeperator,p2-p1-LenSeperator);
    str := AnsiReplaceStr(str,SEPERATOR+Bez+SEPERATOR,IniList.Values[Bez]);
   end;
  until p1 = 0;
end;

{ END ************************************************************* VARIANTS B }

{ Test - Operationsausführung }

procedure TForm1.Button1Click(Sender: TObject);
 var sl:THashedStringList;
     I:dword;
     s: string;
     tick,tack : dword;
 begin
  sl := THashedStringList.Create;
  try
   // Testliste füllen
   for i:=1 to 1000000 do sl.Add('Name'+inttostr(i)+'='+'Wert'+inttostr(i));
   // aufgeblasener String / Testvariante 
   s := stringofchar('o',10)+'..##Name1007##..'+
        stringofchar('o',10)+'..##Name951341##..'+
        stringofchar('o',10)+'..##Name341##..'+
        stringofchar('o',10)+'..##Name9511##..'+
        stringofchar('o',10)+'..##Name1341##..'+
        stringofchar('o',10)+'..##Name91341##..'+
        stringofchar('o',10)+'..##Name2041##..'+
        stringofchar('o',10)+'..##Name321001##..'+
        stringofchar('o',10)+'..##Name777879##..'+
        stringofchar('o',10)+'..##Name1111##..';

   tick := gettickcount; // Startzeitpunkt

   StrConstructorB4(s,sl); // String-Constructor

   tack := gettickcount; // Endzeitpunkt

   showmessage(s);
   showmessage(inttostr(tack-tick));
  finally
   sl.free;
  end;
end;

{ **************************************************************************** }
{ letzte statistische Zeiterfassung: (Zeiteinheit ms)                          }
{       hintereinander (btn-press) | nach Deaktivierung Autorun AntiVirus      }
{ FKT | ---------------------------------------------------------------------- }
{ A1  | 5238 -> 4807 -> 4787       | 4857                                      }
{ A2  | 4857 -> 4797 -> 4786       | 4796                                      }
{ B1  | 4907 -> 4807 -> 4627       | 4626                                      }
{ B2  | 4947 -> 4987 -> 4747       | 4616                                      }
{ B3  | 4867 -> 4727 -> 4527       | 4627                                      }
{ B4  | 5177 -> 4637 -> 4557       | 4476                                      }
{ **************************************************************************** }

end.

Anzumerken sei noch das die Anwendung im Debugger lief und dass das System (CPU 600Mhz,256 RAM) wohl nicht mehr zum schnellsten gehört.

_________________
mfg
Tana´Ri

jasocul · Verfasst: Di 31.08.04 16:57

Sieht eigentlich schon ganz gut aus, was Du da machst.
Was Du unbedingt machen solltest sit eine genaue Analyse, wie die Daten in der Realität aussenhen werden. Deine letzte Prozedur ist nur deshalb die schnellste, weil sehr viele Separatoren in den Strings sind. Wenn nur sehr wenige enthalten sind, dürfte eine Routine mit der Pos-Funktion schneller sein.

mfg,
Jasocul

.Chef · Beiträge: 1112

Enormen Gewinn bringt die Festlegung der Länge pro Eintrag. Wenn z.B. alle Einträge zwischen 7 und 10 Byte lang sind, ist es vertretbar auf Kosten des Platzes für jeden Eintrag 10 Byte zu reservieren. Dann nimm anstatt der Liste ein Array und arbeite mit Move.

_________________
Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme