Страницы

Поиск по вопросам

Показаны сообщения с ярлыком поиск. Показать все сообщения
Показаны сообщения с ярлыком поиск. Показать все сообщения

четверг, 9 апреля 2020 г.

Java автодополнение в консоли используя статистику списка слов

#java #сортировка #поиск #консоль

                    
Цель - создание консольного Линукс/Win приложения с автодополнением текста используя
файл статистики слов. 

Пример файла статистики:

бумага 223
утро 114
утюг 513
уран 22
тепло 144


Всего около 100000+ слов

Какой наилучший алгоритм для поиска и как лучше отсортировать считанные с файла слова
с их статистикой?

Я думаю записать слова для каждой первой буквы в отдельный список List типа ключ-значение
(SortedMap-TreeMap?) с сортировкой по значению, и разместить те списки в ArrayList.
Когда пользователь начинает писать слово, список с его соответственный его первой букве
сканируется на подходящие слова и они выдаются с сортировкой по значению. Это хороший
способ? как практически лучше это написать, используя что из коллекций и какой алгоритм?
    


Ответы

Ответ 1



Собственно есть два быстрых пути. Можно реализовать, перенеся твой справочник в таблицу БД create table dictonary (word Varchar(30) primary key, cost integer not null) Тогда поиск будет сводиться к select word from dictonary where word like 'начало_твоего_слова%' order by cost desc Встроенные базы довольно шустрые (H2, HSQLDB) Но если тебе надо использовать только java, то используй TreeMap. Только для начала оговоримся, что все твои слова должны содержать только русские буквы (привет кэп), и желательно только нижнего регистра. Далее остается использовать метод subMap, но с одной хитростью. Если ты ищешь слова начинающиеся с бу, то тебе надо передавать параметры в submap в виде бу\u040f (в конце символ, код которого меньше кода первой буквы алфавита) и бу\u0450 (в конце символ, код которого больше кода последней буквы алфавита). Хитрость, но работает. Плюс тебе придётся сортировать результат, согласно статистике повторений слова.

понедельник, 30 марта 2020 г.

Регулярное выражение поиск от и до. Notepad++

#регулярные_выражения #поиск #замена


Есть такой код:

{
version 0
1.000000
0.835000
0.190000
}
{
version 1
    diffuse_cube = diffuse.dds
    specular_cube = Art.dds
    hor_angle = 3.141590
    vert_angle = 0.364425
    env_brightness = 0.21
    attenuation = 0.0357142857142857
    water = 0.107142857142857
}
false
0.004015
""
1
    "FogExp" "-346.250000 2817.500000 0.133250 4.123750 0.391750 0.325000 0.325000 "
false

{
version 0
1.000000
0.835000
0.190000
}

{
version 1
    iveness = 0.050000
    wind = 0.226195
    swell = 0.400000
    period = 0.046286
}


Задача найти и удалить все блоки version 1

{
version 1
}


Исключая блоки version 0

{
version 0
}


Пока что дошел до такого выражения:
"version 1.*?[}]"
Но мне надо также захватить и верхнюю фигурную скобку.
Код в блоках может быть совершенно разным, но "version 1" всегда есть.
    


Ответы

Ответ 1



Попробуйте — \{\Rversion 1[^\}]*\}

суббота, 21 марта 2020 г.

QtС++. Доработать поиск файлов в директории и поддиректориях

#cpp #алгоритм #qt #qt5 #поиск


Есть код:

 // Получение списка файлов в папке
    QStringList nameFilter;
        QDir dir(MTEPathTMP);
        nameFilter.clear();
        nameFilter << "*.png";

        QFileInfoList list = dir.entryInfoList( nameFilter, QDir::Files );
        QFileInfo fileinfo;

        nameFilter.clear();
        foreach (fileinfo, list) nameFilter << fileinfo.absoluteFilePath();


Он ищет файлы по маске в директории.

НО! Он не умеет смотреть в поддиректории. Как можно его доработать, чтоб он мог искать?
    


Ответы

Ответ 1



Уже обсуждалось тут. Я бы рекомендовал не изобретать велосипед с рекурсивной функцией, а применить готовый класс QDirIterator со специальным флагом в параметрах. QDirIterator it("/sys", QStringList() << "scaling_cur_freq", QDir::NoFilter, QDirIterator::Subdirectories); while (it.hasNext()) { QFile f(it.next()); f.open(QIODevice::ReadOnly); qDebug() << f.fileName() << f.readAll().trimmed().toDouble() / 1000 << "MHz"; }

Поиск “скрытой” подстроки в строке

#алгоритм #строки #поиск #подстрока


Надо узнать если ли в строке "раздробленная" подстрока.
Пример:

У нас имеется строка и предпологаемая подстрока, надо просто вывести true или false
если такая трока имеется
    


Ответы

Ответ 1



string a, b; cin >> a >> b; int bIndex=0; for (size_t i = 0; i < a.size(); i++) { if (b[bIndex] == a[i]) { bIndex++; } } if (bIndex==b.size()) { cout << "YES"; } else { cout << "NO"; }

четверг, 19 марта 2020 г.

Поиск пути на карте.

#поиск #пути


Понабилось мне, значит, такая штука, как поиск путей на полу-статической карте. 
Ясен пень первым делом пошел в поиск. Много чего интересного, но как-то слишком муторно
всё. Хотя думаю есть и более простые алгоритмы, но я дальше не пошел и решил сам поумничать. 
Нарисовал вот такую карту (кстати, все картинки кликабельны ;-) ):

Как видно, карта ограничена определенными размерами и на ней есть закрашенные многоугольники
- ака "непроходимые места". Также на карту нанесены графы. Графы служат основным путем,
к которому и будет цепляться наш "проходимец". 
Так вот, допустим есть пример:

Как я представляю работу алгоритма:

