Existe uma rotina rápida para Delphi?
https://stackoverflow.com/questions/1694001
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
No meu programa, processo milhões de cordas que têm um personagem especial, por exemplo, "|" para separar os tokens dentro de cada string. Eu tenho uma função de devolver o nó de token, e é isso:
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 }
Desenvolvi essa função quando estava usando o Delphi 4. Ele chama de rotina Posex muito eficiente que foi originalmente desenvolvida pelo FastCode e agora está incluída na Biblioteca Strutils de Delphi.
Recentemente, atualizei para Delphi 2009 e minhas cordas são todas unicode. Essa função GetTok ainda funciona e ainda funciona bem.
Passei pelas novas bibliotecas em Delphi 2009 e há muitas novas funções e acréscimos.
Mas eu não vi uma função GetToken, como eu preciso em nenhuma das novas bibliotecas Delphi, nos vários projetos do FastCode, e não consigo encontrar nada com uma pesquisa no Google, exceto Funções de Zarko Gajic: Delphi Split / Tokenizer, que não é tão otimizado quanto o que eu já tenho.
Qualquer melhoria, mesmo 10% seria perceptível no meu programa. Eu sei que uma alternativa são listas de strings e sempre mantêm os tokens separados, mas isso tem uma grande memória no alto e não tenho certeza se fiz todo esse trabalho para converter se seria mais rápido.
Ufa. Então, depois de toda essa conversa longa, minha pergunta realmente é:
Você conhece alguma implementação muito rápida de uma rotina GetToken? Uma versão otimizada do assembler seria ideal?
Caso contrário, existem otimizações que você pode ver no meu código acima que pode melhorar?
Acompanhamento: Barry Kelly mencionou uma pergunta que fiz um ano atrás sobre otimizar a análise das linhas em um arquivo. Naquela época, eu nem tinha pensado na minha rotina GetTok, que não era usada para a leitura ou análise. É só agora que vi a sobrecarga da minha rotina GetTok, que me levou a fazer essa pergunta. Até as respostas de Carl Smotricz e Barry, eu nunca pensei em conectar os dois. Tão óbvio, mas simplesmente não se registrou. Obrigado por apontar isso.
Sim, meu delim é um único personagem, então, obviamente, tenho uma grande otimização que posso fazer. Meu uso de POS e Posex na rotina GetTok (acima) me cegou para a ideia de que posso fazê -lo mais rápido com um personagem por pesquisa de personagens, com pedaços de código como:
while (cp^ > #0) and (cp^ <= Delim) do
Inc(cp);
Vou passar pelas respostas de todos, tentar as várias sugestões e compará -las. Então eu postarei os resultados.
Confusão: Ok, agora estou realmente perplexo.
Peguei a recomendação de Carl e Barry para ir com PCHAs, e aqui está minha implementação:
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 }
No papel, acho que você não pode fazer muito melhor do que isso.
Então, coloquei as duas rotinas na tarefa e usei o Aqtime para ver o que está acontecendo. A corrida que eu incluí 1.108.514 ligações para o GetTok.
O AQTIME cronometrou a rotina original em 0,40 segundos. Os milhões de chamadas para POS levaram 0,10 segundos. Meio milhão de tokennum = 1 cópias levou 0,10 segundos. As 600.000 chamadas Posex levaram apenas 0,03 segundos.
Então eu cronometei minha nova rotina com o AQTIME para a mesma execução e exatamente as mesmas chamadas. O AQTime relata que minha nova rotina "rápida" levou 3,65 segundos, o que é 9 vezes mais. O culpado de acordo com o Aqtime foi o primeiro loop:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
A linha enquanto foi executada 18 milhões de vezes, foi relatada em 2,66 segundos. Dizia -se que a linha INC, executada 16 milhões de vezes, levou 0,47 segundos.
Agora eu pensei que sabia o que estava acontecendo aqui. Eu tive um problema semelhante com o Aqtime em uma pergunta que fiz no ano passado: Por que Charinset é mais rápido que a declaração de caso?
Novamente, foi Barry Kelly quem me considerou. Ele adiciona uma sobrecarga a cada linha que pode inundar os resultados que são mostrados claramente nesses números. As 34 milhões de linhas executadas em meu novo "código otimizado" sobrecarregam os vários milhões de linhas do meu código original, com aparentemente pouca ou nenhuma sobrecarga das rotinas de PDV e Posex.
Barry me deu uma amostra de código usando o QueryPerformAncounter para verificar se ele estava correto e, nesse caso, ele estava.
Ok, então vamos fazer o mesmo agora com o QueryPerformanCous para provar que minha nova rotina é mais rápida e não 9 vezes mais lenta, como o Aqtime diz que é. Então aqui vou eu:
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;
Portanto, isso testará 1.000.000 de chamadas para o GetTok.
Meu procedimento antigo com as chamadas POS e Posex levou 0,29 segundos. O novo com PChars levou 2,07 segundos.
Agora estou completamente confuso! Alguém pode me dizer por que o procedimento PCHA não é apenas mais lento, mas é 8 a 9 vezes mais lento!?
Mistério resolvido! Andreas disse em sua resposta para alterar o parâmetro Delim de uma string para um char. Sempre usarei apenas um char, então, pelo menos para minha implementação, isso é muito possível. Fiquei impressionado com o que aconteceu.
O tempo para os 1 milhão de ligações caiu de 1,88 segundos para 0,22 segundos.
E, surpreendentemente, o tempo para minha rotina original de POS/Posex subiu de 0,29 para 0,44 segundos, quando eu mudei seu parâmetro delim para um char.
Francamente, estou decepcionado com o otimizador de Delphi. Esse delim é um parâmetro constante. O otimizador deveria ter notado que a mesma conversão está acontecendo dentro do loop e deveria tê -lo movido para que seja feito apenas uma vez.
Verificando duas parâmetros de geração de código, sim, eu tenho otimização true e o formato de string verificando.
A linha inferior é que a nova rotina PCHA com a correção de Andrea é cerca de 25% mais rápida que a minha (.22 versus 0,29).
Ainda quero acompanhar os outros comentários aqui e testá -los.
Desligar a otimização e ligar o formato da string A verificação apenas aumenta o tempo de 0,22 para 0,30. Adiciona quase o mesmo ao original.
A vantagem de usar o código do Assembler ou rotinas de chamadas escritas no assembler como POS ou Posex é que elas não estão sujeitas a quais opções de geração de código você definiu. Eles sempre serão executados da mesma maneira, uma maneira pré-otimizada e não inchada.
Reafirmei nos últimos dias, que a melhor maneira de comparar o código para microoptimização é examinar e comparar o código do assembler na janela da CPU. Seria bom se Embarcadero pudesse tornar essa janela um pouco mais conveniente e nos permitir copiar partes para a área de transferência ou imprimir seções dela.
Além disso, bati injustamente no AQTIEL no início deste post, pensando que o tempo extra adicionado para minha nova rotina foi apenas por causa da instrumentação que ela acrescentou. Agora que volto e verifico com o parâmetro CHAR em vez da string, o loop while está abaixo de 0,30 segundos (de 2,66) e a linha Inc caiu para 0,14 segundos (de 0,47). Estranho que a linha INC também caia. Mas já estou sendo desgastado de todos esses testes.
Eu tomei a idéia de Carl de loop por personagens e reescrevi esse código com essa ideia. Faz outra melhoria, até 0,19 segundos a partir de 0,22. Então aqui está agora o melhor até agora:
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;
Ainda pode haver algumas pequenas otimizações para isso, como a comparação de Curtoken = Tokennum, que deve ser o mesmo tipo, número inteiro ou byte, o que for mais rápido.
Mas digamos, estou feliz agora.
Mais uma vez obrigado à comunidade Stackoverflow Delphi.
Solução
Sua nova função (aquela com PChar) deve declarar "delim" como Caracteres e não como Corda. Na sua implementação atual, o compilador deve converter a placa em uma string para compará -la com "Delim". E isso acontece em um loop apertado resultante, é um enorme sucesso de desempenho.
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 }
Outras dicas
Faz uma grande diferença o que "Delim" deve ser. Se é esperado que seja um único caractere, você é muito melhor pisar no caractere da string por caractere, idealmente através de um PChar, e testando especificamente.
Se for uma corda longa, Boyer-Moore e pesquisas semelhantes têm uma fase de configuração para tabelas de salto, e a melhor maneira seria construir as tabelas uma vez e reutilizá-las para cada achado subsequente. Isso significa que você precisa declarar entre chamadas, e essa função seria melhor como um método em um objeto.
Você pode estar interessado em Esta resposta que dei a uma pergunta algum tempo antes, sobre a maneira mais rápida de analisar uma linha em Delphi. (Mas vejo que é você quem fez a pergunta! No entanto, ao resolver seu problema, eu iria para como descrevi a análise, não Usando Posex como você está usando, dependendo do que o delim normalmente se parece.)
ATUALIZAR: Ok, passei cerca de 40 minutos olhando para isso. Se você sabe que o delimitador será um personagem, você está sempre melhor com a segunda versão (ou seja, digitalização), mas você precisa passar Delim como um personagem. No momento da redação deste artigo, você está convertendo o PLine^ Expressão - do tipo char - a uma string para comparação com o delim. Isso será muito lento; até indexar na string, com Delim[1] também será um pouco lento.
No entanto, dependendo do tamanho de suas linhas e de quantas peças delimitadas você deseja retirar, você pode estar melhor com uma abordagem resumível, em vez de pular peças delimitadas indesejadas dentro da rotina tokenizante. Se você ligar para o GetTok com índices aumentando sucessivamente, como você está fazendo no seu mini -benchmark, você acabará com o desempenho O (n*n), onde n é o número de seções delimitadas. Isso pode ser transformado em O (n) se você salvar o estado da varredura e restaurá -lo para a próxima iteração, ou empacote todos os itens extraídos em uma matriz.
Aqui está uma versão que faz toda a tokenização uma vez e retorna uma matriz. Ele precisa ser tokenizar duas vezes, para saber o quão grande é fazer a matriz. Por outro lado, apenas a segunda tokenização precisa extrair as cordas:
// 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;
Aqui está a abordagem resumível. As cargas e lojas da posição atual e do personagem delimitador têm um custo:
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;
Aqui está o programa completo que usei para o benchmarking.
Aqui estão os 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
Dependendo das características dos seus dados, se o delimitador provavelmente será um personagem ou não e de como você trabalha com ele, diferentes abordagens podem ser mais rápidas.
(Cometi um erro no meu programa anterior, não estava medindo as mesmas operações para cada estilo de rotina. Atualizei o link Pastebin e os resultados de referência.)
Delphi compila com código muito eficiente; Na minha experiência, foi muito difícil fazer melhor no assembler.
Eu acho que você deveria apenas apontar um pchar (eles ainda existem, não é? Eu me separei de Delphi por volta de 4.0) no início da corda e o incrementam enquanto contava "|" s até que você encontre N-1 deles. Eu suspeito que isso será mais rápido do que ligar para Posex repetidamente.
Observe essa posição e aumente o ponteiro um pouco mais até bater no próximo tubo. Retire sua substring. Feito.
Estou apenas adivinhando, mas não ficaria surpreso se isso fosse próximo do mais rápido que esse problema pode ser resolvido.
EDITAR: Aqui está o que eu tinha em mente. Esse código é, infelizmente, não compilado e não testado, mas deve demonstrar o que eu quis dizer.
Em particular, o Delim é tratado como um único char, o que acredito fazer um mundo de diferença se isso cumprir os requisitos, e o personagem da Plina for testado apenas uma vez. Finalmente, não há mais comparação com tokennum; Eu acredito que é mais rápido diminuir um contador para 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;
O uso do assembler seria uma microtimização. Existem ganhos muito maiores a serem obtidos ao otimizar o algoritmo. Não está fazendo batidas de trabalho fazendo o trabalho da maneira mais rápida possível, todas as vezes.
Um exemplo seria se você tivesse lugares em seu programa em que precisará de vários tokens da mesma linha. Outro procedimento que retorna uma matriz de tokens nos quais você pode indexar deve ser mais rápido do que chamar sua função mais de uma vez, especialmente se você deixar o procedimento não retornar todos os tokens, mas apenas o máximo necessário.
Mas em geral eu concordo com a resposta de Carl (+1), usando um PChar para a digitalização provavelmente seria mais rápido que o seu código atual.
Esta é uma função que eu tive na minha biblioteca pessoal há algum tempo que uso extensivamente. Eu acredito que esta é a versão mais atual dele. No passado, tive várias versões sendo otimizadas por vários motivos diferentes. Este tenta levar em consideração strings citados, mas se esse código for removido, torna a função um pouco mais rápida.
Na verdade, tenho várias outras rotinas, as contagens e a parsesecção de alguns exemplos.
Infelizmente, essa rotina é apenas baseada no ANSI/PCHA. Embora eu não ache que seria difícil movê -lo para o Unicode. Talvez eu já tenha feito isso ... vou ter que verificar isso.
Nota: Esta rotina é 1 com base na indexação do parseno.
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 }
No seu código, acho que esta é a única linha que pode ser otimizada:
Result := copy(Line, P+1, MaxInt)
Se você calcular o novo comprimento lá, poderá ficar um pouco mais rápido, mas não os 10% que você está procurando.
Seu algoritmo simbólico parece muito bom. Para otimizá -lo, eu passaria por um perfil (como Aqtime de AutomatedQa) com um subconjunto representativo de seus dados de produção. Isso o apontará para o local mais fraco.
A única função RTL que se aproxima é essa na unidade de classes:
procedure TStrings.SetDelimitedText(const Value: string);
Ele é compatível, mas usa os dois Quotechar e Delimitador, mas você usa apenas um delimitador.
Ele usa o SetString Função na unidade do sistema, que é uma maneira bastante rápida de definir o conteúdo de uma string com base em um PCHO/Pansichar/Punicodechar e um comprimento.
Isso pode fazer algumas melhorias também; por outro lado, cópia de é muito rápido também.
Eu não sou a pessoa sempre culpando o algoritmo, mas se eu olhar para a primeira peça de fonte, o problema é que, para a string n, você também faz o POS/Posexes para a String 1..n-1.
Isso significa para n itens, você soma (n, n-1, n-2 ... 1) poses (=+/-0,5*n^2), enquanto apenas n são necessários.
Se você simplesmente armazenar em cache a posição do último resultado encontrado, por exemplo, em um registro que é aprovado pelo parâmetro var, poderá ganhar muito.
modelo
TlastPosition = registro elementnr: integer; // Last Tokennumber ElementPos: Integer; // Índice de caracteres da última partida final;
E então algo
se tokennum = (lastPosition.Elementnr+1), inicie o newpos: = Posex (delim, linha, lastPosition.ElementPos); fim;
Infelizmente, não tenho tempo agora para escrevê -lo, mas espero que você entenda a ideia
