Farklı altyazı arama (ala strstr) algoritmalarını ve uygulamalarını değerlendirmeye çalışıyorum ve en kötü durum performansını ve olası olası köşe hatalarını yakalayacak iyi hazırlanmış bir iğne ve saman dizisi arıyordum. Sanırım onları kendim halledebilirim ama birisinin bir yerde oturmuş iyi bir test örneği koleksiyonuna sahip olması gerektiğini düşünüyorum ...Karşılaştırma ve stres testi için alt test arama algoritmalarında iyi test senaryoları nelerdir?
Sorunuzu doğrudan yanıtlamıyorsunuz, ancak algoritmaları kitapta bulabilirsiniz - Algoritmalar Dizeler, Ağaçlar ve Diziler: Bilgisayar Bilimi ve Hesaplamalı Biyoloji - ilginç (alt dize aramada birçok yeni algoritmalar vardır). Ek olarak, aynı zamanda özel ve karmaşık vakaların iyi bir kaynağıdır.
Teşekkürler, ama gerçekten test/kıyaslama fikirleri arıyorum. Burada algoritmaları üzerinde iyi bir referans vardır: http://www-igm.univ-mlv.fr/~lecroq/string/index.html İki Way ve SMOA büyük O'da (sadece "hızlı" gibi görünüyor) Geri kalanlar uzayda kararsız olduğu ve stresli bellek koşullarında başarısız olabileceği için, hata durumlarına izin verilmeyen kodlara uygun algoritmalar. Bununla birlikte, naif uygulama da çok ilginçtir ve son derece büyük iğne boyutlarına kadar optimal olabileceği düşünülmektedir. Denediğim kısa ve ılımlı dizeler için glibc'in İki Yolundan yaklaşık iki kat daha hızlı. –
Bağlantı için teşekkürler! Bu, tam dizgi eşleme algoritmalarının çok güzel bir derlemesidir. – tathagata
Bazı düşünceler ve kendime kısmi cevap: kaba kuvvet algoritması için
En kötü durum:
a^(n+1) b
(a^n b)^m örn (yxyxyxxyxyxyxy)^n yılında yxyxyxxyxyxyxx gibi
Something: SMOA için aabaabaabaabaabaabaab
Kötü durumda aaab. Daha fazla iyileştirme ihtiyacı var. Her ilerlemenin, kısmi eşleşmenin yalnızca yarısı kadar olduğundan emin olmaya çalışıyorum ve bu maksimum son ek hesaplaması, maksimum geri dönüş miktarını gerektiriyor. Eminim doğru yolda olduğumdan eminim çünkü bu tür bir durum, SMOA (asimptotik olarak 6n+5) uygulamasının, asimptotik olarak iki yönlü (gycc'nin İki Yolundan) daha yavaş çalışmasını sağlamak için bulduğum tek yoldur. 2n-m ancak orta derecede ağrılı ön işleme ek yüküne sahiptir. tabanlı şey haddeleme-karma için
En kötü durum:
bayt dizisi iğnenin karma ile karma çarpışmalar neden ne olursa olsun. Herhangi bir makul hızlı karma ve belirli bir iğne için, karma her noktada iğnenin karma ile çarpışan bir samanlık inşa etmek kolay olmalıdır. Ancak, en kötü durum davranışını elde etmenin tek yolu olan eş zamanlı olarak uzun kısmi eşlemeler oluşturmak zor görünüyor. Doğal olarak, en kötü durum davranışları için, iğnenin belirli bir periyodikliğe sahip olması ve sadece son karakterleri ayarlayarak hashı taklit etmesinin bir yolu olmalıdır.
En kötü durum İki Way :
nontrivial MS ayrışma ile çok kısa iğne gibi görünüyor samanlık iğne sağ yarısı bileşeninde yanlış pozitif tekrarlanan içerir nerede - - dacdacdacdacdacdacdac gibi bir şey - bac gibi bir şey . Bu algoritmanın yavaşlayabilmesinin tek yolu (glibc yazarlarının bunu kötü bir şekilde uygulayabilmesi ...) dış döngü yinelemesini defalarca yapmak ve tekrar tekrar bu yükü uygulamaktır (ve kurulumun genel giderlerini önemli ölçüde arttırır).
diğer algoritmalar:
ben uzayda O(1) ve düşük ön işleme yükü olan algoritmaları gerçekten sadece ilgilendiğim, bu yüzden bu kadar onların kötü durumda bakmadım. En azından Boyer-Moore (O(n) yapmak için yapılan değişiklikler olmadan), O(nm) haline geldiğinde en kötü durumdadır.
Şu anda test etmek için zamanım yok gerçi, ilginç istatistikler verebilir bir prosedür:
Randomize dize uzunluğu boyunca, o zaman, bu uzunluğun dize içeriğini üzerinde rastgele sonra ofset/uzunluğu boyunca rastgele alt dize (dizede muhtemelen bir şey değildir), sonra şekilde rasgele alt dize (muhtemelen hiç), tekrarı üzerinde clobber. Bir bir karakter ekleyerek anda kümesindeki bir dizi takviyesi ile verilen tüm dizeleri oluşturmak, boş bir dizge ile başlayarak
:
Konteyner dizeleri üretebilir şekilde tekrar tekrar (. solunu test değerlerini ihtiva) sola veya sağa (her ikisi de) alfabe.
üreten konteyner dizeleri alfabe sizin tarafınızdan seçilir.
Sen testi içerdiği dizeler için 2 alfabe. Bir tanesi konteynır dizilerini oluşturan diğeri ise tamamlayıcısıdır.
nihai hedefiniz burada ne var? Sadece algoritmaları öğrenmek için? Yoksa alışılmadık iğneler/haystacks içeren bir uygulamanız var mı? – Cascabel
Kısa vadede, sadece algoritmaları öğrenmek için. Uzun vadede ise, bir C kütüphanesi uygulama strstr saflık yaklaşım kullanıyor ortalamanın performansından çok küçük boyutu yönelik var ve değiştirmeyi göz önünde istediğinizi O (n) zaman/O biri (ile 1) uzay algoritmaları. SMOA ümit verici görünüyor, ancak 6n + 5 üstündeki karşılaştırmalarda sabit 6'nın pratikte sorun yaratıp yaratmadığını görmek istiyorum (ilk testlerimin uzaktan aklı başında verilerde daha düşük olduğunu ve performansın tüm özel olmaksızın glibc ile karşılaştırılabilir olduğunu görmek istiyorum. kısa/uzun iğneler için muhafaza). –