Archive

Archive for November, 2010

QImage vs QImageReader

November 22nd, 2010 No comments

QImage is not good choice  for scaling images (like QImage::load() + QImage::scaled()).

QImageReader API is better approach than loading full image into memory and stretching it there. QImageReader API allows to set needed scaling limitations first and then load it. The image will be scaled as part of loading process and there is no needs to allocate memory for full size image.

pattern: QImageReader::setScaledSize() + QImageReader::read()

Tags:

Cuckoo hashing

November 12th, 2010 No comments

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table. Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in 2001. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches.

Theory

The basic idea is to use two hash functions instead of only one. This provides two possible locations in the hash table for each key.
When a new key is inserted, a greedy algorithm is used: The new key is inserted in one of its two possible locations, “kicking out”, that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there, until a vacant position is found, or the procedure enters an infinite loop. In the latter case, the hash table is rebuilt in-place using new hash functions.

Tags:

MurmurHash

November 5th, 2010 No comments

MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. It was created by Austin Appleby in 2008, and exists in a number of variants, all of which have been released into the public domain.

Variants

The current version is MurmurHash2, which yields a 32-bit hash value and is optimized for Intel processors. Slower versions of MurmurHash2 are available for big-endian and aligned-only machines. The MurmurHash2A variant adds the Merkle-Damgard construction so that it can be called incrementally. There are two variants which generate 64-bit values; MurmurHash64A, which is optimized for 64-bit processors, and MurmurHash64B, for 32-bit ones. MurmurHash1 is obsolete.

Implementations

The canonical implementations are in C++, but there are efficient ports for a variety of popular languages, including Python, C#, Perl, Ruby, Haskell, Java, and JavaScript.

It has been adopted into a number of open-source projects, most notably libmemcached (the C driver for Memcached), maatkit, and Hadoop.

Tags:

Алгоритм Рабина — Карпа

November 5th, 2010 No comments

Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом.

Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не слишком широко используется. Однако, алгоритм имеет уникальную особенность находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.

Tags:

Фильтр Блума

November 5th, 2010 No comments

Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году[1], позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.

Bloom Filter

Дополнительно:

  • The Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.
  • C++ Bloom Filter Library
  • «Алёна C++: Фильтр Блума»
Tags:

Seth Godin on standing out

November 4th, 2010 No comments

About this talk

In a world of too many options and too little time, our obvious choice is to just ignore the ordinary stuff. Marketing guru Seth Godin spells out why, when it comes to getting our attention, bad or bizarre ideas are more successful than boring ones.

About Seth Godin

Seth Godin is an entrepreneur and blogger who thinks about the marketing of ideas in the digital age. His newest interest: the tribes we lead.

Tags: ,