Gabor;

It just happened that I needed this function myself, and I found two errors in my pseudo-code. Here it is, corrected: [snip]

Your algorithm is similar to what I had devised initially, but I was not happy with the performance. In my case I was using it on files that could (conceivably) be 20+ meg. Some of those files were taking 3-5 minutes for the calculations (even with a 933mhz PIII). That, I felt, was unacceptable.

Basically, I had a const that was my 10 or 12 delimiter characters and I would then use the pos() function to see if each character of every string was a delimiter. Seemed like a good idea at the time, but it was very slow.

What I found to be faster was to do something like this:

for each character of the string check to see if it's an upper or lower case letter or number;

  if TRUE, keep counting;
  if FALSE, do pos() on the delimiters const
    if TRUE, it's the end of a word -- add to word count
    if FALSE, it's not a word -- keep looking

Here's an idea of what I had done...

Function GetWords (StringToCheck : string) : longint;
const
  DELIMITERS = ' .,!?_-)}]>;';
var
  Index       : longint;
  LineLength  : longint;
  Loop        : longint;
  Words       : longint;
  CurrentChar : char;
begin
  Words := 0;
  Index := 0;
  LineLength := length (StringToCheck);
  if LineLength  0 then   // don't check empty srings
     while Index < LineLength do
     begin
       inc (Index);
       CurrentChar := StringToCheck [Index];

while (Index < LineLength) and ((CurrentChar >= 'a') and (CurrentChar <= 'z')) and
((CurrentChar >= 'A') and (CurrentChar <= 'Z')) and ((CurrentChar >= '0') and (CurrentChar <= '9'))

             do inc (Index);   // skip all the "word" characters

       // don't count double delims, like a period followed by a space, as
2 words
       if pos (StringToCheck [succ (Index)],DELIMITERS)  0 then
       begin
         inc (Words);
         inc (Index);   // move index past current delim char
       end;
     end;
  GetWords := Words;
end;

Replace the string by a set, this is much faster:
const
DELIMITERS : set of char = ['
','.',',','!','?','_','-',')','}',']','>',';',':','=','@','/','\',#9];

You can leave away the if, the while index<linelength is false if linelength is 0 because
index is set to 0 above.

Using

while (Index < LineLength) and (CurrentChar in ['A'..'Z','a'..'z','0'..'9']) do

might be faster as well

do inc (Index); // skip all the "word" characters // don't count double delims, like a period followed by a space, as 2 words

        if StringToCheck [succ (Index)] in DELIMITERS then

Replace the string by a set, this is much faster:
const
DELIMITERS : set of char = ['
','.',',','!','?','_','-',')','}',']','>',';',':','=','@','/','\',#9];

You can leave away the if, the while index<linelength is false if linelength is 0 because
index is set to 0 above.

Using

while (Index < LineLength) and (CurrentChar in ['A'..'Z','a'..'z','0'..'9']) do

might be faster as well

do inc (Index); // skip all the "word" characters // don't count double delims, like a period followed by a space, as 2 words

        if StringToCheck [succ (Index)] in DELIMITERS then

should beat the pos call easily

Florian;

','.',',','!','?','_','-',')','}',']','>',';',':','=','@','/','\',#9];

if StringToCheck [succ (Index)] in DELIMITERS then should beat the pos call easily

Much faster? Boy, was that an understatement. The original version I had posted checked an entire 30 meg ASCII text file in a pathetic 2 minutes. Simply making the 2 changes above that you had suggested dropped that to a mind-blowing 4 seconds! That's a staggering difference. But I must confess that I don't know exactly why there would be such a huge difference. Why is a "set of char" soooo much faster then a const?

while (Index < LineLength) and (CurrentChar in

['A'..'Z','a'..'z','0'..'9']) do

might be faster as well

This was certainly cleaner looking then what I had posted, but I can't honestly tell if it makes much difference because the previous update was so fast it left little room for improvement! :-)

Thanks much for the tip...

Jim

At 10/1/01 10:34 AM, you wrote:

James,

Your algorithm is similar to what I had devised initially, but I was not happy with the performance. In my case I was using it on files that could (conceivably) be 20+ meg. Some of those files were taking 3-5 minutes for the calculations (even with a 933mhz PIII). That, I felt, was unacceptable.

There is something definitely fishy around here, no implementation can be faster than a single run across the whole text file... :-)) The reason for your performance problem, as you have already noted, was not the algorithm itself but using Pos. Pos is a rather expensive string operation, each time you call it, it has to iterate through your string of delimiters. The set is practically equivalent to a table lookup: just imagine an array[#0..#255] of Boolean. Before you start, you fill this array with False, then put True into the places you want to call a delimiter, for instance:

array[#32] := true; array [#9] := true;

Now, checking for a delimiter is as simple and fast as:

if array[c] then ...

Still, my algorithm is basically a little bit faster. The important idea is to make sure you only check each character of the input stream once (and this is the theoretical optimum, you cannot find all words without checking all characters at least once but you don't need more than one check for each character to learn whether it is a delimiter or not).

You first check with

   CurrentChar := StringToCheck [Index];

then, later, you check the next character using

   if pos (StringToCheck [succ (Index)],DELIMITERS)  0 then

However, if it's not a delimiter, you don't increment Index and you'll re-check the very same input character in the next iteration.

But yes, you're right, this is hair splitting... :-))) However, it can become quite important in some cases, not necessarily because of the speed, but in some applications where you receive the input characters one by one and you cannot go back to the previous character any more.

Bye,
Gábor

------------------------------------------------------------------- Gabor DEAK JAHN -- Budapest, Hungary.
E-mail:

Because Pascal isn't C. :-) Pascal has this concept built in; Pos checks for a string in another string, it isn't optimized for just a character.

What you posted looked typically C-ish alright.

-- Barry

We do have a separate version of pos for use with a character as first parameter. The reason it's much faster has been already explained with someone else (set ~ array[char] of boolean)

Jonas

Hi All,

I know there had some talks about porting ICS (Internet Component Suite) from Delphi/Kilyx to Fpc.

Somebody could tell me what is the advancement ?

Thank you.
Alexis.

None, but with the routines from Michael Schnell (see contrib units port), and about an half year of compiler and RTL fixes a new attempt could be successfull.

There is still no thread support in the RTL

Peter

En réponse à Marco van de Voort :

Sorry, I did'nt find anything from Michael Schnell on freepascal.org. (But I am really stupid... so...;-). I looked in contributed unit section, development section, future plans... where is it exactly ?

It's called FPthreads, and it is also in the /pub/fpc/contrib dir on FTP.

It is a substitute for some base classes from Delphi.

I once got some basic ICS stuff to compile by using some VCL code to cover missing parts, but it didn't work, probably -as Peter noted- due to the still not perfect threading support of the RTL.

FPthreads could substitute some of the stuff I used from the VCL to test, to create a more Open Source friendly system.

timized for just a character.

By the way, pos() is sometimes too slow itself, especially for searching lage strings. Using attached unit I saw big difference. (Selection of start positions is free :))

Petr