OMarchenko
@OMarchenko
Random Expansion

Как в Python корректно использовать алгоритм бинарного поиска?

Помогите чайнику, пожалуйста.
Задача на простейшие алгоритмы, из средств Python используются только циклы. Понятно, что можно это сделать проще, но хочется разобраться в бинарном поиске и потом сравнить время работы этого алгоритма с линейным поиском.
Требуется произвести подсчет числа прописных букв в тексте (файл Source.txt). Приведенный ниже код где-то в циклах подвисает. Как его исправить?
AllCapitalLetters = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ' # Строка из всех прописных букв русского алфавита
CapitalInTEXT = []
myfile = open(r'c:\My_Scripts_Macros_and_Progs\Python\34\AnalyseOfText\Source.txt')
TEXT = myfile.readlines()  # Считывает содержимое файла, возвращает список строк
STR_TEXT = " ".join(TEXT)  # Сливает список в строку
k = 0  # Обнуляем переменные
i = 0  # первый элемент
j = len(AllCapitalLetters) - 1  # последний элемент
m = int((i + j) / 2)  # середина (приблизительно)
for k in STR_TEXT:
    while k != AllCapitalLetters[m] or i > j:
        m = int((i + j) / 2)  # найти новую середину
        if k > AllCapitalLetters[m]: # если значение больше серединного
            i = m + 1  # то сместить левую границу за середину
        else:  # иначе
            j = m - 1  # переместить правую границу до середины

    if i > j:
        None
    else:
        CapitalInTEXT.append(AllCapitalLetters[m])  # Добавить в список найденное значение

print(CapitalInTEXT)  # Вывести список
print(len(CapitalInTEXT))  # Вывести длину списка

P.S. Прототип алгоритма взят отсюда.
  • Вопрос задан
  • 2601 просмотр
Решения вопроса 1
bobrovskyserg
@bobrovskyserg
Вижу несколько разных вопросов:
Как произвести подсчет числа прописных букв в тексте просто?
Как произвести подсчет числа прописных букв в тексте быстро?
Что за хрень я написал и почему она не работает?

#  просто и быстро
STR_TEXT = "Требуется произвести подсчет числа прописных букв в тексте."
AllCapitalLetters = set("АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ")
CapitalInTEXT = [c for c in STR_TEXT if c in AllCapitalLetters]
print(CapitalInTEXT)
print(len(CapitalInTEXT))

С латиницей прокатил бы такой вариант:
STR_TEXT = "CapitalInTEXT = [c for c in STR_TEXT if 'A' <= c <= 'Z']"
CapitalInTEXT = [c for c in STR_TEXT if 'A' <= c <= 'Z']

С кириллицей так не выйдет: в юникоде, например
In [1]: ''.join(chr(i) for i in range(1025, 1072))
Out[1]: 'ЁЂЃЄЅІЇЈЉЊЋЌЍЎЏАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
в других кодировках по-другому.

Чтож, попрактикуемся в бинарном поиске:
AllCapitalLetters = 'ЁАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
# обрати внимание на порядок букв
# на неотсортированном AllCapitalLetters алгоритм виснет
CapitalInTEXT = []
for c in STR_TEXT:
    i = 0
    j = len(AllCapitalLetters) - 1
    while i <= j:
        m = (i + j) // 2
        cm = AllCapitalLetters[m]
        if c > cm:
            i = m + 1
        elif c < cm:
            j = m - 1
        else:
            CapitalInTEXT.append(cm)
            break

Вместо самописа можно воспользоваться стандартной библиотекой:
from bisect import bisect_left

AllCapitalLetters = 'ЁАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
CapitalInTEXT = []
for c in STR_TEXT:
    idx = bisect_left(AllCapitalLetters, c)
    if idx < len(AllCapitalLetters) and c == AllCapitalLetters[idx]:
        CapitalInTEXT.append(c)


По быстродействию простой вариант в 8 раз лучше варианта с bisect и 24 раза лучше самописного.
На этой задаче бинарный поиск бесполезен. А полезен он, например, при поиске ближайших соседей испытуемой буквы, которой в AllCapitalLetters нет, напр. буквы "Ї".
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
STLEON
@STLEON
In Console We Trust. Code hard. Or die.
Какой-то у тебя большой бинарный поиск. Посмотри на мой omgit.ru/blog/binary-search
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы