Code: Select all
/' ------------ hash table v.04 demo - 2017 Oct 9 - by dafhi
Background: Thread about color quantization rekindled my interest
to develop a color quant of my own.
Most standard images contain less than 500K unique colors,
and it seems wasteful to create a 16M size array.
The most untrivial part is to read a source pixel and tell
which palette index it associates with.
Ponder that if you care to.
A short answer to this problem: modulus (whatever palette size you prefer)
A more complete answer: hashing technique
There is a great video about this on youtube - mFY0J5W8Udk
'/
' ------------ hash table v.04 - 2017 Oct 9 - by dafhi
type byteTriple 'for counting or binning, uses 3 bytes
as ubyte a,b,c
declare operator cast as ulong
declare operator cast as string
End Type
operator byteTriple.cast as ulong
return ((c)shl 16)or((b)shl 8)or a
End Operator
operator byteTriple.cast as string
return str(culng(this))
End Operator
operator +(lhs as byteTriple, rhs as ulong) as byteTriple
rhs+=lhs.a+((lhs.b)shl 8)+((lhs.c)shl 16)
lhs.a=rhs and 255: lhs.b=(rhs shr 8)and 255: lhs.c=(rhs shr 16)and 255
return lhs
End Operator
type HashInput as ulong
type val_and_count
as HashInput v
as byteTriple c
End Type
type HashTable
as long u = -1, c, uniq, colli
as HashInput lo, hi
as val_and_count histo(any)
declare property get(v as HashInput) as long
declare function push(v as HashInput) as long
declare sub size(in as long)
declare constructor
private:
as long trig, push0
as single i, j
End Type
constructor.HashTable: size 290000
end constructor
sub HashTable.size(in as long): c=in: u=c-1: trig = c*1.0: redim histo(u)
colli=0: push0=0: uniq=0
End sub
property HashTable.get(v as HashInput) as long
v and= &HFFFFFF
j=1: i = int(v+.5) mod c
while histo(i).v <> v
if histo(i).c=0 then exit while
i=(i+j)mod c
if j>trig then return 0 '-1 v.03
j *= 1.11
Wend: return i
End Property
function HashTable.push(v as HashInput) as long
v and= &HFFFFFF
if push0<1 then lo=v: hi=v: push0=1
lo+=(lo-v)*(v<lo)
hi+=(hi-v)*(v>hi)
j=1: i = int(v+.5) mod c
while histo(i).v <> v
if histo(i).c=0 then exit while
i=(i+j)mod c
if j>trig then colli+=1: return 0 ' -1 v.03
j *= 1.11
Wend: if histo(i).c=0 then uniq+=1
histo(i).v=v
histo(i).c+=1: return i
End function
var u = 9
dim as ulong cols(u)
dim as hashtable ht: ht.size (u+1)*1.1
for i as long = 0 to u
cols(i) = int(rnd*&H1000000)
ht.push cols(i)
Next
if ht.colli=0 then
? "low "; ht.lo
? "high "; ht.hi
?
? "unique values "; ht.uniq
? "table size "; ht.c
else
? "there was a collision"
EndIf
sleep