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.
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.
Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом.
Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не слишком широко используется. Однако, алгоритм имеет уникальную особенность находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.
Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году[1], позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
Дополнительно:
- 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++: Фильтр Блума»
Alexander Alexandrovich Stepanov (Russian: Александр Александрович Степанов) (born November 16, 1950 in Moscow) is the primary designer and implementer of the C++ Standard Template Library [1], which he started to develop around 1992 while employed at HP Labs. He had earlier been working for Bell Labs close to Andrew Koenig and tried to convince Bjarne Stroustrup to introduce something like Ada Generics in C++.
Лекция «Наибольшая общая мера последние 2500 лет» (часть 1 и часть 2)
Слайды: англ и рус.
Лекция «Преобразования и их орбиты» (часть 1 и часть 2)
Elements of Programming – (November 3, 2010) Speakers Alexander Stepanov and Paul McJones give a presentation on the book titled “Elements of Programming”. They explain why they wrote and attempt to explain their book. They describe programming as a mathematical discipline and that it is extremely useful and should not be overlooked.
Stepanov’s homepage
Here’s the Vigenere crypto algorithm as suggested by Allan:
function Vigenere(Src, Key : string; Encrypt : boolean) : string;
const
OrdMinChar : integer = Ord('A');
OrdMaxChar : integer = Ord('Z');
IncludeChars : set of char = ['A'..'Z'];
var
CharRangeCount, i, j, KeyLen, KeyInc, SrcOrd, CryptOrd : integer;
SrcA : string;
begin
CharRangeCount := OrdMaxChar - OrdMinChar + 1;
KeyLen := Length(Key);
SetLength(SrcA, Length(Src));
If Encrypt then
begin
// transfer only included characters to SrcA for encryption
j := 1;
for i := 1 to Length(Src) do
begin
if (Src[i] in IncludeChars) then
begin
SrcA[j] := Src[i];
inc(j);
end;
end;
SetLength(SrcA, j - 1);
end;
SetLength(Result, Length(SrcA));
if Encrypt then
begin
// Encrypt to Result
for i := 1 to Length(SrcA) do
begin
SrcOrd := Ord(Src[i]) - OrdMinChar;
KeyInc := Ord(Key[((i - 1 ) mod KeyLen)+ 1]) - OrdMinChar;
CryptOrd := ((SrcOrd + KeyInc) mod CharRangeCount) + OrdMinChar;
Result[i] := Char(CryptOrd);
end;
end;
else
begin
// Decrypt to Result
for i := 1 to Length(SrcA) do
begin
SrcOrd := Ord(Src[i]) - OrdMinChar;
KeyInc := Ord(Key[((i - 1 ) mod KeyLen)+ 1]) - OrdMinChar;
CryptOrd := ((SrcOrd - KeyInc + CharRangeCount)
mod CharRangeCount) + OrdMinChar;
// KeyInc may be larger than SrcOrd
Result[i] := Char(CryptOrd);
end;
end;
end;
In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e. an edit distance). The term edit distance is often used to refer specifically to Levenshtein distance.
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965. (wikipedia with code, russian version)
The following is a list of algorithms described in Wikipedia. This list is manually updated and additions of links to existing pages are welcome. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.
uint8_t num_of_bits32(uint32_t _arg)
{
_arg = (_arg & 0x55555555L) + ((_arg >> 1) & 0x55555555L);
_arg = (_arg & 0x33333333L) + ((_arg >> 2) & 0x33333333L);
_arg = (_arg + (_arg >> 4)) & 0x0F0F0F0FL;
_arg = _arg + (_arg >> 8);
return (uint8_t)(_arg + (_arg >> 16)) & 0x3F;
}
or
int count1(int t)
{
__asm
{
mov edx,t
mov eax, 0
cycle : bsf ecx, edx
jz finish
inc eax
inc ecx
shr edx, cl
jmp cycle
finish:
}
}
Автор: Александр Шарахов
Предлагаю вашему вниманию еще один подход к построению алгоритмов вычисления CRC32. Хотя многие использованные в нем идеи в той или иной мере содержатся в известных руководствах по оптимизации кода для IA32 и вычислению CRC32, он может представлять некоторый интерес. Использование свойств CRC-арифметики позволило разработать алгоритм вычисления CRC32, имеющий производительность в 3-5 раз выше стандартной табличной реализации. Например, на компьютере с процессором E6850/3.2GHz он расходует 1.33 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC32 составляет 0.75 байта за такт центрального процессора или 2.4*10^9 байтов в секунду.
далее
