Быстрый способ извлечения списка на основе другого списка

Question

List1: {"123456", "432978", "321675", …} // containing 100,000 members 

List2: {"7674543897", "1234568897", "8899776644",…} // containing 500,000 members 

Я хочу, чтобы извлечь все элементы в List2, что их первые 6 цифр из членов List1, так вот строка «1234568897» является действительным, поскольку его первые 6 цифр из первого элемента List1. Что это самый быстрый способ сделать это?

foreach(string id in List1) 
    { 
    string result = List2.FirstOrDefault(x => x.Contains(id)); 
    if(result!=null) 
     { 
     //some works here 
     } 
} 

это работает для группы менее 1000, но когда list2 пунктов растет это занимает слишком много времени

Answer 1

Вы можете использовать Enumerable.Join который quite efficient:

var match = from str1 in List1 
      join str2 in List2 
      on str1 equals (str2.Length < 6 ? str2 : str2.Substring(0, 6)) 
      select str2; 

Demo

Редактировать

Поскольку @Oleksandr Pshenychnyy предположил, что это будет очень медленно с такими большими коллекциями, вот демо со 100000 случайными строками в строках list1 и 500000 в списке2 с тем же диапазоном, что и в вопросе. Он выполняет в 600 миллисекунд на ideone:

http://ideone.com/rB6LU4

Answer 2

Это очень сильно зависит от аппаратного обеспечения, вы работаете на. Возможно, вы, возможно, будете заниматься преждевременной оптимизацией. Это может быть достаточно быстро, просто грубо заставляя его. 500 000 * 100 000 - это ваше максимальное количество сравнений (т. Е. Если ничего не соответствует). Это действительно не займет много времени на разумном настольном ПК.

Если вы обнаружили, что это слишком медленно для ваших целей, то есть несколько методов, которые вы можете использовать для повышения производительности:

1. Parallelise его. Это только продемонстрирует большие преимущества для многоядерных аппаратных средств. По сути, вам нужен класс диспетчера, который передает числа из List2 в потоки, которые выполняют поиск соответствия в List1. См. Task Parellel Library.

2. Уменьшить количество сравнения, умясь. Сделайте предварительный анализ своих коллекций, чтобы улучшить их характеристики для этапа сравнения. например поместите элементы из списка1 в список «ведер», где каждое ведро содержит все последовательности с теми же самыми первыми двумя числами. например ведро 1 будет содержать те, которые начинаются «00», ведро 2 «01» и т. д. Когда вы выполняете фактическое сравнение, вам нужно будет сравнить только небольшое количество строк. В вашем примере для «1234568897» мы проверили ведро на «12», и тогда мы знаем, что нам нужно всего лишь выполнить полное сравнение строк со строками в этом ковше.

Этот вид предварительной обработки может фактически замедлить работу, поэтому убедитесь, что вы точно знаете свой код.

Answer 3

Самый эффективный способ реализовать то, что вам нужно, это алгоритм Aho-Corasick - если вам нужно динамически обрабатывать новые элементы List 2. Он основан на prefix-tree, обычно используемой технике в строковых алгоритмах поиска. Этот алгоритм даст вам сложность O (сумма всех строк)

Другой вариант - это Knuth-Morris-Pratt алгоритм, который даст вам такую ​​же сложность, но изначально работает с одной строкой для поиска.

Но если вы в порядке с O((list2.Count*log(list2.Count) + list1.Count*log(list1.Count))*AverageStrLength), я могу предложить свою простую реализацию: Сортировка обоих списков. Затем пройдите по ним одновременно и выберите совпадения.

ОБНОВЛЕНИЕ: Эта реализация прекрасна, если вы уже отсортировали списки. Затем он выполняется примерно через 100 мс. Но сортировка занимает 3,5 секунды, поэтому реализация не так хороша, как я ожидал вначале. Что касается простой реализации, решение Тима работает быстрее.

list1.Sort(); 
list2.Sort(); 
var result = new List<string>(); 
for(int i=0, j=0; i<list1.Count; i++) 
{ 
    var l1Val = list1[i]; 
    for (; j < list2.Count && string.CompareOrdinal(l1Val, list2[j]) > 0; j++) ; 
    for (; j < list2.Count && list2[j].StartsWith(l1Val); j++) 
    { 
     result.Add(list2[j]); 
    } 
} 

Это самая простая эффективная реализация, которую я могу предложить.