Največ n-krat

Obvezna naloga

Na enem od izpitov ste morali napisati funkcijo najvec_n(s, n), ki prejme seznam s (da ne bo kakih zapletov, predpostavimo, da gre za seznam števil) in neko število n. Funkcija je morala vrniti nov seznam, ki je vseboval iste elemente, vendar vsakega največ n-krat; nadaljnje (tudi nezaporedne) ponovitve elementov so bile odstranjene.

Tako je moral klic najvec_n([1, 2, 3, 1, 1, 2, 1, 1, 2], 2) vrniti [1, 2, 3, 1, 2].

Rešitev naloge je lahko bila, recimo

def najvec_n(s, n):
    nov = []
    for e in s:
        if nov.count(e) < n:
            nov.append(e)
    return nov

Za domačo nalogo boste ponovno napisali to funkcijo, vendar tako, da bo v doglednem času (največ nekaj sekund) predelala tudi bistveno večje sezname. Gornja funkcija zmore prvi test (test_najvec_n_mali), drugega (test_najvec_n_veliki), pri katerem ima vhodni seznam 100000 elementov, izhodni pa 20000 pa ne premelje primerno hitro. (Kar poskusite!)

Najbrž bo potrebno uporabiti, kar smo se učili na zadnjih predavanjih.

Ko poženete program, ga lahko, če se naveličate čakanja, ustavite z rdečim kvadratkom, ki je v PyCharmu zgoraj desno in spodaj levo.

Rešitev

Bistvo naloge: uporabiti slovar in videti, kako hitrejši je od seznama.

Naredimo lahko tako:

def najvec_n(s, n):
    nov = []
    stevci = {}
    for e in s:
        if e not in stevci:
            stevci[e] = 0
        if stevci[e] < n:
            nov.append(e)
            stevci[e] += 1
    return nov

Ali pa uporabimo deafultdict.

import collections

def najvec_n(s, n):
    nov = []
    stevci = collections.defaultdict(int)
    for e in s:
        stevci[e] += 1
        if stevci[e] <= n:
            nov.append(e)
    return nov

Dodatna naloga

Napišite funkcijo najvec_n_na_mestu(s, n), ki je podobna prejšnji, vendar ne vrne nobenega rezultata (torej: vrne None) temveč pobriše elemente iz podanega seznama s. Test za to funkcijo je takšen:

    s = [1, 2, 3, 1, 1, 2, 1, 1, 2]
    self.assertIsNone(najvec_n_na_mestu(s, 3))
    self.assertEqual(s, [1, 2, 3, 1, 1, 2, 2])

Sestavimo seznam s; pokličemo najvec_n_na_mestu in predpostavimo, da bo vrnila None; preverimo, ali se je seznam s spremenil.

Rešitev

Najpreprosteje gre tako, da spraznimo podani seznam in vanj vstavimo, enega za drugim, vse elemente novega, prečiščenega, ki ga dobimo kar s prejšnjo funkcijo.

def najvec_n_na_mestu(s, n):
    s.clear()
    for e in najvec_n(s, n):
        s.append(e)

Vendar je to čisto kompliciranje. Uporabimo lahko kar rezine.

def najvec_n_na_mestu(s, n):
    s[:] = najvec_n(s, n)

Če hočemo v resnici predelovati podani seznam, bi lahko naivno napisali kaj takšnega.

# To ne deluje!
def najvec_n_na_mestu(s, n):
    stevci = collections.defaultdict(int)
    for i, e in enumerate(s):
        stevci[e] += 1
        if stevci[e] > n:
            del s[i]

To ne deluje, ker pride ob brisanju element, ki sledi pobrisanemu, na mesto pobrisanega in se nam na ta način izmakne. Pravilno se to naredi takole:

def najvec_n_na_mestu(s, n):
    stevci = collections.defaultdict(int)
    i = 0
    m = len(s)
    while i < m:
        e = s[i]
        stevci[e] += 1
        if stevci[e] > n:
            del s[i]
        else:
            i += 1

Ob vsakem element se odločimo, da ga bomo pobrisali (del s[i]) ali pa nadaljevali z naslednjim (i += 1). Oboje pa ne, saj bi v tem primeru spet preskočili, element, ki sledi pobrisanemu. Ali gre gora k Mohamedu ali pa Mohamed h gori, oboje pa ne.

Iz razlogov, ki bodo jasnejši v tretjem letniku, je ta rešitev počasna. Točneje: vsako brisanje mora premakniti vse elemente, ki sledijo pobrisanemu, in to zna trajati nekaj časa. Hitrejša rešitev (predvsem, če bi programirali v C-ju, v Pythonu pa se bo razlika poznala kvečjemu pri zeloooo velikih seznamih), je:

def najvec_n_na_mestu(s, n):
    preverjam = 0
    prosto = 0
    stevci = collections.defaultdict(int)
    while preverjam < len(s):
        e = s[preverjam]
        stevci[e] += 1
        if stevci[e] <= n:
            s[prosto] = e
            prosto += 1
        preverjam += 1
    del s[prosto:]

Kako deluje, smo videli na predavanjih, ko smo reč lepo počasi sprogramirali.