Форум 'Алгоритмы' на RSDN

Дерево с O(1) доступом по ID

Fri, 09 Jan 2026 09:47:32 GMT

У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
Какие есть варианты?

Как лучше сжать данные разрешенных ходов для игры?

Sun, 16 Nov 2025 19:16:37 GMT

Начало тут: https://rsdn.org/forum/etude/9018754.flat

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

Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.

А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.

Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.

Далее, я пишут в таком виде:

{
  red: [A1, A2, A3],
  black: [B1, B2, B3],
  redForbidden: null,
  blackForbidden: null,
  transitions: [
    [B1, C1],
    [B2, C1],
    [B2, C2],
    [B2, C3],
    [B3, C3],
  ],
}

т.е. текущее состояние и transitions — разрешенные переходы.

Но состояний то вроде не много, менее 16 тыс., значит влезет в 2 байта. Первые 4 поля значит — 8 байт с лихвой. Ну и преходы.

Еще вариант вычислять на лету, но будет нагружать слабые телефоны.

задача о таблетках

Thu, 30 Oct 2025 13:20:30 GMT

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

Таблеток N видов. Принимаю я ровно 1 таблетку каждого вида в день (это действительно так).

Таблетки в блистерах или флаконах. В одних блистерах 10 штук, в других 15, во флаконах иные значения.

Когда блистер или флакон заканчивается, я заменяю его на новый.

И вот сегодня одновременно закончились 2 разных блистера. Не помню, было ли такое когда-то раньше.

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

Вариант 1. В день X я начинаю прием, все блистеры/флаконы полные.

Вариант 2. В день X я начинаю прием, но блистеры/флаконы неполные, в каждом осталось свое количество таблеток.

Найти день Y, в который закончатся хотя бы 2 блистера/флакона. Для определенности в течение некоторого срока, скажем, года. Если такого не будет, ответ — нет.

Программистское решение. Оно тривиально для обоих вариантов. Просто в цикле делаем T[i]-- каждому блистеру/флакону и смотрим, не получили ли мы хотя бы два нуля на данной итерации цикла. В общем, точная калька того, что я делаю в реальности.

Математическое решение для варианта 1. Оно тоже простое — нужно взять минимальное из НОК для пар блистеров/флаконов. Если, скажем, в одном блистере 10 таблеток, в другом 15, то НОК == 30, и через 30 дней я полностью съем 3 блистера первого лекарства и 2 — второго.

Существует ли математическое решение для варианта 2 ?

Не надо думать, что вариант 2 получился из варианта 1 спустя сколько-то дней, то есть начал я с полных блистеров/флаконов. Нет. Просто в день X в каждом блистере/флаконе Ti таблеток, а как их количества стали такими — не обсуждается.

Нечеткое сравнение слов.

Fri, 17 Oct 2025 01:22:18 GMT

Такая задача.

Есть набор из названий брендов (озвучено — порядка миллиона).
Есть входная строка, например "планшет Samsung"

Необходимо без ИИ сопоставить бренд из словаря этой строке.
Задача выглядит простой для решения — произвести токенизацию строки и затем поиск в хеш-таблице, где хранятся бренды.

Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками.

И сделать поиск эффективным, т.е. придумать такой алгоритм, который не стал бы последовательно перебирать все слова используя, допустим, стороннюю библиотеку поиска дистанции между словами (есть полно готовых таких алгоритмов).

У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))

Найден способ считать кратчайшие пути быстрее Дейкстры?

Mon, 11 Aug 2025 19:51:32 GMT

На днях прошла новость: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Классический Дейкстра устроен так: мы храним вершины в приоритетной очереди и итеративно выбираем ближайшую, проверяя рёбра и обновляя расстояния, если путь через текущее ребро короче. Узкое место тут как раз в необходимости постоянно поддерживать упорядоченность большой очереди вершин.

Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.

Но вот, что сделали авторы тут:

1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.

Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.

Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:

– В графовых нейросетях на основе расстояний между вершинами часто вычисляются самые важные фичи.
– Для всяких ML-алгоритмов для логистики просто незаменимо.
– И даже в RL есть применение. Например, при обучении роботов среда может быть представлена как граф состояний, в котором оптимальная политика – это кратчайший путь.

