List<E> Entries;
return Entries.Find(i => i.A == a);
он отсортирован значит можно бинарным поиском искать
но проблема в том что мы тут ищем по значению поля, а не сам элемент, хотя мы можемзадать компаратор
var i = Entries.BinarySearch(сюда наша шото передать, Comparer<E>.Create((x, y) => x.A.CompareTo(y.A)));
return Entries[i];
но нам нужно все равно передать элемент для поиска, а его нет, есть только значения поля, и создать его нельзя потому E это шаблонный параметр который нельзя создать
можно ли разрулить без
Entries.Select(i => i.A).ToList().BinarySearch...
ибо такое может может похерить весь бенефит от BinarySearch
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Здравствуйте, Barbar1an, Вы писали:
B>но нам нужно все равно передать элемент для поиска, а его нет, есть только значения поля, и создать его нельзя потому E это шаблонный параметр который нельзя создать
При желании можно немного костылей нагородить. Для поиска передавать null (default(T)), а действительно искомое значение прописать в своей реализации IComparer.
Что-то типа:
public class BinaryComparer<T> : IComparer<T>
{
Func<T, int> _comparer;
public BinaryComparer(Func<T, int> comparer)
{
_comparer = comparer;
}
public int Compare(T x, T y)
{
return _comparer(x);
}
}
...
var i = Entries.BinarySearch(null, new BinaryComparer<E>(x => x.A.CompareTo(10))); // Поиск элемента, у которого A == 10
Ну, либо свой бинарный поиск написать, он достаточно простой.
Возможно Вам поможет ArrayList.Adapter(IList)
В документации написано, что это обертка над передаваемой коллекцией без копирования.
пример
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace binarysearch {
class Program {
static void Main(string[] args) {
List<MyClass> lc = new List<MyClass>();
lc.Add(new MyClass() { f1 = 1 });
lc.Add(new MyClass() { f1 = 3 });
lc.Add(new MyClass() { f1 = 2 });
lc.Sort(new MyClassComparer());
ArrayList al = ArrayList.Adapter(lc);
var mc1 = new MyComparer<int, MyClass>(
Comparer<int>.Default.Compare,
(MyClass mc_)=>{return mc_.f1;}
);
int r1 = al.BinarySearch(5, mc1);
int r2 = al.BinarySearch(3, mc1);
Console.WriteLine(r1);
Console.WriteLine(r2);
Console.ReadKey();
}
class MyComparer<TAttr, TObj> : IComparer where TObj : class {
private Func<TAttr, TAttr, int> cmp;
private Func<TObj, TAttr> conv;
public MyComparer(Func<TAttr, TAttr, int> cmp, Func<TObj, TAttr> conv) {
this.cmp = cmp;
this.conv = conv;
}
public int Compare(object x, object y) {
TObj x_ = x as TObj;
if (x_ != null && y is TAttr) {
return cmp(conv(x_), (TAttr)y);
} else {
TObj y_ = y as TObj;
if (y_ != null && x is TAttr) {
return cmp((TAttr)x, conv(y_));
}
}
throw new InvalidOperationException();
}
}
class MyClass {
public int f1;
}
class MyClassComparer : IComparer<MyClass> {
public int Compare(MyClass x, MyClass y) {
return x.f1.CompareTo(y.f1);
}
}
}
}
я бы даже немного по-другому сделал работу с ArrayList.Adapter: через обертку реализующую IList.
пример
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace binarysearch {
class Program {
static void Main(string[] args) {
Test2();
}
static void Test2() {
List<MyClass> lc = new List<MyClass>();
lc.Add(new MyClass() { f1 = 1 });
lc.Add(new MyClass() { f1 = 3 });
lc.Add(new MyClass() { f1 = 2 });
lc.Sort(new MyClassComparer());
ArrayList al = ArrayList.Adapter(new Wrapper<int,MyClass>(lc, (MyClass mc_) => { return mc_.f1; }));
var mc2 = new MyComparer2<int>(Comparer<int>.Default.Compare);
int r1 = al.BinarySearch(5, mc2);
int r2 = al.BinarySearch(3, mc2);
Console.WriteLine(r1);
Console.WriteLine(r2);
Console.ReadKey();
}
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 MyClass {
public int f1;
}
class MyClassComparer : IComparer<MyClass> {
public int Compare(MyClass x, MyClass y) {
return x.f1.CompareTo(y.f1);
}
}
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
}
}
}
Здравствуйте, Barbar1an, Вы писали:
B>но проблема в том что мы тут ищем по значению поля, а не сам элемент, хотя мы можемзадать компаратор
Готовой функции нет. Но бинарный поиск настолько прост, что пишется за пять минут.
public static int BinarySearch<T>(this IList<T> list, Func<T, T, int> comparer, T value)
{
var left = 0;
var right = list.Count - 1;
while (left <= right)
{
var mid = left + (right - left) / 2;
var cmp = comparer(value, list[mid]);
if (cmp == 0)
return mid;
if (cmp < 0)
right = mid - 1;
else
left = mid + 1;
}
return ~left; // индекс вставки с битовым дополнением
}
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
я полагаю, что ТС знает, как написать binarysearch.
А значит его интересует именно альтернативные решения, поиск которых вполне себе интересная задача.
Здравствуйте, VladD2, Вы писали:
VD>Что же за тяга к костылям то на ровном месте?
VD>Не проще ли такую функцию руками написать или какой-нить ИИ запрячь для этого?
Ну, если это какой-то наколеночный проект, то лично мне проще подобный костыль написать.
Правда вряд ли я бы задумывался в таком случае об оптимизации типа бинарного поиска.
Если это какой-то относительно серьёзный проект, который потом нужно поддерживать, то отдельно бинарный поиск мне всё равно не нравится.
Сегодня коллекцию отсортировали по свойству A и всё работает. Завтра отсортируют по свойству B, а в поиске не поменяют компаратор, получится неприятный плавающий баг поиска.
Тут уже напрашивается свой тип коллекции, который защитит от подобных сюрпризов.
VD>А какой смысл в этом? Если написать свою функцию проще чем городить костыли, то зачем вообще рассматривать вопрос костылей?
Можно написать свою, а можно взять ArrayList.Adapter, как я предлагаю выше.
Однако это не является достаточным для решения задачи ТС.
Т.к. ему нужно искать по значению поля (T value у него нет)
public static int BinarySearch<T>(this IList<T> list, Func<T, T, int> comparer, T value)
А значит в любом случае нужна какая-то обертка над T или IList<T> ("овердизайн"), либо хитрый comparer ("костыли").
Здравствуйте, karbofos42, Вы писали:
K>Ну, если это какой-то наколеночный проект, то лично мне проще подобный костыль написать.
Ну вот так вот признаваться, что предпочитаешь городить костыли просто не прилично.
K>Правда вряд ли я бы задумывался в таком случае об оптимизации типа бинарного поиска.
Вот-вот. А главное тратить время на поиск костылей, когда можно просто спросить у ИИ есть ли готовое решение и, если нет, попросить сгенерить реализацию под свои нужды, если ух основ не знаешь и не можешь её с закрытыми глазами написать.
K>Если это какой-то относительно серьёзный проект, который потом нужно поддерживать, то отдельно бинарный поиск мне всё равно не нравится.
K>Сегодня коллекцию отсортировали по свойству A и всё работает. Завтра отсортируют по свойству B, а в поиске не поменяют компаратор, получится неприятный плавающий баг поиска.
А если кто-то в проекте еще и "!" рандомом в if-ах расставит?
Тесты делать надо. Иначе ничего работать не будет после мало мальских серьезных изменений.
K>Тут уже напрашивается свой тип коллекции, который защитит от подобных сюрпризов.
Да, точно! Лучше с языка программирования начинать. Прямо со встроенным синтаксисом.
Где-то может спец-коллекция и норм. Но алгоритмы в виде функций это никак не отменял. В конце концов не писать же специализированные копипасты в этих самых коллекциях?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, m2user, Вы писали:
M>Можно написать свою, а можно взять ArrayList.Adapter, как я предлагаю выше. M>Однако это не является достаточным для решения задачи ТС. M>Т.к. ему нужно искать по значению поля (T value у него нет)
Ну это просто мне было влом самому писать, а ИИ тупанул чутка. Без параметра легко можно обойтись:
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; // индекс вставки с битовым дополнением
}
M>А значит в любом случае нужна какая-то обертка над T или IList<T> ("овердизайн"), либо хитрый comparer ("костыли").
Думать немножко надо.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Вот-вот. А главное тратить время на поиск костылей, когда можно просто спросить у ИИ есть ли готовое решение и, если нет, попросить сгенерить реализацию под свои нужды, если ух основ не знаешь и не можешь её с закрытыми глазами написать.
Так я не тратил время на поиск костыля. Написал его за пару минут на основании своих знаний об устройстве стандартных структур и алгоритмов.
Если бы кто-то ТСу быстро ответил, я бы этого не делал. Спросить у ИИ или найти/написать простейший бинарный поиск он тоже сам бы наверно справился.
VD>Тесты делать надо. Иначе ничего работать не будет после мало мальских серьезных изменений.
Надо. Только в итоге оказывается, что в тестах кто-то заполнил коллекцию данными вида: ("a", 1), ("b", 2), ("c", 3)
и смена свойства для сортировки ничего не меняет в результате, тесты проходят.
Но конечно же при написании теста нужно предвидеть все возможные будущие изменения и под них создавать безупречные тестовые наборы данных.
А ещё и код без багов нужно писать.
VD>Где-то может спец-коллекция и норм. Но алгоритмы в виде функций это никак не отменял. В конце концов не писать же специализированные копипасты в этих самых коллекциях?
Так я и предложил вариант, чтобы обойтись без специализированной копипасты алгоритма бинарного поиска.
А уж где что использовать — тут много факторов влияет.
Я предупредил, что это костыль, и не заставляю использовать.
Редко сам что-то подобное использую, если где и напишу, то сильно как временное решение, которое быстро меняется в рамках рефакторинга/оптимизации на что-то более адекватное.
VD>Ну это просто мне было влом самому писать, а ИИ тупанул чутка. Без параметра легко можно обойтись:
Угу, и если добавить реализацию Func<T, int> comparer, то по объему содержательного кода будет примерно столько же, как в предложенном здесь (https://rsdn.org/forum/dotnet/8914066?tree=tree
) варианте.
Поэтому не вижу там никакого овердизайна.
Также я полагаю, что с т.з. поддержки кода собственная реализация даже самых простых алгоритмов это дополнительная нагрузка и потенциальный источник bug`ов.
Т.е. для автора кода алгоритм выглядит как 100% верный (например скопирован с reference source), однако для другого разработчика, который будет иметь дело с этим кодом, это уже не так (даже если есть unit тесты).
Здравствуйте, m2user, Вы писали:
M>Угу, и если добавить реализацию Func<T, int> comparer, то по объему содержательного кода будет примерно столько же, как в предложенном здесь (https://rsdn.org/forum/dotnet/8914066?tree=tree
) варианте. M>Поэтому не вижу там никакого овердизайна.
1. Как бы любому непредвзятому очевидно обратное. Объем кода как-то сильно выше.
2. ArrayList — это древнючий не типизированный класс не пригодный, например, для списков структур.
3. Он не решает исходную задачу, так как у него точно так же нет перегрузки не принимающий эталонный элемент. В результате ты начинаешь городить костыли над костылями — Wrapper, вторую обёртку.
. Он короче, понятнее и быстрее.
M>Также я полагаю, что с т.з. поддержки кода собственная реализация даже самых простых алгоритмов это дополнительная нагрузка и потенциальный источник bug`ов.
Твои предположения высосаны из пальца и не верны. Твои обёртки плохо читаются, создают оверхэд и точно так же требуют тестирования. Код бинарного поиска очень прост. Он, конечно, требует тестирования, но не более чем костыли. А вот мину у костылей всего лишь один, но глобальный — они ухудшают читаемость кода усложняя его без необходимости.
M>Т.е. для автора кода алгоритм выглядит как 100% верный (например скопирован с reference source), однако для другого разработчика, который будет иметь дело с этим кодом, это уже не так (даже если есть unit тесты).
Если тесты есть, проблем никаких не вижу. А они всё равно нужны.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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
Вот только это тоже незаконченное решение. Ты не знаешь, под каким аргументом (x или у) в Compare придет null или default(T).
Предлагаю сначала реализовать эту логику (как для классов, так и для структур), после чего обсуждать краткость, понятность и пр. M>>Также я полагаю, что с т.з. поддержки кода собственная реализация даже самых простых алгоритмов это дополнительная нагрузка и потенциальный источник bug`ов. VD>Твои предположения высосаны из пальца и не верны. Твои обёртки плохо читаются, создают оверхэд и точно так же требуют тестирования.
Не вижу проблем с читаемостью.
Да, формально общий объём кода больше, но логика, которую он реализует, заметно проще.
По оверхэд могут быть проблемы, не спорю. VD> Код бинарного поиска очень прост.
И тем не менее он сложнее, чем обертка, частично реализующая IList<>.
Конечно сложность не такая, чтобы принципиально отказываться от собственной реализации BinarySearch, но достаточная для того, чтобы озаботиться поиском альтернативных вариантов. VD> Он, конечно, требует тестирования, но не более чем костыли. А вот мину у костылей всего лишь один, но глобальный — они ухудшают читаемость кода усложняя его без необходимости.
Вот там выше karbofos42 прокомментировал относительно тестов.
Одно дело тестировать алгоритм поиска, другое — простейший wrapper на два метода.
Вероятность ошибки в коде совсем разная.
Здравствуйте, m2user, Вы писали:
M>Вот только это тоже незаконченное решение. Ты не знаешь, под каким аргументом (x или у) в Compare придет null или default(T).
Это законченное решение.
Есть конечно вероятность, что кто-то когда-то поменяет реализацию бинарного поиска и в x положит искомый элемент, тогда перестанет работать и нужно будет вызывать _comparer(y).
Таков удел костылей, они всегда несут с собой подобные риски.
K>Есть конечно вероятность, что кто-то когда-то поменяет реализацию бинарного поиска и в x положит искомый элемент, тогда перестанет работать и нужно будет вызывать _comparer(y).
Или, если такие изменения реализации были в прошлом — в рамках диапазона версий .NET Framework, на которых должно работать приложение.
K>Таков удел костылей, они всегда несут с собой подобные риски.
Здравствуйте, Pzz, Вы писали:
Pzz>Если он именно, что list (т.е., список), то у него есть только последовательный доступ к элементам. А значит, бинарным поиском искать нельзя.
В .NET List — это динамический массив (аналог vector из C++). Связный список с последовательным доступом — это LinkedList.
