Bloom Filter

Deduplicating a high-volume stream with a plain array or a set means memory that grows without bound as more items pass through - fine for a session, awkward for an EA meant to run for weeks against a busy news feed or a symbol that generates thousands of ticket numbers a day. A Bloom filter answers "have I seen this before" from a fixed-size bit array, whatever volume passes through it, at the cost of an occasional false positive whose rate is chosen up front. Init(expectedItems, falsePositiveRate) sizes the bit array and the number of hash functions using the standard formulas - m = -n*ln(p)/(ln2)^2 bits, k = (m/n)*ln2 hash functions - so the filter is tuned for the volume and accuracy actually needed, rather than a guessed bit count that wastes memory or degrades early. Two simple hashes (FNV-1a and djb2) are combined with the standard Kirsch-Mitzenmacher trick, g_i = h1 + i*h2, to synthesise k independent-looking hash functions from just those two, instead of writing and tuning k separate ones by hand. The contract is asymmetric by design and that asymmetry is the whole point: MightContain can return a false positive (says "probably seen" for something never added), but it can never return a false negative (an item that was Added always tests true afterwards, with certainty). That is why the function is named MightContain and not Contains - a name that promised certainty would be a lie the first time the filter reported a collision. Notes and limitations - There is no Remove(). Bloom filters cannot support deletion without a counting variant that trades away the fixed memory footprint - rebuild with Init() (which clears everything) when the tracked set needs to shrink or reset. - Sizing is fixed at Init() time. Adding far more items than expectedItems raises the real false-positive rate above the design target - EstimatedFalsePositiveRate() is the way to notice this before it causes a silent increase in skipped duplicates. - Add/AddLong/MightContain/MightContainLong are not safe to call while another call on the same instance is in progress - normal single-threaded execution on either platform never triggers this, but a filter should not be shared across pointers if a future multi-context use case ever needed it. - The two hash functions (FNV-1a, djb2) are chosen for speed and dispersion, not for security - this is not suitable as a cryptographic commitment or a hash meant to resist deliberate collision construction.

Script · MT4 · v1.0 · Free

Tags: Volume · Trading Sessions · News Trading · MT4 Script · MQL4 Source Code

MQL4 & MQL5 scripts · PolyMaria