Matching into a long list

[ghost]

Suppose I have a very long replacement list, for example O(10^5) entries.

id f(int?,1) = ...
id f(int?,2) = ...
...
id f(int?,100000) = ...

And I have known for each term there is only one f. So in fact once we have found one matched function f the remaining matching should be skipped.

I have tried ifmatch->continue, but does not work.

id ifmatch->continue, f(int?,1) = ...
id ifmatch->continue, f(int?,2) = ...
...
id ifmatch->continue, f(int?,100000) = ...
label continue;

It seems the module will always check all the matching, instead of one by one. Since there is int? in the matching pattern, I do not know how to use tablebase for this mission.

So is there any efficient way to skip the unnecessary matching checks? Thank you.

[tueda]

In your code with ifmatch, FORM has to test pattern matching O(N) times (N=10000, best: O(1), average: O(N/2), worst: O(N)). Instead, you can use tables. For example,

CF f;
S x,n,a;

CTable ftab(1:10000,x?);
Fill ftab(1) = x;
Fill ftab(2) = (3*x^2-1)/2;
Fill ftab(3) = (5*x^3-3*x)/2;
* and other table elements...

L F = f(a,3);
id f(x?,n?) = ftab(n,x);
P;
.end

[ghost]

Thank you so much. We have tried your algorithm. And it works very well.

In your code with ifmatch, FORM has to test pattern matching O(N) times (N=10000, best: O(1), average: O(N/2), worst: O(N)). Instead, you can use tables. For example,

CF f;
S x,n,a;

CTable ftab(1:10000,x?);
Fill ftab(1) = x;
Fill ftab(2) = (3*x^2-1)/2;
Fill ftab(3) = (5*x^3-3*x)/2;
* and other table elements...

L F = f(a,3);
id f(x?,n?) = ftab(n,x);
P;
.end

[tueda]

Nice to hear that works very well.