Dane są dwie tablice o rozmiarach n oraz m. Napisz metody, które pozwolą wypełnić te tablice
losowo wygenerowanymi danymi z zakresu [1,1000000000]. Napisz metodę która zapisze do pliku
tekstowego liczność elementów zawartych w obu tablicach.
Witam, założenie jest takie, że ten algorytm powinien wykonywać się w mniej niż 3s. Zwykłym for'em wertowanie tablic dla np. 300 elementów jest bardzo czasochłonne. Jaki jest inny sposób tego rozwiązania.
Ty chyba sobie robisz jakieś jaja, albo śmigasz na 8086 jeszcze. W takim czasie to można zaalokować i wypełnić setki megabajtów pamięci, jeśli nie więcej. Pokaż kod, bo błąd leży właśnie tam...
package javaapplication21;
import java.util.Random;
public class JavaApplication21 {
private int tab[];
Random losowanie = new Random();
JavaApplication21(int n) {
tab = new int[n];
}
void wypelnij() {
for( int i = 0; i < tab.length; i++ )
tab[i] = losowanie.nextInt(1000000000)+1;
}
void licz() {
int suma = 0;
for( int i = 1; i < 1000000001; i++) {
for( int j = 0; j < tab.length; j++ ) {
if(tab[j] == i)
suma++;
}
}
System.out.println(suma);
}
public static void main(String[] args) {
JavaApplication21 java = new JavaApplication21(10);
java.wypelnij();
java.licz();
}
}
Przy takim prostym sposobie wykonuje mi się 30s.
Zmienienoe na long.
Pytanie co to ma wspólnego z zadaniem?
I co tam robią te dwie zagnieżdżone pętle, z czego jedna ma 1000000001 iteracji?
Nie sądzę, bo masz tylko jedną zmienną suma.
I żeby to zliczyć musisz iterować po wszystkich możliwych liczbach z zakresu?
Jakbyś miał to na kartce i liczył w głowie to też byś iterował od 1 do 1000000000 i dla każdej liczby sprawdzał czy istnieje w tablicy 10-cio elementowej? xD
Czy może jednak byś iterował po elementach tablicy i sprawdzał czy taki element już był i jak tak to zwiększał licznik?
1000000000 iteracji jak tu jest potrzebna tylko jedna pętla po elementach tablicy.
Zrób sobie tablicę o rozmiarze 1000000000, przeleć po tych wypełnionych tablicach i za każdym razem podbijaj licznik w odpowiednim miejscu, na przykład jak trafisz na liczbę 23 to robisz tab[23]++. Zamiast miliarda iteracji masz tyle ile miejsc w tych twoich m i n. Albo po prostu zrób mapę Integer->Integer. W czym problem?
No to ja się nie dziwię że ci się to tyle czasu wykonuje. Widać przespałeś zajęcia z Algorytmów kiedy omawianio Sortowanie Przez Zliczanie (countingsort) i wyjaśniano że co prawda jest liniowe względem n ale realny koszt to O(n)+O(k) i sporo zależy od zakresu k.
Twoje policzenie wystąpień będzie miało złożoność O(k2*n) podczas gdy można to zrobić w średnim czasie O(n). A skoro u ciebie k ma miliard a n ma 10 to chyba sam widzisz że nie trudno zrozumieć czemu ci się długo liczy?
Lekcja na dziś: Map<Integer, Integer>