FieldByName é O(n), que tal melhorá-lo para O(Lg n)?

Há muitas formas de acessar os campos dos DataSets no Delphi, conforme a relação a seguir (observe a relação linha x item enumerado):

DataSet.Fields[0].AsString
cdsClienteNOMECLIENTE.AsString
DataSet.FieldByName(''NOMECLIENTE'').AsString
DataSet[''NOMECLIENTE'']
  1. Pelo índice do campo: É uma causa frequente de erros, afinal, mudando a ordem dos campos (na SQL ou no DataSet) altera totalmente o comportamento do código.
  2. Diretamente pelo objeto que representa o campo: Evita os erros da primeira e ainda garante que você acesse somente campos que existem no dataset, avisando durante a compilação caso contrário. Só pode ser usada quando os campos são adicionados em tempo de projeto. Quando se trabalha com multi-bancos existem problemas de mapeamento de tipos de campos e classes de representação.
  3. Por FieldByName: Evita os problemas da primeira abordagem. Mas não há aviso a respeito de campos não existentes no dataset em tempo de compilação.
  4. Pegando o valor diretamente: Usa FieldByName internamente.
  5. Alguma outra?

Para o objetivo deste artigo, irei considerar o uso de FieldByName (3).

Não uso FieldByName, portanto vou parar de ler o artigo!

Calma! Há um detalhe que passa despercebido. Mesmo você não usando, a própria VCL e componentes de terceiros estão cheios de chamadas a este método! Por exemplo, um simples TDBEdit chama este método. O DBGrid, o seu gerador de relatórios e muitos outros.

Hummm, mesmo atribuindo o DataField em tempo de projeto ao TDBEdit?

Sim! A propriedade DataField é uma string. Para fazer o primeiro vínculo é chamado o método FieldByName. Observe este trecho de código, retirado da unit DBCtrls.pas:

