Lists vs Tuples

Among the many things that Python does right, there are also a few that could have been better thought out. No language is perfect, of course, but since Python is increasingly adopted as the language of choice for complete beginners in programming, the net effect will be many new coders being heavily influenced by ideas they encounter here.

And unfortunately, some of those ideas are dead wrong. A chief example is the relation between lists and tuples, specifically the mistaken notion of their mutual similarity. In reality – that is, in every other language – they are completely different concepts, and rightfully so.

What is list?…

The term ‘list’ in programming is sometimes meant to refer to ‘linked list’ – one of the simple data structures you’d typically encounter in the introductory course to algorithms. It consists of a sequence of separately allocated elements, stitched together using pointers. Depending on the density and direction of those pointers, the type is further subdivided into singly and doubly linked lists, cyclic lists, and so on.

But the broader meaning, which is also more common now, describes a general collection of elements that can be linearly traversed, regardless of the details of its underlying representation. The List interface in Java or .NET is intended to capture the idea, and it does so pretty accurately. Concrete implementations (like ArrayList or LinkedList) can still be decided between if those details turn out to be important, but most of the code can deal with lists in quite abstract, storage-agnostic manner.

…in Python

In Python, lists generally conform to the above description. Here, you cannot really decide how they are stored under the hood (array module notwithstanding), but the interface is what you would expect:

You can insert, append and remove elements, as well as iterate over the list and access elements by indexes. There is also a handy bracket notation for list literals in the code:

About the only weird thing is the fact that you can freely put objects of different types into the same list:

In a way, though, this appears to be in sync with the general free-form nature of Python. For analogy, think about List<Object> in Java that can do exactly the same (or, in fact, any List prior to introduction of generics).

On the other hand, this is a tuple:

Besides brackets giving way to parentheses, there is no difference in literal notation. Similarly, you can iterate over the tuple just as well as you can over the list:

in addition to accessing elements by index. What you cannot do, though, is modifying a tuple once it is created: be it by trying to add more elements, or changing existing ones:

But just like with lists, there is no limitation for the types of elements you put therein:

All in all, a tuple in Python behaves just like an immutable (unchangeable) list and can be treated as such for all intents and purposes.

Tuplication

Now, let’s look at tuples in some other programming languages. Those that support them one way or another include C++, D, Haskell, Rust, Scala, and possibly few more exotic ones. There is also a nascent support for tuple-like constructs in Go, but it’s limited to returning multiple results from functions.

In any of these, tuple means several objects grouped together for a particular purpose. Unlike a list, it’s not a collection. That’s because:

• objects retain their individual identity
• their number is not arbitrary; in fact, tuples of different count have separate names: pairs, triples, etc.
• objects have positions assigned: when handling a tuple, it is expected that certain thing X will be at position N

Statically typed languages expand especially on the last point, making it possible to specify what type we expect to see at every position. Together, they constitute the tuple type:

In other words, you don’t operate on “tuples” in general. You use instances of specific tuple types – like a pair of int and string – to bind several distinct values together.
Then, as your code evolves, you may need to have more of them, or to manipulate them in more sophisticated ways. To accommodate, you may either expand the tuple type, or increase readability at the (slight) cost of verbosity and transform it into a structure:

Once here, you can stay with functions operating on those structures, or refactor those into methods, or use some combination of those two approaches.

Missing link

But in Python, that link between tuples and structures is almost completely lost. There is one built-in tuple type, which is simply tuple, but even that isn’t really paid attention to. What happens instead is that tuples are lumped together with lists and other collections into the umbrella term of “iterable”, i.e. something which can iterated over (typically via for loop).

As a result, a tuple can be converted to list and list can be converted to tuple. Both operations make no sense whatsoever. But they are possible, and that leads to tuples and lists being used interchangeably, making it harder to identify crucial pieces of data that drive your logic. And so they will grow uncontrollably, rather than having been harnessed at appropriate time into an object, or a namedtuple at the very least.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

— Linus Torvalds

