โซลูชันที่มีประสิทธิภาพสูงสุดสำหรับ USACO: Triangles - Python
ฉันกำลังพยายามแก้ปัญหานี้ด้วย Python 3.8 ในรหัสของฉันฉันใช้ 3 แบบซ้อนกันสำหรับลูปเพื่อตรวจสอบทุกจุดเดียวและจัดเก็บพื้นที่ที่ใหญ่ที่สุดด้วยชุดของคะแนนแต่ละชุด โปรแกรมนี้ใช้งานได้ดี แต่เป็น\$ O(n^3) \$ความซับซ้อนของเวลาและฉันสงสัยว่ามีโซลูชันที่หรูหรา / มีประสิทธิภาพมากกว่านี้หรือไม่ มีอัลกอริทึมที่มีประสิทธิภาพมากกว่าที่ไม่วนซ้ำทุกจุดหรือจำเป็นหรือไม่?
รหัสของฉัน:
with open("triangles.in", "r") as file_in:
lines = [x.strip() for x in file_in.readlines()]
n, points = lines[0], lines[1:]
def main(points):
largest = 0
for corner in points:
cx, cy = corner.split()
for leg in points:
lx, ly = leg.split()
for width in points:
wx, wy = width.split()
if lx == cx and wy == cy:
area = abs(int(ly)-int(cy)) * abs(int(wx)-int(cx))
if area > largest:
largest = area
return str(largest)
with open("triangles.out", "w+") as file_out:
file_out.write(main(points))
file_out.close()
ไฟล์อินพุตtriangles.in:
4
0 0
0 1
1 0
1 2
สรุปปัญหา:ให้ชุดของ\$ n \$จุดที่แตกต่าง\$ (X_1, Y_1) \$ถึง\$ (X_n, Y_n) \$หาพื้นที่ของสามเหลี่ยมที่ใหญ่ที่สุดคูณด้วย 2 เนื่องจากสามเหลี่ยมนั้นเป็นสามเหลี่ยมมุมฉาก (เส้นหนึ่งของสามเหลี่ยมขนานกับแกน x และอีกเส้นหนึ่งขนานกับแกน y)
คำตอบ
การปรับปรุงที่เห็นได้ชัดคือการไม่แบ่งสายและแปลงส่วนที่จะซ้ำแล้วซ้ำอีกint ทำครั้งเดียวตั้งแต่เริ่มต้น:
def main(points):
points = [tuple(map(int, point.split())) for point in points]
largest = 0
for cx, cy in points:
for lx, ly in points:
for wx, wy in points:
if lx == cx and wy == cy:
area = abs(ly-cy) * abs(wx-cx)
if area > largest:
largest = area
return str(largest)
และสามารถแก้ไขได้ใน O (n) สำหรับทุก "มุม" ตามที่คุณเรียกคุณจะต้องผ่านคู่จุดทั้งหมด ให้มองหาจุดที่อยู่ไกลที่สุดบนพิกัด y เดียวกันและจุดที่อยู่ไกลที่สุดบนพิกัด x เดียวกัน ที่สามารถคำนวณล่วงหน้าได้ใน O (n):
with open('triangles.in') as f:
next(f)
points = [tuple(map(int, line.split())) for line in f]
xmin, xmax, ymin, ymax = {}, {}, {}, {}
for x, y in points:
xmin[y] = min(xmin.get(y, x), x)
xmax[y] = max(xmax.get(y, x), x)
ymin[x] = min(ymin.get(x, y), y)
ymax[x] = max(ymax.get(x, y), y)
result = max(max(x - xmin[y], xmax[y] - x) * max(y - ymin[x], ymax[x] - y)
for x, y in points)
with open('triangles.out', 'w') as f:
print(result, file=f)
โปรดทราบว่าฉันยังได้ผลลัพธ์ที่แตกต่างกันเล็กน้อย ไม่จำเป็นต้องcloseตัวเอง การปิดไฟล์สำหรับคุณเป็นเหตุผลที่คุณใช้withในตอนแรกจำได้ไหม? และฉันชอบprintมากกว่าwriteเพราะฉันไม่ต้องแปลงเป็นสตริงและเชื่อว่าการสิ้นสุดบรรทัดจะทำได้ตามความเหมาะสมสำหรับแพลตฟอร์ม (อาจไม่ใช่ปัญหาที่นี่เนื่องจากเอาต์พุตเป็นเพียงบรรทัดเดียวและดูเหมือนว่าพวกเขาไม่สนใจว่าจะทำอย่างไร มันจบลง)
PS ยี้ ... พวกเขาเหล่านั้นเก็บไว้ว่าวิธีการแก้ปัญหาของฉันล้มเหลวเนื่องจาก"Runtime ข้อผิดพลาดหรือหน่วยความจำวงเงินเกิน"และจะเอาฉันในขณะที่ตัวเลขออก: แทนที่จะผมใช้ที่ต้องการของฉันtuple(map(...)) [*map(...)]แต่พวกเขาใช้ Python 3.4 อย่างอธิบายไม่ได้และไม่มีอยู่จริงในตอนนั้น แต่นั่นน่าจะเป็นข้อผิดพลาดทางไวยากรณ์ กร๊ากกก ....
สิ่งนี้จะคล้ายกับคำตอบที่ยอดเยี่ยมของ Rain
เขียนฟังก์ชัน
การเขียนฟังก์ชันจะช่วยให้คุณเขียนได้ง่ายขึ้นเพื่อรักษาโค้ด นอกจากนี้สำหรับความท้าทายของอัลกอริทึมจะช่วยให้คุณมุ่งเน้นไปที่อัลกอริทึมเองแทนที่จะจัดการกับอินพุต / เอาต์พุต
เขียนแบบทดสอบ
เมื่อคุณมีฟังก์ชันแล้วการเขียนข้อสอบจะง่ายขึ้น (คุณสามารถเขียนการทดสอบก่อนฟังก์ชันได้ด้วย) สิ่งนี้จะช่วยในการทดสอบการใช้งานต่างๆเพื่อทดสอบเพื่อเปรียบเทียบพวกเขา (ทั้งในด้านความถูกต้องและในการแสดง)
คำแนะนำในการเพิ่มประสิทธิภาพ
คำนวณให้น้อยที่สุดหยุดโดยเร็วที่สุด
ในที่นี้อาจหมายถึงการตรวจสอบlx == cxโดยเร็วที่สุดและคำนวณabs(ly-cy)เพียงครั้งเดียวต่อทูเพิล (ly, cy)
def get_solution_naive_on_smaller_range(points):
largest = 0
for cx, cy in points:
for lx, ly in points:
if lx == cx:
dy = abs(ly-cy)
for wx, wy in points:
if wy == cy:
dx = abs(wx-cx)
area = dy * dx
if area > largest:
largest = area
return largest
คำนวณล่วงหน้าให้มากที่สุด
แทนที่จะต้องวนซ้ำทุกจุดเพื่อค้นหาจุดในบรรทัดหรือคอลัมน์เดียวกันกับจุดที่กำลังพิจารณาเราสามารถทำการคำนวณล่วงหน้าเพื่อให้สามารถค้นหาจุดทั้งหมดในบรรทัด (หรือคอลัมน์) เดียวกันกับจุดปัจจุบันได้อย่างรวดเร็ว
def get_solution_using_dicts(points):
largest = 0
by_x = dict()
by_y = dict()
for x, y in points:
by_x.setdefault(x, []).append(y)
by_y.setdefault(y, []).append(x)
for cx, cy in points:
for ly in by_x[cx]:
dy = abs(ly-cy)
for wx in by_y[cy]:
dx = abs(wx - cx)
area = dy * dx
if area > largest:
largest = area
return largest
คำนวณให้น้อยที่สุด (อีกครั้ง)
สำหรับจุดที่กำหนดเราไม่จำเป็นต้องพิจารณาจุดอื่น ๆ ทั้งหมดในบรรทัดเดียวกันและจุดอื่น ๆ ทั้งหมดในคอลัมน์เดียวกัน เราสามารถพิจารณาอันที่อยู่ไกลที่สุดในแนวตั้งหรือแนวนอน
ดังนั้นในประเด็นหนึ่งเราสามารถมีผู้สมัครที่ดีที่สุดได้อย่างรวดเร็ว:
def get_solution_using_dicts_and_maxabs(points):
largest = 0
by_x = dict()
by_y = dict()
for x, y in points:
by_x.setdefault(x, []).append(y)
by_y.setdefault(y, []).append(x)
for cx, cy in points:
max_y_delta = max(abs(y-cy) for y in by_x[cx])
max_x_delta = max(abs(x-cx) for x in by_y[cy])
area = max_x_delta * max_y_delta
if area > largest:
largest = area
return largest
รหัสสุดท้าย
# https://codereview.stackexchange.com/questions/250205/most-efficient-solution-for-usaco-triangles-python
# http://usaco.org/index.php?page=viewproblem2&cpid=1011
import random
def get_random_points(n, mini, maxi):
# First generate a triangle so that there is at least one
points = set([(5, 0), (0, 0), (0, 5)])
# Generate remainings points
while len(points) < n:
a = random.randint(mini, maxi)
b = random.randint(mini, maxi)
points.add((a, b))
# Shuffle
l = list(points)
random.shuffle(l)
return l
def get_solution_naive(points):
largest = 0
for cx, cy in points:
for lx, ly in points:
for wx, wy in points:
if lx == cx and wy == cy:
area = abs(ly-cy) * abs(wx-cx)
if area > largest:
largest = area
return largest
def get_solution_naive_on_smaller_range(points):
largest = 0
for cx, cy in points:
for lx, ly in points:
if lx == cx:
dy = abs(ly-cy)
for wx, wy in points:
if wy == cy:
dx = abs(wx-cx)
area = dy * dx
if area > largest:
largest = area
return largest
def get_solution_using_dicts(points):
largest = 0
by_x = dict()
by_y = dict()
for x, y in points:
by_x.setdefault(x, []).append(y)
by_y.setdefault(y, []).append(x)
for cx, cy in points:
for ly in by_x[cx]:
dy = abs(ly-cy)
for wx in by_y[cy]:
dx = abs(wx - cx)
area = dy * dx
if area > largest:
largest = area
return largest
def get_solution_using_dicts_and_maxabs(points):
largest = 0
by_x = dict()
by_y = dict()
for x, y in points:
by_x.setdefault(x, []).append(y)
by_y.setdefault(y, []).append(x)
for cx, cy in points:
max_y_delta = max(abs(y-cy) for y in by_x[cx])
max_x_delta = max(abs(x-cx) for x in by_y[cy])
area = max_x_delta * max_y_delta
if area > largest:
largest = area
return largest
def perform_check(points, solution):
ret = get_solution_naive(points)
ret1 = get_solution_naive_on_smaller_range(points)
ret2 = get_solution_using_dicts(points)
ret3 = get_solution_using_dicts_and_maxabs(points)
if ret != solution:
print("ret", points, ret, solution)
if ret1 != solution:
print("ret1", points, ret1, solution)
if ret2 != solution:
print("ret2", points, ret2, solution)
if ret3 != solution:
print("ret3", points, ret3, solution)
# Provided test case
perform_check([(0, 0), (0, 1), (1, 0), (1, 2)], 2)
# Generated test case
perform_check([(5, 0), (-1, 1), (-5, -3), (1, -5), (5, -2), (4, 5), (-2, 5), (-2, 1), (-4, -3), (5, -4), (-4, 3), (-5, -1), (0, 0), (-2, -5), (3, 1), (3, 2), (-4, 2), (2, 3), (0, 5), (5, 5)] , 70)
```