Ответы пользователя по тегу Алгоритмы
  • Как определить алгоритмическую сложность функции?

    @SolidMinus
    Внутри foreach используется strcmp, имеющий сложность O(N)

    Цикл также имеет такую сложность. Сложности алгоритмов вложенных перемножаются:

    O(kN^2 + nlogn)

    k - количество внутри алгоритмов со сложностью O(N), так как там strtolower, preg_split и т.д, то, соответственно домножается цикл O(N*(N + N + ... N)) ( в пределах одного блока сложности суммируются )

    nlogn - из-за usort, я не знаю какой там алго используется, поэтому возьмем самый быстрый.

    В результате округляем до того значения, который дает большой самый вклад, т.к при росте сумма nlogn становится незначительной, как и множитель k, то: O(N^2) ответ

    P.S. Существует метод для не-аналитической оценки сложности алгоритма.

    Берешь в цикле увеличиваешь размер входных данных и замеряешь скорость выполнения, строишь график где по Y откладываешь время, а по X - N и обычно точки ложатся в пределах какой либо функции: y=N;Y=N^2;Y=logN и т.д
    Ответ написан
    8 комментариев
  • В каких случаях эффективнее дублирование кода вместо вызова функции?

    @SolidMinus
    Если вставлять inline функции, то бинарный код в размере очень сильно будет расти, но будет скорость выполнения будет также расти.

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

    Поэтому это все можно упростить до такой степени, чтобы выполнялся лишь нужный код. Для этого лишь не надо плодить функции. Замечаешь разницу в количестве выполняемых этапов?

    Если размер кода так критичен, но и нужна скорость, то можно выставить _fastcall перед определением функции, тогда вместо _cdecl функция будет вызываться без передачи параметров через стек, а передаваться внутри регистров. Это увеличит скорость вызова функций. Но не стоит злоупотреблять, т.к регистры используются для "быстрых вычислений", без доступа к памяти, и огромное количество _fastcall функций заставит компилятор перед вызовом функций постоянно сохранять состояние регистров, а потом восстанавливать.

    Решается это все настройками оптимизатора на скорость или размер кода. При выставленной оптимизации по размеру кода спецификатор _inline игнорируется.
    Ответ написан
    6 комментариев
  • Генетический алгоритм. Как делается жизнь?

    @SolidMinus
    генетические алгоритмы - это не алгоритмы обучения, это алгоритмы оптимизации. Наподобии градиентного спуска, адама и прочих. И, к слову, один из самых неэффективных. Он просто очень красиво показывает эволюцию и не более. Хотите заниматься машинным обучением - почитайте про стохастический градиентный спуск, градиентный бустинг, рандомные леса, и SVM-машины. Ну и про нейронки почитайте. но только после всего этого
    Ответ написан
    2 комментария
  • Быстрый поиск пересечений треугольников (для 2D и 3D)?

    @SolidMinus
    Попробуй пойти в сторону задания вершин треугольников как координат в пространстве.

    Тогда для каждого треугольника можно составить по три параметрических уравнения прямых, далее составить такую систему для каждого треугольника. В теории, если решить эту общую систему линейных уравнений можно как-то понять есть ли пересечения.

    Попробуй двигаться в этом направлении: www.cleverstudents.ru/line_and_plane/parametric_eq...

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

    Если я прав, то задача сведется к вычислению огромной матрицы.
    Ответ написан
  • Алгоритм поиска однотонных мест на картинке?

    @SolidMinus
    Как уже сказали на SO. Различие между набором пикселей - RMSE. Оно же расстояние минковского с p=2. Можешь p ( степени ) другими. Это изменит "чувствительность" к различиям. Эксперементируй.

    https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D...

    width = 0
    height = 0
    Берешь image[i][j] пиксель, сравниваешь с теми, что по краям image[i][j + 1] image[i][j - 1] если они похожи, то добавляешь в heigth = heigth + n, количество пикселей которое похоже вокруг. Далее повторяешь то же самое для этих самих пикселей которые похожи, если там есть куда идти, опять добавляешь.

    Когда widthXheigth = соответствующим размерам текста, то ты нашел то место.

    В общем, думаю что-то в этом направлении надо.
    Ответ написан
    Комментировать
  • Дешифровка строки: исходя из примера, каким способом зашифрована, закриптована или сжата строка?

    @SolidMinus
    Ты думаешь тут экстрасенсы или всякие тьюринги сидят, что могут распознать алгоритм шифрования по его hex выхлопу?

    начнем с того, что чем она зашифрована/закриптована никак не узнать быстро, т.к выхлоп будет разный от различных ключей.

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

    Пысы.

    49 8D 77 1A 4A 99 соответственной байты 73 141 119 26 74 153


    Поясни за слова. Чейта у тебя даны последовательности такие? Hex и Dec что ли?

    Это задание откуда?

    Могу посоветовать глянуть в сторону криптоанализа на основе известного открытого текста и шифротекста, чтобы узнать ключ, но придется перебирать все алгоритмы шифрования шифруя 111111 всеми возможными ключами пока не получится 498D771A4A99.... тогда ты найдешь ключ и алгоритм шифрования

    Может, ну его?
    Ответ написан
    Комментировать
  • Как улучшить алгоритмическое мышления?

    @SolidMinus
    Видимо, только начинаешь кодить. Оно рано или поздно само придет, причем внезапно. Потом будешь спрашивать как перейти от него к математическому, а то все решения будут "наивными" - чисто алгоритмическими)
    Ответ написан
    Комментировать
  • Кто может помочь с алгоритмом?

    @SolidMinus
    линейным же уравнением описывается, бро ( в реальности полиномиальным, т.к со временем просмотры идут на спад, но раз нужен линейный, то дальше читай )


    f($end, $start, $now, $count) = ($count * $end- $start * $count) / ($now - $start)
    f($end, $start, $now, $count) = ($count * ($end- $start)) / ($now - $start)


    44467b2ecc6f4fc794fac0b474fceed9.PNG

    f(x) = ax + b, f(x) - количество предсказываемое лайков, x - время a, b - коэффициенты

    Предполагается, что в самом начале нет лайков:
    20000a + b = 10000
    5000a + b = 0

    b = -5000a

    20000a - 5000a =10000
    15000a = 10000
    a = 0.666
    b = -3333.3

    Следовательно:

    лайки(время) = 0.666 * время - 3333.3

    лайки($end) = 56 607

    В общем виде:

    $now * a + b = $count
    $start * a + b = 0

    -b = $start * a
    $now * a - $start * a = $count

    a($now - $start) = $count
    a = $count / ($now - $start)
    b = -($start * $count) / ($now - $start)


    f($time) = ($count * $time - $start * $count) / ($now - $start)
    f($time) = ($count * ($time - $start)) / ($now - $start)
    Ответ написан
    1 комментарий
  • Какой алгоритм подойдет для описания полета насекомого?

    @SolidMinus
    т.е. голова должна быть направлена в направлении движения


    Направление движения будет вектор = касательная к кривой в данной точке * (вектор скорости/ значение скорости)

    mathserfer.com/theory/kiselev2/node64.html
    Вот тут есть как ее найти.

    Производная в точке программно вычисляется через определение производной отношение разницы значений, см. определение частной производной через предел и как через нее найти полную производную.

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


    Чтобы траектория была гладкая - надо генерировать больше точек. Чтобы были дуги - использовать тригонометрические функции.

    Главное правило, которое поможет:
    * нужна цикличность - cos/sin etc
    * нужно сглаживание между некоторым границами - sigmoid
    * нужен рост - функции высшего порядка

    В данном случае - нужна 2d функция, которая будет принимать x, y и возвращать z, подобная картина будет ее проекцией на 2d-плоскость

    Берешь функцию:

    f(x(t1), y(t1)) = a*cos(x(t1))^k + b * sin(y(t1))^t + O, где a,b,k,t, O - переменные, которые рандомно подбираешь для придания уникального вида, t1 - время, f(x(t1),y(t1)) - высота мухи по z, в зависимости от ее координат по x,y

    Я хз как привести практический пример, поэтому приведу в python, некая гипотетическая пьяная муха или обдолбанный раптором комар
    Nk9X0Bh.png8935555cc6f04cd8a21a52a0bb294fb6.PNG
    import numpy as np
    import matplotlib.pyplot as plt
    from mpl_toolkits.mplot3d import Axes3D
    def func(x, y, a, b, t, k, O):
        return a * np.power(np.sin(x), t) + b * np.power(np.cos(y), k) + O
    
    t = 5
    k = 5
    
    theta = np.linspace(-4 * np.pi, 4 * np.pi, 1000)
    time = np.linspace(0, 5, num=1000)
    
    a = 10
    b = 10
    
    x = time * np.sin(theta) + a
    y = time * np.cos(theta) + b
    
    z = np.asarray([func(x[i], y[i], a, b * i, t, k, 100) for i in range(len(x))])
    
    
    plt.plot(x, z, 'r')
    plt.show()
    
    fig = plt.figure()
    ax = fig.gca(projection='3d')
    
    
    ax.plot(x, y, z)


    Короче вектор в каком направлении двигаться ясен. Тупо перебирай функции генерации x, y и z пока не найдешь нужную красотульку
    Ответ написан
    Комментировать
  • Есть ли способ для компактной и наглядной записи алгоритма работы многопоточных программ?

    @SolidMinus
    А что не так?
    Поток 1
    пока x < 10
      x = x + 10
    вернуть x * x
    
    Поток 2
    пока x > 10
      x = x - 10
    вернуть sqrt(x)
    
    Ждать(x = поток1, y = поток2)
    вывод x + y


    Полнейший полет фантазии, запись алгоритма лишь формальная система, Вы вольны придумывать что угодно.
    Ответ написан