Keskustelu: Ohjelmointikysymykset: Python-ohjelma on liian hidas

Minulla on Pythonilla tehty ohjelma, joka hakee kokonaislukusarjoja
30*200 kokoisesta tekstimuotoisesta kokonaislukutaulukosta.
Tulosta tulee suht nopeasti, mutta jos kasvatan taulukon rivien määrää esim.
30*300, niin ohjelma näyttää toimivan, mutta ei anna tulosta, vaikka odottaisi tunnin.

Jos taas vähennän haettavan kokonaislukusarjan pituutta vaikka yhdellä, niin voin
kasvattaa hiukan taulukon rivien määrää ja saan tuloksen.

Mielestäni tämä viittaisi jotenkin ohjelman käyttämään muistin määrään.
Olenko oikeilla jäljillä ja mitä ongelmalle olisi tehtävissä, jotta voisin "ajaa" myös rivimäärältään suurempia taulukoita.
Kone, jolla ohjelmaa ajan, on 3 vuotta vanha 27" iMac 8 GT:n keskusmuistilla. Python on 3.3.1-versio.

Itse veikkaisin, että ohjelmasi aikavaatimus on liian suuri. Jos vaikka näyttäisit ohjelmakoodisi, niin sitä olisi helpompi analysoida ja korjata.

Koodi on alunperin samaa kuin löytyy Antti Laaksosen tekemänä Yleinen keskustelu-osiosta Miten tämä tehtäisiin -kysymyksellä nimimerkillä Alfkeke.
Koodia jos saisi muokattattuna myös siten, että se tulostaisi numerot suuruuusjärjestyksessä.

Kiitos paljon jo etukäteen.

Itselle uutena Python-käyttäjänä tuo aikavaatimus ei paljoa kerro. Voisiko joku ystävällisesti myös valaista sitä puolta ja kertoa, miten tuota aikavaatimusta muutetaan.

Tässä hieman muutettu versio, joka näyttää etenemisen prosentteina. Tosiaan, tuossa myös tuo muistinkäyttö voi tulla vastaan: itselläni muistia kului jopa 2GT. Toisaalta kyllä tuosta sinunkin koneesta pitäsi tarpeeksi muistia löytyä, ellei sitten käyttis tunge juuri tuon prosessin muistia kovalevylle.

data = open("data.txt").readlines()

sarakkeita = 30

tilasto = {}
suurin = 0
rivin = 1

for rivi in data:
    osat = rivi.strip().split(" ")
    if len(osat) != sarakkeita:
        continue
    osat.sort()
    for a in range(sarakkeita):
        for b in range(a+1,sarakkeita):
            for c in range(b+1,sarakkeita):
                for d in range(c+1,sarakkeita):
                    for e in range(d+1,sarakkeita):
                        sarja = (osat[a],osat[b],osat[c],osat[d],osat[e])
                        if sarja not in tilasto:
                            tilasto[sarja] = 0
                        tilasto[sarja] += 1
                        suurin = max(suurin,tilasto[sarja])
    print (str(100.0 * rivin / len(data)) + "%")
    rivin += 1

for sarja in tilasto:
    if tilasto[sarja] == suurin:
        print (sarja, tilasto[sarja])

ElinaSam kirjoitti:

Itselle uutena Python-käyttäjänä tuo aikavaatimus ei paljoa kerro. Voisiko joku ystävällisesti myös valaista sitä puolta ja kertoa, miten tuota aikavaatimusta muutetaan.

Aikavaatimus ei liity mitenkään erityisesti Pythoniin, vaan kaikkiin algoritmeihin. Se kuvastaa, miten paljon aikaa algoritmi maksimissaan käyttää. Esimerkiksi tuolle yllä olevalle ohjelmalle suhteellisen tarkka aikavaatimus olisi O(n*m^k), missä n on riven määrä, m sarakkeiden määrä ja k haettavan sarjan pituus.

Lue lisää putkan oppaista (täältä ja täältä)

Ohjelman aikavaatimukseen voi vaikuttaa keksimällä paremman algoritmin, mutta tähän tehtävään (jos se on aiemmassa keskustelussa oikein esitetty) ei ole parempaa algoritmia, koska kaikki sarjat on pakko tutkia. Mieti kuitenkin vielä, onko tilanne oikeasti tuo vai voiko kysymystä muuttaa jotenkin.

Ohjelman nopeuteen voi vaikuttaa tekemällä ohjelman tehokkaammalla ohjelmointikielellä, mutta se on yleensä myös hankalampaa. Jos omat taidot eivät riitä eikä ole tarkoituskaan opetella ohjelmointia, mielestäni tällaisessa tilanteessa olisi parasta palkata joku taitavampi tekemään sopiva ohjelma.

Voisko tuohon edelliseen saada vielä sellaisen ohjelmamuutoksen, että tulostaisi numerosarjat suuruusjärjestyksessä.
Sort-komennollako se onnistuu?
Kiitos

Muuta lopun for-silmukkaa näin:

for sarja in sorted(tilasto):

Jostain syystä ei järjestä oikein, varsinkin jos tuloksena on useampia rivejä.

Kyllä se järjestää rivit aivan oikein – yhdellä logiikalla. Jos haluat jonkin muun logiikan, kannattaisi varmaan selittää, millä tavalla haluat niiden järjestyvän (ja minkä; en ole ihan varma edes, haluatko rivit järjestykseen vai yhden rivin luvut järjestykseen).

Sorry, jos olen esittänyt toiveeni epäselvästi.
Haluaisin tuloksena kunkin vaakarivin numerot suuruusjärjestyksessä pienemmästä suurempaan vasemmalta oikealle.
Lisäksi jos saisi vielä siten, että pienimmät numerosarjat ovat ylhäällä ja suureenee alaspäin mentäessä.
Nyt kokeellisesti tulostettuna antoi esim. seuraavanlaisesti prosenttilukujen jälkeen:
('1','39','5','51','70')6
('15','38','4','7','70')6
Kiitos kärsivällisyydestä.

Ahaa.

Luvut olisivat jo järjestyksessä, jos alkuperäisessä koodissa käsiteltäisiin niitä lukuina. Tekijä on kuitenkin jättänyt ne tekstimuotoon, jolloin ne ovat ikään kuin aakkosjärjestyksessä. (Tämä oli alunperin aivan käypä ratkaisu, koska alkuperäisessä esimerkkidatassa luvut 0–9 ilmoitettiin etunollan kera, esimerkiksi '01'.)

Vaihda siis koodin keskivaiheilta rivi osat.sort() tällaiseksi:

osat = sorted(int(i) for i in osat)

Rivien järjestäminen toimii aiemman neuvoni mukaan.

Nyt on kukin vaakarivi numeroarvoiltaan suuruusjärjestyksessä.
Pystysuunnassa rivien alkunumeroiden mukaan järjestys on epämääräinen.
Mikäli "uskaltaa" vielä ehdottaa siihenkin suuruusjärjestyksen mukaisen järjestyksen eli pienimmällä numerolla alkavat rivit "yläpäähän" eli tulostuksen alkupäähän.
Lämmin kiitos!
Hienoa osaavaa porukkaa.

Sanoinhan, että rivien järjestäminen toimii aiemman neuvoni mukaan. Oletko noudattanut neuvoa eli lisännyt for-silmukkaan sorted-kutsun?

Olen noudattanut neuvojasi ja lisännyt molemmat antamasi korjaukset eli ohjelman keskivaiheille: osat=sorted(int(i) for i in osat) ja loppupuolelle: for sarja in sorted(tilasto):
Ohjelma toimii muuten kaikinpuolin ok, mutta rivit keskenään eivät tulostu pystysuunnassa suuruusjärjestyksessä rivin ensimmäisen eli pienimmän mukaan lajiteltuna.
Kiitos.

Herää epäilys, että olet laittanut rivin jotenkin väärin. Selvennän nyt vielä varmuuden vuoksi, että antamani for-rivin on tarkoitus tulla tulostussilmukan entisen for-rivin tilalle eli toisin sanoen alkuperäiseen for-riviin vain lisätään sorted().

for sarja in sorted(tilasto):
    if tilasto[sarja] == suurin:
        print (sarja, tilasto[sarja])

Jos tämä ei todellakaan toimi, laita varmuuden vuoksi tähän näytille koko koodi sekä esimerkki parista rivistä, jotka ovat väärässä järjestyksessä.

Olet täysin oikeassa, olin jättänyt yhdestä tekemästäni versiosta rivin:
for sarja in sorted(tilasto): muotoon for sarja in tilasto ja tallentanut sen vain osittain korjattuna.
Pahoittelen suuresti tapahtunutta.
Nyt on kaikki kunnossa ja teikäläinen on ollut kaiken aikaa oikeassa.
Paljon kiitoksia ja oikein hyvää jatkoa!