whats en hızlı dize toplama yapısı/algoritması ile başlar ve/veya aramalar içerir

Question

Şu anki durumum var: Büyük olasılıkla dizgiler (250.000'den fazla söyleyeyim) ortalama uzunluğu belki 30. Bunların içinde birçok arama yapmaktır. Bunlar çoğunlukla StartsWith ve İçerdekilerdir.

Koleksiyon çalışma zamanında statiktir. Bu, seçim koleksiyonunun ilk okuma ve doldurma işleminin sadece bir kez yapıldığı anlamına gelir. Bu nedenle, veri yapısını oluşturmanın performansı kesinlikle önemli değildir. Bellek de bir sorun değil: aynı zamanda gerekirse her biri için aynı veriyi içeren iki koleksiyona sahip olmamam gerektiği anlamına gelir (başlangıç ​​için bir tane diğeri için olan gibi). Sadece önemli olan, arama koşullarıyla eşleşen tüm öğeleri döndürmesi gereken aramaların performansıdır.

startswith için bir Trie veya Radix-ağacın üzerine geldi .. ama belki daha iyi seçimler vardır? İçin

I (alışkanlık veri bu miktarı ile çok hızlı olacak bir listedeki bir linq sorgusu çalıştıran yanında) henüz hiç iyi bir fikir var .. içeriyor.

Herkese şimdiden teşekkürler!

güncelleme: Önemli bir kısmını unuttular İçeren ile i koleksiyonunda kesin eşleşmeleri demek .. ama bir suffix tree sizi sağlayacak Bina verilen aranacak

Answer 1

ihtiva koleksiyonundaki tüm dizeleri bulmak isterken O(1) içinde tüm dizelerinizde bir alt dizgi araması yapın. içimdeki bilgiçlik yardımcı ama n sizin alt dize eşleşmesi ve m alt dize boyutu sorgulanan olan dizeleri sayısıdır gerçekten O(n + m) var olduğuna dikkat olamaz.

Yani sormak bir sonek ağaç nedir? En basit uygulamasında, bir meraklı ekleme yöntemine sahip bir çentiktir: bir dizgenin eklenmesine ek olarak, bu dizgenin olası tüm soneklerini de trie'ye ekler. Bu veri yapısında, bir alt dizgi araması tüm olası soneklerin bir önek araması haline gelir. Ayrıca, önek aramalarını yapmak istediğinizden, eklenen her dizenin ve sorgu alt dizelerinin önüne özel bir karakter eklemek istersiniz. Özel karakter, bir sonek ve tam bir dize arasında ayrım yapmanıza izin verecektir. Bir sonek ağacının bu uygulama oldukça basit olsa da

, aynı zamanda (O(n^2) uzay ve zamanı inşa) çok verimsiz. Neyse ki, alanı ve zaman sınırlarını büyük ölçüde azaltabilen başka daha verimli uygulamalar var. Bunlardan biri olan Ukkonen'in algoritması, this SO answer'da çok iyi açıklanmış ve O(n)'a bağlı alanı getiriyor. Ayrıca, ek ağaçların eşdeğer ama daha etkili bir temsilidir suffix arrays içine bakmak isteyebilirsiniz.

Ben sadece bunları bilmiyorum (muhtemelen kullanım örneği için tatlı isabetli olurdu bunlardan biri) orada eki ağaçların çok çok daha fazla uygulama vardır bilirken. Bir uygulamaya geçmeden önce konuyla ilgili bazı araştırmalar yapmanızı tavsiye ederim.