pythainlp/thai_wikipedia_clean_20230101 huggingface dataset:
3. Allocation : เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้ ถ้า Allocation[i,j] = k หมายถึงโพรเซส i กำลังใช้งานทรัพยากรชนิด j อยู่ เป็นจำนวน k บริการ
4. Need : เมตริกซ์ขนาด n x m เพื่อบ่งบอกจำนวนทรัพยากรที่เหลือที่ยังต้องการใช้ของแต่ละโพรเซส เช่น Need[i,j] = k หมายถึงโพรเซส i ยังคงต้องการใช้งานทรัพยากร j อยู่อีก k บริการ
พบว่า Need[i,j] = Max[i,j] – Allocation[i,j]
อัลกอริทึมของการขอใช้ทรัพยากร.
กำหนดให้ Request i เป็นเวกเตอร์ของการขอใช้งานสำหรับโพรเซส i ถ้า request i[j] = k หมายถึงโพรเซส i ต้องการทำงาน k บริการจากทรัพยากร j เมื่อมีการขอใช้งานทรัพยากรโดยโพรเซส i ก็ จะเกิดการทำงานดังต่อไปนี้
1. ถ้า Request i ≤ Need i ไปยังขั้นตอนที่ 2 นอกจากนั้น ให้แสดงข้อความเตือน เนื่องจากโพรเซสมีการใช้ทรัพยากรมากกว่าที่คาดการณ์ไว้
2. ถ้า Request i ≤ Available ไปยังขั้นตอนที่ 3 นอกจากนี้โพรเซส i ต้องรอเนื่องจากทรัพยากรไม่มีให้ใช้งาน
3. มีการตั้งระบบลวงเพื่อใช้ทรัพยากรที่โพรเซส i ขอใช้โดยการใส่ค่าในตัวแปรต่อไปนี้
Available = Available – Request;
Allocation i = Allocation i + Request i ;
Need i = Need i – Request i ;
ถ้าผลของการกำหนดค่าการให้ใช้ทรัพยากรออกมา พบว่าระบบอยู่ในภาวะปลอดภัย ก็จะจบสิ้นการทำงานแล้วยอมให้โพรเซส i ใช้งานทรัพยากรนั้นจริง ๆ อย่างไรก็ตามถ้าผลออกมาว่าไม่ปลอดภัย โพรเซส i ต้องรอ Request i แล้วก็จะกลับไปสู่ค่าสถานะเก่า
Banker’s algorithm จะแบ่งสถานะออกเป็น 2 สถานะคือ.
สถานะไม่ปลอดภัย (Unsafe State) เมื่อระบบอยู่ใน Unsafe state จะไม่มี process ใดทำงานได้สำเร็จ เนื่องจาก process ต่างๆ ร้องขอใช้ทรัพยากรตามจำนวนสูงสุดที่สามารถจะใช้ได้ แต่ระบบไม่สามารถจัดสรรทรัพยากรให้กับงานต่างๆได้จึงเกิด deadlock ขึ้น
สถานะปลอดภัย (Safe State) เมื่อระบบอยู่ใน safe state เมื่อจัดอันดับการใช้ resource ให้กับ process แล้วไม่เกิด deadlock
ตัวอย่างขั้นตอนวิธีของนายธนาคาร.
Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
หา Need จาก Max - Allocation
จะได้ Need
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
จัดอันดับการใช้ Resource ได้ดังนี้
Need ≤ Available
A B C A B C
P0 7 4 3 ≤ 3 3 2 ; False
P1 1 2 2 ≤ 3 3 2 ; True ; Work = available + allocation = 332 + 200 = 532
P2 6 0 0 ≤ 5 3 2 ; False
P3 0 1 1 ≤ 5 3 2 ; True ; Work = 532 + 211 = 743
P4 4 3 1 ≤ 6 4 3 ; True ; Work = 743 + 002 = 745
P0 7 4 3 ≤ 7 4 5 ; True ; Work = 745 + 010 = 755
P2 6 0 0 ≤ 7 5 5 ; True ; Work = 755 + 302 = 10 5 7
เรียงลำดับการใช้ Process ได้ดังนี้ P1,P3,P4,P0,P2 จึงจะไม่เกิด Deadlock เพราะอยู่ใน Safe state
def bankers(E,A,C,R):
n,m = len(C), len(C[0])
terminatedProcesses = []
deadlock = False
while len(terminatedProcesses) &lt; n and not(deadlock):
deadlock = True
if i in terminatedProcesses:
elif all([R[i][j] &lt;= A[j] for j in range(m)]):
# required resources are given to process i
# process i terminates and gives all his resources back
A = [C[i][j] + A[j] for j in range(m)]
terminatedProcesses.append(i)
#print (i, A)
return not(deadlock), terminatedProcesses
รายการตอนในวันพีซ (อะนิเมะ)
รายการภาพยนตร์ไทยที่เสนอเข้าชิงรางวัลออสการ์ สาขาภาพยนตร์ภาษาต่างประเทศยอดเยี่ยม
ลิงค์ลิสต์แบบสองทิศทาง
ลิงค์ลิสต์แบบสองทิศทาง (Doubly Linked List).
ได้เป็นโครงสร้างของข้อมูลไว้ในnodeเป็นลำดับ โดยแต่ละnodeจะประกอบไปด้วยข้อมูลและpointer 2ตัว ชี้ไปยังnode ถัดไปและอีกหนึ่งตัวชี้ไปยังnodeถัดไปและอีกหนึ่งตัวชี้ไปยังnodeก่อนหน้า ยกเว้นnodeแรกที่Pointer สำหรับชี้ไปnode ก่อนหน้าจะชี้ไปที่nullและnode สุดท้ายที่pointer สำหรับชี้ไปnodeถัดไปจะชี้ไปที่null ถ้านํา node มาเรียงต่อๆกัน เป็นลำดับจะได้doubly linked list ของข้อมูล n ตัวโดยจะกำหนดให้มี pointer อย่างน้อย1ตัวที่ชี้ไปยังnodeตัวแรกของdoubly linkedlist เสมอ
doubly linked lists.
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.prev = None
# Class to create a Doubly Linked List
class DoublyLinkedList:
# Constructor for empty Doubly Linked List
self.head = None
การเพิ่มnode.
2.1 การเพิ่มnode ข้างหน้า
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
2.1 การเพิ่มnode ข้างหลัง
def append(self, new_data):
new_node.next = None
if self.head is None:
new_node.prev = None
last = self.head
while(last.next is not None):
last = last.next
last.next = new_node
new_node.prev = last
การลบnode.
def delete(self, valueToDelete):
currentNode = self.head
previousNode = None
while currentNode is not None:
if currentNode.data == valueToDelete:
if previousNode is None:
newHead = currentNode.next
currentNode.next = None
return newHead # Deleted the head
previousNode.next= currentNode.next
return self.head
previousNode = currentNode
currentNode = currentNode.next
return self.head# Value to delete was not found.
การค้นหาnode.
def search(self,data):
node = self.head
while (node and node.data != data):
node = node.next
return node.data
def printList(self):
output = '['
output += str(currentNode.data)
if currentNode is not None:
output += ', '
output += ']'
การเรียงลำดับแบบค็อกเทลเชกเกอร์
การเรียงลำดับแบบค็อกเทลเชกเกอร์ ยังเป็นที่รู้จักกันในนามฟองเรียงลำดับ เรียงระลาดเรียงสับเปลี่ยน หรือกระสวยเรียงเป็น รูปแบบของฟองสบู่ที่มีทั้งแบบอัลกอริทึมการจัดเรียงที่มีเสถียรภาพและการเรียงลำดับการเปรียบเทียบ อัลกอริทึมจะแตกต่างจากการจัดเรียงแบบฟองสบู่ในแบบที่เรียงตามทั้งสองทิศทางในแต่ละการผ่านรายการ อัลกอริทึมการเรียงลำดับนี้เป็นเพียงเล็กน้อยยากที่จะใช้มากกว่าการเรียงลำดับฟองและแก้ปัญหาของเต่าในฟองสบู่ จะให้การปรับปรุงประสิทธิภาพเพียงเล็กน้อยและไม่เพิ่มประสิทธิภาพการทำงานแบบไม่ประจำตัว เช่นการเรียงลำดับฟองสบู่ก็ไม่ได้เป็นที่น่าสนใจในทางปฏิบัติ (การจัดเรียงแทรกเป็นที่ต้องการสำหรับประเภทที่เรียบง่าย) แม้ว่าจะพบว่ามีประโยชน์บางอย่างในด้วย
การเรียงลำดับแบบค็อกเทล ชาร์คเกอร์ ซอร์ต  เป็นการปรับปรุงรูปแบบการจัดเรียงแบบ Bubble sort ให้ทำงานได้ดีขึ้น ด้วยการเพิ่มขึ้นตอนการจัดเรียงขึ้นอีกกระบวนการหนึ่ง โดยวิธีการจัดเรียงสองทางสลับกัน
ซูโดโค้ด
procedure cocktailShakerSort( A : list of sortable items ) defined as:
swapped := false
for each i in 0 to length( A ) - 2 do:
if A[ i ] &gt; A[ i + 1 ] then // test whether the two elements are in the wrong order
swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
if not swapped then
// we can exit the outer loop here if no swaps occurred.
break do-while loop
for each i in length( A ) - 2 to 0 do:
if A[ i ] &gt; A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
while swapped // if no elements have been swapped, then the list is sorted
ช่องทางด้านขวาแรกจะเปลี่ยนองค์ประกอบที่ใหญ่ที่สุดไปยังตำแหน่งที่ถูกต้องในตอนท้ายและทางออกด้านซ้ายต่อไปนี้จะเปลี่ยนองค์ประกอบที่เล็กที่สุดไปยังตำแหน่งที่ถูกต้องในตอนเริ่มต้น การส่งผ่านครั้งที่สองเสร็จสมบูรณ์จะเปลี่ยนองค์ประกอบที่เล็กที่สุดเป็นอันดับสองและใหญ่เป็นอันดับสองไปยังสถานที่ที่ถูกต้องและอื่น ๆ หลังจากที่ฉันผ่านฉัน i แรกและองค์ประกอบ i ล่าสุดในรายการอยู่ในตำแหน่งที่ถูกต้องและไม่จำเป็นต้องได้รับการตรวจสอบ โดยการย่อส่วนของรายการที่เรียงลำดับในแต่ละครั้งจำนวนการดำเนินการสามารถลดลงครึ่งหนึ่ง (ดูการจัดเรียงแบบฟอง)
def cocktail_shaker_sort(array):
for i in range(len(array)-1, 0, -1):
for j in range(i):
if array[j] &gt; array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
print(array)
for j in range(i, 0, -1):
if array[j] &lt; array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
if not swapped:
user_input = raw_input('Enter numbers Ex.[1,0,8,9]:\n').strip
array = [int(x) for x in user_input.split(',')]
print(cocktail_shaker_sort(array))
ความแตกต่างจากการจัดเรียงแบบฟองสบู่
ตัวอย่างของรายการที่พิสูจน์จุดนี้คือรายการ (2,3,4,5,1) ซึ่งจะต้องผ่านการจัดเรียงค็อกเทลหนึ่งครั้งเพื่อจัดเรียง แต่ถ้าใช้การจัดเรียงฟองแบบเรียงจากน้อยไปมากจะใช้เวลาสี่ ผ่าน อย่างไรก็ตามการจัดเรียงค๊อกเทลแบบหนึ่งจะต้องนับเป็นแบบฟองสบู่สองแบบ โดยทั่วไปแล้วการจัดเรียงค็อกเทลจะเร็วกว่าการจัดเรียงแบบฟองสบู่น้อยกว่าสองเท่า
การเพิ่มประสิทธิภาพอีกอย่างหนึ่งอาจเป็นได้ว่าอัลกอริทึมจะจำตำแหน่งที่ได้รับการแลกเปลี่ยนจริงครั้งล่าสุด ในการทำซ้ำถัดไปจะไม่มีการแลกเปลี่ยนใดที่เกินขีด จำกัด นี้และอัลกอริทึมจะมีการส่งผ่านที่สั้นกว่า เนื่องจากการจัดเรียงเครื่องปั่นค็อกเทลจะเกิดขึ้นแบบสองทิศทางช่วงของการแลกเปลี่ยนที่เป็นไปได้ซึ่งเป็นช่วงที่จะทดสอบจะลดลงต่อ pass ซึ่งช่วยลดเวลาในการทำงานโดยรวมเล็กน้อย
ความซับซ้อน
การเรียงลำดับเครื่องปั่นค็อกเทลยังกล่าวสั้น ๆ ในหนังสือศิลปะการเขียนโปรแกรมคอมพิวเตอร์พร้อมกับการปรับแต่งฟองแบบคล้าย ๆ กัน สรุปได้ว่า Knuth ได้กล่าวถึงการเรียงลำดับฟองและการปรับปรุง:
แต่ไม่มีการปรับแต่งเหล่านี้นำไปสู่อัลกอริทึมที่ดีกว่าการแทรกตรง (นั่นคือการจัดเรียงแบบแทรก); และเรารู้อยู่แล้วว่าการแทรกตรงไม่เหมาะสำหรับ N ขนาดใหญ่ [... ] ในระยะสั้นการจัดเรียงฟองดูเหมือนว่าไม่มีอะไรจะแนะนำให้ใช้ยกเว้นชื่อที่จับใจและความจริงที่ว่ามันนำไปสู่ปัญหาทางทฤษฎีบางอย่างที่น่าสนใจ
การเรียงลำดับแบบลูกปัด
"การจัดเรียงแบบลูกปัด" หรือที่เรียกอีกชื่อว่า "การจัดเรียงแบบแรงโน้มถ่วง" เป็นขั้นตอนวิธีการเรียงลำดับแบบธรรมชาติ พัฒนาโดย Joshua J. Arulanandham, และ  ในปี ค.ศ.2002
O(1) : ลูกปัดทั้งหมดเคลื่อนที่พร้อมกันในหน่วยเวลาเดียวกันเช่นเดียวกับตัวอย่างทางกายภาพที่เรียบง่ายข้างต้น นี่คือความซับซ้อนที่เป็นนามธรรมและไม่สามารถนำไปปฏิบัติได้
O(√n) : ในรูปแบบทางกายภาพที่สมจริงที่ใช้แรงโน้มถ่วงเวลาที่ใช้ในการปล่อยให้ลูกปัดตกลงมาเป็นสัดส่วนกับรากที่สองของความสูงสูงสุดซึ่งเป็นสัดส่วนกับ n (จำนวนข้อมูลทั้งหมด)
O(n) : ลูกปัดจะถูกย้ายไปทีละแถว นี่คือกรณีที่ใช้ในโซลูชั่นฮาร์ดแวร์อนาล็อกและดิจิตอล
O(S) : โดย S คือผลรวมของจำนวนเต็มในชุดข้อมูล ลูกปัดแต่ละลูกจะถูกย้ายทีละลูก นี่เป็นกรณี่จัดเรียงแบบลูกปัดโดยไม่มีกลไกเพื่อช่วยในการหาช่องว่างด้านล่างของลูกปัด
ตัวอย่างการเขียนโปรแกรมด้วยภาษาไพทอน (Python) โปรแกรมนี้ใช้ได้เฉพาะกับชุดข้อมูลที่มีสมาชิกภายในเป็น "จำนวนเต็มบวก" หรือ "มากกว่า 0"
def Gravity(obj):
n = len(obj)
if all([type(x) == int and x &gt;= 0 for x in obj]):
reference = [range(x) for x in obj]
raise ValueError("All elements must be positive integers")
intermediate = []
previous = n
while previous:
intermediate.append(range(previous))
previous = sum([1 for x in reference if len(x) &gt; index])
previous = len(intermediate)] # จำนวนที่มากที่สุด
out = [0 for x in range(n)]
out[n-1] = previous
for i in range(0,n-1):
previous = sum([1 for x in intermediate if len(x) &gt; n-i-1])
out[i] = previous
obj = [2, 4, 1, 3, 3]
print(Gravity(obj)) # [1, 2, 3, 3, 4]
kukuruku. Bead Sort. Retrieved 5 may 2018
การเรียงลำดับสลีป
เป็นอัลกอริทึมการเรียงลำดับตามเวลา ทำงานโดยเชื่อมโยงตัวนับเวลากับแต่ละไอเท็มที่ต้องการจะเรียงลำดับ เคาน์เตอร์แต่ละตัวจะตั้งค่าเริ่มต้นด้วยค่าขององค์ประกอบที่จะสั่ง เคาน์เตอร์จะลดลง แล้วที่ความเร็วเท่ากัน เมื่อตัวนับที่กำหนดสิ้นสุดลงองค์ประกอบที่เชื่อมโยงจะถูกเพิ่มลงในตอนท้ายของรายการ เนื่องจากตัวนับหยุดขึ้นอยู่กับขนาดขององค์ประกอบรายการจะเรียงลำดับเมื่อเคาน์เตอร์ทั้งหมดถูกหยุดลง สามารถใช้งานได้โดยใช้ตัวจับเวลาระบบปฏิบัติการเช่นโดยการแยกแต่ละกระบวนการออกเป็นส่วน ๆ หรือใช้เวคเตอร์ตัวนับ
sleep sort จะก่อให้เกิดกระบวนการหนึ่งสำหรับแต่ละอาร์กิวเมนต์ แต่ละกระบวนการรอประมาณ n วินาทีจากนั้นพิมพ์ n ออกมา ซึ่งหมายความว่าใช้เวลา 1 วินาทีในการพิมพ์ "1", 2 วินาทีเพื่อพิมพ์ "2", 100 วินาทีเพื่อพิมพ์ "100" ซึ่งหมายความว่าส่วนใหญ่ตัวเลขจะถูกพิมพ์ออกมาตามลำดับขนาดของมันดังนั้นจึงเป็นการ "เรียงลำดับ" อาร์กิวเมนต์
ความซับซ้อนของอัลกอริธึมนี้ในโลกที่สมบูรณ์แบบคือ O (max (args)) เนื่องจากจะใช้เวลาสูงสุด (args) วินาทีในการพิมพ์ arg ที่ขนาดใหญ่ที่สุด ในความเป็นจริงความซับซ้อนคือ O (n ^ 2 + max (args)) เนื่องจากการรักษากระบวนการพื้นหลังหลายระบบขึ้นอยู่กับระบบปฏิบัติการเพื่อจัดการการสลับบริบทและจัดลำดับความสำคัญของกระบวนการดังนั้นอัลกอริทึมจึงใช้การจัดเรียงที่แท้จริงของเคอร์เนล
นอกจากนี้ยังไม่มีการค้ำประกันว่าผลลัพธ์ของการจัดเรียงเป็นจริงถูกต้องซึ่งเป็นคุณลักษณะที่อัลกอริทึมการเรียงลำดับอื่นๆส่วนใหญ่ไม่มี
from time import sleep
from threading import Timer
def sleepsort(values):
sleepsort.result = []
def add1(x):
s leepsort.result.append(x)
mx = values[0]
if mx &lt; v:
mx = v
Timer(v, add1, [v]).start
sleep(mx+1)
return sleepsort.result
x = [5, 1, 3, 7]
print sleepsort(x)
Result = [1, 3, 5, 7]
ทางรถไฟสายเด่นชัย-เชียงราย-เชียงของ
ทางรถไฟสายแก่งคอย-บัวใหญ่
ขั้นตอนวิธีของพริม
ขั้นตอนวิธีของพริม Prim's Algorithm ถูกพัฒนาโดยนักคณิตศาสตร์ชื่อ Vojtech Jarnik ในปี1930 ต่อมาถูก พัฒนาต่อโดยนักคอมพิวเตอร์ชื่อ Robert C. Prim ในปี1957 และ Edsger Dijkstra ในปี1959 ดังนั้น อัลกอริทึมนี้บางทีจึงมักเรียกว่า DJP Algorithm , Jarnik Algorithm หรือ Prim-Jarnik Algorithm ซึ่งเป็นอัลกอริทึมที่ใช้ในการหาขนาด หรือน้ำหนักของต้นไม้ทอดข้ามที่น้อยที่สุด
เราจะเริ่มจากการทำ minimum spanning tree เล็ก ๆในกราฟก่อน จากนั้นจะค่อยๆเลือก edge ที่ ไม่ต่อกับ minimum spanning tree ย่อย ๆเดิมมาต่อเพิ่มไปเรื่อย ๆ จนได้ครบทุก node ซึ่ง algorithm ตัวนี้ จะ implement คล้ายๆกับ Dijkstra's Algorithm
codeขั้นตอนวิธีของพริม.
import heapq
def prim(nodes,edges):
if nodes==None and edges==None:
for u, v, w in edges:
if u not in conn:
conn[u] = [(w,u,v)]
# print(conn[u])
conn[u].append((w, u, v))
if v not in conn:
conn[v] = [(w,v,u)]
# print(conn[v])
conn[v].append((w, v, u))
node = nodes[0]
usable_edges = conn[node]
heapq.heapify(usable_edges)
Q = set(node)
mst = []
while len(usable_edges) &gt; 0:
wt, from_node, to_node = heapq.heappop(usable_edges)
if to_node not in Q:
Q.add(to_node)
mst.append((from_node, to_node, wt))
# print(mst)
for edge in conn[to_node]:
ww, uu, vv = edge
if vv not in Q:
heapq.heappush(usable_edges, (ww, uu, vv))
return mst
testcase ขั้นตอนวิธีของพริม.
from prim import prim
def test_case1:
edges = [ ("A", "B", 7), ("A", "D", 5),
("B", "C", 8), ("B", "D", 9), ("B", "E", 7),
("C", "E", 5),
("D", "E", 15), ("D", "F", 6),
("E", "F", 8), ("E", "G", 9),
("F", "G", 11)]
nodes = ["A","B","C","E","F","G"]
mst=[('A', 'D', 5),('D', 'F', 6),('A', 'B', 7),('B', 'E', 7),('E', 'C', 5),('E', 'G', 9)]
assert prim(nodes,edges )==mst
def test_case2:
edges = [ ("A", "B", 4),("A", "C", 3),("A", "D", 5),("B", "D", 2)]
nodes = ["A","B","C",]
mst=[ ("A", "C", 3),("A", "B", 4),("B", "D", 2)]
def test_case3:
edges =None
nodes =None
mst=None
def test_case4:
edges =[ ("A", "B", 2), ("A", "E", 2),("A", "C", 3),("B", "D", 4), ("D", "C", 5), ("E", "C", 6)]
nodes =["A","B","C","E"]
mst=[ ("A", "B", 2),("A", "E",2 ),("A", "C", 3),("B", "D", 4)]
Big-o.
Big-o Prim’s algorithm
Big o=o(n^2logn)
Best case กรณีไม่มีmatrix
Big o=o(1)
Worst case กรณีมีmatrix
แฮชชิงคู่
แฮชชิ่งคู่  เป็นเทคนิคการเขียนโปรแกรมคอมพิวเตอร์ โดยใช้ตารางแฮชเพื่อป้องกันการชนกันของแฮช ในกรณีที่สองค่าที่แตกกต่างกันค้นหาคีย์แฮชเดียวกัน ซึ่งการแฮชสองชั้นเป็นเทคนิค การแฮชแบบสองชั้นถูกนำไปใช้ในคลังโปรแกรมที่นิยมมาก
1. กำหนดความกว้างของตารางแฮช และ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม
2. กำหนดข้อมูลที่เราต้องการ อย่างตัวอย่างจะกำหนดให้คือ 26, 54, 94, 17, 31, 77, 44 และ 51 ความกว้างของตาราง คือ 13 ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม คือ 5
3. นำข้อมูลที่กำหนดให้มาคำนวณ โดย ข้อมูล ณ ตำแหน่งที่ Mod ความกว้างของตาราง (formula_1) จะได้ formula_2 ซึ่งเป็นค่าในตำแหน่งของตารางแฮช แล้วทำต่อให้ครบทุกค่า
4. หาค่าการแฮชสองชั้นโดยใช้ ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม ลบกับ ข้อมูล ณ ตำแหน่งที่ Mod ค่าที่ใช้เพื่อเลื่อนค่าจากตำแหน่งเดิม  ( formula_3 ) จะได้ formula_4
5. นำค่าที่ได้ในข้อที่ 3 ไปใส่ยังตารางในข้อที่ 2
5.1 ค่า 26 ตำแหน่งที่ 0
5.2 ค่า 54 ตำแหน่งที่ 2
5.3 ค่า 94 ตำแหน่งที่ 3
5.4 ค่า 17 ตำแหน่งที่ 4
5.5 ค่า 31 ตำแหน่งที่ 5
5.6 ค่า 77 ตำแหน่งที่ 12
5.7 ค่า 44 ตำแหน่งที่ 5 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 5 + 1 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 6)
เมื่อได้ค่าเท่ากับ 6 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง
ค่า 51 ตำแหน่งที่ 12 (กรณีค่าที่ตำแหน่งทับกัน จะนำค่าจากตารางในข้อที่ 4 มา บวกกับ ค่าตารางที่ 1 จะได้ 12 + 4 แล้ว Mod ด้วยความกว้างของตารางแฮช จะเท่ากับ 3)
เมื่อได้ค่าเท่ากับ 3 แล้ว จะเป็นค่าตำแหน่งใหม่ที่ใส่ลงในตาราง แต่เมื่อกรณียังมีค่าในตารางให้นับเพิ่มอีก 3
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3
กรณียังมีค่าในตารางให้นับเพิ่มอีก 3 แต่เมื่อเจอช่องที่ว่างเปล่า สามารถนำค่านั้นลงในตารางได้ทันที
จะสรุปได้ว่า Big(O) = O(formula_5) Best Case คือ ขนาดของข้อมูลเป็น 0 มีค่าเดียว หรือข้อมูลมีค่ามากกว่าตาราง O(1) Worst Case คือ ขนาดของข้อมูลที่ให้ฟังก์ชั่นทำงานครบทั้งหมด O(formula_5)
def doubleHashing(data, hashTableSize, doubleHashSize):
if len(data) &gt; hashTableSize:
listOfHashTable = [None] * hashTableSize
for i in range(len(data)):
primaryHash = data[i] % hashTableSize
doubleHash = primaryHash
if listOfHashTable[primaryHash] is None:
listOfHashTable[primaryHash] = data[i]
while listOfHashTable[doubleHash] is not None:
secondary = doubleHashSize - (data[i] % doubleHashSize)
doubleHash = (doubleHash + secondary) % hashTableSize
listOfHashTable[doubleHash] = data[i]
return listOfHashTable
Mohit Makhija . Double Hashing Code2begin. Retrieved 1 May 2018.
สโมสรฟุตบอลปานาซีไนโกส
สโมสรฟุตบอลปานาซีไนโกส  สโมสรฟุตบอลอาชีพของประเทศกรีซ มีที่ตั้งอยู่ใน กรุงเอเธนส์ ทุกวันนี้พวกเขาเป็นส่วนหนึ่งของ ปานาซีไนโกส เอโอ สโมสรกีฬาแบบครบวงจรที่โด่งดังที่สุดของกรีซและพวกเขาเป็นสโมสรฟุตบอลที่เก่าแก่ที่สุดของกรีซที่ยังทำกิจกรรมอยู่
สโมสรปานาซีไนโกสก่อตั้งเมื่อ ค.ศ. 1908 โดย จอร์จอส คาลาฟาติส และเพื่อนนักกีฬากว่า 40 คนโดยแยกออกมาจากสโมสรกีฬาแห่งหนึ่งภายหลังจากทางสโมสรกีฬาแห่งนั้นตัดสินใจยุติการทำทีมฟุตบอลโดยปานาซีไนโกสในยุคแรกถูกก่อตั้งขึ้นเพื่อฝึกสอนกีฬาเท่านั้น
ต่อมาทางสโมสรได้เข้าร่วม ซูเปอร์ลีกกรีซ และกลายเป็นหนึ่งในสโมสรที่ประสบความสำเร็จมากที่สุดในวงการฟุตบอลกรีซและเป็นหนึ่งในสามสโมสรที่ไม่เคยตกชั้นจากลีกสูงสุดร่วมกับ เออีเค เอเธนส์ และ โอลิมเปียกอส
สโมสรฟุตบอลปานาซีไนโกสเป็นสโมสรฟุตบอลของกรีซที่ประสบความสำเร็จมากที่สุดในการแข่งขันฟุตบอลยุโรปเป็นทีมเดียวของกรีซที่ได้เข้าสู่รอบชิงชนะเลิศของฟุตบอล ยูโรเปียน คัพ (ยูฟ่าแชมเปียนส์ลีก ในปัจจุบัน) ปี ค.ศ. 1971 ภายใต้การคุมทีมของ แฟแร็นตส์ ปุชกาช ตำนานยอดกองหน้าของ ทีมชาติฮังการี และ เรอัลมาดริด แต่แพ้ให้กับ อายักซ์ อัมสเตอร์ดัม เข้าถึงรอบรองชนะเลิศถึง 2 ครั้งคือปี ค.ศ. 1985 และ ค.ศ. 1996 และเป็นทีมเดียวของกรีซที่ได้ลงแข่ง ฟุตบอลชิงแชมป์สโมสรยุโรปและอเมริกาใต้ (1971) นอกจากนี้พวกเขายังเข้าถึงรอบก่อนรองชนะเลิศของแชมเปียนส์ลีกถึง 2 ครั้งใน ค.ศ. 1992 และ ค.ศ. 2002 และรอบก่อนรองชนะเลิศของ ยูฟ่า คัพ อีก 2 ครั้งใน ค.ศ. 1988 และ ค.ศ. 2003 พวกเขายังคว้าแชมป์ บอลข่าน คัพ ใน ค.ศ. 1977 ปานาซีไนโกสเป็นสมาชิกของ สมาคมสโมสรฟุตบอลยุโรป
ต้นไม้ค้นหาไตรภาค
ในวิทยาการคอมพิวเตอร์ ต้นไม้ค้นหาไตรภาค  เป็นทรัยประเภทหนึ่งซึ่งมีการจัดเรียงบัพแบบที่คล้ายกับต้นไม้ค้นหาทวิภาค แต่มีบัพลูกสามบัพแทนที่จะมีสองบัพ ต้นไม้ค้นหาไตรภาคสามารถใช้เป็นโครงสร้างแผนที่สัมพันธ์ที่มีความสามารถค้นหาสายอักขระแนวเดิม อย่างไรก็ดี ต้นไม้ค้นหาไตรนามใช้พื้นที่มีประสิทธิภาพกว่าเมื่อเทียบกับต้นไม้เติมหน้ามาตรฐานแต่มีความเร็วช้ากว่า การใช้ต้นไม้ค้นหาไตรภาคทั่วไป เช่น การตรวจสอบตัวสะกดและการเติมคำอัตโนมัติ
การดำเนินการของต้นไม้ค้นหาไตรภาค.
•    ตัวชี้ซ้ายชี้ไปที่โหนดที่มีค่าต่ำกว่าค่าในโหนดปัจจุบัน (LEFT NODE)
•    ตัวชี้ที่เท่ากันชี้ไปที่โหนดที่มีค่าเท่ากับค่าในโหนดปัจจุบัน (MID NODE or EQUAL NODE)
•    ตัวชี้ด้านขวาชี้ไปที่โหนดที่มีค่ามากกว่าค่าในโหนดปัจจุบัน (RIGHT NODE)
a u h
t t e u
s p e i s
&lt;/syntaxhighlight&gt;จากกราฟนี้แสดงให้เห็นแต่ละโหนดที่ถูก insert หรือเพิ่มเข้ามาเป็นโครงสร้างของ TST โดยมีการเพิ่มข้อมูล "cute","cup","at","as","he","us" and "i" ตามลำดับ โดยข้อมูลที่ถูกเพิ่มเข้ามาก่อนนั้นจะเป็นกราฟ tree ที่อยู่ในตำแหล่งตรงกลาง และข้อมูลลำดับถัดไปหากลำดับตัวอักษรมีค่าน้อยกว่า parent node ก็จะเป็นกราฟ child node ที่อยู่ซ้ายมือ เช่นเดียวกันหากข้อมูลที่เพิ่มเข้ามามีค่าลำดับตัวอักษรมากกว่า parent node ก็จะอยู่ child node ขวามือ
CODE(PYTHON).
คุณสมบัติของโหนด
self.end = False
self.left = None
self.mid = None
self.right = None
def print_(self):
return ".join(['[', self.data,
(" if not self.end else ' &lt;end&gt;'),
(" if self.left is None else ' left: ' + self.left.print_),
(" if self.mid is None else ' mid: ' + self.mid.print_),
(" if self.right is None else ' right: ' + self.right.print_), ']'])
def add(self, node, string):
if len(string) == 0:
head = string[0]
tail = string[1:]
node = Node(head)
if head &lt; node.data:
node.left = self.add(node.left,string)
elif head &gt; node.data:
node.right = self.add(node.right,string)
if len(tail) == 0:
node.end = True
node.mid = self.add(node.mid, tail)
การค้นหาข้อมูล
def search(self, node, string):
if node is None or len(string) == 0:
return self.search(node.left, string)
return self.search(node.right, string)
if len(tail) == 0 and node.end:
return self.search(node.mid, tail)
การเรียงลำดับแบบรังนกพิราบ
การเรียงลำดับแบบรังนกพิราบ  เป็นขั้นตอนวิธีการเรียงลำดับที่เหมาะกับการเรียงลำดับรายการส่วนย่อยที่จำนวนส่วนย่อย (n) และความยาวของพิสัยค่าหลักที่เป็นไปได้ (N) ประมาณเท่า ๆ กัน ต้องใช้ O(n + N) ครั้ง การเรียงลำดับแบบนี้คล้ายกับการเรียงลำดับนับ แต่ต่างกันที่การเรียงลำดับนี้ "ย้ายรายการสองครั้ง ครั้งหนึ่งเข้าแถวลำดับที่ฝากข้อมูลแล้วอีกครั้งย้ายกับจุดหมายสุดท้าย"
การทำงานของการเรียงลำดับ.
•     กำหนดให้เป็น array ของค่าที่จะเรียงลำดับ โดยกำหนด array ที่จะช่วยในการเรียงลำดับ array มีชื่อว่า holes ซึ่งเป็น array ว่างเปล่าที่รอรับจำนวนสมาชิกเป็นช่วงของ array เดิม
•     ที่ array ที่ต้องการจัดเรียงเราใส่ค่าแต่ละ array ลงใน holes ที่ตรงกับตำแหน่งของ array เดิม
•     ทำซ้ำใน holes โดยเขียนทับ array เดิมตามองค์ประกอบของ holes ว่าอยู่ตำแหน่งไหนบ้าง
การวิเคราะห์ความซับซ้อนของขั้นตอนวิธี.
1.ในการนับเพื่อเพิ่มค่าของหลุม(holes) จะทำเท่ากับสมาชิกของอเรย์ หากให้สมาชิกของอเรย์เท่ากับ n จะได้ O(n)
2.ในการนับเพื่อที่จะเขียนทับไปยังอเรย์เดิมจะทำเท่ากับจำนวนของสมาชิกใน size ซึ่งมากจาก ค่าสูงสุดของอเรย์-ค่าต่ำสุดของอเรย์ +1 กำหนดให้เป็น m และเงื่อนไงของการที่จะเขียนทับลงไปยังอเรย์เดิมคืออเรย์ที่ holes ใดๆ ต้องมากกว่า 0 กำหนดให้เป็น x ดังนั้นสรุปได้ว่าความซับซ้อนจะมีค่าเป็น O(mx)
3.ดังนั้นเราสามารถสรุปได้ว่าขั้นตอนความซับซ้อนของการเรียงลำดับนี้คือ O(n+mx) ซึ่ง n=x เนื่องจากจากเงื่อนไงของ x มาจากจำนวนของ n ดังนั้นความซับซ้อนเท่ากับO(n+mn) เมื่อให้ N = mn จะได้ความซับซ้อนของขั้นตอนวิธี O(n+N)
4.ในกรณีที่ของมูลมีค่าหเมือนกันจะส่งผลให้ max-min+1 มีค่าเท่ากับ 1 และความซับซ้อนของ m=1 จะได้ความซับซ้อนของขั้นตอนวิธีเท่ากับ O(n+n) หรือ O(2n) นั่นเอง
CODE (PYTHON).
def Pigeonhole_sort(array):
min_arr = min(array)
size = max(array) - min_arr + 1
holes = [0] * size
for i in array:
holes[i - min_arr] += 1
i_array = 0
for count in range(size):
while holes[count] &gt; 0:
array[i_array] = count + min_arr
holes[count] -= 1
i_array += 1
TEST CASE.
from PigeonholeSorting import Pigeonhole_sort
def is_sorted(array):
for i in range(1,n):
if array[i] &lt; array[i-1]:
class test_sorting(unittest.TestCase):
def test_ipigeonhole_sort(self):
max_size = 1500
for size in range(1, max_size + 1):
array = [random.randrange(20) for num in range(size)]
sorted = Pigeonhole_sort(array)
self.assertTrue(is_sorted(sorted))
ซอฟต์ฮีป
ในวิทยาการคอมพิวเตอร์ โดย Soft heap เป็นตัวแปรในโครงสร้างข้อมูล(Data structure) heap ง่ายๆ ซึ่งมีคำสั่งที่สามารถสั่งงานได้ 5 ชนิด นี่คือการลุล่วงคำสั่งโดยการ " corrupting(ทำความเสียหาย)" (การเพิ่มขึ้น) เป็นกุญแจสำคัญในค่าของจำนวนที่แน่นอนที่อยู่ใน Heap โดยมีคำสั่งที่ให้ในการดำเนินการดังนี้
Heapอื่น ๆ เช่น heaps Fibonacci สามารถทำคำสั่งได้สำเร็จมากที่สุดโดยไม่มีจำเป็นต้องมี"corrupting", แต่ไม่สามารถให้ขอบเขตเวลาคงที่บนการดำเนินการในคำสั่ง “ลบ” (delete) ที่สำคัญได้ ปริมาณของ Corruptionสามารถควบคุมได้โดยการเลือกพารามิเตอร์ “ε”, แต่การตั้งค่าต่ำกว่านี้จำเป็นต้องมีการใส่เวลามากขึ้นด้วยเช่นกัน (O(log 1/ε) สำหรับอัตราการผิดพลาดของ ε)
ท้ายที่สุดอัลกรอลิทึมจะมีลักษณะดังนี้:
function softHeapSelect(a[1..n], k)
if k = 1 then return minimum(a[1..n])
create(S)
for i from 1 to n
insert(S, a[i])
for i from 1 to n/3
x := findmin(S)
delete(S, x)
xIndex := partition(a, x) "// Returns new index of pivot x"
if k &lt; xIndex
softHeapSelect(a[1..xIndex-1], k)
softHeapSelect(a[xIndex..n], k-xIndex+1)
ค่าตัวแปรทั่วไปที่ใช้ในการเรียงลำดับความสำคัญ เรียกว่า “Soft Heap” โครงสร้างข้อมูลจะถูกสนับสนุนโดยกระบวนการหลักดังนี้ : insert(การแทรก), delete(การลบ), meld(การรวม), findmin(หาค่าที่น้อยที่สุด) เป็นที่น่าแปลกใจมากที่มันมีความสามารถในการเอาชนะขอบเขตของลอกาลึทึมบนความซับซ้อนของ Heap ในแบบจำลองการเปรียบเทียบพื้นฐาน เพื่อที่ทำลายอุปสรรค์ของทฤษฎีนี้ เอนโทรปีของโครงสร้างข้อมูลจะถูกทำให้ลดลงโดยค่าบางค่าในKeys ซึ่งมีการผสมลำดับของ n คำสั่งกับค่าของความผิดพลาด(Error rate, ε) จะมีค่าอยู่ระหว่าง (0&lt; ε ≤ 1/2) สิ่งที่เป็นข้อยืนยันคือในเวลาใดๆ ส่วนมาก ε*n มันจะมี keys จะถูกยกขึ้นมาใช้งาน ,การหักล้างความซับซ้อนของแต่ละคำสั่งนั้นเป็นที่แน่นอน ยกเว้นในคำสั่ง Insert ซึ่งจะใช้เวลา O(Log 1/ε) ครั้ง
Soft Heap จะดีที่สุดก็ต่อเมื่อมีค่าของ ε อยู่ในแบบจำลองการเปรียบเทียบพื้นฐาน โดยโครงสร้างข้อมูลนั้นจะมีแค่Pointer อยู่อย่างเดียว ไม่มี Array ใดๆที่จะใช้ค่าเลขสมมุติในการสร้าง Keys ได้ แนวความคิดหลักของ Soft Heap คือการเคลื่อนย้ายรายการข้ามโครงสร้างข้อมูลไม่ใช่ทีละรายการแต่เป็นกลุ่ม นั้นเป็นไปอย่างปกติ, ในโครงสร้างข้อมูลจะมีลักษณะคล้ายกับ Carpooling (การร่วมโดยสารกันไปในเส้นทางเดียวกัน โดยในยานพาหนะเดียวกัน) Keys จะต้องขึ้นอยู่กับผลของมัน เพื่อที่จะรักษาลำดับโครงสร้างข้อมูลของ Heap เอาไว้ Soft Heap สามารถใช้การคำนวณได้อย่างแน่นอนหรือ มีค่ามัธฐาน และค่าเปอร์เซ็นสูงสุด มันมีประโยชน์มากสำหรับการประมาณค่าการเรียงลำดับข้อมูล(Sorting)และ เพื่อคำนวณหาค่าที่ต่ำที่สุดของแผนภูมิต้นไม้อีกด้วย
การเรียงลำดับคี่–คู่