3
$\begingroup$

Can we find the first position of elements of a list satisfying a condition, with good performance, if the conditions is a tail condition of the list.

What is tail condition ? (the term is informal, personal.) I will explain with an examples.

Ex1) Let L={12,14,16,18,17,15,13} and Cond=OddQ, then Cond is a tail condition of L.
Because, the first odd number seen in the list is the 5-th element 17, any element after 17 is also odd.
For Ex1), Earliest[L,Cond] becomes 5.

Ex2) Let L={12,14,17,18,16,15,13} and Cond=OddQ, then Cond is not a tail condition of L.
Because, the first odd number seen in the list is the 3-th element 17, but there is an element that comes after 17, which is not odd. Like 18 or 16.
For Ex2), Earliest[L,Cond] becomes 6. (At present stage, you can't know why it becomes 6.)
Note that the first odd element is 3-th, not 6-th. But complaining about this is doesn't make sense, because Earliest is designed to work properly only if Cond is a tail condition of L.

Ex3) Let L={12,14,17,18,16,15,13} and Cond=#>10&, then Cond is a tail condition of L. Because every element is bigger then 10.
For Ex3), Earliest[L,Cond] becomes 1.

Ex4) Let L={12,14,17,18,16,15,13} and Cond=#>20&, then Cond is a tail condition of L. Because there is no element bigger then 20.
For Ex4), Earliest[L,Cond] becomes Missing["NotFound"].

$\endgroup$
4
  • $\begingroup$ What about FirstPosition? $\endgroup$
    – rhermans
    Jun 27 at 12:05
  • $\begingroup$ What is your question? This is a Q&A site, so you should split this post in two, resulting in a question that explains the requirements you have for your function, with sample inputs and outputs, and then a self-answer showing your current implementation. $\endgroup$
    – MarcoB
    Jun 27 at 12:08
  • $\begingroup$ @MacroB, I understood. I'll split the post in two, thank you. $\endgroup$
    – imida k
    Jun 27 at 12:55
  • $\begingroup$ If r is the result, a way to do some level of verification after the fact about having a tail condition to begin with would be to run Earliest on part ;;r-1 and on part r;; . The result should be {Missing[Not Found],1}. $\endgroup$ Jun 27 at 21:05

3 Answers 3

3
$\begingroup$

Perhaps you mean binary search. If you plan to compile, see here and here.

earliest[list_,cond_] := Module[{L,R,M},
    L=0;R=Length[list]+1;While[L<R-1,M=Quotient[L+R,2];If[cond[list[[M]]],R=M,L=M];];
    If[R<=Length[list],R,Missing["NotFound"]]];
$\endgroup$
1
  • $\begingroup$ I verified that your earliest behaves correctly just as mine! I intended to avoid computation like addition, Quotient[#,2], for better performance. But come to think of it now, such consideration will not make notable improvement of performance. And your code is much shorter. $\endgroup$
    – imida k
    Jun 27 at 18:21
2
$\begingroup$

I've made a function called Earliest

So what is Earliest function ?

Earliest[a list_, a condition_]:=

It finds the first position of elements of a list satisfying the condition, if the condition is a tail condition of the list.
Earliest has a good performance.

What is tail condition ? (the term is informal, personal.) I will explain with an examples.

Ex1) Let L={12,14,16,18,17,15,13} and Cond=OddQ, then Cond is a tail condition of L.
Because, the first odd number seen in the list is the 5-th element 17, any element after 17 is also odd.
For Ex1), Earliest[L,Cond] becomes 5.

Ex2) Let L={12,14,17,18,16,15,13} and Cond=OddQ, then Cond is not a tail condition of L.
Because, the first odd number seen in the list is the 3-th element 17, but there is an element that comes after 17, which is not odd. Like 18 or 16.
For Ex2), Earliest[L,Cond] becomes 6. (At present stage, you can't know why it becomes 6.)
Note that the first odd element is 3-th, not 6-th. But complaining about this is doesn't make sense, because Earliest is designed to work properly only if Cond is a tail condition of L.

Ex3) Let L={12,14,17,18,16,15,13} and Cond=#>10&, then Cond is a tail condition of L. Because every element is bigger then 10.
For Ex3), Earliest[L,Cond] becomes 1.

