Блог пользователя JKeeJ1e30

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

Не так давно я писал статью, в которой я описывал данный алгоритм. После серии доработок, благодаря идее  Narg  появилась более хорошая версия данного алгоритма. Ниже излагаю ее, без доказательств(доказательства найдете в предыдущей версии).


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

Шаг 2. Запускаемся из каждой вершины 0-1 обходом.

Собственно, вот обновленная версия алгоритма.

Недавно я заинтересовался, насколько медленно/быстро работает мой алгоритм в сравнении с алгоритмом Флойда. Я взял код Эдварда Давтяна и протестировал его Флойд и мой алгоритм(генератор тестов). Тестирование проводилось на почти полных, разреженных в 4 раза и на разреженных в 20 раз графах. Результат превзошел все мои ожидания:

 n m тип ребер(все положительные +, если есть отрицательные -) время работы Флойда, мсвремя работы моего алгоритма, мс 
 1009000 +38  36
 1009000 48 68
 20039000 263 160 
 20039000 280 513 
 400159000 2080 1224 
 400159000 2033 4054 
 500240000 4043 2336 
 500240000 3880 7482 
 1002500 31 93 
 1002500 47 110 
 20010000 265 125 
 20010000 276 226 
 40040000 2068 409 
 40040000 2028 1096 
 50062500 4027 701 
 50062500 3861 2019 
 100500 29 93 
 100500 37 94 
 2002000 237 105 
 2002000 265 120 
 4008000 1968 180 
 4008000 1954 305 
 50012500 3902 251 
 50012500 3766 492 
  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
Интересует еще какая-нибудь информация-спрашивайте.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Еще, просьба: помогите с переводом.
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Наверное критическими являются 2 строки в Вашей таблице:
 

 n

 m

 тип ребер(все положительные +, если есть отрицательные -)

 время работы Флойда, мс

время работы Вашего алгоритма, мс 

 400

159000 

2033 

4054 

 500

240000 

3880 

7482 


Собственно они, наверное, ставят пока под вопрос и его эффективность...
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -19 Проголосовать: не нравится
    Почему это? Они, наоборот, говорят, что он даже на почти полных графах примерно столь же эффективен, как и Флойд(уступает-то всего в 1,5-2 раза). А на разреженных он оставляет Флойда далеко позади.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Алгоритм конечно эффективнее флойда на неполных графах. Но, имхо, на полном графе 2сек и 4сек при n=400 совсем не "примерно столь же эффективен", по крайней мере в рамках олимпиадного соревнования.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -15 Проголосовать: не нравится
        Во-первых, если бы кто-нибудь помог пооптимизить мне мой код, то вполне возможно от двойки мы бы избавились. Во-вторых, все-таки обычно ТЛ ставят с запасом.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Это смотря какое решение они хотят там увидеть. Сабмит в стиле "как-нибудь пропихнуть" покажет, что флойд значительно эффективнее. Насчет правильных решений: не всегда бывает такой большой запас TL, если я конечно не ошибаюсь.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится -18 Проголосовать: не нравится
            Не всегда для моего алгоритма бывают критичные графы. На макстесте, где соединено каждое ребро с каждым, то есть КСС - это весь граф, да еще и отрицательный цикл есть - он работает в 2 раза медленнее чем Флойд. А на макстесте, где нет отрицательного цикла - он работает в 2 раза быстрее.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              Ну это все хорошо конечно :) я к тому что это немного преувеличение - говорить "примерно столь же эффективен" когда реальное время выполнения в 2 раза больше (причем когда время на гране TL).
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится -8 Проголосовать: не нравится
                В крайнем случае, знаете, если уж так приспичило толкать - пишете: 
                if(n*n < 2*m) then Floyd();
                else algo();