строим прямую от начальной точки до конечной точки (через всю карту, поверх непроходимых
мест, коричневая линия)
ищем точку, которая находится на прямой (коричневой), до пересечения объекта. Переходим
на неё.
От полученной точки рисуем прямую по принципу первого пункта. Ищем точку по принципу
второго пункта.
Зацикливаем.
Если мы стоим на точке, от которой до финиша нет препятствий, то проводим прямую линию. 

(Проблема 1) Вроде всё легко и просто. Но прикол в том, что точка, на которую мы
перемещаемся, может быть близко, но путь длинее. А чуть дальше будет точка, которая
дальше, но через неё путь короче. 
Как вариант думаю - перебирать все пути до конечной цели и сравнивать их длину, но
чото мне стремно становится от такого дела. 
(Проблема 2) Плюс на карте будет присутствовать такая штука, как "переменная проходимость"
через непроходимые места, т.е.:

Собственно у меня тоже есть некоторые мысли, но они требуют доработки по существующим
проблемам. Добавлю то, что на карте не будет непроходимых мест (т.е. не получится застрять
в каком-нибудь квадрате с внутренним вырезом, из которого нельзя выйти).
Более просто: хотелось бы услышать мнения по улучшению существующего находа пути
+ идеи по решению проблемы 1 и 2.     


Ответы

Ответ 1



Я бы порекомендовал A*. Он должен перекрывать по производительности алгоритм Дейкстры. Исходя из дискуссии в комментариях, должен подходить.

Ответ 2



Я года 2 назад столкнулся с такой же проблемой когда делал игру, и сам написал алгоритм для поиска пути, потом я узнал что он называется волновой. Надеюсь поможет.

понедельник, 9 марта 2020 г.

Регулярные выражения. Поиск слов по набору букв

#регулярные_выражения #поиск


Помогите составить регулярное выражение для поиска слов только по определённому набору
букв. Т.е. Есть слово "зажигалка" в результате в искомых словах могут использоваться
только буквы из этого слова и в том же количестве.

Нужно найти все слова, состоящие из этих букв. Т.е. "глаз", "газ", "галка" и т.д.
В общем, как в игре "Слова из слова"
    


Ответы

Ответ 1



Если речь о перестановке букв, то: ^(?=.*з)(?=.*а.*а.*а)(?=.*ж)(?=.*и)(?=.*г)(?=.*л)(?=.*к)[зажиглк]{9}$ Если речь просто о подмножестве, то так: ^(?!.*з.*з)(?!.*а.*а.*а.*а)(?!.*ж.*ж)(?!.*и.*и)(?!.*г.*г)(?!.*л.*л)(?!.*к.*к)[зажиглк]+$

Ответ 2



условие «в том количестве» (точнее, как понятно из комментария к другому ответу, «в количестве, не большем заданного») с помощью известных мне стандартов регулярных выражений выполнить невозможно. если, конечно пользоваться только движком регулярных выражений, без дополнительного кода (см. ниже). если условие про количество опустить и если слова идут по одному в строке, то, например, так: $ echo -e 'глаз\nгаз\nмозг\nгалка' | grep '^[зажигалка]\+$' глаз газ галка под дополнительным кодом я имею ввиду: преобразование искомой строки в отсортированный список букв с квантификатором количества для букв, встречающихся более одного раза. например: зажигалка преобразовать в ^а{1,3}?г?ж?з?и?к?л?$ (или чуть по-другому, только с квантификаторами количества и без квантификатора ?: ^а{0,3}г{0,1}ж{0,1}з{0,1}и{0,1}к{0,1}л{0,1}$) преобразование слова на входе в отсортированный список букв. например: мозг → гзмо, глаз → агзл, заза → аазз. если такие преобразования выполнить, то движок, понимающий bre (basic regular expressions), вполне справится: $ echo -e 'гзмо\nагзл\nаазз' | grep '^а\{1,3\}\?г\?ж\?з\?и\?к\?л\?$' агзл пример выполнения описанных преобразований средствами posix-утилит: преобразование исходного слова в регулярное выражение bre: $ echo 'зажигалка' | sed 's/./&\n/g;s/.$//' | sort | uniq -c | \ sed -r 's/\s*([0-9]+)\s*(.*)/\2\\{0,\1\\}/;1s/^/^/;$s/$/$/' | \ sed ':a;N;s/\n//;ta' ^а\{0,3\}г\{0,1\}ж\{0,1\}з\{0,1\}и\{0,1\}к\{0,1\}л\{0,1\}$ сортировка букв: $ echo 'глаз' | sed 's/./&\n/g;s/.$//' | sort | sed ':a;N;s/\n//;ta' агзл обновление: в своём ответе Qwertiy продемонстрировал, что без второго из описанных мною преобразований можно обойтись, если использовать стандарт pcre (perl compatible regular expressions), в котором есть функция предпросмотра (look-ahead). первое преобразование в таком случае может быть сделано средствами posix-утилит, например, так: $ w='зажигалка'; echo $w | sed 's/./&\n/g;s/.$//' | sort | uniq -c | \ sed -r 's/^\s*([0-9]+)\s*(.)$/echo \\(?!\\(.*\2\\)\\{$((\1+1))\\}\\)/e;1s/^/^/;$s/$/['$w']+$/' | \ sed ':a;N;s/\n//;ta' ^(?!(.*а){4})(?!(.*г){2})(?!(.*ж){2})(?!(.*з){2})(?!(.*и){2})(?!(.*к){2})(?!(.*л){2})[зажигалка]+$ полученное регулярное выражение работает корректно: $ echo -e 'мозг\nглаз\nзаза' | grep -P '^(?!(.*а){4})(?!(.*г){2})(?!(.*ж){2})(?!(.*з){2})(?!(.*и){2})(?!(.*к){2})(?!(.*л){2})[зажигалка]+$' глаз

