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

Question

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

---

* 1009.* Вот игрушечный пример:

Создайте некоторые данные:

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[Flatten@Position[corr, patt.patt], 
             digits[[# ;; # + Length[patt] - 1]] === patt &]
        ]

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

---

Сводка:

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

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

---

Смежные вопросы:

• Быстрое внедрение в Mathematica для Position2D (2D случай того же самого)
• Каков наилучший способ найти период (повторяющегося) списка в Mathematica?

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

• Алгоритм поиска строки Бойера-Мура

---

РЕДАКТИРОВАТЬ:

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

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

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

Answer 1

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

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

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

Edit : полагает, что использовать правило с задержкой несколько элегантнеена карту Length впоследствии.

Answer 2

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

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

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[Flatten@Position[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 намного быстрее.

Answer 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]]