»
13 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
250 строк кода вместо 4-5 у флойда, молодец, чо
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    BPSW тоже 250 строк кода вместо проверки за корень на 3 строки. Укконен тоже 100500 строк кода. И вот че? 

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Ты увеличил код в 50 раз, уменьшив время работы в 5 раз. Поэтому сравнение с BPSW и Укконеном некорректно - они такой фигней не страдают.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Я уменьшил асимптотику. n3 против n*m. Ты бы потрудился прочитать прежде чем критиковать.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

          O(n3) и O(n * m) - это как ложка и вилка. Иногда лучше одно, иногда другое, но по сути одна фигня.


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

          Может, вилка удобнее, быстрее, но мне гиря немного мешает решать задачи кушать.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

             JKeeJ1e30 суров! JKeeJ1e30 не страшит гиря!

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Первое. Ты можешь мне помочь уменьшить размер гири. У тебя олимпиадный опыт много больше, чем у меня. Я знаю, что у меня написано не оптимально (потому что я не умею писать, я краб). Подкинь идею, как это написать быстрее.

            Второе. По сути, мой алгоритм состоит из трех боянов. Боян 1- Форд-Беллман. Боян 2 - топсорт. Боян 3 - 0-1 обход. Бояны пишутся легко.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Решение Флойдом из топика ровно в 1.928 раза короче (125 строк против 241). Не такая уж и большая разница, правда? Если код почистить и отделить алгоритм от ввода, объявлений и прочей рутины, то он будет занимать не более 100 строчек, которые чуть менее, чем полностью состоят из боянов, как уже было ранее отмечено. Не придирайтесь.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      125(!!!!?? как!??) можешь показать?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не сам Флойд, а решение с помощью него данной задачи же.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          поверь, сам флойд и решение будут не сильно отличаться, если написать нормально, будет не один флойд, а два, не 4 строки, а 8
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Понятно, но там всё-таки
            1. Инициализация
            2. Считывание
            3. Флойд в 4 строки
            4. Флойд в 4 строки
            5. Восстановление ответа
            6. Вывод
            7. Куча требухи (#include  и т.д.)
            Идейных строки то всё-равно 2 по 4 =D
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Топик смотрел? Там написано решение именно такого размера. Конечно, там объявлена куча дефайнов(у нас с Эдиком их примерно равное количество).
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          а, ну конечно такого кода...

          кстати, я не пойму смысла вот этого:

          if (old[i][j] == d[i][j] && d[i][j] > -INF64 / 2)
          {
          ;
          }

          это шикарно)

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

            Блин, я просто взял готовый код Эдика и чуть-чуть его поправил под свои нужды. Пустой оператор времени много не отнимает, ведь так? Хорош по мелочам придираться.

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Вот еще такая таблица. Понятное дело, сравнения с Флойдом нет, потому что на таких тестах Флойд до завтра не отработает.

 n m тип ребер время работы моего алгоритма
 10002000  162
 10002000  267
 10005000  377
 10005000  511
 15005000  627
 15005000  780
 150010000  795
 150010000  1284
 300010000  2479
 300010000  3447
 50005000  462
 50005000  471
 500020000  7327
 500020000  11156
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Попробовать и правду можно, но уже не уменьшение константы должно являться дальнейшей целью. Коля в чем-то прав, нужно пытаться упростить код.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Исправил. И в правду быстрее, но ненамного. Что самое странное - на положительных тестах стало сильно быстрее, на отрицательных почти не ускорилось. Код прилагается. Вот результаты:
       n m тип ребер время работы моего алгоритма
       10002000  53
       10002000  282
       10005000  282
       10005000  512
       15005000  349
       15005000  785
       150010000  607
       150010000  1309
       300010000  968
       300010000  3415
       50005000  313
       50005000  309
       500020000  3137
       500020000  10482
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если уж погнаться за скоростью, то можно ещё
         vector < vector < pair < int,int > > >
        заменить на 3 обычных массива. Правда,  обход будет в пару строк длиннее.
        Иногда такая замена изменяет вердикт с TL на AC.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, я именно это и имел в виду, когда писал о замене векторов на массивы
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Особенно эпический vector<bool>
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А чем он так эпичен?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        "Vector<bool> как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool". Моя любимая цитата из Мейерса.

        Если кратко, то он битово сжимает булены и из-за этого имеет ряд спецэффектов. Короче, не нужен в 99% случаев. Заодно известен как эпик фейл стандартизации в STL.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