вторник, 25 февраля 2020 г.

Как составить предложение из букв, введенных пользователем?

#php #алгоритм #математика #поиск


На вход программе подаётся набор английских букв. Имеется словарь из слов.

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

Пример

Входящий набор символов: hellomyfriend

Вывод программы:

Feed Hilly Morn
Feed Hilly Norm
Feed Horny Mill
Freehold Nil My
Refilled Hon My
Defiler Hymn Lo
и т.д.




Выбрать слова которые удовлетворяют входному набору символов у меня получилось. А
вот быстро составлять из них предложения не получается.

Я делал методом перебора всех слов. Для фразы myfavoritegame скрипт отрабатывал около
5 минут. На сайте предложения отдаются мгновенно.

Можете что-нибудь посоветовать?
    


Ответы

Ответ 1



Предположим, вам нужно просто найти все возможные комбинации слов из данного словаря, удовлетворяющие условию. Не отвлекаясь на особенности именно языка. Важно для поиска: наличие букв в слове. Исключаем содержащие буквы вне заданных. Исключаем, по мере составления фразы, уже использованные. считаем буквы. В любой момент составления фразы известно, слова какой длины подходят, или точно не подходят. повторы букв. Не важно: порядок букв в словарном слове. смысл слова. Для скорости нужно сделать поиск по важным признакам максимально быстрым, при необходимости убрав неважные аспекты. Для быстрого нахождения слов с подходящим набором букв, но без учёта повторов, можно сделать битный индекс, как предложил @Mirdin: 26 букв английского алфавита = 26 бит. Пронумеровать слова в словаре (или просто индексом считать номер строки) и составить отдельный индекс в две колонки: id слова - битовая маска имеющихся букв. Для словаря меньше 65 тыс. слов, такой индекс будет "весить" 6 байт на слово, менее 400k. Можно держать в оперативной памяти для почти-мгновенного поиска. Так можно быстро найти например, первое слово фразы – просто, чтобы точно были выключены биты "лишних" букв. Стоит сделать копию словаря, где буквы слова отсортированы по алфавиту, и слова отсортированы по алфавиту. Т.е. опять отдельный индекс: сортированные_буквы - id_слова. Этот индекс будет тяжелее самого словаря на (число слов * 2 или 3 байта). В этом индексе можно быстро находить подходящие слова и отбрасывать точно-неподходящие. Алгоритм примерно такой. Ищем первое слово. Хочется найти первое же слово наибольшей возможной длины. Перебор по длине, от большего к меньшему. Ест допустимый набор букв и длина. Нашли первое слово, обновили допустимый набор букв и длины слов – ищем следующее слово.

Ответ 2



Делаете структуру (таблицу в БД, хеш-таблица, словарь и тд что там есть в пхп) из двух полей на запись: хэш и собственно говоря слово. Забиваем эту структуру словами. Хэш примерно делается так: индекс буквы в алфавите - степень двойки, все буквы слова складываем (32 бит для русского языка должно хватить). Это простейший вариант, возможно будет необходимо придумать более сложную функцию. Получив слово которое надо заанаграмить - вычисляем его хэш и ищем по нему в нашей структуре UPD: Это для одного слова, с фразами будет сложнее, но принцип тот же

пятница, 14 февраля 2020 г.

Поиск максимальной суммы квадратов чисел

#python #алгоритм #поиск


Требуется найти максимальную сумму квадратов двух натуральных чисел, которая будет
близка(или равна) к заданному числу.  

Примеры: 


  20 -> 20  т.к. (42 + 22)
  50 -> 50  т.к. (52 + 52 или 72 + 12)
  30 -> 29  т.к. (52 + 22)


Не пойму, почему моя программа неверна.

res = int((N)**0.5)
res1 = int(((N-res**2)**0.5))
print(res**2+res1**2)

    


Ответы

Ответ 1



Ваше решение неверное так как int(N**.5)**2 не обязан быть одним из слагаемых в сумме. К примеру, 18 = 32 + 32, а ваше решение возвращает 17 = 42 + 12 для N=18 (17 < 18 поэтому это не является наибольшей суммой квадратов чисел близких к N). Помимо перебора, можно построить решение на основе теоремы о сумме двух квадратов, из которой следуют разрешённые варианты разложения числа на простые множители — целое число m > 1 является суммой квадратов тогда и только тогда когда у него нет простых множителей вида 4*n+3 в нечётной степени: def is_sum_of_two_squares(m): p = 2 while m > 1: multiplicity = 0 while m % p == 0: # found prime factor multiplicity += 1 m //= p if multiplicity & 1: # odd power if p % 4 == 3: # 4*n+3 form return False p += 1 return True Имея способ определить является ли натуральное число суммой квадратов, можно найти наибольшую сумму близкую к числу, перебирая рядом стоящие числа (от близких к далёким, от больших к маленьким числам): def max_sum_of_two_squares_nearest(m): for i in range(m + 1): if is_sum_of_two_squares(m + i): return m + i elif is_sum_of_two_squares(m - i): return m - i assert 0 Пример: for m in range(21): print(m, "->", max_sum_of_two_squares_nearest(m)) Результат 0 -> 0 1 -> 1 2 -> 2 3 -> 4 4 -> 4 5 -> 5 6 -> 5 7 -> 8 8 -> 8 9 -> 9 10 -> 10 11 -> 10 12 -> 13 13 -> 13 14 -> 13 15 -> 16 16 -> 16 17 -> 17 18 -> 18 19 -> 20 20 -> 20

Ответ 2



Ваша программа неверна потому что она рассматривает только один случай. Так, 89 = 64 + 25 но ваша программа найдет только 85 = 81 + 4. Вместо "жадного" выбора первого числа по формуле int((N)**0.5) правильнее будет перебрать все варианты от 0 до int((N)**0.5) и выбрать среди них наилучший. Формулу для второго числа можете оставить ту же самую.