Simulating nonlocal Keyword in Python 2.x

The overall direction where Python 3 is going might be a bit worrying, but it’s undeniable that the 3.0 line has some really nice features and quality-of-life improvements. What’s not to love about Unicode string literals enabled by default? Or the print function? What about range, map and filter all being generators? Neato!

There are also few lesser known points. One is the new nonlocal keyword. It shares the syntax with the global keyword, which would make it instantaneously fishy just by this connotation. However, nonlocal looks genuinely useful: it allows to modify variables captured inside function’s closure:

It’s something you would do quite a lot in certain other languages (*cough* JavaScript), so it’s good that Python has got around to support the notion as well. Syntax here is a bit clunky, true, but that’s simply a trade off, stemming directly from the lack of variable declarations in Python.

What about Python 2.x, though – are we out of luck? Well, not completely. There are a few ways to emulate nonlocal through other pythonic capabilities, sometimes even to better effect than the nonlocal keyword would yield.

Use generator instead

Speaking of yielding… As you have probably noticed right away, the example above is quite overblown and just plain silly. You don’t need to play functional just to count some values – you would use a loop instead:

Really, the previous version is just a mindless application of the classic Visitor pattern, which is another reason why you shouldn’t do that: pattern overuse is bad. This saying, Visitor obviously has its place: it’s irreplaceable when traversing more complicated structures in more bureaucratic languages. A simple list of numbers in Python is the direct opposite of both of these characteristics.

Complex data structures exist in any language, however. How would we run some Python code for every node in a tree, or maybe graph? Unrolling the DFS or BFS or whatever traversal algorithm we use certainly doesn’t sound like an elegant and reusable approach.
But even then, there is still no need for functions and closures. We can easily get away with the simple for loop, if we just find a suitable iterable to loop over:

The bst_nodes function above is not black magic by any stretch. It’s just a simple example of generator function, taking advantage of the powerful yield statement:

This works because both bst_count_parity and bst_nodes functions are executed “simultaneously”. That has the same practical effect as calling the visitor function to process a node, only the “function” is concealed as the body of for loop.

Language geeks (and Lisp fans) would say that we’ve exchanged a closure for continuation. There is probably a monad here somewhere, too.

Create reference where there is none

Generators can of course solve a lot of problems that we may want to address with nonlocal, but it’s true you cannot write them all off just by clever use of yield statement. For the those rare occasions – when you really, positively, truly need a mutable closure – there are still some options on the board.

The crucial observation is that while the closure in Python 2.x is indeed immutable – you cannot add new variables to it – the objects inside need not be. If you are normally able to change their state, you can do so through captured variables as well. After all, you are still just “reading” those variables; they do not change, even if the objects they point to do.

Hence the solution (or workaround, more accurately) is simple. You need to wrap your value inside a mutable object, and access it – both outside and inside the inner function – through that object only. There are few choices of suitable objects to use here, with lists and dictionaries being the simplest, built-in options:

If you become fond of this technique, you may want to be more explicit and roll out your own wrapper. It might be something like a Var class with get and set methods, or just a value attribute.

Classy solution

Finally, there is a variant of the above approach that involves a class rather than function. It is strangely similar to “functor” objects from the old C++, back when it didn’t support proper lambdas and closures. Here it is:

Its main advantage (besides making it a bit clearer what’s going on) is the potential for extracting the class outside of the function – and thus reusing it. In the above example, you would just need to add the __init__(self, key) method to make the class independent from the enclosing function.

Ironically, though, that would also defeat the whole point: you don’t need a mutable closure if you don’t need a closure at all. Problem solved? ;-)

Kwitnące zbiory

Przedstawię dzisiaj interesującą strukturę danych, będącą pewnego rodzaju uogólnieniem lub modyfikacją kontenerów typu bitset. Nazywa się ona filtrem Blooma (Bloom filter) i stanowi przykład struktury probabilistycznej, czyli działającej… czasami ;) Nie niweluje to aczkolwiek w żaden sposób jej przydatności, o czym zresztą opowiem dalej.