Отсюда: Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру

Здесь основная идея — это гибрид из алгоритма Дейкстры и алгоритма Беллмана-Форда.

Но если я все правильно понял, то в общем случае
* Новый алгоритм: O(m log²/³ n)
* Алгоритм Дейкстры: O(m + n log n)

1. Разреженные графы (Sparse Graphs): В таких графах количество рёбер m сопоставимо с количеством вершин n, то есть m ≈ n.
* Новый алгоритм: O(n log²/³ n)
* Алгоритм Дейкстры: O(n + n log n) = O(n log n)
* Вывод: В этом случае n log²/³ n растёт медленнее, чем n log n, поэтому новый алгоритм быстрее. Именно это и является его главным достижением, как указано в документе.

2. Плотные графы (Dense Graphs): В таких графах количество рёбер m близко к максимально возможному, то есть m приближается к n².
* Новый алгоритм: O(n² log²/³ n)
* Алгоритм Дейкстры: O(n² + n log n) = O(n²)
* Вывод: В этом случае n² растёт медленнее, чем n² log²/³ n. Поэтому на плотных графах алгоритм Дейкстры будет быстрее.

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

Так?

Алгоритмы и структуры данных

Sun, 27 Jul 2025 04:18:16 GMT

https://ru.algorithmica.org/cs/
На все случаи жизни...
И даже математика и даже геометрия

Написано в конце:

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

Хранилище интервалов

Sat, 26 Jul 2025 18:13:49 GMT

Всем привет.
Нужна помощь коллег.

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

Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.

В общем, нужна помощь коллективного разума

Трансформация дерева с простыми операциями

Wed, 04 Jun 2025 11:02:23 GMT

Привет
Пытаюсь починить парсер нашего рабочего доморощенного язычка и внезапно понял что мозг атрофировался за годы роботы в кровавом энтерпрайсе.

Итак, задача — есть дерево в котором два типа нодов — листья со значениями и узлы с операциями. Пусть операций два типа — сложение и умножение.
Надо заполнить структуру данных, которая содержит группы операций умножения, разделенные группами сложения, это неоходимо для заполнения другой структуры данных, которая потом отправится на удаленный сервак.

Т.е. выражение, распаршеное в дерево:
(a+b)*(c+d)*e должно превратиться в такое a*c*e+a*d*e+b*c*e+b*d*e.

      *
     / \
    *   e
   / \
  +   +
 / \ / \