Ответ 3



Вот моё решение на Питоне, перебирает меньшее из двух чисел в отрезке [1, sqrt(n)] а второе вычисляет по формуле, находит все ответы для максимальной из найденных сумм, для максимального числа 10^9 отрабатывает алгоритм мгновенно. Вот код на Питоне, можно запустить онлайн: n = 1000000000 sqrt_n = int(n ** 0.5) max_sum = 0 result = [] for i in range(1, sqrt_n + 1): j = int((n - i * i) ** 0.5) if j < i: break s = i * i + j * j if (s > max_sum): max_sum = s result = [] if (s == max_sum): result.append((i, j)) print(max_sum, result) Вот какой вывод для примера 10^9: 1000000000 [(1200, 31600), (7696, 30672), (10000, 30000), (18000, 26000), (19920, 24560)]

Ответ 4



Предполагая, что Вам таки не важно(могу ошибаться) в какие именно суммы разложимо число, предлагаю решение полным перебором до sqrt(N): from math import sqrt x = int(input()) def check(x): sn = int(sqrt(x))+1 for i in range(1, sn): j = int(sqrt(x - i*i)) if (i*i+j*j == x): # print("{0}^2 + {1}^2".format(i, j)) return True return False while x > 0: if check(x): print(x) break x = x - 1 if x == 0: print("Not found\n") 30 29 50 50 1000000000 1200^2 + 31600^2 1000000000 (4ms)

вторник, 28 января 2020 г.

Можно ли улучшить поиск в многомерном списке python

#python #python_3x #поиск #списки


Здравствуйте. Есть многомерный список:

spisok=[{'a':'1','b':'2'},{'a':'3','b':'4'}]


необходимо проверить есть ли в списке ключ 'a' с определенным значением.
поискав в интернете смог собрать такую конструкцию:

for i in range(len(spisok)):
    if spisok[i]['a'] == stroka_poiska:
        print('True')


Можно ли как то улучшить данный код? И верна ли логика построения алгоритма?
    


Ответы

Ответ 1



Попробуйте так: def chk_for_val(lst, key, val): for d in lst: if d.get(key) == val: return True return False При использовании dict.get(key) (вместо dict[key]) - не будут генерироваться исключения для несуществующих ключей In [138]: chk_for_val(lst, 'a', '3') Out[138]: True In [139]: chk_for_val(lst, 'X', '3') Out[139]: False

Ответ 2



Самый лучший вариант: check = any(dct.get('a')==stroka_poiska for dct in spisok) print(check) Лаконично, читабельно и эффективно.

Ответ 3



Предложу свой немного странноватый вариант: In [17]: array = [{'a':'1','b':'2'},{'a':'3','b':'4'}] In [18]: def search(dictionary, key, value): ...: verbose_data = sum(map(list, map(dict.items, dictionary)), []) ...: return (key, value) in verbose_data ...: In [19]: search(array, 'a', '1') Out[19]: True In [20]: search(array, 'a', '4') Out[20]: False Или: In [27]: search = lambda array, key, value: any(map(lambda x: (key, value) in x.items(), array)) In [28]: search(array, 'a', '1') Out[28]: True In [29]: search(array, 'A', '1') Out[29]: False Или: In [13]: from itertools import takewhile In [14]: def search(array, key, value): ...: return len(list(takewhile(lambda x: x.get(key) != value, array))) < len(array) ...: In [15]: search(array, 'a', '3') Out[15]: True In [16]: search(array, 'A', '3') Out[16]: False

Ответ 4



В стандартной библиотеке collections есть класс отображения ChainMap. Он хранит список отображений, так что их можно просматривать как единое целое. Поиск производится в каждом отображении по порядку и завершается успешно, если ключ найден хотя бы в одном. from collections import ChainMap spisok=[{'a':'1','b':'2'},{'a':'3','b':'4'}] chain = ChainMap(*spisok) print(chain.get('a')) документация

Ответ 5



Я вот так сделал: for i in range(len(spisok)): for key in spisok[i]: if spisok[i][key]=='4': print(spisok[i][key])

среда, 22 января 2020 г.

Как проверять слова Русского языка?

#разработка_игр #поиск #любой_язык #словари


Для игры типа «Эрудита» надо проверять, есть ли составленное игроком слово в словаре,
и соответствует ли оно требованиям: именительный падеж, единственное число.
Наверное, достаточно раздобыть текстовый файл со словами через разделитель, и в нём
искать. Кстати, может, есть некий формат, более удобный для поиска? Дерево, сортировка,
всё такое?
Основной вопрос — как расширить набор правил? Разрешить, например, все падежи, множественное
число, глаголы во всех временах.     


Ответы

Ответ 1



На мой взгляд, какого-то лёгкого или средней сложности способа вы врядли найдёте. Разве что, пропишите все возможные варианты в БД или файле. С падежами - проще. Можно было бы прописать корни слов и отдельно возможные суфиксы, окончания слов и т.д. Но и тут засада. Возьмём для примера слова "хэшкод" и "конь". Как проверить правильность написанных слов, если в дательном падеже первое слово будет "хэшкодУ", а второе - "конЮ"? Вопрос риторический. С глаголами и их временами ещё печальней. Берём: "ехать" и "идти". В неопределенном времени (1-е лицо) получаем "езжу" и "хожу". Тут даже логики не просматривается. Вывод: "Велик и могуч русский язык, но под PHP не заточен". P.S. Кстати, тут неподалеку есть еще один форум (Русский язык). Возможно, что там могут кое-что дельное подсказать.

Ответ 2



