حسابيا كفاءة الأبعاد الثلاثة المصفوفات في C

Question

أنا أحاول حل عدديا مجموعة من المعادلات التفاضليه الجزءيه في ثلاثة أبعاد.في كل من المعادلات التالية قيمة المجهول في نقطة يعتمد على القيمة الحالية لكل المجهول في اقرب نقطة.

كتابة فعالة مدونة أنا بحاجة للحفاظ على نقطة إغلاق في ثلاثة أبعاد في (أحادية البعد) مساحة الذاكرة ، بحيث يكون لكل قيمة يتم استدعاؤها من الذاكرة مرة واحدة فقط.

كنت أفكر في استخدام octtrees ، ولكن أنا أتساءل عما إذا كان أي شخص يعرف طريقة أفضل.

Answer 1

Octtrees هي وسيلة للذهاب.يمكنك تقسيم المصفوفة إلى 8 octants:

1 2
3 4

---

5 6
7 8

ثم يضعونها في الذاكرة في النظام 1, 2, 3, 4, 5, 6, 7, 8 على النحو الوارد أعلاه.يمكنك تكرار هذا متكرر في كل octant حتى تصل إلى بعض حجم قاعدة, على الأرجح حوالي 128 بايت أو نحو ذلك (هذا مجرد تخمين -- تأكد من أن ملف التعريف لتحديد أفضل قطع نقطة).هذا أفضل بكثير مخبأ الاتساق و محلة إشارة من السذاجة تخطيط.

Answer 2

بديل واحد إلى شجرة-الطريقة:استخدام مورتون-أجل تشفير البيانات الخاصة بك.

في ثلاثة أبعاد وغني عن مثل هذا:تأخذ تنسيق مكونات تعشيق كل بت اثنين بت صفر.هنا هو مبين في الثنائية:11111b يصبح 1001001001b

ج-وظيفة هل هذا يبدو مثل هذا (كما هو موضح للتوضيح فقط لمدة 11 بت):

int morton3 (int a)
{
  int result = 0;
  int i;
  for (i=0; i<11; i++)
  {
     // check if the i'th bit is set.
     int bit = a&(1<<i);
     if (bit)
     {
       // if so set the 3*i'th bit in the result:
       result |= 1<<(i*3);
     }
  }
  return result;
}

يمكنك استخدام هذه الوظيفة إلى الجمع بين المناصب مثل هذا:

index = morton3 (position.x) + 
        morton3 (position.y)*2 +
        morton3 (position.z)*4;

هذا يتحول ثلاثية الأبعاد مؤشر إلى أحد الأبعاد واحدة.أفضل جزء من ذلك:القيم التي هي قريبة في الفضاء 3D هي قريبة في 1D الفضاء أيضا.إذا كنت الوصول إلى قيم قريبة من بعضها البعض في كثير من الأحيان سوف تحصل أيضا لطيفة جدا تسريع لأن مورتون النظام الترميز الأمثل من حيث ذاكرة التخزين المؤقت المحلية.

بالنسبة morton3 من الأفضل عدم استخدام التعليمات البرمجية أعلاه.استخدام طاولة صغيرة للبحث عن 4 أو 8 بت في الوقت نفسه و الجمع بينهما معا.

نأمل أن يساعد ، نيلز

Answer 3

الكتاب أسس متعددة الأبعاد و المقاييس هياكل البيانات يمكن أن تساعدك على أن تقرر أي هيكل البيانات أسرع مجموعة استفسارات:octrees دينار كويتي-الأشجار R-الأشجار ...كما توضح البيانات تخطيطات حفظ نقاط معا في الذاكرة.