मैं 500000 यादृच्छिक रूप से जनरेट Tuple<long,long,string> वस्तुओं की एक सूची है जिस पर मैं खोज "के बीच" एक साधारण प्रदर्शन कर रहा है:एक सॉर्ट किए गए सरणी की तुलना में एक क्रमबद्ध सरणी को धीमा क्यों कर रहा है?
var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
जब मैं अपने यादृच्छिक सरणी पैदा करते हैं और x के 100 बेतरतीब ढंग से उत्पन्न मूल्यों के लिए मेरे खोज चलाने के लिए, खोज लगभग चार सेकंड में पूर्ण हो जाती है। Item1 से तो Item2 द्वारा Item3 से पहले, और अंत में - - great wonders that sorting does to searching के जानने के बाद, हालांकि, मैं अपने डेटा को सॉर्ट करने का निर्णय लिया मेरी 100 खोजों को चलाने से पहले। मैं शाखा भविष्यवाणी की वजह से तेजी से एक छोटे से प्रदर्शन करने के लिए क्रमबद्ध संस्करण की उम्मीद: मेरी सोच रहा है कि एक बार हम बिंदु है जहां Item1 == x, t.Item1 <= x के सभी आगे के चेक को सही ढंग से शाखा भविष्यवाणी के रूप में "नहीं ले", पूंछ भाग को तेज करने के लिए मिलता है खोज का मेरे आश्चर्य करने के लिए बहुत, खोजें एक क्रमबद्ध सरणी पर जब तक दो बार ले ली!
मैं जिस क्रम में मैं अपने प्रयोगों भाग गया, और यादृच्छिक संख्या जनरेटर के लिए विभिन्न बीज इस्तेमाल किया आसपास स्विचन की कोशिश की है, लेकिन प्रभाव ही कर दिया गया है: खोज एक अवर्गीकृत सरणी में खोजों में के रूप में लगभग दो बार के रूप में तेजी से भाग गया एक ही सरणी, लेकिन क्रमबद्ध!
किसी को भी इस अजीब प्रभाव का एक अच्छा विवरण है? मेरे परीक्षणों का स्रोत कोड निम्नानुसार है; मैं .NET 4.0 का उपयोग कर रहा हूँ।
private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
var data = new byte[8];
r.NextBytes(data);
return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
var res = x.Item1.CompareTo(y.Item1);
if (res != 0) return res;
res = x.Item2.CompareTo(y.Item2);
return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
}
}
static void Test(bool doSort) {
var data = new List<Tuple<long,long,string>>(TotalCount);
var random = new Random(1000000007);
var sw = new Stopwatch();
sw.Start();
for (var i = 0 ; i != TotalCount ; i++) {
var a = NextLong(random);
var b = NextLong(random);
if (a > b) {
var tmp = a;
a = b;
b = tmp;
}
var s = string.Format("{0}-{1}", a, b);
data.Add(Tuple.Create(a, b, s));
}
sw.Stop();
if (doSort) {
data.Sort(new TupleComparer());
}
Console.WriteLine("Populated in {0}", sw.Elapsed);
sw.Reset();
var total = 0L;
sw.Start();
for (var i = 0 ; i != TotalQueries ; i++) {
var x = NextLong(random);
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
total += cnt;
}
sw.Stop();
Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
Test(false);
Test(true);
Test(false);
Test(true);
}
Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)
शाखा भविष्यवाणी के कारण: पी –
@jalf मुझे उम्मीद है कि क्रमबद्ध संस्करण शाखा भविष्यवाणी के कारण थोड़ा तेज़ प्रदर्शन करेगा। मेरी सोच यह थी कि एक बार जब हम उस बिंदु पर पहुंच जाते हैं जहां 'Item1 == x',' t.Item1 <= x' की सभी और जांच शाखा की भविष्यवाणी को "नहीं लेती" के रूप में सही ढंग से भविष्यवाणी करती है, जो खोज के पूंछ हिस्से को तेज करती है। जाहिर है, कठोर वास्तविकता द्वारा सोच की उस पंक्ति को गलत साबित कर दिया गया है :) – dasblinkenlight
दिलचस्प बात यह है कि 'कुल राशि' के लिए '10,000' या उससे कम के लिए, क्रमबद्ध संस्करण तेजी से प्रदर्शन करता है (बेशक, उन छोटी संख्याओं में तेज़ी से तेज़) (एफवाईआई, आपके कोड में 'var डेटा सूची = नई सूची> (500000) 'प्रारंभिक आकार की क्षमता को हार्ड कोडिंग के बजाय' टोटलकाउंट' के विरुद्ध बाध्य होना चाहिए) –