Задать вопрос

dmshar

Ответы пользователя по тегу Алгоритмы

  • Метрическое пространство для k-nearest neighbors?

    @dmshar
    Теоретически может использоваться любая функция, которая удовлетворяет аксиомам метричности (тождества, положительности, симметричности, треугольника). Которые, в свою очередь, выражают интуитивные представления о понятии "расстояния". Т.е. можно взять любую функцию, проверить, удовлетворяет-ли она указанным аксиомам, и если да - то применять. В данном случае понятия "лучше"-"хуже" нет - этот вопрос выноситься за скобки, и как правило является предметом исследования на этапе предварительного анализа задачи.

    Наиболее распространенным меры, применяемые в кластерном, классификационном анализе, в задачах распознавания образов и пр. - уже упомянутая вами эвклидова мера (или метрика L2). Ее модификация - квадрат евклидова расстояния. Манхэттенская мера (или метрика L1), мера Махаланобиса, мера Чебышева, мера Хэмминга, косинусная мера (полезная в многомерном пространстве, но в случае, если много параметров могут иметь нулевые значения), ее модификация - "мягкая" косинусная мера, мера Кульбака — Лейблера (если все значения всех признаков положительны и векторы объектов нормированы на единицу ) и пр.

    А бывают еще неметрические меры близости. (т.е. случаи кода используется функция, которая нарушает одну из упомянутых выше аксиом). В общем, не советую задавать вопрос в теоретической плоскости типа "какой мат. аппарат понадобится для решения такой задачи", потому как там, в этом аппарате, можно и закопаться :-). Достаточно ознакомиться с такой вот интересной книгой: Деза Е.И., Деза М.-М. Энциклопедический словарь расстояний. Ну и при большом желании все перечисленные выше метрики, их описание и области применения легко гуглятся.

    Что до практического использования этого аппарата - такая функция должна подбираться для каждой прикладной задачи отдельно. Это подтверждается успешным использованием в разных прикладных областях различных специфических мер близости - например, мера Левенштейна и мера Джаро — Винклера (используемые при обработке текстов), мера Хаусдорфа (при работе с подмножествами), мера Вассерштейна (применяется в различного рода транспортных задачах и - неожиданно - в обработке изображений, от распознавания рукописных текстов до диагностики по рентгеновским снимкам), и пр. А иногда выбор и обоснование тех или иных мер в конкретной задаче есть предмет научных статей и даже диссертаций.
    Ответ написан
    1 комментарий
    1 комментарий

  • Почему скрипт выдает разные результаты?

    @dmshar
    А причем тут код? Это вы намудрили какую-то операцию, от которой требуете чего-то невозможного. Возьмите простейший пример
    series_3 = '1101'
    series_2 = '110'
    Согласно вашей чудо операции имеем результат '1'

    Теперь делаем "симметричную" по вашему мнению операцию:
    series_3 = '1101'
    series_2 = '1'
    Получаем '101'

    Что не так?
    Ответ написан
    3 комментария
    3 комментария

  • Где учить алгоритмы и структуры данных?

    @dmshar
    "Грокаем алгоритмы". Насколько она хороша? - хороша. Изучайте.

    Что можете посоветовать ещё? - ну,например, https://superstudy.guide/algorithms-data-structure... Достаточно сжато, понятно, все необходимое на месте и без заумствования.

    На что обратить большее внимание при ознакомлении? - странный вопрос. Вы выбираете книгу и учите. А не "обращаете внимание" и торгуетесь "что больше, что меньше, а что может вообще пропустить" .
    Ответ написан
    1 комментарий
    1 комментарий

  • Что эффективней, чтение из файла или массив?

    @dmshar
    Уважаемый mayton2019 дал в общем-то почти исчерпывающий ответ. Но раз вы задали этот вопрос "из возникшего интереса", то есть шанс, что и другим ответы данной темы будут интересы, потому попробую еще чуть-чуть дополнить упомянутый ответ.

    Возможно многие и не слышали, но тем не менее существуют т.н. In-memory database (по-русски это, кажется, называется "Резидентная база данных", но я не уверен). Применяются такие системы как правило в высоконагруженных приложениях - в системах провайдеров телекоммуникационных услуг, когда-то читал - что в системах он-лайн биржевой торговли и пр. Там где данных очень много и доступ к ним нужен очень быстро. И главное - владелец таких данных оччччеееень богатенький, что-бы позволить себе приобрести оборудование с объемом оперативной памяти сопоставимым с объемом внешней памяти для "обычных" серверов баз данных. И вот тогда, для таких задач все данные СУБД, включая все индексы и другой служебно-вспомогательной информации, загоняются в оперативную память, обеспечивая и нужную скорость доступа и удобство доступа, которое обычно присуще СУБД.
    Главнейшая проблема, которую решают разработчики таких систем - как обеспечить целостности базы данных при внезапной перезагрузке систем. Это влияет на производительность In-memory database, заставляя тратить часть вычислительных ресурсов на синхронизацию данных в ОП и резервных копий на внешней памяти.
    Список таких систем можно, кстати, найти даже в Википедии:
    https://en.wikipedia.org/wiki/List_of_in-memory_da...

    Если же "спуститься" с небес на землю и учесть финансовые возможности "нормального" пользователя, то например, в языке программирования Python есть такой модуль - Pandas. По сути он дает удобство доступа к данным, почти такое-же (а может и еще большее) как SQL, сохраняя таблицы в ОП. А скорость обработки - сопоставимую с реализацией на "голых" массивах, а для сложных поисковых запросов - и еще большую. Естественно, что объем таблиц (DataFrame в терминологии Pandas) не может быть слишком большим. И не смотря на то, что есть прямой шлюз для перехода от DataFrame к SQL-структурам СУБД и обратно, скорость работы "в памяти" на много выше, чем скорость работы с теми-же данными, выгруженными в БД. Поэтом программист может комбинировать работу DataFrame для скорости обработки и СУБД для долговременно энергонезависимого хранения, найдя приемлемый для своего приложения компромисс.
    Ответ написан
    2 комментария
    2 комментария

  • Как правильно определить, какое число итераций необходимо?

    @dmshar
    А двавайте велосипед не выдумывать. Есть такой раздел вычислительной науки. "Теория алгоритмов" называется. Он-то как раз и занимается тем, что объясняет, как оценить вычислительную сложность алгоритмов, в том числе ОЦЕНИВАЕТ, сколько циклов, операций сравнения и пр. требуется для того или иного алгоритма.
    Просто после вопроса " единственный вариант - сравнивать список "до" итерации и "после". Но в таком случае, не будет ли затраты на подобные сравнения "затратнее" холостых циклов?" становиться понятным, что тут не на конкретный вопрос отвечать надо, а с азов начинать. Ведь и то что это "единственный способ", и про то что сравнение можно сравнивать с холостым циклом - про все это говориться в Теории алгоритмов. Причем как правило - с самого начала.
    Ответ написан
    Комментировать
    Комментировать

  • Нужен алгоритм победы по процентам, как это сделать?

    @dmshar
    Да все еще проще, причем алгоритмически.
    Генерируется случайное число S, равномерно распределенное в диапазоне от 1 до 800.
    Если S<=100 то победа первого игрока.
