Я смотрел несколько видео на Youtube с интервью программистов. Один из вопросов - написать функцию, которая возвращает n-й наименьший элемент массива.
В видео, которое я видел, одна леди пыталась закодировать это в C ++ с некоторой периодичностью, но я подумал, что хорошо, в C # это одна строка:
var nth = vals.OrderBy(x => x).Take(i).Last();
Тогда я понял, что понятия не имею, действительно ли это хорошее решение, поскольку следующий вопрос касался сложности времени. Я перешел к документации и обнаружил, что объект, возвращаемый OrderBy, имеет всю информацию, необходимую для выполнения полной отложенной сортировки при перечислении.
Поэтому я решил проверить его и написал класс MyComparable : IComparable<MyComparable> с одним значением и статическим счетчиком в методе CompareTo:
class MyComparable : IComparable<MyComparable>
{
public MyComparable(int val)
{
Val = val;
}
public static int CompareCount { get; set; }
public int Val { get; set; }
public int CompareTo(MyComparable other)
{
++CompareCount;
if (ReferenceEquals(this, other)) return 0;
if (ReferenceEquals(null, other)) return 1;
return Val.CompareTo(other.Val);
}
}
Затем я написал цикл, который находит n-й элемент в массиве:
static void Main(string[] args)
{
var rand = new Random();
var vals = Enumerable.Range(0, 10000)
// .Reverse() // pesimistic scenario
// .OrderBy(x => rand.Next()) // average scenario
.Select(x => new MyComparable(x))
.ToArray();
for (int i = 1; i < 100; i++)
{
var nth = vals.OrderBy(x => x).Take(i).Last();
Console.WriteLine($"i: {i,5}, OrderBy: {MyComparable.CompareCount,10}, value {nth.Val}");
MyComparable.CompareCount = 0;
var my_nth = vals.OrderByInsertion().Take(i).Last();
Console.WriteLine($"i: {i,5}, Insert : {MyComparable.CompareCount,10}, value {my_nth.Val}");
MyComparable.CompareCount = 0;
my_nth = vals.OrderByInsertionWithIndex().Take(i).Last();
Console.WriteLine($"i: {i,5}, Index : {MyComparable.CompareCount,10}, value {my_nth.Val}");
MyComparable.CompareCount = 0;
Console.WriteLine();
Console.WriteLine();
}
}
Я также написал 2 "разные" реализации для нахождения элемента min, его возврата и удаления из списка:
public static IEnumerable<T> OrderByInsertion<T>(this IEnumerable<T> input) where T : IComparable<T>
{
var list = input.ToList();
while (list.Any())
{
var min = list.Min();
yield return min;
list.Remove(min);
}
}
public static IEnumerable<T> OrderByInsertionWithIndex<T>(this IEnumerable<T> input) where T : IComparable<T>
{
var list = input.ToList();
while (list.Any())
{
var minIndex = 0;
for (int i = 1; i < list.Count; i++)
{
if (list[i].CompareTo(list[minIndex]) < 0)
{
minIndex = i;
}
}
yield return list[minIndex];
list.RemoveAt(minIndex);
}
}
Результаты действительно были для меня неожиданностью:
i: 1, OrderBy: 19969, value 0
i: 1, Insert : 9999, value 0
i: 1, Index : 9999, value 0
i: 2, OrderBy: 19969, value 1
i: 2, Insert : 19997, value 1
i: 2, Index : 19997, value 1
i: 3, OrderBy: 19969, value 2
i: 3, Insert : 29994, value 2
i: 3, Index : 29994, value 2
i: 4, OrderBy: 19969, value 3
i: 4, Insert : 39990, value 3
i: 4, Index : 39990, value 3
i: 5, OrderBy: 19970, value 4
i: 5, Insert : 49985, value 4
i: 5, Index : 49985, value 4
...
i: 71, OrderBy: 19973, value 70
i: 71, Insert : 707444, value 70
i: 71, Index : 707444, value 70
...
i: 99, OrderBy: 19972, value 98
i: 99, Insert : 985050, value 98
i: 99, Index : 985050, value 98
Простое использование LINQ OrderBy().Take(n) на сегодняшний день является наиболее эффективным и быстрым, что я и ожидал, но никогда бы не догадался, что разрыв составляет несколько порядков.
Итак, мой вопрос в основном к интервьюерам: как бы вы оценили такой ответ?
Код:
var nth = vals.OrderBy(x => x).Take(i).Last();
Сложность времени:
Я не знаю деталей, но, вероятно, OrderBy использует какую-то быструю сортировку, без n log(n), независимо от того, какой n-й элемент нам нужен.
Не могли бы вы попросить меня реализовать мои собственные методы, подобные этим, или этого будет достаточно для использования фреймворка?
EDIT:
Итак, как и в приведенном ниже ответе, OrderedEnumerable использует вариант QuickSelect для сортировки только тех элементов, которые вы запрашиваете. С положительной стороны, он кэширует порядок.
Хотя вы можете найти n-й элемент немного быстрее, он не класс быстрее, а на несколько процентов быстрее. Кроме того, каждый программист C # поймет ваш один вкладыш.
Я думаю, что мой ответ во время собеседования закончится где-то рядом: «Я буду использовать OrderBy, потому что он достаточно быстрый, а запись занимает 10 секунд. Если окажется, что он медленный, мы можем выиграть некоторое время с QucikSelect, но на его реализацию уходит много времени "
Спасибо всем, кто решил поучаствовать в этом, и извините всех, кто потратил свое время, думая, что это что-то другое