зачем?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Потому что кокосы падают.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

      P.S. при чем тут кокосы? 

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

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

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Придумай факторизацию полиномиальную)
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +7 Проголосовать: не нравится
            За O(N) пойдёт?
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится -6 Проголосовать: не нравится
              За , так чтобы O(q * g) <  < O(N), q, g, P - многочлены, зависящие от
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ну тогда и P!=NP не проблема ))
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  У вас там знак не тот стоит ;)
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится -6 Проголосовать: не нравится
                  JKeeJ1e30 может все, я уверен)
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я таки сторонник такого знака.... Ну а отрицательный ответ, тоже ответ.
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Вопрос (классический для любой научной работы) какие алгоритмы решения этой проблемы существуют на настоящий момент?
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Описано в предыдущей статье. Из всех известных мне-только Флойд-Уоршелл, работающий за O(n3)

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

          Для поиска у китайцев луше всего использовать их поисковик. Итак загружаем: http://baidu.com и в строке поиска вводим интересующий Вас алгоритм (естественно, на английском языке).

          Проверено неоднократно - выгребает не только "и мох и болото", но попадаются и очень и даже очень стоящие вещи! :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        Вроде как вот тут http://solab.kaist.ac.kr/files/seminar/1st/All-Pairs%20Shortest%20Paths%20and%20the%20essential%20subgraph.pdf обещают за O(ns + n2logn) , где s=o(m) (s - подмножество ребер)

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

          Спасибо, плохо искал значит:) Но у меня нет добавочной асимптотики, везде O(n*m). Предыдущий вариант решения был O(n1*m1 + n2*n2), где n1,n2 = O(n), m1 = O(m), но от такого варианта решения отказался - тормозное было ужасно.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

            Насчет добавочной асимптотики: реальное время этого алгоритма при небольших n (ну например n <= 10^7) может быть значительно меньше твоего. Наверное теперь следует сравнивать уже с данным алгоритмом, а не с флойдом :)

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

              Если бы достать реализацию данного алгоритма...

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

              Фигасе небольшие n. 107. Ты сам-то посмотри что ты написал.

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится
                Ну алгоритмы вообще-то не только для олимпиад созданы.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  n*m при n<=107, m<=107 до следующего тысячелетия не отработает.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится
                  оценим грубо: 107 * 107 / 108= 106 секунд = 11.5 суток
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Да, до следующего тысячелетия погорячился, но посмотрите на данные тестов. Этот алгоритм делает только 107 операций в секунду.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я не призывал делать тесты с n=10^7. Ну даже если в 10 раз больше, пусть будет 115 суток.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится -9 Проголосовать: не нравится
                  по-моему, в таких тестах лучше искать закономерность.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится -11 Проголосовать: не нравится
          Кстати, опять: на почти деревянных графах мой алгоритм намного лучше.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится
            Исходя из чего? Из-за того что у этого алгоритма + n^2 log n в асимптотике? Ты наверняка даже не померил константу. Нужно смотреть на реальное время.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Моя константа явно не убийственно высокая, раз уж почти наравне с Флойдом. Можно даже сказать примерно чему она равна. Если 108 - стандартное количество операций(мой домашний компьютер, на котором производились измерения, явно стандартный), то получается константа не больше 10. n2logn при n = 1000 - это 107. Если брать константу 10(хотя меньше, ну ладно) и 1000 вершин и примерно столько же ребер, получаем те же 107. Ну не верю я что там константа 1.Не может такого быть.
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

                Надо же как все просто. По твоей логике тогда вообще и с флойдом можно было не тестить, там же очевидно какая константа. Ты ведь даже алгоритм не вкуривал, это может быть оценка сверху или еще чего, и по секрету: константа иногда бывает < 1.

                Пример: как ты думаешь, почему поиск max flow работает в 100500 раз быстрее времени, обещанному асимптотикой, а полный перебор нет?
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится -6 Проголосовать: не нравится
                  екараныедритьбатонввашуедрить
                  Ты думаешь, я этого не знаю и не понимаю? Спасибо, открыл Америку. Даже если там константа 1/10, и че? На графе 105 тогда загнется. И кроме того, НЕТУ там константы меньше единицы. В графе циклы надо найти, без этого никак(а это, кстати, O(n*s) как раз - я бы кстати тоже эту же оценку мог бы написать, если цикла отрицательного нет Форд выйдет раньше чем после такой оценки), потом еще все равно что-нибудь да придется делать, потому что надо найти все пары вершин, лежащие вне КСС. За ноль-время это не сделаешь.

                  Вместо того чтобы умничать лучше бы помог: код пооптимизил, потестил. А то критиковать все тут умные, а как дело до помочь доходит - сколько просил, только Родион и помог.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В Беллмане, можно добавить такое : не пытаться релаксировать из вершин до которых расстояние бесконечность, интересно будет узнать уменьшится ли время на ваших тестах.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Ой, блин, как я в коде мог так набажить:)
    Вот результаты. Ускорилось, но малоощутимо:
     n m тип ребер время работы моего алгоритма
     10002000  47
     10002000  269
     10005000  258
     10005000  500
     15005000  333
     15005000  729
     150010000  587
     150010000  1169
     300010000  900
     300010000  3140
     50005000  262
     50005000  265
     500020000  2855
     500020000  10299
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да не должно это улучшить, у тебя по определению все изначальные расстояния равны нулю, и эта проверка никогда не сработает.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Понял, исправил. Все изменения в порядке статистической погрешности.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ещё, что за магия в 61, 62 строчек, все расстояние инициализируешь нулями?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
пользуясь случаем, спрошу, что такое cerr и как он работает и чем он отличается от cout?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тонкостей не знаю,  лично я cerr использую чтобы вывести в консоль интересующие меня вещи. То есть при открытом output.txt cerr выводит нужный текст в консоль(в коде моей программы - clock(), то есть время работы, выводится в консоль, ответ на задачу - в output.txt)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну это стандартный поток зарезервированный под вывод ошибок. Обычный поток вывода как и cout, clog.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      clog и cerr вроде одно и то же за исключением, что cerr, как отмечено ниже - не буферизованный.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Помимо сказанного важно, что cerr - не буферизированный, т.е. если пытаться писать в cout и не делать перевод строки, то в случае падения программы можно не увидеть своего сообщения, а cerr долетает всегда, что делает его более подходящим для всякого дебаг-вывода.