Saturday, 16 August 2014

(#9)Bucket Addressing/ Perfect Hashing/Deletion

         මෙහිදී අප collide වන elements store කිරීම සඳහා වෙනම list එකක් හෝ table එකක් සූදානම් කරගෙන තබා ගනියි . එය bucket එක ලෙස හඳුන්වයි.  Collide වන elements link එකක් තබාගෙන bucket එකට add කිරීම සිදු කරයි.





Hash Table Organization







Perfect Hashing



Worste case එකද O(1) ට සමාන වන පරිදි hash table එකක් ගොඩනැගිය හැකිනම් එයට perfect hashing යැයි කියනු ලැබේ. මෙහිදී hash table එකේ collisions වැලැක්වීම සඳහා හැම slot එකකටම තවත් hash table එක බැගින් සම්බන්ධ කිරීම කරනු ලැබේ. මෙහිදී ප්‍රධාන hash table එක primary hash table ලෙසද අනිත් hash table එක secondary hash table (Sj) ලෙසද හඳුන්වනු ලබයි.





මෙහිදී collision විසදාගනු ලබන hash function එක outer hash function ලෙස හදුන්වනු ලබයි. එය පහත ලෙස නිර්මාණය කරයි.


                   h(k) = ( ( ak + b ) mod p )

මෙහි p යනු  key values වලට වඩා විශාල වන ඕනෑම ප්‍රථමක (prime ) සංඛ්‍යාවකි.

Sj  hash table එකේ j වන slot එකට ලැබෙන සියලුම keys ගබඩා  කරගනියි. එම hash table එකෙහි size ඒක mj ලෙස ගනිමු.
එවිට secondary hash function එක ,

           hj(k) = ( ( aj k + bj ) mod p ) mod mj  

 ලෙස වෙයි.
මෙහිදී secondary level එකේදී collisions ඇති නොවන පරිදි hash function එක තෝරාගැනීම වැදගත් වෙයි.


Deletion

· Chaining method  එකේදී link list එකේ ඇති element එක delete කිරීම මගින් අදාළ element එක delete කළ හැක.හේතුව chaining වලදී නිතරම collision එක ඇතිවූ slot එකේ සිට element එක ඇත්තටම store කළ ඇති slot එකට link එකක් තබාගැනීමයි.

· Open addressing කර ඇති hash table එකක elements delete කිරීම තරමක් අපහසු වෙයි. Collision එක ඇතිවූ slot එකේ සිට item එක store කරන slot එකට link එකක් තබා නොගැනීම එයට හේතුවයි. යම්කිසි slot එකකින් key එක delete කල පසු එහි NIL(null) node එකක් store කිරීමෙන් එය empty slot එකක් බවට පත්කළ නොහැකිය.





·Table එකක ඇති element එකක් delete කළ පසු එය empty බවට mark එකක් තැබිය හැක.එවිට නැවත item එකක් insert කිරීමට search කරගෙන යනවිට අදාළ slot එක empty slot එකක් ලෙස පෙන්වයි. නමුත් මෙහිදී කලින් store කර තිබූ item එක delete වීමක් සිදු නොවන අතර සිදු වන්නේ එම item එක උඩින් අලුත් item එක store වීමක් (overwrite) පමණි.

· විශාල items ප්‍රමාණයක් delete කිරීම search time එක වැඩි කරන අතර delete කරන ලද items test කිරීමට සිදුවීම එයට හේතුවයි.

·එම නිසා එලෙස items විශාල ප්‍රමාණයක් delete කර පසු table එක නැවතත් හිස්කිරීමක් පිරිසිදු කිරීමක් සිදු කලයුතුවෙයි.




Applications of Hash Tables







Monday, 11 August 2014

(#8) Chaining

                 මෙහිදී collision එකක් ඇතිවූ විට එම element  එක වෙනත් slot  එකකට යොමු කරයි. collision එක ඇතිවූ slot එක හා අළුත් element  එක store කළ slot එක අතර link එකක් තබා ගැනීමද සිදු කරයි.
          
Chaining වල ප්‍රධාන ආකාර තුනක් පවතියි.
 i) Separate Chaining
ii) Coalesced Chaining
iii) Overflow Area

 i) Separate Chaining


මෙහිදී හැම collisions ඇතිවන slot එකකටම link list එකක් සම්බන්ධ කර වැඩිපුර ලැබෙන elements , link list ඒක තුළ store කරනු ලබය




Chaining - Load Factor
      මෙහිදී table එකේ slot ප්‍රමාණයට වඩා වැඩි elements ප්‍රමාණයක් table ඒක තුළ store කරන නිසා load factor (α) , 1ට වඩා විශාල වීම සිදුවිය හැකියි.(α > 1)

Analysis of Chaining


Unseccessful Search
·        Link list එක තුළ අදාළ element ඒක නොමැති අවස්ථාව .
   
Search time = θ(1+α)

Successful Search

·        Link list එක තුළ අ
·        අදාළ element ඒක ඇති අවස්තාව.
  
  Search time = θ(1+α)




ii) Coalesced Chainig


   මෙය chaining හා linear probing යන දෙකෙහි එකතුවක් වශයෙන් සැලකිය හැකිය. Empty slot එකක් සොයාගෙන collision විසඳාගන්නා අතර නමුත් collision ඒක ඇතිවූ slot එකේ සිට element ඒක store කරන ලද slot එකට link එකක් තබාගනියි.





iii) Overflow Area


මෙහිදී table එකේ වෙනම කොටසක් collision සඳහා වෙන්කර තබයි. මෙහි ප්‍රධාන table ඒක primary area ලෙස හඳුන්වන අතර collision සඳහා වෙන්කර ඇති කොටස overflow area ලෙස හඳුන්වයි. Collision එකක් ඇති වූ විට එම element එක කලින් වෙන් කරන ලද overflow area එකේ ඇති slot එකක් තුළ store කරන අතර collision එක ඇතිවූ  slot එකට  link එකක් තබාගනියි.







Friday, 7 March 2014