Я думаю стоит конвертировать словарь в отдельную SQL таблицу для каждой части речи: Например для имен существительных могут быть такие поля: ID, Приставка, Корень, Суффикс, Окончание, Падеж, Род, Все слово, Одушевлённость, Число(единственное множественнно),Склонение, Нарицательность, Это же слово по умолчанию(ед число именительный падеж) И далее просто делать SELECT к этой таблице. Другой вопрос как получить эту таблицу из текстового файла, придется писать очень нетривиальный парсер учитывающий морфологию.

воскресенье, 12 января 2020 г.

алгоритм поиска в массиве строк наиболее отличающуюся от первой

#cpp #массивы #алгоритм #поиск #сравнение


Я ищу наиболее быстрый алгоритм для поиска строки в массиве строк, которая сильнее
всего отличается от первой строки массива. Строки все одинаковой длины. Позиция символов
и их ASCII код имеет принципиальное значение. Если решать задачу в лоб, то нужно перебрать
каждую строчку массива и сравнить каждый ее символ с символом первой строки с тем же
индексом. Если они отличаются, то счетчик для этой строки массива увеличивается. Самый
большой счетчик дает нам строку, которая наиболее отличается от первой.
    


Ответы

Ответ 1



Можно использовать следующий алгоритм: std::vector strings ... std::vector distances; for(size_t i = 1; i < strings.size(); ++i) { std::deque tmp(strings[i].size()); for(size_t j = 0; j < tmp.size(); ++j) tmp[j] = static_cast(strings[i][j] == strings[0][j]); auto distance = count(begin(tmp), end(tmp), false); distances.push_back(distance); } auto idx = distance(begin(distances), max_element(begin(distances), end(distances))) + 1; auto result = strings[idx]; Этот код очень легко переписать под векторные инструкции и его скорость может вырасти многократно, но для этого надо знать размер строк(Вы его знаете, я — нет)

суббота, 11 января 2020 г.

Бинарный поиск интервала

#алгоритм #поиск


Есть массив 1 2 3 ... N. Известно, что этот массив можно разбить на три интервала
[1 2 .. .L-2 L-1], [L L+1 ... R-1 R], [R+1 R+2 ... N-1 N], (L<=R) так что каждый элемент
из своего интервала дает определенный результат в функции f. f(1)=f(2)=...f(L-1), f(L)=f(L+1)=...f(R).
f(R+1)=f(R+2)=...f(N).   

Как за logN (какой-нибудь модифицированный бинарный поиск) найти эти L и R?
    


Ответы

Ответ 1



Извиняюсь что на Джаве. public class App { public static void main(String[] args) { int[] arr = {1,1,2,2,2,2,3,3}; Interval interval = find(0, arr.length - 1, i -> arr[i]); System.out.println(interval); } static Interval find(int start, int finish, Function f) { int intStart = findStart(start, finish, f) + 1; int intEnd = findStart(intStart, finish, f); return new Interval(intStart, intEnd); } private static int findStart(int start, int finish, Function f) { int a = start; int b = finish; Object aO = f.apply(start); Object bO = f.apply(finish); while (a + 1 < b) { int m = (a + b) / 2; Object mO = f.apply(m); if (aO.equals(mO)) { a = m; } else { assert bO.equals(mO); b = m; } } return a; } @Data private static class Interval { private final int intStart; private final int intEnd; } }

пятница, 10 января 2020 г.

Нечеткий поиск подстроки в строке

#java #поиск #нечеткий_поиск


Здравствуйте. Необходимо реализовать на Java поиск подстроки в строке.
Т.е. строка 
"Разница между родившимися и умершими" должна быть найдена в строке "Разность между
числом родившихся и числом умерших за определенное время (например, за один год) называют
естественным приростом населения."

А строка "Ивановыми" должна быть найдена в строке "Иванов - древнейший житель города"

Необходим лишь ответ - есть ли что-то похожее в строке. Посоветуйте что-нибудь, желательно
уже реализованное на Java.
    


Ответы

Ответ 1



Грубо говоря это делается в 3 шага: Разбиваем строку на лексемы/слова Полученные лексемы прогоняем через Apache Lucene c русской морфологией - в итоге получаем список лексем очищенный от падежных/родовых и прочих морфологичечких признаков характерных для великого могучего, то есть вместо: Разность между числом родившихся и числом умерших за определенное время получим Разница между число родить и число умереть за определенный время Далее для этих лексем вычисляем хэш функцию умеющую выдавать близкие значения хэша для похожих слов - например SimHash или что-то вроде упомянутого Левенштейна Остальное надеюсь объяснять не надо.

суббота, 21 декабря 2019 г.

Как ускорить код поиска на java?

#java #поиск #производительность


Как ускорить код? При изменении ввода/вывода система отказывается принимать, поэтому
нужно оставить неприкосновенный Scan. На данный момент проходит за 1070 мс, нужно ускорить
до 1000 мс. Приветствуются любые идеи!

import java.util.Scanner;

