Архив рубрики: Без рубрики

Поиск первого вхождение подстроки. Решение в лоб.

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…


С поиском подстроки мы встречаемся постоянно. Всем любимый ctrl+f, это именно то, что нам нужно.
Часто ли вы задумывались, а как оно работает? Многие из Вас, наверняка, скажут, что если потребуется — сделаем.
Большинство, думаю, решат эту задачу в лоб и для наглядности я покажу, как это сделать.

Прямой поиск, или, как еще часто говорят, «просто взять и поискать» — это первое решение, которое приходит в голову неискушенному программисту. Суть проста: идти по проверяемой строке A и искать в ней вхождение первого символа искомой строки X. Когда находим, делаем гипотезу, что это и есть то самое искомое вхождение. Затем остается проверять по очереди все последующие символы шаблона на совпадение с соответствующими символами строки A. Если они все совпали — значит вот оно, прямо перед нами. Но вот если какой-то из символов не совпал, то ничего не остается, как признать нашу гипотезу неверной, что возвращает нас к символу, следующему за вхождением первого символа из X.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так, легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: «AAAAB», где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.
Неправильные гипотезы неизбежны, а из-за таких откатываний назад, при плохом стечении обстоятельств, может оказаться, что мы каждый символ в A проверили около |X| раз. То есть вычислительная сложность сложность алгоритма O(|X||A|). Так поиск фразы в параграфе может и затянуться…

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

А вот и реализация:

def stringSearch(s, x):
i=j=0
lengthS = len(s)# Длина строки в которой ищем
lengthX = len(x)# -||- которую ищем
# пока не достигли одного из концов
while i<=lengthS - lengthX and j>lengthx:
# если совпали буквы продвигаемся по обеим строкам
if li[i+j]==x[j]:
j+=1
# иначе двигаемся по строке(+1), начиная с 0 символа подстроки
else:
i+=1
j=0
# если дошли до конца подстроки - нашли, иначе - нет
return i if j==lengthX else None

Алгоритм прост и тривиален, а главное, как было замечено выше, зачастую неплохо работает, особенно, когда строка поиска не сильно велика.
Разобравшись с прямым подходм, давайте  посмотрим, как решать эту задачу — правильно.
Алгоритм Кнута-Морриса-Пратта (КМП)
Алгоритм Бойера — Мура

Используемая литература:

  1. Википедия
  2. habrahabr

Автор: Pavel Petropavlov

Алгоритм Кнута-Морриса-Пратта (КМП)

Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

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

Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Для понимания: Префикс строки A[..i] — это строка из i первых символов строки AСуффикс строки A[j..] — это строка из |A|-j+1 последних символов. Подстроку из Aбудем обозначать как A[i..j], а A[i] — i-ый символ строки. 

В статье http://habrahabr.ru/post/111449/ сказано:

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: «AAAAB», где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.

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

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

Вот пример для «ababcaba»:

суффикспрефиксp
aa0
abab0
abaaba1
abababab2
ababcababc0
ababcaababca1
ababcabababcab2
ababcabaababcaba3

Итак, идея ясна? Ну тогда попробум написать префикс функцию в лоб:

def predkompil(x):
#первый символ всегда 0, поэтому заносим и пропускаем
d = {0:0}
for i in xrange(1,len(x)):
# проходоим от конца к началу
j = i
sdvig = 0
while j>0:
j -= 1
if x[j] == x[i-sdvig]:
sdvig += 1
else:
j += sdvig
sdvig = 0
d[i] = sdvig
return d

Вроде работает, но как то много сравнений и проходов. Попробуем оптимизировать.
Начать можно с замены строки j = i, на j = d[i-1]+1.

Что нам это дает? А то, что незачем просматривать каждый раз с конца и до начала.  Можно заметить, что если мы на предыдущем шаге (i-1) нашли вхождение > 0 (d[i-1]), то и начинать стоит с данной позиции (d[i-1]).

Пример:

При i=4 ABAAB -> 2, тогда на i+1, т.е. i=5  смотрим не с j=i(5), а с 3! Т.к. либо счетчик вырастет и станет 3 в случае ABAABA, либо сбросится в 0 при любой другой букве.
И хотя мы делаем меньше сравнений(пропускаем середину слова), однако весь совпадающий префикс мы проходим, что не есть хорошо.

