(Dis) Udowodnienie, że jeden algorytm działa szybciej niż inny dzięki wewnętrznym językom

Question

W przypadku projektu na uniwersytecie, musieliśmy wprowadzić kilka różnych algorytmów, aby obliczyć wartości ekwiwalentne, gdy dany zestaw elementów i zbiór relacji między tymi elementami .

Zostaliśmy poinstruowani, aby wdrożyć, między innymi, algorytm wyszukiwania i optymalizacji Union-Find (Union by Depth, Size). Przez przypadek (robiąc coś, co uważałem za konieczne dla poprawności algorytmu), odkryłem inny sposób optymalizacji algorytmu.

To nie jest tak szybkie, jak w przypadku Union By Depth, ale blisko. Nie mogłem dla mnie zrozumieć, dlaczego było tak szybko, jak to było, więc skonsultowałem się z jednym z asystentów, którzy też nie mogli tego zrozumieć.

Projekt był w Java i datastructures używałem były oparte na prostych tablic liczb całkowitych (obiekt, a nie int) Później, przy ocenie projektu, powiedziano mi, że to chyba coś wspólnego z „Java buforowanie ", ale nie mogę znaleźć niczego online na temat tego, w jaki sposób buforowanie może to zmienić.

Jaki byłby najlepszy sposób, bez obliczania złożoności algorytmu, aby udowodnić lub obalić, że moja optymalizacja jest tak szybka z powodu sposobu robienia rzeczy przez Javę? Wdrożenie go w innym, (niższym poziomie?) Języku? Ale kto mówi, że język nie zrobi tego samego?

Mam nadzieję, że wyraziłem się jasno,

dzięki

Answer 1

Jedynym sposobem jest udowodnić najgorszego przypadku (case średnia itp) złożoność algorytmu.

Bo jeśli nie, to może być po prostu konsekwencją kombinacji

• Poszczególne dane
• Wielkość danych
• Niektóre aspekt sprzętu
• Niektóre aspekt implementacji języka:
• itd.

Answer 2

Jeśli masz dostęp do kodu źródłowego - i wydaje mi się, że kod źródłowy JDK jest dostępny, możesz przeszukać go, aby znaleźć odpowiednie szczegóły implementacji.

Answer 3

Generalnie bardzo trudno jest wykonać takie zadanie, biorąc pod uwagę nowoczesne maszyny wirtualne! Tak jak ty podpowiadasz, wykonują wszelkiego rodzaju rzeczy za plecami. Wywołania metod zostają wstawione, obiekty są ponownie używane. Itd. Najlepszym przykładem jest to, w jaki sposób zbędne pętle są kompilowane, jeśli oczywiście nie wykonują niczego poza liczeniem. Lub w jaki sposób funtioncall w programowaniu funkcjonalnym jest inline lub zoptymalizowany pod ogonem.

Co więcej, trudno jest udowodnić swój punkt w ogóle na temat dowolnego zestawu danych. O (n^2) może być znacznie szybszy niż pozornie szybszy, powiedzmy, O (n), algorytm. Dwa przykłady:

1. Sortowanie bąbelkowe jest szybsze przy sortowaniu zbioru posortowanego w przybliżeniu niż sortowanie szybkie.
2. Szybki sortowanie w ogólnym przypadku, oczywiście, jest szybsze.

Ogólnie notacja big-o celowo ignoruje stałe, które w praktyce mogą oznaczać życie lub śmierć dla realizacji. i te stałe mogły być tym, co cię uderzyło. Tak więc w praktyce 0.00001 * n ^ 2 (powiedzmy, że czas działania twojego algorytmu) jest szybszy niż 1000000 * n log n

Zatem rozumowanie jest trudne, biorąc pod uwagę ograniczone informacje, które podajesz.

Answer 4

Prawdopodobnie kompilator lub JVM znalazły optymalizację kodu. Możesz spróbować odczytać kod bajtowy, który jest wyprowadzany przez kompilator javac i wyłączać kompilację JIT środowiska wykonawczego z opcją -Djava.compiler=NONE.