python - Testing a vector without scanning it -

for series of algorithms i'm implementing need simulate things sets of coins being weighed or pooled blood samples. overriding goal identify sparse set of interesting items in set of otherwise identical items. identification done testing groups of items together. example classic problem find light counterfeit coin in group of 81 (identical) coins, using few weightings of pan balance possible. trick split 81 coins 3 groups , weigh 2 groups against each other. on group doesn't balance until have 2 coins left.

the key point in discussion above set of interesting items sparse in wider set - algorithms i'm implementing outperform binary search etc type of input.

what need way test entire vector indicates presence of single, or more ones, without scanning vector componentwise.

i.e. way return hamming weight of vector in o(1) operation - accurately simulate pooling blood samples/weighing groups of coins in pan balance.

it's key vector isn't scanned - output should indicate there @ least 1 one in vector. scanning mean looking @ vector algorithms such binary search or looking @ each element in turn. need simulate pooling groups of items (such blood samples) , s single test on group indicates presence of 1.

i've implemented 'vector' list currently, needn't set in stone. task determine, testing groups of sublist, 1s in vector are. example of list is:

sparselist = [0]*100000 sparselist[1024] = 1 

but equally long/set/something else suggested below.

currently i'm using any() test it's been pointed out me any() scan vector - defeating purpose of i'm trying achieve.

here example of naive binary search using test groups:

def binary_search(inlist):     low = 0     high = len(inlist)      while low < high:         mid = low + (high-low) // 2         upper = inlist[mid:high]         lower = inlist[low:mid]           if any(lower):             high = mid         elif any(upper):             low = mid+1         else:             # neither side has 1             return -1    return mid 

i apologise if code isn't production quality. suggestions improve (beyond any() test) appreciated.

i'm trying come better test any() it's been pointed out any() scan list - defeating point of i'm trying do. test needn't return exact hamming weight - merely needs indicate there (or isn't!) 1 in group being tested (i.e. upper/lower in code above).

i've thought of using binary xor, don't know how use in way isn't componentwise.

here sketch:

class orvector (list):       def __init__(self):          self._nonzero_counter = 0         list.__init__(self)      def append(self, x):          list.append(self, x)         if x:             self._nonzero_counter += 1      def remove(self, x):          if x:              self._nonzero_counter -= 1         list.remove(self, x)       def hasone(self):          return self._nonzero_counter > 0   v = orvector()  v.append(0) print v print v.hasone()  v.append(1);  print v print v.hasone()  v.remove(1);  print v print v.hasone() 

output:

[0] false [0, 1] true [0] false 

the idea inherit list, , add single variable stores number of nonzero entries. while crucial functionality delegated base list class, @ same time monitor number of nonzero entries in list, , can query in o(1) time using hasone() member function.

hth.