صافي مستطيلة صالحة: كيفية الوصول في حلقة؟
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
وأساسا لديك طريقتان للقيام بذلك:
for (int x = 0; x < UPPER_X; x++)
for (int y = 0; y < UPPER_Y; y++)
{
arr1[x, y] = get_value();
arr2[y, x] = get_value();
}
والفرق الوحيد هو ما متغير التغير في الحلقة الداخلية: الأولى أو الثانية. سمعت أن النتائج تختلف من لغة إلى لغة.
ما هو الترتيب الصحيح ل. NET؟
المحلول
والسبب واحد هو أسرع من الآخر له علاقة مع ذاكرة التخزين المؤقت المعالج، والطريقة التي وضعت البيانات في الذاكرة.
وهناك طريقتان العادية لتخزين البيانات ثنائية الأبعاد في الأبعاد واحد مساحة العنوان، إما يمكنك تخزين كافة البيانات عن الصف الأول، ثم الصف الثاني، وهلم جرا (ويعرف أيضا باسم <لأ href = "http://en.wikipedia.org/wiki/Row-major_order" يختلط = "نوفولو noreferrer"> <م> الصف أجل الرئيسي )، أو يمكنك القيام بذلك عن طريق الأعمدة (الملقب < وأ href = "http://en.wikipedia.org/wiki/Row-major_order#Column-major_order" يختلط = "نوفولو noreferrer"> <م> العمود أجل الرئيسي ). وفيما يلي ما مواقع الذاكرة سيكون لمجموعة 3X3 لكل من هذه الخيارات.
والصفوف:
1 2 3
4 5 6
7 8 9
وأعمدة:
1 4 7
2 5 8
3 6 9
وعند الوصول إلى موقع ذاكرة واحدة، يتم تحميل خط كامل مخبأ (والتي يمكن أن تكون بين 8 و 512 بايت، وفقا لويكيبيديا) إلى ذاكرة التخزين المؤقت. حتى إذا كنت الوصول إلى موقع ذاكرة القادم سيكون بالفعل في ذاكرة التخزين المؤقت. وهكذا، يمكن أن يكون أسرع بكثير للوصول بالتتابع الذاكرة من القفز حولها في مساحة العنوان. وهكذا، مع المصفوفات ثنائية الأبعاد الكبيرة، يمكن أن يكون هناك اختلاف كبير بين سرعة اختيار الصفوف أو الأعمدة كما متغير الحلقة الداخلية الخاصة بك.
نصائح أخرى
ويجب عليك القياسي ظروفك الخاصة للتأكد.
وأنت أعتقد أنه لن يكون هناك أي فرق للصفائف مستطيلة (ذاكرة أي تخصص متاخم)، ولكن وفقا لهذا <وأ href = "http://msdn.microsoft.com/en-us/magazine/cc163995.aspx "يختلط =" noreferrer نوفولو "> المادة MSDN هناك فرق:
<اقتباس فقرة>ويمكنك الحصول على أفضل النتائج وفقا ل تحويل مجموعة متعددة الأبعاد في مجموعة واحدة الأبعاد. إذا كنت لا تمانع في بناء الجملة، وهذا يمكن أن يكون تافهة. مجرد استخدام مؤشر واحد على أنه الأوفست. على سبيل المثال، ما يلي تعلن مجموعة واحدة الأبعاد ل أن تستخدم مجموعة ثنائية الأبعاد:
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
لفهرسة عناصر هذا مجموعة، استخدم ما يلي الأوفست:
myArray[row * COLUMN_DIM + column];
وهذا بلا شك سيكون أسرع من أي ما يعادل خشنة أو مستطيل صفيف.
وهكذا لم المؤشر والنتائج هي أن الوصول إلى arr1 ثلاث مرات أسرع.
ومثيرة جدا للاهتمام، وأنا لم تتوقف للنظر التي يمكن أن تكون مثل هذا الفارق الضخم ببساطة عن طريق الوصول إلى مؤشرات مجموعة "غير بالتتابع". أعطى ذلك في محاولة لنفسي، ووجدت أيضا كان البرمجية التالية في الحلقة الثانية اتخاذ بين 2-3 مرات أطول:
// Hmmm, how to insert blank lines in the code formatter???
static void Main(string[] args)
{
Stopwatch timer = new Stopwatch();
int arraySize = 10000;
// First array, access X by Y
int[,] xbyy = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
xbyy[x, y] = 15;
}
timer.Stop();
TimeSpan duration = timer.Elapsed;
string realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("X by Y took " + realTimeFormat);
// Seecond array, access Y by X
int[,] ybyx = new int[arraySize, arraySize];
timer.Start();
for (int x = 0; x < arraySize; x++)
for (int y = 0; y < arraySize; y++)
{
ybyx[y, x] = 15;
}
timer.Stop();
duration = timer.Elapsed;
realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
duration.Minutes, duration.Seconds, duration.Milliseconds);
Console.WriteLine("Y by X took " + realTimeFormat);
Console.ReadLine();
}
لابقاء الامور قصيرة، وهنا قصاصات IL المنبعثة لX من Y حلقة وY التي كتبها X حلقة.
وكود الأولي قبل حلقات،
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
// Code size 290 (0x122)
.maxstack 4
.locals init ([0] class [System]System.Diagnostics.Stopwatch timer,
[1] int32 arraySize,
[2] int32[0...,0...] xbyy,
[3] int32 x,
[4] int32 y,
[5] valuetype [mscorlib]System.TimeSpan duration,
[6] string realTimeFormat,
[7] int32[0...,0...] ybyx,
[8] int32 V_8,
[9] int32 V_9)
IL_0000: newobj instance void [System]System.Diagnostics.Stopwatch::.ctor()
IL_0005: stloc.0
IL_0006: ldc.i4 0x2710
IL_000b: stloc.1
وحلقات X من Y
IL_000c: ldloc.1
IL_000d: ldloc.1
IL_000e: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0013: stloc.2
IL_0014: ldloc.0
IL_0015: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_001a: ldc.i4.0
IL_001b: stloc.3
IL_001c: br.s IL_003d
IL_001e: ldc.i4.0
IL_001f: stloc.s y
IL_0021: br.s IL_0034
IL_0023: ldloc.2
IL_0024: ldloc.3
IL_0025: ldloc.s y
IL_0027: ldc.i4.s 15
IL_0029: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_002e: ldloc.s y
IL_0030: ldc.i4.1
IL_0031: add
IL_0032: stloc.s y
IL_0034: ldloc.s y
IL_0036: ldloc.1
IL_0037: blt.s IL_0023
IL_0039: ldloc.3
IL_003a: ldc.i4.1
IL_003b: add
IL_003c: stloc.3
IL_003d: ldloc.3
IL_003e: ldloc.1
IL_003f: blt.s IL_001e
IL_0041: ldloc.0
وحلقات Y التي كتبها X
IL_0090: ldloc.1
IL_0091: ldloc.1
IL_0092: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_0097: stloc.s ybyx
IL_0099: ldloc.0
IL_009a: callvirt instance void [System]System.Diagnostics.Stopwatch::Start()
IL_009f: ldc.i4.0
IL_00a0: stloc.s V_8
IL_00a2: br.s IL_00c7
IL_00a4: ldc.i4.0
IL_00a5: stloc.s V_9
IL_00a7: br.s IL_00bc
IL_00a9: ldloc.s ybyx
IL_00ab: ldloc.s V_9
IL_00ad: ldloc.s V_8
IL_00af: ldc.i4.s 15
IL_00b1: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_00b6: ldloc.s V_9
IL_00b8: ldc.i4.1
IL_00b9: add
IL_00ba: stloc.s V_9
IL_00bc: ldloc.s V_9
IL_00be: ldloc.1
IL_00bf: blt.s IL_00a9
IL_00c1: ldloc.s V_8
IL_00c3: ldc.i4.1
IL_00c4: add
IL_00c5: stloc.s V_8
IL_00c7: ldloc.s V_8
IL_00c9: ldloc.1
IL_00ca: blt.s IL_00a4
IL_00cc: ldloc.0
وتدفق منطق IL يشبه إلى حد ما. والفرق الرئيسي I يمكن أن نلاحظ هو حلقة الأولى يدير لاستخدام stloc وldloc لشغل وظائف 2 و 3 للمجموعة الأولى ومتغير مؤشر X. في الوقت الذي جاء إلى حلقة الثانية، فقد أنفقت maxstack وبالتالي استخدام stloc.s والتعليمات ldloc.s. وأعتقد أن هذا هو الفرق بين الرجوع المتغيرات على المكدس مقابل على كومة، والمساهمة في تباطؤ الأداء.
والآن، إذا كنت مبادلة الترتيب الذي يتم اختباره الحلقات، بحيث Y التي كتبها X حلقة يحصل على تشغيل الأول للوصول المراجع المكدس، سترى فترات توقيت الحصول على عكسه.
وUPDATE: كنت مخطئا حول ترجع إلى كومة كومة أو عناوين. ويبدو فقط أن المتغيرات الأربعة الأولى في طريقة أكثر كفاءة لمرجع مع stloc.0 مكرسة، 1، 3، 4 و ldloc.0، 1، 3، 4 أكواد العمليات.
http://weblogs.asp.net/mnolton /archive/2004/01/09/48992.aspx
