Fast searching through bitarray? I've been thinking for some time but can't figure a way out.
I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of memory).

I'm looking for some better algorithm for searching/matching !

Do you have any idea ?

bitarray looks like this :

 0) 1011.... &lt;= 10_000 bits
 1) 1100....
 2) 0010....
 3) ........
 ...........


now find index of "1100...." :

 find(1100....) = 1




50% of bits are 1, 50% are 0, always.



I could probably sort it by hamming distance, but will be time consuming! (and array grows dynamically, so i have to re-sort) and the search will still be slower if I search one by one (probably because python overhead).
Currently the search is binary op+, but as you expect doesn't scale well i.e. 

#duplicate the search item to the size of array
si_dup = search_item * array_size
dist's = (array ^ si_dup).count_by_row(1s)
top_idx = dist's.argmin()


The bad thing is that this is parallelize-able (I can process it in chunks), but python is not multi-threaded :(.
Also can seem to find a DB which handle large binary-strings, that will be a way out for large sets, I think!



thanks, "locality sensitive hashing" was the key, I researched it a bit and that seem will be the solution for large bitarrays (LSH via BitSampling).
For small ones the current approach I think will be faster.
If you want to look for an exact match, use a hashtable.  Choose a hash function that hashes a 10,000-bit string to a short hashcode.  This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.