Pairing functions are surprisingly useful increasing application performace.
As per Wiki, Pairing functions uniquely encode two natural numbers into a single natural number.
While designing system software this feature can be exploited to reduce runtime data structures data footprint.
Here is Dope-tale about one of that use.
While design of compiler diagnostics or run time err0r checkers, we record error location at line:column
pair from user code, typical implementation for this use-case is
typedef std::uint32_t Line
typedef std::uint32_t Column
typedef std::pair<Line,Column> Location;
typedef std::map<Line,Location> LocationTable;
// OR
typedef std::multi_map<Line,Location> LocationTable1;
This implemenation creates wrong semantics. map implemenation does not cover multiple errors on same location.
While both of them fail in semantics as Line does not uniquely identify error and its location.
So we define problem as
0 <= Line <= 232-1
0 <= Column <= 232-1
Given < Line,Column > --uniquely--> Error, We would be needing O(1) search
with single key, like...
typedef std::unordered_map \< LocationHash,ErrorDescriptor \> LocationTable;
So we wish to pair two integeres into one. hence pairing functions.
A pairing function is a computable bijection
π : N × N → N .
- Line and Column are natural number
- Practically 32 bits are enough to accommodate Line and Number
- Key made by both can be accommodated in 64 bits
here is sample implemenation
typedef std::uint32_t UI32;
typedef std::uint64_t UI64;
typedef std::uint64_t Key64;
typedef std::uint32_t LocationKey;
using LocationHash = Key64;
typedef std::pair<LocationHash,ErrorDescriptor> LocationListItemPair;
struct PairHashFunction : std::binary_function<UI32,UI32,Key64>
{
Key64 operator()(UI32 first,UI32 second) const{
Key64 first64 = (Key64) first;
Key64 second64 = (Key64) second;
Key64 sum64 = (first64 + second64);
Key64 hashValue64 = sum64 * (sum64 + 1) >> 1;
return hashValue64 + second64;
}
};
template<typename HashKeyType,typename KeyType>
struct UnPairHashFunctionTemplate
{
void operator() (HashKeyType hashValue,KeyType *first, KeyType * second){
HashKeyType temp = (hashValue << 3) + 1;
temp = std::sqrt(temp) - 1;
temp = std::floor(temp>>1);
HashKeyType consum = (temp * temp + temp) >> 1;
*second = hashValue - consum;
*first = temp - *second;
}
};
typedef UnPairHashFunctionTemplate<Key64,UI32> UnPairHashFunction;
class HitTable{
LocationTable table;
public:
void hit(Location locKey){
PairHashFunction hfunc;
Key64 key = hfunc(locKey.first,locKey.second);
auto it = table.find(key);
if(it == table.end()){
table[key] = 1;
}
else{
KeyCountType count = table[key];
table[key] = count+1;
}
}
bool isHit(Location locKey){
PairHashFunction hfunc;
auto it = table.find(hfunc(locKey.first,locKey.second));
return (it == table.end()) ? false :true;
}
};
HTH!
Top comments (0)