Ex4) Let L={12,14,17,18,16,15,13} and Cond=#>20&, then Cond is a tail condition of L. Because there is no element bigger then 20.
For Ex4), Earliest[L,Cond] becomes Missing["NotFound"].

The advantage of Earliest is the speed!
Below is the code for Earliest

Earliest[L_, Cond_] := If[
  Length[L] == 0 || ! Cond[L[[-1]]],
  
  Missing["NotFound"],
  
  Module[{x = {BitLength[Length[L]] - 1}, 
    condi = (# > Length[L] || Cond[L[[#]]] &), final},
   While[x[[-1]] != 0, 
    If[condi[Total[2^x]], (x[[-1]] = x[[-1]] - 1; x), 
     x = Append[x, x[[-1]] - 1]]];
   final = 
    If[condi[Total[2^x]], x, 
     Module[{n = 1}, While[n <= Length[x] && (n - 1 == x[[-n]]), n++];
      Append[x[[;; Length[x] - (n - 1)]], n - 1]]];
   Total[2^final]]
  ]

To test Earliest, I've made a function parrot :

parrot[a_, b_] := (Earliest[Join[ConstantArray[0, a], Prime[Range[b]]], 
    PrimeQ[#] &] == If[b == 0, Missing["NotFound"], a + 1])

Now lets test :

Table[parrot[a, b], {a, 0, 10}, {b, 0, 10}]

You can check that it gives True for all cases.

To compare the performance of Earliest and method using the built-in functions, you can try :

SeedRandom[1000]; tibis = Accumulate[RandomInteger[10, 100000000]];
SelectFirst[tibis, # > 250000000 &] // Timing
Position[tibis, _?(# > 250000000 &), {1}, 1] // Timing
Earliest[tibis, # > 250000000 &] // Timing

Finally, this is a related screenshot :

enter image description here

$\endgroup$
2
$\begingroup$

I am probably confused, but I can't explain the following. Here is a list of 100 integers.

rr = RandomInteger[1000, 100]

(* {235,40,513,519,487,552,7,634,608,527,458,695,70,54,557,665,801,\
205,18,99,235,908,615,268,391,228,124,301,257,743,321,910,415,793,217,\
660,81,81,465,278,192,128,148,1,37,327,836,485,379,988,661,942,142,\
778,704,897,629,777,693,4,474,540,602,584,36,82,979,511,287,312,565,\
65,845,650,448,235,823,323,518,257,463,423,623,608,946,894,823,87,186,\
543,705,482,591,214,892,830,749,848,590,612} *)

If my condition is integer > 500:

Earliest[rr, # > 500 &]

(* 3 *)

It seems to me that the answer should be 95, the position of value 892, if I undertsand what Earliest is supposed to do. For example, the following code returns 95 (it also returns 0 if there is no match).

i = 0; l = Length[rr];
While[i < l, If[rr[[l - i]] > 500, i++; Continue[], Break[]]];
If[i == 0, 0, l - i + 1]
$\endgroup$
3
  • $\begingroup$ The condition # > 500 & is NOT a tail condition of rr. In short, Earliest is meaningless in your example. If rr were any list of monotonic increasing sequence, then # > 500 & would be a tail condition of rr. $\endgroup$
    – imida k
    Jun 27 at 17:24
  • $\begingroup$ I see. So a tail condition exists if the first element matching the condition is the first element of the tail... and Earliest assumes, but does not verify, that the given condition is a tail condition. $\endgroup$ Jun 27 at 17:39
  • $\begingroup$ Yes, use Earliest only when we already know the condition is a tail condition of L $\endgroup$
    – imida k
    Jun 27 at 18:23

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.