Вопросы Теги

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

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

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

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

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} , хотя последние может вызвать сложности.)

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

Связанные вопросы:

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

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

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

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

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

12
задан Community 23 May 2017 в 12:24
поделиться