a  b c  d

                        +
              ___________|___________
             /                       \
            +                         +
         ___|___                   ___|___
        /       \                 /       \
      (*       (* )            (* )      (* )
     /   \    /    \           /    \    /    \
   (* )  e   (* )  e         (* )   e  (* )   e
   /  \       /  \           /  \      /  \
  a    c     a    d         b    c    b    d

Какие идеи?
Спасибо.

Карацюба или Фюрер?

Sat, 17 May 2025 14:44:04 GMT

Здравствуйте!

Есть такие алгоритмы для умножения чисел:
Алгоритм Фюрера — https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D1%8E%D1%80%D0%B5%D1%80%D0%B0
Алгоритм Карацубы — https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%80%D0%B0%D1%86%D1%83%D0%B1%D1%8B

Какой из них лучше использовать?

Сбор теннисных мячей на корте

Tue, 13 May 2025 08:46:06 GMT

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

Что-то получше Левенштейна

Wed, 16 Apr 2025 19:39:56 GMT

В продолжении соседней темы

Вроде расстояние Л. является стандартом но для неточного поиска както оно плохо подходит
потому что если у нас есть строки

xyz
abc123456

и мы ищем по ним запросом

abc

то Л. даст меньшую длину для xyz чем для abc123456
хотя abc123456 содержит запрос abc и выглядит более подходящей

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

ЖПТ мне сходу написал просто Левенштейна который двигает ту строку, что короче, по той, которая длиннее и ищет минимальное дистанцию,

public static int SubstringAwareLevenshtein(string a, string b)
{
    int minDist = int.MaxValue;

    // Сравниваем a со всеми подстроками b
    for (int i = 0; i <= b.Length - a.Length; i++)
    {
        string sub = b.Substring(i, a.Length);
        int dist = ComputeLevenshteinDistance(a, sub);
        if (dist < minDist)
            minDist = dist;
    }

    // Сравниваем b со всеми подстроками a
    for (int i = 0; i <= a.Length - b.Length; i++)
    {
        string sub = a.Substring(i, b.Length);
        int dist = ComputeLevenshteinDistance(b, sub);
        if (dist < minDist)
            minDist = dist;
    }

    return minDist;
}

это уже лучше, но не факт что лучшее совпадение равно длине запроса, а самое хреновое что Л итак медленный а тут еще в M-N раз больше его вызывать нада

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

    public int ComputeDistance(string p, string t)
    {
        if(p.Length > t.Length)
        {
            var x = p;
            p = t;
            t = x;
        }

        var d = 0;

        var min = int.MaxValue;
        var max = int.MinValue;

        for(int i = 0; i < p.Length; i++)
        {
            var j = t.IndexOf(p[i]);

            if(j != -1)
            {
                if(j < min)
                    min = j;
    
                if(j > max)
                    max = j;
            } 
            else
            {

                //  непонятно что тут делать
            }
        }


        return ComputeLevenshteinDistance(t.Substing(min, max - min), p);
    }

но если символ не найден, то хрен его знает что делать,
всякие тупые "+ чтото" не работают потому что с ними функция не получается метрической

Векторизация слов для быстрого поиска похожих

Tue, 25 Mar 2025 00:44:48 GMT

нужно сделать поисковый индекс
чтобы можно был найти "cde" в "abcdefgh" без тупого перебора

по идее это решается вектроризацией которая в ИИ применяется

но как точно это сделать не знаю

потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab

название алгоритма сортировки

Sun, 23 Mar 2025 13:53:22 GMT

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

for i in range(n): 
    for j in range(i + 1,n):
        if a[i] > a[j]:
           v = a[i]
           a[i] = a[j]
           a[j] = v

Транзакция с помощью рандома и задержки

Sun, 23 Mar 2025 09:10:04 GMT

Ну давайте с простого. Имеем:

1. Функция чтения (ну пусть атомарно).
2. Функция записи (так же атомарно).
3. ГСЧ.
4. Функция задержки времени.

Нужно:

1. Считать число (изначально 0).
2. Увеличить число на 1.
3. Записать число.

Но при этом нужно чтобы все это корректно работало в многопоточной среде. Т.е. сколько было вызовов чтения/записи (ну или потоков, который выполнили чтение а затем конечную запись) — столько должно быть установлено значение счетчика.

Добавлю что считывать и записывать — можно произвольное значение, а не только числа.

Так же можно сузить определение гарантированности — считаем что GUID т.е. 16 случайных байт — гарантированно уникальный, что второй такой же не будет создан за время существования Вселенной.

Можно ли как-то гарантировать, не имея мьютексов и пр. блокировок — а только 4 функции из списка?

Обновление дерева

Tue, 04 Mar 2025 13:57:04 GMT

Есть иерархия компании с сотрудниками в базе данных.
Каждый день некое приложение берет из файла данные в таком же по сути виде, просто плоские и надо обновить структуру в базе не удалением вставкой, а только где есть изменения.
Новые добавить\удалить иза базы, изменения применить. Какие есть эффективные алгоритмы получения дифа между деревьями?

Вид данных. То есть иерархия может быть с разными уровнями вложенности

Отдел 1
Сотрудник А
Отдел 2
Сотрудник Б
Отдел 3
Сотрудник В
Отдел 4
Сотрудник Г
Отдел 5
Сотрудник Д

а такая вот задачка

Tue, 28 Jan 2025 13:07:17 GMT

у функции не входе параметры
ф(а, б, ц, д)
а — до какого числа генерировать
б — сколько чисел
ц — минимальное число
д — максимальное число.
собственно задача сгенерировать б случайных чисел, попадающих под критерии ц и д, причем чтоб было нормальное распределение.
забыл написать — чтоб их сумма была равна а

метод деления пополам в больших синтаксических выражениях

Sun, 19 Jan 2025 07:19:38 GMT

это только первый этап алгоритмов, в так называемом скетче "как читать нейронки"

Методология была разработана и применена при анализе регекспоподобніх вьіражений размером до 1.5MB .
В данном методе присутствуют три ленты. В реальности их может быть и больше.

0 лента данных (корпус)
1 лента синтаксического выражения
2 лента кода

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

Попытаемся применить к выражению метод деления пополам. Очевидным становится то, что на определенный момент времени t позиции на лентах будут p0 p1 p2, очевидным становится то, что p[n] (в нашем случае кода)
имеет большую вариативность, чем больше размер ленты tape[n]. вводим понятие консистентность выржанеия consist(expr). консистентность выражается в том, что его определяет
переход от элемента к элементу в ленте минимального размера. tape tmin=min_tape(expr). Таким образом, иы получаем детерминированное консистентное отношение между p0, p2, p3. Где pn E pn{1-tapeN},

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

дальше можно нужно описать тейпизацич кода.

Про канонический алгоритм парсинга Markdown и подобного

Mon, 13 Jan 2025 10:26:25 GMT

Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:

Скрытый текст

TextSpan markdown2TextSpan(String markdownText) {
  final spans = <TextSpan>[];
  final buffer = StringBuffer();

  int asteriskCount = 0;
  bool isItalic = false;
  bool isBold = false;

  for (int i = 0; i < markdownText.length; i++) {
    final char = markdownText[i];

    if ("*" == char) {
      if (asteriskCount < 2) {
        asteriskCount++;
        continue;
      }

      buffer.write(char);
      continue;
    }

    if (asteriskCount > 0) {
      if (buffer.isNotEmpty) {
        spans.add(_buildTextSpan(buffer.toString(), isItalic, isBold));
      }

      if (1 ==  asteriskCount) isItalic = !isItalic;
      if (2 ==  asteriskCount) isBold = !isBold;

      buffer.clear();
      asteriskCount = 0;
    }

    buffer.write(char);
  }

  if (buffer.isNotEmpty) {
    spans.add(_buildTextSpan(buffer.toString(), isItalic, isBold));
  }

  return TextSpan(children: spans);
}

Но это не точно, голова сейчас не работает — могут быть ошибки тут.

Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.

Попросил без регулярных выражений — он начал как бы заглядывать вперед, делать i+1 и т.д. Т.е. не понял как сделать проще. Когда попросил без i+1 — то он такого наворотил, раз в 5 больше кода и ошибку там найти стало не реально.

Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его?

Вероятность коллизий хешей

Fri, 06 Dec 2024 13:51:06 GMT

Добрый день.

Есть где-то документация как можно посчитать вероятность коллизий хешей на произвольных данных? В смысле, что их не будут специально ломать, а использовать для проверки на уникальность.
Или чему она равна?
Особенно интересуют Md5, Sha-1, Sha-256.

Алгоритм анонимного и проверяемого голосования

Sat, 12 Oct 2024 18:55:32 GMT

Вопрос такой, может кто в теме.

Уже придумали ли алгоритм, чтобы:

1. Соблюдалась анонимность. Т.е. чтобы никто не мог узнать за кого проголосовал тот или иной человек, желательно чтобы даже имеющие доступ к базе. Иначе могут быть расправы. Ну ОК, пусть имеющие доступ к баз знают, но хотя бы соседи чтобы не могли узнать.

2. Была возможность проверить свой голос, чтобы знать правильно ли он учтен. Но при этом желательно чтобы ты мог одурачить тех, кто требует от тебя доказательств что ты проголосовал за нужного кандидата (т.е., к примеру, если тебе дают денег — ты на телефоне показал — вот я проголосовал за Кривдина, давайте деньги — а сам проголосовал за Правдина). Т.е. чтобы ты мог проверить но так же и мог само одурачить других — тогда подкуп не имеет смысла.

3. Была возможность как-то проконтролировать общую картину — знать число избирателей, знать что нет мертвых душ — т.е. чтобы была общедоступная инфа по адресам — какой номер дома и квартира в принципе голосовала а кто не голосовал. Тогда можно проверить — вот, я не голосовал а меня записали. Или проверить — вот, у нас на улице 50 домов а в списке почему-то 500.

4. Была бы возможность вычислить итоговый результат, не зная результата каждого отдельного человека (кроме себя самого). Вроде есть алгоритмы.

Есть ли такое? Решены ли данные вопросы?