Dijkstra trên Java: Nhận kết quả thú vị Sử dụng Fibonacci Heap so với PriorityQueue

Question

Gần đây tôi đã so sánh ban đầu về thời gian chạy của thuật toán Dijkstra sử dụng hai cấu trúc dữ liệu, PriorityQueue dựa trên nền tảng nhị phân, nếu tôi ' m không nhầm lẫn) và một vùng Fibonacci. Tôi đã sử dụng currentTimeMillis() của Java để thực hiện các phép tính của mình. Kết quả tôi đã kết thúc với khá thú vị. Đây là đầu ra cho một trong những testcases của tôi:

Running Dijkstra's with 8 nodes and 27 links 
- Execution time with binary heap: 1 miliseconds 
- Execution time with Fibonacci heap: 4 miliseconds 

Phải thừa nhận rằng, tôi là ngắn trên tập hợp dữ liệu tại thời điểm này, với đồ thị trên là lớn nhất của tôi (tôi có kế hoạch để làm sớm hơn). Nhưng điều này có ý nghĩa gì không? Tôi đã luôn luôn nghĩ rằng Fibonacci heaps nhanh hơn so với các cấu trúc dữ liệu khác do thời gian chạy phân bổ của chúng so với các cấu trúc dữ liệu khác. Tôi không thực sự chắc chắn rằng sự khác biệt 3 milisecond này đến từ đâu. (Tôi đang chạy nó trên bộ vi xử lý Intel Core Ivy Bridge i7-3630M, nếu điều đó có ích.)

Lưu ý: Tôi tình cờ gặp phải this thread có thể giải thích được vấn đề, mặc dù tôi vẫn chưa rõ lý do tại sao vùng Fibonacci phiên bản mất nhiều thời gian hơn. Theo chủ đề đó, nó có thể là do đồ thị của tôi không đủ dày đặc và do đó số lượng các hoạt động giảm-Key không đủ lớn để hiệu suất của vùng Fibonacci thực sự tỏa sáng. Đây có phải là kết luận hợp lý duy nhất, hoặc có cái gì khác tôi đang mất tích?

Answer 1

Fibonacci là tiệm nhanh hơn so với đống nhị phân (cấu trúc dữ liệu được sử dụng trong hàng đợi ưu tiên của Java), trong thuật toán của Dijkstra sẽ mất O (m + n log n) thời gian với một đống Fibonacci nhưng O (m log n) với một đống nhị phân. Điều này có nghĩa là đối với các đồ thị lớn, dày đặc, trong trường hợp xấu nhất, các vùng Fibonacci sẽ nhanh hơn.

Mặc dù đống Fibonacci nhanh hơn nhiều so với đống nhị phân, chúng có các yếu tố không đổi lớn và nhiều thao tác cơ bản trên vùng Fibonacci mất nhiều thời gian để hoàn thành. Về lâu dài, chúng sẽ hoạt động tốt hơn các phân vùng nhị phân, nhưng đối với các đồ thị nhỏ, các thuật ngữ không đổi có thể quá lớn đến nỗi mức Fibonacci thực sự chậm hơn.

Thứ hai, so sánh thời gian chạy tiệm cận (O (m + n log n) so với O (m log n)). Nếu đồ thị bạn đang sử dụng là thưa thớt (nghĩa là, m = O (n)), thì cả hai thời gian chạy tiệm cận này đều giống nhau (O (n log n)). Trong trường hợp đó, lợi thế lý thuyết của vùng heap Fibonacci không có mặt và heap nhị phân có thể là sự lựa chọn cao cấp.

Cuối cùng, lưu ý rằng ký hiệu big-O đề cập đến hành vi xấu nhất trong trường hợp này, thay vì trường hợp trung bình. Có một tờ giấy trong khi đó lại cho thấy rằng đối với các đồ thị ngẫu nhiên của một loại nhất định, thuật toán của Dijkstra về kỳ vọng sẽ thấp hơn nhiều so với số trường hợp xấu nhất của các hoạt động giảm và khóa. Trong trường hợp đó, một đống nhị phân có thể vượt trội hơn một đống Fibonacci ngay cả trên các đồ thị lớn, vì hành vi xấu nhất mà không bao giờ được kích hoạt.

Hy vọng điều này sẽ hữu ích!

Answer 2

Hố Fibonacci có nhanh hơn tiệm cận, nhưng các yếu tố không đổi của chúng không nhất thiết phải tuyệt vời. Trên đầu vào khổng lồ lố bịch hơn một triệu hoặc hơn, chúng có thể nhanh hơn, nhưng đối với đầu vào nhỏ, đống nhị phân có thể nhanh hơn đáng kể.

đống