Иначе победа второго игрока.

    Ровно три строчки кода.
    P.S. кстати, при заданных значениях задача может еще упроститься. Числа могут быть от 1 до 8. Победа первого, если выпадает 1. В противном случае - победа второго. При достаточно большом количестве повторов вероятности в "полной" и "сокращенной" задачах совпадут. Пруф ищите в курсе теории вероятностей.
    Ответ написан
    3 комментария
    3 комментария

  • Как решить задачу языком программирования?

    @dmshar
    Боюсь, что языком программирования эту задачу не решить. Решить ее можно мозгами. А вот записать решение - с помощью языка программирования.
    А поскольку вам все равно, каким "языком программирования" пользоваться, то вот вам решение.
    flag=False
dt=datetime.date(2022,1,1)
while dt<datetime.date(2023,1,1):
    if flag==True:
        color='Черная'
    else:
        color='Белая'      
    print(dt,color)
    flag= not flag
    dt+=datetime.timedelta(days=1)


    И фрагменты вывода:
    ...
2022-02-25 Черная
2022-02-26 Белая
2022-02-27 Черная
2022-02-28 Белая
2022-03-01 Черная
2022-03-02 Белая
2022-03-03 Черная
...
2022-03-29 Черная
2022-03-30 Белая
2022-03-31 Черная
2022-04-01 Белая
2022-04-02 Черная
....

    Как вы и просили, "о нюансах календаря" не забыли.
    Ответ написан
    4 комментария
    4 комментария

  • Что значит, что алгоритм работает...?

    @dmshar
    В любом нормальном курсе теории алгоритмов (или в соответствующей книге) с первых страниц объясняется, что нотация O() НЕ показывает зависимость времени выполнения алгоритма от количества элементов, поскольку не в состоянии учесть кучу факторов - от языка реализации до стиля написания кода программистом и даже архитектуры hardware вашего компьютера. Все что эта нотация показывает по сути - это как зависит время выполнения алгоритма от роста количества элементов в наборе - линейно, квадратично, логарифмично и пр. И этого в общем-то достаточно, что-бы уметь сравнивать алгоритмы между собой - для чего эта метрика и вводится.
    Ответ написан
    Комментировать
    Комментировать

  • Как хранить и сравнивать локации?

    @dmshar
    Имея геолокацию найти расстояние между двумя точками - задача элементарная (вспоминаем школьную геометрию). Соответственно найти несколько точек, у который расстояния то-ли минимальное, то-ли не превышает заданную величину (те-же 50 км.) также особого труда не представляет. Хотя что делать, если населенные пункты А и В находятся в 50км, но между ними курсирует скоростной поезд, а пункты А и С - в трех километрах, но через высокогорный перевал или реку - с объездом в 100 км (да, бывает и так) ? В общем, мне кажется поиск по геолокации - не лучший способ решения проблемы.

    А вот искать "по области" (или по населенному пункту) - уже перспективнее. Наиболее просто способ - "в лоб" выяснять у пользователя из какой он области. И тогда проблем нет. Но если исходить из геолокации - то проблема серьезная. Надо где-то искать соответствующую базу (по сути границ областей), потом решать задачу, в какую область угодила точка.... В общем весьма муторно.
    Можно, например, спрашивать город, от которого по имеющейся открытой информации переходить к области. Или по области находить города - в том числе близлежайшие - такая карта расстояний имеется (правда, не заю, в свободном-ли доступе). На худой конец искать API Google-maps и тянуть информацию из него.

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

  • Какие разработчики работают с алгоритмами?

    @dmshar
    Так и не смог понять, как мог устареть алгоритм сортировки или поиска пути за лет 5... Тогда мне это показалось диким и, как оказалось, не зря.
    Не знаю, что вы поняли из того, что вам сказали загадочные "мидолами" с несколькими лет стажа, но вот что вам сказал выше уважаемый Wataru вы похоже таки и не поняли.
    Поясню. Алгоритмы учат не для того, что бы запомнить еще один "самый современный" алгоритм, - все равно завтра вы его забудете, а если надо будет применить - поищете в Гуугле. Алгоритмы УЧАТ для того, что бы приобрести навыки алгоритмического мышления. А ВЫСОКОквалифицированный разработчик тем и отличается от "мидола" с "несколькими годами опыта работы", что в первую очередь умеет проанализировать ЛЮБОЙ алгоритм, найти его ограничения, сильные и слабые стороны и пр., а не похвастаться, что он запомнил самый новейший алгоритм, который улучшает некоторые ранее известные на 0.00002%.

    Это как в музыке - сначала учатся играть гаммы (изучают язык программирования), потом учатся играть этюды - простые и незамысловатые пьесы, что-бы приобрести навыки, а уж потом играют сложные композиции. Так вот в программировании, изучение алгоритмов - это и есть этюды. Только тренируете вы не руки, как музыканты, а мозги. И не важно, по учебнику какого года вы это делаете.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм оптимизации выбрать?

    @dmshar
    Не пойму.
    Вы курс оптимизации изучаете и вам надо сделать такое задание? Тогда вам должны были рассказать о преимуществах и недостатках каждого метода. Примените эти знания, что вам мешает?
    Или вы решили решать эту задачу вообще не имея ни малейшего представления о теме? И пришли сюда, что бы вам не зная ни ваших данных, ни вашей функции ни вашей задачи, ни ресурсов вашего компьютера кто-то по озарению ткнул в какой-нибудь метод. И вы ему поверите? По сути в таком случае вы просто попытаетесь переложить на кого-то ответственность за принимаемое решение?
    Ну вы же должны понимать, что по таким совершенно неинформативным признаком нельзя объективно выбрать "правильный метод".
    А если вдруг ваша функция столь сложна, что каждое значение вычисляется примерно 2 часа (что-то слабо себе это представляю. Вы что, на калькуляторе считаете, или как?) то попробуйте подбирать метод сильно упростив вашу функцию, и попробуйте на этой упрощенной модели проверить несколько методов оптимизации. Это же элементарное и естественное решение любого мало-мальски квалифицированного инженера.
    Ответ написан
    4 комментария
    4 комментария

  • Как узнать процент вхождения словосочетания в строку на python?

    @dmshar
    Если строго следовать тому, что вы написали, то процент вхождения словосочетания
    'создание чат-ботов' в вашу строку равен 0. Поскольку словосочетание - это вхождение всех представленных в качестве образца слов, а слово "чат" или "чат-бот" в заданном предложении отсутствует.
    Если же вас интересует процент вхождения слов из примера в набор слов целевого предложения - то это проще. Правда, если слова будут находиться в одинаковой словоформе.
    ex='создать чат бота'
ex_set=set(ex.split(' '))
sent="Добрый день, Требуется создать телеграм бота для размещения объявлений"
sent_set=set(sent.split(' '))
print(1-len(sent_set.difference(ex_set))/len(sent_set))

    Результат:
    0.2222222222222222
    А вот если словоформы будут разные, то тут придется попотеть. Приведение слов к одинаковой словоформе - отдельная и весьма нетривиальная задача.
    Ответ написан
    Комментировать
    Комментировать

  • Какие материалы подойдут, чтобы изучить основы алгоритмизации и программирования на C++?

    @dmshar
    На вопрос "Основы алгоритмизации и программирования на С++" Google выдает 59 тысяч ответов. А на вопрос "С++ учебник для начинающих" - еще 80 тысяч. Вы просмотрели хотя-бы десяток (не тысяч, а просто 10) из них и поняли - ни одна из этих ссылок не подойдет. Потому что ваши запросы - уникальны! Ну кто-же додумается изучать "поэтапно и от простого сложного". Все идут точно в обратном порядке. При таких ваших запросах - вряд-ли кто на форуме сможет вам помочь, увы.
    Ответ написан
    Комментировать
    Комментировать

  • Как еще чуть ускорить алгоритм?

    @dmshar
    А вот так не быстрее будет?
    (Пример специально усложнил)

    lst=[5, 3, 0, 2, 0, 3, 8, 2, 9, 7, 0, 0,7,1, 5, 3]

