Can Sets be used to skip array items? [Solved]

[mas steindorff]

What I want to do is to move the data from one source array to another array while skipping select indexes.
the source array is 30 items [1..30]
1: will this work?
2: I need this to be fast as I process 1000s of arrays / second (with the same SkipSet).  Is there a better way?

Code: [Select]

type
 DataSlots = set of byte ;

var Skipset :DataSlots;
   final :array[0..29] of double;


procedure f1
var i:byte;
 begin
  skipset :=[]; 
  for i:= 1 to 30 do begin
    if (testForSkip(i)) then
       include(skipset ,i);  // include is a pascal set operator "skipset := skipset +[i]"
   end;
end;

function f2(sarray:array[1..30] of double):interger;
var i:byte;
     c:integer;
begin
  c := 0;
  for i:= 1 to 30 do
     if not (i in SkipSet) then begin
        final[c] = sarray[i];   // or doSomething(sarray[i])
        inc(c);
       end;
  result := c;
end;

suggestions?  Thanks

[taazz]

have you tried the opposite?

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

1. function f2(sarray:array[1..30] of double):interger;
2. var i:byte;
3.      c:integer;
4.      d:DataSlots;
5. begin
6.   c := 0;
7.   D := fullset-skipset;
8.   for I in D do begin
9.     final[c] = sarray[i];   // or doSomething(sarray[i])
10.     inc(c);
11.   end;
12.   result := c;
13. end;
14.  

[guest60499]

What you are wanting to do is best described using the filter function. It turns a list into a new list where all members satisfy a predicate. However in most languages this allocates memory and then copies the values from the input array.

Another way to implement this functionality that reduces copying (and is closer to what you described) is used by R and older array programming languages. E.g. array > 3 would return a list of indices that satisfy the test, and you can index an array with an array to get a array, so you could write:

Code: [Select]

array[array > 3]To get the elements of array greater than 3.

So: Yes, this will work, but you are not directly making use of language level facilities to do it, even though you are using sets. I would suggest using an array of indices, not a set.

[mas steindorff]

Taazz: interesting, I can see a lot of use for this type of code.  Do you have a fill for how long to takes?
  My first though was to use a bit list (i.e word) and a shifting mast operation but the reference guide suggested SETs were already set up as bits.  If this code comes down to a simple "bit test" in the ASM, I do not think I can better it in pascal.

Rob0t1: also interesting, do you know of a reference or keyword  I can use to find more info in the pascal usage of array filter functions?  "Filters" hits a lot of objects but I'm stuck with an array[] at this time. 

[engkin]

• Pass pointers instead of arrays as you already know the number of items. Because an array is two values, a pointer and an upper limit, which would waste a precious CPU register.
  
• Remove c and used Result directly
• You can try to unroll the loop and see if that gives you any boost
• Move in reverse order from last item to cancel the need to compare with 30

Maybe:

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

1. {$Optimization REGVAR}
2. function f2(Src:PDouble; Dst:PDouble; Skipset:DataSlots):integer;
3. var
4.   i:byte;
5. begin
6.  Result := 0;
7.  i := 30;
8.   repeat
9.      if not (i in SkipSet) then begin
10.         Dst^ := Src^;
11.         inc(Result);
12.        end;
13.      dec(Src);
14.      dec(Dst);
15.      dec(i);
16.   until i<>0;
17. end;

Not tested.

[taazz]

Taazz: interesting, I can see a lot of use for this type of code.  Do you have a fill for how long to takes?
  My first though was to use a bit list (i.e word) and a shifting mast operation but the reference guide suggested SETs were already set up as bits.  If this code comes down to a simple "bit test" in the ASM, I do not think I can better it in pascal.

Sorry no, I did not had the chance to test or use the construct yet but I'm assuming that there is a set enumerator class somewhere on the rtl you can take a look.

[Thaddy]

Back to the original question:
Yes, this is perfectly legal:

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

1. program test;
2. {$mode delphi}
3. Type
4.   TMyRange = 0..29;
5.   TMySet = set of TMyRange;
6. var
7.   S:TMySet;
8.   R:TMyRange;
9. begin
10.   S:=[0,2,5,9];
11.   For R in S do writeln(R); // no need to test for membership.....
12. end.

It is also very fast. Of course this can also be applied to the array directly which would look something like this:

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

1. program test;
2. {$mode delphi}
3. Type
4.   TMyRange = 0..29;
5.   TMySet = set of TMyRange;
6. var
7.   S:TMySet;
8.   R:TMyRange;
9.   A:array[TMyRange] of integer;
10. begin
11.   S:=[0,2,5,9];
12.   For R in S do
13.   begin
14.     A[R] := R; // just to have some value here...
15.     writeln(A[R]);
16.   end;
17. end.

As you can see the array elements are now restricted/filtered to the members of the set.
This is typical Pascal and much cleaner and should be faster than all those repeat/until's 

[Mr.Madguy]

Have you tried RLE? It can be much faster for filters like this 000001111100000.

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

