我在 Youtube 上看了一些程序員采訪的視頻。其中一個(gè)問(wèn)題是編寫(xiě)一個(gè)返回?cái)?shù)組中第 n 個(gè)最小元素的函數(shù)。在視頻中，我看到一位女士嘗試用 C++ 編寫(xiě)一些重復(fù)代碼，但我認(rèn)為很好，在 C# 中它是一個(gè)襯里：var nth = vals.OrderBy(x => x).Take(i).Last();然后我意識(shí)到我不知道這實(shí)際上是否是一個(gè)好的解決方案，因?yàn)橄乱粋€(gè)問(wèn)題是關(guān)于時(shí)間復(fù)雜度的。我去了文檔，我發(fā)現(xiàn)的是返回的對(duì)象OrderBy具有在枚舉時(shí)執(zhí)行完整延遲排序所需的所有信息。所以我決定對(duì)其進(jìn)行測(cè)試，并MyComparable : IComparable<MyComparable>在 CompareTo 方法中編寫(xiě)了一個(gè)具有單值和靜態(tài)計(jì)數(shù)器的類(lèi)： 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); } }然后我寫(xiě)了一個(gè)循環(huán)來(lái)查找數(shù)組中的第 n 個(gè)元素： 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(); } }
LINQ 中的 OrderBy 和 Take
翻過(guò)高山走不出你
2022-11-22 15:20:55
