Podniesienie wydajności programu

Witam,

Jakieś rady żeby program działał szybciej? Kod oblicza wyrazu "ciągu", i później ma wyciągnąć n-ty wyraz tego "ciągu". Dla dużych liczb jest mało wydajny.

import java.util.Set;
import java.util.TreeSet;

class DoubleLinear {
    
    public static int dblLinear (int n) {
   
     Set list = new TreeSet();
     list.add(1);

     for (int i = 0 ; n > i; i++) {
        list.add((int) list.toArray()[i] * 2 + 1);
        list.add((int) list.toArray()[i] * 3 + 1);
     }
    
     return (int)list.toArray()[n];

    }
}

*to nie ciąg, nie wiem jak to nazwać.

Znaleźć równanie na N-ty wyraz ciągu i je zastosować zamiast liczyć cały ciąg? Dodatkowo czemu do diabła używasz TreeSet zamiast ListArray czy jaki tam sekwencyjną kolekcję masz w Javie?

Bo to nie za bardzo ciąg geometryczny ani arytmetyczny:

y = 2 * x + 1 and z = 3 * x + 1
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Korzystałem z ArrayList ale dla tego ciągu musiałem go sortować na końcu pętli, co w tym przypadku załatwia za mnie Hash.

Poza tym jeżeli tutaj dodaje tylko elementy i je wyciągam to nie ma takiego dramatu:

http://bigocheatsheet.com/#data-structures

Jesteś pewien, że chodzi o ciąg?
Cytat, który koliduje z definicją ciągu, przypomnijmy, "ciąg to funkcja określona na podzbiorze zbioru liczb naturalnych":
"1 gives 3 and 4"
Jak to rozumieć? a_1 = 3 i a_1 = 4?

Ok, użyłem zbyt pochopnie matematycznego określenia problemu, którego nie potrafiłem inaczej nazwać.

Czy jezeli liczba w ciągu się powtarza .. to ma być zignorowana ? TreeSet tak robi - jak wrzucisz dwa razy 31 to powstanie jedna pozycja? zamierzone ?
Czyli dla n=8 masz skończyć z tym:
1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 46
czy z tym
1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 31, 39, 40, 46

edit: I dla jakich n - potrzebujesz to liczyć?

Gdybyś mial drugi przypadek to kilkukrotnie przyspieszenie dostaniesz na rympał przepisując tak:

 public static int dblLinear(int n) {

        int[] list = new int[n*2+1] ;
        list[0] = 1;

        for (int i = 0 ; n > i; i++) {
            Arrays.sort(list,i, i*2+1);
            list[i*2+1]  = list[i]*2+1;
            Arrays.sort(list,i, i*2+2);
            list[i*2+2]  = list[i]*3+1;

        }
        Arrays.sort(list,n, n*2+1);
        return list[n];
    }

I to nadal jest słabe dla dużych liczb.

Duplikaty mają być usuwane. Między innymi dlatego wyrzuciłem ArrayList, bo tam na końcu pętli musiałem się przelecieć bo wszystkich elementach i sprawdzić czy nie występuje. Generalnie nie przechodzi testów na codewars ze względu na czas, więc trudno mi określić rząd wielkości liczb jakie tam są sprawdzane.

Może warunek wykonania pętli jest zbyt długi?

No ale jak duplikaty mają być usuwane - to nie to rozwiązanie - trochę się sprawa komplikuje..

Binary search z arrays przed dorzuceniem (jak jest nie wrzucasz) elementu - dodatkowy index k - ile elemntów już masz wrzuconych i będzie.
Pytanie czy to wystarczająco szybko....
Hinweis - przyspieszenie 1 to użycie prymitywnych int, a drugie to sortowanie tylko istotnych kawałków (czyli od i w górę).
moment.... właśnie mi coś przysżlo do głowy....

update:
no to czaj to:

  public static int dblLinear4 (int n) {

        HashSet<Integer> known = new HashSet<>();
        PriorityQueue<Integer> list = new PriorityQueue<>();
        list.offer(1);
        known.add(1);

        for (int i = 0 ; n > i; i++) {

            Integer element1 = list.poll();
            Integer new1= element1 *2 +1;
            if (! known.contains(new1)) {
                list.offer(new1);
                known.add(new1);
            }
            Integer element2 = list.poll();
            Integer element = Math.min(element1,element2);

            Integer new2= element *3 +1;
            if ( !known.contains(new2)) {
                list.offer(new2);
                known.add(new2);
            }
            list.offer(Math.max(element1,element2));
        }

        // System.out.println(list.toString());
        return (int)list.poll();

    }

na vmce (czyli troszke słabo wiarygodne czasy -ale pi razy oko good - mam tak)
wyniki dla n = 15000
263431
time = 4927ms //twoj
263431
time = 33ms //dla priority queue

a dla n=25000

495031
time = 12805ms
495031
time = 35ms

(dobry algoryzm wyszedł - ale nijak nie potrafię go udowodnić :-) )

winerfresh napisał(a):

Znaleźć równanie na N-ty wyraz ciągu i je zastosować zamiast liczyć cały ciąg? Dodatkowo czemu do diabła używasz TreeSet zamiast ListArray czy jaki tam sekwencyjną kolekcję masz w Javie?

ArrayList.