(#5)Pigeonhole Principle

Pigeonhole Principle


පරවියන් රඳවා තබනු ලබන කුඩා කුටි  Pigeonholes  ලෙස හඳුන්වයි.අපි  n පරවියන් ප්‍රමාණයක් m Pigeonholes ප්‍රමාණයකට දමන්නේනම්  n > m  වෙයිනම් අඩු තරමින් එක Pigeonhole එකක හෝ පරවියන් එකකට වැඩියෙන් රැදී සිටිය යුතුය. මෙය Pigeonhole principle  ලෙස හැඳින්වෙයි.

මෙය සම්භාවිතා මූලධර්ම ඇසුරෙන් මෙලෙස පැහැදිලි කරගතහැකිය. n පරවියන් ප්‍රමාණයක් අහඹු ලෙස m Pigeonholes ප්‍රමාණයකට 1/m  යන ඒකාකාර සම්භාවිතාවකින් යුතුව දමන්නේ නම් එක Pigeonhole එකක හෝ පරවියන් එකකට වඩා රඳවා තබාගැනීමේ සම්භාවිතාව   
      1 – ( mn/mnවෙයි.
       මෙහි  mn  = mCn   වෙයි.

මෙලෙස එක Pigeonhole එකකට පරවියන් එකකට වඩා යොමුවීමක් collision එකක් ලෙස හඳුන්වයි. මෙමෙ මූලධර්මය අපි hash tables වලටද යෝදාගන්නෙමු.පහත උදාහරණයෙන් පැහැදිලිකරගනිමු.

  • What is the probability that no two hash keys collide(එකම storage location එකකට hash keys දෙකක් යොමුවීම.)?

මෙහිදී අසනු ලබන්නේ keys දෙකක් එකම slot එකකට යොමු නොවීමේ සම්භාවීතාවයි.
 h(k) = k mod 5
slots  5ක් ඇති table එකක් සලකමු.

  • පළමු item එක දැමීමේදී slot 5ම හිස් නිසා collide වීමක් සිදු නොවේ.එම නිසා collide නොවීමේ සම්භාවිතාව = 5/5 = 1 වෙයි.
  • දෙවන item එක දැමීමේදී හිස්ව ඇත්තේ slot 4ක් පමණි.එම නිසා collide වීමේ සම්භාවිතාව  1/5 කි.
  • එමනිසා collide නොවීමේ සම්භාවිතාව  = 4/5 ක්  වෙයි.
මෙලෙස,
  • 3 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 3/5
  • 4වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 2/5
  • 5 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 1/5
එමනිසා collide නොවීමේ මුළු සම්භාවිතාව = 5/5 * 4/5 * 3/5 * 2/5 * 1/5
                                                                         = 0.0384

එමනිසා keys 5ක් add කිරීමේදී එක collision එකක්
හෝ ඇති වීමේ සම්භාවිතාව  = 1- P5  = 1- 0.0384 = 0.9616

Collisions

hashing  වලදී මෙම collision ඇති කිරීම මගින් keys ප්‍රමාණයට වඩා slots අඩුවෙන් ඇති table එකක වුවද අපිට සියලුම keys store කරගතහැකිය. එමගින් අවශ්‍යකරන memory space එක අඩුකරගතහැකිය. යම්කිසි hash table එකක ඇතිවන collisions ප්‍රමාණය අවම වෙයිනම් hash table එක හොඳින් ක්‍රියා කරන්නේයැයි කියනු ලැබේ.එමගින් O(1) search time එකක් ලබාගතහැකිය.මෙහි worste case එක O(n) විය හැකිය.එය දුර්වල hash table එකක් ලෙස හඳුන්වයි.එමෙන්ම මෙම collisions විසඳා ගැනීමටද අප ක්‍රමවේදයන් කිහිපයක් අනුගමනය කරයි.

Handling the Collisions

i.Open Addressing
ii.Chaining
iii.Bucket Addressing



Sunday, 2 March 2014

(#4) Variables ,Data types ,Data type convertion

අප ලියන programme වලදී අපිට විවිධාකාරයේ data store කර තබාගැනීමට සිදුවෙයි.මෙවැනි data එකක් store කිරීම සඳහා memory space එකක් වෙන්කරගැනීම variable එකක් declare කිරීම ලෙස හැඳින්වෙයි.එලෙස වෙන් කරන ලද memory space එකක් තුළ data එකක් store කිරීම variable එකක් assign කිරීම ලෙස හැඳින්වෙයි.මෙහිදී විවිධාකාර data store කිරීම සඳහා විවිධාකාර වූ data types යොදා ගනියි.

Assigning Values to Variables:

අනෙකුත් languages වලමෙන් python වල variable එක මුලින් declare කර පසුව assign කිරීමක් සිදු කල නොහැකිය.variable එක declare කරන අවස්ථාවේම value එකද assign කල යුතුය.එමෙන්ම variable එකෙහි data type එක අපට define කල නොහැකි අතර අප එයට assign කරන value එක අනුව compiler එක මගින් data type එක හඳුනාගැනීම සිදු කරයි.

syntax:

variableName = value

උදා:

#!/usr/bin/python

counter = 100          # An integer assignment
miles   = 1000.0       # A floating point
name    = "John"       # A string

print counter
print miles
print name
Output:

100
1000.0
John

Multiple Assignment:

එකවර variables කිහිපයකට වුවද එකම අගය assign කල හැක.
උදා:
a = b = c = 1
පහත උදාහරණයේදී 
a=1
b=2
c="john"
ලෙස අගයන් assign වීම සිදුවෙයි.
 a, b, c = 1, 2, "john"

Standard Data Types:

python වල ප්‍රධාන data types 5ක් පවතියි.


  • Numbers
  • String
  • List
  • Tuple
  • Dictionary

Python Numbers:

මෙම data type එක සංක්‍යාත්මක අගයන් store කිරීම සඳහා යොදා ගනියි.

var1 = 1
var2 = 10
ඔබට del   යන key word එක යොදාගෙන assign කරනලද variables delete කිරීමද සිදු කල හැකිය.
del var1[,var2[,var3[....,varN]]]]
ඔබට මෙම key word එක යොදාගනිමින් object එකකට වඩා වැඩි ගණනක් වුවද delete කල හැක.
del var
del var_a, var_b
මෙහිදී numeric datatypes වර්ග හතරකි.
  • int (signed integers)
  • long (long integers [can also be represented in octal and hexadecimal])
  • float (floating point real values)
  • complex (complex numbers)

Examples:

Here are some examples of numbers:
intlongfloatcomplex
1051924361L0.03.14j
100-0x19323L15.2045.j
-7860122L-21.99.322e-36j
0800xDEFABCECBDAECBFBAEl32.3+e18.876j
-0490535633629843L-90.-.6545+0J
-0x260-052318172735L-32.54e1003e+26J
0x69-4721885298529L70.2-E124.53e-7j

Python Strings:

string එකක් assign කිරීමේදී single quotation හෝ double quotation යොදාගත යුතුය. (+) ලකුණ මගින් string දෙකක් join කල හැකි අතර (*) ලකුණ මගින් එකම string එක කිහිප වාරයක් print කරගත හැකිය.
#!/usr/bin/python

str = 'Hello World!'

print str          # Prints complete string
print str[0]       # Prints first character of the string
print str[2:5]     # Prints characters starting from 3rd to 5th
print str[2:]      # Prints string starting from 3rd character
print str * 2      # Prints string two times
print str + "TEST" # Prints concatenated string
This will produce the following result:
Hello World!
H
llo
llo World!
Hello World!Hello World!
Hello World!TEST

Python Lists:

එකම variable එකක් තුළ data කිහිපයක් store කරගැනීමට list එකක් භාවිතා කරයි.

syntax:
list = [item1,item2, item3]

#!/usr/bin/python

list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]
tinylist = [123, 'john']

print list          # Prints complete list
print list[0]       # Prints first element of the list
print list[1:3]     # Prints elements starting from 2nd till 3rd 
print list[2:]      # Prints elements starting from 3rd element
print tinylist * 2  # Prints list two times
print list + tinylist # Prints concatenated lists
This will produce the following result:
['abcd', 786, 2.23, 'john', 70.200000000000003]
abcd
[786, 2.23]
[2.23, 'john', 70.200000000000003]
[123, 'john', 123, 'john']
['abcd', 786, 2.23, 'john', 70.200000000000003, 123, 'john']

Python Tuples:

tuples , list වලටම සමාන data type එකක් වන අතර නමුත් tuple එකක් assign කල පසු එයට අලුතින් data add කිරීම හෝ තිබෙන data delete කිරීමක් සිදුකල නොහැක.නමුත් list එකක assign කරන data වලට අමතරව අලුතින් data add කිරීම මෙන්ම තිබෙන data delete කිරීමද සිදු කල හැකිය.

syntax:
tuple = (item1,item2, item3) මෙයට සාමාන්‍ය වරහන යොදාගනී.

#!/usr/bin/python

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
tinytuple = (123, 'john')

print tuple           # Prints complete list
print tuple[0]        # Prints first element of the list
print tuple[1:3]      # Prints elements starting from 2nd till 3rd 
print tuple[2:]       # Prints elements starting from 3rd element
print tinytuple * 2   # Prints list two times
print tuple + tinytuple # Prints concatenated lists
This will produce the following result:
('abcd', 786, 2.23, 'john', 70.200000000000003)
abcd
(786, 2.23)
(2.23, 'john', 70.200000000000003)
(123, 'john', 123, 'john')
('abcd', 786, 2.23, 'john', 70.200000000000003, 123, 'john')
Following is invalid with tuple, because we attempted to update a tuple, which is not allowed. Similar case is possible with lists:
#!/usr/bin/python

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
list = [ 'abcd', 786 , 2.23, 'john', 70.2  ]
tuple[2] = 1000    # Invalid syntax with tuple
list[2] = 1000     # Valid syntax with list

Python Dictionary:

dictionary එකක් යනු එකවර data විශාල ප්‍රමාණයක් store කරගත් හැකි data type එකකි.එය table එකකට සමාන වෙයි.
dictionary එක assign කිරීම සඳහා {} යොදාගන්නා අතර එයට data add කිරීම සඳහා [] යොදාගනියි.
උදා:

#!/usr/bin/python

dict = {}
dict['one'] = "This is one"
dict[2]     = "This is two"

tinydict = {'name': 'john','code':6734, 'dept': 'sales'}


print dict['one']       # Prints value for 'one' key
print dict[2]           # Prints value for 2 key
print tinydict          # Prints complete dictionary
print tinydict.keys()   # Prints all the keys
print tinydict.values() # Prints all the values
This will produce the following result:
This is one
This is two
{'dept': 'sales', 'code': 6734, 'name': 'john'}
['dept', 'code', 'name']
['sales', 6734, 'john']
Dictionaries have no concept of order among elements. It is incorrect to say that the elements are "out of order"; they are simply unordered.

Data Type Conversion:

එක් data type එකකින් assign කර ඇති data එකක් තවත් data type එකක් බවට පරිවර්තනය කල හැක.ඒ සඳහා python වල සකසන ලද විශේෂ functions කිහිපයක් පවතී. ඒවා පහත දැක්වෙයි.

FunctionDescription
int(x [,base])
Converts x to an integer. base specifies the base if x is a string.
long(x [,base] )
Converts x to a long integer. base specifies the base if x is a string.
float(x)
Converts x to a floating-point number.
complex(real [,imag])
Creates a complex number.
str(x)
Converts object x to a string representation.
repr(x)
Converts object x to an expression string.
eval(str)
Evaluates a string and returns an object.
tuple(s)
Converts s to a tuple.
list(s)
Converts s to a list.
set(s)
Converts s to a set.
dict(d)
Creates a dictionary. d must be a sequence of (key,value) tuples.
frozenset(s)
Converts s to a frozen set.
chr(x)
Converts an integer to a character.
unichr(x)
Converts an integer to a Unicode character.
ord(x)
Converts a single character to its integer value.
hex(x)
Converts an integer to a hexadecimal string.
oct(x)
Converts an integer to an octal string.