LINQ может использовать двоичный поиск, когда набор заказан?
Я не парень.NET, но, не можете Вы использовать:
HttpUtility.UrlEncode Method (String)
, Который описан здесь:
4 ответа
Насколько я знаю, встроенными методами это невозможно. Однако было бы относительно легко написать метод расширения, который позволил бы вам написать что-то вроде этого:
var item = myCollection.BinarySearch(i => i.Id, 42);
(при условии, конечно, что ваша коллекция реализует IList; нет способа выполнить двоичный поиск, если вы не можете получить доступ элементы случайным образом)
Вот пример реализации:
public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
where TKey : IComparable<TKey>
{
if (list.Count == 0)
throw new InvalidOperationException("Item not found");
int min = 0;
int max = list.Count;
while (min < max)
{
int mid = min + ((max - min) / 2);
T midItem = list[mid];
TKey midKey = keySelector(midItem);
int comp = midKey.CompareTo(key);
if (comp < 0)
{
min = mid + 1;
}
else if (comp > 0)
{
max = mid - 1;
}
else
{
return midItem;
}
}
if (min == max &&
min < list.Count &&
keySelector(list[min]).CompareTo(key) == 0)
{
return list[min];
}
throw new InvalidOperationException("Item not found");
}
(не тестировалось ... может потребоваться несколько корректировок) Теперь протестировано и исправлено;)
Тот факт, что он выдает исключение InvalidOperationException может показаться странным, но это то, что делает Enumerable.First , когда нет подходящего элемента.
Enumerable.First (предикат) работает с IEnumarable , который поддерживает только перечисление, поэтому у него нет произвольного доступа к элементам внутри.
Кроме того, ваш предикат содержит произвольный код, который в конечном итоге приводит к истинному или ложному результату, и поэтому не может указать, был ли проверенный элемент слишком низким или слишком высоким. Эта информация потребуется для выполнения бинарного поиска.
Enumerable.First (predicate) может проверять каждый элемент только по порядку, когда он проходит через перечисление.
Имейте в виду, что все (? По крайней мере, большинство) методов расширения, используемых LINQ, реализованы в IQueryable или IEnumerable или IOrderedEnumerable или IOrderedQueryable .
Ни один из этих интерфейсов не поддерживает произвольный доступ, и поэтому ни один из них не может использоваться для двоичного поиска. Одним из преимуществ чего-то вроде LINQ является то, что вы можете работать с большими наборами данных без необходимости возвращать весь набор данных из базы данных. Очевидно, что вы не можете выполнять бинарный поиск чего-либо, если у вас еще нет всех данных.
Но, как говорили другие, нет никаких причин, по которым вы не можете написать этот метод расширения для IList < T> или другие типы коллекций, поддерживающие произвольный доступ.
Ну, вы можете написать свой собственный метод расширения для ObservableCollection - но тогда он будет использоваться для любого ObservableCollection , где доступен ваш метод расширения, не зная, отсортирован он или нет.
Вам также нужно будет указать в предикате, что вы хотите найти - что было бы лучше сделать с деревом выражений ... но это было бы больно разбирать. По сути, подпись First не совсем подходит для бинарного поиска.
Я предлагаю вам не пытаться перегрузить существующие подписи, а написать новую, например
public static TElement BinarySearch<TElement, TKey>
(this IList<TElement> collection, Func<TElement, TItem> keySelector,
TKey key)
(Я не собираюсь реализовывать это прямо сейчас, но я могу сделать это позже, если хотите.)
Предоставляя функцию,