Двоичный поиск по списку на основе свойства типа списка - PullRequest
Новая
       7

Двоичный поиск по списку на основе свойства типа списка

0 голосов
/ 04 октября 2019

У меня есть список T, и этот список предварительно отсортирован на основе некоторого индекса int ID. Я хотел бы посмотреть, есть ли в нем элемент с идентификатором, поэтому бинарный поиск - самый быстрый способ.

Проблема в том, что я не хочу сравнивать на основе T, я хочу сравнивать на основев свойстве ID.

Так как список огромен и находится в некоторой части приложения, чувствительной к производительности, применение какого-либо серьезного преобразования ко всему списку было бы невозможным (например, selectдля obj.ID). Было бы лучше выполнить поиск O(lg n) и преобразовать элементы, поскольку бинарный поиск продолжает выполнять свою работу.

Я попытался заставить лямбду работать, выполнив что-то вроде 

// T = the List<T> type
// I = the type for transforming T -> I (as in I would be `int` in this example)
internal class BinarySearchHelper<T, I> : IComparer<I>
{
    private readonly Func<T, I> _transformer;
    private readonly Func<I, I, int> _comparer;

    public BinarySearchHelper(Func<T, I> transformFunc, Func<I, I, int> comparerFunc)
    {
        _transformer = transformFunc;
        _comparer = comparerFunc;
    }

    public int Compare(I x, I y) => _comparer(_transformer(x), _transformer(y));
}

но потом я обнаружил, что List<T>.BinarySearch() работает с типом списка T, а не с тем типом свойства, которое я хочу, так что этого нет, потому что я хочу искать по идентификатору (который является int а не T).

Я не могу найти какие-либо автономные функции, которые выполняют общий двоичный поиск, существует ли такая функция в стандартной библиотеке (или даже в какой-нибудь общей библиотеке, которую я могу добавить с помощью nuget), которую я могу использовать? Или я должен катиться самостоятельно? Не то чтобы я возражал против своего собственного, потому что алгоритм тривиален, но мне нравится, когда я не пишу что-то, что, вероятно, было сделано в другом месте и уже проверено модулем. Я не знаю, пропускаю ли я что-то в каком-то классе утилит в экосистеме .NET (хотя .NET Core, но не Framework), или я должен либо искать в другом месте, либо свернуть свой собственный.

1 Ответ

0 голосов
/ 04 октября 2019

Вам нужно очень мало для пользовательского компаратора, который отвечает вашим требованиям: 

public class MyComparer : Comparer<MyClass>
{
    public override int Compare(MyClass x, MyClass y) => x.Id.CompareTo(y.Id);
}

Если вы хотите универсальный, вы можете написать класс, подобный этому: 

public class LambdaComparer<TSource, TKey> : IComparer<TSource> 
    where TKey : IComparable<TKey>
{
    private readonly Func<TSource, TKey> _keySelector;

    public LambdaComparer(Func<TSource, TKey> keySelector)
    {
        if (keySelector == null)
        {
            throw new ArgumentNullException(nameof(keySelector));
        }

        _keySelector = keySelector;
    }

    public override int Compare(TSource x, TSource y)
    {
        var xKey = _keySelector(x);
        var yKey = _keySelector(y);

        if (xKey == null) 
        {
            return yKey == null ? 0 : -1;
        }

        return _keySelector(x).CompareTo(_keySelector(y));
    }
}

Изатем оберните его в метод расширения для удобства: 

public static class ListExtensions
{
    public static int BinarySearch<TSource, TKey>(
        this List<TSource> list,
        TSource item, 
        Func<TSource, TKey> keySelector) where TKey : IComparable<TKey> => 
        list.BinarySearch(item, new LambdaComparer<TSource, TKey>(keySelector));

}

Наконец тест: 

var list = new[]
{
    "AVeryLongString",
    null,
    "NotLong",
    "A",
    "ZZZ"
};

var orderedByDefault = list.OrderBy(s => s).ToList();
var orderedByLength = list.OrderBy(s => s?.Length).ToList();

var indexOfZZZByDefault = orderedByDefault.BinarySearch("ZZZ");
var indexOfZZZByLength = orderedByLength.BinarySearch(
    "ZZZ", 
    s => s?.Length ?? 0);

Assert.Equal(4, indexOfZZZByDefault);
Assert.Equal(2, indexOfZZZByLength);
...