C # - сравнить 2 списка с пользовательскими элементами

Question

У меня есть 2 списка.Один содержит поисковый элемент, один содержит данные.Мне нужно зациклить для каждого элемента в list2, который содержит любую строку в list1 ("кошка" или "собака").Например:

List<string> list1 = new List<string>();
list1.Add("Cat");
list1.Add("Dog");
list1.Add... ~1000 items;

List<string> list2 = new List<string>();
list2.Add("Gray Cat");
list2.Add("Black Cat");
list2.Add("Green Duck");
list2.Add("White Horse");
list2.Add("Yellow Dog Tasmania");
list2.Add("White Horse");
list2.Add... ~million items;

Я ожидаю listResult: {"Gray Cat", "Black Cat", "Yellow Dog Tasmania"} (потому что в списке «1» содержится «кошка» и «собака»).Вместо вложенных циклов, у вас есть идея ускорить выполнение последовательности?

Мое текущее решение, как показано ниже.Но ... это кажется слишком медленным:

foreach (string str1 in list1)
{
   foreach (string str2 in list2)
   {
      if str2.Contains(str1)
      {
         listResult.Add(str2);
      }
   }
}

Answer 1

Поскольку вам кажется, что вы хотите сопоставить целые слова, вы можете использовать HashSet для более эффективного поиска и предотвращения повторения list1 и list2 более одного раза.

HashSet<string> species =
    new HashSet<string>(list1);

List<string> result = new List<string>();
foreach (string animal in list2)
{
    if (animal.Split(' ').Any(species.Contains))
        result.Add(animal);
}

ЕслиЯ запускаю это (с list1, содержащим 1000 элементов и list2, содержащим 100 000 элементов) на 4-ядерном ноутбуке:

The algorithm in the question:    37    seconds
The algorithm using AsParallel:    7    seconds
This algorithm:                    0.17 seconds

С 1 миллионом элементов в list2 этот алгоритм занимает около секунды.

---

Теперь, пока этот подход работает, он может давать неверные результаты.Если list1 содержит Лев , то к результатам будет добавлен Морской лев в list2, даже если в list1 его нет.(Если вы используете StringComparer без учета регистра в HashSet, как предложено ниже.)

Чтобы решить эту проблему, вам понадобится какой-то способ разобрать строки в list2 в более сложный объект Animal.Если вы можете контролировать свой ввод, это может быть тривиальной задачей, но в целом это сложно.Если у вас есть какой-то способ сделать это, вы можете использовать решение, подобное следующему:

public class Animal
{
    public string Color { get; set; }
    public string Species { get; set; }
    public string Breed { get; set; }
}

, а затем искать виды в HashSet.

HashSet<string> species = new HashSet<string>
{
    "Cat",
    "Dog",
    // etc.
};

List<Animal> animals = new List<Animal>
{
    new Animal {Color = "Gray", Species = "Cat"},
    new Animal {Color = "Green", Species = "Duck"},
    new Animal {Color = "White", Species = "Horse"},
    new Animal {Color = "Yellow", Species = "Dog", Breed = "Tasmania"}
    // etc.
};

var result = animals.Where(a => species.Contains(a.Species));

---

Обратите внимание, что поиск строки в HashSet чувствителен к регистру, если вы не хотите, чтобы вы могли указать StringComparer в качестве аргумента конструктора:

new HashSet<string>(StringComparer.CurrentCultureIgnoreCase)

Answer 2

Строка списка не является подходящей структурой данных для эффективного решения этой проблемы.

Что вам нужно, так это Trie или Dawg , чтобы отсортировать всеслово из вашего оригинального списка словаря1.

Цель - каждая буква слова из списка 2, у вас будет только проверка 0-26.

С этой структурой данных вместо чтения большого списка слов, пока вы не найдете его, вы будете искать слово, как в бумажном словаре.И это должно быть быстрее.Приложение, которое ищет все слова из языка в тексте, использует этот принцип.

Answer 3

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

Одним из способов сделать это может быть создание обобщенного дерева суффиксов для всех ваших поисковых слов.Затем переберите все элементы в вашем списке2, чтобы увидеть, совпадают ли они.

Тем не менее, это может быть излишним.Сначала вы можете попробовать выполнить несколько простых оптимизаций, предложенных fubo, чтобы проверить, достаточно ли это для вас.

Answer 4

Отличный вариант использования для распараллеливания!

Подход Linq без распараллеливания (равен внутреннему вашему подходу, за исключением того, что внутренний цикл прерывается, если найдено одно совпадение - ваш подход также ищет другие совпадения)

List<string> listResult = list2.Where(x => list1.Any(x.Contains)).ToList();

Распараллеливание цикла с AsParallel() - если у вас многоядерная система, это значительно улучшит производительность.

List<string> listResult = list2.AsParallel().Where(x => list1.Any(x.Contains)).ToList();

Сравнение времени выполнения : (4-ядерная система, list1 1000 элементов, list2 1.000.000 элементов)

Without AsParallel(): 91 seconds
With    AsParallel(): 23 seconds

---

Другой способ с Parallel.ForEach и потокобезопасным списком результатов

System.Collections.Concurrent.ConcurrentBag<string> listResult = new System.Collections.Concurrent.ConcurrentBag<string>();
System.Threading.Tasks.Parallel.ForEach<string>(list2, str2 =>
{
    foreach (string str1 in list1)
    {
        if (str2.Contains(str1))
        {
            listResult.Add(str2);
            //break the loop if one match was found to avoid duplicates and improve performance
            break;
        }
    }
});

---

Примечание: Вы должны перебрать list2 сначала и break; после матча, в противном случае вы добавляете элементы дважды: https://dotnetfiddle.net/VxoRUW