TriPrvkyPola

Reiki · Napísal **Reiki**: 02.12.2010 13:32

Ahojte, chcem naprogramovat, aby mi vypisalo 3 najvacsie prvky z pola.

Z toho co som robil mi vzniklo toto:

Kód:

    public int[] maxTriPrvky(){
        int[] vysledok = new int[3];
        int max1 = pole[0];
        int max2 = pole[1];
        int max3 = pole[2];
        if((velkostPola > 3) && (max1 > max2) && (max2 > max3)){
            for(int i=3; i < velkostPola; i++){
                if(pole[i] > max1){
                    max3 = max1;
                    max2 = max1;
                    max1 = pole[i];
                }
                else if(pole[i] > max2){
                        max3 = max2;
                        max2 = pole[i];
                }
                else{
                    if(pole[i] > max3)
                        max3 = pole[i];
                }
            }
        }
        vysledok[0] = max1;
        vysledok[1] = max2;
        vysledok[2] = max3;
        return vysledok;
    }

Aj ked sa to da zkompilovat, nezda sa mi, ze by to pracovalo vzdy spravne. Je dost mozne, ze je to uplne zle. Preto prosim o radu.

coldak · Napísal **coldak**: 02.12.2010 14:03

predpokladam ze je to java. ide ti o naucenie sa praci s polom alebo ti ide o vysledok ?

Reiki · Napísal autor témy **Reiki**: 02.12.2010 14:09

Ano je to java. No v prvom rade sa chcem s tym polom naucit pracovat. Ale na druhej strane vysledok chcem tiez

coldak · Napísal **coldak**: 02.12.2010 14:14

najjednoduchsie bude pouzit java funkciu Arrays.sort() ktora ti zosortuje hodnoty pola a ty si nacitas posledne tri, popripade zosortujes reverzne a nacitas prve tri
http://www.exampledepot.com/egs/java.ut ... Array.html

Reiki · Napísal autor témy **Reiki**: 02.12.2010 14:40

Dakujem.
Co sa tyka toho case sensitive. Niekde som cital, ze sa to dava nejak do hlavicky triedy? Mozno, ze si to mylim s niecim inym.

// pridané po 18 minútach od posledného príspevku

No s tym array som sa domotal, budem si to musiet lepsie pozriet, lebo mi teraz nic ani zkompilovat nejde.

ado21 · Napísal **ado21**: 06.12.2010 17:19

coldak píše:

najjednoduchsie bude pouzit java funkciu Arrays.sort() ktora ti zosortuje hodnoty pola a ty si nacitas posledne tri, popripade zosortujes reverzne a nacitas prve tri
http://www.exampledepot.com/egs/java.ut ... Array.html

to je casovo narocne O(nlogn). Naco, ak sa to da v case O(n)?

coldak · Napísal **coldak**: 06.12.2010 17:53

ado21 píše:

to je casovo narocne O(nlogn). Naco, ak sa to da v case O(n)?

a to tvoje riesenie je rovnako jednoduche ?

ado21 · Napísal **ado21**: 06.12.2010 18:56

coldak píše:

a to tvoje riesenie je rovnako jednoduche ?

Kód:

/*
 * k je pocet maximalnych prvkov
 */
public int[] najdiMax(int[] pole, int k)
{      
   int[] vysledok = new int[k];
   for(int i = 0; i < vysledok.length; i++) {
      int max = Integer.MIN_VALUE;
      int indexMax = 0;
      for (int m = 0; m < pole.length; m++) {
         if (pole[m] > max) {
            max = pole[m];
            indexMax = m;
         }
      }
      vysledok[i] = max;
      pole[indexMax] = Integer.MIN_VALUE;         
   }
   return vysledok;
}

Tvoje ma vzdy 0(nlogn). Oznacme pocet maximalnych prvokov k. Moje riesenie ma 0(nk) a v pripade k << n, co je asi velmi realne predpokladat, bude mat O(kn) = O(n). V jeho pripade sa je k = 3...

coldak · Napísal **coldak**: 06.12.2010 19:58

ado21 píše:

Kód:

/*
 * k je pocet maximalnych prvkov
 */