1. unit Unit1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. interface
6.  
7. uses
8.   Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
9.  
10. type
11.  
12.   { TForm1 }
13.  
14.   TForm1 = class(TForm)
15.     Memo1: TMemo;
16.     procedure FormCreate(Sender: TObject);
17.   private
18.     { private declarations }
19.   public
20.     { public declarations }
21.   end;
22.  
23. var
24.   Form1: TForm1;
25.  
26. implementation
27.  
28. {$R *.lfm}
29.  
30. type
31.   TMyArray = array of Double;
32.   TRLEElement = ShortInt;//Should be enough for 30 elements
33.   TRLEArray = array of TRLEElement;
34.  
35. function FilterArray(AArray:TMyArray;AFilter:TRLEArray):TMyArray;
36.   var I, J, K, Count:Integer;
37. begin
38.   I := 0;
39.   J := 0;
40.   K := 0;
41.   SetLength(Result, Length(AArray));
42.   while (I < Length(AArray)) and (J < Length(AFilter)) do begin
43.     Count := AFilter[J];
44.     if Count < 0 then begin
45.       Count := -Count;
46.       Move(AArray[I], Result[K], Count * SizeOf(AArray[I]));
47.       Inc(K, Count);
48.     end;
49.     Inc(I, Count);
50.     Inc(J);
51.   end;
52.   SetLength(Result, K);
53. end;
54.  
55. { TForm1 }
56.  
57. procedure TForm1.FormCreate(Sender: TObject);
58.   var Source, Dest:TMyArray;
59.   Filter:TRLEArray;
60.   I:Integer;
61.   S:String;
62. begin
63.   SetLength(Source, 30);
64.   S := '';
65.   for I := 0 to Length(Source) - 1 do begin
66.     Source[I] := I + 1;
67.     if I <> 0 then S := S + ', ';
68.     S := S + FloatToStr(Source[I]);
69.   end;
70.   Memo1.Lines.Add(S);
71.   SetLength(Filter, 3);
72.   Filter[0] := -10;
73.   Filter[1] := 10;
74.   Filter[2] := -10;
75.   Dest := FilterArray(Source, Filter);
76.   S := '';
77.   for I := 0 to Length(Dest) - 1 do begin
78.     if I <> 0 then S := S + ', ';
79.     S := S + FloatToStr(Dest[I]);
80.   end;
81.   Memo1.Lines.Add(S);
82. end;
83.  
84. end.
85.  

[Thaddy]

It is actually slower than my pure set code:
You iterate once over all elements to test for conditions and include set elements, but the filter is set in one go and you can subsequently use for in do.
That's how sets work. Sets are close to optimal for such filters.

[Mr.Madguy]

It is actually slower than my pure set code:
You iterate once over all elements to test for conditions and include set elements, but the filter is set in one go and you can subsequently use for in do.
That's how sets work. Sets are close to optimal for such filters.

Your code actually iterates through all elements too.

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

1. type
2.   TValues = 0..29;
3.   TSet = set of TValues;
4.  
5.   var R:TValues;S:TSet;
6. begin
7.   S := [1, 3, 5];
8.   for R in S do begin
9.     ShowMessage(IntToStr(R));
10.   end;
11.  

[Thaddy]

Well, the compiler generates at least close to optimal code... Actually impressive...Much better than the alternatives here...Check that!

[Mr.Madguy]

Well, the compiler generates at least close to optimal code... Actually impressive...Much better than the alternatives here...Check that!

Not really. LEA ESI, [ESI + 0] - is dummy instruction. Using BL and copying data to EAX instead of using whole EBX - is waste of time.

What I wanted to say, is that your code is actually 100% equivalent to OP's F2 routine.

[Thaddy]

Although algorithmically the same (indeed) the compiler generates much better code for my example. Check that! I know the compiler can be improved upon, but not by much.
I can't test X86 atm, but I ran some tests against armhf.

[Mr.Madguy]

Although algorithmically the same (indeed) the compiler generates much better code for my example. Check that! I know the compiler can be improved upon, but not by much.
I can't test X86 atm, but I ran some tests against armhf.

Yeah, only difference - his code uses memory to store local variable. Yeah, registers should be faster, but difference isn't so big on modern computers. But that's because Lazarus still haven't learned, how to store local variables in registers, if possible. And I'm not sure, if compiler would be able to do it, if code would be more complex. I guess, this happens, cuz variable is used in some another operator inside loop, so compiler decides to store it in memory. If your code would also have some calculations with variable R - I guess compiler would put it to memory too.

P.S. It's Debug mode. I've tried to compile in Release one - no difference in both cases.

[Thaddy]

Note there is a bug in the original code by OP anyway (off by one index: 0..29 vs 1..30)
After I ran all code through -a and examined the assembler output I found that indeed clean set use is fastest, as I expected. Even if it iterates internally like Mr.MadGuy explained.
Also note that copying like above is only beneficial over simple assignments when large chunks can be copied at once. If there are too many skips, it becomes less efficient.