Bir proje üzerinde çalışıyorum ve çalışma süresini optimize etmem gerekiyor. String.contains() çalışma zamanı TreeSet.contains() ile aynıdır, O (logN) nedir?Java'daki String.contains() ürününün Big-O nedir?
Sormamın nedeni, Şarkıların bir dizi söz dizimi içerdiği bir TreeMap<String, TreeSet<Song>> yapıyorum. Verimliliğe bağlı olarak, Şarkı içindeki lirik sözcüklerin bir Setini dahil etmeyi ve String yerine bunun üzerinde arama yapmayı düşünüyorum.
En iyi bilinen algoritmalardan biri, en iyi durumda sublineer performans gösterebilmesine rağmen O (n) olan Boyer-Moore dizgi arama algoritmasıdır.
Java'da hangi algoritma kullanıldığında, hangi öğenin indirileceğine bağlıdır. Örneğin OpenJDK, en iyi durumda O (nm) ve lineer performansta çalışan bir naif algoritma kullanmaktadır. 1770-1806 here numaralı çizgilere bakınız.
söylenen makalenin en fazla 3n karşılaştırması yaptığı için O (n) olduğunu söylediniz. "en kötü durum O (n)" bir totolojidir - tanım gereği O (n) en kötü durumdur :) –
@Nicholas White: Düzeltme için teşekkürler. –
jdk1.6.0_23, https://programmers.stackexchange.com/questions/65558/why-does-javas-string-class-not-, adresinden yola çıkarak, çağdaş bir OpenJDK olarak aynı 'String.indexOf()' uygulamasına sahipti. Bir-daha-verimli-endeks uygulamak. Birisi, 'String.contains()' – rakslice
Ayrıca TreeMap yerine bir tray kullanarak deneyebilirsiniz (Java olmasına rağmen hiçbir yerleşik Trie uygulaması)
[Trie referansı] (https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/) – cellepo
ama bir pislik ya da bir şey olmaya çalışıyorum değil: Neden profiline değil? –
Test için zamanım varsa, belki. Proje ile çalışmak istediğim başka bir test daha var: Treeet ve hashset arasındaki çalışma zamanı varyasyonları. Bir günde 30 saat olsaydı, hala her şey için yeterli zaman olmazdı! – Jason