• 0
Khaled Alshaya

مثال في الـ metaprogramming لحساب ناتج حساب أنواع

بواسطة Khaled Alshaya,

سؤال

تم النشر منذ

السلام عليكم,

خلال تطوير uint, صادفت العديد من المشاكل(لاحصر لها :lol:) و لكن إحدى الحلول تضمنت الـ metaprogramming على أصول. القضية, أن المستخدم يقوم بكتابة شيء مشابه للتالي:

// unsigned integer: 128 bits
uint<128> number;

هذه المئة و ثمانية و عشرون bits سوف تخزن في مصفوفة بكل تأكيد, و لكن ماهو نوع هذه المصفوفة؟

unsigned char
unsigned short int
unsigned int
unsigned long
unsigned long long

أضف لذلك, أن المكتبة لاتقبل كسوراً, مثلاً لا يوجد لدي عدد من الـ bits يكون مصفوفة مكونة من ثلاث عناصر "و ربع". باختصار, الحل كان لابد أن يكون من الشكل التالي:

template <std::size_t size>
struct type_factory
{
	typedef typename type_factory_impl<size>::type type;
};

int main()
{
	auto a = type_factory<8>::type(0);  // unsigned char
	auto b = type_factory<16>::type(0); // unsigned short int
	auto c = type_factory<24>::type(0); // unsigned char
	auto d = type_factory<32>::type(0); // unsigned long
	auto e = type_factory<40>::type(0); // unsigned char
	auto f = type_factory<48>::type(0); // unsigned short int
	auto g = type_factory<56>::type(0); // unsigned char
	auto h = type_factory<64>::type(0); // unsigned long long
}

و الخوارزمية المتبعة في اختيار النوع المناسب:

if(size % bits<unsigned long long>::value == 0)
	typedef unsigned long long type;
else if(size % bits<unsigned long>::value == 0)
	typedef unsigned long type;
else if(size % bits<unsigned int>::value == 0)
	typedef unsigned int type;
else if(size % bits<unsigned short int>::value == 0)
	typedef unsigned short int type;
else if(size % bits<unsigned char>::value == 0)
	typedef unsigned char type;
else
	static_assert(false, "The type should be multiple of 'unsigned char' size");

الحقيقة كان الحل ممتعاً, و خارجاً عن المألوف. حللت المشكلة بطريقتين: الأولى باستخدام الـ pattern matching أو ما يطلق عليه partial template specialization. فكرت قليلاً, ثم قمت بعمل refactoring لأن الكود و إن كان سهل الفهم نسبياً, إلا أنه طويل. لذلك قمت بكتابة meta if-else و اختصرت الحل :wink:

بالنسبة للحل الأول:


#include <cstddef>
#include <climits>

typedef unsigned char      uchar;
typedef unsigned short int usint;
typedef unsigned int       uint;
typedef unsigned long      ulong;
typedef unsigned long long ulonglong;

// Returns how many bits in Unsigned_Type
template <typename Unsigned_Type>
struct bits
{ enum { value = sizeof(Unsigned_Type)*CHAR_BIT }; };

template <bool is_uchar>
struct unsigned_char
{
	typedef unsigned char type;
	static_assert(is_uchar,
     "error: size must be multiple of 'unsigned char' size"); 
};
template <>
struct unsigned_char <true>
{ typedef uchar type; };

template <bool is_usint, std::size_t size>
struct unsigned_short_int
{ typedef typename
   unsigned_char<size % bits<uchar>::value == 0>::type type; };
template <std::size_t size>
struct unsigned_short_int <true, size>
{ typedef usint type; };

template <bool is_uint, std::size_t size>
struct unsigned_int
{ typedef typename
   unsigned_short_int<size % bits<usint>::value == 0, size>::type type; };
template <std::size_t size>
struct unsigned_int <true, size>
{ typedef uint type; };

template <bool is_ulong, std::size_t size>
struct unsigned_long
{ typedef typename
   unsigned_int<size % bits<uint>::value == 0, size>::type type; };
template <std::size_t size>
struct unsigned_long <true, size>
{ typedef ulong type; };

template <bool is_ulonglong, std::size_t size>
struct unsigned_long_long
{ typedef typename 
   unsigned_long<size % bits<ulong>::value == 0, size>::type type; };
template <std::size_t size>
struct unsigned_long_long <true, size>
{ typedef ulonglong type; };

template <std::size_t size>
struct type_factory_impl
{ typedef typename 
   unsigned_long_long<size % bits<ulonglong>::value == 0, size>::type type; };

template <std::size_t size>
struct type_factory
{
	typedef typename type_factory_impl<size>::type type;
};

