Удаление элемента списка из другого списка

Question

У меня есть список с некоторыми элементами, и я хочу удалить элементы из другого списка. Элемент должен быть удален, если его значение Contain s (не равно) значению из другого списка.

Один из способов сделать это:

var MyList = new List<string> { ... }
var ToRemove = new List<string> { ... }
MyList.RemoveAll(_ => ToRemove.Any(_.Contains));

Это работает ...

, но у меня есть LOT списков (> 1 миллиона), и, поскольку ToRemove можно сортировать, имеет смысл использовать его для того, чтобыускорить процесс.

Легко сделать цикл, который делает это, но есть ли способ сделать это с отсортированными коллекциями?

---

Обновление:

На 20 000 итераций текста с нашим запрещенным списком я получаю следующее:

Запрещенный список в виде списка -> 00: 00: 07.1993364

Запрещенный список в виде HashSet -> 00:00: 07.9749997

Это согласованно после нескольких запусков, поэтому хэш-сет медленнее

Answer 1

Поскольку это удаление строк, содержащих строки из другого списка, HashSet не сильно поможет.На самом деле не так много было бы, если бы вы не искали точные полные совпадения или не поддерживали индекс всех подстрок (дорогой и только AFIK, SQL Server делает это полуэффективно за пределами области BigData).Если все, о чем вы заботились, было ли это начинаться с элементов в «ToRemove», сортировка могла бы помочь.Сортируйте строку «MyList» и foreach в пользовательском двоичном поиске «ToRemove», чтобы найти любую строку, начинающуюся с этой строки и индекса RemoveAt, пока не начинается с, затем уменьшите индекс в обратном направлении, удаляя до тех пор, пока не начнется с.

Answer 2

Ну, сортировка ToRemove может быть полезна из-за сложности двоичного поиска O(log n) (вам нужно будет переписать _ => ToRemove.Any(_.Contains)).

Но вместо этого использование HashSet<string> вместо List<string> для ToRemove будет намного быстрее, поскольку поиск элемента в хэш-наборе (с использованием Contains) - это операция O(1).

Кроме того, использование LinkedList<string> для MyList может быть полезным, поскольку удаление элемента из связанного списка обычно происходит быстрее, чем удаление из списка на основе массива из-за изменения размера массива.