Здравствуйте, scale_tone, Вы писали:
_>И да, известно, что Enumerable.Any() медленнее foreach(), т.к., видимо, почему-то не делает break при нахождении первого совпадения.
ЩИТО?
public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
if (source == null)
{
throw Error.ArgumentNull("source");
}
if (predicate == null)
{
throw Error.ArgumentNull("predicate");
}
foreach (TSource current in source)
{
if (predicate(current))
{
return true;
}
}
return false;
}
Делает он бряку
А медленнее он потому что работает с IEnumerable<T> и лямбдой (и то и другое — накладные расходы). В случае, если source — это массив, то foreach будет еще быстрее так как разворачивается в for.
Здравствуйте, debugx, Вы писали:
D>Подскажите, как соптимизировать это дело?
Если смотреть на микро-оптимизации, то во-первых, первый foreach можно переписать на передачу arr1 в конструктор hashset-а, во-вторых, переписать второй if с linq-ом на простой foreach, вызов дерегата все-таки не бесплатная операция.
Если подходить по-серьезному, то надо не этот участок разгонять, а смотреть, нельзя ли уменьшить число его вызовов.
Здравствуйте, debugx, Вы писали:
D>Подскажите, как соптимизировать это дело?
Уже правильно предложили отсортировать массивы (собственно, самое очевидное). Я бы предложил вместо этого превратить arr1 и arr2 в сортированные массивы хэш-кодов строк и уже их сравнивать.
И да, известно, что Enumerable.Any() медленнее foreach(), т.к., видимо, почему-то не делает break при нахождении первого совпадения.
Здравствуйте, debugx, Вы писали:
D>После продолжительных экспериментов, лучше всех себя показал вариант:
D>
D>var uniqueWords = new List<string>(8);
D>for (int i = 0; i < arr1.Count; i++) {
D> uniqueWords.Add(arr1[i]);
D>}
D>for (int i = 0; i < arr2.Count; i++) {
D> if (!uniqueWords.Contains(arr2[i])) {
D> return;
D> }
D>}
D>
D>в этом варианте на миллионе вызовов мы незначительно проигрываем хешсету на функции Contains, порядка 1 sec. Понятно, что это только по той причине, что элементов в массиве очень мало. Если бы их там было 1000+, то на Contains терялось бы гораздо больше. D>Но зато по сравнению с хешсетом хорошо экономим на функции Add, порядка 15 sec.
Да, по сути это как раз и получилось "полное попарное сравнение элементов двух массивов без их сортировки (7*7=49 сравнений)".
Поэтому можно даже не создавать дополнительный список, а напрямую написать двойной цикл по массивам arr1, arr2 — асимптотическая сложность O(N^2)от этого не изменится, а накладные расходы будут чуть поменьше.
Кстати, немного смущает логика проверки во втором цикле: "как только мы нашли слово, которого нет в uniqueWords, то сразу выходим из метода". Это точно то, что задумывалось?
Всем привет,
Подскажите алгоритм.
Есть два массива строк. Нужно определить пересекаются ли множества элементов этих массивов, т.е. есть ли в первом массиве хотя бы один элемент, который присутствует также во втором.
Дополнительные условия: оба массива короткие, примерно по семь элементов. Вызов этого алгоритма происходит порядка 10 млн раз.
Сейчас сделал так:
var uniqueWords = new HashSet<string>();
foreach (var word in arr1) {
uniqueWords.Add(word);
}
if (arr2.Any(word=> !uniqueWords.Add(word))) {
return true;
}
return false;
Вот что говорит профайлер:
System.Collections.Generic.HashSet`1.AddIfNotPresent(T) — 19 sec — 15 113 490 calls
System.Linq.Enumerable.Any(IEnumerable[TSource], Func[TSourceBoolean]) — 14 sec — 1 971 170 calls
Здравствуйте, debugx, Вы писали:
D>Дополнительные условия: оба массива короткие, примерно по семь элементов. Вызов этого алгоритма происходит порядка 10 млн раз.
В данном случае, когда размеры массивов не превышают десятка элементов, многое будет определяться накладными расходами, и могут "выстрелить" даже самые примитивные методы, вплоть до полного попарного сравнения элементов двух массивов без их сортировки (7*7=49 сравнений).
Но, в любом случае, будет неплохо работать следующий велосипедный алгоритм:
1) сортируем массивы arr1, arr2
2) заводим два указателя-позиции в массивах и за ОДИН проход, поочерёдно продвигая указатели, выявляем факт наличия хотя бы одной совпадающей строки.
Здравствуйте, hardcase, Вы писали:
H>Делает он бряку H>А медленнее он потому что работает с IEnumerable<T> и лямбдой (и то и другое — накладные расходы). В случае, если source — это массив, то foreach будет еще быстрее так как разворачивается в for.
Ну согласен, про пробегание всего массива я только предположил, когда как-то сам на это наткнулся. В код не смотрел.
Re: Алгоритм пересечения двух множеств
От:
Аноним
Дата:
18.01.12 11:49
Оценка:
У HashSet<string> есть функция void IntersectWith(IEnumerable<string> other), которая прорежает HashSet до пересечения c передаваемым массивом/HashSet'ом/коллекцией other
Впрочем, да, по зрелому размышлению: не стоит ни строки сортировать, ни хэш-коды строк. С HashSet-ом по-любому должно быть быстрее — это ж и есть сортированный массив хэш-кодов, но еще и с доступом O(1).
Здравствуйте, debugx, Вы писали:
D>Подскажите, как соптимизировать это дело?
После продолжительных экспериментов, лучше всех себя показал вариант:
var uniqueWords = new List<string>(8);
for (int i = 0; i < arr1.Count; i++) {
uniqueWords.Add(arr1[i]);
}
for (int i = 0; i < arr2.Count; i++) {
if (!uniqueWords.Contains(arr2[i])) {
return;
}
}
в этом варианте на миллионе вызовов мы незначительно проигрываем хешсету на функции Contains, порядка 1 sec. Понятно, что это только по той причине, что элементов в массиве очень мало. Если бы их там было 1000+, то на Contains терялось бы гораздо больше.
Но зато по сравнению с хешсетом хорошо экономим на функции Add, порядка 15 sec.
Здравствуйте, andy1618, Вы писали:
A>Да, по сути это как раз и получилось "полное попарное сравнение элементов двух массивов без их сортировки (7*7=49 сравнений)". A>Поэтому можно даже не создавать дополнительный список, а напрямую написать двойной цикл по массивам arr1, arr2 — асимптотическая сложность O(N^2)от этого не изменится, а накладные расходы будут чуть поменьше.
Я упрощенный код привел. В arr1, arr2 объекты лежат, сравнивать надо не все, а только с определенным флагом.
A>Кстати, немного смущает логика проверки во втором цикле: "как только мы нашли слово, которого нет в uniqueWords, то сразу выходим из метода". Это точно то, что задумывалось?
))) интересно, если бы вы не подсказали, я бы это заметил когда-нибудь. ни факт
Раньше там было !Add(), где add функция хешсета. После замены на Contains, конечно ! надо убрать )
Здравствуйте, debugx, Вы писали:
A>>Кстати, немного смущает логика проверки во втором цикле: "как только мы нашли слово, которого нет в uniqueWords, то сразу выходим из метода". Это точно то, что задумывалось?
D>))) интересно, если бы вы не подсказали, я бы это заметил когда-нибудь. ни факт
Кстати, чтобы своевременно отлавливать подобные досадные баги, очень полезно пяток простеньких юнит-тестов написать (непересекающиеся массивы, полностью пересекающиеся, пустые, с дублирующимися элементами).
