Optymalizacja algorytmu

Question

Czesc wszystkim,

Mam problem z zadaniem z algorytmow. Zadanie sklada sie z dwoch czesci:

1. Majac liste liczb calkowitych gdzie kazda liczba moze pojawic sie wiele razy nalezy zidentyfikowac liczbe wystepujaca najrzadziej. Jesli kilka roznych liczb wystepuje z taka sama frekwencja, program powinien zwrocic liczbe o najwyzszym indeksie. Przykladowo z listy [1,2,2,1] algorytm musi zwrocic 1. Lista jest nieuporzadkowana.

Ta czesc nie stanowi problemu. Moj algorytm napisany w Python wyglada tak:

def leastCommon(someList):
    element = someList[0]
    counter = someList.count(element)
    # counter inicjuje zmienna stanowiaca poczatkowy punkt odniesienia 
    for i in someList:
        # petla liczy czestotliwosc wystepowania
        # kazdego elementu na liscie i zapisuje
        # w zmiennej least liczbe o najnizszej frekwencji
        if someList.count(i) <= counter:
            counter = someList.count(i)
            least = i
    return least

   Problemem jest natomiast druga czesc zadania:

2. Majac uporzadkowana w kolejnosci rosnacej liste liczb calkowitych, zoptymalizuj wczesniejszy algorytm. Optymalizacja musi uwzgledniac strukture nowej listy (uporzadkowana w kolejnosci rosnacej).

W zadaniu nie wolno uzyc slownikow ani zadnych bibliotek Pythona.

Pierwszy algorytm ma zlozonosc O(n²). Zeby ulepszyc drugi algorytm, musialby miec zlozonosc O(n), O(log n) albo O(n log n). Niestety doznalem jakiejs blokady umyslowej i nie jestem w stanie zrobic drugiej czesci zadania. Walkuje to od tygodnia i potrzebuje swiezego spojrzenia. Nie chodzi mi o gotowe rozwiazanie, a raczej pokierowanie we wlasciwym kierunku. Bede bardzo wdzieczny za wszelka pomoc.

M.

Answer 1

Po prostu przeleć tę pętlę i dodawaj += 1 przy każdej iteracji. W momencie zmiany liczby (są uporządkowane), zapisz wynik i zresetuj licznik. Przy następnej zmianie liczby sprawdź, czy ten "counter" osiągnął mniejszą wartość niż poprzedni. Jeśli tak, to go zapisz i kontynuuj.

 

EDIT:

Próbowałem to napisać sobie i jest mały problem z edge-case'ami, ale szedłbym w tę stronę. Edge-case to taki, że najmniejszą częstość posiada liczba ostatnia i jest tylko jedna. Obszedłem go w taki sposób, że dodałem na końcu tablicy nulla, żeby zrobić jeszcze jedną iterację. https://paste.ofcode.org/bxAndi7e2XW8rmDGDKWyVb. Ba, wykonanie tej jeszcze jednej iteracji jest niezbędne :P

Comments

Dzieki za pomoc. Za bardzo skupilem sie na probie optymalizacji do O(n log n) i oddalilem sie od bardziej oczywistych rozwiazan. Twoj kod przelozony na Pythona dziala doskonale.

Dzieki i pozdrawiam!

---

Proszę, pozdrawiam.

Nota bene nie wiem, jaką złożonością cieszy się mój algorytm, ale chyba to będzie n+1. Nie mam pojęcia, jak się takie coś liczy. Ale zakładam, że skoro wywołaliśmy pętlę n + 1 razy, to można to pobić tylko wywołując ją n-razy, lub posiadając więcej informacji na temat zbioru danych.

---

Zgadza sie, Twoj algorytm ma zlozonosc O(n) (jedynka jest zbedna). Moj algorytm majacy jako input nieuporzadkowana liste jest O(n²) ze wzgledu na uzycie count() w petli. count() samo w sobie jest O(n) i wykonujac sie z kazda iteracja petli podnosi zlozonosc do kwadratu. Ja sam dopiero sie ucze dlatego za wszelka cene probowalem zastosowac divide and conquer do optymalizacji na posortowanej liscie, ale nie wiem nawet czy to w tym przypadku mozliwe.

---

Według mnie - "na logikę" - niemożliwe jest zejście poniżej O(n) przy takim zbiorze danych i takich informacjach jakie posiadamy. Siłą rzeczy musimy sprawdzić każdy element przecież.

---

No wlasnie nie jestem pewien. Na liscie nieuporzadkowanej rzeczywiscie trzeba sprawdzic kazdy jeden element. Na liscie posortowanej wystarczy sprawdzic pierwszy element z danego rodzaju, zeby wiedziec ile ich jest, nie pojawia sie juz wiecej na liscie np. na koncu. Przy malych listach tego nie widac, ale zalozmy, ze na liscie jest 100 zer, 150 jedynek i jedna 9 na koncu. count() przeleci przez cala liste liczac zera, ale wiedzac po pierwszym wywolaniu, ze zer jest 100 mozna by je usunac z listy, oszczedzajac 99 kolejnych wywolan count. Mowiac krotko, zredukowac liczbe elementow na liscie po kazdym wywolaniu count(). Na tym sie wlasnie zacialem, bo zaczalem brnac w jeszcze bardziej zlozone rozwiazania zamiast prostsze.

---

Ah, chciałeś zredukować swoje rozwiązanie. No to oczywiście. Myślałem, że chcesz jeszcze bardziej zredukować moje.

Gdybym miał to robić na liście nieuporządkowanej, to bym zebrał do osobnej tablicy informacje o tym, ile jest wystąpień każdej liczby (tablica asocjacyjna), a następnie przeleciał tylko tę tablicę, żeby znaleźć minimum. Nie wiem ile by to było (jedna pętla na zebranie danych i jedna na ich analizę).

---

Najwiekszym problemem tego zadania sa jego ograniczenia. Najlatwiej byloby uzyc Counter() z biblioteki Pythona. Druga opcja to slowniki, ktore tez sa zabronione. Tak jak w Twoim przykladzie z tablicami, wystarczylaby jedna iteracja przypisujaca frekwencje do liczby na zasadzie key:value, a nastepnie wyciagniecie najmniejszej value uzywajac np. min(). Jak dostane formalne rozwiazanie tego zadania, to na pewno sie nim tutaj podziele.