Тестирование вектора без сканирования

Question

Для серии алгоритмов, которые я реализую, мне нужно моделировать такие вещи, как наборы монет, взвешиваемых или объединенных образцов крови. Главной целью является выявление редкого набора интересных предметов в наборе идентичных предметов. Эта идентификация выполняется путем тестирования групп предметов вместе. Например, классическая проблема заключается в том, чтобы найти легкую поддельную монету в группе из 81 (идентичных) монет, используя как можно меньше весов баланса лотка. Трюк состоит в том, чтобы разделить 81 монет на три группы и взвесить две группы друг против друга. Затем вы делаете это в группе, которая не балансирует, пока у вас не останется 2 монеты.

Ключевым моментом в обсуждении выше является то, что набор интересных элементов разрежен в более широком наборе - алгоритмы, которые я реализую для всех типов бинарного поиска и т. Д. Для этого типа ввода.

Что мне нужно, это способ проверить вектор весь, что указывает на наличие одного или нескольких из них, без сканирования вектор покомпонентно.

I.e. способ вернуть вес Хэмминга вектора в операцию O (1) - это будет точно имитировать объединение образцов крови/групп взвешивания монет в балансе лотка.

Ключом к тому, что вектор не сканируется, но на выходе должно указываться, что в векторе имеется по меньшей мере один символ. При сканировании я имею в виду просмотр вектора с такими алгоритмами, как бинарный поиск или просмотр каждого элемента по очереди. Это необходимо для моделирования групп элементов (например, образцов крови) и одного теста в группе, который указывает на наличие 1.

Я реализовал этот «вектор» в качестве списка в настоящее время, но это необходимо «Не станешь в камне. Задача состоит в том, чтобы определить, тестируя группы подписок, где находятся 1s в векторе. Примером списка является:

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

Но это также может быть длинным/установленным/что-то еще, как предложено ниже.

В настоящее время я использую any() в качестве теста, но мне было указано, что any() сканирует вектор - побеждая цель того, чего я пытаюсь достичь.

Вот пример наивного двоичного поиска с использованием любого для проверки группы:

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 a 1 
      return -1 
    return mid 

Я прошу прощения, если этот код не качество продукции. Любые предложения по его улучшению (за пределами теста any()) будут оценены.

Я пытаюсь найти лучший тест, чем любой(), как было указано, что any() сканирует список - побеждая то, что я пытаюсь сделать. Тест не должен возвращать точный вес Хэмминга - он просто должен указать, что в тестируемой группе (или нет!) Нет 1 (то есть верхний/нижний код выше).

Я также думал об использовании двоичного xor, но не знаю, как использовать его таким образом, который не является покомпонентным.

Answer 1

any будет сканировать весь вектор, если вы не находите вас после конца «вектора». Из docs это эквивалентно

def any(iterable): 
    for element in iterable: 
     if element: 
      return True 
    return False 

Это делает его O(n).Если у вас есть вещи отсортированы (в вашем «двоичном векторе»), вы можете использовать bisect.

например. position = index(myVector, value)

Answer 2

Вот набросок:

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() 

Выход:

[0] 
False 
[0, 1] 
True 
[0] 
False 

Идея заключается в том, чтобы наследовать от list, и добавить одну переменную, которая хранит число ненулевых элементов. В то время как решающая функциональность делегируется базовому классу list, в то же время вы отслеживаете количество ненулевых записей в списке и можете запросить его в O(1) с использованием функции-члена hasOne().

HTH.

Answer 3

Хорошо, возможно, я попробую альтернативный ответ.

Вы не можете сделать это без каких-либо предварительных знаний о своих данных. Единственное, что вы можете сделать, чтобы сделать тест и кэшировать результаты. Вы можете создать структуру данных, которая поможет вам определить результат любых последующих тестов в случае, если ваша структура данных изменена, или структуру данных, которая сможет лучше определить ответ в подмножестве вашего вектора.

Однако, ваш вопрос не указывает на это. По крайней мере, это не было на момент написания ответа. Пока вы хотите сделать один тест на вектор, для присутствия определенного элемента, не дающего предварительных знаний о данных, во временной сложности меньше O (log n) в среднем случае или O (n) в худшем случае. Это невозможно.

Также имейте в виду, что вам нужно загрузить вектор в какой-либо точке, который выполняет операции O (n), поэтому, если вы заинтересованы в выполнении одного теста над набором элементов, вы вряд ли потеряете много. В среднем случае с большим количеством элементов время загрузки будет намного больше, чем тестирование.

Если вы хотите выполнить набор тестов, вы можете разработать алгоритм, который будет «накапливать» некоторые знания во время последующего теста, что поможет определить результаты в лучшие времена. Однако это относится только к тому, что вы хотите сделать более одного теста!