Avatar billede lrj Nybegynder
27. april 2000 - 11:04 Der er 10 kommentarer og
1 løsning

Hurtig streng manipulation til XML parser

Jeg sidder og roder med en OpenSource XML-parser til Delphi. Sourcen til denne kan hentes på http://www.delphihome.com/xml/ - men den er ikke programmeret helt færdigt - den kan gemme XML-filer, men ikke læse dem ind igen.

Projektet hedder XMLWorks, og hvad jeg så har lavet, er en lille udvidelse, så den kan læse sine egne filer ind igen. Her kommer så performance ind i billedet - for en XML-fil med 2000 poster (ikke så utænkeligt endda...) tager forholdsvist lang tid at parse. Jeg har lavet 2 implementationer, en baseret på strings og en baseret på PChars - og på min temmelig store maskine med rigeligt ram tager det ca. 16 sekunder at parse med PChar-løsningen og ca. 11 sekunder med string løsningen.

Nu har jeg jo altid troet at PChar var mere effektiv end Delphi's indbyggede strenge.. Det er da i hvert fald hvad jeg har hørt. Men jeg kan også godt se, efter jeg har optimeret så meget som jeg fåmår, at der er lidt uhensigtsmæssigheder i min XML implementering.

Nå, tid til spørgsmålet: Nedenfor har jeg pastet mine to implementeringer - hent XMLWorks og sæt dem ind i sourcen dertil (jeg kan evt. sende dig et eksempelprojekt). Hjælp mig så med at få presset maximal performance ud af det forhåndenværende :)

På forhånd tak :)

{$IFDEF str}
procedure TXMLCollection.ParseXML(const Value: string);
//String implementeringen
//  Previous: TXMLCollectionItem(Add).ParseXML(PChar(Value));
var
  XMLList          : string;
  StartIndex,
    StopIndex      : integer;
  SearchStrStart,
    SearchStrStop  : string;
begin
  SearchStrStart := '<' + DTDName + '>';
  StartIndex := pos(SearchStrStart, value);
  SearchStrStop := '</' + DTDName + '>';
  StopIndex := pos(SearchStrStop, value);
  XMLList := copy(value, StartIndex, StopIndex - StartIndex +
    length(SearchStrStop));

  SearchStrStart := '<' + TXMLCollectionItemClass(ItemClass).GetElementName +
    '>';
  SearchStrStop := '</' + TXMLCollectionItemClass(ItemClass).GetElementName +
    '>';

  while pos(SearchStrStart, XMLList) > 0 do
  begin
    StartIndex := pos(SearchStrStart, XMLList);
    StopIndex := pos(SearchStrStop, XMLList);

    TXMLCollectionItem(Add).ParseXML(PChar(copy(XMLList, StartIndex, StopIndex -
      StartIndex + length(SearchStrStop))));

    XMLList := copy(XMLList, StopIndex + length(SearchStrStop),
      length(XMLList));
  end;
end;
{$ENDIF}

{$IFNDEF str}

procedure TXMLCollection.ParseXML(const Value: string);
//PChar løsningen:
//  Previous: TXMLCollectionItem(Add).ParseXML(PChar(Value));
var
  pDTDName          : PChar;
  pXMLList          : PChar;
  pSearchStr        : PChar;
  pCloseElementName,
    pElementName    : PChar;
  CloseElementLength: integer;
  Length            : cardinal;
begin
  pSearchStr := PChar(value);

  pDTDName := PChar('<' + DTDName + '>');

  pXMLList := strpos(pSearchStr, pDTDName); //find the start index of the list

  Length := strpos(pXMLList, PChar('</' + DTDName + '>')) - pXMLList;  //find the length of the data-list

  StrLCopy(pXMLList, pXMLList, Length + strlen(pDTDName) + 1);  //removes everything AFTER the list

  if Length > 0 then                    //data in the list to be processed
  begin
    pElementName := PChar('<' + TXMLCollectionItemClass(ItemClass).GetElementName
      + '>');
    pCloseElementName := PChar('</' +
      TXMLCollectionItemClass(ItemClass).GetElementName + '>');

    CloseElementLength := strlen(pCloseElementName);
    //initialize variable:
    pXMLList := strpos(pXMLList, pElementName);

    while pXMLList <> nil do
    begin
      pXMLList := strpos(pXMLList, pElementName); //crop up to the next element

      StrLCopy(pSearchStr, pXMLList, strpos(pXMLList, pCloseElementName) -
        pXMLList + CloseElementLength); //return in pSearchStr, the current post to be searched

      inc(pXMLList, strlen(pSearchStr));

      TXMLCollectionItem(Add).ParseXML(pSearchStr);

      pXMLList := strpos(pXMLList, pElementName);
    end;
  end;