class Main {
    public static boolean find(int search, int[] arr, int len) {
        boolean ret = false;
        int fst = 0;
        int lst = len - 1;
        if ( arr != null){
            while (fst <= lst) {
                int mid = (fst + lst) >>> 1;
                if (search == arr[mid]) {
                    ret = true;
                    break;
                } else if (search < arr[mid]) {
                    lst = mid - 1;
                } else {
                    fst = mid + 1;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int len = scan.nextInt();
        int[] arr = new int[len];
        int i;
        for (i = 0; i < len; i++) {
            arr[i] = scan.nextInt();
        }
        int num = scan.nextInt();
        int search;
        for (i = 0; i < num; i++) {
            search = scan.nextInt();
            System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
        }
    }
}

    


Ответы

Ответ 1



Не трогая собственно дихотомический поиск, предложу модификации: //убран лишний параметр len + упрощаем вызов private дешевле public private static boolean find(int search, int[] arr) { //boolean ret = false; //лишняя декларация - фтопку int mid; if ( arr == null) return false; int fst = 0; int lst = arr.length - 1; while (fst < lst) { mid = (fst + lst) >>> 1; //убираем декларацию mid - зачем нам лишнее движение в стеке? if (search == arr[mid]) return true; //убираем break else if (search < arr[mid]) lst = --mid; else fst = ++mid; } if(search==arr[fst]) //улучшаем асимптотику - то есть последний проход, когда fst==lst выносим за цикл return true; return false; }

Ответ 2



Записывай числа не в массив, а в HashSet. Бинарный поиск по массиву работает за O(ln(n)), а проверка наличия элемента в HashSet-е может выполниться за O(1). Если проблема с производительностью была НЕ из-за долгого поиска, или если есть специальные проверки, учитывающие особенности реализации хэш-функции, то не сработает. Но в общем случае должно помочь.

Ответ 3



Считывание из файла за 940мс прошло. Не понимаю правда почему из файла быстрее, но это сработало. Сама задача https://www.e-olymp.com/ru/problems/3966 import java.io.*; import java.util.*; import java.lang.*; public class test1 { public static boolean find(int search, int[] arr, int len) { boolean ret = false; int fst = 0; int lst = len - 1; while (fst <= lst) { int mid = (fst + lst) / 2; if (search == arr[mid]) { ret = true; break; } else if (search < arr[mid]) { lst = mid - 1; } else { fst = mid + 1; } } return ret; } public static void main(String[] args) throws FileNotFoundException { final Scanner scan = new Scanner(new BufferedInputStream(new FileInputStream(new File("input.txt")))); final PrintStream out = new PrintStream(new BufferedOutputStream(new FileOutputStream(new File("output.txt")))); int len = scan.nextInt(); int[] arr = new int[len]; int i; for (i = 0; i < len; i++) { arr[i] = scan.nextInt(); } int num = scan.nextInt(); int search; for (i = 0; i < num; i++) { search = scan.nextInt(); out.print((find(search, arr, len))? "YES\n" : "NO\n"); } scan.close(); out.flush(); out.close(); } }

Как сделать поисковый сниппет на Javascript?

#javascript #регулярные_выражения #поиск


Javascript. 
Есть массив со статьями. По ним происходит поиск через indexOf. 

Как сделать сниппет аля гугл? То есть брать первое вхождение в строке и выдергивать
несколько слов справа и слева? 

Например ищем слово file в строке:

Edit config.toml and change the default properties to suit your own information.
This is not required to run the example, but this is the global configuration file
and you're going to need to use it eventually. Start here!

In a command prompt or terminal, navigate to the path that contains your config.toml
file and run hugo. That's it! You should now have a public directory with a complete
blog! Open public/index.html in your browser and bask.

If that wasn't amazing enough, from the same terminal, run hugo server. This will
watch your directories for changes and rebuild the site immediately, and it will make
these changes available at http://localhost:1313/ so you can view your finished site
in your browser. Go on, try it. This is one of the best ways to preview your site while
working on it.


И получить сниппет:


  ...global configuration file and you're...

    


Ответы

Ответ 1



Можно так, как вариант: var str = 'navigate to the path that contains your config.toml file and run hugo'; console.log(snippet(str, 'file')); function snippet(string, phrase) { var re = new RegExp('(\\S+\\s){0,3}\\S*' + phrase + '\\S*(\\s\\S+){0,3}'); return string.match(re)[0]; }

Ответ 2



Или так, как вариант: var str = "this is the global configuration file and you're going"; var find = "file"; console.log(snippet(str, find)); function snippet(str, find) { var arr = str.split(" "); var index = arr.indexOf(find); var result = ""; for (i = -2; i <= 2; i++) { if(index + i >= 0 && index + i < arr.length) { var result = result + arr[index + i] + " "; } } return result; }

вторник, 10 декабря 2019 г.

Поиск файла по расширению C++

#cpp #linux #файлы #поиск #g++


Нужно найти файл по расширению в известной директории. Для винды существует такое
решение:

FindFirstFile("Some/Directory/Some/*.some");


А как такое же провернуть под Linux, ибо подход описанный выше не работает и не заработает
в Linux. Уже имеется вот такой код:

cout << "Type path - ";
string path_to;
getline(cin, path_to);
cout << "Type filename - ";
string filename;
getline(cin, filename);
string result = path_to + "/" + filename;
FindFirstFile(result);//знаю, что другое что-то использовать нужно вот и спрашиваю.


Вчера начал изучать C++ после C#, объясните простым языком
    


Ответы

Ответ 1



В С++17 появился новый крутой инклюд для работы с файловой системой: . Им и воспользуйтесь. Код ниже делает поиск непосредственно в выбранной папке, без подпапок. Если нужен рекурсивный поиск, замените directory_iterator на recursive_directory_iterator. #include #include #include #include namespace fs = std::filesystem; // Чтобы не писать `std::filesystem` каждый раз int main() { std::string directory_name = "some/directory"; std::string extension = ".ext"; try // Может быть исключение, например, если папки не существует { for (auto &p : fs::directory_iterator(directory_name)) // Для всех файлов в папке { if (!fs::is_regular_file(p.status())) continue; // Пропускаем, если это не простой файл, а папка или что-то другое std::string name(p.path().filename()); // Проверяем, что имя заканчивается нужным расширением // В С++20 можно будет просто `bool match = name.ends_with(extension);` bool match = !name.compare(name.size() - extension.size(), extension.size(), extension); if (!match) continue; // Тут делаем с путем то, что нужно std::cout << name << '\n'; } } catch (std::exception &e) { std::cout << "Error: " << e.what() << '\n'; } } Чтобы это работало в GCC, нужен флаг -std=c++17 (или -std=gnu++17), и нужно подключить библиотеку -lstdc++fs.

четверг, 5 декабря 2019 г.

Поиск светлых зон на изображении

#изображения #поиск #нейронные_сети


Имеется выборка, в которой 50-200к изображений (раскадровка с видео).
Суть задачи сводится к поиску таких изображений на которых светлая область находится
вертикально или занимает больше 30% площади изображения. Само видео -- съемка грозы
ночью. После раскадровки нужно перенести в отдельную папку все изображения, на которых
есть молнии. Мне в голову приходит только две идеи:


Использовать нейросети (но я не уметь их писать) даже если OpenCV. 
Простой проход в цикле попиксельно по изображению, поиск и подсчет
    кол-ва ярких точек и нужное изображение то, где количество пикселей
    к примеру 30..35% от ширины * высоту.


Подскажите, как правильно это было бы реализовать.
Знаю языки C#/Java/JavaScript/Python. 
    


Ответы

Ответ 1



Итак, если подходить к решению Вашей задачи со стороны нейронных сетей, то, как уже правильно заметил в своем ответе @MaxU, Вам бы понадобилась огромная размеченная выборка с картинками в духе Молния/НеМолния. По сему я считаю, что Вы правильно задумались о попиксельном анализе изображения. Если оценивать изображение по содержанию светлых пикселей - то получите очень неточный результат. Например изображение шахматной доски будет распознано как изображение содержащее молнию... Тут я позволю себе не согласиться с @MaxU, ибо очень сомнительно, что во время съемки материала мимо камеры щеголял шахматист, закрывая камеру своей доской. Думаю, стоит подробнее акцентировать внимание на том, что Ваша задача сводится к тому, чтобы из картинок рода пейзаж / пейзаж с молнией выбрать таки последний, а не к тому, чтобы из набора случайных картинок (в лице тех же шахматных досок) безошибочно выбрать те, где есть молния. Это важное замечание, ибо если мы делаем корм для домашних животных, мы должны учитывать, как на него реагируют и собаки, и кошки. А вот если мы делаем корм исключительно для собак, то ориентироваться на вкус кошек будет как-то глупо (уж простите мне мои аналогии) Каким цветом отображается молния на фотокарточках? Практически идеально белым. Так что яркость пикселей, отражающих молнию, будет стремиться к 1 (или 100%). Это мы и будем использовать. К слову, я уж не знаю, что у Вас там за молнии такие, которые 30% фото занимают, ибо у меня минимальный процент сравнялся с 1.5%) Ладно, от слов к делу. Нам надо выбрать картинки, у которых число пикселей с яркостью >= 0.75 (>= 75%) также >= 0.015 (>= 15%) от всего изображения. Код у меня вышел следующий: using System; using System.IO; using KE.Drawing; using System.Linq; using System.Drawing; namespace LightingDetect { class Program { #region Var private static string InputPath { get; } = $"{Environment.CurrentDirectory}\\Input\\"; // Общая директория, откуда будем брать картинки на анализ private static string OutputLighting { get; } = $"{Environment.CurrentDirectory}\\Output\\Lighting\\"; // Выходная директория для картинок с молниями private static string OutputNoLighting { get; } = $"{Environment.CurrentDirectory}\\Output\\NoLighting\\"; // Выходная директория для картинок без молний #endregion #region Main private static void Main(string[] args) { int lightings = 0; int total = 0; // Убедимся в наличии директорий if (!Directory.Exists(InputPath)) Directory.CreateDirectory(InputPath); if (!Directory.Exists(OutputLighting)) Directory.CreateDirectory(OutputLighting); if (!Directory.Exists(OutputNoLighting)) Directory.CreateDirectory(OutputNoLighting); // Начнем анализ каждой картинки в указанной директории foreach (string imgPath in Directory.GetFiles(InputPath)) { if (HasLighting(imgPath, 0.75f, 1.5)) { File.Move(imgPath, $"{OutputLighting}{imgPath.Split('\\').Last()}"); ++lightings; } else File.Move(imgPath, $"{OutputNoLighting}{imgPath.Split('\\').Last()}"); ++total; } Console.WriteLine("Обработано файлов: {0}\nОбнаружено молний: {1}", total, lightings); Console.ReadKey(); } #endregion #region Functions private static bool HasLighting(string ImagePath, float MinLuminosity, double Percentage) { try { Percentage /= 100; using (Image img = Image.FromFile(ImagePath)) return ((LockedBitmap)img) .Select(x => (HSLColor)x) // Будем читать пиксели в формате HSL, ибо там учитывается яркость пикселя .Count(color => color.Luminosity >= MinLuminosity) / (double)(img.Width * img.Height) >= Percentage; // Сверим условие } catch { return false; } } #endregion } } Увы, я тут для быстрой обработки изображений злоупотребляю своей самописной библиотекой, так что представлю Вам код метода HasLighting с использованием обычного Bitmap (предупреждение: Bitmap.GetPixel() и Bitmap.SetPixel() - чертовски медленные вещи, так что с учетом размеров Вашей выборки советую забыться крепким и сладким сном на время работы программы): private static bool HasLighting(string ImagePath, float MinLuminosity, double Percentage) { try { Percentage /= 100; int count = 0; using (Bitmap img = (Bitmap)Image.FromFile(ImagePath)) { for (int y = 0; y < img.Height; y++) for (int x = 0; x < img.Width; x++) // Запускаем цикл по всем пикселям изображения { Color color = img.GetPixel(x, y); float luminosity = (Math.Max(Math.Max(color.R, color.G), color.B) + Math.Min(Math.Min(color.R, color.G), color.B)) / 510.0f; // Рассчитываем яркость if (luminosity >= MinLuminosity) // Сверяем ++count; } return count / (double)(img.Width * img.Height) >= Percentage; } } catch { return false; } } Поигравшись со значениями MinLuminosity и Percentage, я нашел идеальные значения для моей выборки, так что в итоге на моих скромных входных данных, состоящих из 15 абсолютно разных картинок из Google, было показано стопроцентное попадание. Так как у Вас все картинки из одной серии, думаю, Вам будет легко подобрать идеальные для Вас значения Вообще, такой подход аналогичен переводу изображения в бинарное. Так что если вместо логической обработки мы заменим цвета, что не прошли порог MinLuminosity, на черный, а другие - на белый, то получим нечто такое для изображения с молнией: И что-то такое для изображения без молнии: Как-то так. Надеюсь, мой подход хоть как-то помог в разрешении Вашей задачи. А так - хотелось бы все таки увидеть часть Вашей выборки. Тогда, думаю, я мог бы помочь чуть более конкретно) Удачи Вам! Если что - спрашивайте, будем думать дальше)

Ответ 2



НС вам поможет только если вы сможете ее правильно обучить. Соответственно для обучения нужен солидный (обычно десятки тысяч изображений) набор заведомо размеченных картинок (в вашем случае две папки/категории с изображениями - там где присутствует молния и там где ее нет). Если оценивать изображение по содержанию светлых пикселей - то получите очень неточный результат. Например изображение шахматной доски будет распознано как изображение содержащее молнию... PS Вот похожий вопрос на англоязычной версии сайта, который закрыли как слишком общий...

среда, 17 июля 2019 г.

Алгоритм поиска пика числовой последовательности

Имеется алгоритм поиска пика последовательности, где nel - количетво элементов последовательности, а *less - указатель на функцию сравнивания двух элементов последовательности.
Язык Си:
unsigned long peak(unsigned long nel, int(*less)(unsigned long i, unsigned long j)) { if (nel < 3) return less(0, 1); for (unsigned long k = 1; k < (nel - 1); k++) { if(less(k-1, k) && less(k+1, k)) return k; } }
Он работает для небольших по длине числовых последовательностей, но при подключения функции к программе:
int less(unsigned long i, unsigned long j) { if (i == j) return 0;
if (i < j) { if (j <= 11241155978086311589UL) return 1; if (i >= 11241155978086311589UL) return 0; return (11241155978086311589UL-i) < (j-11241155978086311589UL); }
if (i <= 11241155978086311589UL) return 0; if (j >= 11241155978086311589UL) return 1; return (11241155978086311589UL-j) < (i-11241155978086311589UL); }
unsigned long peak(unsigned long, int (*)(unsigned long, unsigned long));
int main(int argc, char **argv) { unsigned long i = peak(13356955260197607378UL, less); if (i == 11241155978086311589UL) { printf("CORRECT
"); } else { printf("WRONG
"); } return 0; }
Программа выполняется очень долго. Нужна идея оптимизации функции peak(), чтобы она работала как для коротких последовательностей, так и для данной выше программы.
Функция peak должна возвращать индекс любого найденного пика.


Ответ

Для решения задачи можно использовать дихотомию. Кроме того "unsigned long" насколько я знаю 32-битный, потому нужно исправить в коде на uint64_t или unsigned long long. Вот я написал решение на C (немного аккуратней код автора сделал но суть он не меняет), можно запустить онлайн
#include #include
typedef uint64_t u64;
u64 const c_peak = 11241155978086311589ULL; u64 const c_cnt = 13356955260197607378ULL;
u64 peak(u64 nel, int(*less)(u64 i, u64 j)) { if (nel <= 1) return 0; // Note: if nel == 0 there is no answer! if (!less(0, 1)) return 0; if (!less(nel - 1, nel - 2)) return nel - 1;
u64 l = 1, r = nel - 1; while (r - l > 2) { u64 m = l + (r - l) / 2; if (less(m + 1, m)) r = m + 1; else l = m; } if (r - l == 2 && !less(l, l + 1) || r - l <= 1) return l; else return l + 1; }
int less(u64 i, u64 j) { if (i == j) return 0;
if (i < j) { if (j <= c_peak) return 1; if (i >= c_peak) return 0; return (c_peak - i) < (j - c_peak); } else { if (i <= c_peak) return 0; if (j >= c_peak) return 1; return (c_peak - j) < (i - c_peak); } }
u64 peak(u64, int (*)(u64, u64));
int main(int argc, char **argv) { u64 i = peak(c_cnt, less); if (i == c_peak) { printf("CORRECT
"); } else { printf("WRONG
"); } return 0; }

пятница, 12 июля 2019 г.

На каком языке программирования лучше писать поискового робота? [закрыт]

Здравствуйте, возник вопрос: на как каком языке программирования лучше писать поискового робота? Писал на PHP, но робот получился медленный. Если писать на c++, то каким способом лучше общаться с сервером через cURL, LWP, Urdl или winsock?


Ответ

Python. Вот курс о создании поисковой системы с примерами на питоне на Udacity

понедельник, 8 июля 2019 г.

Поиск методов в списке C#

Есть список List с записанными в него методами. Надо выполнить поиск по списку(по свойству MethodInfo.Name), чтобы потом получить нужный MethodInfo и запустить его через Invoke;


Ответ

var consoleType = typeof(Console); var methods = new List(consoleType.GetMethods()); string wantedMethodName = "WriteLine";
1) Можно сделать простой перебор списка и забрать первый элемент, удовлетворяющий условию:
MethodInfo findedMethod; foreach (var method in methods) { if (method.Name == wantedMethodName) { findedMethod = method; break; } }
2) Или воспользоваться методами LINQ, что сделает код проще и симпатичнее:
var findedMethod = methods.FirstOrDefault(m => m.Name == wantedMethodName);
или
var findedMethod = methods.Find(m => m.Name == wantedMethodName);
Об отличиях FirstOrDefault и Find можете прочесть здесь