วิธีที่ดีที่สุดในการเลือกองค์ประกอบอาร์เรย์แบบสุ่มเพื่อหลีกเลี่ยงรายการยกเว้น
วิธีใดเป็นวิธีที่สวยงาม / มีประสิทธิภาพที่สุดในการเลือกตำแหน่งสุ่มในเมทริกซ์ n * n โดยไม่รวมชุดตำแหน่ง
ตัวอย่าง:ลองนึกภาพกระดานหมากรุกดังนั้นn = 8และมี8 * 8 = 64ตำแหน่งทั้งหมด มีเบี้ย 3 ตัวที่ตำแหน่ง (0, 0), (5, 3), (7, 4) ภารกิจคือการเลือกตำแหน่งแบบสุ่มที่เบี้ยยังไม่ถูกครอบครอง
นี่คือสิ่งที่ฉันคิดขึ้นมา:
def get_random_position(n, occupied_positions):
while True:
random_position = (random.choice(range(n)), random.choice(range(n)))
if random_position not in occupied_positions:
return random_position
if __name__ == '__main__':
unoccupied_random_position = get_random_position(8, [(0, 0), (5, 3), (7, 4)])
print(unoccupied_random_position)
ความซับซ้อนของเวลาเป็นค่าคงที่สำหรับ n และเชิงเส้นด้วยจำนวนเซลล์ที่ครอบครอง ดังนั้นหากเซลล์ 90% ถูกครอบครองแล้วลูปจะวนซ้ำอีกต่อไป
มีวิธีที่ดีกว่านี้หรือไม่?
คำตอบ
ประการแรกเป็นที่ชัดเจนว่าคุณไม่สามารถทำได้ดีไปกว่ากรณีที่เลวร้ายที่สุดของO (m)โดยที่mคือจำนวนเซลล์ในเมทริกซ์นั่นคือm = n²โดยที่nคือความกว้างของเมทริกซ์: ในกรณีที่เลวร้ายที่สุดทั้งหมด เซลล์ยกเว้นเซลล์หนึ่งถูกครอบครองคุณจะต้องดูพิกัดm-1 แต่ละอันเป็นอย่างน้อย
ฉันควรพูดถึงที่นี่ด้วยว่าในรหัสของคุณrandom_position not in occupied_positions
ไม่ใช่การดำเนินการที่คงที่ ทุกครั้งที่มีการทำรายการซ้ำเพื่อค้นหารายการที่ตรงกัน
นี่คือทางเลือก:
คุณสามารถหาจำนวนเซลล์อิสระสร้างตัวเลขสุ่มได้จนถึงขีด จำกัด นั้นแล้ววนซ้ำเซลล์ที่ถูกยึดครองเพื่อปรับจำนวนนั้น (เพิ่มขึ้น) เพื่อชี้ไปยังเซลล์ว่างจริง ในกระบวนการนี้ตัวเลขจะจับคู่กับพิกัด x และ y โดยไม่ซ้ำกัน
เพื่อให้สิ่งนี้มีประสิทธิภาพเราต้องถือว่ารายการของเซลล์ที่ถูกยึดนั้นได้รับการจัดเรียงเรียบร้อยแล้ว
นี่คือวิธีที่สามารถเข้ารหัสได้:
def get_random_position(n, occupied_positions):
rnd = random.randint(0, n*n - 1 - len(occupied_positions))
for (row, col) in occupied_positions:
if rnd < row*n+col:
break
rnd += 1
return (rnd // n, rnd % n)
รหัสนี้ทำงานในO (k)โดยที่kคือขนาดของoccupied_positions
รายการ ถ้าเราไม่สามารถรับประกันได้ว่ารายการนี้จะถูกจัดเรียงแล้วเราจำเป็นต้องเรียงลำดับมันเป็นครั้งแรกและครั้งนี้แล้วกำหนดความซับซ้อนเวลาโดยรวมคือO (klogk)
แทนที่จะเลือกตำแหน่งแบบสุ่มและตรวจสอบว่าว่างอยู่หรือไม่ก่อนอื่นให้สแกนบอร์ดเพื่อดูว่าตำแหน่งใดเปิดอยู่ สร้างรายชื่อสปอตเหล่านั้น นี่คือO(n)
โดยที่ n คือจำนวนช่องว่างของบอร์ดทั้งหมด จากนั้นเลือกองค์ประกอบแบบสุ่มจากเฉพาะจุดที่เปิดอยู่ สังเกตว่าเมื่อคุณมีช่องเปิดเพียงไม่กี่ช่องการเลือกแบบสุ่มยังคงเลือกจากช่องว่างไม่กี่ช่องเท่านั้นและคุณจะต้องสุ่มตัวอย่างเพียงครั้งเดียว