Birkaç sıralama sorusu

Question

Yapmış olduğumun ötesindeki quicksort algoritmasıyla (test ettiğim kadarıyla) geliştirmenin bir yolunu buldum. Bunu test etmek için çalışıyorum ve sonra bu kelimeyi öğrenmek istiyorum. Ancak, bazı şeylerle ilgili bazı yardımları takdir ediyorum. Sorularım işte burada. Tüm kodlarım bu arada C++. Benim quicksort karşılaştırarak edilmiştir türlü

1. Bir C++ Standart Kitaplığı'ndan std :: çeşittir. Ancak, son derece yavaş gibi görünüyor. Ben sadece ints ve longs dizilerini sıralıyorum, ama hem Quicksort'umdan hem de Bentley ve McIlroy (ve belki de Sedgewick) tarafından standart bir quicksort'tan yaklaşık 8-10 kat daha yavaş görünüyor. Kimsenin neden bu kadar yavaş olduğuna dair bir fikri var mı? Sıralama için kullandığım kod sadece std :: sort (a, a + numelem); Burada a, longs veya ints dizisidir ve numelem dizideki öğe sayısıdır. Sayılar çok rasgele ve farklı boyutlarda ve tekrarlanan farklı element miktarlarını denedim. Ayrıca qsort'u denedim, ama beklediğimden daha da kötü. Düzenleme: Bu ilk sorumu dikkate almayın - çözüldü.

2. Quicksort'umla karşılaştırmak için daha iyi quicksort uygulamalarını bulmak istiyorum. Şimdiye kadar bir Bentley-McIlroy bir var ve ben de Vladimir Yaroslavskiy'nin çift pivot quicksort ilk yayınlanan sürümü ile karşılaştırdık. Buna ek olarak, jdk 7 kaynağından optimize edilmiş dual-pivot quicksort ve timsort (ki ben inanıyorum birleştirme sıralama) yerleştirmeyi planlıyorum. Diğer iyi hızlı uygulamalar nasıl yapılır? C veya C++ içinde değilse, bu iyi olabilir, çünkü ben portta oldukça iyiyim, ama eğer onları biliyorsanız C veya C++ olanları tercih ederim.

3. Eklentilerim ile ilgili sözlüğü quicksort'a nasıl bildirirsiniz? Şimdiye kadar benim quicksort test ettiğim diğer tüm hızlardan çok daha hızlı görünüyor. Hızının ana kaynağı, yinelenen öğeleri bulduğum diğer yöntemlerden çok daha verimli bir şekilde ele almasıdır. Tekrarlanan elementleri kontrol etmek için çok zaman eklemeden en kötü durum davranışını neredeyse tamamen ortadan kaldırır. Bunu Java forumlarında yayınladım ama yanıt alamadım. Aynı zamanda Jon Bentley'e yazmayı denedim çünkü o, çift pivot çabukluğuyla Vladimir'le çalışıyordu ve yanıt alamadım (bununla çok şaşırmadım). Bu konuda bir makale yazmalı ve arxiv.org’a koymalı mıyım? Bazı forumlarda yayınlamalı mıyım? Göndermem gereken bazı posta listeleri var mı? Şimdi bir süredir bunun üzerinde çalışıyorum ve yöntemim yasal. Araştırma yayıncılığı konusunda biraz deneyimim var çünkü hesaplamalı fizikte doktora adayıyım. Üniversitemin Bilgisayar Bilimleri bölümünde birisine yaklaşmaya çalışmalı mıyım? Bu arada, farklı bir çift pivot quicksort da geliştirdim, ancak tek-pivot quicksort'umdan daha iyi değil (bazı veri kümeleriyle Vladimir'in dual-pivot quicksort'undan daha iyi olsa da).

Yardımlarınız için gerçekten minnettarım. Sadece bilgisayar dünyasına elimden geleni eklemek istiyorum. Bu ya da böyle saçma bir şeyi patentlemekle ilgilenmiyorum.

Answer 1

Çalışmanıza güveniyorsanız, en kısa sürede üniversitenizde bilgili birisiyle mutlaka konuşmaya çalışın. Kodunuzun makinenizdeki başka bir prosedürden daha hızlı çalıştığını göstermek için yeterli değildir. Algoritmanızın analiziyle elde ettiğinizi iddia ettiğiniz performans kazancını matematiksel olarak kanıtlamanız gerekir. Yapmanız gereken ilk şey, karşılaştırdığınız algoritmaların en iyi şekilde uygulandığından ve derlendiğinden emin olmanızdır - kendinizi burada kandırıyor olabilirsiniz. Bir bireyin, kabul edilen varyantları hakkında tam bir bilgiye sahip olmadan, böyle önemli bir sıralama yöntemi üzerinde bu kadar belirgin bir gelişmeye ulaşma olasılığı, sadece küçük gözükmektedir. Ancak, sizi cesaretlendirmeme izin verme. Yine de ilginç olmalı. Kodu buraya göndermek ister misiniz? ...Ayrıca, fastsort özellikle en kötü durum senaryolarına karşı hassas olduğundan, çalıştırmayı seçtiğiniz testler de büyük bir etkiye sahip olabilir. Genel olarak, çok sayıda eşdeğer elemanla veya halihazırda yüksek oranda sıralanmış olan herhangi bir veri setinin hiçbir zaman quicksort için iyi bir seçenek olmadığını söyleyebilirim - ve bu durumla mücadele için zaten iyi bilinen yollar ve daha iyi alternatif sıralama yöntemleri vardır .

Answer 2

Gerçekten bir atılım yaptıysanız ve bunu kanıtlamak için matematiğe sahipseniz, onu Journal of the ACM numaralı belgede yayımlamaya çalışmalısınız. Bilgisayar bilimleri için kesinlikle en prestijli dergilerden biri.

İkinci en iyi, Transactions on Software Engineering gibi IEEE journals'dan biri olacaktır.