Kilka pytań o sortowanie

Question

Znalazłem sposób, który poprawia (o ile testowałem) algorytm quicksort poza to, co już zostało zrobione. Pracuję nad testowaniem tego, a potem chcę się o tym dowiedzieć. Jednak byłbym wdzięczny za pomoc w niektórych sprawach. Oto moje pytania. Cały mój kod jest w C++ przy okazji.

1. Jednym z rodzajów, w porównaniu do mojego quicksort, jest std :: sort z biblioteki standardowej C++. Wydaje się jednak, że jest bardzo powolny. Sortuję tylko tablice int i longs, ale wydaje mi się, że są one około 8-10 razy wolniejsze od obu quicksortów i standardowego quicksortu Bentleya i McIlroy'a (i może Sedgewicka). Czy ktoś ma jakieś pomysły, dlaczego jest tak powolny? Kod, którego używam do sortowania, to tylko std :: sort (a, a + numelem); gdzie a jest tablicą longs lub ints i numelem jest liczbą elementów w tablicy. Liczby są bardzo losowe i próbowałem różnych rozmiarów, a także różnych ilości powtarzanych elementów. Próbowałem też qsort, ale jest jeszcze gorzej, jak się spodziewałem. Edytuj: zignoruj ​​to pierwsze pytanie - zostało rozwiązane.

2. Chciałbym znaleźć więcej dobrych implementacji quicksort do porównania z moim quicksort. Do tej pory mam wersję Bentley-McIlroy, a także porównałem ją z pierwszą opublikowaną wersją dwumiejscowego quicksort Vladimira Yaroslavskiego. Ponadto planuję przeniesienie timsorta (który jest sortowaniem według mnie) i zoptymalizowanego quicksortu z dwoma pivotami ze źródła jdk 7. Jakie inne dobre implementacje quicksorts znasz? Jeśli nie są w C lub C++, to może być w porządku, ponieważ jestem całkiem dobry w przenoszeniu, ale wolałbym te C lub C++, jeśli je znasz.

3. Jak poleciłbyś poznać słowo o moich dodatkach do quicksort? Do tej pory mój quicksort wydaje się być znacznie szybszy niż wszystkie inne quicksorts, które testowałem to przeciwko. Głównym źródłem jego szybkości jest to, że obsługuje on powtarzające się elementy znacznie wydajniej niż inne metody, które znalazłem. Niemal całkowicie eliminuje zachowanie najgorszego przypadku, nie dając wiele czasu na sprawdzenie powtarzających się elementów. Pisałem o tym na forach Java, ale nie otrzymałem odpowiedzi. Próbowałem też napisać do Jona Bentleya, ponieważ pracował z Vladimirem nad jego podwójnym pchnięciem i nie otrzymał żadnej odpowiedzi (chociaż nie byłem tym strasznie zaskoczony). Czy powinienem napisać o tym artykuł i umieścić go na arxiv.org? Czy powinienem publikować posty na niektórych forach? Czy istnieje lista mailingowa, którą powinienem opublikować? Pracuję nad tym od jakiegoś czasu i moja metoda jest prawidłowa. Mam pewne doświadczenie w publikowaniu badań, ponieważ jestem doktorantem w dziedzinie fizyki obliczeniowej. Czy powinienem spróbować skontaktować się z kimś z wydziału informatyki na moim uniwersytecie? Nawiasem mówiąc, opracowałem także inny podwójny przegubowy quicksort, ale nie jest on lepszy niż mój quicksort z jednym pivotem (choć jest lepszy niż podwójny pchnięcie Vladimira z niektórymi zbiorami danych).

Bardzo dziękuję za pomoc. Chcę tylko dodać, co mogę, do świata komputerów. Nie interesuje mnie opatentowanie tej czy innej absurdalnej rzeczy.

Answer 1

Jeśli masz zaufanie do swojej pracy, zdecydowanie spróbuj omówić to z kimś, kto ma wiedzę na twoim uniwersytecie tak szybko, jak to możliwe. Nie wystarczy pokazać, że twój kod działa szybciej niż inna procedura na twoim komputerze. Musisz matematycznie udowodnić, jaki przyrost wydajności osiągnąłeś dzięki analizie swojego algorytmu. Powiedziałbym, że pierwszą rzeczą, którą należy zrobić, to upewnić się, że oba algorytmy, które porównujesz, są zaimplementowane i skompilowane optymalnie - możesz po prostu oszukać się tutaj. Prawdopodobieństwo, że dana osoba osiągnie tak znaczną poprawę w tak ważnej metodzie sortowania, nie posiadając już dogłębnej wiedzy na temat akceptowanych wariantów, wydaje się po prostu niewielkie. Jednak nie pozwól mi cię zniechęcić. To i tak powinno być interesujące. Czy chciałbyś opublikować kod tutaj? ...Ponadto, ponieważ quicksort jest szczególnie podatny na najgorsze scenariusze, testy, które wybierzesz, mogą mieć ogromny wpływ, podobnie jak wybór czopów. Ogólnie rzecz biorąc, chciałbym powiedzieć, że każdy zestaw danych z dużą liczbą równoważnych elementów lub taki, który jest już w wysokim stopniu sortowany, nigdy nie jest dobrym wyborem dla quicksort - i są już dobrze znane sposoby zwalczania tej sytuacji i lepsze alternatywne metody sortowania .

Answer 2

Jeśli rzeczywiście dokonałeś przełomu i masz matematykę, aby to udowodnić, powinieneś spróbować opublikować go w numerze Journal of the ACM. To zdecydowanie jeden z bardziej prestiżowych czasopism dla informatyków.

Drugim najlepszym rozwiązaniem byłby jeden z IEEE journals, taki jak Transactions on Software Engineering.