நெறிமுறையின் செயல்திறன்

நெறிமுறையின் செயல்திறன்

கணினி வளங்கள் எல்லைக்குட்பட்டதால் திறம்பட அதனை பயன்படுத்த வேண்டும். நெறிமுறையின் செயல்திறன் என்பது நெறிமுறை பயன்படுத்தும் கணக்கீட்டு (computational) வளங்களின் எண்ணிக்கையை வரையறுக்கும். நெறிமுறையின், பகுப்பாய்வு அதனுடைய வளங்களின் பயன்பாட்டைத் பொருத்து தீர்மானிக்கப்படுகிறது. பல்வேறு வளங்களின் பயன்பாட்டின் அடிப்படையில் நெறிமுறையின் செயல்திறனை அளவிட வேண்டும்.

நெறிமுறையின் அதிகபட்ச செயல்திறனுக்காக வளங்களின் பயன்பாட்டைக் குறைக்க விரும்புகிறேம். எனினும், வெவ்வேறு வளங்களான நேரம் மற்றும் இடச்சிக்கல் ஆகியவற்றை நேரடியாக ஒப்பிட முடியாது. இருப்பினும், இவை, இரண்டும் நெறிமுறையின் செயல்திறனுக்கு கருதப்பட வேண்டும்.

1. செயல்திறனைத் தீர்மானிக்கம் வழிமுறை (Method for determining Efficiency)

நெறிமுறையின் செயல்திறன், நேரத்தையும், நினைவக இருப்பிடத்தையும் எவ்வாறு அது திறமையாகப் பயன்படுத்துகிறது என்பதைத் பொறுத்ததாகும்.

நெறிமுறையின் நேர செயல்திறனை அளவிடுவதற்கு பல்வேறு காரணிகள் உள்ளன. எடுத்துக்காட்டாக ஒரு நிரலாக்க மொழியின் அடிப்படையில் நிரலை எழுதி, அதனைச் செயல்படுத்தி, அது இயக்குவதற்கு எடுத்துக் கொள்ளும் நேரத்தை அளவிடவும். இங்கு, அளவிடப்படும் இயங்கு நேரம் பின்வரும் காரணிகளைப் பொறுத்ததாகும்:

• இயந்திரத்தின் வேகம்

• நிரல்பெயர்ப்பி மற்றும் பிற கணினி மென்பொருள் கருவிகள்

• இயக்க அமைப்பு

• பயன்படுத்தப்பட்ட நிரலாக்க மொழி

•  தரவு தொகுதி.

ஒரு நெறிமுறை கொடுக்கப்பட்ட ஒரு சிக்கலை எவ்வாறு திறனுடன் தீர்க்கிறது என்பதை கண்டறிய அதன் இயக்க நேரம் எவ்வாறு அந்நெறிமுறையின் இயல்பை பாதிக்கிறது என்பதை கண்டறிய வேண்டும். எனவே, நெறிமுறையின் இயல்பில் ஒரு நிரலின் செயல்திறனை தீர்மானிக்கும் அடிப்படை விதிகளை வகுக்க வேண்டும்.

நெறிமுறையை வடிவமைக்கும் வழிமுறையே நெறிமுறை யுக்தி ஆகும்.

2 இடம் நேரம் பரிமாற்றம்

இடம் நேரம் பரிமாற்றம் அல்லது நேரம் நினைவகம் பரிமாற்றம் என்பது குறைந்த நேரத்தில் அதிகமான சேமிக்கும் இடத்தைப் பயன்படுத்தி நெறிமுறையை தீர்க்கும் வழியாகும்.

கொடுக்கப்பட்ட நிரலாக்கத்தின் சிக்கலைத் தீர்ப்பதற்கு பல விதமான நெறிமுறைகளைப் பயன்படுத்தலாம். அதில் சில நெறிமுறைகள் மிகவும் நேர செயல்திறன் உடையதாகவும் மற்றும் சில நெறிமுறைகள் மிகவும் இட செயல்திறன் உடையதாகவும் இருக்கும்.

நேரம் / இடம் பரிமாற்றம் என்பது மெதுவான நிரல் இயங்கு நேரத்தில் நினைவகப் பயன்பாட்டைக் குறைக்கும் நிலைமையை அல்லது அதிகமான நினைவக பயன்பாட்டில் இயங்கு நேரத்தைக் குறைக்கும் நிலைமையைக் குறிப்பதாகும்.

நினைவகத்தில் தேவைப்படும் குறைந்த இடத்தையும் மற்றும் அதன் கட்டளைகளை இயக்குவதற்கு குறைந்த நேரத்தையும் எடுத்துக்கொண்டு வெளியீட்டினை வெளியிடும் நெறிமுறையே கொடுக்கப்பட்ட சிக்கலைத் தீர்க்கும் சிறந்த நெறிமுறையாகும்.