l=[i for i,v in enumerate(lst) if v == 0]
m_l=[]
for i,ls in enumerate(lst):
    m=len(lst)
    for j in l:
        if m>abs(i-j):
            m=abs(i-j)
    m_l.append(m)
print (m_l)


    Результат:
    [2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 4]

    Если надо еще ускорить - можно порождать список m_l сразу, т.е.
    m_l=[len(lst)]*len(lst)
    и
    m_l.append(m)
    заменить на
    m_l[i]=m
    За счет статики работы с списком должно бы получиться еще быстрее.
    Ответ написан
    2 комментария
    2 комментария

  • Почему быстрая сортировка Хоара медленнее пузырьковой?

    @dmshar
    Дело не в реализации.
    Быстрая сортировка она действительно "быстрая" в случае частично-упорядоченных массивов (которые в реальных задачах могут встречаться не реже, чем полностью неупорядоченные). Причем для корректного исследования не достаточно взять фиксированное количество элементов, а необходимо выполнить сравнения при разном N. И вообще, в O()-нотации, это не столько о времени конкретного выполнения, сколько о том, как изменяется (растет) время выполнения алгоноитма в зависимости от N.

    Вопрос обсуждается в интернет в огромном количестве статей. Ну например:
    https://habr.com/ru/post/274017/
    https://works.doklad.ru/view/w4c2OLj2iMk.html
    Ответ написан
    Комментировать
    Комментировать

  • Как используя цикл for узнать периметр окружности вписанной в квадрат?

    @dmshar
    После дискуссии в комментариях ( 6084 точек на периметр квадрата и требуется понять сколько из них входит в круг) (правда, причем тут "периметр квадрата" я так и не понял) задача сводиться к простой проверке
    расстояние от точки до цента фигуры <= радиус окружности.

    Радиус окружности задан явно.
    Расстояние - простое эвклидово двумерное расстояние (корень квадратный от суммы квадратов расстояний по каждой из двух координат)
    В цикле проверяете каждую точку и считаете, сколько из них указанному условию соответствуют.
    Выяснить периметр - это вообще-то из другой оперы.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоитм сортировки выбрать?

    @dmshar
    Ну так вы же сами ответили на свой вопрос. В любом учебнике по теории алгоритмов есть информация по каждому из вами перечисленных (и другим) алгоритмам сортировки, в котором читателю рассказывают, какую вычислительную сложность имеет каждый из алгоритмов для лучшего (все уже отсортировано), среднего и худшего случаев.
    Другое дело, что применять эти знания можно не при сортировке конкретного массива, а когда вы знаете, что вам надо часто сортировать массив, и как правило (или просто - чаще) ваш массив уже будет отсортированным, частично, отсортированным и т.д. (Так очень часто бывает при решении конкретных прикладных задач).
    А для конкретного массива, не зная заранее что за данные приходят на вход, ничего конкретного сказать нельзя. Поэтому в таком случае ориентируются на "средний" случай.
    Ответ написан
    2 комментария
    2 комментария

  • Есть ли эффективый и не сложный алгоритм посика ярко выраженных пиков в 2D массивах без ML?

    @dmshar
    На сколько мне известно, строгого алгоритма поиска пиков в произвольном временнОм ряду - нет. Поэтому стоит довольствоваться эмпирикой.
    Ну, я бы делал так.
    1. Фиксировал бы размер скользящего окна.
    2. На первом положении окна искал бы максимум.
    3. Сдвигал-бы окно так, что-бы оно начиналось с найденной точки максимума.
    4. Опять искал-бы максимум.
    Если максимум на первом окне оставался максимумом и на втором окне - считал бы это "ярко выраженным пиком". Если нет - повторял бы процедуру .
    Вопрос выбора размера скользящего окна - решается эмпирически.
    Ответ написан
    7 комментариев
    7 комментариев

  • Как ускорить перебор элементов списка?

    @dmshar
    Т.е. прошло больше года, а вы не сдвинулись ни на шаг?
    https://qna.habr.com/q/740387
    И скорее всего, даже не прочитали ответы, которые вам там дали.
    Это отлично характеризует автора вопроса и подсказывает всем, что смысла отвечать на него нет никакого.
    Ответ написан
    5 комментариев
    5 комментариев

  • Как понять какой алгоритм машинного обучения лучше подходит для задачи?

    @dmshar
    Если вы ПРОЧИТАЛИ книгу,но НЕ ПОНЯЛИ основ - то одно из двух: либо книжка была "не та", либо вы ее именно читали, но не разбирались в сути прочитанного. И надеяться на какие-то короткие статьи, в которых будет это то-ли более подробно изложено, то-ли специально адаптировано - весьма наивно.

    Совет - "не зашла" одна книга - ИЗУЧАЙТЕ (!!!) другую. Если не зайдет вторая, третья - то возможно, это "не ваше".
    Ответ написан
    2 комментария
    2 комментария