Forum
Aktif konular
Üyeler
Kurallar
Arama
Java Nested Loop Alternatif Java Nested Loop Alternatif
-
Millet selamlar çözdüğüm bir soruda ( x,y koordinatları veriliyor kendi aralarında aynı diyagonal doğrultuda olanları sayan kod )iç içe for-while loop kullandım. Test caselerde 200 bin koordinat verince time exceeding yiyorum. O(n2) den kurtulmak için aklınıza gelen başka çözüm var mı? O nested yerine başka bir yapı var mı alternatif, beynim durdu?
package codeforces; import java.util.*; public class WSandBishopsB { public static void main(String[] args) { // TODO Auto-generated method stub Scanner key = new Scanner(System.in); int bishnum = key.nextInt(); int [] arr = new int[400000]; int sayac=0; for(int i=0;i<bishnum*2;i++){ int a = key.nextInt(); int b = key.nextInt(); arr[i]=a; arr[i+1]=b; i++; } for(int m=0;m<bishnum*2-1;m++){ int x=arr[m]; int y=arr[m+1]; int d=m; System.out.println(m); while(d<bishnum*2-2){ if(Math.abs(arr[d+2]-x)==Math.abs(arr[d+3]-y)){ sayac++; } d+=2; } m++; } System.out.println(sayac); key.close(); } }
input5
1 1
1 5
3 3
5 1
5 5output6
-
Bu arada sitedeki bir problem açığa çıktı. Kod içerisinde tag varsa kodu bozuyor. bknz. line:2
-
benzer bir problem var hocam burada
http://stackoverflow.com/questions/34446707/why-is-my-program-exceeding-the-time-limit
alltaki cevap muhtemelen senin de çözümündür..
ayrıca sitedeki örnekte stringbuilgder kullanılmış, sen de ekrana yazdırmak yerine dönen değeri string builder e at, işlem bitince yazdırırsın.. Diğer türlü sürekli ekrana yazdırmak doğru değil.
-
unbalanced bunu yazdı
benzer bir problem var hocam burada
http://stackoverflow.com/questions/34446707/why-is-my-program-exceeding-the-time-limit
alltaki cevap muhtemelen senin de çözümündür..
ayrıca sitedeki örnekte stringbuilgder kullanılmış, sen de ekrana yazdırmak yerine dönen değeri string builder e at, işlem bitince yazdırırsın.. Diğer türlü sürekli ekrana yazdırmak doğru değil.
hacı ben string example+="xyz"; tarzında bir kullanımdan doğan bi verimsizlikte stringbuilder kullanılıyor diye biliyordum. Onu da düzelteyim bari. O topicte yanıtı veren eleman time complexity den bahsedip geçmiş ben daha çok soruya özel bir çözüm arıyorum.
Benim çözümümde bütün koordinatlar tek dizide sırayla x1, y1, x2, y2 diye tutuluyor sonra birinciden başlayıp tarıyor diğerlerini içteki loop o taramayı yapıyor dıştaki diziyi ilerletiyor. doğal olarak O(n2) büyük inputta koşulları sağlamıyor.
-
edit: iki defa atmışwhopper tarafından 01/Şub/16 14:36 tarihinde düzenlenmiştir
-
O(n^2) den kurtulmanın tek yolu brute-force yapmaktan vazgeçmek. Onun için de matematiksel bir formül bulmak gerekir. Şuan istediğin şey mevcut kodun hızlandırılması mı complexity düşürülmesi mi ona göre cevap vericem.
-
Soruyu yazabilir misin hocam? Koddan bakıp çıkamadım işin içinden.
Ayrıca soru hakkında hiçbir şey bilmeden yapacağım yorum da şu olur: neden
int[] arr =newint[400000]; ? -
JPriest bunu yazdı
Soruyu yazabilir misin hocam? Koddan bakıp çıkamadım işin içinden.
Ayrıca soru hakkında hiçbir şey bilmeden yapacağım yorum da şu olur: neden
int[] arr =newint[400000]; ?http://codeforces.com/contest/621/problem/B
-
S2buyuk bunu yazdı
O(n^2) den kurtulmanın tek yolu brute-force yapmaktan vazgeçmek. Onun için de matematiksel bir formül bulmak gerekir. Şuan istediğin şey mevcut kodun hızlandırılması mı complexity düşürülmesi mi ona göre cevap vericem.
Ben soruya baktığımda brute force ile yapılamayacağını nasıl anlamadım da bu kodu yazdım ona şaşırıyorum.
-
Edit: Ben olayı komple yanlış anlamışım.
S2kucuk tarafından 01/Şub/16 19:26 tarihinde düzenlenmiştir -
Çok güzel soruymuş.
Tek boyutlu dizi hareket kabiliyetini azaltır. İki boyutlu dizi ile gitsen, sadece i değil j seçeneğin de olur, karşılaştırma yaparken falan rahat edersin.
Ayrıca String concatenation ile StringBuilder.append() karşılaştırmasında (içeriğe göre değişir denmesine rağmen) genel olarak pek de bir fark yokmuş.
http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java
Ama StringBuffer vs StringBuilder denirse, StringBuilder daha performanslı.
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla