Contest: fastest IsAnagram function

[Bart]

Optimized my unit code

Still fails, but now on different check:

Code: [Select]

TestValidity for Josh
FAIL to detect invalid character #0
Validitycheck FAIL for Josh
Should be easy to fix?

Bart

[Josh]

hi

simpliest would be to check the garbage location at end, should wrk. not at pc with laz/fpc on at the moment.

edit : back on lappy with fpc on, so moded  the unit

Code: Pascal  [Select][+][-]

1. unit josh_unit;
2. //{$define OnlyAlphaNumericChars}// a-z,A-Z,' ',0--9
3. {$mode ObjFPC}{$H+}
4.  
5.  
6. interface
7.  
8. uses
9.  {$IFDEF UNIX}
10.   cthreads,
11.   {$ENDIF}
12.   SysUtils;
13.  
14. const
15.   josh_squote=chr(39);
16.   josh_arlow=Byte(32);
17.   josh_arhigh=Byte(128); // 128 is dumping ground for invalid chars
18.   josh_mess_s1='Invalid character in input string at position %d in s1';
19.   josh_mess_s2='Invalid character in input string at position %d in s2';
20.  
21. Var
22.   josh_Map: array[0..255] of Byte;
23.   josh_IgnoredCounter:Int32;
24.   josh_loop:Int32;
25.  
26.  
27. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
28.  
29. implementation
30.  
31. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
32. var
33.   k, l1, l2: Int32;
34.   offset:Byte=0;
35.   josh_FreqArray: array[josh_arlow..josh_arHigh] of Int32;
36. begin
37.   if IgnoreSpaces then offset:=1;
38.   fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
39.   l1:=Length(s1);
40.   l2:=Length(s2);
41.   //inc and dec are slower than +1 -1;
42.   If Not ExceptionOnError then
43.   begin
44.     for k:=1 to l1 do josh_FreqArray[josh_Map[Byte(s1[k])]]:=josh_FreqArray[josh_Map[Byte(s1[k])]]+1;
45.     for k:=1 to l2 do josh_FreqArray[josh_Map[Byte(s2[k])]]:=josh_FreqArray[josh_Map[Byte(s2[k])]]-1;
46.   end
47.   else
48.   begin
49.     for k:=1 to l1 do
50.     begin
51.       if ((Byte(s1[k])<32) or (Byte(s1[k])>127)) then raise Exception.CreateFmt(josh_mess_s1,[k]);
52.       josh_FreqArray[josh_Map[Byte(s1[k])]]:=josh_FreqArray[josh_Map[Byte(s1[k])]]+1;
53.     end;
54.     for k:=1 to l2 do
55.     begin
56.       if ((Byte(s2[k])<32) or (Byte(s2[k])>127)) then raise Exception.CreateFmt(josh_mess_s2,[k]);
57.       josh_FreqArray[josh_Map[Byte(s2[k])]]:=josh_FreqArray[josh_Map[Byte(s2[k])]]-1;
58.     end;
59.   end;
60.   josh_IgnoredCounter:=josh_FreqArray[josh_arhigh];
61.   Result:=josh_IgnoredCounter=0;
62.   if Result then for k:=josh_arlow+offset to josh_arhigh-1 do if josh_FreqArray[k]<>0 then Exit(False);
63. end;
64.  
65. Initialization
66.   for josh_loop:=0 to 255 do josh_Map[josh_loop]:=josh_arhigh;
67.   // map all to arhigh so collects all chars
68.   // now map wanted chars
69.   josh_map[$20]:=$20;
70.   {$ifdef OnlyAlphaNumericChars}
71.   for josh_loop:=$30 to $39 do josh_Map[josh_loop]:=josh_loop;
72.   for josh_loop:=$41 to $5A do josh_Map[josh_loop]:=josh_loop;
73.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=IterationLoop-$20;
74.   {$else}
75.   for josh_loop:=josh_arlow+1 to josh_arhigh-1 do josh_Map[josh_loop]:=josh_loop;
76.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=josh_loop-$20;
77.   {$endif}
78. end.
79.  

     

note i do not have any editing icons
                           

[n_e_k]

hi

what think about this?

valid
'Rep!Yc_{^t'
'Y^!Rcp{_te'

valid
'1234567890'
'0 1 2 3 4 5 6 7 8 9 '

valid
'abcd efgh ijkl mnop qrst uvwx yz'
'qwertyuiop asdfghjkl zxcvbnm'

valid
#1'nightio'
#1'thingio'
 
valid
'!"#$%&''()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~⌂'
'⌂~}|{zyx wvutsrqpon mlkjihgfed cba`_^]\[Z YXWVUTSRQP ONMLKJIHGF EDCBA@?>=< ;:98765432 10/.-,+*)( ''&%$#"!'

Code: Pascal  [Select][+][-]

1. function IsAnagram_nek_v1(const S1, S2: String; IgnoreSpaces: Boolean = True; ExceptionOnError: Boolean = False): Boolean;
2. var
3.   i: integer;
4.   sumS1, sumS2: integer;
5. begin
6.   sumS1:=0; sumS2:=0;
7.  
8.   if IgnoreSpaces then
9.   begin
10.     for i := 0 to length(S1) do sumS1 += byte(S1[i]);
11.     sumS1 -= (32 * length(S1));
12.     for i := 0 to length(S2) do sumS2 += byte(S2[i]);
13.     sumS2 -= (32 * length(S2));
14.   end else
15.   begin
16.     for i := 0 to length(S1) do sumS1 += byte(S1[i]);
17.     for i := 0 to length(S2) do sumS2 += byte(S2[i]);
18.   end;
19.  
20.   result := ( sumS1 - sumS2 ) = 0;
21. end;
22.  

[Josh]

Hi n_e_k,

Welcome to the Forum, good to have another Pascal enthusiast on board – happy coding! 🚀

note
there is no limit on ansistrings they could be 1000's of chars long. you will go out of range.
no exception handling, or ignoring case

try putting these in your routine are they valid?
'abcabcabcabc'
'bbbbbbbbbbbb'

'azazazazaz'
'bybybybyby'

'VJKUKQARCQR'
'THISISATEST'

[n_e_k]

try putting these in your routine are they valid?
'abcabcabcabc'
'bbbbbbbbbbbb'

yes

lol

Dont think about,

thanks

[Bart]

simpliest would be to check the garbage location at end, should wrk. not at pc with laz/fpc on at the moment.

edit : back on lappy with fpc on, so moded  the unit

Alas,

Code: [Select]

TestValidity for Josh
FAIL to detect invalid character #0
Validitycheck FAIL for Josh
Bart

[Bart]

what think about this?

Code: Pascal  [Select][+][-]

1. function IsAnagram_nek_v1(const S1, S2: String; IgnoreSpaces: Boolean = True; ExceptionOnError: Boolean = False): Boolean;
2.  

Fails validity check.

Code: [Select]

TestValidity for Nek
FAIL: valid anagram rejected (with IgnoreSpaces=TRUE):
S1: "abcd efgh ijkl mnop qrst uvwx yz"
S2: "QWERTYUIOP ASDFGHJKL ZXCVBNM"
Validitycheck FAIL for Nek

But it also does not fullfill the requirements that is should raise an exception on errror if ExceptionOnError = True.
So, you cheated as well 

Bart

[Josh]

hi bart
when i add chr(0) to a string it fails validity check

[Bart]

hi bart
when i add chr(0) to a string it fails validity check