Filtr Blooma to tablica bitowa, w której przechowujemy pewien zbiór. Liczba owych bitów – i to jest pierwsza różnica w stosunku do bitsetu – nie jest równa liczbie wszystkich możliwych elementów zbioru. Wręcz przeciwnie, zwykle jest ona znacznie, znacznie mniejsza.
Drugą różnicą jest reprezentacja elementu, która dla odmiany zajmuje więcej miejsca. Definiuje je określona z góry liczba bitów, rozrzuconych po całej tablicy i ustawionych na 1. Sposób owego rozmieszczenia jest określony przez zestaw funkcji haszujących, przyjmujących element zbioru jako swój argument i zwracających indeks jednej z pozycji w tablicy. Owych funkcji jest zaś tyle, ile bitów reprezentacji.

Poglądowe przedstawienie filtru Blooma

Jak wyglądają operacje na tak zaimplementowanych zbiorze? Sprawdzenie przynależności jest proste, bo sprowadza się do obliczenia wartości wszystkich funkcji haszujących dla danego elementu i upewnieniu się, że na zwróconych przez nie pozycjach tablicy jest zapisana jedynka. Dodawanie, jak można się domyślić, polega na ustawieniu tychże jedynek. A co wobec tego z usuwaniem elementu?
Otóż usuwania… nie ma :) Jest to zamierzony efekt, konsekwencja założeń które czynią filtr Blooma strukturą probabilistyczną. Dopuszcza ona mianowicie fałszywe pozytywy. Są to przypadki, w których filtr odpowiada pozytywnie na pytanie o przynależność elementu, gdy w rzeczywistości element ten do zbioru nie należy. Jest to jednak jedyny rodzaj dopuszczalnych błędów. Wykluczone są w szczególności sytuacje odwrotne: gdy element jest w zbiorze, ale filtr odpowiada coś przeciwnego (byłby to z kolei fałszywy negatyw). Usuwanie – polegające na wyzerowaniu odpowiednich bitów – mogłoby jednak do dopuścić do takiej sytuacji. Wynika to z faktu, że każdy z bitów w tablicy odpowiada za przechowywanie więcej niż jednego elementu.

Przypuszczam, że wobec powyższych cech filtrów Blooma pojawiają się dwa pytania, z których jedno dotyczy częstotliwości pojawiania się fałszywych pozytywów. Zależy to oczywiście od rozmiaru tablicy (m), liczby funkcji haszujących (k), a także liczby elementów będących aktualnie w zbiorze (n). Ogólny wzór jest, jak widać, raczej nieoczywisty ;)
Dlatego pozwolę sobie raczej przejść do drugiego pytania: o zastosowania. Te są całkiem rozliczne – dotyczą chociażby przyspieszania dostępu do dużych kolekcji danych. Jeśli koszt wczytania danych odpowiadających danemu kluczowi jest spory (bo wymaga np. odczytu z dysku lub sieci), wówczas utrzymywanie w pamięci filtru Blooma może znacząco polepszyć efektywność poprzez szybkie odrzucanie zapytań o nieistniejące klucze. Oczywiście filtr będzie czasami się mylił, ale jego użycie i tak pozwoli ograniczyć liczbę drogich odwołań co najmniej o rząd wielkości.

Przykładową implementację filtru Blooma – wykorzystującą do haszowania generator liczb pseudolosowych – można zobaczyć choćby tutaj.

Podstawy autouzupełniania

