¿Hay una rutina GetToken rápido para Delphi?
https://stackoverflow.com/questions/1694001
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En mi programa, procesar millones de cadenas que tienen un carácter especial, por ejemplo, "|" para separar las fichas dentro de cada cadena. Tengo una función para devolver el testigo enésimo, y esto es que:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
I, P, P2: integer;
begin
P2 := Pos(Delim, Line);
if TokenNum = 1 then begin
if P2 = 0 then
Result := Line
else
Result := copy(Line, 1, P2-1);
end
else begin
P := 0; { To prevent warnings }
for I := 2 to TokenNum do begin
P := P2;
if P = 0 then break;
P2 := PosEx(Delim, Line, P+1);
end;
if P = 0 then
Result := ''
else if P2 = 0 then
Result := copy(Line, P+1, MaxInt)
else
Result := copy(Line, P+1, P2-P-1);
end;
end; { GetTok }
he desarrollado esta función cuando estaba usando Delphi 4. Se llama a la rutina PosEx muy eficiente que fue desarrollado originalmente por Fastcode y ahora se incluye en la biblioteca StrUtils de Delphi.
Recientemente he actualizado a Delphi 2009 y mis cadenas son todos Unicode. Esta función GetTok todavía funciona y todavía funciona bien.
He pasado por las nuevas bibliotecas en Delphi 2009 y hay muchas nuevas funciones y adiciones a la misma.
Pero no he visto una función GetToken como que necesito en cualquiera de las nuevas bibliotecas de Delphi, en los diversos proyectos fastcode, y no puedo encontrar nada con una búsqueda en Google que no sea de Zarko Gajic:. Funciones Delphi de Split / Tokenizer , que no es tan optimizado como lo que ya tengo
Cualquier mejora, incluso el 10% sería notable en mi programa. Sé que es una alternativa stringlists y para mantener siempre las fichas separadas, pero esto tiene una gran memoria en cuanto a los gastos generales y no estoy seguro si lo hiciera todo el trabajo para convertir si sería más rápido.
Uf. Así que después de todo este discurso largo aliento, mi pregunta realmente es:
¿Sabe de cualquier implementación muy rápida de una rutina GetToken? Una versión optimizada ensamblador sería ideal?
Si no es así, ¿hay optimizaciones que se pueden ver a mi código de seguridad que podría hacer una mejora?
Seguimiento: Barry Kelly mencionó una pregunta que hice hace un año acerca de cómo optimizar el análisis de las líneas en un archivo. En ese momento ni siquiera había pensado en mi rutina GetTok que no fue utilizado para el que lee o análisis. Es sólo ahora que vi la cabeza de mi rutina GetTok que me llevó a hacer esta pregunta. Hasta Carl Smotricz y respuestas de Barry, nunca había pensado en la conexión de los dos. Tan obvio, pero simplemente no se registró. Gracias por señalarlo.
Sí, mi Delim es un solo carácter, por lo que, obviamente, tengo una optimización importante que puedo hacer. Mi uso de POS y PosEx en la rutina GetTok (arriba) me cegó a la idea de que puedo hacerlo más rápido con un carácter por carácter en lugar de búsqueda, con trozos de código como:
while (cp^ > #0) and (cp^ <= Delim) do
Inc(cp);
Voy a ir a través de las respuestas de todos y tratar las diversas sugerencias y compararlas. A continuación, voy a publicar los resultados.
Confusión:. Bien, ahora estoy realmente perplejo
Tomé recomendación de Carl y Barry para ir con PChars, y aquí es mi aplicación:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
Sobre el papel, no creo que se puede hacer mucho mejor que esto.
Así que puse ambas rutinas para la tarea y solía AQTime para ver lo que está pasando. La carrera me había incluido 1,108,514 llamadas a GetTok.
AQTime timed la rutina original a 0,40 segundos. El millón de llamadas a Pos tomó 0.10 segundos. Un medio millón de copias de los TokenNum = 1 tomó 0.10 segundos. El PosEx 600.000 llamadas sólo tomó 0.03 segundos.
A continuación, Cronometré mi nueva rutina con AQTime para la misma carrera y exactamente las mismas llamadas. AQTime informa que mi nueva rutina "rápida" tomó 3.65 segundos, que es 9 veces más largo. El culpable de acuerdo con AQTime fue el primer bucle:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
La línea de tiempo, que fue ejecutado 18 millones de veces, se informó en 2,66 segundos. La línea inc, ejecutado 16 millones de veces, que se dijo para tomar 0.47 segundos.
Ahora yo creía que sabía lo que estaba pasando aquí. He tenido un problema similar con AQTime en una pregunta que hice el año pasado: ¿Por qué es CharInSet más rápido que instrucción Case?
De nuevo fue Barry Kelly que me dio un indicio. Básicamente, un perfilador instrumentar como AQTime does no necesariamente hacer el trabajo para microoptimization. Se añade una sobrecarga a cada línea que puede inundar los resultados que se muestra claramente en estos números. Los 34 millones de líneas ejecutadas en mi nuevo "código optimizado" abrumar a los varios millones de líneas de mi código original, aparentemente con poca o ninguna sobrecarga de las rutinas de punto de venta y PosEx.
Barry me dio una muestra de código usando QueryPerformanceCounter para comprobar que estaba en lo cierto, y en ese caso era él.
Bueno, por lo que vamos a hacer lo mismo ahora con QueryPerformanceCounter para demostrar que mi nueva rutina es más rápido y no 9 veces más lento como dice AQTime que es. Así que aquí voy:
function TimeIt(const Title: string): double;
var i: Integer;
start, finish, freq: Int64;
Seconds: double;
begin
QueryPerformanceCounter(start);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 1);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 2);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 3);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 4);
QueryPerformanceCounter(finish);
QueryPerformanceFrequency(freq);
Seconds := (finish - start) / freq;
Result := Seconds;
end;
Así que esto pondrá a prueba 1.000.000 llamadas a GetTok.
Mi antiguo procedimiento con las llamadas de punto de venta y PosEx tomó 0.29 segundos. El nuevo con PChars tomó 2,07 segundos.
Ahora estoy completamente confundido! ¿Puede alguien decirme por qué el procedimiento PChar no sólo es más lento, pero es de 8 a 9 veces más lento!?
El misterio resuelto! Andreas dijo en su respuesta a cambiar el parámetro Delim de una cadena a un Char. Siempre va a utilizar sólo una Char, por lo que al menos para mi aplicación esto es muy posible. Me quedé sorprendido por lo sucedido.
El tiempo de 1 millón de llamadas se redujo de 1,88 segundos a .22 segundos.
Y, sorprendentemente, el tiempo de mi rutina original Pos / PosEx subió de 0,29 a 0,44 segundos cuando he cambiado es el parámetro Delim a un Char.
Francamente, estoy decepcionado por el optimizador de Delphi. Delim que es un parámetro constante. El optimizador debería haber dado cuenta de que la misma conversión está sucediendo dentro del bucle y debería haber movido hacia fuera de modo que sólo se realiza una vez.
Doble comprobar mis parámetros de generación de código, sí lo tengo Optimización formato True y Cadena inspección de ésta fuera.
El fondo es que la nueva rutina PChar con solución de Andrea es aproximadamente un 25% más rápido que mi original (0,22 frente a 0,29).
Todavía quiero hacer un seguimiento de los otros comentarios aquí y ponerlas a prueba.
Desactivación de optimización y encender el formato de cadena chequeando solo aumenta el tiempo de 0,22-0,30. Se añade aproximadamente la misma que la original.
La ventaja de utilizar el código ensamblador, o llamar a rutinas escritas en ensamblador, como POS, o PosEx es que no están sujetos a lo que las opciones de generación de código que haya establecido. Ellos siempre van a funcionar de la misma manera, una forma de pre-optimizado y no hinchado.
He reafirmado en el último par de días, que la mejor manera de comparar código para microoptimization es mirar y comparar el código ensamblador en la ventana de la CPU. Sería bueno si Embarcadero podría hacer que la ventana un poco más conveniente, y nos permitirá copiar partes en el portapapeles o imprimir secciones de la misma.
Además, me injustamente estrelló AQTime al principio de este post, pensando que el tiempo extra añadido para mi nueva rutina era únicamente debido a la instrumentación, agregó. Ahora que vuelvo y comprobar con el parámetro Char en lugar de String, el bucle while se ha reducido a .30 segundos (de 2,66) y la línea inc está abajo a .14 segundos (de 0,47). Es extraño que la línea inc iría hacia abajo también. Pero estoy cansado de toda esta prueba ya.
Tomé la idea de Carl de bucle por los personajes, y volvió a escribir ese código con esa idea. Se hace otra mejora, a .19 segundos de 0.22. Así que aquí es ahora el mejor hasta ahora:
function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I, CurToken: Integer;
PLine, PStart: PChar;
begin
CurToken := 1;
PLine := PChar(Line);
PStart := PLine;
for I := 1 to length(Line) do begin
if PLine^ = Delim then begin
if CurToken = TokenNum then
break
else begin
CurToken := CurToken + 1;
inc(PLine);
PStart := PLine;
end;
end
else
inc(PLine);
end;
if CurToken = TokenNum then
SetString(Result, PStart, PLine - PStart)
else
Result := '';
end;
Todavía puede haber algunas optimizaciones menores a este, tales como la comparación CurToken = Tokennum, que debe ser del mismo tipo, número entero o Byte, el que sea más rápido.
Pero digamos, estoy feliz ahora.
Gracias de nuevo a la comunidad StackOverflow Delphi.
Solución
Su nueva función (el que tiene PChar) debe declarar "Delim", como Char y no como Cadena . En su implementación actual el compilador tiene que convertir el POL ^ carbón en una cadena de compararlo con "Delim". Y eso ocurre en un bucle estrecho que resulta un enorme impacto en el rendimiento.
function GetTok(const Line: string; const Delim: Char{<<==}; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; http://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
Otros consejos
Se hace una gran diferencia lo que se espera "Delim" a ser. Si se espera que sea un solo carácter, eres mucho mejor paso a paso a través de la cadena de caracteres por carácter, idealmente a través de un PChar, y prueba específica.
Si se trata de una cadena larga, Boyer-Moore y búsquedas similares tienen una fase de puesta a punto para las tablas de salto, y la mejor manera sería construir las tablas una vez y reutilizarlos para cada hallazgo posterior. Esto significa que necesita el estado de una llamada, y esta función sería mejor como un método en un objeto en su lugar.
Se le pueden interesar esta respuesta que he dado a una pregunta algún tiempo antes, acerca de la manera más rápida para analizar una línea en Delphi. (Pero veo que usted es que hizo la pregunta! Sin embargo, en la solución de su problema, lo haría ceñirse a la forma en que he descrito el análisis, no utilizando PosEx como que está utilizando, dependiendo de lo que normalmente se ve como Delim.)
Actualizar : OK, pasé unos 40 minutos mirando esto. Si conoce el delimitador va a ser un personaje, usted es casi siempre mejor con la segunda versión (es decir PChar exploración), pero hay que pasar Delim como personaje. En el momento de la escritura, que está convirtiendo la expresión PLine^ - de tipo char - a una cadena de comparación con Delim. Eso será muy lento; incluso la indexación en la cadena, con Delim[1] también será algo más lento.
Sin embargo, dependiendo del tamaño de sus líneas son, y cuantas delimitado desea retirarse, puede ser mejor con un enfoque resumable, en lugar de saltarse piezas delimitados no deseados dentro de la rutina de tokenizing. Si llama GetTok con sucesivamente crecientes índices, como se está haciendo actualmente en su mini punto de referencia, que va a terminar con O (n * n) el rendimiento, donde n es el número de secciones delimitadas. Que se puede convertir en O (n) si se guarda el estado de la exploración y restaurarlo para la siguiente iteración, o el paquete de todos los elementos extraídos en una matriz.
Aquí hay una versión que hace todo tokenización una vez, y devuelve una matriz. Tiene que tokenize dos veces, sin embargo, con el fin de saber qué tan grande para hacer la matriz. Por otro lado, sólo el segundo tokenización necesita para extraer las cadenas:
// Do all tokenization up front.
function GetTok4(const Line: string; const Delim: Char): TArray<string>;
var
cp, start: PChar;
count: Integer;
begin
// Count sections
count := 1;
cp := PChar(Line);
start := cp;
while True do
begin
if cp^ <> #0 then
begin
if cp^ <> Delim then
Inc(cp)
else
begin
Inc(cp);
Inc(count);
end;
end
else
begin
Inc(count);
Break;
end;
end;
SetLength(Result, count);
cp := start;
count := 0;
while True do
begin
if cp^ <> #0 then
begin
if cp^ <> Delim then
Inc(cp)
else
begin
SetString(Result[count], start, cp - start);
Inc(cp);
Inc(count);
end;
end
else
begin
SetString(Result[count], start, cp - start);
Break;
end;
end;
end;
Aquí está el enfoque resumable. Las cargas y los almacenes de la posición y el delimitador de carácter actual tienen un costo, sin embargo:
type
TTokenizer = record
private
FSource: string;
FCurrPos: PChar;
FDelim: Char;
public
procedure Reset(const ASource: string; ADelim: Char); inline;
function GetToken(out AResult: string): Boolean; inline;
end;
procedure TTokenizer.Reset(const ASource: string; ADelim: Char);
begin
FSource := ASource; // keep reference alive
FCurrPos := PChar(FSource);
FDelim := ADelim;
end;
function TTokenizer.GetToken(out AResult: string): Boolean;
var
cp, start: PChar;
delim: Char;
begin
// copy members to locals for better optimization
cp := FCurrPos;
delim := FDelim;
if cp^ = #0 then
begin
AResult := '';
Exit(False);
end;
start := cp;
while (cp^ <> #0) and (cp^ <> Delim) do
Inc(cp);
SetString(AResult, start, cp - start);
if cp^ = Delim then
Inc(cp);
FCurrPos := cp;
Result := True;
end;
Aquí está el programa completo que he usado para la evaluación comparativa.
Estos son los resultados:
*** count=3, Length(src)=200
GetTok1: 595 ms
GetTok2: 547 ms
GetTok3: 2366 ms
GetTok4: 407 ms
GetTokBK: 226 ms
*** count=6, Length(src)=350
GetTok1: 1587 ms
GetTok2: 1502 ms
GetTok3: 6890 ms
GetTok4: 679 ms
GetTokBK: 334 ms
*** count=9, Length(src)=500
GetTok1: 3055 ms
GetTok2: 2912 ms
GetTok3: 13766 ms
GetTok4: 947 ms
GetTokBK: 446 ms
*** count=12, Length(src)=650
GetTok1: 4997 ms
GetTok2: 4803 ms
GetTok3: 23021 ms
GetTok4: 1213 ms
GetTokBK: 543 ms
*** count=15, Length(src)=800
GetTok1: 7417 ms
GetTok2: 7173 ms
GetTok3: 34644 ms
GetTok4: 1480 ms
GetTokBK: 653 ms
En función de las características de sus datos, si el delimitador es probable que sea un personaje o no, y cómo se trabaja con él, diferentes enfoques pueden ser más rápido.
(he cometido un error en mi programa antes, no estaba midiendo las mismas operaciones para cada estilo de rutina. He actualizado el enlace de Pastebin y resultados de referencia.)
Delphi compila a código muy eficiente; en mi experiencia, que era muy difícil hacerlo mejor en ensamblador.
Creo que sólo debe apuntar un PChar (todavía existen, ¿no me separó de Delphi alrededor de 4,0?) Al principio de la cadena y se incrementará mientras cuenta "|" s, hasta que haya encontrado n-1 de ellos. Sospecho que habrá más rápido que llamar PosEx repetidamente.
Tome nota de esa posición, incremente el puntero un poco más hasta que se pulsa el tubo siguiente. Saque su subcadena. Hecho.
Sólo estoy adivinando, pero no me sorprendería si esto estaba cerca de los más rápidos este problema puede ser resuelto.
EDIT: Esto es lo que tenía en mente. Este código es, por desgracia, no compilado y no probado, pero debe demostrar lo que quería decir.
En particular, Delim se trata como un solo carbón, que creo que hace un mundo de diferencia si eso va a cumplir con los requisitos, y el carácter en POL se prueba una sola vez. Por último, no hay más comparación frente TokenNum; Creo que es más rápido para disminuir un contador a 0 para contar delimitadores.
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
var
Del: Char;
PLine, PStart: PChar;
Nth, I, P0, P9: Integer;
begin
Del := Delim[1];
Nth := TokenNum + 1;
P0 := 1;
P9 := Line.length + 1;
PLine := PChar(line);
for I := 1 to P9 do begin
if PLine^ = Del then begin
if Nth = 0 then begin
P9 := I;
break;
end;
Dec(Nth);
if Nth = 0 then P0 := I + 1
end;
Inc(PLine);
end;
if (Nth <= 1) or (TokenNum = 1) then
Result := Copy(Line, P0, P9 - P0);
else
Result := ''
end;
Uso de ensamblador sería un micro-optimización. Hay mucho mayores ganancias que se tenía al optimizar el algoritmo. No hacer ritmos de trabajo que hace el trabajo de la manera más rápida posible, cada vez.
Un ejemplo sería si usted tiene lugares en su programa donde se necesita varias muestras de la misma línea. Otro procedimiento que devuelve un conjunto de fichas que luego se puede indexar en debe ser más rápido que llamar a su función más de una vez, sobre todo si se deja que el procedimiento no devuelve todas las fichas, pero sólo tanto como usted necesita.
Pero en general estoy de acuerdo con la respuesta de Carl (1), utilizando un PChar para la exploración, probablemente sería más rápido que el código actual.
Esta es una función que he tenido en mi biblioteca personal desde hace bastante tiempo que utilizo ampliamente. Creo que esta es la versión más actual de la misma. He tenido varias versiones en el pasado se han optimizado para una variedad de razones diferentes. Éste intenta tener en cuenta las cadenas entre comillas, pero si se elimina ese código que hace la función de un ligero poco más rápido.
De hecho, tengo una serie de otras rutinas, CountSections y ParseSectionPOS son un par de ejemplos.
Unfortuately esta rutina es ANSI / pchar basado solamente. Aunque no creo que sería difícil para moverlo a Unicode. Tal vez ya he hecho eso ... Voy a tener que comprobar eso.
Nota:. Esta rutina se basa en el 1 de indexación ParseNum
function ParseSection(ParseLine: string; ParseNum: Integer; ParseSep: Char; QuotedStrChar:char = #0) : string;
var
wStart, wEnd : integer;
wIndex : integer;
wLen : integer;
wQuotedString : boolean;
begin
result := '';
wQuotedString := false;
if not (ParseLine = '') then
begin
wIndex := 1;
wStart := 1;
wEnd := 1;
wLen := Length(ParseLine);
while wEnd <= wLen do
begin
if (QuotedStrChar <> #0) and (ParseLine[wEnd] = QuotedStrChar) then
wQuotedString := not wQuotedString;
if not wQuotedString and (ParseLine[wEnd] = ParseSep) then
begin
if wIndex=ParseNum then
break
else
begin
inc(wIndex);
wStart := wEnd+1;
end;
end;
inc(wEnd);
end;
result := copy(ParseLine, wStart, wEnd-wStart);
if (length(result) > 0) and (QuotedStrChar <> #0) and (result[1] = QuotedStrChar) then
result := AnsiDequotedStr(result, QuotedStrChar);
end;
end; { ParseSection }
En su código, creo que esta es la única línea que puede ser optimizado:
Result := copy(Line, P+1, MaxInt)
Si se calcula la longitud del nuevo allí, que podría ser un poco más rápido, pero no el 10% que busca.
Su algoritmo tokenizing parece bastante bien. Para la optimización, lo haría ejecutar a través de un generador de perfiles (como AQTime de AutomatedQA) con una subconjunto representativo de los datos de producción. Eso le apunte al punto más débil.
La única función RTL que se acerca es éste en la unidad de clases:
procedure TStrings.SetDelimitedText(const Value: string);
tokenizes, pero utiliza tanto QuoteChar y Delimitador , pero sólo utiliza un delimitador.
Se utiliza el SetString función en la unidad del sistema, que es una manera bastante rápido para ajustar el contenido de una cadena basada en un PChar / PAnsiChar / PUnicodeChar y una longitud.
Eso podría conseguir que una cierta mejora, así; por el contrario, Copiar es muy rápido también.
No estoy culpando a la persona siempre el algoritmo, pero si miro la primera pieza de la fuente, el problema es que para la cadena de N, haces los POS / posexes de cadena 1..n-1 de nuevo también.
Esto significa para los N elementos, que haces suma (n, n-1, n-2 ... 1) plantea (= + / - 0,5 * N ^ 2)., Mientras que se necesitarán sólo n
Si simplemente almacenar en caché la posición del último de los resultados encontrados, por ejemplo, en un registro que se pasa por el parámetro VAR, se puede ganar mucho.
tipo
TLastPosition = registro
elementnr: número entero; // última tokennumber
elementpos: número entero; // índice de caracteres del último partido
fin;
y luego algo
si tokennum = (lastposition.elementnr + 1), entonces empezar NewPos: = posex (DELIM, línea, lastposition.elementpos); final;
Por desgracia, no tengo el tiempo para escribirlo, pero espero que la idea