int main()
{
	auto a = type_factory<8>::type(0);  // unsigned char
	auto b = type_factory<16>::type(0); // unsigned short int
	auto c = type_factory<24>::type(0); // unsigned char
	auto d = type_factory<32>::type(0); // unsigned long
	auto e = type_factory<40>::type(0); // unsigned char
	auto f = type_factory<48>::type(0); // unsigned short int
	auto g = type_factory<56>::type(0); // unsigned char
	auto h = type_factory<64>::type(0); // unsigned long long
}

أما الحل الثاني:


#include <cstddef>
#include <climits>

typedef unsigned char      uchar;
typedef unsigned short int usint;
typedef unsigned int       uint;
typedef unsigned long      ulong;
typedef unsigned long long ulonglong;

// Returns how many bits in Unsigned_Type
template <typename Unsigned_Type>
struct bits
{ enum { value = sizeof(Unsigned_Type)*CHAR_BIT }; };

template <bool condition, typename Then, typename Else>
struct IF
{ typedef Else type; };
template <typename Then, typename Else>
struct IF <true, Then, Else>
{ typedef Then type; };

template <std::size_t size>
struct type_factory_impl
{
	typedef typename
		IF<size % bits<ulonglong>::value == 0, ulonglong,
			typename IF<size % bits<ulong>::value == 0, ulong,
				typename IF<size % bits<uint>::value == 0, uint,
					typename IF<size % bits<usint>::value == 0, usint,
						typename IF<size % bits<uchar>::value == 0, uchar, uchar>::type
					>::type
				>::type
			>::type
		>::type type;
};

template <std::size_t size>
struct type_factory
{
	typedef typename type_factory_impl<size>::type type;
};

int main()
{
	auto a = type_factory<8>::type(0);  // unsigned char
	auto b = type_factory<16>::type(0); // unsigned short int
	auto c = type_factory<24>::type(0); // unsigned char
	auto d = type_factory<32>::type(0); // unsigned long
	auto e = type_factory<40>::type(0); // unsigned char
	auto f = type_factory<48>::type(0); // unsigned short int
	auto g = type_factory<56>::type(0); // unsigned char
	auto h = type_factory<64>::type(0); // unsigned long long
}

استخدمت static_assert و auto في visual studio 2010. لن أشرح الكود, لأني لا أعرف من أين أبدأ في شرحه. و لكن أرحب بأي سؤال أو مناقشة أو مثال آخر.

تحياتي...

4

شارك هذا الرد

رابط المشاركة
شارك الرد من خلال المواقع ادناه

2 إجابة على هذا السؤال .

  • 0

قام بالرد منذ

لم أفهم كل شيء ، طريقة template specialization أكثر وضوحاً من meta التي و الحمد لله لم أفهم منها شيء إطلاقاً :/ . عندما قرأت في العنوان metaprogramming ، " خلت " أنك تستخدم macro بسيط define# :-) .

سؤالي هو حول auto ، هل لها بديل في المواصفات الحالية ؟ استخدم الآن VS 2008 .

لأني بصراحة ، لم أفهم النقطة التي أدت لكل هذا ، ( المعذرة ، فلم أتابع مشروعكم ) ، لكن اسمح لي أن أفهم المشكلة أولاً :

ما فهمته أنك ستقوم بتخزين البتات في مصفوفة ، وكان يمكنكم اختيار أبسط نوع ،و بالتالي يظهر بهذا الشكل :


		// with  : uint<10> number;
		bool bitsArray_first[10] = {1,1,1,1,1,1,1,1,0,1 };
		std::cout << int(bitsArray_first[9] + bitsArray_first[8])   << std::endl;

		// output :
		//  1 + 0 = 1 ;

لكن بعد أن فكرتكم بتسريع الخوارزمية ، أنت تريد من المعالج أن يقوم بحساب العمليات الرياضية لأقصى نوع ممكن ، لذلك بدلاً من تقسم 10 بت إلى 10 أقسام كل قسم يحوي " بت " واحد ، صار يمكنكم تقسيمها إلى قسمين 8-بت لكل قسم ، وبالتالي تستخدم النوع unsigned char ، وبالتالي ستسفيدون من سرعة المعالج لحساب بعض الأجزاء ،بهذا الشكل :


		// with  : uint<10> number;
		const unsigned int size_of_array =(unsigned int) ceil(10.0f/(sizeof(unsigned char)*CHAR_BIT));
		unsigned char *bitsArray_second  = new unsigned char [size_of_array];
		bitsArray_second[0] = 0xFF;
		bitsArray_second[1] = 0x01;

		std::cout << "size of array " << size_of_array << std::endl;
		std::cout << (int)bitsArray_second[1] + (int)bitsArray_second[0]   << std::endl;

		delete bitsArray_second;
		// output :
		//  255 + 1 = 256 ;

