Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?

Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc całkowity czas potrzebny do uruchomienia algorytmów?

Jest to w rzeczywistości głęboka kwestia, która zawiera pewne metodyczne i pragmatyczne odpowiedzi. Zakładam, że chcesz wiedzieć coś o dostępnym algorytmie (algorytmach) . Jeśli chcesz wiedzieć, który algorytm działa lepiej na danej maszynie na danych wejściowych, kontynuuj i mierz środowiska wykonawcze. Jeśli chcesz porównać jakość kompilatora dla danego algorytmu, śmiało i zmierz czasy działania. Aby dowiedzieć się czegoś o algorytmie, nie rób tego.

Pozwól mi najpierw podać kilka powodów, dla których używanie środowisk wykonawczych nie jest dobrym pomysłem.

1. Ogólne środowiska
   wykonawcze mierzone za pomocą jednego języka i jednego kompilatora na jednym komputerze mają niewielkie znaczenie, jeśli zmienisz dowolny komponent. Nawet nieznacznie różne implementacje tego samego algorytmu mogą działać inaczej, ponieważ uruchamiasz pewną optymalizację kompilatora w przypadku, ale nie w innym.
2. Prognozowanie
   Masz więc kilka środowisk uruchomieniowych dla niektórych danych wejściowych. Co to mówi o czasie wykonywania niektórych innych danych wejściowych? Ogólnie nic.
3. Znaczenie
   Zwykle nie porównujesz wszystkich danych wejściowych (o pewnym rozmiarze), co natychmiast ogranicza twoją zdolność porównywania algorytmów: może twój zestaw testowy wywołał najgorszy przypadek w jednym i najlepszy przypadek w drugim algorytmie? A może twoje dane wejściowe były zbyt małe, aby pokazać zachowanie w czasie wykonywania .
4. Pomiary Dobrze
   mierzone czasy wykonania nie są trywialne. Czy jest JIT? Czy było spór, tj. Czy odliczasz czas, gdy algorytm nawet nie działał? Czy możesz odtworzyć dokładnie ten sam stan komputera dla innego przebiegu (innego algorytmu), w szczególności dla równoległych procesów i pamięci podręcznych? Jak radzone jest opóźnienie pamięci?

Mam nadzieję, że przekonały cię, że środowiska wykonawcze są okropną miarą do porównywania algorytmów i że potrzebna jest ogólna, abstrakcyjna metoda badania środowiska uruchomieniowego algorytmu.

Do drugiej części pytania. Dlaczego korzystamy z porównań lub podobnych operacji elementarnych?

1. Zdolność analityczna
   Zakładając, że chcesz przeprowadzić analizę formalną, musisz być w stanie to zrobić. Liczenie pojedynczych stwierdzeń jest bardzo techniczne, a czasem nawet trudne; mimo to niektórzy to robią (np. Knuth). Liczenie tylko niektórych instrukcji - dominujących w środowisku wykonawczym - jest łatwiejsze. Z tego samego powodu często „tylko” badamy (górne granice) środowisko wykonawcze w najgorszym przypadku.

2. Dominacja
   Wybrana operacja dominuje w środowisku wykonawczym. Nie oznacza to, że wnosi najwięcej czasu wykonywania - porównania wyraźnie nie, np. W Quicksort podczas sortowania liczb całkowitych wielkości słowa. Ale są one wykonywane najczęściej , więc licząc je, liczysz, jak często uruchamiane są najczęściej wykonywane części algorytmu. W związku z tym twój asymptotyczny czas pracy jest proporcjonalny do liczby dominujących operacji elementarnych. Właśnie dlatego wygodnie posługujemy się notacją Landau i słowem „środowisko wykonawcze”, mimo że liczymy tylko porównania.

Pamiętaj, że przydatne może być policzenie więcej niż jednej operacji. Na przykład niektóre warianty Quicksort wymagają więcej porównań, ale mniej swapów niż inne (średnio).

Jeśli warto, po zapoznaniu się z całą teorią, warto ponownie sprawdzić środowiska wykonawcze, aby sprawdzić, czy prognozy przedstawione przez teorię są prawidłowe. Jeśli nie są, twoja teoria nie jest przydatna (w praktyce) i musi zostać rozszerzona. Hierarchia pamięci jest jedną z pierwszych rzeczy, które zdajesz sobie sprawę, że są ważne, ale brakuje ich w podstawowych analizach.

Wynika to z faktu, że całkowity czas uruchomienia algorytmów zależy od sprzętu, na którym jest uruchamiany, wraz z innymi czynnikami. Nie jest wiarygodne porównywanie dwóch algorytmów, jeśli jeden działa na Pentium 4, a drugi na, powiedzmy, Core i7. Nie tylko to, ale powiedzmy, że oba działały na tym samym komputerze. Co powiedzieć, że oba mają taki sam czas procesora? Co się stanie, jeśli jakiś inny proces ma wyższy priorytet niż proces jednego z algorytmów?

Aby temu zaradzić, oddzielamy się od tego całkowitego czasu do ukończenia, a zamiast tego porównujemy na podstawie tego, jak dobrze skaluje się algorytm. Być może zauważyłeś notację taką jak O (1) lub O (n ^ 2) w pracach badawczych. Może to wymagać nieco więcej czytania, jeśli jesteś zainteresowany See notacji Big O .

Ponieważ inne odpowiedzi wyjaśniają, dlaczego analizujemy środowisko wykonawcze pod względem liczby elementarnych operacji, przedstawię kilka powodów, dla których porównania są właściwą miarą wielu (nie wszystkich) algorytmów sortowania:

• w przypadku wielu algorytmów sortujących liczba porównań dominuje w czasie wykonywania, tj. co najmniej tyle porównań jest wykonywanych, jak każda inna operacja elementarna
• porównania są kosztowną operacją; pomyśl o tym, jak procedura sortowania jest implementowana w bibliotece: funkcja sortująca przekazuje tablicę elementów i wskaźnik do funkcji, która porównuje dwa elementy; generalnie wywołanie i oczekiwanie na wykonanie funkcji porównania jest droższe niż operacje „wewnętrzne”; ponieważ funkcja ta jest zapewniana przez użytkownika, trudniej ją zoptymalizować
• (może to być, ale nie musi być dobrym powodem), możemy powiedzieć coś interesującego o liczbie porównań, które są wystarczające i konieczne do posortowania sekwencji; wiemy, jak to zrobić w najgorszym przypadku i średnio dla różnych dystrybucji, nawet jak zaprojektować algorytm, który zbiega się w optymalny sposób, ponieważ jest uruchamiany na elementach próbkowanych z nieznanej dystrybucji ( algorytmy samodoskonalące ); wiemy, jak to zrobić, gdy niektóre porównania są podane za darmo ( Sortowanie z częściowymi informacjami )