• Стоит ли до верится спел чек еру? Про стой пять ни чинный пост до бра
    0
    Шикарный спотыкач! Кстати, возникает интересная алгоритмическая задача по автоматической генерации такого рода текстов.
  • Алгоритм поиска путей в лабиринте
    +6
    А неплоский… лабиринт тоже довольно экзотичен для реального мира.

    image
  • Разбор всех задач и результаты Яндекс.Алгоритма
    0
    Понял, спасибо!
  • Разбор всех задач и результаты Яндекс.Алгоритма
    +2
    Хм, а первая задача разве за линейное время не решается? В каждом слове ищем первую слева букву (начиная при этом со второй буквы, т.к. префикс не должен быть пустым), большую первой буквы в следующем слове и обрезаем слово по найденной букве (не включая ее), от последнего слова оставляем только первую букву. На всех приведенных примерах это вроде работает…
  • Диаграммы разложения на простые множители
    +1
    С числом 210 смешно получается (или с 222, короче, если в делителях только одна двойка) — эффект двоения в глазах зачетный :)
  • Диаграммы разложения на простые множители
    +2
    Красиво! Пифагор бы порадовался :)
  • Через тернии к Haskell (перевод). 2/2
    +3
    Оригинальная статья на английском (Yann Esposito) и перевод на русский (mungobungo), в pdf-формате для чтения на 6-дюймовых е-читалках.
  • Через тернии к Haskell (перевод). 2/2
    +1
    Быстро вы вторую часть выкатили, спасибо!
  • Через тернии к Haskell. 1/2
    +2
    кстати, на викибукс есть викиучебник по хаскелю в формате pdf, сверстанный под 6-дюймовые читалки…
  • Через тернии к Haskell. 1/2
    +2
    Спасибо за статью, ждем продолжения!

    ЗЫ: Не совсем функционально, зато рекурсивно и в одну строчку :)

    int sum(int* x) 
    { 
      return x[0]?(((x[0]%2)?0:x[0])+sum(x+1)):0; 
    }
    
  • Сжатые префиксные деревья
    0
    Во, то что доктор прописал :) Спасибо еще раз!
  • Сжатые префиксные деревья
    0
    Спасибо большое за ссылки, обязательно поизучаю на досуге! С libdatrie, кстати, я сравнение не делал… Относительно терминологии, мне больше нравится Radix Tree и русский вариант — дерево цифрового поиска.
  • Сжатые префиксные деревья
    0
    Кстати, кто-нибудь может подскажет, где найти стандартные тестовые наборы для такого рода задач?
  • Сжатые префиксные деревья
    +2
    Это я к тому, что суммарный объем необходимой памяти, в принципе, один и тот же, поэтому, чем меньше куски, тем больше их нужно, тем больше операций с памятью…
  • Сжатые префиксные деревья
    +1
    Эти куски памяти к тому же и очень мелкие :(
  • Сжатые префиксные деревья
    0
    Была мысль вместо односвязного списка хранить двоичное дерево (то же АВЛ), но что-то страшно стало :) А вот с алфавитом все немного интереснее выглядит, надо будет подумать…
  • Сжатые префиксные деревья
    +1
    Доля правды в ваших словах есть. Вот распределение длин ключей во внутренних узлах дерева для двух тестовых наборов:



    Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…

    Ссылку попозже посмотрю, спасибо!
  • Сжатые префиксные деревья
    0
    1) С этим замечанием согласен, на графике время отнормировано на размер (в символах) используемого набора строк, иначе разброс для одного графика оказывался очень большим. Сейчас попробую пересчитать чистое время… На третьем графике шкала обозначена в подписи :) — по оси Y отложено количество байт на один символ (символ у меня занимает один байт)…
    2,3) Про продакшн никто и не говорит :)
  • Сжатые префиксные деревья
    0
    1) На первых двух графиках сравниваются между собой два времени, какая разница, какая там шкала? На третьем шкала обозначена… На серьезную статобработку данных времени и сил пока нет :)
    2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
    3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…
  • Решение задачи коммивояжёра рекурсивным полным перебором
    +1
    Про минимум эвристики улыбнуло :) Есть мнение, что уйти от экспоненциальности (а ведь это ваша цель?) и при этом сохранить оптимальность нельзя…
  • Решение задачи коммивояжёра рекурсивным полным перебором
    +1
    В результате вы все равно получили эвристический алгоритм… Чуда не произошло! :)
  • АВЛ-деревья
    +1
    Как я понял, АВЛ-деревья лучше сбалансированы, чем красно-черные. В этом их плюс, т.к. поиск выполняется чуть-чуть быстрее: высота в АВЛ-дереве ограничена величиной 1.44log2(n+2) против 2log2(n+1) в красно-черных. С другой стороны, это означает, что в АВЛ-деревьях больше сил затрачивается на балансировку, следовательно, операции вставки и удаления работают медленнее, чем в красно-черных деревьях. Так что однозначного победителя здесь похоже нет…
  • АВЛ-деревья
    0
    Оглавление интересное, надо поискать… Спасибо!
    PS: уже нашел :)
  • АВЛ-деревья
    0
    Т.е. все-таки случай, когда ключи не все одинаковы! Как я понимаю, количество «ложных» срабатываний (когда мы переходим в узел, не содержащий искомого ключа, как в вашем примере) в одном случае будет 2h, во втором h, где h — высота дерева. Если дерево идеально сбалансировано, то получим 2log2n против log2n, что уже не выглядит так драматично :)
  • АВЛ-деревья
    0
    Спасибо! Теперь можно сравнить с реализацией на Haskell… Кстати, не нашел удаления ключей в вашей программе. Правда, там есть union — это слияние двух деревьев? Если «да», то удаление уже несложно реализовать…
  • АВЛ-деревья
    0
    Все равно непонятно: чтобы добраться до какого-то элемента, мы должны спуститься к нему из предыдущего по дуге, что эквивалентно выполнению ровно одного сравнения. Т.е. число сравнений (<= или >=) все равно окажется равным n-1. Для примера можно взять случай с тремя вершинами (выше в комментариях) — в обоих нарисованных вариантах дерева нам потребуется 3 (т.е. n) сравнения на равенство и 2 (т.е. n-1) на меньше-больше, нет? Возможно, по другому будет, если число одинаковых ключей, которые мы ищем, равно k и оно меньше n? Сейчас подумаю…
  • АВЛ-деревья
    +1
    Предположим, что у нас в дереве n одинаковых ключей (предельный случай) и больше ничего, и одинаковые ключи могут быть и слева и справа. Тогда поиск найдет все их, обойдя все дерево, и выполнит при этом O(n) действий. Пока я не вижу проблемы — чтобы найти n вхождений, потребовалось выполнить O(n) действий… Может я чего-то не понимаю?
  • АВЛ-деревья
    0
    Красиво! И местами даже понятно… :)
  • АВЛ-деревья
    +1
    Нет, не только вам, мне теперь тоже так кажется :) Обычно пишу, как во втором варианте, а тут решил «укомпактить» код…
  • АВЛ-деревья
    0
    Собственно, при написании топика я этот момент не проверил, т.к. мне казалось, что я помню именно такое определение (два нестрогих неравенства). Сейчас посмотрел Кормена, оказывается я правильно помнил… Вообще-то, чуть ниже в топике (в том же абзаце) я ввел более строгое ограничение, предположив, что все ключи различны, и рисунок относится именно к этому случаю. Уникальность же ключей, например, гарантрируется, если мы с помощью дерева поиска реализуем какой-нибудь словарь (или ассоциативный массив).
  • АВЛ-деревья
    0
    Спасибо!
  • АВЛ-деревья
    +4
    Сначала хочется разобраться со сплей-деревьями, а потом уже очередь красно-черных…
  • АВЛ-деревья
    0
    Как это не удивительно, но я не встретил ни разу рекурсивной реализации АВЛ-деревьев, везде предлагается итеративный подход. Поделитесь ссылками на реализацию на непроцедурных ЯП?
  • АВЛ-деревья
    +2
    Правильно, функции поворота служебные, для внешнего пользователя (в данном случае) не нужные, а внутреннее использование подразумевает, что все нужные указатели не нулевые.
  • История информатики в лицах
    +1
    Геделя упустил, каюсь. А Левенштейна не нашел карточку. Вернее одна есть на его персональной странице в ИПМ, но она слишком маленькая (хотя можно было попытаться ее увеличить)… Точно придется вторую версию делать! :)
  • История информатики в лицах
    0
    Затруднит :) т.к. списков никаких не составлялось… Как только был превышен порог в 256 персон, процесс остановился. Википедия (например, вот) и гугл-картинки — вот по сути и все источники. Бумажные энциклопедия по информатике и математический энциклопедический словарь (единственное место, где я нашел фотографию Жегалкина). Еще пара ссылок, которыми я пользовался: тыц и тыц.
  • История информатики в лицах
    0
    Спасибо!
  • История информатики в лицах
    +1
    А Цезарь вас на этом постере не смущает? :)
  • История информатики в лицах
    +2
    Гильберт в q10. В остальном согласен, но переделывать ничего не буду :)
  • История информатики в лицах
    0
    Спасибо, то что надо!