procedure TFieldDataLink.UpdateField;
begin
  if Active and (FFieldName <> '''') then
  begin
    FField := nil;
    if Assigned(FControl) then
      SetField(GetFieldProperty(DataSource.DataSet, FControl, FFieldName)) else
      SetField(DataSource.DataSet.FieldByName(FFieldName));
  end else
    SetField(nil);
end;

Abra a unit DBGrids.pas e procure por FieldByName. Você irá encontrar referência em muitas linhas.

Chegamos então a questão do título. O algoritmo que procura um campo no dataset é linear em relação a quantidade de campos, ou seja, sua complexidade é:

  • Ω(1). No melhor caso, o campo procurado é o primeiro da lista.
  • Θ(n/2). No caso médio, você encontra o campo mais ou menos na metade e para.
  • O(n). No pior caso, o campo procurado é o último. O nome do campo foi comparado com todos os outros.

Veja o algorítmo, retirado da unit DB.pas. Note que o TDataSet.FieldByName chama TFields.FindField:

function TFields.FindField(const FieldName: string): TField;
var
  I: Integer;
begin
  for I := 0 to FList.Count - 1 do
  begin
    Result := FList.Items[I];
    if WideCompareText(Result.FFieldName, FieldName) = 0 then Exit;
  end;
  Result := nil;
end;

Repare a simplicidade. Na linha 5 é realizado um for na lista de campos (FList). Atribui o i-ésimo item à variável de retorno Result na linha 7. Na linha 8, caso o FFieldName seja igual ao campo procurado o algoritmo é interrompido. Se o campo procurado for o último da lista, o for será executado completamente.

Isso é conhecido como o algoritmo do pintor burro. Suponha que você contrate um pintor para pintar aquelas linhas do meio da rodovia. Mas o pintor não move a lata de tinta. Então todas as vezes ele molha o pincel, pinta a rodovia e volta para molhar o pincel novamente. No começo é rápido, mas quanto mais ele se distancia da lata de tinta, mais demorado fica. (Veja mais sobre isso neste ótimo post no Blog do Joel)

Puxa, isso é muito ruim. Como melhorar isso?

De fato existem alguns algoritmos melhores para fazer isso. Pode-se implementar um hash que distribua os nomes dos campos de acordo com os índices. Mas isso parece um pouco complicado. Além do mais, não existe este tipo de estrutura pronta no Delphi, e então seria necessário incluir uma outra dependência no DB.pas.

Outra forma de melhorar é usar uma lista ordenada. Sabe-se que procurar um item numa lista ordenada é O(lg n). Inclusive, este algoritmo é implementado no tão conhecido TStringList. Só é necessário ordenar ele, com a propriedade sorted := true.

Ótimo então, vamos alterar o arquivo DB.pas e incluir uma lista ordenada!

Realizar uma alteração em um arquivo da VCL é mais complicado que só alterar o código. O ideal seria:

  1. Adicionar uma variável privada na classe TFields do tipo TStringList.
  2. Ao adicionar os Fields no dataset, adicioná-lo também nesta outra lista ordenada.
  3. Ao procurar por um campo, utilizar a lista ordenada.

Porém, alterar a definição de um objeto implica em recompilar todas as units dependentes. Isso inclui tudo que usa TDataSet, inclusive partes da própria VCL. Já recebeu à famosa mensagem Unit x was compiled with a different version of y?

Como é melhor causar o menor impacto possível, a saída é declarar uma variável global na unit DB.pas. Porém, sendo global, não temos uma instância própria para cada instância de dataset. Isso implica em termos uma lista de datasets antes. Cada item desta lista tem uma outra lista com os campos, ou seja, uma lista de listas. (Uma lista de datasets onde cada item é uma outra lista de campos)

Desta forma, realizar a alteração é feito na seguinte ordem:

  1. Declarar uma variável global do tipo TStringList. Iniciar na seção initialization e destruir na finalization;
  2. Alterar o método FindField da classe TDataSet. (O melhor seria FindField de TFields, mas o código não ficaria tão simples, já que precisaria preocupar com a leitura de campos do dfm)
  3. Na primeira chamada de FieldByName, construir a lista ordenada de campos
  4. Destruir a lista ao fechar o dataset

“Há, mas qual é o overhead introduzido com estas alterações?”

Bom, não tem como não ter nenhum. Então o overhead introduzido com esta alteração é o seguinte:

  • Uma lista é instanciada no início da aplicação. Esta lista será preenchida com dataset”s que invocaram o método FieldByName pelo menos uma vez. O dataset é removido da lista quando for fechado. Isso só é preocupante quando se tem muitos dataset”s ativos na aplicação. Deixá-los abertos também é uma má prática, ok?
  • Uma outra lista é instanciada para cada dataset, e contém os campos do mesmo, de forma ordenada. É executado o algoritmo quicksort Θ(lg n) para ordenar a lista. Isto é feito uma vez a cada abertura do dataset.
  • O quicksort tem pior caso O(n²), quando os itens já estão ordenados. Mas em geral isso raramente irá acontecer, certo?

Não seria melhor remover o dataset da lista somente no evento Destroy do TDataSet?

Seria. Mas há o caso de dataset”s temporários, onde os campos são criados em tempo de execução. E se o desenvolvedor fechar o dataset e modificar os campos?

Para ser mais breve, vou anexar um diff do arquivo DB.pas no final. Por hora, uma análise da alteração no método TDataSet.FindField:

function TDataSet.FindField(const FieldName: string): TField;
var
  List: TStringList;
  i, di: Integer;
begin
  di := DataSetsListOrderFields.IndexOf(GetObjectUniqueName(Self));
  if di < 0 then
  begin
    List := TStringList.Create;
    List.Capacity := FFields.Count;
    for i := 0 to FFields.Count - 1 do
      List.AddObject(FFields[i].FieldName, Fields[i]);
    List.Sorted := True;
    DataSetsListOrderFields.AddObject(GetObjectUniqueName(Self), List);
  end
  else
    List := TStringList(DataSetsListOrderFields.Objects[di]);

  Result := nil;
  if List.Find(FieldName, i) then
    Result := TField(List.Objects[i]);
  if (Result = nil) and ObjectView then
    Result := FieldList.Find(FieldName);
  if Result = nil then
    Result := FAggFields.FindField(FieldName);
end;

Seja m a quantidade de dataset”s abertos e n a quantidade de campos:

  • Ao iniciar o método (linha 6), procuramos pelo dataset na lista. Essa operação leva O(lg m), já que esta lista também é ordenada.
  • Se ele não é encontrado (primeira chamada a FieldByName), o dataset é então adicionado a lista (linhas 9 a 14). Esta operação leva O(n + lg m). O lg m é para buscar a posição onde inserir o dataset.
  • Na linha 20 o campo é então procurado, isso leva O(lg n).

Resumindo, a complexidade total na primeira chamada seria O(2 lg m + lg n) e nas demais O(lg m + lg n). Poderia remover o O(lg m) se fosse declarado uma nova variável a classe TDataSet. Mas esta complexidade já garantirá um bom desempenho. Vamos aos testes?

Os testes executados consistem em criar um ClientDataset com cem (100) campos inteiros, preenchê-lo com 10, 20 e 30 mil registros usando FieldByName e consultar os valores do melhor caso (1º campo), caso médio (50º campo) e pior caso (último campo). Veja a figura com os resultados:

Comparação de FieldByName O(n) e O(lg n)
Tempos da comparação de FieldByName O(n) e O(lg n)

Os testes foram executados em uma máquina virtual VMWare com Windows XP e Delphi 2009. O aplicativo foi executado fora do Delphi, para não haver interferência do debugger. Talvez os tempos mudem em uma máquina real, mas acredito que a proporção entre eles se mantenha. Segue uma breve discussão dos resultados:

  • Append: Na adição de registros todos os campos são chamados uma vez para cada registro. O novo método FieldByName mostra-se até 73% mais rápido que o antigo (de 9,78 para 2,59 segundos).
  • No melhor caso: Como era esperado, o novo método é alguns centésimos de segundos (0,14 para 0,17) pior. Isso ocorre porque o novo algoritmo é Ω (lg n), ao contrário do antigo, que é Ω (1).
  • No caso médio: O novo FieldByName chega a ser 63% mais rápido que o antigo.
  • No pior caso: O novo FieldByName é até 80% mais rápido.
  • Constante: Observe também que tempo entre o melhor, médio e pior caso se mantém constante entre os registros, mostrando que sua complexidade é sempre lg n (na tabela, destacado em laranja).

Aqui está o arquivo diff com as modificações no arquivo DB.pas e o código dos testes. Elas foram feitas para o Delphi 2009. Aplicarei elas ao Delphi 2006 e 2007. Caso haja alguma diferença, postarei as outras versões.

Para você que resistiu firme até aqui, se tiver algum comentário ou observação, sinta-se a vontade!

Anúncios

10 comentários sobre “FieldByName é O(n), que tal melhorá-lo para O(Lg n)?

  1. Realmente existe uma pequena diferença entre D2009 e os demais. No Delphi 7 e 2009 é usado string enquanto no Delphi 2006 e 2007 é usado widestring.
    Atualizei o arquivo diff com estas diferenças e uma correção. O FindField alterado estava retornando campos incorretos. Quem já baixou o arquivo até o momento, por favor, atualize para corrigir o problema.

    Curtir

  2. Oi, deixa eu ver se entendi seu teste, após a inclusão dos dados:
    Depois que vc incluiu os dados, vc apenas tentou ler o 100º campo, independente da posição do registro, e levou 0.5 segundo?

    Se for isso, levando-se em conta que tenhamos cerca de 30 campos, menos da metade do seu teste, no pior caso ele levaria 0.3 segundos pra acessar, hummmm…

    talvez essa situação de “lentidão” do fieldbyname seja mais notada em operações que ocorrem em loop, fora isso, não sei se causaria uma real lentidão.

    Oura coisa, qdo vc diz:

    “# Diretamente pelo objeto que representa o campo: Evita os erros da primeira e ainda garante que você acesse somente campos que existem no dataset, avisando durante a compilação caso contrário. Só pode ser usada quando os campos são adicionados em tempo de projeto. Quando se trabalha com multi-bancos existem problemas de mapeamento de tipos de campos e classes de representação.”

    Esse problema de multi-bancos: no que diz respeito a tipos de campos, não é resolvido pelo DBExpress? Por exemplo, se digo que meu TField é um ftMemo (no clientdataset), o driver de conexão do banco que uso no momento, não tem que converter ftMemo para o tipo específico do banco?

    Curtir

  3. @paulo quicoli
    Paulo,

    1. No “worst case” foi lido o último campo, porém para todos os registros. Este é o pior caso, onde o código original compara todos os TFields do dataset até encontrar o último. Observe que os valores variam muito para a quantidade de registros. E também variam muito se você está acessando o primeiro ou último campo. No código alterado estes tempos são praticamente constantes.

    Você realmente irá perceber melhora significativa em loops, mas existem outros casos, como no carregamento das telas/criação de datamodules onde poderás verificar uma boa melhora também.

    2. Não é resolvido pelo DBExpress. O tipo de campo que você define no ClientDataSet diz respeito ao formato que o criador do driver mapeou. Há muita incompatibilidade entre campos numéricos (por exemplo) entre os vários drivers existentes.

    Curtir

  4. Olá Thiago,

    Consegui baixar o arquivo, porém estou com dúvidas de como implementar.

    Devo aplicar essa diff no DB.pas nativo do Delphi ou criar um outro, não sei como implementar essa solução. Você pode me ajudar?

    Abraço.

    Curtir

    1. Sim Fábio. Os passos são:
      1. Aplicar o diff no DB.pas original, da pasta source do Delphi
      2. Colocar o novo DB.pas (após o diff) na pasta Lib do Delphi
      3. Remover a DB.dcu da pasta Lib e também da Debug do Delphi.
      4. As vezes é necessário reiniciar o Delphi, pois ele faz cache do dcu antigo!
      Você terá certeza que está usando o novo DB.pas quando for gerado um novo .dcu para ele.

      Curtir

  5. Olá Thiago,

    Obrigado pela ajuda, segui todos os passos e funcionou perfeitamente.

    Vou testar agora com uma aplicação maior, qualquer novidade ou dúvida eu posto aqui.

    Abraço.

    Curtir

  6. Olá Fábio, como se aplica o diff no tornoise, eu tentei mas só da erro, tem como você fazer um passo a passo para aplicar o diff, e eu tambem tentei implementar a alteração direto no DB.pas, mas ai fica dando erro em outras Units como a DBTalbe entre outras, ele diz que o DB.pas foi compilado em outra versão.

    E se eu apenas alterar o DB.pas ele não acata a alteração, ai ei preciso apagar o DB.dcu que fica na pasta lib e libdebuger e jogar o DB.pas na pasta lib para criar novamente os dcu e ai que da o maior pau em outras Units.

    Att.
    Carlos Fitl.

    Curtir

    1. Carlos, você pode aplicar o diff utilizando diretamente o comando patch (disponível na internet para win32) ou aplicar diretamente a alteração no DB.pas. Neste último caso, tome cuidado para não alterar a seção interface da unit. Qualquer alteração nela vai causar esta necessidade de recompilação de outras units.

      Curtir

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s