{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Esempi di compiti frequenti\n", "========================\n", "\n", "Alcuni esempi di brevi programmi per affrontare problemi che si incontrano sovente nella pratica.\n", "Possono servire di ispirazione per ulteriori esplorazioni di algoritmi in Python.\n", "\n", "Molti modi per calcolare una somma\n", "-----------------------------\n", "\n", "Come esempio, calcoliamo la somma dei numeri pari in modi diversi. Notate la definizione di funzioni seguite dal test dopo:
`if __name__ == \"__main__\":`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "compute_sum1 result is 12, expected to be 12\n" ] } ], "source": [ "def compute_sum1(n):\n", " \"\"\"computes and returns the sum of 2,4,6, ..., m\n", " where m is the largest even number smaller than n.\n", "\n", " For example, with n = 7, we compute 0 + 2 + 4 + 6 = 12.\n", " With n = 6, we compute 0 + 2 + 4 = 6.\n", " Start from 0 to account for n ≤ 2.\n", " \n", " This implementation uses a variable 'mysum' that is\n", " increased in every iteration of the for-loop.\"\"\"\n", "\n", " mysum = 0\n", " for i in range(0, n, 2):\n", " mysum = mysum + i\n", " return mysum\n", "\n", "\n", "def compute_sum2(n):\n", " \"\"\"computes and returns ...\n", "\n", " This implementation uses a while-loop:\n", " \"\"\"\n", "\n", " counter = 0\n", " mysum = 0\n", " while counter < n:\n", " mysum = mysum + counter\n", " counter = counter + 2\n", "\n", " return mysum\n", "\n", "\n", "def compute_sum3(n, startfrom=0):\n", " \"\"\"computes and returns ...\n", " \n", " Slightly more general:\n", " Calling compute_sum3(7,4) we compute 4 + 6 = 10 \n", " This is a recursive implementation:\"\"\"\n", "\n", " if n <= startfrom:\n", " return 0\n", " else:\n", " return startfrom + compute_sum3(n, startfrom + 2)\n", "\n", "\n", "def compute_sum4a(n):\n", " \"\"\"A functional approach ... this seems to be\n", " the shortest and most concise code.\n", " \"\"\"\n", " return sum(range(0, n, 2))\n", "\n", "from functools import reduce\n", "def compute_sum4b(n):\n", " \"\"\"A functional approach ... not making use of 'sum' which\n", " happens to exist and is of course convenient here.\n", " \"\"\"\n", " return reduce(lambda a, b: a + b, range(0, n, 2))\n", "\n", "\n", "def compute_sum4c(n):\n", " \"\"\"A functional approach ... a bit faster than compute_sum4b\n", " as we avoid using lambda.\n", " \"\"\"\n", " import operator\n", " return reduce(operator.__add__, range(0, n, 2))\n", "\n", "\n", "def compute_sum4d(n):\n", " \"\"\"Using list comprehension.\"\"\"\n", " return sum([k for k in range(0, n, 2)])\n", "\n", "\n", "def compute_sum4e(n):\n", " \"\"\"Using another variation of list comprehension.\"\"\"\n", " return sum([k for k in range(0, n) if k % 2 == 0])\n", "\n", "\n", "def compute_sum5(n):\n", " \"\"\"Using numerical python (numpy). This is very fast\n", " (but would only pay off if n >> 10).\"\"\"\n", " import numpy\n", " return numpy.sum(2 * numpy.arange(0, (n + 1) // 2))\n", "\n", "\n", "def test_consistency():\n", " \"\"\"Check that all compute_sum?? functions in this file produce\n", " the same answer for all n>=2 and =2. Raise AssertionError if outputs disagree.\"\"\"\n", " funcs = [compute_sum1, compute_sum2, compute_sum3,\n", " compute_sum4a, compute_sum4b, compute_sum4c,\n", " compute_sum4d, compute_sum4e, compute_sum5]\n", " ans1 = compute_sum1(n)\n", " for f in funcs[1:]:\n", " assert ans1 == f(n), \"%s(n)=%d not the same as %s(n)=%d \" \\\n", " % (funcs[0], funcs[0](n), f, f(n))\n", "\n", " #main testing loop in test_consistency function\n", " for n in range(2, 1000):\n", " check_one_n(n)\n", "\n", "if __name__ == \"__main__\": \n", " m = 7\n", " correct_result = 12\n", " thisresult = compute_sum1(m)\n", " print(f\"compute_sum1 result is {thisresult}, expected to be {correct_result}\")\n", " # compare with correct result\n", " assert thisresult == correct_result\n", " # also check all other methods\n", " assert compute_sum2(m) == correct_result\n", " assert compute_sum3(m) == correct_result\n", " assert compute_sum4a(m) == correct_result\n", " assert compute_sum4b(m) == correct_result\n", " assert compute_sum4c(m) == correct_result\n", " assert compute_sum4d(m) == correct_result\n", " assert compute_sum4e(m) == correct_result\n", " assert compute_sum5(m) == correct_result\n", "\n", " # a more systematic check for many values\n", " test_consistency()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "18" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "compute_sum3(10, 4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Tutte le implementazioni viste sopra danno lo stesso risultato. Alcune lezioni da apprendere:\n", "\n", "- Ci sono molte soluzioni (probabilmente infinite) ad un problema dato: questo significa che programmare richiede creatività.\n", "\n", "- Le diverse soluzioni possono ottenere lo stesso \"risultato\", in questo caso il calcolo di un numero.\n", "\n", "- Soluzioni diverse possono avere caratteristiche differenti. Possono:\n", "\n", " - essere più veloci o più lente\n", "\n", " - usare più o meno memoria\n", "\n", " - essere più facili o più difficili da capire quando si legge il codice\n", "\n", " - essere considerate più o meno \"eleganti\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ordinamento\n", "-------\n", "\n", "Supponiamo di aver bisogno di ordinare una liste di ntuple a due elementi di user-id e nomi, per esempio:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "mylist = [(\"fangohr\", \"Hans Fangohr\",),\n", " (\"admin\", \"The Administrator\"),\n", " (\"guest\", \"The Guest\")]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "che vogliamo ordinare in ordine crescente di user-id. Se ci sono due o più user-id identici (Pratica da evitare come la peste), vogliamo che questi vengano ordinati a seconda del nome associato allo user-id. Questo è semplicemente il comportamento di default del metodo `sort`, che si basa su come due oggetti vengono paragonati." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('admin', 'The Administrator'), ('fangohr', 'Hans Fangohr'), ('guest', 'The Guest')]\n" ] } ], "source": [ "stuff = mylist # collect your data\n", "stuff.sort() # sort the data in place\n", "print(stuff) # inspect the sorted data" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le sequenze sono paragonate comparando inizialmente solo i primi elementi. Se sono diversi, allora la decisione viene presa sulla base di questi soli elementi. Per esempio, in un vocabolario, \"az\" viene prima di \"ba\". Se i primi elementi sono uguali, solo allora vengono paragonati i secondi elementi ... e così via fino a quando viene trovata una differenza oppure finiscono gli elementi. Per esempio:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2,0) > (1,0)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2,1) > (1,3)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2,1) > (2,1)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2,2) > (2,1)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "'a' < 'b'" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(False, True)" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "('a' < 'A','A' < 'a')" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(False, True)" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "('a' < '1','1' < 'a')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si può anche ordinare con la funzione `sorted`:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "stuff = sorted(stuff)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quando la lista non è paticolarmente lunga, in genere è preferibile usare la funzione `sorted`, che restituisce *copia ordinata* della lista, invece del metodo `sort` dell'oggetto lista, che trasforma la lista nella lista ordinata e restituisce None, sovrascrivendo la lista di partenza." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 5, 1]\n", "[1, 2, 5]\n" ] } ], "source": [ "s0 = [2,5,1]\n", "s1 = sorted(s0)\n", "print(s0)\n", "print(s1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Supponiamo invece che i dati siano stati immagazzinati in modo tale che in ciascuna ntupla il nome viene prima dell'id, cioè:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "mylist2 = [(\"Hans Fangohr\", \"fangohr\"),\n", " (\"The Administrator\", \"admin\"),\n", " (\"The Guest\", \"guest\")]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'ordinamento deve utilizzare l'id come discriminante primario. La prima possibilità è quella di scambiare l'ordine degli elementi nelle ntuple e poi usare `sort` come prima.\n", "\n", "La seconda, più elegante, richiede di decifrare l'help, piuttosto oscuro, della funzione `sorted`. `list.sort()` ha le stesse opzioni ma il suo help è meno utile." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Help on built-in function sorted in module builtins:\n", "\n", "sorted(...)\n", " sorted(iterable, key=None, reverse=False) --> new sorted list\n", "\n" ] } ], "source": [ "help(sorted)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si noti che `sorted` and `list.sort` hanno due keyword parameters. Il primo si chiama key. Lo si può utilizzare per passare una *key function*, con cui trasformare gli elementi che `sort` deve comparare." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vediamo come sfruttarla nel nostro esempio. I nostri dati hanno la struttura:\n", "\n", " pair = name, id\n", " \n", "e li vogliamo ordinare secondo l'id e ignorando il nome. Lo possiamo ottenere definendo una funzione che restituisca solo il secondo elemento della coppia che gli viene passata:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def my_key(pair):\n", " return pair[1]" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "mylist2.sort(key=my_key)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si può anche usare una funzione anonima:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "mylist2.sort(key=lambda p: p[1]) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Efficienza\n", "\n", "La funzione`key` viene chiamata una volta sola per ogni elemento nella lista. Tuttavia, se la lista da ordinare è molto lunga l'overhead di chiamare una funzione di Python function (che è relativamente grande rispetto alle chiamate in altri linguaggi come il C) potrebbe farsi notare.\n", "\n", "Se l'efficienza è veramente importante e vi siete resi conto che una parte significativa del tempo di esecuzione viene spese in queste funzioni (Si chiama profiling)allora è possibile che sia necessario riscrivere le funzioni in C oppure un altro linguaggio più low-level. Python può essere interfacciato con questi linguaggi ma i dettagli li vedrete in altri corsi." ] } ], "metadata": { "hide_input": false, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }