Блог пользователя e-maxx

Автор e-maxx, 13 лет назад, По-русски

Занимаясь исправлением и дополнением статьи на емаксе, с удивлением обнаружил, что, оказывается, хорошо известная нам временная оценка, данная Тарьяном ещё в 1975 г., ставится под сомнение!

Самой адекватной критической статьёй мне показалась статья Zhang (2008 г.), см. ниже в конце списка.


Итак, хронология событий:

древность - известны разные реализации DSU, с различными эвристиками, по большей части с доказанным временем O(логарифма).

1973 г. - Hopcroft, Ullman - "Set-merging algomthms" - разработка сложного алгоритма DSU с асимптотикой О(итерированного логарифма).  

1975 г. - Tarjan - "Efficiency of a Good But Not Linear Set Union Algorithm" - впервые доказал, что давно известные всем эвристики сжатия пути и объединения по рангу работают за О(обратной функции Аккермана), причём доказал эту оценку как снизу, так и сверху.

1976 г. - Doyle, Rivest - "Linear Expected Time of a Simple Union-Find Algorithm" - предлагается версия DSU только со сжатием путей и показывается, что она работает за O(1) в среднем. Впрочем, как я понял, здесь анализируется случай, когда входные данные сами случайны.

1979 г. - Tarjan - "A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets" - помимо другого, содержит альтернативное доказательство того же факта (см. статья 1975 г.) про обратную функцию Аккермана.

1980 г. - Banachowsky - "A complement to Tarjan's result about the lower bound on the complexity of the set union problem" - указывается, что в доказательстве Тарьяна 1975 г. содержалась ошибка, и она исправлена (и факт ошибки был признан Тарьяном, см. статью 1984 г.).

1984 г. - Tarjan, Leeuwen - "Worst-Case Analysis of Set Union Algorithms" - ссылаются на статью 1975 г., упоминая при этом, что в доказательстве в ней была допущена ошибка, исправленная Баначовски (см. статья 1980 г.). В статье анализируются несколько различных алгоритмов DSU, но нижняя граница О(обратной функции Аккермана) здесь вроде бы не доказывается, а есть только лишь ссылки на статьи 1975 г. и 1979 г.

1985 г. - Yao - "On the expected performance of path compression algorithms" - доказательство того, что DSU работает за O(1) в среднем.

1989 г. - Fredman, Saks - "The cell probe complexity of dynamic data structures" - насколько я понял, описывается новый метод анализа асимптотики динамических структур данных. Этот метод применяется к доказательству нижней границы O(обратной функции Аккермана) для любого алгоритма DSU (теорема 5 в статье).

2005 г. - Wu, Otoo - "A Simpler Proof Of The Average Case Complexity Of Union-Find With Path Compression" - приводят альтернативную реализацию DSU, которая, как они доказывают, работает за O(1).

2008 г.(?) - Zhang - "The Union-Find Problem Is Linear" - предлагается доказательство того, что DSU на самом деле работает за O(1). В конце статьи приводится список ошибок (по мнению автора), содержащихся в доказательствах Тарьяна 1975 г. - 1979 г., а также ошибка в доказательстве Fredman-Saks 1989 г.



В общем, весьма запутанная ситуация. С одной стороны, доказательство Тарьяна за прошедшие 30 лет должно было быть прочёсано вдоль и поперёк. С другой - если после статьи 1975 г. в ней были обнаружены ошибки (см. Banachowsky 1980 г.), то до сих пор нельзя быть уверенным, что ошибок там больше нет.

Но, опять же, статьи китайских авторов не слишком внушают доверия. У меня не было сил углубляться в их доказательства, но вдруг они доказывают поведение DSU на случайных входных данных, вместо анализа худшего случая? Как, например, в статье Royle, Rivest 1976 г. (если я сам не ошибаюсь).


Интересно, кто-нибудь что-нибудь ещё слышал обо всём этом?

  • Проголосовать: нравится
  • +78
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится
Прям детектив какой-то получается! А ты в доказательствах пробовал разбираться?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

Я с Вашего сайта (спасибо за прекрасный ресурс) иногда черпаю идеи для задач различных олимпиад, меня этот вопрос тоже заинтересовало где-то ещё год назад.
Я тогда нашел очень интересный документ, но вопросы у меня до сих пор так и остались.
Может этот документ Вам пригодится и я у Вас же на сайте прочту ответ на интересующий всех вопрос.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится
    А, заимствуя с сайта идеи некоторых задач, вы не боитесь, что некоторые участники ваших олимпиад тоже решают задачи с КФ, и, таким образом, получают несправедливое преимущество?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я так понял, имелся в виду сайт e-maxx.ru. Хотя для серьёзных олимпиад черпать оттуда идеи немного странно - все сильные участники давно про этот сайт знают. Но для тренировок и тематических контестов - самое то.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, в 2009 году на один из алгоритмов, описанных на http://e-maxx.ru/algo/, мной была предложена задачка на областной олимпиаде: "Интересное уравнение".
        Результат оказался плачевным - больше 15 балов из 100 возможных во время реальной олимпиады не набрал никто. :(
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну что касается конкретно этой задачи - она неоднократно проверена временем, если мне не изменяет память, даже на тимусе в каком-то из ранних томов есть (не говоря уж о том, что алгоритм рассказывают на университетских курсах теории чисел). Хотя не вижу ничего плохого в том, чтобы давать школьникам такого рода задачи (на малоизвестные красивые алгоритмы), - возможно, это будет стимулировать их идти в науку. А вот на каких-нибудь "профессиональных" соревнованиях вроде Google Code Jam или Topcoder Open она бы была не очень кстати, да и результаты были бы диаметрально противоположными :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Во первых, в данном случае речь шла об этом сайте
      Во-вторых, это открытые ресурсы и кто мешал остальным при подготовке к олимпиаде также подготовится.
      В-третьих - мои уж 100% условий моих задач не знают, именно поэтому я в последенне время стараюсь не давать своих задач на официальные олимпиады, так как в этом случае мои ученики попадают в невыгодные условия по сравнению с остальными - остальные могут готовить к чему угодно, а я не имею права рассекречивать задачу и поэтому по материалу, на который будет задача подготовка мной не ведётся по вышеизложенной причине..
      Так что тут палка о 2-х концах, и я всё больше и больше склоняюсь к мысли, что готовить к официальным олимпиадам задачи должны те люди, ученики которых в этом соревновании принимать участия не будут - чтобы дети не страдали - это раз, и другие не задавали подобных вопросов (речь не о Вас, надеюсь Вы понимаете)  - это два.
      А использовать идеи с КФ - спасибо за идею... :)
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Я делаю из этого простой вывод:

Можно смело считать, что на практике DSU работает за O(1), потому что таково время работы в среднем (доказано несколько раз), а об antiDSU-тестах я пока ничего не слышал=)

  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Ну, если ребята до сих пор спорят, O(1) это все-таки, или обратная функция Аккермана, то анти-DSU тесты вряд ли существуют в природе, иначе за 30+ лет, наверное, точно были бы обнаружены =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Я боюсь, таких тестов просто не может существовать - потому что невозможно отделить на практике константу от обратной функции Аккермана (которая <=4 для всех разумных ограничений).

    Это скорее теоретический вопрос - является ли время работы DSU настоящей константой, или всё же чрезвычайно медленно растущей функцией.

    Как отмечал в своей статье Тарьян, "DSU - это первый (и, возможно, последний) элементарный алгоритм, который имеет настолько сложную доказанную асимптотику". Будет символично, если и у этого уникума DSU асимптотика окажется "простой".

13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

В википедии пишут, что статья Zhang не прошла peer-reviewing на конференции STOC 2008, после чего была удалена с сайта автора...

Всё же, с вероятностью 99%, доказательство в ней неверно (хотя я проглядел его - доказывалось там как раз для худшего теста, не для случайного).

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Может я банален, но получается тогда, что доказательство, которое используется в "Алгоритмы. Построение и анализ" некорректное ? Просто перелистал- не увидел ссылок, на кого ссылаются авторы. На Тарьяна?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там доказывается оценка сверху. Для оценки снизу просто приводятся ссылки на соответствующие статьи.

    + автору топика: нижние границы всё-таки правильно обозначать как Ω, а не как O
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, Кормен ссылается на Тарьяна.

    Я пока ещё только приступаю к попытке изучения доказательств (в особенности в свете "ошибок", указанных Zhang), поэтому особо нового мне сказать пока нечего. Но в целом, по ощущениям, скорее китайцы не правы, а Tarjan и соавторы - вряд ли могли допустить настолько серьёзный промах.


    Я планирую начать с более современного анализа, проведённого в 2005 г. Seidel и Sharir ("Top-down analysis of path compression"), который, как утверждается, значительно проще доказательств Tarjan.

13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Кстати, по поводу новой статьи на e-maxx: у кого-нибудь есть что-нибудь ещё, что можно указать как интересные применения DSU? У меня сейчас есть:

  • поддержка компонент связности, Крускал
  • задача о покраске подотрезков отрезка (в оффлайн)
  • LCA, RMQ (в оффлайн)
  • поддержка расстояний до лидера
  • поддержка чётности пути до лидера, задача о проверке двудольности в онлайн
  • хранение DSU в виде явных списков; применение этой идеи в некоторых других задачах, где надо сливать две структуры
  • хранение помимо DSU явной структуры деревьев; переподвешивание деревьев за новые корни

Наверняка есть ещё что-нибудь, о чём я забыл - как минимум, из Петрозаводска какая-нибудь жесть :)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

.