Część bywalców kanału #warsztat może wiedzieć, że od jakiegoś czasu w wolnych chwilach rozwijam pewien niewielki projekt. Jest to prosty IRC-owy bot, który potrafi wykonywać różne predefiniowane czynności, dostępne za pomocą komend rozpoczynających się od kropki. Wśród nich mamy między innymi wysyłanie zapytań do wyszukiwarki Google, wyświetlanie skrótów artykułów z Wikipedii, przekazywanie wiadomości między użytkownikami i jeszcze kilka innych. W sumie jest ich już około kilkanaście, więc pomyślałem, że dobrym rozwiązaniem byłby wbudowany system pomocy oraz podpowiedzi opartych na “domyślaniu się”, jakie polecenie użytkownik chciał wydać.
Brzmi to może nieco zagadkowo, ale w gruncie rzeczy chodzi o zwykłe autouzupełnianie (autocompletion), do którego jesteśmy przyzwyczajeni w wielu innych miejscach – takich jak środowiska programistyczne czy choćby wyszukiwarki internetowe. Oczywiście tutaj mówimy o nawet miliardy razy mniejszej skali całego rozwiązania, ale ogólna zasada we wszystkich przypadkach jest – jak sądzę – bardzo podobna.

Cały mechanizm opiera się właściwie o jedną strukturę danych zwaną drzewem prefiksowym (prefix tree). Jest to całkiem pomysłowa konstrukcja, w której każde dopuszczalne słowo (zwane tradycyjnie w takich drzewach kluczem) wyznacza pewną ścieżkę od korzenia drzewa. Kolejne krawędzie etykietowane są tu znakami słowa.
Najważniejszą cechą drzewa prefiksowego jest jednak to, że wspomniane ścieżki mogą się nakładać, jeśli początkowe części danych słów się pokrywają. Stąd zresztą bierze się nazwa struktury, gdyż pozwala ona szybko znaleźć ciągi zaczynające się od podanego tekstu – czyli właśnie prefiksu.

DOD organizuje dane

Moi koledzy-częściowo-po-fachu, czyli programiści silników gier, wymyślili niedawno magiczny trzyliterowy akronim DOD – skrót od Data-Oriented Design, czyli projektowanie oparte o dane. Oczywiście określenie ‘niedawno’ jest względnym i pewnie wielu z nich orzekło by, że DOD jest z nimi już całkiem długo. Każdy mem potrzebuje jednak czasu na rozprzestrzenienie się, a w przypadku tego fala tweetów na jego temat dotarła do mnie dopiero niedawno. Niedługo potem rzecz wydała mi się cokolwiek podejrzana.

Podstawowe pytanie brzmi rzecz jasna: o co w tym właściwie chodzi?… Ponieważ mówimy o programowaniu gier, to odpowiedź jest jasna: jeśli nie wiadomo o co chodzi, to chodzi o wydajność. W zaawansowanych grach czasu rzeczywistego mamy do czynienia z ogromną ilością danych, na których trzeba wykonać wiele, często skomplikowanych operacji, a wszystko to jeszcze musi być zrobione dostatecznie szybko, aby możliwe było pokazanie na ekranie kolejnej klatki bez widocznych przycięć. Dlatego też już dawno zauważono, że kodowanie “blisko sprzętu” się opłaca, bo pozwala maksymalnie wykorzystać jego możliwości.
To oczywiście nakłada na kod pewne wymagania oraz stwarza konieczność zwrócenia uwagi na rzeczy, którymi “normalnie” nie ma potrzeby się zajmować. Ładnym przykładem jest chociażby zarządzanie pamięcią. W wielu językach jest ono albo kompletnie pomijalne (garbage collector), albo sprowadza się do dbania o to, aby każdy zaalokowany blok był w końcu zwolniony. Gdy jednak stawiamy na wydajność, powinniśmy też zainteresować się szybkością samej operacji alokacji oraz takim rozmieszczeniem przydzielanych bloków, aby komunikacja na linii procesor-pamięć odbywała się z jak najmniejszą liczbą zgrzytów.
Ten i wiele podobnych szczegółów platformy sprzętowej powodują, że pisanie efektywnego kodu w silnikach gier to często dość literalne postępowanie według zasady Do It Yourself, połączone z ignorowaniem części feature‘ów wysokopoziomowych języków programowania, o których wiadomo, że negatywnie odbijają się na wydajności. Cóż, życie; nie ma w tym nic zaskakującego. Myślę, że każdy co bardziej zaawansowany programista zdążył zdać sobie sprawę z tego, że wszelkie koderskie udogodnienia związane z podniesieniem poziomu abstrakcji mają swój koszt liczony w dodatkowych cyklach procesora (i nie tylko). Rezygnacja z nich jest więc dobrym posunięciem, jeśli chcemy te “stracone” cykle odzyskać.
Robiąc to, będziemy mieli ciastko, ale już nie będziemy mogli go zjeść – a to oczywiście nie jest przyjemne. I po części zapewne stąd wzięło się pojęcie DOD, które nie odnosi się do niczego w gruncie rzeczy nowego, ale pozwala łatwiej odnosić się do tego rodzaju koderskich praktyk poprzez nadanie im nazwy. A przy okazji – jak mi się wydaje – w jakiś nie do końca wytłumaczalny sposób redukuje dysonans poznawczy programistów silników gier, którzy świadomie muszą pozbawiać się możliwości przestrzegania “jedynie słusznych” zasad pisania kodu.

