Вход | Регистрация

Решение на първа задача

  • Понеже едва ли ще направим инфраструктурата за публикуване на наши решения скоро, реших да ви дам това на първа задача на форумите. Заслужава си да разберете решенията ни, понеже от този процес ще научите доста за езика:

    def fizzbuzz(n):
        def value(x):
            if   x % 15 == 0: return 'FizzBuzz'
            elif x % 3  == 0: return 'Fizz'
            elif x % 5  == 0: return 'Buzz'
            else: return x
        return list(map(value, range(1, n + 1)))
    
    def minmaxmean(ages):
        mean = sum(ages.values()) / len(ages)
        return tuple(min(ages, key = k) for k in [
            ages.__getitem__, lambda n: -ages[n], lambda n: abs(ages[n] - mean)])
    
    def anagrams(words):
        anagrams = {}
        for word in words:
            anagrams.setdefault(''.join(sorted(word)), []).append(word)
        return [value for value in anagrams.values() if len(value) >= 2]

    Първата функция може да се направи на един ред, но нарочно избрахме по-четимия вариант. Това е доста любопитен въпрос, за който може да прочетете повече тук , особено ако някога планирате да ходите на интервю за работа. Втората е умишлено написана по най-краткия възможен начин и прилага някои трикове, които ви показахме в лекцията за ООП. Третата пък е написана по най-праволинейния начин и е пример за каноничен код на Python.

    С цел малко забавление, ето и решение на вторите две чрез функциите от втора задача:

    def minmaxmean(ages):
        return tuple(construct([curry(func, key = key) for (func, key) in (
            (min, ages.__getitem__),
            (max, ages.__getitem__),
            (min, (lambda mean: lambda n: abs(ages[n] - mean))(sum(ages.values()) / len(ages))))],
        ages))
    
    def anagrams(words):
        return [group for group in groupby(compose(sorted, tuple), words).values() if len(group) >= 2]

    Обърнете внимание колко е кратка anagrams. minmaxmean пък е умишлено усложнена. Някой има ли идея защо дефинирам анонимна функция, която извиквам непосредствено?

    28.03.2009 (променeно 28.03.2009)
  • Thumbs_up

    (min, (lambda mean: lambda n: abs(ages[n] - mean))(sum(ages.values()) / len(ages))))]

    Да намерим средното аритметично е все едно да намерим минималното число, такова, че ако mean ни е средното аритметично, а числото ни е x ние искаме abs( mean - x ) да ни е минимално. Затова използваме min. (lambda mean: lambda n: abs(ages[n] - mean)) първата ламбда връща функция, която прави именно това. Само че за целият израз ни трябват 2 аргумента. Тази средна стойност и числото x. Тъй като min взима за аргументи нещо подържащо итератори и функция с един аргумент, то за функцията, която използваме трябва да определим единия от 2-та аргументи (mean или n) => извикваме първата функция с аргумент sum(ages.values()) / len(ages) и така уточняваме mean. Сега вече функцията min като влезе в първата ламбда, тя връща директно втората, където вече mean е изчислен.

    28.03.2009 (променeно 28.03.2009)
  • Аз да си пробутам и моето решение на minmaxmean() (не онова, което видяхте на лекцията):

    def minmaxmean(ages):
        min_name = min(ages, key = lambda name: ages[name])
        max_name = max(ages, key = lambda name: ages[name])
        mean_age = sum(ages.values()) / len(ages)
        mean_name = min(ages, key = lambda name: abs(ages[name] - mean_age))
        return (min_name, max_name, mean_name)
    28.03.2009
  • А какви решения ни препоръчвате да ви изпращаме - решения на един ред и/или четими решения?

    28.03.2009
  • Четими решения на един ред.

    28.03.2009
  • Здрасти, Имам въпрос по примерното решение на Николай: в реализацията на използваните функции min, max и sum, пълно обхождане ли се прави на дадения списък за да се намерят съотв. мин, макс елемент и сумата? Ако да- тогава в решението си Николай (нищо лично към него) обхожда веднъж ages за да намери мин елемент, втори път за да намери макс и трети- за да намери сумата. Със стандартните алгоритми мисля че това може да се направи само с едно обхождане, но с доста повече код Прав ли съм? Мерси предварително: Велизар.

    29.03.2009 (променeно 29.03.2009)
  • Да така е. Може да се направи с един цикъл в който се смятат и трите едновременно.

    29.03.2009
  • Тогава кое от двете решения е по-близо до определението "елегантно" ?

    29.03.2009
  • Според кого?

    Отговора на "кое е по-елегантно" винаги варира спрямо това кого питаш. Освен, разбира се, ако не е очевидно, но тогава не би питал.

    Коя е по-елегантна Anne или Jennifer?

    Това настрана, решението на Ники ми харесва повече, вероятно защото моето е същото...

    29.03.2009
  • Точно колко е Същото? Ха-ха-ха...

    29.03.2009 (променeно 29.03.2009)
  • Толкова:

    def minmaxmean(ages):
        mean_age = sum(ages.values()) / len(ages)
        mini = min(ages.items(), key=lambda x: x[1])[0]
        maxi = max(ages.items(), key=lambda x: x[1])[0]
        mean = min(ages.items(), key=lambda x: abs(x[1] - mean_age))[0]
        return (mini, maxi, mean)
    29.03.2009
  • Ясно. Ники е преписвал от Славомир. По -10 и на двамата.

    Иначе, в контекста на Python и основните тези на този курс, решението на Ники/Славомир е строго по-добро/елегантно от решението с един цикъл и три отделни проверки в него, понеже първото е семантично (казва какво искате да постигнете), докато второто е алгоритмично (казва как да постигнете нещо). Основното твърдение което правим, програмирайки на Python е Ще жертваме производителност на програмата за да получим производителност на програмиста или още Жертваме скорост за простота.

    Или както казва Donald Knuth, един от най-големите алгоритмици, Premature optimization is the root of all evil :)

    Иначе, аз предпочитам това на Ники, което освен по-кратко е малко по-бързо от това на Славомир, за голямо учудване и на двамата.

    30.03.2009 (променeно 30.03.2009)
  • Също така, от алгоритмична гледна точка, ако имаш 3 цикъла (1..n) с по 5 операции всеки == 15n операции == 1 цикъл (1..n) с 15 операции. Така, теоретически, не би трябвало да има разлика в бързодействито на решение с 3 цикъла и на това с 1. Практически, може и да има от викането на ламбдите, но човек не може да е сигурен без benchmark.

    А защо на Ники решението да е по-бързо и аз съм учуден...

    30.03.2009 (променeно 30.03.2009)
  • Асимптотично ако трябва да бъдем точни :)

    Но това игнорира константите...

    30.03.2009
  • Според твоето е по-бавно (18 единици), заради създаването на двойки. Това на Ники е 17 единици. Моето пък е 15. Пренаписах го и с един цикъл и тогава стана 12.

    От друга страна, стана много по-дълго и трудно за четене.

    Такива неща може да проверите с модула timeit.

    31.03.2009