LINUX.ORG.RU

Оцените мою программу (функцию) на Питоне

 , ,


0

2

У меня две версии. Интересно ваше мнение. )) Нормально написана или нет?

Ищет самый длинный палиндром-подстроку (одинаково читающуюся в обоих направлениях) в строке/тексте.
Возвращает положение этого палиндрома в заданном тексте
1)

def subpalindr(text):
    try:
        l=len(text)
        text=text.lower()
        reversed_text=text[::-1]
        result=[]
        for i in range(l):
            result+=[(i,j+1) for j in range(i+2,l) if text[i:j+1] in reversed_text]
        return max(result,key=lambda a: a[1]-a[0])
    except:
        return(0,0)

2)

def subpalindr(text):
    try:
        l=len(text)
        text=text.lower()
        reversed_text=text[::-1]
        result=[]
        i=0
        while i<=l-3:
            j=i+3
            while text[i:j] in reversed_text and j<=l:
                j+=1
            result+=[(i,j-1)]
            i=j-1
        return max(result,key=lambda a: a[1]-a[0]) if len(result)>1 else result[0]
    except:
        return(0,0)

Перемещено leave из general



Последнее исправление: leave (всего исправлений: 3)

subpalindr = (lambda text:
    max((
        (text[i:j], i, j)
            for i in range(len(text))
                for j in range(1+i, len(text))
                    if (text[i:j] == text[i:j][::-1])),
        key=lambda l: len(l[0]))[1:])
aedeph_ ★★
()

тред погрмиздов

def subpalindr(text):
    text = text.lower()
    reversed_text = text[::-1]
    
    results = {}
    for a in range(len(text)-1):
        for b in range(a+1, len(text)):
            if text[a:b] in reversed_text:
                results[b-a] = results.get(b-a, []) + [text[a:b]]
                
    return results[max(results.keys())]

cast vvn_black

anonymous
()

Нормально написана или нет?

нет

1) Функция не должна быть оберткой над try-except, надо наоборот, внутри try размещать функцию (одну)

2) try-except тут вообще ни к чему

alpha ★★★★★
()
Ответ на: комментарий от anonymous

Да без проблем.

subpalindr = (lambda text:
    __import__("functools").reduce(lambda x, y: x if (len(x[0]) > len(y[0])) else y,
        ((text[i:j], i, j)
            for i in range(len(text))
                for j in range(1+i, len(text))
                    if (text[i:j] == text[i:j][::-1])))[1:])
aedeph_ ★★
()
Последнее исправление: aedeph_ (всего исправлений: 1)
Ответ на: комментарий от anonymous

Осталось вытащить text[a:b] == text[a:b][::-1] в отдельную функцию и будет ништяк.

no-such-file ★★★★★
()
Ответ на: комментарий от anonymous

протестровано

функция возвращает список подстрок-палиндромов, а если как параметр ввести пустую строку выдает ошибку.

hibiscusM
() автор топика

Нормально написана или нет?

Вариант №2 не рабочий. Оба варианта ужасны. Смотри как анонимус выше написал - всё понятно и никакой магической арифметики.

no-such-file ★★★★★
()
Ответ на: комментарий от alpha

except без указания типа(ов) исключения тоже дурной тон.

pawnhearts ★★★★★
()
Ответ на: протестровано от hibiscusM

так сойдёт?

def subpalindr(text, min_len=3):
    text = text.lower()
    
    results = {}
    for a in range(len(text)):
        for b in range(a+min_len, len(text)+1):
            if text[a:b] == text[a:b][::-1]:
                results[b-a] = results.get(b-a, []) + [(a,b)]
                
    if results:
        return results[max(results)]
anonymous
()
Ответ на: комментарий от hibiscusM

Ну и в целом как ты понял, я голосую за вариант с

def palindr(text)
    return text == text[::-1]

...

for i in range(len(text)):
    for j in range(i+1, len(text)):
        if palindr(text[i:j]):

...

no-such-file ★★★★★
()
Ответ на: комментарий от aedeph_

нравится!

Мне нравится, так хитровывернуто )) с reduce() и lambda. Пара моментов:

1) выдает ошибку, если ввести пустую строку как параметр (вот почему у меня try/except было)

     
    for i in range(len(text))
TypeError: reduce() of empty sequence with no initial value

Process finished with exit code 1
2)
 for j in range(1+i, len(text)+1) 
единицу добавить
3) есть предположение, что медленно выполняется, т.к. многократный вызов len() и 2 цикла for, а также прочие функции.

