Блог

Я работаю над проектом, в котором мне нужно сгенерировать несколько идентификаторов для комбинаторного объединения различных молекул. Для этого я присваиваю каждой молекуле n-битную строку (где n — количество имеющихся у меня пулов. В данном случае 79 пулов), и каждая строка имеет 4 бита «on» (4 бита, равные 1), соответствующие тому, в каких пулах появится эта молекула. Далее я хочу сократить количество строк таким образом, чтобы ни одна из двух молекул не появлялась в одном пуле более двух раз (другими словами, наибольшее число перекрывающихся битов между двумя строками не может быть больше 2).

Для этого я: 1) скомпилировал список всех n-разрядных строк с k битами «on», 2) сгенерировал список списков, где каждый элемент представляет собой список индексов, в которых бит используется re.finditer , и 3) перебираю список для сравнения строк, добавляя только строки, которые соответствуют моим критериям в моем окончательном списке строк.

Код, который я использую для сравнения строк:

 drug_strings = [] #To store suitable strings for combinatorial pooling rules

class badString(Exception): pass

for k in range(len(strings)):
    bit_current = bit_list[k]
    try:
        for bits in bit_list[:k]:
            intersect = set.intersection(set(bit_current),set(bits))
            if len(intersect) > 2:
                raise badString() #pass on to next iteration if string has overlaps in previous set
        drug_strings.append(strings[k])
    except badString:
        pass 
 

Однако выполнение этого кода занимает целую вечность. Я запускаю это с n = 79-битными строками с k = 4 битами «on» на строку (~ 1,5 млн возможных строк), поэтому я предполагаю, что длительное время выполнения связано с тем, что я сравниваю каждую строку с каждой предыдущей строкой. Есть ли альтернативный / более разумный способ сделать это? Алгоритм, который работал бы быстрее и был бы более надежным?

РЕДАКТИРОВАТЬ: я понял, что более простой способ подойти к этой проблеме вместо определения всего подмножества строк, которые были бы подходящими для моего проекта, состоял в том, чтобы просто случайным образом выбрать больший набор n-разрядных строк с k битами «on», сохранить только те строки, которые соответствуют моим критериям, а затем, как только я у меня есть соответствующее количество подходящих строк, просто возьмите из них столько, сколько мне нужно. Новый код выглядит следующим образом:

 my_strings = []
my_bits = []

for k in range(2000):
    random = np.random.randint(0, len(strings_77))
    string = strings_77.pop(random)
    bits = [m.start() 1 for m in re.finditer('1',string)]
      
    if all(len(set(bits) amp; set(my_bit)) <= 2
           for my_bit in my_bits[:k]):
        my_strings.append(string)
        my_bits.append(bits)
 

Теперь мне нужно сравнить только со строками, которые я уже извлек (не более 1999 предыдущих строк вместо 1 миллиона). Так все проходит гораздо быстрее. Спасибо за помощь!

Создание исключений обходится дорого. Создается сложная структура данных, и стек должен быть размотан. На самом деле, настройка блока try / except обходится дорого.

На самом деле вы хотите проверить, что все пересечения имеют длину меньше или равную двум, а затем добавить. Нет необходимости в исключениях.

 for k in range(len(strings)):
    bit_current = bit_list[k]

    if all(len(set(bit_current) amp; set(bits)) <= 2
           for bits in bit_list[:k]):
        drug_strings.append(strings[k])
 

Кроме того, вместо того, чтобы искать строки и индекс bit_list, вы можете перебирать все нужные вам части одновременно. Вам все еще нужен индекс для фрагмента bit_list:

 for index, (drug_string, bit_current) in enumerate(zip(strings, bit_list)):
    if all(len(set(bit_current) amp; set(bits)) <= 2
           for bits in bit_list[:k]):
        drug_strings.append(drug_string)
 

Вы также можете избежать создания bit_current набора с каждым циклом:

 for index, (drug_string, bit_current) in enumerate(zip(strings, bit_list)):
    bit_set = set(bit_current)
    if all(len(bit_set amp; set(bits)) <= 2
           for bits in bit_list[:k]):
        drug_strings.append(drug_string)
 

Некоторые незначительные вещи, которые я бы улучшил в вашем коде, которые могут вызывать некоторые накладные расходы:

1. set(bit_current) переместите это за пределы внутреннего цикла;
2. удалите raise except часть;
3. Поскольку у вас есть это условие if len(intersect) > 2: , вы можете попытаться реализовать interception метод остановки при выполнении этого условия. Чтобы избежать ненужных вычислений.

Таким образом, код станет:

 for k in range(len(strings)):
    bit_current = set(bit_list[k])
    intersect = []
    for bits in bit_list[:k]:
        intersect = []
        b = set(bits)
        for i in bit_current:
            if i in b:
                intersect.append(i)
            if len(intersect) > 2:
                break

        if len(intersect) > 2:
            break
    if len(intersect) <= 2:
       drug_strings.append(strings[k])