Ответы пользователя по тегу Алгоритмы
  • Как применить алгоритм "Разделяй и Властвуй" к неотсортированному массиву?

    tsarevfs
    @tsarevfs Куратор тега C++
    C++ developer
    >количество запросов многократно превышает размер массива
    Сортировка работает за O(n*log(n)), бинпоиск будет работать за O(log(n)). Суммарная сложность будет O(n*log(n)) при количестве запросов порядка n.

    Поиск полным перебором будет работать за O(n) для каждого запроса. Суммарная сложность будет не лучше O(n ^ 2), что очевидно хуже.

    Быстрее можно только с построением hash-таблицы. Но это дополнительная память и не «Разделяй и Властвуй».
    Ответ написан
    1 комментарий
  • Как быстро сгруппировать набор точек (2500х2500) по ячейкам Вороного?

    tsarevfs
    @tsarevfs Куратор тега C++
    C++ developer
    Если нужно быстрее чем за линейное время, то есть относительно сложный путь. Диаграмма вороного двойственна с триангуляцией делоне. Если соединить центры смежных ячеек диаграммы - получим триангуляцию. Локализоваться в триангуляции делоне. можно не перебирая все вершины, а переходя к соседним треугольникам в нужном направлении (delaunay triangulation walk).
    Зная в каком мы треугольнике, достаточно проверить расстояние до 3 его вершин которые совпадают с центрами ячеек вороного.
    Что-то такое реализовано тут:
    https://doc.cgal.org/latest/Voronoi_diagram_2/clas...
    И тут:
    https://doc.cgal.org/latest/Triangulation_2/classC...

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

    Может сработает более простой путь. Можно сначала разбить центры ячеек вороного по ячейкам регулярной(прямоугольной) сетки а затем искать ближайшую точку в соседних регулярных ячейках.
    Ответ написан
    Комментировать
  • Как подготовиться к олимпиаде по программированию?

    tsarevfs
    @tsarevfs
    C++ developer
    https://acmp.ru/
    Решайте задачи на разные темы. Начните с простого. Потренируйтесь делать ввод-вывод разных данныи из\в файл. Вспомните как работать со строками, массивами(в том числе двумерными). Целые и вещественные числа.
    Почитайте про графы (список смежности, матрица смежности, обходы, поиск пути).
    Скорее всего будет 1-2 простых задачи, на "моделирование", где надо просто сделать то что просят.
    Задачи на динамику обычно сложные и за 2 недели их сложно научиться решать, но если останется время почитайте пару разборов.
    Часто бывают задачи на геометрию.
    https://e-maxx.ru/algo/intersecting_segments часто используемый метод, когда мы проходим "скользящим окном" по данным, отслеживая изменения.
    Ответ написан
    Комментировать
  • Зачем учить алгоритмы сортировки, если есть уже готовые методы сортировки?

    tsarevfs
    @tsarevfs
    C++ developer
    Скорее в учебных целях. Это хороший пример алгоритма, в котором нужно разобраться. На практике вы конечно не будете писать это сами. Ну и знать про разные методы полезно, так как они немного отличаются.
    Кстати, линейная сложность это O(n). O(n^2) называют квадратичной.
    Стандартные сортировки работают за O(n * log(n)). Но часто это оценка не точная а усредненная.
    Есть сортировки которые могут работать с данными по кускам, не загружая все в память.
    Линейные сортировки бывают, но для этого нужно что-то дополнительно знать про данные. Например сортировка подсчетом хорошо работает на ограниченных наборах (например на массивах цифр 0-9).
    Есть еще другие важные свойства типа стабильности. Это когда вы сортируете файлы сначала по дате а потом по типу и в итоге все файлы одного типа остаются упорядоченны по дате.
    Ответ написан
    Комментировать
  • Как получить базу данных для собственного алгоритма рекомендаций?

    tsarevfs
    @tsarevfs
    C++ developer
    https://www.kaggle.com/c/movie

    Если поискать по запросу "kaggle movie recommendation" или "movie recommendation dataset" можно получить еще много информации.
    Ответ написан
    Комментировать
  • Что для Python лучше? Sort() или сортировка выбором?

    tsarevfs
    @tsarevfs
    C++ developer
    Если это не учебное задание, цель которого научиться писать сортировку, используйте стандартную.
    Сортировка выбором работает за квадрат от количества элементов. Массив из 1000 элементов потребует порядка 1000000 сравнений.
    Стандартная -- вариация на тему quick sort. Работает за O(n * log(n)). Это примерно в 100 раз быстрее.
    Чем больше массив, тем больше будет отрыв.
    Ответ написан
    2 комментария
  • Как лучше искать путь среди окружностей?

    tsarevfs
    @tsarevfs
    C++ developer
    Достаточно легко доказать что пути будут лежать по общим касательным и дугам между точек касания для непроходимых сфер. Можно строить динамический граф и использовать A*.
    C тормозящими кругами может быть сложнее. Если они не могут пересекаться с препятствиями, то их выгоднее обходить по дуге, которая не более чем в pi/2 (~1.5) длинее хорды.
    Если могут, то если аналитическое решение найти трудно, я бы добавил несколько точек на границе медленных зон в граф и искал приближенное решение.
    Про непроходимые круги: https://redblobgames.github.io/circular-obstacle-p...
    Ответ написан
    2 комментария
  • Какой алгоритм выбрать для поиска в тексте?

    tsarevfs
    @tsarevfs
    C++ developer
    Можно написать динамический алгоритм.
    Для каждой ячейки будем хранить:
    left[x][y] - количество пробелов подряд слева от текущей ячейки
    up[x][y] - количество пробелов подряд сверху от текущей ячейки
    square[x][y] - размер квадрата из пробелов с правым нижним углом в текущей ячейке
    5d0cacf2352d3856992078.png
    Тогда:
    left[x][y] = isspace(a[x][y]) ? left[x][y - 1] + 1 : 0
    up[x][y] = isspace(a[x][y]) ? left[x - 1][y] + 1 : 0
    square[x][y] = min(left[x][y] + 1, left[x][y] + 1, square[x - 1][y - 1] + 1)

    Таким образом можно заполнить весь квадрат двигаясь по строкам слева направа, сверху вниз.
    Ответ написан
    1 комментарий
  • Какой алгоритм сортировки сортирует массив с временной сложностю O(n * (N))?

    tsarevfs
    @tsarevfs
    C++ developer
    Судя по разным буквам n и N имеется в виду сортировка подсчетом. Время ее работы зависит от размера массива n и количества возможных значений в массиве N. Так, например, если мы хотим отсортировать массив состоящий из чисел от 1 до 10, то мы можем сделать это за линейное время.
    Кормен "Алгоритмы: построение и анализ" подойдет как справочник.
    Ответ написан
    Комментировать
  • Какой алгоритм текстового калькулятора лучше?

    tsarevfs
    @tsarevfs
    C++ developer
    Польская запись -- простой и незатейлевый алгоритм. Работает с выражениями содержащими бинарные операции и скобки. Вероятно ваш выбор.
    Низходящий разбор это то что вы пытались описать под первым пунктом. Он более универсален. Позволяет разбирать более сложные грамматики c унарными операциями и контекстной завичимостью (один знак может иметь разные значения в зависимости от контекста). В этом методе больше подводных камней. Нужно изучить много теории чтобы понять как обойти некоторые сложности, например левую рекурсию. При некоторой настойчивости можно разобраться.
    Восходящий разбор. SLR, LALR парсеры. Активно применяются на практике. Они сложные, их нет практического смысла писать самостоятельно. Если вы будете использовать генератор парсеров Bison, то это оно.

    То что вы описали вторым пунктом разбивается на выборе операции с максимальным приоритетом. В сложных случаях для этого придется разобрать выражение одним из описанных мной способов.
    Ответ написан
    2 комментария
  • Как покрыть полигон прямыми?

    tsarevfs
    @tsarevfs
    C++ developer
    Предлагаю вращать не прямые, а фигуру. Для этого достаточно домножить координаты каждой вершины на матрицу поворота. Ну, а прямые можно взять горизонтальные (y=c1, y=c2, ...). Так будет значительно проще искать пересечения сторон с этими прямыми.
    Ответ написан
    3 комментария
  • Какими способами можно ускорить работу с объектами на сцене при большм удалении?

    tsarevfs
    @tsarevfs Куратор тега C++
    C++ developer
    1. Лодирование -- не показывать и не давать выделить мелкие объекты на таком масштабе.
    2. Кластеризация. Объединяем близкие объекты в группы по близости. Например так работают маркеры на яндекс картах. Если производительность упирается в обновление множества объектов, групповое изменение можно сделать асинхронным и ленивым.
    3. Можно сделать что-то среднее между 1 и 2. Если граф сцены хорошо группирует объекты логически, то можно прописать лодирование для этих узлов. Например на верхнем уровне у нас есть машина, при увеличении мы можем выделять и двигать отдельные узлы: двери, колеса...
    Ответ написан
    Комментировать
  • Как найти наибольшую поседовательность за O(n)?

    tsarevfs
    @tsarevfs
    C++ developer
    Хранить hash map, в которой ключ - значение последнего элемента в последовательности встреченной раньше, а значение -- длина. И дальше проходим по массиву и заполняем.
    Ответ написан
    2 комментария
  • Какой алгоритм построения графиков выбрать?

    tsarevfs
    @tsarevfs
    C++ developer
    Комментировать
  • Как в графе найти самый "большой" полный подграф?

    tsarevfs
    @tsarevfs
    C++ developer
    Хм, придумалось судя по всему неправильное решение (жадное). Но интересно где проблема.
    UPD: Понял где проблема.
    Лемма 1 Два полных непересекающихся подграфа (без общих вершин) размера m и n соответственно между вершинами которых есть m*n ребер образуют полный подграф с m*n вершин.
    Запихиваем все вершины в СНМ (Система непересекающихся множеств). Каждая вершина -- полный подграф размера 1. Дальше в процессе обхода "сливаем" полные подграфы.
    Для этого храним map: (subgraph1, subgraph1) -> numOfConnections. Каждый раз когда встречаем ребро -- с помощью СНМ находим к каким подграфам относятся вершины и увеличиваем значение в map (или добавляем единицу, если ключа не было). Если значение оказалось больше чем произведение размеров подграфов -- сливаем их.

    UPD: проблема жадного алгоритма в том, что мы получим не максимальный подграф. Иногда делать очередное слияние не выгодно. Например есть маленький подграф А, и 2 больших B и C. B можно слить с С или с А, но все 3 не образуют полный граф. Тогда если мы сольем B и A, то оптимальное решение уже не получится.
    Ответ написан
  • Где ошибка в реализации алгоритма QuickSort?

    tsarevfs
    @tsarevfs Куратор тега C++
    C++ developer
    Вектор передаете по значению. При каждом вызове функции будет создаваться копия. Исправить эту ошибку так: void Quicksort(vector<int> &A, int p, int r)
    Ответ написан
  • Как сделать обход в глубину на основе файловой системы?

    tsarevfs
    @tsarevfs
    C++ developer
    Для реальной задачи используйте os.walk.
    Пробел после запятой -- зло!

    def filegraph(current, last):
        
        if current in visited:
            print( visited, ' visited')
            print(node)
            for key in node:
                    print('%s -> %s' % (key, node[key]), end = ' \n')
            print(current, ' Посещено')
            return #*Сразу выходим, чтобы уменьшить вложенность кода*
    
        #spisok.clear()
        current_dir_items = [] #*это список файлов в текущей директории, то что он был глобальным создавало проблемы ниже*
    
        names = os.listdir(current)
        visited.append(current)
        
        print(current, ' Текущая директория')
        print(last, ' Последняя директория')
        
        for name in names:
            directory = os.path.join(current, name)            
            if os.path.isdir(directory) == True:
                current_dir_items.append(directory)
                print(directory, 'директория')
        print( current_dir_items,  ' список')
        
        print(last)
        node[current] = last, current_dir_items #Добавляем в словарь !!!список не копируется, мы помещаем в словарь ссылку на него!!!
        
        if (last in node) #*логика на исключениях -- плохая идея*
            print(node[last], ' last' )
        else
            print(' Ключа нет')
    
        print(node[current], ' current')
        if len(current_dir_items) != 0:
            #for a in range(0, len(current_dir_items)):
            #    if node[current][1][a] not in visited:
            for next_item in current_dir_items: #*по возможности не используйте for in range(len)*
                if next_item not in visited: 
                    time.sleep(3) 
                    os.chdir(next_item) #*код становится проще*
                    for key in node:
                        print('%s -> %s' % (key, node[key]), end = ' \n')
                    print(next_item, ' current ', '-' * 10 )
                    return filegraph(next_item, current) #тут происходил spisok.clear() и портил вам данные в словаре. 
                
        else:
            time.sleep(3)
            print(' Возвращение ' )
            print(node[current][0], ' current  0' )
            for key in node:
                print('%s -> %s' % (key, node[key]), end = ' \n')
    
            return filegraph(node[current][0], '')
    Ответ написан
  • Как обеспечить автономность программы от сервера?

    tsarevfs
    @tsarevfs
    C++ developer
    В оффлайне сохранять черновик договора без номера и даты. Регистрировать их при синхронизации с сервером.
    Ответ написан
    Комментировать
  • Оптимальный алгоритм нахождения слагаемых суммы?

    tsarevfs
    @tsarevfs
    C++ developer
    Немного переформулируем задачу: найти первое такое число i, что найдется j от 0 до i-1, что a[i] + a[j] = N.
    Ответ написан