Jak dotąd wszystko jest w gruncie rzeczy bardzo ładne i sensowne, i bez problemu zgadzam się z postulatami Data-Oriented Design tam, gdzie się one aplikują. Zgadzam się nawet z tą domniemaną ukrytą motywacją, zwłaszcza że sam nieraz narzekałem na owe “jedynie słuszne” rady. Za to nijak nie mogę pojąć, dlaczego następnym krokiem – po wynalezieniu pojęcia DOD – był mniej lub bardziej frontalny atak na programowanie obiektowe, określane nieco bardziej znanym (ale naturalnie również trzyliterowym) akronimem OOP.
Nie, nie chodzi o to, że programowanie obiektowe jest doskonałe – bo nie jest, nie było, nigdy nie będzie i nawet nie aspiruje do miana finalnego rozwiązania dla dowolnego problemu (już nie wspominając o tym, że takowe po prostu nie istnieją). Rzecz w tym, że zwolennicy DOD (DOD-a? :]) w nieprzemyślany sposób wybrali sobie przeciwnika, nie zauważając, że jest on paradygmatem zupełnie innego rodzaju niż ich własny. A to przecież takie proste:

• OOP sugeruje, że naturalną architekturą dla systemów jest ta oparta o obiekty, będące mniej lub bardziej abstrakcyjnymi bytami, połączonymi relacjami i wchodzącymi ze sobą w interakcje
• DOD wskazuje na to, że głównym zadaniem kodu jest transformacja danych w inne dane i że optymalizacja procesu przetwarzania danych jest priorytetem przy tworzeniu wewnętrznej struktury programu

Widać to, prawda?… Miedzy powyższymi dwoma podejściami nie tylko nie ma sprzeczności. One są od siebie po prostu niezależne, co oznacza również, że mogą występować razem w jednym programie.

“Mapa nie jest terytorium.”

Jeśli Data-Oriented Design koniecznie potrzebuje jakiegoś przeciwnika, to są nim raczej inne xOD-y, których jest już przynajmniej kilka, chociaż wiele nie zostało jeszcze nawet nazwanych. (Dobry przykład to projektowanie oparte o user experience, czyli wrażenie użytkownika, gdzie priorytetem jest m.in. responsywność, nie będąca wcale synonimem wydajności). To, co piewcy DOD zdają się krytykować w swoich publikacjach, to jakieś “projektowanie oparte o eleganckie abstrakcje”, czyli pisanie kodu, który jest sztuką dla sztuki: ładnie wygląda (w założeniu), ściśle trzyma się założeń używanego paradygmatu przy jednoczesnym eksploatowaniu wszelkich jego “zdobyczy” (czyli np. wzorców projektowych). I chociaż bywają w swoich wysiłkach niezwykle twórczy (w prezentacjach z tego tematu spotkałem nawet cytaty z Baudrillarda), to nie zmienia to faktu, że kopią leżącego (czy raczej biją martwego konia, jakby to powiedzieli Amerykanie ;-)). Bo jeśli ktoś naprawdę posuwa się do takich absurdów jak czteropoziomowa hierarchia dziedziczenia obiektów gry, to znaczy że ma znacznie poważniejsze problemy niż okazjonalny cache miss :)

