Найти Same шаблоны в списках

Question

Предположим, что мы имеем ниже списков:

List<int> Journey1 = new List<int>() { 1, 2, 3, 4, 5 }; 
    List<int> Journey2 = new List<int>() { 2, 3, 4, 6, 7, 3, 4 }; 
    List<int> Journey3 = new List<int>() { 6, 7, 1 }; 
    List<int> Journey4 = new List<int>() { 3, 1, 4 }; 

И узоры:

2, 3, 4 -> Journey1, Journey2; 
6, 7 -> Journey2, Journey3; 
1  -> Journey2, Journey3, Journey4; 
5  -> Journey1; 
3, 4 -> Journey2; 
3  -> Journey4; 
4  -> Journey4; 

Мы имеем 5000 списков, и каждый из них имеет около 200 пунктов, так что образцы могут иметь между 1-200 элементами и можно увидеть в списках 1-5000.

Поэтому мне нужен очень быстрый способ сопоставления рисунка.

Answer 1

Без предвычисления и с наивным поиска на лету:

var matchedJourneys = journeys.Where(x => ContainsPattern(x, mypattern)); 

bool ContainsPattern(List<int> list, List<int> pattern) 
{ 
    for(int i = 0; i < list.Count - (pattern.Count - 1); i++) 
    { 
     var match = true; 
     for(int j = 0; j < pattern.Count; j++) 
      if(list[i + j] != pattern[j]) 
        { 
         match = false; 
         break; 
        } 
     if(match) return true; 
    } 
    return false; 
} 

Это будет выполняться при макс 200 млн равно проверяет для ваших «чисел». Но так как проверки не будут выполняться для целых паттернов, это может быть (просто догадка) ~ 5 миллионов равнодействует операциям при проверке всех списков. Это несколько сотен миллисекунд.

Все зависит от того, что для вас очень «очень быстро». Если это слишком медленно, вам понадобится гораздо более сложный подход ...

Answer 2

Я не уверен, что вы хотите в качестве вывода. Я просто попробовал.

Я предлагаю вам составить список списков, вместо объявления отдельных переменных списка.

List<List<int>> journeys = new List<List<int>>(); 
journeys.Add(new List<int>() { 1, 2, 3, 4, 5 }); 
journeys.Add(new List<int>() { 2, 3, 4, 6, 7, 3, 4 }); 
journeys.Add(new List<int>() { 6, 7, 1 }); 
journeys.Add(new List<int>() { 3, 1, 4 }); 

Я предположил, что число в диапазоне от 0 до 255. При этом запросе

var result = Enumerable.Range(0, 256) 
    .Select(number => new 
    { 
     number, 
     listIndexes = journeys 
      .Select((list, index) => new { index, list }) 
      .Where(a => a.list.Contains(number)) 
      .Select(a => a.index) 
      .ToList() 
    }) 
    .Where(b => b.listIndexes.Count > 0) 
    .ToList(); 

и этого цикла испытаний

foreach (var item in result) { 
    Console.Write("Number {0} occurs in list # ", item.number); 
    foreach (var index in item.listIndexes) { 
     Console.Write("{0} ", index); 
    } 
    Console.WriteLine(); 
} 

вы получите этот результат

 
    Number 1 occurs in list # 0 2 3 
    Number 2 occurs in list # 0 1 
    Number 3 occurs in list # 0 1 3 
    Number 4 occurs in list # 0 1 3 
    Number 5 occurs in list # 0 
    Number 6 occurs in list # 1 2 
    Number 7 occurs in list # 1 2 

Где пронумерованы списки начиная с нуля.

Answer 3

Для подбора грубой силы вы можете попытаться использовать polynomial hash-functions для ускорения совпадений подсекций. Требуется еще безумное количество сравнений, но по крайней мере совпадение может быть почти постоянным независимо от длины подпоследовательности.

Answer 4

В вашем случае есть возможность воспользоваться препроцессором шаблонов, а также препроцессором текста (http://en.wikipedia.org/wiki/String_searching_algorithm).

Например, построение trie для всех подпоследовательностей в списке позволит запросить этот список для заданного шаблона во времени, пропорциональном длине шаблона.