Posts tagged ‘experiments’

Dictionary with Missing Values

2012-06-29 22:36

When working with dictionaries in Python, or any equivalent data structure in some other language, it is quite important to remember the difference between a key which is not present and a key that maps to None (null) value. We often tend to blur the distinction by using dict.get:

  1. thingie = some_dict.get('key')
  2. if thingie:
  3.     do_stuff_with(thingie)

We do that because more often that not, None and other falsy values (such as empty strings) are not interesting on their own, so we may as well lump them together with the “no value at all” case.

There are some situations, however, where these variants shall be treated separately. One of them is building a dictionary of keyword arguments that are subsequently ‘unpacked’ through the **kwargs construct. Consider, for example, this code:

  1. import re
  2. from bs4 import BeautifulSoup
  3.  
  4. def find_images_by_text(html, text, in_alt=True, in_title=False):
  5.     """Search for <img> tags 'matching' given text in HTML document."""
  6.     regex = re.compile(".*%s.*" % re.escape(text), re.IGNORE_CASE)
  7.     attrs = {}
  8.     if in_alt:
  9.         attrs['alt'] = regex
  10.     if in_title:
  11.         attrs['title'] = regex
  12.     return BeautifulSoup(html).find_all('img', **attrs)

With a key mapping to None, we’re calling the function with argument explicitly set to None. Without the key present, we’re not passing the argument at all, allowing it to assume its default value.

But adding or not adding a key to dictionary is somewhat more cumbersome than mapping it to some value or None. The latter can be done with conditional expression (x if cond else None), together with many other keys and value at once. The former requires an if statement, as shown above.
Would it be convenient if we had a special “missing” value that could be used like None, but caused the key to not be added to dictionary at all? If we had it, we could (for example) rewrite parts of the previous function that currently contain if branches:

  1. attrs = {'alt': regex if in_alt else missing,
  2.          'title': regex if in_title else missing}

It shouldn’t be surprising that we could totally introduce such a value and extend dict to support this functionality – after all, it’s Python we’re talking about :) Patching the dict class itself is of course impossible, but we can inherit it and come up with something like the following piece:

  1. class MissingDict(dict):
  2.     def __init__(self, **kwargs):
  3.         kwargs = dict((k, v) for (k, v) in kwargs.iteritems()
  4.                       if v is not missing)
  5.         dict.__init__(self, **kwargs)
  6.  
  7. missing = object()

The magical missing object is only a marker here, used to filter out keys that we want to ignore.

With this class at hand, some dictionary manipulations become a bit shorter:

  1. def find_images_by_text(html, text, in_alt=True, in_title=False):
  2.     regex = re.compile(".*%s.*" % re.escape(text), re.IGNORE_CASE)
  3.     return BeautifulSoup(html).find_all('img', **MissingDict(
  4.         alt=regex if in_alt else missing,
  5.         title=regex if in_title else missing))

We could take this idea further and add support for missing not only initialization, but also other dictionary operations – most notably the __setitem__ assignments. This gist shows how it could be done.

Tags: , ,
Author: Xion, posted under Computer Science & IT » Comments Off on Dictionary with Missing Values

Badania terenowe nad budowaniem stringów

2009-07-18 13:04

Cokolwiek kodujemy, konieczność zbudowania dużego łańcucha znaków składającego się z kolejno dołączanych fragmentów pojawia się bardzo często. To może być zapytanie do bazy danych, misternie wyrzeźbiony adres URL, dynamicznie generowany i kompilowany później shader czy w końcu obszerny i szczegółowy komunikat o błędzie.
Wspólną cechą tych tekstów jest to, że budujemy je stopniowo, kawałek po kawałku. Na takie okazje niektóre języki (jak .NET-owe lub Java) posiadają specjalne klasy w rodzaju StringBuilder. Mają one być efektywniejsze niż bezpośrednie używanie typów string, głównie ze względu na nietworzenie wielu łańcuchów i niezaśmiecanie nimi pamięci, co odciąża garbage collector z dodatkowej pracy.