Это уже не плохо, однако, мы с Вами так и не научились использовать  информацию, полученную на предыдущих и

Подключение Google Drive к Linux Mint

К сожалению, сама Google ещё не выдала нам версию Drive для Linux, поэтому приходиться обходиться сторонними средствами.

Сначала я попробовал такой вариант.

Через установку пакета google-docs-fs. Я попробовал несколько похожих способов, описанных в сети, и у меня возникли ошибки, поэтому пишу здесь окончательный вариант.
Нужно скачать этот пакет с сайта launchpad.net, положить в домашнюю папку.
Установить:
sudo dpkg -i google-docs-fs_1.0~gdrive_all.deb
Часть зависимостей не установилось, дорешил это командой
sudo apt-get install -f
Далее в домашней папке создаём папку Drive и монтируем ее:
gmount Drive name@gmail.com
В ответ запросит пароль, вводим.
Если как у меня, например, в Google двойная аутентификация, то выйдет ошибка.
Значит нужно сходить на страницу авторизованного доступа к аккаунту и сгенерировать там пароль для приложения, который нужно будет ввести в терминале.
Первоначально, синхронизация начиналась, часть файлов в папку загрузилась. Потом почему-то эта папка была постоянно пустой.

Поэтому я решил попробовать ещё один способ — через клиент Insync.

Установить его можно через Synaptic или с официального сайта

Insync создаёт в домашней директории папку insync, где для каждого аккаунта будет своя папка с файлами.

На панели появляется апплет Insync, cодержащий ссылки на папку с файлами, переход в web-интерфейс сервиса Insync, информацию об используемых аккаунтах и hfpkbxyst уведомления.

Причем, файлы выгружаются в совместимом для работы с обычными приложениями, такими как LibreOffice.

Я добавил Insync в автозагрузку.

Источники:
http://prostolinux.ru/kak-ustanovit-google-disk-v-linux/
http://ubuntovod.ru/soft/insync.html

Автор: Sergey Bolshakov

О сборке мусора, деструкторах и разных питонах

В этом посте я писал почему работа с файлами и другими объектами, требующими гарантированного закрытия должна должна производиться через with. Однако кроме минуса в виде добавления в код лишнего уровеня вложенности with еще и решает только часть проблемы — если код обработки файла не локален (нужно возвращать дескриптор в вызывающий код или хранить неопределенное время) with не может помочь. И собственно никто вообще не может помочь — суровая реальность состоит в том, что python не гарантирует вызов деструктора объекта. Т.е. если вы работаете на CPython, и не создаете циклических ссылок, то за крайне редкими исключениями деструктор будет вызываться вовремя. Но если вы используете ironpython/jython/pypy то ситуация становится совсем печальна.

Для тех кто, вдруг, не в курсе — немного про С++, как пример удобной для программиста реализации деструкторов. С++ гарантирует вызов деструктора у объекта по его уничтожению чтобы не произошло (за исключением полного краха программы/пропадания питания/конца света/etc). Уничтожение наступает либо по выходу из блока в котором определена переменная, либо по удалению объекта с помощью оператора delete при выделении объекта в куче.

    // C++
{
// open file
std::fstream fs(fname, std::ios_base::out);
process_file(fs);
} // file is closed before we get beyong this line, no matter what happened

Гарантированный вызов деструктора — великое программистское благо, позволяющее не заботится о освобождении некоторых ресурсов, не загромождать код всякими with/using/try-finally & Co, и даже для объектов в куче есть всякие unique_ptr. Но все это хорошо работает только в том случае, если объект имел некую локальную область жизни(впрочем unique_ptr/shared_ptr могут и больше). Если же объект выделяется из кучи в одном месте, а освобождается в другом то можно забыть сделать ему delete — получаем утечку памяти. Не смотря на множество способов значительно сократить вероятность такого исхода (например арены) полностью исключить его нельзя.

В качестве решения этой проблемы в современных языках используются сборщики мусора. Периодически они проходятся по памяти, и тем или иным способом удаляют неиспользуемые объекты. Все бы хорошо, но у сборщиков мусора возникают небольшие или большие проблемы с вызовами деструкторов у объектов. Во-первых все сборщики мусора бессильны перед циклическими ссылками. Если объект a ссылается на b, а b ссылается на a, то не понятно в каком порядке вызывать деструкторы. Сначала у a или сначала у b. Если сначала у a, то при вызове деструктора b его ссылка на a будет не валидна и наоборот. Отсутствие информации о смысле взаимосвязей между объектами не дает сборщику мусора вызвать деструкторы в корректном порядке. Копирующие сборщики мусора пошли еще дальше. Они вообще ничего не вызывают, оставляя программиста один на один с этой проблемой и гордо подписываясь «современный сборщик мусора».

Проблема, очевидно, состоит в том что оперативная память это не единственный ресурс требующий освобождения. Еще, как минимум, есть объекты OS, мютексы, транзакции БД, и много много другого. Часть из таких объектов будет через время прикрыта другим кодом (например транзакции БД — но в любом случае они будут создавать лишнюю нагрузку на базу все это время), но объекты OS останутся с процессом до его смерти. А ведь бОльшая часть таких объектов имею локальную область видимости и при гарантированном вызове деструктор был бы идеальным местом для их освобождения. Таким образом переходя от С++ к языкам со сборкой мусора но с недетерменированным вызовом деструкторов мы выигрываем в коде освобождения памяти, но проигрываем на других объектах. Теперь вместо delete «где-то там» вы должны написать dispose/using/with/try-finally прямо тут на каждый объект. Впрочем если файл, например, является не локальным, то и это не поможет. Для примера можно открыть Экслера и глянуть как в яве правильно работать с файлами. Страница ужасного кода ради одного маленького файлика. Не уверен, что такая сборка мусора того стоила.

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

Без подсветки синтаксиса

import gc
import sys

class DestTest(object):
def __init__(self, val):
self.val = val

def __del__(self):
sys.stdout.write(str(self) + '.__del__()n')

def __str__(self):
return "DestTest({})".format(self.val)

def __repr__(self):
return "DestTest({})".format(self.val)

def simple_var():
d = DestTest("simple var")

def mdeleted_var():
d = DestTest("manyally deleted var")
del d

def simple_list():
a = [DestTest("simple list")]

def internal_exc():
try:
d = DestTest("exception_func")
raise IndexError()
except:
pass

def exception_func():
d = DestTest("exception_func")
raise IndexError()

def self_ref_list():
a = [DestTest("self-ref list")]
a.append(a)

def cycle_refs():
d1 = DestTest("cycle_ref_obj1")
d2 = DestTest("cycle_ref_obj2")
d3 = DestTest("free_obj")

d1.ref = d2
d2.ref = d1
d2.ref2 = d3

simple_var()
sys.stdout.write("after simple varn")
sys.stdout.write("n")

simple_list()
sys.stdout.write("after simple listn")
sys.stdout.write("n")

mdeleted_var()
sys.stdout.write("after manually deleted varn")
sys.stdout.write("n")

self_ref_list()
sys.stdout.write("after self ref listn")
gc.collect()
sys.stdout.write("after gc.collect()n")
sys.stdout.write("n")

internal_exc()
sys.stdout.write("after internal excn")

try:
exception_func()
except Exception as x:
pass
sys.stdout.write("after exception funcn")
gc.collect()
sys.stdout.write("after gc.collect()n")
try:
sys.exc_clear()
except AttributeError:
pass
else:
sys.stdout.write("after sys.exc_clear()n")
sys.stdout.write("n")

cycle_refs()
sys.stdout.write("after cycle refsn")
gc.collect()
sys.stdout.write("after gc.collect()n")
sys.stdout.write("n")

d = DestTest("module var")

import gc
import sys

class DestTest(object):
def __init__(self, val):
self.val = val

def __del__(self):
sys.stdout.write(str(self) + '.__del__()n')

def __str__(self):
return "DestTest({})".format(self.val)

def __repr__(self):
return "DestTest({})".format(self.val)

def simple_var():
d = DestTest("simple var")

def mdeleted_var():
d = DestTest("manyally deleted var")
del d

def simple_list():
a = [DestTest("simple list")]

def internal_exc():
try:
d = DestTest("exception_func")
raise IndexError()
except:
pass

def exception_func():
d = DestTest("exception_func")
raise IndexError()

def self_ref_list():
a = [DestTest("self-ref list")]
a.append(a)

def cycle_refs():
d1 = DestTest("cycle_ref_obj1")
d2 = DestTest("cycle_ref_obj2")
d3 = DestTest("free_obj")