Struktury danych nieobecne w .NET

Programując z użyciem platformy .NET można niekiedy mieć wrażenie, że jest w niej niemal wszystko. Oczywiście takie przekonanie jest nietrwałe: wystarczy bowiem znaleźć coś, co być w niej mogłoby (a zwłaszcza coś, co występuje w innych, podobnych bibliotekach), a czego jednak nie ma. Nietrudno zauważyć, że takich rzeczy jest mimo wszystko większość – bo w sumie nie może być przecież inaczej :)
Niektóre braki są aczkolwiek bardziej dotkliwe niż inne. Należą do nich chociażby luki w systemie kolekcji obiektów, czyli – mówiąc ogólniej – wszelkiego rodzaju struktur danych. W .NET brakuje bowiem takich rzeczy jak:

Niedużo tego…

• Zbiory. Wprawdzie niemal każdy pojemnik zawiera metodę Contains o wiadomym przeznaczeniu, jednak tylko kontenery słownikowe sprawdzają unikalność umieszczanych w nich obiektów. Te zaś zasadniczo służą do czegoś innego: mapowania jednych obiektów na inne. Brakuje więc zwykłej, prostej klasy Set z operacjami dodawania, usuwania i wyszukiwania elementów – odpowiednika std::set z STL.
• Kolejki priorytetowe (priority queues). Tutaj znowu można je symulować przy pomocy klas typu SortedDictionary, które jednak nie są zasadniczo do tego przeznaczone. Kolejka priorytetowa powinna mieć przecież niemal identyczny interfejs do zwykłej kolejki FIFO (czyli głównie metody Push i Pop), bo różnica polega wyłącznie na porządku zwracanych elementów, określonym przez ich porównania.
• Kolekcje zbiorów rozłącznych (disjoint sets). Te dość specyficzne struktury danych są przydatne wtedy, gdy musimy szybko zorganizować kolekcję obiektów w osobne podgrupy wedle jakichś kryteriów. Można to oczywiście zrobić za pomocą dowolnych pojemników, tyle że będzie to nieefektywne. Dedykowana implementacja z użyciem wydajnych algorytmów (tzw. łączenia według rangi i kompresji ścieżek) byłaby znacznie bardziej na miejscu.
• Grafy. Wprawdzie grafy nie są aż tak często wykorzystywane, ale nie da się ukryć, że czasami ich użycie jest konieczne. Na pewno nie zaszkodziłoby posiadanie ich jako wbudowanego feature‘a w każdej bibliotece struktur danych. Zwłaszcza z gotowym zestawem podstawowych algorytmów grafowych.

Tę listę można by oczywiście ciągnąć bardzo długo, ale zdecydowałem się ograniczyć do tych czterech rzeczy z dwóch powodów. Po pierwsze, przynajmniej raz zdarzyło się, że potrzebowałem którejś z wymienionych tutaj struktur w .NET i byłem zmuszony poradzić sobie we własnym zakresie. Po drugie, bez problemu można podać przykłady innych bibliotek, języków czy środowisk, gdzie jedna z nich, większość lub nawet wszystkie są obecne. Najlepszym przykładem jest C++ (z STL) uzupełniony o bibliotekę Boost, który pod względem struktur danych prezentuje się w tej postaci naprawdę potężnie.
Nie widzę więc specjalnych usprawiedliwień dla faktu, że w .NET lista standardowych struktur prezentuje się nadzwyczaj skromnie. Może więc zamiast dodawać w nowych wersjach platformy kolejne wątpliwej jakości “usprawnienia” – jak wyrażenia lambda wbudowane w C# czy zabawki typu LINQ – programiści Microsoftu zajęliby się raczej zaniedbanymi dotąd podstawami?…