end;
{$ENDIF}
Avatar billede sjensen Nybegynder
27. april 2000 - 13:39 #1
hvad med at bruge delete i stringen for hver pos du finder:

..
..
l1 := length(searchstart);
l2 := length(searchstop);
sa := pos(searchstart);
ss := pos(searchstop);

if sa > 1 do delete(value,1,sa-1);
while sa > 0 do
begin
  delete(value,p,l);
  if ss > 0 then collectionitem.add(copy(value,1,ss-1);
  delete(value,1,ss+l2);
  sa := pos(searchstart);
  ss := pos(searchstop);
end;

det burde da være hurtigt !!
Avatar billede lrj Nybegynder
27. april 2000 - 13:45 #2
Delete var et godt bud - vender lige tilbage med lidt benchmark-resultater :)
Avatar billede lrj Nybegynder
27. april 2000 - 14:27 #3
Whoha!

Linjen i mit program, der modsvarer
  delete(value,1,ss+l2);
fik lige tiden fra 11 sekunder for 2000 poster ned på 3 sekunder - ganske komfortabelt :)

Jeg siger mange tak - men mon ikke man kan gøre det endnu bedre med PChar - har de generelt ikke bedre performance?
Avatar billede sjensen Nybegynder
27. april 2000 - 14:28 #4
lrj,

hvis du bruger den sådan som jeg har vist (med de nødvendige ændringer) så vær lige opmærksom på at jeg glemte en vigtig detalje:

Før while loopen tester jeg på og der er noget i strengen før searchstart og hvis der er fjerner jeg det (if sa > 1 do delete(value,1,sa-1);), men jeg glemmer så efterfølgende at sætte sa igen, så hvis whilen bliver udført vil første delete være forkert, da p (som jo skulle have været sa) vil pege forkert ind i strengen. Der skal derfor tilføjes endnu en sa := pos(..) så her kommer det lige igen:

..
..
sa := pos(searchstart);

if sa > 1 then
begin
  delete(value,1,sa-1);
  sa := pos(searchstart);
end;

while sa > 0 do
begin
  delete(value,sa,l);
  if ss > 0 then collectionitem.add(copy(value,1,ss-1);
  delete(value,1,ss+l2);
  sa := pos(searchstart);
  ss := pos(searchstop);
end;


Avatar billede lrj Nybegynder
27. april 2000 - 14:31 #5
Hmm, problemet er lidt at det skalerer meget dårligt - med 4000 poster tager det så 16 sekunder, i stedet for 6-7 som man kunne forvente. Det er en temmelig fæl tilvækst, if I may say so.

Men er det generelt sådan når man opererer med strenge i megabytestørrelsen?
Avatar billede sjensen Nybegynder
27. april 2000 - 14:57 #6
lrj,

jeg tror ikke på den med pchar. Delphi er historisk set (fra pascal) udstyret med strenge hvor nul-byten er en værdi der angiver længden på strengen. Derfor ved den allerede ved første byte hvormange der er i strengen og skal ikke først igennem hele strengen for at finde et nul-tegn som terminering. Jeg er godt klar over at det ikke gælder for de såkaldte "huge-strings" men jeg mener stadig at der sker en intern konvertering fra en streng 8af traditionel karakter) til en nul-termineret når man angiver den som pchar. Derfor er pchar langsommere at arbejde med.

Pchar er en unaturlig tilvækst for Delphi der efter min opfattelse kun er medtaget for at gøre kald til Windows API lidt lettere. Ellers ville jeg ikke bruge pchars til andre opgaver.

Så generelt tror jeg ikke det kan gøres hurtigere med en pchar istedet for en string.

I øvrige kunne jeg foreslå at du istedet for at fylde de isolerede strenge ind i din collection i parserrutinen, kaldte dem med en tstrings og fyldte dem derind i stedet. Når du så kommer tilbage kan du køre dem over i collections, evt. med assgin eller noget lign. Det burde alt andet lige være hurtigere end at holde styr på din collection i samme rutine, men vi er måske dernede hvor tiden ikke betyder så meget.
Avatar billede lrj Nybegynder
27. april 2000 - 16:57 #7
Min algoritme ser ud som følger, med dine betegnelser:

sa := pos(searchstart);
ss := pos(searchstop);
l2 := length(ss);

while sa > 0 do
begin
  if ss > 0 then
    collectionitem.add(copy(value,sa,ss-1+l2));

  system.Delete(value, 1, ss + lStop);

  sa := pos(searchstart);
  ss := pos(searchstop);
end;

Men det er vel i bund og grund det samme? For den indledende delete du laver er jo blot initialisering af variable - hvad der tæller er vel indholdet af while løkken. Og det skal gøres så småt som muligt.

Men er der snart mere der kan forbedres i denne løsning?
Avatar billede lrj Nybegynder
27. april 2000 - 17:00 #8
Du mener altså, at lave det som dual-pass-agtigt, hvor først udtrækkes alle elementer som skal parses som items - disse stykker rå-xml lægges i en tstring(-list). Denne itereres så igennem med kald til TCollection.add og de enkelte linjer i tstringen sendes så som parametre. Det var det du mente?
Avatar billede sjensen Nybegynder
28. april 2000 - 09:28 #9
ja, det var det. Jeg mener at det er hurtigere at arbejde med elementerne i en tstringlist fordi de er memory-only og ikke samtidig fremme på skærmen, som jeg formoder din Collection er. I almindelighed er det væsentligt hurtigere at arbejde med elementer der ikke skal opdatere et visual komponent, selvom man ofte kan sætte det visuelle komponents Update- til false mens man opdaterer således at den ikke skal ændre skærmen samtidig.

Men hvis din tcollection ikker er et visuelt komponent burde der ikke være den store forskel, og det kan udmærket tænkes at det blot vil forøge tiden at kopiere det fra den ene til den ande efterfølgende.

Husk på at en tstringlist har en property der hedder Text, der er en samling af alle linier i listen, behørigt udfyldt med crlf, og du kan derfor flytte alle linier fra en stringlist til en tilsvarende liste ved blot at sætte Tlist.text := Tlist1.text;

Det er væsentligt hurtigere end en tilsvarende:

for 0 to listcount do ..

Så det må vel komme an på en prøve.
Avatar billede lrj Nybegynder
09. maj 2000 - 21:52 #10
Jeg beklager den lange behandlingstid. Ændringen er nu lavet i min source, og en kopi af begge mine løsninger er sendt tilbage til den originale forfatter. Så må vi se om han kan bruge det til noget. :)

Tak for hjælpen :)
Avatar billede lrj Nybegynder
09. maj 2000 - 21:56 #11
Den collection det drejer sig om er kun til hukommelsesbrug, og den er altså ikke visuel. Det er den valgte datastruktur til elementerne i XML-filen.

Den endelige løsning kan ses her, og bruges af enhver i stedet for den medfølgende til komponenten:

procedure TXMLCollection.ParseXML(const Value: string);
//  Previous: TXMLCollectionItem(Add).ParseXML(PChar(Value));
var
  pDTDName          : PChar;
  pXMLList          : PChar;
  pSearchStr        : PChar;
  pCloseElementName,
    pElementName    : PChar;
  CloseElementLength: integer;
  Length            : cardinal;
begin
  pSearchStr := PChar(value);

  pDTDName := PChar('<' + DTDName + '>');

  pXMLList := strpos(pSearchStr, pDTDName); //find the start index of
the list

  Length := strpos(pXMLList, PChar('</' + DTDName + '>')) -
pXMLList;  //find the length of the data-list

  StrLCopy(pXMLList, pXMLList, Length + strlen(pDTDName) +
1);  //removes everything AFTER the list

  if Length > 0 then                    //data in the list to be
processed
  begin
    pElementName := PChar('<' + TXMLCollectionItemClass
(ItemClass).GetElementName
      + '>');
    pCloseElementName := PChar('</' +
      TXMLCollectionItemClass(ItemClass).GetElementName + '>');

    CloseElementLength := strlen(pCloseElementName);
    //initialize variable:
    pXMLList := strpos(pXMLList, pElementName);

    while pXMLList <> nil do
    begin
      pXMLList := strpos(pXMLList, pElementName); //crop up to the
next element

      StrLCopy(pSearchStr, pXMLList, strpos(pXMLList,
pCloseElementName) -
        pXMLList + CloseElementLength); //return in pSearchStr, the
current post to be searched

      inc(pXMLList, strlen(pSearchStr));

      TXMLCollectionItem(Add).ParseXML(pSearchStr);

      pXMLList := strpos(pXMLList, pElementName);
    end;
  end;
end;
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester