Найдите слова, отличающиеся только одной буквой, из списка слов

Я пытаюсь найти в списке все буквы, которые отличаются друг от друга словом. Затем я вывожу их в массив. Проблема в том, что моему текущему коду на 18 000 слов требуется 17 секунд, и я пытаюсь сократить это время.

Могу ли я как-нибудь ускорить это?

#compares words and returns true if they are neighbours
def isneighbour(word1, word2):
    diff = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            diff += 1
            if diff > 1:
                return False
    return diff == 1


def find_neighbours(lst):
    #take a word from lst
    #compare to rest of words from lst
    hood = []
    #convert dictionary to list
    #search for all words of same length
    keylst = list(lst.keys())
    length = len(keylst) -1
    for i in range(0, length -1):
        temp = []
        temp.append(keylst[i])
        for j in range(i + 1, length):
            if len(keylst[i]) == len(keylst[j]):
                #test to see if two words of the same length are neighbours
                if isneighbour(keylst[i], keylst[j]):
                    temp.append(keylst[j])
        if len(temp)>1:
            quicksort(temp)
            hood.append(temp)
    return hood

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

Возможно, на этот вопрос лучше ответить в проверке кода

— 27.05.2024 04:19

Я создал простой пример кода C++ с кодами ядра для графического процессора. Вычисление матрицы на графическом процессоре RTX4070 заняло 8 миллисекунд. С оптимизацией это может быть намного быстрее, но для простоты я не оптимизировал. Используя библиотеку Python numba, вы можете добиться аналогичной производительности. В настоящее время он работает только для 18000 слов, и если сделать его динамическим, производительность снизится на несколько процентов: github.com/tugrul512bit/examplesForLibGPGPU/blob/main/…

— 27.05.2024 11:22

python algorithm performance data-structures

27.05.2024 03:47

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

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

Советы по эффективной веб-разработке с помощью Python

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

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Расстояние Левенштейна

Это зависит от вашего определения «отличаться друг от друга буквой».
Мне кажется, порядок букв имеет значение, что усложняет задачу.
Если это ваши предположения, я бы начал с Левенштейна, который использует динамическое программирование. Вы можете настроить алгоритм в зависимости от ожидаемого результата или использовать его для сужения пространства поиска, поскольку расстояние Левенштейна довольно быстрое.


import random, string, collections


def levenshtein_edit_distance(A, B):
    dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
    for i in range(len(A) + 1):
        dp[i][0] = i
    for j in range(len(B) + 1):
        dp[0][j] = j

    for i in range(1, len(A) + 1):
        for j in range(1, len(B) + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1]


def _gen_words(l):
    return ''.join(random.choice(string.ascii_lowercase) for _ in range(l))


def _modify(word, diffs=1):
    word = list(word)
    for _ in range(diffs):
        i = random.randint(0, len(word) - 1)
        word[i] = random.choice(string.ascii_lowercase)
    return ''.join(word)


words = [_gen_words(3)]

random.seed(10)

for _ in range(100000):
    diffs = random.randint(1, 1)
    w = _modify(words[-1], diffs)
    words.append(w)

unique_words = list(set(words))

memo = collections.defaultdict(list)
for a, b in zip(unique_words[:], unique_words[1:]):
    dist = levenshtein_edit_distance(a, b)
    if dist == 1:
        memo[a] += [b]

print(memo)

Принты

defaultdict(<class 'list'>, {'sqb': ['sqe'], 'evn': ['lvn'], 'wsr': ['wfr'], 'nnl': ['cnl'], 'joe': ['boe'], 'qol': ['qzl'], 'rbm': ['rbk'], 'tsj': ['tsg'], 'sga': ['sgt'], 'abw': ['arw'], 'yjl': ['fjl'], 'wth': ['вау'], 'zkn': ['ukn'], 'shs': ['xhs'], 'szi': ['czi'], 'eps': ['cps'], 'asb': ['hsb'], 'ish': ['iss'], 'owm': ['rwm'], 'vae': ['vab'], 'dou': ['doz'], 'qeh': ['qch'], 'wod': ['woj'], 'pyg': ['ryg'], 'ctf': ['jtf'], 'hjw': ['hjq'], 'alx': ['clx'], 'ikj': ['ikp'], 'gyr': ['gym'], 'pkj': ['kkj'], 'bcy': ['xcy'], 'ebr': ['evr'], 'gcm': ['gcq'], 'iqw': ['iqx'], 'bml': ['bma'], 'wrz': ['wwz'], 'psk': ['ksk'], 'wtp': ['wzp'], 'inc': ['inn'], 'qbp': ['mbp'], 'bas': ['aas'], 'jfx': ['jyx'], 'osa': ['tsa'], 'shn': ['sun'], 'lhs': ['fhs'], 'fzm': ['fzu'], 'rzc': ['ruc'], 'idi': ['ido'], 'sdw': ['sdo'], 'lye': ['hye'], 'dht': ['cht'], 'gjy': ['gyy'], 'efs': ['efb'], 'rnb': ['rqb'], 'gtw': ['rtw'], 'pgf': ['pgn'], 'yhz': ['ycz'], 'rre': ['rce'], 'box': ['fox'], 'zql': ['zqn'], 'wmc': ['wmx'], 'tny': ['tey'], 'ayy': ['azy'], 'jka': ['jkn'], 'ost': ['ist'], 'ktc': ['kcc'], 'zxl': ['zxo'], 'jfs': ['jvs'], 'jgy': ['rgy'], 'tql': ['tel'], 'yne': ['yje'], 'mpa': ['ypa'], 'uwg': ['ufg'], 'uec': ['uee'], 'ppr': ['rpr'], 'eln': ['egn'], 'opp': ['opk'], 'rip': ['jip'], 'zge': ['fge'], 'jfb': ['jft'], 'jcu': ['jcq'], 'ngc': ['ngq'], 'vrw': ['vcw'], 'uml': ['fml'], 'lez': ['lmz'], 'nhy': ['uhy'], 'nuz': ['nuj'], 'wjj': ['wjg'], 'bqa': ['uqa'], 'kil': ['kix'], 'ymj': ['yxj'], 'bqg': ['bhg'], 'lop': ['lok'], 'fev': ['fei'], 'fjp': ['fje'], 'wzw': ['wiw'], 'ayp': ['anp'], 'xvf': ['yvf'], 'ptw': ['pte'], 'cts': ['ats']})