3. Asymptotic குறியீடுகள்

இந்த Asymptotic குறியீடுகள் நேரம் மற்றும் இடச்சிக்கலைகளைப்பற்றிய அர்த்தமுள்ள கூற்றுகளைப் பயன்படுத்தும் ஒரு மொழியாகும். பின்வரும் மூன்று Asymptotic குறியீடுகள் நெறிமுறையில் நேரச் சிக்கலைக் குறிக்கும் மிகவும் பயன்படுகிறது.

1. Big O

நெறிமுறையின் மிக மோசமான நிலையை விவரிக்க Big O பெரும்பாலும் பயன்படுத்தப்படுகிறது.

2. Big Ω  

Big Omega, Big O-வின் தலைகீழ் ஆகும். Big O-asymptotic (மோசமான நிலையில்) செயற்கூறின் உச்ச வரம்பையும், Big Omega அதன் கீழ்வரையை குறிக்கும் (சிறந்த நிலையில்).

3. Big ɵ

நெறிமுறையானது கீழ் எல்லை = மேல் எல்லை என்னும் சிக்கலைக் கொண்டிருந்தால், உதாரணத்திற்கு O(n log n) மற்றும் Ω(n log n),  ஆகிய சிக்கல்களைக் கொண்டுள்ளது என வைத்துக் கொள்வோம். உண்மையில் அதனுடைய சிக்கல் © (n log n), என்பது ஆகும். இதனுடைய அர்த்தம் என்னவென்றால் நெறிமுறையின் இயங்கு நேரம் மிகச் சிறந்த நிலை மற்றும் மிக மோசமான நிலை ஆகிய இரண்டு நிலையிலுமே எப்பொழுதும் n log n ஆக இருக்கும்.

4. சிறந்த, மோசமான மற்றும் சராசரி நிலைகளின் செயல்திறன்

எடுத்துக்காட்டாக, ஒரு அணியில் n-மதிப்புகள் உள்ளதாக வைத்துக் கொள்வோம். இந்த பட்டியலில் இருந்து ஒரு குறிப்பிட்ட உறுப்பைத் தேட வேண்டும். நெறிமுறையானது n-உறுப்புகளைக் கொண்ட பட்டியலில் இருந்து தேட வேண்டிய பட்டியலில் உள்ள ஒவ்வொரு உறுப்புகளோடு வரிசையாக ஒப்பீடு செய்து உருப்புகளை பட்டியலில் ஒவ்வொன்றாக அதன் முதன்மை உறுப்பை கொண்டு ஒப்பிட வேண்டும்.

இந்த எடுத்துக்காட்டில், பட்டியலில் உள்ள முதல் உறுப்பு தேடப்படும் உறுப்போடு பொருத்தமாக இருந்தால் அது தான் மிகச் சிறந்த நிலையாகும். இந்த நிலையின் செயல்திறனை O(1) என்று வெளிப்படுத்தலாம். ஏனெனில், ஒரே ஒரு ஒப்பீடுதான் தேவைப்படுகிறது.

அதைப்போல, இந்த எடுத்துக்காட்டில், பட்டியல் முழுவதற்கும் சென்று தேடினால், அந்த உறுப்பு பட்டியலின் இறுதியில் கண்டுபிடிக்கப்பட்டால் அல்லது பட்டியலில் இல்லாமல் இருந்தால் அதுதான் மோசமான நிலையாகும். இந்த நிலையின் செயல்திறனை O(n) என்று வெளிப்படுத்தலாம். ஏனென்றால், n ஒப்பீடுகள் செய்யப்படுகின்றன.

அதே எடுத்துக்காட்டுடன் தொடர்ந்தால் சராசரி ஒப்பீடுகளின் எண்ணிக்கையைக் கண்டுபிடிப்பதன் மூலம் சராசரி நிலையின் செயல்திறனைப் பெறலாம். இங்கு,

குறைந்தபட்ச ஒப்பீடுகளின் எண்ணிக்கை = 1

அதிகப்பட்ச ஒப்பீடுகளின் எண்ணிக்கை = n

கண்டுபிடிக்கப்படாத உறுப்பின் அதிகபட்ச ஒப்பீடுகளின் எண்ணிக்கை = n

எனவே, சராசரி ஒப்பீடுகளின் எண்ணிக்கை = (n +1)/2

ஆகையால், சராசரி நிலையின் செயல்திறனை O(n) என்று வெளிப்படுத்தலாம்.