10
$\begingroup$

I have a database for example datatest (Length[datatest]=10) :

datatest={
{52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2}, 
{1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1}, 
{2, 6, 4, 3, 8, 4, 2, 9, 4, 6, 5}, 
{0, 0, 0, 0, 1, 2, 2, 3, 2, 0, 83},
{1, 6, 4, 6, 2, 12, 4, 8, 2, 12, 5}, 
{1, 1, 2, 2, 3, 3, 4, 41, 11, 12, 1}, 
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
{15, 22, 40, 43, 49, 52, 58, 14, 120, 150, 305}, 
{32, 38, 46, 54, 64, 76, 89, 104, 122, 585, 760}
}

Now I have a list for instance: checklist={40, 43, 49, 52}

If I want to know whether the checklist is in the datatest, the easy way to do is as following:

For[iii= 1, iii<= Length[datatest], iii++, 

    exist = SequenceCount[datatest[[iii]], checklist];

    If[exist!=0,
       ... (*here i ignore the code, just for dealing with the data*)

       Break[],
       ... (*here i ignore the code, just for dealing with the data*)
    ];
];

I will search datatest many time, so when the datatest is very large (Length[datatest] is large), it will take a lot of time with the above for-loop method . So I wonder whether there is a fast way to do such thing?

I think the question can be written as How to check whether a sublist exist in a large nested lists in a fast way?

Thank you very much!

$\endgroup$
  • $\begingroup$ It would be useful to know how large is very large. The solutions would be very different for 1000, 10^6, and 10^9 items. $\endgroup$ – Eriks Klotins Aug 26 at 9:37
  • $\begingroup$ Also, whether you have to perform this task once or frequently? $\endgroup$ – Eriks Klotins Aug 26 at 9:48
  • $\begingroup$ I have to perform this task very frequently@EriksKlotins $\endgroup$ – Xuemei Gu Aug 26 at 12:37
8
$\begingroup$

Being intrigued by the question I did some measurements. Below are some benchmarks showing the most performant solution. All tests are done on Macbook Pro i9, 3.2 GHz, 32 Gb Ram.

First, the test data, a list of 10^6 sublists varying between 0 and 100 in lenght:

datatest = Table[Table[RandomInteger[10], {j, RandomInteger[{0, 100}]}], {i, 1000000}];
checklist = {38, 3, 32, 24, 58, 8};

The author's own solution: 21.6039 seconds

Timing[
 For[iii = 1, iii <= Length[datatest], iii++, 
  exist = SequenceCount[datatest[[iii]], checklist];
  If[exist != 0,
   Print["Found it", iii];
   Break[]
   ]
  ]
 ]

Optimizing for loop with Map: 19.9 seconds

Timing[
 Map[SequenceCount[#, checklist]  &, datatest] // Tally
 ]

Solution by @C. E. 0.263156 seconds (impressive gains)

Timing[
 Cases[datatest, {___, Sequence @@ checklist, ___}]
 ]

Solution by @sakra, 0.216559 seconds (The best so far)

Timing[SequencePosition[Flatten@datatest, checklist] // 
   Quotient[(# - 1), Last@Dimensions@datatest] & // 
  AnyTrue[Apply[SameQ]]]
$\endgroup$
  • $\begingroup$ Rather than referring to answers solely by the user’s name (users can change their display names, so those may not always be accurate), it would be best to link to their answer. You can get a link for a particular answer by clicking the “share” link next to “edit” and “flag” on the bottom-left of the answer. That way it will always be clear which answer you’re referring to. $\endgroup$ – KRyan Aug 27 at 1:38
  • $\begingroup$ On my computer, I see a much smaller difference. 1.586616 versus 1.57901. But note that OP revealed in a comment to my answer that he's only interested in the first matching list, which means that FirstCase can be used and if the sequence is present then it can be much faster than Sakra's solution depending on how early the matching sequence is encountered. $\endgroup$ – C. E. Aug 27 at 4:28
12
$\begingroup$

Cases is pretty fast. Consider the case where you have 10,000 lists, each with 100 numbers. Cases can find all lists with the given subsequence in less than 0.05 seconds:

SeedRandom[100]
data = RandomInteger[{0, 100}, {10000, 100}];
checklist = {29, 49, 25, 53, 57, 25, 86};

Cases[data, {___, Sequence @@ checklist, ___}] // RepeatedTiming

{0.049, {{44, 38, 64, 92, 40, 83, 82, ... }}

If you are only looking for the first instance of such a list, then FirstCase can be used. If you are only looking for the positions, then Position can be used, and similarly, FirstPosition can be used if you only need the first sequence that can be found.

In case you need both the position and the list, use this:

pos = FirstPosition[data, {___, Sequence @@ checklist, ___}];
list = Extract[data, pos];
$\endgroup$
  • $\begingroup$ Cool, Thank you very much! In addition, the Cases[data, {___, Sequence @@ checklist, ___}] gives the list you find and is it possible to give the first position at the same time? Use FirstPosition? $\endgroup$ – Xuemei Gu Aug 25 at 16:07
  • $\begingroup$ @XuemeiGu I added an example of how to find the position of the first list and the list itself. $\endgroup$ – C. E. Aug 25 at 16:09
  • $\begingroup$ Thank you very much! nice solution! $\endgroup$ – Xuemei Gu Aug 25 at 16:18
10
$\begingroup$

Instead of using SequenceCount in a loop, locate all possible matches of the checklist with SequencePosition in the flattened dataset in one go:

exist = SequencePosition[Flatten@datatest, checklist] // 
    Quotient[(# - 1), Last@Dimensions@datatest] & // 
    AnyTrue[Apply[SameQ]]

Because a false match may occur in the flattened dataset, we only consider matches where the beginning index and the end index of the match lie in the same row.

The Quotient ... expression computes the row index from the position index for the beginning and the end of each match. The AnyTrue ... then checks for the presence of a genuine match.

$\endgroup$
  • $\begingroup$ Could you please explain the expression in more detail. What exactly is going on there? $\endgroup$ – Eriks Klotins Aug 26 at 20:55

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.