/KolPopr

TI:WTBD/Kolokwium Poprawkowe

zadanie 1

Medianę sekwencji liczb można zdefiniować za pomocą następującego kodu:

    def median(x):
        xx = sorted(x)
        if not xx:
            return None
        if len(xx) == 1:
            return xx[0]
        if len(xx) == 2:
            return sum(xx)/2.
        else:
            return median(xx[1:-1])

(kod ten służy wprowadzeniu definicji mediany, nie jest to optymalna ani nawet szczególnie dobra implementacja obliczania mediany w praktyce!)

Niech T będzie tabelą, zawierającą (między innymi) kolumnę "X float not null". Napisać zapytanie SQL zwracające medianę wartości z kolumny X. Napisać program do testowania tego zapytania, tworzący tabelę z 10 000 liczb losowych (w pamięci) i porównujący medianę obliczoną za pomocą zapytania SQL z wynikiem rachunku w Pythonie na tych samych liczbach (ulepszając algorytm z powyższej definicji).

przykład rozwiązania:

#! /usr/bin/python
# coding: utf-8

def py_median(x):
    xx = sorted(x)
    if not xx:
        return None
    limit, offset = 2 - len(xx) % 2, (len(xx) - 1) / 2
    middle = xx[offset:offset+limit]
    return sum(middle) / float(limit)

def sql_median(x):
    from sqlite3 import connect
    conn = connect(':memory:')
    conn.execute('create table T (X float not null)')
    conn.executemany('insert into T values (?)', zip(x)) #((X,) for X in x))
    ((res,), ) = conn.execute('''
    select avg(X)
    from (
        select X
        from T
        order by X
        limit 2 - (select count(*) from T)%2
        offset ((select count(*) from T) - 1)/2
        )'''
    )
    conn.close()
    return res

def test_median(N=10000):
    from numpy.random import rand
    x = rand(N)
    m1 = py_median(x)
    m2 = sql_median(x)
    delta = m1 - m2
    return delta

if __name__ == '__main__':
    from sys import argv
    N = 10000
    if len(argv) == 2:
        N = int(argv[1])
    print 'py_median - sql_median = {}'.format(test_median(N))

zadanie 2

Posługując się gotową bazą SQLite zawartą w pliku pl_lud.db napisać program, który:

• w odpowiedzi na argument 'q1' wypisuje listę nazw województw, po jednym na linijkę, i w tej samej linijce dla każdego z nich podaje liczbę powiatów, należących do danego województwa;
• w odpowiedzi na argument 'q2' wypisuje listę nazw 10 powiatów o największym zaludnieniu w kraju, obok jego nazwy wypisując liczbę ludności i nazwę województwa, do którego należy;
• w odpowiedzi na argument 'q3' wypisuje średnią i odchylenie standardowe liczby ludności obliczone dla wszystkich powiatów w kraju.

przykład rozwiązania:

#! /usr/bin/python
# coding: utf-8

QUERIES = {
'q1' : '''
select w.NAZWA as WOJEWODZTWO, count(*) as ILE_POWIATOW
from WOJEWODZTWA w
    join POWIATY p on w.ID=p.W_ID
group by w.NAZWA
order by w.NAZWA
''',
'q2' : '''
select p.NAZWA as POWIAT, p.LUDNOSC, w.NAZWA as WOJEWODZTWO
from POWIATY p
    join WOJEWODZTWA w on w.ID=p.W_ID
order by p.LUDNOSC desc
limit 10
''',
'q3' : '''
select sum(LUDNOSC)/count(*), sum(LUDNOSC*LUDNOSC)/count(*)
from POWIATY;
'''
}

def main(baza, arg):
    from sqlite3 import connect
    conn = connect(baza)
    cursor = conn.execute(QUERIES[arg])
    if arg in ('q1', 'q2'):
        rows = list()
        rows.append(tuple(r[0] for r in cursor.description))
        for r in cursor:
            rows.append(tuple(unicode(x) for x in r))
        for r in rows:
            print u' | '.join(r).encode('utf-8')
            #print r
    elif arg == 'q3':
        avg, avg2 = cursor.fetchall()[0]
        stddev = (avg2 - avg**2)**0.5
        print u'średnia: {}; sigma: {}'.format(avg, round(stddev)).encode('utf-8')

if __name__ == '__main__':
    from sys import argv
    baza = 'pl_lud.db'
    try:
        arg = argv[1]
    except IndexError:
        print u'{}: wymaga dokładnie jednego argumentu.'.format(__file__).encode('utf-8')
        exit(1)
    if arg in ('q1', 'q2', 'q3'):
        main(baza, arg)
    else:
        print u'{0}: {1}: nieznany argument.'.format(__file__, arg).encode('utf-8')

zadanie 3

Napisać program, który na podstawie pliku tekstowego kodowanego w UTF-8 stworzy indeks słów występujących w tym pliku, w postaci tabeli SQLite zawierającej kolumny slowo (tekst słowa), wiersz (nr wiersza w którym wystąpiło) i kolumna (pozycja w wierszu). Sprawdzić działanie tego programu na podstawie pliku z tekstem 1. księgi Pana Tadeusza (Plik:PanTadeusz1.txt).

 W sformułowaniu tego zadania kryje się niestety pewna niejednoznaczność, której
 z początku nie zauważyłem: ,,pozycja w wierszu" może oznaczać numer kolejny słowa
 w wierszu, lub pozycję w wierszu początku tego słowa jako numer kolejny znaku w wierszu -- 
 ta druga interpretacja była zamierzona, ale oceniając traktowałem obie jako poprawne. 
 Również jako równie poprawne traktowałem zaczynanie numeracji od zera lub od jedynki.

przykład rozwiązania:

#! /usr/bin/python
# coding: utf-8

import re
import sqlite3

def words(plik):
    wordrx = re.compile(r'\b\w+\b', re.UNICODE)
    f = open(plik)
    for num, line in enumerate(f):
        line = line.decode('utf-8')
        ## to jeśli kolumnę rozumieć jako nr słowa w linii
        #for pos, word in enumerate(wordrx.findall(line)):
            #yield word, num, pos
        ## a teraz wersja gdy kolumna oznacza pozycję początku słowa w znakach
        m = wordrx.search(line)
        while m:
            yield m.group(0), num, m.start()
            m = wordrx.search(line, m.end())
    f.close()

def create(dbplik, plik):
    db = sqlite3.connect(dbplik)
    db.execute('''
        drop table if exists indeks_slow
        ''')
    db.execute('''
        create table indeks_slow (slowo text, wiersz int, kolumna int, primary key (wiersz, kolumna))
        ''')
    db.executemany('''
        insert into indeks_slow (slowo, wiersz, kolumna) values (?, ?, ?)
        ''', words(plik))
    db.commit()
    ((n,),) = db.execute('''
        select count(*) from indeks_slow
        ''')
    return n

if __name__ == '__main__':
    from sys import argv
    try:
        plik = argv[1]
    except IndexError:
        print (u'{}: wymaga argumentu - nazwy pliku tekstowego w UTF-8.'.
                    format(__file__).encode('utf-8')
              )
        exit(1)
    dbplik = plik + '.sqlite3'
    print u'tworzę tabelę indeks_slow w pliku {} ...'.format(dbplik).encode('utf-8')
    nrows = create(dbplik, plik)
    print u'wstawiono {} wierszy.'.format(nrows).encode('utf-8')