1
$\begingroup$

I have the following (long) list (exemplary I will show you only a few elements of it):

  list={a[om1,om2,om3,om4,om5,om6]*F[om1] F[om2] F[om4] F[om5] F[om6],b[om1,om2,om3,om4,om5,om6]*F[om1] F[om2], c[om1,om2,om3,om4,om5,om6]*F[om2],d[om1, om2, om3, om4,om5,om6]}

I want to keep only those elements that are linear in the function F[_] (i.e. the result in the example should be {c[om1,om2,om3,om4,om5,om6]*F[om2]}). So far I did this with Select, sth like

Select[list, 
 MemberQ[#, F[_]] && FreeQ[#, F[_] __F] &]

For a very large list, however, this becomes too slow (can I invoke Assumptions with Select?). Is there another way, to do the same task in a faster way? I was thinking of Series but it doesn't seem to be applicable to expansions in functions.

$\endgroup$
2
$\begingroup$

The question of efficient lookup of terms linear relative expression satisfying a given pattern depends strongly on whether coefficients c[om1,...] themselves can somehow depend on this expression.

If coefficients a, b, c, etc can themselves depend on F, then none of the above solutions can be reliable. For example, the expression Sin[F[om1]] contains exactly one expression matching _F at the first level, so both approaches of Fraccalo and Alexei Boulbitch will return it.

Select[{Sin[F[om1]]}, Count[#, F[_]] == 1 &]
(*Returns {Sin[F[om1]]}*)

ClearAll[count];
count[expr_] := Count[expr, _F, Infinity];
Select[{Sin[F[om1]]}, count[#] == 1 &]
(*Returns {Sin[F[om1]]}*)

In this, the most general case, the only option I see is to use FreeQ:

list={a[om1,om2,om3,om4,om5,om6]*F[om1] F[om2] F[om4] F[om5]    F[om6],b[om1,om2,om3,om4,om5,om6]*F[om1] F[om2],c[om1,om2,om3,om4,om5,om6]*F[om2],d[om1,om2,om3,om4,om5,om6]};
list2=Join@@ConstantArray[list,10000];
RepeatedTiming[
  general=Cases[
    list2,
    (a_/;(FreeQ[a,_F]))*_F
  ]
]//First
(*0.298*)

However, if coefficients themselves cannot depend on F and we just need to figure out how many times F[...] is repeated, then Fraccalo approach is a good option.

RepeatedTiming[
  select = Select[list2, Count[#, F[_]] == 1 &]
] // First
(*0.054*)

But we can improve the result a little bit by exploiting the fact that in this case we are not interested in how many there are F[...] expressions in the terms, what Count computes. We only need to know, whether there is exactly one expression of the form or not. For this reason, we can try the following:

RepeatedTiming[
   pattern = Cases[list2, Repeated[Except[_F], {1}]*_F]
] // First
(*0.0280*)

general === select === pattern
(*True*)

Note, that Except[_F]*_F will not work here because Times is Flat.

$\endgroup$
  • $\begingroup$ Very nice answer! In the most general case that you correctly point out, a slightly more efficient code would probably be: Select[list, FreeQ[1/F*Head /@ #, F] &] On my machine is 1.5x faster (not a big speed up though, but it's nice to see a different approach to the problem) $\endgroup$ – Fraccalo Aug 20 '18 at 12:38
  • 1
    $\begingroup$ Thank you. I doubt that there can be a universal method not involving FreeQ explicitly or effectively just because what such a universal functions does if effectively implementing FreeQ applied to the terms' coefficients. Select[{a Sin[F[om1]] F[om1]}, FreeQ[1/F*Head /@ #, F] &] returns {a F[om1] Sin[F[om1]]}. $\endgroup$ – Anton.Sakovich Aug 20 '18 at 12:49
  • 1
    $\begingroup$ I mean the following. Lets suppose that we have a function f that universally determines whether an expression is linear relative patt pattern. Then f[expr * x, patt], where MatchQ[x, patt]=True, is an effective analog of FreeQ[expr, patt]. $\endgroup$ – Anton.Sakovich Aug 20 '18 at 12:56
  • $\begingroup$ Yes, that makes sense :) $\endgroup$ – Fraccalo Aug 20 '18 at 13:04
1
$\begingroup$

Provided each term always has a coefficient (like a[om1,...], c[om1,...] etc.) and may (or may not) have one or several F factors, try this:

Select[list, Length[#] == 2 &]

(* {c[om1, om2, om3, om4, om5, om6] F[om2]}  *)

Edit: taking into account your comment try also this:

count[expr_] := Count[expr, _F, Infinity]

Select[list, count[#] == 1 &]

   (*  {c[om1, om2, om3, om4, om5, om6] F[om2]} *)

Have fun!

$\endgroup$
  • $\begingroup$ The coefficients in this case are meant to be arbitrary functions/functionals of the given frequencies. Unfortunately, their lengths can differ and are not known a priori. Thank you anyway! $\endgroup$ – Display Name Aug 20 '18 at 9:34
  • $\begingroup$ @Display Name It is not clear. Do you mean that there can be terms without factors, or you mean that the factors like a[om1,...] may in reality represent several terms, or what? Please have in mind to give a realistic, comprehensible c explanation of your problem, otherwise, we only loose time trying to help you. $\endgroup$ – Alexei Boulbitch Aug 20 '18 at 9:39
  • $\begingroup$ I'm sorry. Yes I mean the latter one. a[om1,...] is meant to be a placeholder for several terms. Sorry, this was sloppy in the opening post. $\endgroup$ – Display Name Aug 20 '18 at 9:44
  • $\begingroup$ Have a look at the edit. $\endgroup$ – Alexei Boulbitch Aug 20 '18 at 9:45
  • $\begingroup$ Yes, that's much better than my initial solution. Thank you! $\endgroup$ – Display Name Aug 20 '18 at 10:10
3
$\begingroup$

Replace MemberQ and FreeQ with Count as follows:

list2 = Join @@ ConstantArray[list, 10000];
RepeatedTiming[A=Select[list2, MemberQ[#, F[_]] && FreeQ[#, F[_] __F] &]][[1]]
RepeatedTiming[B = Select[list2, Count[#, F[_]] == 1 &]][[1]]
A == B

0.302

0.063

True

Speed up: 5x (better than nothing :) )

$\endgroup$
  • $\begingroup$ Good idea, thank you. If there is an even better solution, feel free to post it. $\endgroup$ – Display Name Aug 20 '18 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.