W C++ nie ma oczywiście odśmiecacza, który musiałby po nas sprzątać, i nie ma też narzędzi typu StringBuilder. Czy to oznacza więc, że możemy radośnie korzystać z samej klasy std::string do budowania dowolnie długich tekstów, bo żadnej efektywniejszej alternatywy nie ma?… To właśnie zdecydowałem się sprawdzić, przeprowadzając mały eksperyment z tworzeniem długich łańcuchów znaków kilkoma sposobami, aby potomni nie musieli rozwiązywać tego jakże uciążliwego dylematu ;]
Przechodząc do rzeczy, wpierw wysmażyłem taką oto funkcję która generuje tekst o podanej minimalnej długości:

  1. const string GenerateString(string::size_type minLen)
  2. {
  3.     string res;
  4.     string::size_type currLen = 0;
  5.  
  6.     while (currLen < minLen)
  7.     {
  8.         string::size_type next = rand() % (MAX_FRAG_LEN + 1);
  9.         res += STRINGS&#91;next];
  10.         currLen += next;
  11.     }
  12.  
  13.     return res;
  14. }&#91;/cpp]
  15. Użyta w niej tablica <code>STRINGS</code> zawierała przygotowane wcześniej "kawałki" w postaci losowych napisów, z których składany był wynikowy tekst. Każdy element <code>STRINGS[n]</code> był tu tekstem o długości <code>n</code> znaków (z zakresu 0 do 111).
  16. Powyższej funkcji użyłem następnie do wygenerowania stringów o długościach 222.222, 555.555, 1.111.111, 5.555.555 i 11.111.111 znaków, mierząc czas każdej z tych operacji i uśredniając go z 10 powtórzeń. Skąd takie długości tych tekstów?... No cóż, tylko co najmniej takie wartości dawały sensowne i wystarczają długie czasy, które dawało się zmierzyć i porównać z innymi :)
  17.  
  18. No właśnie - a jakież to inne sposoby na konstruowanie napisów można było jeszcze wymyślić? Otóż wymyśliłem jeszcze dwa, polegające na wykorzystaniu wektora znaków (<code>vector&lt;char&gt;</code>). Operacja konkatenacji została w nich zaimplementowana jako rozszerzenie wektora (metoda <code>resize</code>), a następnie przekopiowanie zawartości stringa w powstałe miejsce - czyli mniej więcej tak:
  19. [cpp]// res to vector<char>
  20. res.resize (currLen + next);
  21. memcpy (&res[currLen], STRINGS[next].data(), next * sizeof(char));

Wyróżnienie dwóch sposobów polegało natomiast na tym, że w jednym z nich dodatkowo wywoływałem na samym początku metodę reserve w celu uprzedniej rezerwacji pamięci w wektorze na 3 * minLen / 2 elementów.

Testy przeprowadziłem na standardowej implementacji klas string i vector dostępnej w Visual C++ 2005. Wyniki eksperymentu przedstawiają się następująco:

Można w nich przede wszystkim zauważyć, że zarządzanie pamięcią w klasie string jest domyślnie znacząco lepsze niż w vector. Najszybszą metodą konstruowania napisów okazuje się jednak użycie wektora z uprzednią rezerwacją pamięci, która okazuje się o ok. 20% szybsza niż zwykła konkatenacja stringów.

Czy to oznacza, że powinniśmy stworzyć sobie własną klasę StringBuilder, opierającą się na wektorze właśnie, i jej używać? Niekoniecznie. Jak widać, znaczące różnice pojawiają się dopiero przy tworzeniu napisów o wielkościach rzędu megabajta lub więcej. Konia z rzędem temu, kto tworzy tak duże zapytania lub shadery :) Do większości typowych zastosowań bezpośrednie użycie typu string wydaje się więc wystarczające.
No chyba że istnieją bardziej efektywne sposoby na budowanie stringów w C++, których nie udało mi się wymyślić – co jest swoją drogą całkiem prawdopodobne :)

Tags: , , ,
Author: Xion, posted under Programming » 12 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.