hibiscusM
() автор топика
Ответ на: комментарий от anonymous

да, со словарем нормально без магической арифметики, спасибо

if results:
  return results[max(results)][0] 
hibiscusM
() автор топика
Ответ на: нравится! от hibiscusM

1), 2)

subpalindr = (lambda text:
    __import__("functools").reduce(lambda x, y: x if (len(x[0]) > len(y[0])) else y,
        ((text[i:j], i, j)
            for i in range(len(text)+1)
                for j in range(1+i, len(text)+1)
                    if (text[i:j] == text[i:j][::-1])),
         ("", 0, 0))[1:])

3) есть предложение тогда переписать на Fortran

aedeph_ ★★
()
Последнее исправление: aedeph_ (всего исправлений: 1)

Ох... ужасный стиль

AUX ★★★
()
Ответ на: нравится! от hibiscusM

1) выдает ошибку, если ввести пустую строку как параметр (вот почему у меня try/except было)

И вместо if not string: return; ты принес try-except?

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

alpha ★★★★★
()
Ответ на: комментарий от aedeph_

EAFP был бы если бы он не парился по поводу фейла на пустой строке, потому что нечего этой пустой строке здесь делать

alpha ★★★★★
()
from itertools import islice, combinations as comb

def subpali(text, min_len=3):
    text = text.lower()

    def text_range_ispali(r):
        a, b = r
        return text[a:b] == text[b-1:a-1:-1]
 
    def range_len(r):
        a, b = r
        return b - a
    
    ranges_combinations = comb(range(len(text)+1), 2)
    sorted_ranges = sorted(ranges_combinations, key=range_len, reverse=True)
    
    for r in sorted_ranges:
        if range_len(r) >= min_len:
            if text_range_ispali(r):
                yield r
        else:
            break

text = '''
    Финский язык:
        Saippuakivikauppias (самое длинное в мире слово-палиндром)
    Греческий язык:
        Νίψον ανομηματα μη μοναν οψίν («Смой грехи, не только лицо»)
'''

text = text.replace(' ', '')
palis_count = 4
for a, b in islice(subpali(text), palis_count):
    print((a,b), repr(text[a:b]))
(83, 108) 'Νίψονανομηματαμημονανοψίν'
(84, 107) 'ίψονανομηματαμημονανοψί'
(85, 106) 'ψονανομηματαμημονανοψ'
(14, 33) 'Saippuakivikauppias'
anonymous
()
Ответ на: комментарий от anonymous

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

Наверное, она еще и самая быстрая из всех предложенных здесь. )) Надо проверить сколько по времени занимает каждый из предложенных вариантов.

hibiscusM
() автор топика
Ответ на: комментарий от anonymous

удачная идея с itertools.combinations и сортировкой.

hibiscusM
() автор топика

И ни одного решения за O(N)?

f1u77y ★★★★
()
Ответ на: комментарий от hibiscusM

спасибо :)

вот это text[b-1:a-1:-1] надо обратно поменять на text[a:b][::-1]

навряд ли будет ощутимая разница в скорости среди предложенных вариантов.

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

def subpalindr(text, min_len=3):
    text = text.lower()
    for length in range(len(text)+1, min_len-1, -1):
        for offset in range(len(text)+1 - length):
            a = offset
            b = offset+length
            if text[a:b] == text[a:b][::-1]:
                return a, b

anonymous
()
Ответ на: комментарий от no-such-file

Где-то читал, что в питоне вызов функции достаточно «дорогой», поэтому не рекомендуют запихивать вызовы внутрь циклов.

grem ★★★★★
()
Ответ на: комментарий от grem

В питоне и тупо цикл по интам достаточно дорогой, и что теперь? Код на питоне должен быть понятным. Горячий код, отстойная производительность которого заверена уважаемым старцем с профайлером, должен быть не на питоне.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Цикл дорог, но не надо же ещё его удорожать ещё сильнее. Код везде должен быть понятным, но это не значит, что не надо использовать преимущества отдельного языка и не избегать его слабых сторон. Цикл внутри функции в питоне гораздо выгоднее вызова функции внутри цикла. Да и одна «непонятная строчка» в данном случае просто комметируется, учитывая что она нигде больше не вызывается.

На питоне и не пишут горячий код. Ну то есть может кто-то и пишет (я не имею ввиду случай использования библиотек на c вроде numpy), но я не знаю, зачем он/они это делают.

grem ★★★★★
()

Твой код больно читать.

anonymous
()

Мой простой вариант:

def palindrome(s):
    s = s.lower().replace(' ', '')
    result = ''
    for i in range(0, len(s)):
        for j in range(i + 1, len(s)):
            if s[i:j] == s[i:j][::-1] and (j - i) > len(result):
                result = s[i:j]
    return result
bff7755a
()
Ответ на: комментарий от anonymous

По вики O(nn) https://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока

text = 'Saippuakivikauppias (самое длинное в мире)'.lower()


def find_palindromon(text):
    """ """
    result = (0, 0, 0)
    a = []
    for i, m in enumerate(text):
        a.append([])
        for j, n in enumerate(text[::-1]):
            a[i].append(0 if m != n else a[i - 1][j - 1] + 1 if i and j else 1)
            if a[i][j] >= result[2]:
                result = (i, j, a[i][j])

    return (result[0] + 1 - result[2], result[2]) if result[2] > 1 else (0, 0)


pos, length = find_palindromon(text)
print(pos, length, text[pos: pos + length])
0 19 saippuakivikauppias
vvn_black ★★★★★
()
Ответ на: комментарий от anonymous

И точно, хрень получилась, общая подстрока не всегда палиндром. Результат фильтровать надо.

vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 1)
Ответ на: комментарий от anonymous

Вот так, сначала найти все общие подстроки, а проверять на «палиндромность» потом, но уже некрасиво:

def find_palindromon(text):
    """ """
    result = (0, 0, 0)
    results = []
    a = []
    for i, m in enumerate(text):
        a.append([])
        for j, n in enumerate(text[::-1]):
            a[i].append(0 if m != n else a[i - 1][j - 1] + 1 if i and j else 1)
            if a[i][j] >= result[2]:
                result = (i, j, a[i][j])
                if a[i][j] > 1:
                    results.append(result)

    for r in results[::-1]:
        pos, l = (r[0] + 1 - r[2], r[2])
        if (text[pos: pos + l] == text[pos: pos + l][::-1]):
            return (pos, l)

    return (0, 0)

vvn_black ★★★★★
()
Ответ на: комментарий от vvn_black

прикольно :) работает быстрее тупых циклов

anonymous
()
Ответ на: комментарий от t184256

это то да, а то потом не разобрать иначе, что из холодного «свалилось» в горячий.

grem ★★★★★
()
Ответ на: комментарий от zaz

да это так

Обе мои функции не совсем работают. Когда неодинаковые пробелы в тексте и в словах, и когда цифры есть, то выдает ерунду.

Функция №1 доработана. Теперь когда есть пробелы в тексте и в словах, а также цифры, ф-я выдает положение палиндрома в заданном тексте с учетом пробелов и цифр. Если палиндром перемешан с цифрами, то такой палиндром отбрасывается(игнорируется).

def subpalindr(text): #first version
    try:
        l=len(text)
        text=text.lower()
        result=[]
        for i in range(l):
            result+=[(i,j+1) for j in range(i+2,l) if text[i: (j + 1)].replace(' ', '').isalpha() \
            and  text[i: (j + 1)].replace(' ', '') == text[i:(j + 1)][::-1].replace(' ', '')]  
        k=max(result, key=lambda a: a[1] - a[0])
        return text[k[0]:k[1]],k if len(text[k[0]:k[1]].strip())>2 else (0,0)
    except:
        return "Empty string!"

Результат:


print(subpalindr('somethingra123 c e12car going'))
print(subpalindr('123 a ba123'))
print(subpalindr('123 aba 123'))
print(subpalindr('Mad am I ma dam.'))
print(subpalindr('somethin rac e car going'))
print(subpalindr(''))


(' c ', (0, 0))
(' a ba', (3, 8))
(' aba ', (3, 8))
('mad am i ma dam', (0, 15))
(' rac e car ', (8, 19))
Empty string!

Process finished with exit code 0
hibiscusM
() автор топика
Ответ на: да это так от hibiscusM

Проблема не в пробелах и цифрах, если взять ф-ю из стартового поста то например для строки:

qweAArty

Подстрока не находится, а хотелось бы (AA)

А вот если взять строку

qwASDFGerGFDSAty

То полиндром находится, хотя его здесь нету ....

zaz ★★★★
()
Ответ на: комментарий от zaz

сейчас нормально

Если поменять

except:
    return "Empty string!"

на 'No palindrome' то

print(subpalindr('qwASDFGerGFDSAty'))

No palindrome

Process finished with exit code 0

А насчет 'qweAArty' моя функция игнорирует палиндром в количестве 2 chars.

hibiscusM
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.