IsAnagram_Josh(#0,#0,True,False)) returns TRUE though, which s an error.

Below an excerpt of the main body of my test program.

Code: Pascal  [Select][+][-]

1. begin
2.   //
3.   InitValidAnagrams;
4.   InitInvalidAnagrams;
5.   InitFuncs;
6.   InitUserCode;  //<<-- does what is in your initialization section (I have all code in include files, no seperate units)
7.  
8.   writeln('Josh: #0 ->',IsAnagram_Josh(#0,#0,True,False));  exit;
9.   ...
10. end.

Output:

Code: [Select]

C:\Users\Bart\LazarusProjecten\bugs\forum\anagram>anagram
Josh: #0 ->TRUE
Bart

[Josh]

Hi Bart

Moded Unit,
code has changed, init has changed, var def have changed.
added a define to use inc/dec rather than +-1, as on my aging lap +-1 is faster but on desktop inc/dec is faster. the function as is set for inc/dec

Code: Pascal  [Select][+][-]

1. unit josh_unit;
2. //{$define OnlyAlphaNumericChars}// a-z,A-Z,' ',0--9
3. {$mode ObjFPC}{$H+}
4.  
5. interface
6.  
7. uses
8.  {$IFDEF UNIX}
9.   cthreads,
10.   {$ENDIF}
11.   SysUtils;
12.  
13. const
14.   josh_squote=chr(39);
15.   josh_Arr_Start=Byte(32);
16.   josh_Arr_End=Byte(127);
17.   josh_mess_s1='Invalid character in input string at position %d in s1';
18.   josh_mess_s2='Invalid character in input string at position %d in s2';
19.  
20. Var
21.   josh_Map: array[josh_Arr_Start..josh_Arr_End] of Byte;
22.   josh_IgnoredCounter:Int32;
23.   josh_loop:Int32;
24.   josh_FreqArray: array[josh_Arr_Start..josh_Arr_End] of Int32;
25.  
26. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
27.  
28. implementation
29.  
30. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
31. var
32.   k, l1, l2: Int32;
33.   v:byte;
34.  
35. begin
36.   {$define UseInc}
37.   l1:=Length(s1);
38.   l2:=Length(s2);
39.   if ((l1=0) or (l2=0)) then exit(false);
40.   fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
41.   //inc and dec are slower than +1 -1;
42.   If Not ExceptionOnError then
43.   begin
44.     for k:=1 to l1 do
45.     begin
46.       v:=Byte(s1[k]);
47.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}inc(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]+1{$endif}
48.       else Exit(False);
49.     end;
50.     for k:=1 to l2 do
51.     begin
52.       v:=Byte(s2[k]);
53.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}dec(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]-1{$endif}
54.       else Exit(False);
55.     end;
56.   end
57.   else
58.   begin
59.     for k:=1 to l1 do
60.     begin
61.       v:=Byte(s1[k]);
62.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}inc(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]+1{$endif}
63.       else raise Exception.CreateFmt(josh_mess_s1,[k]);
64.     end;
65.     for k:=1 to l2 do
66.     begin
67.       v:=Byte(s2[k]);
68.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}dec(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]-1{$endif}
69.       else raise Exception.CreateFmt(josh_mess_s2,[k]);
70.     end;
71.   end;
72.   if IgnoreSpaces then
73.   begin
74.     for k:=josh_Arr_Start+1 to josh_Arr_End do if josh_FreqArray[k]<>0 then Exit(False);
75.   end
76.   else
77.   begin
78.     for k:=josh_Arr_Start to josh_Arr_End do if josh_FreqArray[k]<>0 then Exit(False);
79.   end;
80.   Result:=True;
81. end;
82.  
83. Initialization
84.   for josh_loop:=josh_Arr_Start to josh_Arr_End do josh_Map[josh_loop]:=josh_loop;
85.   {$ifdef OnlyAlphaNumericChars}
86.   for josh_loop:=$30 to $39 do josh_Map[josh_loop]:=josh_loop;
87.   for josh_loop:=$41 to $5A do josh_Map[josh_loop]:=josh_loop;
88.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=josh_loop-$20;
89.   {$else}
90.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=josh_loop-$20;
91.   {$endif}
92. end.
93.  

[Bart]

Moded Unit,
code has changed, init has changed, var def have changed.

OK, it passes validity test now.
As to speed: it's approximatley as fast (or as slow) as my original function.

Code: [Select]

Testing speed
Bart           :   516
Bart2          :   437
Warfly         : Failed validity test
Fibonacci      : Failed validity test
ASerge         :   360
Zvoni          : Failed validity test
Zvoni2         : Failed validity test
Alligator      : Failed validity test
SilverCoder    : Failed validity test
AVK            :   172
Paweld         :   375
BrunoK         :   312
Delphius       :   313
Benibela       :   218
Josh           :   500
Nek            : Failed validity test
Martin         : Failed validity test
Dummy          : Failed validity test
Bart

[Warfley]

Moded Unit,
code has changed, init has changed, var def have changed.

OK, it passes validity test now.
As to speed: it's approximatley as fast (or as slow) as my original function.

Code: [Select]

Testing speed
Bart           :   516
Bart2          :   437
Warfly         : Failed validity test
Fibonacci      : Failed validity test
ASerge         :   360
Zvoni          : Failed validity test
Zvoni2         : Failed validity test
Alligator      : Failed validity test
SilverCoder    : Failed validity test
AVK            :   172
Paweld         :   375
BrunoK         :   312
Delphius       :   313
Benibela       :   218
Josh           :   500
Nek            : Failed validity test
Martin         : Failed validity test
Dummy          : Failed validity test
Bart

Why does mine still fail your validity test? have you used the most recent version?

[Bart]

Why does mine still fail your validity test? have you used the most recent version?

I see you updated a post several pages back.
Better post updated code in a new reply.

Your code now passes.
It runs at the same speed as Bart2.
AVK's is still the fastest.

Bart

[Josh]

Hi Bart,

Moded code in my test data getting 30%boost, but it depends on the test data.

change in function, added line toinit section to fill freqarray. it only refreshed the freqarray when needed

How does it perform with your dataset

Code: Pascal  [Select][+][-]

