В данный момент у меня есть list 1million integers, и я проверяю каждый integer на черный список из 2000 integer s. Это занимает около 2 минут.
for(int i = 0; i< MillionIntegerList.Length ; i++)
{
for(int blacklisted = 0; blacklisted < TwoThousandIntegerList.Length ; blacklisted++)
if(i==blacklisted)
i = 0; //Zero is a sentinel value
}
Это всего 2 000 000 000 итераций (циклов). Есть ли лучший способ, которым я не вижу? спасибо
Теперь три варианта - первые два являются более общими, поскольку они не полагаются на MillionIntegerList, который сортируется (который изначально не был указан). Третий предпочтительнее в случае, когда большой список уже отсортирован.
Вариант 1
Да, там определенно лучший способ сделать это, используя LINQ:
var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();
Это будет внутренне использовать HashSet<int>, построенный с помощью TwoThousandIntegerList, а затем просмотреть каждый элемент MillionIntegerList внутри него - это будет намного более эффективно, чем каждый раз в течение TwoThousandIntegerList.
Если вам нужны только не черные списки, вам нужно:
var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();
Обратите внимание, что если вам нужно только один раз перебирать результаты, вы должны удалить вызов ToList - я включил его для материализации результатов, чтобы их можно было исследовать несколько раз дешевле. Если вы просто повторяете, возвращаемое значение Intersect или Except будет просто передавать результаты, что делает его намного дешевле с точки зрения использования памяти.
Вариант 2
Если вы не хотите полагаться на детали реализации LINQ to Objects, но вы все же хотите использовать хэш-подход:
var hashSet = new HashSet<int>(TwoThousandIntegerList);
hashSet.IntersectWith(MillionIntegerList);
// Now use hashSet
Вариант 3
Подход к использованию того факта, что сортировка большого списка определенно будет полезной.
Предполагая, что вы не против сначала сортировать список с черным списком, вы можете написать реализацию потоковой (и общей цели), подобную этой (непроверенной):
// Note: to use this, you'd need to make sure that *both* sequences are sorted.
// You could either sort TwoThousandIntegerList in place, or use LINQ OrderBy
// method.
public IEnumerable<T> SortedIntersect<T>(this IEnumerable<T> first,
IEnumerable<T> second) where T : IComparable<T>
{
using (var firstIterator = first.GetEnumerator())
{
if (!firstIterator.MoveNext())
{
yield break;
}
using (var secondIterator = second.GetEnumerator())
{
if (!secondIterator.MoveNext())
{
yield break;
}
T firstValue = firstIterator.Current;
T secondValue = secondIterator.Current;
while (true)
{
int comparison = firstValue.CompareTo(secondValue);
if (comparison == 0) // firstValue == secondValue
{
yield return firstValue;
}
else if (comparison < 0) // firstValue < secondValue
{
if (!firstIterator.MoveNext())
{
yield break;
}
firstValue = firstIterator.Current;
}
else // firstValue > secondValue
{
if (!secondIterator.MoveNext())
{
yield break;
}
secondValue = secondIterator.Current;
}
}
}
}
}
(Вы можете взять IComparer<T>, если хотите, вместо того, чтобы полагаться на сопоставимость T.)
Поскольку большой список сортируется. Вы можете получить наилучшие результаты, отсортировав небольшой список (очень быстро), а затем выполнив линейное слияние. Вам нужно будет только просмотреть каждый элемент в большом (и маленьком) списке один раз, и в фоновом режиме не будет необходимости создавать Hashtable.
Обратитесь к функции слияния части MergeSort за идею о том, как это сделать.
Что вам нужно, это Enumerable.Except Method (IEnumerable, IEnumerable), на мой взгляд
Для вашего подхода требуется время O (n * n). Рассмотрим эти оптимизации:
1)
Если ваши целые числа не слишком велики, вы можете использовать массив bool (например, если наибольшее возможное целое число равно 1000000, используйте bool [] b = new bool [1000000]). Теперь, чтобы добавить число K в черный список, используйте b [K] = true. Проверка тривиальна. Это работает в O (n). Вы также можете использовать BitArray
2)
Целые числа могут быть достаточно большими. Используйте двоичное дерево поиска для хранения черного списка (например, SortedSet). он имеет значение O (logN) вставки и извлечения. Таким образом, во всем это O (N * logN). Синтаксис такой же, как для List (Add (int K), Contains (int K)), дубликаты игнорируются
Используйте список HashSet для заблокированных.
foreach(integer i in MillionIntegerList)
{
//check if blockedlist contains i
//do what ever you like.
}
Я думаю, лучшее решение - использовать Bloom filter, и в случае, если фильтр Bloom говорит, что элемент может находиться в черном списке, просто проверьте if не является ложным положительным (что может быть сделано в O (Log (n)), если черный список отсортирован). Это решение является эффективным по времени и не использует практически никакого дополнительного пространства, что делает его намного лучше, чем использование hashset.
Это решение, которое Google использует для черного списка в Chrome.
Как сделать бинарный поиск в более длинном списке, так как он отсортирован.
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer i = MillionIntegerList.binarySearch(blacklisted)
if(i==blacklisted){
//Do your stuff
}
}
Это решение стоит только время O (m log n), где m - размер небольшого списка, а n - размер более длинного списка. Предостережение. Это решение предполагает, что MillionIntegerList не имеет значений дубликатов.
Если это не так, вы можете просто перебирать повторы, поскольку они должны лежать в смежном блоке. Для этого я собираюсь предположить, что MillionInterList - это список записей, каждый из которых имеет value и index.
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer index = MillionIntegerList.binarySearch(blacklisted)
//Find the index of the first occurrence of blacklisted value
while(index > 0 && MillionIntegerList[index - 1].value == blacklisted){
--index;
}
while(MillionIntegerList[index].value == blacklisted){
//Do your stuff
++index;
}
}
Это решение стоит O (m log n + mk), где k - среднее количество дубликатов для черного списка, найденное в MillionInterList.
используйте метод Except для списка. Это будет работать