Метка: Поиск

Формирование списка файлов, содержащих запрос

Очередная тренировка работы с кодировками, поиском слов. И немного про пути к файлам (os, os.path), есть пример использования исключений (try, except).

# Задание
# мне нужно отыскать файл среди десятков других
# я знаю некоторые части этого файла (на память или из другого источника)
# я ищу только среди .sql файлов
# 1. программа ожидает строку, которую будет искать (input())
# после того, как строка введена, программа ищет её во всех файлах
# выводит список найденных файлов построчно
# выводит количество найденных файлов
# 2. снова ожидает ввод
# поиск происходит только среди найденных на этапе 1
# 3. снова ожидает ввод
# ...
# Выход из программы программировать не нужно.
# Достаточно принудительно остановить, для этого можете нажать Ctrl + C

# Пример на настоящих данных

# python3 find_procedure.py
# Введите строку: INSERT
# ... большой список файлов ...
# Всего: 301
# Введите строку: APPLICATION_SETUP
# ... большой список файлов ...
# Всего: 26
# Введите строку: A400M
# ... большой список файлов ...
# Всего: 17
# Введите строку: 0.0
# Migrations/000_PSE_Application_setup.sql
# Migrations/100_1-32_PSE_Application_setup.sql
# Всего: 2
# Введите строку: 2.0
# Migrations/000_PSE_Application_setup.sql
# Всего: 1

# не забываем организовывать собственный код в функции

import os
import chardet

migrations = 'Migrations'
current_dir = os.path.dirname(os.path.abspath(__file__))

def all_list(): 
    'Формируем полный список файлов'
    migrations_dir = os.path.join(current_dir, migrations)
    file_list = os.listdir(path=migrations_dir)
    return file_list
    
def sql_list(all_list): 
    'Функция для отбора sql-файлов'
    sql_file_list = list() # пустой список sql-файлов
    for i in all_list:
        if i.endswith('.sql'):
            sql_file_list.append(i)
    return sql_file_list

def decode_files(file_name):
    'Раскодирует файл, возвращает содержимое в читаемом виде'
    with open(os.path.join(current_dir, migrations, file_name), 'rb') as f:
        data = f.read()
        result = chardet.detect(data)
        data = data.decode(result['encoding'])
        data = data.lower()
    return data
    
def search_string(sql_list):
    'Главная функция: ищет запрашиваемую строку в файлах, список при каждом запросе сужается'
    file_list = sql_list
    while True: 
        search = input('Введите строку (регистр не важен): ') 
        search = search.lower()
        containing_files = list() # пустой список файлов для формирования сужающегося списка
        for file_name in file_list: 
            if search in decode_files(file_name):
                containing_files.append(file_name)
                print(file_name)
        print('Всего: {}'.format(len(containing_files)))
        file_list = containing_files

if __name__ == '__main__':
    search_string(sql_list(all_list()))
            
    pass

 

Бинарный поиск

bool search(int value, int values[], int n)
{
    // смотрим кол-во элементов в массиве, если деление на %2 дает остаток 0, значит, четное кол-во
    // иначе нечетное. Если четное - делим отсортированный массив на 2, смотрим последний элемент в левой части. Сравниваем с искомым.
    // Если нечетное, то вычитаем 1 элемент, делим на 2, смотрим последний элемент в левой части +1.
    // search(needle, haystack, size), где 1 - то, что ищем в массиве; 2 - массив; 3 - размер массива

    int a = 0; //начало массива
    int b = n-1; // конец массива
    int m = b-a; // длина выбранной части массива
    int centr, levo, pravo, i;
    int aa=values[0];
    int bb=values[n-1];
    
   if (aa<=value && bb>=value) 
   {
    do
    {
        float j = m%2; //для определения четного или нечетного
        if (j==0) //если нечетное кол-во элементов в массиве
        {
            centr = (b-a)/2+a;
            if (values[centr]>value)
            {
                b=centr-1;
            }
            else if ((values[centr]<value))
            {
                a=centr+1;
            }
            else return true;
        }
        else // если четное кол-во элементов в массиве
        {
            levo = (b-a+1)/2+a-1;
            pravo = (b-a+1)/2+a;
            if (values[levo]>=value)
            {
                b=levo;
            }
            else
            {
                a=pravo;
            }
        }
        m = b-a;
    
    printf("\na=%i b=%i\n", a, b);
    for (i=a;i<=b;i++)
    {
        printf("%i\n",values[i]);
    }
    
    }
    while (m!=0);
    
// запускаем последний этап проверки, т.к. если остался 1 элемент в конце m может быть равным 0 и цикл закончится

    if (values[a]==value) return true;
    else return false;
       
   }  else return false;
}

 

Линейный поиск

bool search(int value, int values[], int n)
{
// search(needle, haystack, size), где 1 - значение из командой строки, которую ищем в стоге; 2 - массив; 3 - размер массива, номер элемента в массиве
    int i;
    if (n<=0) return false;
    else
    {
        for (i=0; i<n; i++)
        {
            if (value == values[i]) return true;
        }
    }
    return false;
}