Re[10]: BinarySearch со значением поля на входе
От: m2user  
Дата: 02.04.25 00:56
Оценка:
VD>1. Как бы любому непредвзятому очевидно обратное. Объем кода как-то сильно выше.

Ну хорошо, можно подсчитать строки:

  код №1
public static Func<T, int> CreateComparer<T,K>(Func<T,K> conv, Func<K,K, int> comp, K fieldVal) {
    return (T t) => { return comp(conv(t), fieldVal); };
}

public static int BinarySearch<T>(this IList<T> list, Func<T, int> comparer)
{
    var left = 0;
    var right = list.Count - 1;

    while (left <= right)
    {
        var mid = left + (right - left) / 2;
        var cmp = comparer(list[mid]);

        if (cmp == 0)
            return mid;

        if (cmp < 0)
            right = mid - 1;
        else
            left = mid + 1;
    }

    return ~left; // индекс вставки с битовым дополнением
}


25 строк (добавлен метод, создающий comparer)

  код №2
        class MyComparer2<TAttr> : IComparer {
            private Func<TAttr, TAttr, int> cmp;
            public MyComparer2(Func<TAttr, TAttr, int> cmp) {
                this.cmp = cmp;
            }
            public int Compare(object x, object y) {
                return cmp((TAttr)x, (TAttr)y);
            }
        }

        class Wrapper<TAttr,TObj>: IList {

            private IList<TObj> data;
            private Func<TObj, TAttr> conv;

            public Wrapper(IList<TObj> data, Func<TObj, TAttr> conv) {
                this.data = data;
                this.conv = conv;
            }

            public object this[int index] {
                get {
                    return conv(data[index]);
                }
                set {
                    throw new NotImplementedException();
                }
            }

            public int Count {
                get { return data.Count; }
            }

            #region notimpl

            public int Add(object value) {
                throw new NotImplementedException();
            }

            public void Clear() {
                throw new NotImplementedException();
            }

            public bool Contains(object value) {
                throw new NotImplementedException();
            }

            public int IndexOf(object value) {
                throw new NotImplementedException();
            }

            public void Insert(int index, object value) {
                throw new NotImplementedException();
            }

            public bool IsFixedSize {
                get { throw new NotImplementedException(); }
            }

            public bool IsReadOnly {
                get { throw new NotImplementedException(); }
            }

            public void Remove(object value) {
                throw new NotImplementedException();
            }

            public void RemoveAt(int index) {
                throw new NotImplementedException();
            }

            public void CopyTo(Array array, int index) {
                throw new NotImplementedException();
            }


            public bool IsSynchronized {
                get { throw new NotImplementedException(); }
            }

            public object SyncRoot {
                get { throw new NotImplementedException(); }
            }

            public IEnumerator GetEnumerator() {
                throw new NotImplementedException();
            }

            #endregion notimpl
        }

    }


93 строки, из них 60 это NotImplemented методы IList. Без них — 33, что собственно я имел в виду под содержательным кодом.

VD>2. ArrayList — это древнючий не типизированный класс не пригодный, например, для списков структур.


Древний, но ведь задачу решает.
Согласен, что boxing/unboxing может отрицательно сказаться на производительности. Поэтому я бы проводил perf тест для оценки пригодности.

VD>3. Он не решает исходную задачу, так как у него точно так же нет перегрузки не принимающий эталонный элемент. В результате ты начинаешь городить костыли над костылями — Wrapper, вторую обёртку.


Да, wrapper, причём очень простой — достаточно прокинуть IList<T>.Count и IList<T>[]. Куда ещё проще и понятнее?

VD>Уж лучше тогда воспользоваться костылём karbofos42
Автор: karbofos42
Дата: 22.03.25
. Он короче, понятнее и быстрее.


Вот только это тоже незаконченное решение. Ты не знаешь, под каким аргументом (x или у) в Compare придет null или default(T).
Предлагаю сначала реализовать эту логику (как для классов, так и для структур), после чего обсуждать краткость, понятность и пр.

M>>Также я полагаю, что с т.з. поддержки кода собственная реализация даже самых простых алгоритмов это дополнительная нагрузка и потенциальный источник bug`ов.

VD>Твои предположения высосаны из пальца и не верны. Твои обёртки плохо читаются, создают оверхэд и точно так же требуют тестирования.

Не вижу проблем с читаемостью.
Да, формально общий объём кода больше, но логика, которую он реализует, заметно проще.
По оверхэд могут быть проблемы, не спорю.

VD> Код бинарного поиска очень прост.


И тем не менее он сложнее, чем обертка, частично реализующая IList<>.
Конечно сложность не такая, чтобы принципиально отказываться от собственной реализации BinarySearch, но достаточная для того, чтобы озаботиться поиском альтернативных вариантов.

VD> Он, конечно, требует тестирования, но не более чем костыли. А вот мину у костылей всего лишь один, но глобальный — они ухудшают читаемость кода усложняя его без необходимости.


Вот там выше karbofos42 прокомментировал относительно тестов.
Одно дело тестировать алгоритм поиска, другое — простейший wrapper на два метода.
Вероятность ошибки в коде совсем разная.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.