d1.ref = d2
d2.ref = d1
d2.ref2 = d3

simple_var()
sys.stdout.write("after simple varn")
sys.stdout.write("n")

simple_list()
sys.stdout.write("after simple listn")
sys.stdout.write("n")

mdeleted_var()
sys.stdout.write("after manually deleted varn")
sys.stdout.write("n")

self_ref_list()
sys.stdout.write("after self ref listn")
gc.collect()
sys.stdout.write("after gc.collect()n")
sys.stdout.write("n")

internal_exc()
sys.stdout.write("after internal excn")

try:
exception_func()
except Exception as x:
pass
sys.stdout.write("after exception funcn")
gc.collect()
sys.stdout.write("after gc.collect()n")
try:
sys.exc_clear()
except AttributeError:
pass
else:
sys.stdout.write("after sys.exc_clear()n")
sys.stdout.write("n")

cycle_refs()
sys.stdout.write("after cycle refsn")
gc.collect()
sys.stdout.write("after gc.collect()n")
sys.stdout.write("n")

d = DestTest("module var")

В идеальном мире вызов деструктора у объектов класса DestTest во всех этих функциях должен происходить до выхода из соответствующей функции. Итак что получается:

python2.7

    DestTest(simple var).__del__()
after simple var

DestTest(simple list).__del__()
after simple list

DestTest(manyally deleted var).__del__()
after manually deleted var

after self ref list
DestTest(self-ref list).__del__()
after gc.collect()

after exception func
after gc.collect()
DestTest(exception_func).__del__()
after sys.exc_clear()

after cycle refs
after gc.collect()

Exception AttributeError: "'NoneType' object has no attribute 'stdout'" in
ignored

Более-менее. Деструктор у циклических ссылок не был вызван, как и ожидалось. Для уничтожения объектов, связанных с исключением, дошедшем до уровня модуля приходится вызывать sys.clear_exc(), в остальных случаях с исключениями все ок. Интересно, что питон освободил sys.stdout раньше, чем переменную d, в итоге чего ее деструктор отработал не корректно (впрочем это поведение не всегда повторяется).

python3.3

    DestTest(simple var).__del__()
after simple var

DestTest(simple list).__del__()
after simple list

DestTest(manyally deleted var).__del__()
after manually deleted var

after self ref list
DestTest(self-ref list).__del__()
after gc.collect()

DestTest(exception_func).__del__()
after exception func
after gc.collect()

after cycle refs
after gc.collect()

Exception AttributeError: "'NoneType' object has no attribute 'stdout'" in
ignore

Почти то-же самое, что и 2.7, только sys.exc_clear() больше не нужно.

ironpython2.7

    after simple var

after simple list

after manually deleted var

after self ref list
DestTest(self-ref list).__del__()
DestTest(manyally deleted var).__del__()
DestTest(simple list).__del__()
DestTest(simple var).__del__()
after gc.collect()

after exception func
DestTest(exception_func).__del__()
after gc.collect()
after sys.exc_clear()

after cycle refs
DestTest(free_obj).__del__()
DestTest(cycle_ref_obj2).__del__()
DestTest(cycle_ref_obj1).__del__()
after gc.collect()

DestTest(module var).__del__()

Удаляет все, но только при сборке мусора, до те
х пор все объекты живут где-то в памяти.

И — встречаем победителя. Сама лаконичность или мир всем вашим деструкторам от нашей Java и копирующего сборщика мусора: jython2.7a2 — Java HotSpot(TM) Client VM (Oracle Corporation) on java1.7.0_07

    after simple var

after simple list

after manually deleted var

after self ref list
after gc.collect()

after exception func
after gc.collect()
after sys.exc_clear()

after cycle refs
after gc.collect()

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

А вывод все тот-же. По возможности — используйте with. По невозможности — попробуйте поправить код, так что-бы можно было использовать with. Иначе — аккуратно вызывайте деструкторы руками

P.S. Как я люблю, когда мне предлагают делать какую-то рутинную работу в коде «аккуратно».

Ссылки:
          koder-ua.blogspot.com/2012/10/python-with.html
          en.wikipedia.org/wiki/Region-based_memory_management

Исходники этого и других постов со скриптами лежат тут — github.com/koder-ua. При использовании их, пожалуйста, ссылайтесь на koder-ua.blogspot.com.

Автор: konstantin danilov