1. unit josh_unit;
2. //{$define OnlyAlphaNumericChars}// a-z,A-Z,' ',0--9
3. {$mode ObjFPC}{$H+}
4.  
5. interface
6.  
7. uses
8.  {$IFDEF UNIX}
9.   cthreads,
10.   {$ENDIF}
11.   SysUtils;
12.  
13. const
14.   josh_squote=chr(39);
15.   josh_Arr_Start=Byte(32);
16.   josh_Arr_End=Byte(127);
17.   josh_mess_s1='Invalid character in input string at position %d in s1';
18.   josh_mess_s2='Invalid character in input string at position %d in s2';
19.  
20. Var
21.   josh_Map: array[josh_Arr_Start..josh_Arr_End] of Byte;
22.  
23.   josh_loop:Int32;
24.   josh_FreqArray: array[josh_Arr_Start..josh_Arr_End] of Int32;
25.  
26.  
27. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
28.  
29. implementation
30.  
31. function IsAnAnagramJosh(const s1, s2: AnsiString; IgnoreSpaces: Boolean; ExceptionOnError: Boolean = False): boolean;  inline;
32. var
33.   k, l1, l2: Int32;
34.   v:byte;
35. begin
36.   {$define UseInc}
37.   l1:=Length(s1);
38.   l2:=Length(s2);
39.   if (l1 = 0) or (l2 = 0) then Exit(False);
40.   If Not ExceptionOnError then
41.   begin
42.     for k:=1 to l1 do
43.     begin
44.       v:=Byte(s1[k]);
45.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}inc(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]+1{$endif}
46.       else
47.       begin
48.         fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
49.         exit(false);
50.       end;
51.     end;
52.     for k:=1 to l2 do
53.     begin
54.       v:=Byte(s2[k]);
55.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}dec(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]-1{$endif}
56.       else
57.       begin
58.         fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
59.         exit(false);
60.       end;
61.     end;
62.   end
63.   else
64.   begin
65.     for k:=1 to l1 do
66.     begin
67.       v:=Byte(s1[k]);
68.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}inc(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]+1{$endif}
69.       else
70.       begin
71.         fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
72.         Result:=False;
73.         raise Exception.CreateFmt(josh_mess_s1,[k]);
74.         exit;
75.       end;
76.     end;
77.     for k:=1 to l2 do
78.     begin
79.       v:=Byte(s2[k]);
80.       if v in [josh_Arr_Start..josh_Arr_End] then {$ifdef useinc}dec(josh_FreqArray[josh_Map[v]]){$else}josh_FreqArray[josh_Map[v]]:=josh_FreqArray[josh_Map[v]]-1{$endif}
81.       else
82.       begin
83.         fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
84.         Result:=False;
85.         raise Exception.CreateFmt(josh_mess_s2,[k]);
86.         exit;
87.       end;
88.     end;
89.   end;
90.  
91.   if IgnoreSpaces then
92.   begin
93.     for k:=josh_Arr_Start+1 to josh_Arr_End do if josh_FreqArray[k]<>0 then
94.     begin
95.       fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
96.       exit(false);
97.     end;
98.     josh_FreqArray[josh_Arr_Start]:=0;
99.   end
100.   else
101.   begin
102.     for k:=josh_Arr_Start to josh_Arr_End do if josh_FreqArray[k]<>0 then
103.     begin
104.       fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
105.       exit(false);
106.     end;
107.   end;
108.   Result:=True;
109. end;
110.  
111. Initialization
112.   for josh_loop:=josh_Arr_Start to josh_Arr_End do josh_Map[josh_loop]:=josh_loop;
113.   fillchar(josh_FreqArray,sizeof(josh_FreqArray),0);
114.   {$ifdef OnlyAlphaNumericChars}
115.   for josh_loop:=$30 to $39 do josh_Map[josh_loop]:=josh_loop;
116.   for josh_loop:=$41 to $5A do josh_Map[josh_loop]:=josh_loop;
117.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=josh_loop-$20;
118.   {$else}
119.   for josh_loop:=$61 to $7A do josh_Map[josh_loop]:=josh_loop-$20;
120.   {$endif}
121. end.
122.  
123.  

[Bart]

Moded code in my test data getting 30%boost, but it depends on the test data.

How does it perform with your dataset

Still about the same.

Code: [Select]

Testing speed
Bart           :   375
Bart2          :   344
Warfly         :   312
Fibonacci      : Failed validity test
ASerge         :   250
Zvoni          : Failed validity test
Zvoni2         : Failed validity test
Alligator      : Failed validity test
SilverCoder    : Failed validity test
AVK            :   109
Paweld         :   266
BrunoK         :   281
Delphius       :   234
Benibela       :   188
Josh           :   390
Nek            : Failed validity test
Martin         : Failed validity test
Dummy          : Failed validity test
Bart