Ищите оптимизированное Regex / другое решение для массового сопоставления строк

Question

Часть моего текущего кода включает (псевдо) случайную генерацию довольно большого количества пар строк различной длины, в частности,

shiftspace = {
    2: 20,
    3: 79,
    4: 250,
    5: 791,
    6: 2500,
    7: 7906,
    8: 25000,
    9: 79059
}

, где ключ = длина строки и значение = пары, которые должны быть сгенерированы. Эти строки могут состоять из любого варианта символов 0-9, а также символа *, который представляет любой символ. Проблема заключается в том, что я не хочу, чтобы наборы содержали какие-либо повторы. До того, как я реализовал *, я просто проверил, было ли уже сгенерировано новое сгенерированное число, но теперь строки могут «перекрываться», несмотря на то, что они не идентичны. Например, существование "* 056 * 3" делает недействительной сгенерированную последовательность "* 05693" или "905623" или "4056 * 3"

В настоящее время решением является мой старый "" друг "" Regex. Я просто генерирую строку регулярного выражения, состоящую из [char1 *] [char2 *] [char3 *] et c, которая способна идеально подобрать эти совпадения. Проблема в скорости - я проверяю регулярное выражение для каждой записи, которая увеличивается во времени, когда достигаются более высокие числа (максимально возможный набор для проверки может достигать почти 80 000 записей). То, что раньше занимало 5 минут до *, теперь занимает час или больше. Код, который делает все это, приведен ниже.

def regexfit(strang,set):
    regex = ""
    for char in strang:
        regex = regex + "["+char+"*]"
    match = re.search(regex,set)
    if match:
        return True

def shiftgen():
    baseset = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "*"]
    shiftset = {}
    keys = list(shiftspace.keys())
    togo = sum(shiftspace.values())
    print(togo)
    for i in range(min(keys), max(keys) + 1):
        print(i)
        shiftset[i] = {}
        shiftset[i]["0"] = 0
        for j in range(shiftspace[i]):
            num = 0
            num2 = 0
            while num == num2:
                num = np.random.choice(baseset, size=i)
                num = "".join(num)
                numset = [i for i in str(num)]
                while any((regexfit(num,x) for x in shiftset[i].keys())):
                    num = np.random.choice(baseset, size=i)
                    num = "".join(num)
                    numset = [i for i in str(num)]
                if len(str(num)) < i:
                    for k in range(i - len(str(num))):
                        numset.append(0)
                num2 = np.random.choice(numset, size=i, replace=False)
                num2 = "".join(num2)
            shiftset[i][num] = num2
            togo = togo - 1
            if togo % 1000 == 0:
                print([num, num2])
        shiftset[i].pop("0")
    return shiftset

Вещи, которые я рассмотрел:

• Объединение всех последовательностей для проверки в одну огромную строку (с разделителем char чтобы предотвратить сопоставление регулярного выражения в двух последовательностях) и использовать регулярное выражение в этом. Я не знаю достаточно о внутренностях двигателя re , чтобы понять, насколько хорошо это закончится. Я собираюсь проверить, насколько быстро он запускается после завершения моего первого временного теста кода, приведенного выше.

• Добавление этих звездочечных строк в базу данных в виде просто каждой возможной перестановки, которую они могут выполнить ( ie: 2 * добавляется как 21,22,23 и др. c)>. Затем вы просто просматриваете базу данных (или, если вы генерируете звездочку, вы просматриваете каждую перестановку и проверяете, положительны ли они). Я очень сомневаюсь, что это будет более эффективным, но вы никогда не знаете.

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

• Некоторое более продвинутое выражение регулярного выражения, которое оценивается быстрее.

• Какой-то волшебный c модуль / формула, который по какой-то причине действительно хорошо справляется с этой задачей.

• Черные маги c, жертвы Elder Gods, et c.

TL: DR Я ищу более быстрый способ сопоставления последовательностей со многими потенциальными перестановками, чтобы гарантировать, что перестановка ранее не была выбрана.

Answer 1

Несколько комментариев, всего слишком много для комментария ...

Регулярное выражение, которое вы строите в своем текущем коде, на самом деле не правильно. Класс персонажа [**], который вы создаете, когда встречаете * в strang, будет соответствовать * в set, где вы на самом деле хотите сопоставить любому символу. Когда вы сталкиваетесь с * в strang, вы должны поставить . в регулярное выражение. Например:

regex = ''.join('.' if c == '*' else '[*' + c + ']' for c in strang)

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

Наконец, это должно быть быстрее, чем использование регулярных выражений (мои тесты показывают 3-4x), чтобы просто перебирать символы в каждом значении, сравнивая их по одному и сразу заканчивая неудачей, когда нет совпадений, например

def regexfit(strang,set):
    for a, b in zip(strang, set):
        if a != '*' and b != '*' and a != b:
            return False
    return True