من هنا فكرّت باستخدام metaprogramming لمحاولة استنتاج نوع المصفوفة و طولها ؟

هل فهمي صحيح للمشكلة التي أدت لكل هذا :wacko: ؟

1

شارك هذا الرد

رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

قام بالرد منذ (معدل)

:)

المشكلة يا عزيزي, هي أني لا أقوم بحساب ناتج الـ Arbitrary Precision Number(المكتبة التي نتكلم عنها) من خلال حساب الـ bits. أنا لا أبني معالج, و إنما سأقوم بتقسيم الـ bits إلى digits من base أكبر كـ hex أو 256 أو أكبر. بهذه الطريقة, يمكنك تخيل أن لدي أدوات جاهزة في اللغة للتعامل مع الـ digit فقط و لدي جميع العمليات الحسابية و المنطقية التي أحتاجها, و يبقى على المكتبة بناء arithmetic system لعدد متغير من الـ digits. لذلك, كلما كان الـ digit و الذي في هذه الحالة هو unsigned char أو unsigned long أو واحداً من باقي الأنواع - أكبر و يستطيع استيعاب base أكبر, قمنا بتقليل عدد العمليات اللازمة بشكل كبير. تصور معي العدد ذو 128 bits. لو قمنا بتنفيذ عملية كالضرب عليه, سنقسمه إلى digits لكي نقوم بالعمليات الحسابية. لو كان الـ digit عبارة عن bit فسنحتاج إلى 128*128 عملية في خوارزميات الضرب السهلة. بينما لو قسمنا العدد إلى unsigned long long ستصبح النتيجة على بعد 2*2 عمليات. باختصار, لو أخذنا bits و قسمناها إلى مصفوفة من أكبر نوع, هل سنحتاج إلى padding bits غير مستعملة في النهاية؟ إذا كان كذلك, قم بمحاولة تقسيمه إلى نوع أصغر و هكذا.

سؤالي هو حول auto ، هل لها بديل في المواصفات الحالية ؟ استخدم الآن VS 2008 .

للأسف لا أعتقد أنها موجودة. و لكن يمكنك تجربة 2010 فهو جميل جداً بالمناسبة. و به الكثير من مكتبات 0x و تقريباً خمس ميزات في اللغة من ضمنها auto. باختصار, هي تعمل type inference تمام كـ var في #C.

إذا كنت تريد تجربة الكود بدون auto فاستخدم الطريقة التالية في تعريف الأنواع, و لا أعتقد أن auto في هذه الحالة له تفوق كبير:

type_factory<64>::type i = 0;

إضافة إلى ذلك, قم بإزالة السطر الذي يتضمن static_assert. هذه عبارة عن compile-time tool لكي تقوم بإصدار أخطاء "مفهومة" تقوم أنت بكتابتها بنفسك و هي ميزة رائعة جداً للمكتبات.

لم أفهم كل شيء ، طريقة template specialization أكثر وضوحاً من meta التي و الحمد لله لم أفهم منها شيء إطلاقاً :/ . عندما قرأت في العنوان metaprogramming ، " خلت " أنك تستخدم macro بسيط define# :-) .

طريقة الـ partial specialization بالفعل أسهل عند النظر لأول مرة. و لكن الـ meta-if أسهل في التفكير و الكتابة عندما تمعن النظر فيها قليلاً. كل ما في الأمر, أن IF ستستقبل condition, فإذا كان صحيحاً ستقوم بإعادة النوع Then. إذا لم يكن صحيحاً ستقوم بإعادة النوع Else :)

الآن, سنقول لو أن bits يمكن تقسيمها إلى مصفوفة unsigned long long تماماً, سنعيد النوع unsigned long long. إذا لم يكن كذلك, سنقوم بإعادة النوع Else. النوع Else في هذه الحالة هو نوع يتم حسابه من خلال IF أخرى, و التي ستعيد unsigned long في حالة تحقق الشرط, و إذا لم يكن كذلك سنختبر النوع الأصغر في Else و هكذا حتى نصل إلى unsigned char. بالطبع الاختلاف بين المثال الأول و الثاني, هو أن الأول سيصدر خطأ في حالة كون bits لا تقسم تماماً إلى unsigned char array. بينما في meta-if لم أستطع حل هذه المشكلة حتى الآن.

تحياتي...

تم تعديل بواسطه Khaled.Alshaya
2

شارك هذا الرد

رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان
إذهب إلى قائمة الأسئلة لغة C و ++C

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .