Есть ли эквивалент StringPosition [] для поиска списков? Если нет, то какой самый быстрый способ реализовать это?

Есть ли функция, которая ищет последовательность элементов для подпоследовательности? Я ищу аналог StringPosition для List s. В моем текущем приложении я работаю с целыми списками, но меня бы интересовала общая функция FindSequence[list, pattern, n], которая найдет первые n вхождения pattern в List.

Вот пример игрушки:

Сгенерируйте некоторые данные:

In[1]:= $HistoryLength = 0    
Out[1]= 0

In[2]:= Timing[digits = First[RealDigits[\[Pi], 2, 10000000]];]    
Out[2]= {26.5, Null}

Позвольте преобразовать его в строку, чтобы мы могли сравнить с StringPosition. Это очень медленное голодание. (Память освобождается при завершении оценки.)

In[3]:= Timing[str = StringJoin[ToString /@ digits];]    
Out[3]= {43.813, Null}

Я ищу эту подпоследовательность:

In[4]:= patt = {1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 
   1, 0, 1, 1};

In[5]:= strpatt = StringJoin[ToString /@ patt];

Поиск строки очень быстрый:

In[6]:= StringPosition[str, strpatt] // Timing    
Out[6]= {1.047, {{5737922, 5737943}}}

Это простая реализация поиска численных массивов. Это медленнее, чем StringPosition:

In[7]:= Timing[
           corr = ListCorrelate[patt, digits];
           Select[[email protected][corr, patt.patt], 
             digits[[# ;; # + Length[patt] - 1]] === patt &]
        ]

Out[7]= {2.234, {5737922}}

Резюме:

  • Есть ли встроенный список, который ищет списки для подпоследовательностей?
  • Если это не так, что такое быстрая и элегантная реализация для числовых списков (моя практическая проблема)?
  • Как насчет общих списков, которые могут содержать что угодно? (Здесь есть две возможности: "статические" шаблоны, такие как {1,0,1} или общие, такие как {1,_,1}, хотя эти последние могут вносить осложнения.)

Я ожидаю, что у этого будет много решений, некоторые быстрые, некоторые более элегантные, некоторые более общие: -)

Похожие вопросы:

Интересное чтение:

EDIT:

Я только что нашел недокументированный LongestCommonSubsequencePositions. LongestCommonSubsequencePositions[a, b] найдет самую длинную общую подпоследовательность списков a и b и вернет позицию ее первого появления только в a и b. (Документированный LongestCommonSubsequence, о котором я не знал, вернет только подпоследовательность, а не ее позицию.)

Он медленнее, чем альтернативы выше, но он работает с общими списками, которые могут содержать любое выражение.

In[57]:= LongestCommonSubsequencePositions[digits, patt] // Timing
Out[57]= {5.25, {{5737922, 5737943}, {1, 22}}}

Ответы

Ответ 1

Вы можете использовать ReplaceList с "префиксом" и "суффиксом" ___ и соответствовать всему списку. Это дает вам все замены, которые могут быть сделаны (в отличие от Replace). Позиция вашего шаблона - это просто длина префикса + 1. Это довольно быстро:

In[40]:= Timing[ReplaceList[digits, Join[{pre___}, patt, {___}] :> Length[{pre}]
   + 1]]

Out[40]= {1.3059, {5737922}}

Изменить: он немного более изящным, чтобы использовать правило с задержкой, чем потом отображать Length.

Ответ 2

Обратите внимание на функции seqPos (общие списки) и seqposC (целые списки, скомпилированные), которые выполняют именно то, что вы просите, и выполняете быстро. Я использовал их в ответе this (для вопроса, на который вы действительно связаны).

Вот результаты синхронизации для различных решений:

In[15]:= seqPos[digits, patt] // Timing
Out[15]= {1.297, {5737922}}

In[16]:= seqposC[digits, patt] // Timing
Out[16]= {0.125, {5737922}}

In[17]:= 
Timing[corr = ListCorrelate[patt, digits];
      Select[[email protected][corr, patt.patt], 
         digits[[# ;; # + Length[patt] - 1]] === patt &]]

Out[17]= {0.844, {5737922}}

In[18]:= Timing[
    ReplaceList[digits, Join[{pre__}, patt, {___}] :> Length[{pre}] + 1]]

Out[18]= {0.953, {5737922}}

In[19]:= AbsoluteTiming[cf[digits, patt]]
Out[19]= {3.1914063, 5737922}

Это означает, что ваш подход с ListCorrelate неплохой. Моя первая функция seqPos (на самом деле из-за Норберта Позара) немного медленнее, но тогда она полностью общая, а seqposC - намного быстрее.

Ответ 3

Вот скомпилированная версия, которая позволяет избежать преобразования String, но не быстрее.

cf = Compile[{{in, _Integer, 1}, {patt, _Integer, 1}},
  Block[{lp, res},
   lp = Length[patt];
   res = 0;
   Do[
    If[Total[Abs[in[[i ;; i + lp - 1]] - patt]] == 0,
      res = i; Break[]];
    , {i, 1, Length[in] - lp}];
   res
   ]
  , CompilationTarget -> "C", RuntimeOptions -> "Speed"]


AbsoluteTiming[cf[digits, patt]]