public int[] najdiMax(int[] pole, int k)
{      
   int[] vysledok = new int[k];
   for(int i = 0; i < vysledok.length; i++) {
      int max = Integer.MIN_VALUE;
      int indexMax = 0;
      for (int m = 0; m < pole.length; m++) {
         if (pole[m] > max) {
            max = pole[m];
            indexMax = m;
         }
      }
      vysledok[i] = max;
      pole[indexMax] = Integer.MIN_VALUE;         
   }
   return vysledok;
}

Tvoje ma vzdy 0(nlogn). Oznacme pocet maximalnych prvokov k. Moje riesenie ma 0(nk) a v pripade k << n, co je asi velmi realne predpokladat, bude mat O(kn) = O(n). V jeho pripade sa je k = 3...

vyznam slova "jednoduchost" si predstavujem tak, ze riesenie bude vyzadovat menej zdrojoveho kodu

Kód:

public static int[] najdiMax(int[] pole, int k) 
   {       
      int[] vysledok = new int[k]; 
      Arrays.sort(pole);
      System.arraycopy(pole, pole.length-k, vysledok, 0, k);
      return vysledok; 
   }

a z pohladu rychlosti tam nieje takmer ziadny rozdiel

Kód:

public static void main(String[] args) {
      int[] vstup = {9,2,3,4,1,6,7,8,4};
   
      long start = System.currentTimeMillis();
      for (int i =0;i<10000000; i++) { 
        int[] vystup = najdiMax(vstup, 3);
      }
      System.out.println("done "+(System.currentTimeMillis()-start));
      start = System.currentTimeMillis();
      for (int i =0;i<10000000; i++) { 
        int[] vystup = najdiMax2(vstup, 3);
      }
      System.out.println("done "+(System.currentTimeMillis()-start));

   }
   
   public static int[] najdiMax(int[] pole, int k) 
   {       
      int[] vysledok = new int[k]; 
      for(int i = 0; i < vysledok.length; i++) { 
         int max = Integer.MIN_VALUE; 
         int indexMax = 0; 
         for (int m = 0; m < pole.length; m++) { 
            if (pole[m] > max) { 
               max = pole[m]; 
               indexMax = m; 
            } 
         } 
         vysledok[i] = max; 
         pole[indexMax] = Integer.MIN_VALUE;          
      } 
      return vysledok; 
   }
   
   public static int[] najdiMax2(int[] pole, int k) 
   {       
      int[] vysledok = new int[k]; 
      Arrays.sort(pole);
      System.arraycopy(pole, pole.length-k, vysledok, 0, k);
      return vysledok; 
   }

ado21 · Napísal **ado21**: 06.12.2010 20:26

skus dat vstup 10 milionov prvkov... A to ani zdaleka nie je tak velke cislo

coldak · Napísal **coldak**: 06.12.2010 21:29

no a ty skus tvojej funkcii povedat ze chces napr ztoho 10 millionoveho vstupu 800 max hodot

800 tiez ani zdaleka nie je tak velke cislo

ado21 · Napísal **ado21**: 06.12.2010 23:56

nejako automaticky sa uz sustredujem na velkost vstupu

coldak · Napísal **coldak**: 07.12.2010 1:40

ado21 píše:

nejako automaticky sa uz sustredujem na velkost vstupu

nevadi, dali sme tu dva sposoby. Oba maju svoje klady aj zapory. je na Reiki , aky sposob bude viac vyhovovat jeho potrebam. Dik za spolupracu

ado21 · Napísal **ado21**: 07.12.2010 2:06

Ono keby som tam robit vazne vyoptimalizovane, tak by som spravil haldu (linearny cas), pozrel maximum(konstatny cas), vyhodil ho (logaritmicky) teda v konecnom dosledku by to bolo O(n + k*logn) :-)

Ale v tychto veciach nie som extra dobry. Ale ak tak rozmyslam, ani cez klasicke vyuzitie intervaloveho stromu by to neslo podstadstne lepsie. Ale s nimi da naozaj carovat. Este sa da celkom dobre kuzlit s bitami... Ani nahodou som si nie isty, ze to nejde lepsie. V tychto veciach poznam vela o dost lepsich ludi, ba az guro-ov

Ale O(n + k*logn) naozaj nie je problem.

Reiki · Napísal autor témy **Reiki**: 07.01.2011 13:24

Ďakujem za rady.