Начало
После окончания работы скоростного алгоритма погрешность найденного тура ещё слишком велика. Чтобы сбросить её в единицы процентов, эстафету подхватывает алгоритм, который рассматривает все рёбра (мы называем его «средний»). Он работает уже по схеме 3-opt, то есть имеет формально кубическую сложность, хотя прыгать от линейной сложности скоростного сразу на кубическую (минуя квадратичную) смотрится «варварством». На самом деле, эффективность 3-opt мы сохранили, а вот трудоёмкость осталась квадратичной. Почему? Да всё из-за тех же «нюансов реализации». Рассказываю.
Начинаем поиск решения с рассмотрения «сверхдлинных» рёбер (алгоритм их определения такой же, как и в скоростном алгоритме), постепенно понижая длину и вовлекая в перебор всё более короткие рёбра. Смысл тот же: именно там выше всего вероятность обнаружения новых модификаций тура, и именно они дают наибольшее падение бета-границы. Кроме того, мы вначале ищем для каждого ребра решение всё-таки по схеме 2-opt, а обнаруженные при этом рёбра, представляющие интерес для 3-opt (то есть короче текущего ребра тура) мы просто отправляем в стек. Если в процессе обхода по 2-opt так и не было найдено ни одного решения (а любое найденное решение, разумеется, мгновенно обнуляет стек и весь расчёт ребра), тогда стек выбирается уже по схеме 3-opt. В результате на глубину 3 «прорывается», в среднем, 2-3 ребра на узел, т.е. трудоёмкость расчёта остаётся квадратичной, а эффективность — «кубической».
Второе важное ускорение — полный запрет обсчёта новых рёбер: «не царское это дело», пусть скоростной развлекается! Таким образом, «средний» алгоритм просто «взлохмачивает» текущий тур, выбрасывает его из локальных минимумов, а скоростной, наоборот, смотрит только новые рёбра (на них вероятность обнаружения улучшений тура довольно высока), «приглаживает» тур, усаживая его в новые минимумы и роняя бету…
Третье важное замечание — введено каскадирование обсчёта рёбер по таймеру (не более одного тика на ребро, не более 2, 4, 8...), чтобы не уходить в глубокий расчёт сложных рёбер и попытаться найти решение «малой кровью». Как правило, на очередной каскад, не успев обсчитаться на этом, прорывается лишь половина-треть-четверть рёбер, а потому, несмотря на удвоение времени на расчёт каждого ребра, время прохождения старших каскадов заметно меньше, чем младших.
В результате работы этой спарки алгоритмов тур получается и совсем уж пригодный для практического использования, кроме, разве что, некоторых экзотических применений. А мы приступаем к поиску точного решения. Но сначала…
После отработки «среднего» алгоритма погрешность составляет всего лишь единицы процентов, но для поиска оптимального тура это очень большая величина, многократно увеличивающая трудоёмкость расчётов. Да, экспериментальные прогоны на небольших графах показали, что уже первый каскад точного алгоритма обычно укладывает бета-границу в доли процента, но трудоёмкость даже первого каскада во много раз превышает затраты на все предыдущие расчёты. Что же делать? Подумаем… обычно погрешность составляет 3-5%, понижать её нужно при жёстких временных рамках (не более 30-40% ожидаемой трудоёмкости первого каскада). И всё же основания для оптимизма есть: за редчайшим исключением, при ошибке в несколько процентов локальные минимумы ещё неустойчивые — достаточно хоть немного «спихнуть» с него тур, и бета-граница тут же падает на процент-другой. Как именно спихнуть? Видимо, есть только один реальный способ: «взлохматить» разворотом несколько случайных рёбер, объявить их «новыми», и произвести «добор» (запомнив, на всякий случай, текущий тур). Сколько? Немного, только чтобы «спихнуть» — иначе возможный выигрыш в одном месте с большой вероятностью «компенсируется» проигрышем в другом. Пожалуй, от одного до четырёх «разворотов», да и то с понижением вероятности. Сколько раз «бросать монету»? Тоже немного: это всё-таки авантюра, поиск решения «на авось». Скажем, 1000 раз — «добор» работает быстро, и даже в случае полной неудачи потери времени будут относительно небольшими. Когда? Однозначно, только перед точным алгоритмом: и скоростной, и средний и так неплохо справляются с погрешностью, а на точном «халява» уже не пройдёт.
Неожиданно этот подход показал невероятно высокую эффективность: best-known решения посыпались, как из рога изобилия, да и в остальных случаях бета-граница резко упала. Похоже, неустойчивость локальных минимумов распространяется на ошибки в десятые или даже сотые доли процента! Так что же, случайный поиск заслужил право быть включённым в общую технологию?
К сожалению, эффективность случайного поиска резко падает с ростом числа узлов. Причины этого понятны: поверхность отклика становится всё более сложной, и мы, сохраняя способность сшибать на ней мелкие «кочки», практически утрачиваем возможность выбраться из более крупных «ям», требующих одновременной замены сколько-нибудь значительного числа рёбер. Заметно растут накладные расходы: при удаче мы изменяем, как правило, очень небольшой участок тура, но сохранять (и восстанавливать) приходится весь тур. Наконец, на небольших графах «добежать» до best-known можно буквально за несколько модификаций, а для более тяжёлых количество (удачных!) изменений тура составляет многие сотни и тысячи. Таким образом, рекомендовать этот алгоритм можно лишь с оговорками: до тысячи узлов он более, чем эффективен, до десяти тысяч тоже окажется полезен, да и до ста тысяч наверняка что-то найдёт (хотя время вычислений начинает уже серьёзно раздражать), до миллиона его могут использовать разве что мазохисты, а после миллиона это уже просто издевательство над компьютером! Одним словом, мы его вообще выбросили!
Алгоритм точного решения… полиномиальный, разумеется… а существует ли он вообще? Ведь за один только ответ на этот вопрос — хоть положительный, хоть отрицательный — дают миллион, да что-то не видно желающих его получить… нет, всем понятно, что там полином, причём невысокой степени, но доказать это не никак получается. И мы не будем — мы же практики!
Более ранней версии нашей программы уже удавалось доказать оптимальность нескольких небольших графов, но достигалось это довольно грубыми средствами: тупая каскадная рекурсия, без учёта перестановок, без «доборов» и множества других нюансов, часть которых была описана выше. Но теперь нам придётся задействовать всю мощь как наших мозгов, так и компьютерных. Если, конечно, там ещё что-то осталось.
Каскадная рекурсия. Да, этот алгоритм экспоненциален (как мы покажем ниже, не всегда), но он всё же способен найти лучшее решение и доказать, что оно именно лучшее. Во всяком случае, это куда более работоспособный вариант, чем метод ветвей и границ — тому тупо не хватит объёма под его матрицы, не говоря уже о том, что он тоже экспоненциальный. Одним словом, рекурсия остаётся главной рабочей версией, если не удастся найти чего-то более приличного. Почему каскадная, и что это вообще такое? Спросите Джонсона — соавтора классического алгоритма решения TSP Lin & Kernighan. Или Кена Томпсона из той же Bell Labs, автора шахматной программы — чемпиона мира. Или любого, кто вообще занимался шахматным программированием. Нет, я тоже занимался, но я не скажу. Из вредности.
Вот и всё! Никаких иных возможностей лично я больше не вижу! Если кто знает — подскажите. Но ведь мы же уже «пробовали на зуб эту» рекурсию, она нас не устраивает по скорости — даже каскадная, даже если сводить дерево вариантов к циклическому графу! Да, мы прекрасно помним про эвристику, которая предписывает рассматривать лишь те варианты, для которых сумма длин удаляемых рёбер на любом этапе больше, чем у вновь включаемых в тур, и это действительно снижает трудоёмкость расчётов совершенно диким образом. Более того, как мы показали в своей работе (вернее, это сделал мой шеф и соавтор Роман Лукацкий), никакая это не эвристика, ибо удаляемые рёбра старого тура и вставляемые рёбра нового всегда образуют замкнутый контур (при этом контуров может быть несколько) и, следовательно, мы всегда можем найти такую точку и направление обхода этого контура, при котором указанное правило соблюдается. Увы, и эта техника тоже помогает, «як бидному рукопожатия»: общее число возможных туров чудовищно велико, и даже та их ничтожная часть, которая «прорывается» на анализ, оказывается слишком большой: время расчёта возрастает катастрофически. А ведь алгоритм работает даже лучше, чем ожидалось! Да и сама технология поиска практически совпадает с «общепризнанно лучшей эвристикой» (хотя и уступает ей, поскольку гарантирует получение точного решения). Конечно, метод этот на порядки эффективнее «ветвей и границ» (чтобы в этом не возникало ни малейших сомнений, достаточно отключить «Конкорду» эвристику). Но всё-таки время расчёта точных решений по-прежнему недопустимо велико!
Собственно, все наши надежды полностью оправдались. Один из самых неприятных графов для ранних версий программы (fl3795), который изначально «удерживал» бета-границу выше 5% почти двое суток, и мы с большим трудом довели этот показатель до двух часов, сейчас «сдаётся» за неполные две минуты. Эксперименты подтвердили, что с увеличением глубины рекурсии объём дерева вариантов растет очень «неохотно». Так и должно быть: попробуйте-ка на графе с малой бета-границей найти десяток-другой новых рёбер меньшей длины, чем удаляемые ребра тура. Да ещё связанных в замкнутый(е) контур(ы). Трудно! Коэффициент ветвления в большинстве случаев оказывается ничтожным — редко более 2 на старте, и почти никогда более 1.5 после 2-3 каскадов. Так в чем же дело? Да просто аппетиты возросли! Нам теперь мало иметь возможность доказать оптимальность тура на сотню узлов. И на тысячу мало. Тысяч на сто надо бы, как минимум!
Одним словом, выводы неутешительные: никакие косметические меры нам не помогут: нужно не просто ускорение — нужен качественный скачок. Что же делать? А чёрт его знает…
В каждой шутке есть доля правды. Мы действительно считаем возможности заявленного подхода исчерпанными. На наш взгляд, получилась достаточно удачная и работоспособная версия, которая может несколько расширить существующие пределы по числу узлов графа, но для выхода на новые рубежи придется искать принципиально иной подход. Собственно, выход один: снижать безумие комбинаторики. И не просто снижать, а с гарантией сохранения «в остатке» точного решения. Возможно ли это? Ещё как!
После окончания работы скоростного алгоритма погрешность найденного тура ещё слишком велика. Чтобы сбросить её в единицы процентов, эстафету подхватывает алгоритм, который рассматривает все рёбра (мы называем его «средний»). Он работает уже по схеме 3-opt, то есть имеет формально кубическую сложность, хотя прыгать от линейной сложности скоростного сразу на кубическую (минуя квадратичную) смотрится «варварством». На самом деле, эффективность 3-opt мы сохранили, а вот трудоёмкость осталась квадратичной. Почему? Да всё из-за тех же «нюансов реализации». Рассказываю.
Начинаем поиск решения с рассмотрения «сверхдлинных» рёбер (алгоритм их определения такой же, как и в скоростном алгоритме), постепенно понижая длину и вовлекая в перебор всё более короткие рёбра. Смысл тот же: именно там выше всего вероятность обнаружения новых модификаций тура, и именно они дают наибольшее падение бета-границы. Кроме того, мы вначале ищем для каждого ребра решение всё-таки по схеме 2-opt, а обнаруженные при этом рёбра, представляющие интерес для 3-opt (то есть короче текущего ребра тура) мы просто отправляем в стек. Если в процессе обхода по 2-opt так и не было найдено ни одного решения (а любое найденное решение, разумеется, мгновенно обнуляет стек и весь расчёт ребра), тогда стек выбирается уже по схеме 3-opt. В результате на глубину 3 «прорывается», в среднем, 2-3 ребра на узел, т.е. трудоёмкость расчёта остаётся квадратичной, а эффективность — «кубической».
Второе важное ускорение — полный запрет обсчёта новых рёбер: «не царское это дело», пусть скоростной развлекается! Таким образом, «средний» алгоритм просто «взлохмачивает» текущий тур, выбрасывает его из локальных минимумов, а скоростной, наоборот, смотрит только новые рёбра (на них вероятность обнаружения улучшений тура довольно высока), «приглаживает» тур, усаживая его в новые минимумы и роняя бету…
Третье важное замечание — введено каскадирование обсчёта рёбер по таймеру (не более одного тика на ребро, не более 2, 4, 8...), чтобы не уходить в глубокий расчёт сложных рёбер и попытаться найти решение «малой кровью». Как правило, на очередной каскад, не успев обсчитаться на этом, прорывается лишь половина-треть-четверть рёбер, а потому, несмотря на удвоение времени на расчёт каждого ребра, время прохождения старших каскадов заметно меньше, чем младших.
В результате работы этой спарки алгоритмов тур получается и совсем уж пригодный для практического использования, кроме, разве что, некоторых экзотических применений. А мы приступаем к поиску точного решения. Но сначала…
Случайный поиск
После отработки «среднего» алгоритма погрешность составляет всего лишь единицы процентов, но для поиска оптимального тура это очень большая величина, многократно увеличивающая трудоёмкость расчётов. Да, экспериментальные прогоны на небольших графах показали, что уже первый каскад точного алгоритма обычно укладывает бета-границу в доли процента, но трудоёмкость даже первого каскада во много раз превышает затраты на все предыдущие расчёты. Что же делать? Подумаем… обычно погрешность составляет 3-5%, понижать её нужно при жёстких временных рамках (не более 30-40% ожидаемой трудоёмкости первого каскада). И всё же основания для оптимизма есть: за редчайшим исключением, при ошибке в несколько процентов локальные минимумы ещё неустойчивые — достаточно хоть немного «спихнуть» с него тур, и бета-граница тут же падает на процент-другой. Как именно спихнуть? Видимо, есть только один реальный способ: «взлохматить» разворотом несколько случайных рёбер, объявить их «новыми», и произвести «добор» (запомнив, на всякий случай, текущий тур). Сколько? Немного, только чтобы «спихнуть» — иначе возможный выигрыш в одном месте с большой вероятностью «компенсируется» проигрышем в другом. Пожалуй, от одного до четырёх «разворотов», да и то с понижением вероятности. Сколько раз «бросать монету»? Тоже немного: это всё-таки авантюра, поиск решения «на авось». Скажем, 1000 раз — «добор» работает быстро, и даже в случае полной неудачи потери времени будут относительно небольшими. Когда? Однозначно, только перед точным алгоритмом: и скоростной, и средний и так неплохо справляются с погрешностью, а на точном «халява» уже не пройдёт.
Неожиданно этот подход показал невероятно высокую эффективность: best-known решения посыпались, как из рога изобилия, да и в остальных случаях бета-граница резко упала. Похоже, неустойчивость локальных минимумов распространяется на ошибки в десятые или даже сотые доли процента! Так что же, случайный поиск заслужил право быть включённым в общую технологию?
К сожалению, эффективность случайного поиска резко падает с ростом числа узлов. Причины этого понятны: поверхность отклика становится всё более сложной, и мы, сохраняя способность сшибать на ней мелкие «кочки», практически утрачиваем возможность выбраться из более крупных «ям», требующих одновременной замены сколько-нибудь значительного числа рёбер. Заметно растут накладные расходы: при удаче мы изменяем, как правило, очень небольшой участок тура, но сохранять (и восстанавливать) приходится весь тур. Наконец, на небольших графах «добежать» до best-known можно буквально за несколько модификаций, а для более тяжёлых количество (удачных!) изменений тура составляет многие сотни и тысячи. Таким образом, рекомендовать этот алгоритм можно лишь с оговорками: до тысячи узлов он более, чем эффективен, до десяти тысяч тоже окажется полезен, да и до ста тысяч наверняка что-то найдёт (хотя время вычислений начинает уже серьёзно раздражать), до миллиона его могут использовать разве что мазохисты, а после миллиона это уже просто издевательство над компьютером! Одним словом, мы его вообще выбросили!
Поиск точного решения
Алгоритм точного решения… полиномиальный, разумеется… а существует ли он вообще? Ведь за один только ответ на этот вопрос — хоть положительный, хоть отрицательный — дают миллион, да что-то не видно желающих его получить… нет, всем понятно, что там полином, причём невысокой степени, но доказать это не никак получается. И мы не будем — мы же практики!
Более ранней версии нашей программы уже удавалось доказать оптимальность нескольких небольших графов, но достигалось это довольно грубыми средствами: тупая каскадная рекурсия, без учёта перестановок, без «доборов» и множества других нюансов, часть которых была описана выше. Но теперь нам придётся задействовать всю мощь как наших мозгов, так и компьютерных. Если, конечно, там ещё что-то осталось.
Каскадная рекурсия. Да, этот алгоритм экспоненциален (как мы покажем ниже, не всегда), но он всё же способен найти лучшее решение и доказать, что оно именно лучшее. Во всяком случае, это куда более работоспособный вариант, чем метод ветвей и границ — тому тупо не хватит объёма под его матрицы, не говоря уже о том, что он тоже экспоненциальный. Одним словом, рекурсия остаётся главной рабочей версией, если не удастся найти чего-то более приличного. Почему каскадная, и что это вообще такое? Спросите Джонсона — соавтора классического алгоритма решения TSP Lin & Kernighan. Или Кена Томпсона из той же Bell Labs, автора шахматной программы — чемпиона мира. Или любого, кто вообще занимался шахматным программированием. Нет, я тоже занимался, но я не скажу. Из вредности.
Вот и всё! Никаких иных возможностей лично я больше не вижу! Если кто знает — подскажите. Но ведь мы же уже «пробовали на зуб эту» рекурсию, она нас не устраивает по скорости — даже каскадная, даже если сводить дерево вариантов к циклическому графу! Да, мы прекрасно помним про эвристику, которая предписывает рассматривать лишь те варианты, для которых сумма длин удаляемых рёбер на любом этапе больше, чем у вновь включаемых в тур, и это действительно снижает трудоёмкость расчётов совершенно диким образом. Более того, как мы показали в своей работе (вернее, это сделал мой шеф и соавтор Роман Лукацкий), никакая это не эвристика, ибо удаляемые рёбра старого тура и вставляемые рёбра нового всегда образуют замкнутый контур (при этом контуров может быть несколько) и, следовательно, мы всегда можем найти такую точку и направление обхода этого контура, при котором указанное правило соблюдается. Увы, и эта техника тоже помогает, «як бидному рукопожатия»: общее число возможных туров чудовищно велико, и даже та их ничтожная часть, которая «прорывается» на анализ, оказывается слишком большой: время расчёта возрастает катастрофически. А ведь алгоритм работает даже лучше, чем ожидалось! Да и сама технология поиска практически совпадает с «общепризнанно лучшей эвристикой» (хотя и уступает ей, поскольку гарантирует получение точного решения). Конечно, метод этот на порядки эффективнее «ветвей и границ» (чтобы в этом не возникало ни малейших сомнений, достаточно отключить «Конкорду» эвристику). Но всё-таки время расчёта точных решений по-прежнему недопустимо велико!
Собственно, все наши надежды полностью оправдались. Один из самых неприятных графов для ранних версий программы (fl3795), который изначально «удерживал» бета-границу выше 5% почти двое суток, и мы с большим трудом довели этот показатель до двух часов, сейчас «сдаётся» за неполные две минуты. Эксперименты подтвердили, что с увеличением глубины рекурсии объём дерева вариантов растет очень «неохотно». Так и должно быть: попробуйте-ка на графе с малой бета-границей найти десяток-другой новых рёбер меньшей длины, чем удаляемые ребра тура. Да ещё связанных в замкнутый(е) контур(ы). Трудно! Коэффициент ветвления в большинстве случаев оказывается ничтожным — редко более 2 на старте, и почти никогда более 1.5 после 2-3 каскадов. Так в чем же дело? Да просто аппетиты возросли! Нам теперь мало иметь возможность доказать оптимальность тура на сотню узлов. И на тысячу мало. Тысяч на сто надо бы, как минимум!
Одним словом, выводы неутешительные: никакие косметические меры нам не помогут: нужно не просто ускорение — нужен качественный скачок. Что же делать? А чёрт его знает…
В каждой шутке есть доля правды. Мы действительно считаем возможности заявленного подхода исчерпанными. На наш взгляд, получилась достаточно удачная и работоспособная версия, которая может несколько расширить существующие пределы по числу узлов графа, но для выхода на новые рубежи придется искать принципиально иной подход. Собственно, выход один: снижать безумие комбинаторики. И не просто снижать, а с гарантией сохранения «в остатке» точного решения. Возможно ли это? Ещё как!
Комментарии (11)
shapovalex
18.05.2019 11:25Вот бывало у меня такое. Прилетает резюме, человеку 45 плюс, всю жизнь программирует но никогда в серьезной коммерческой разработке не участвовал. Но резюме крутое и то сделал и то придумал. HR’ы сразу в топку. Поначалу я вмешивался и собеседовал таких людей.
Когда говорили о предыдущих достижениях вроде все ок. Начиналось техническое интервью и человек начинал сыпаться на базовых вещах. Причём на всех, сплошняком. Но самомнение — а зачем это надо, я в интернете посмотрю, этим никто не пользуется. Раза после 5 я просто перестал вытаскивать эти резюме из корзины.
Так вот Хабр это сообщество умных людей и выскочек тут не любят. Если изобрели что то новое — вперёд научную статью. Только там ещё жёстче будет.slavap
18.05.2019 14:17Как можно всю жизнь программировать и не быть в серьёзной разработке? В гос.конторе что ли сидел? У меня опыт с 45+ значительно более позитивный.
shapovalex
18.05.2019 18:06У кого как. У кого завод, у кого 1С, у кого информационная система предприятия на Делфи 3.
Некоторые просто работают, а программирование как хобби.
rybvv Автор
18.05.2019 21:37Ну, раз у меня 1 коммент в сутки, напишем сегодня В ЭТУ заметку. :)
Текущее положение с графом-миллионником с иерархической кластеризацией:
2711/8 N=5555555/0 L=109342890.00 (42/2048) T=136200.3 sec
0/16 N=5555555/3 L=94427986.00 (551/262144) T=167366.1 sec
1133610/16 N=5555555/120 L=86735067.00 (187/65536) T=200011.9 sec
55136/16 N=5555555/176 L=83262470.00 (1165/524288) T=219064.8 sec
То есть бета-граница упала на данный момент в 7142 раза!
shapovalex
Серьёзно?! Хабр — это сообщество умных людей? И где же они попрятались? Нет, кое-кого видел. Одному я переслал свой «нормальный» сортир, скомпилированный под NT, с возможностью заказа под задачу достаточно большого количества ОЗУ — он мгновенно исчез, и больше не появлялся, даже в личку не отвечает. :) Со вторым мы неплохо поговорили (и, в общем, продолжаем) — он мне писал в личку: Другого слова, как позор, для этого ресурса у меня нет. Если честно, даже подумываю, не пора ли уже его покинуть: Стадные инстинкты в худшем их значении, тупое самодовольство и гонор недоучек, берущихся судить обо всём и закидывать какашками несогласных — вот что я вижу. Третий мне писал: Жду новых Ваших статей, когда бы они ни вышли. Четвёртый был модератор. Вот и всё, кажется — навскидку больше вспомнить не могу. Так где же «умные люди»? Тот поросячий визг в моих ветках с несколькими сотнями комментов в каждой, случайно, не они устроили? А те, которые сейчас? Которые хлебальники позахлопывали, но активно и анонимно гадят в карму — не они, нет? Или, может быть, Вы тот самый «умный человек»? Тогда ЗАЧЕМ Вы этот пост написали? Слов не так уж мало, а мыслей я что-то не заметил. Да и в профиле негусто: 7 лет на Хабре, 2 заметки, 29 комментов, 9 подписчиков… кто Вы, собссно, такой, чтобы «собеседовать людей»?
И при чём тут Хабр и «научные статьи»? Быдлу справка «от компетентных органов» требуется? Чтобы знали, во здравие орать или за упокой? Ну, есть у меня 7 публикаций, из них 4 англоязычных — дальше что? И несколько авторских, за одно из которых мне платили довольно неплохие (по российским меркам) деньги где-то лет 10-15 — дальше что? Так где «умные люди»-то? Покажите пальцем!
michael_vostrikov
Что, лапуль, свалить так и не получается? Эх, бедолага… :) Кстати, shapovalex, как считаете — это умный человек или именно то, что я про него думаю?
Да где уж нам уж понять супер-гения, который даже в «воронке» умудрился квалратичную сложность получить!
Господи, как же Вы затрахали своим унылым враньём! Про подтормаживание говорил я, а не Вы, говорил дважды, и оба раза не Вам: 3 мая 2019 в 09:37 и в 12:45, причём про длинные строки говорил только В ПЕРВОМ случае. А свою долбаную «алгоритмическую сложность» засуньте себе в задницу — я не раз писал, и вот здесь как раз ИМЕННО ВАМ: Меня интересует РЕАЛЬНОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ СОРТИРОВКИ, а не ваш онанизм со «сравнениями»!
Да, только у вас сравнение не только при слиянии, а еще и при помещении в воронку, то есть на каждый элемент как минимум на 1-2 сравнения больше. А в MergeSort сравнение только при слиянии. А еще математиком себя называете.
Ну это уже просто клиника! Классическое слияние начинается С ОДНОГО элемента, а у воронки, даже в худшем случае — С ДВУХ! А в Ваших дебильных «тестах» и вообще с ЧЕТЫРЁХ, а то и С СОРОКА! И не надо ВРАТЬ! Никаким «математиком» я себя не «называю»! Алгоритмист я, лапуль! Причём ХОРОШИЙ алгоритмист.
Да, и для последовательности из 4 элементов, которую я сделал специально для нее, она работает плохо. Хуже чем MergeSort и гораздо хуже чем TimSort. О чем я и говорил.
И я говорил: не надо СВОЁ говно называть МОЕЙ воронкой! ;) Кстати, о птичках: воронка ВСЕГДА одна! Только размер у неё может быть разный — ХОТЯ БЫ ДО ЭТОГО Вы способны допереть за столько времени? А в тех цифирях, которые Вы привели, у меня русским языком написано, что там, вследствие нехватки ОЗУ, мне приходилось сливать 2, 4 и 7 tmp-файлов соответственно! Что же более ранние сравнения не привели? Хотя бы предыдущий: N=134217728 NC=3137971972? Что, не выигрывает «MergeSort» у «VoronkaSort»? Да и что Вы там вынюхиваете даже в случае с промежуточными файлами? Даже по сраным сравнениям там копейки!
N = 268435456 6535172283/6375342080*100-100=2.507%
N = 536870912 13534222142/13220446208*100-100=2.373%
N = 1073741824 28021925721/27380416512*100-100=2.343%
При этом для убывающей последовательности у воронки будет еще больше сравнений, а у MergeSort останется то же самое.
:lol: Ой, уписаюсь! Ловите, лапуль! Вот данные для Вашего первого дебильного примера (N — число строк, NC — число сравнений, NCB — число сравнений для убывающей последовательности ):
N=4 NC=3 NCB=6
N=8 NC=16 NCB=19
N=16 NC=49 NCB=56
N=32 NC=129 NCB=140
N=64 NC=317 NCB=336
N=128 NC=749 NCB=784
N=256 NC=1725 NCB=1702
N=512 NC=3901 NCB=4032
N=1024 NC=8701 NCB=8960
N=2048 NC=19197 NCB=19712
N=4096 NC=41981 NCB=43008
N=8192 NC=91133 NCB=93192
N=16384 NC=196605 NCB=200713
N=32768 NC=421885 NCB=430090
N=65536 NC=901117 NCB=917515
N=131072 NC=1916925 NCB=1949708
N=262144 NC=4063229 NCB=4128781
N=524288 NC=8585319 NCB=8716405
N=1048576 NC=18088468 NCB=18350627
N=2097152 NC=38014679 NCB=38538981
N=4194304 NC=79708817 NCB=80757408
N=8388608 NC=166813171 NCB=168910340
N=16777216 NC=348207988 NCB=352402308
N=33554432 NC=725767274 NCB=734155903
N=67108864 NC=1510250045 NCB=1527027281
N=134217728 NC=3137971972 NCB=3171526426
N=268435456 NC=6535172283 NCB=6603431326 (2 tmp-файла)
N=536870912 NC=13534222142 NCB=13672846935 (4 tmp-файла)
N=1073741824 NC=28021925721 NCB=28275791206 (7 tmp-файлов)
Вот данные для Вашего второго дебильного примера:
N=40 NC=39 NCB=78
N=80 NC=160 NCB=235
N=160 NC=481 NCB=632
N=320 NC=1281 NCB=1580
N=640 NC=3197 NCB=3792
N=1280 NC=7661 NCB=8848
N=2560 NC=17853 NCB=20224
N=5120 NC=40765 NCB=45504
N=10240 NC=91645 NCB=101120
N=20480 NC=203517 NCB=222464
N=40960 NC=447485 NCB=485376
N=81920 NC=975869 NCB=1051656
N=163840 NC=2113533 NCB=2265097
N=327680 NC=4550653 NCB=4853770
N=655360 NC=9748477 NCB=10354699
N=1310720 NC=20791293 NCB=22003724
N=2621440 NC=44171261 NCB=46596109
N=5242880 NC=93521415 NCB=98371093
N=10485760 NC=197399428 NCB=207098771
N=20971520 NC=415532279 NCB=434930949
N=41943040 NC=872545961 NCB=911343288
N=83886080 NC=1828471939 NCB=1906066580
N=167772160 NC=3930141656 NCB=4085330955 (2 tmp-файла)
N=335544320 NC=8634315580 NCB=8372810133 (3 tmp-файла)
N=671088640 NC=16683646832 NCB=17304403943 (5 tmp-файлов)
N=1342177280 NC=34640086080 NCB=35881590227 (9 tmp-файлов)
Здесь тоже копеечная разница! Воронке ПО БАРАБАНУ вся эта ловля блох, она сортирует ЛЮБЫЕ последовательности! Алгоритм ИДЕАЛЕН, лапуль! ;)
А уж если говорить про TimSort, да еще и для 40 элементов
А чего говорить про TimSort? У этого дерьма НЕ МОЖЕТ быть «линейной сложности»! НИ НА КАКОЙ последовательности — даже на Вашей дебильной! Ибо САМ АВТОР «ссылается на собственные эксперименты, показавшие, что при minrun > 256 нарушается пункт (1), при minrun < 8 — пункт (2) и наиболее эффективно использовать значения из диапазона (32;65)». Так что даже для minrun = 256 и миллиарда строк коэффициент должен болтаться в районе двадцатки! Другое дело, что Ваш пример НАСТОЛЬКО идиотский, что для него ДЕЙСТВИТЕЛЬНО может быть эффективен этот дурацкий «Galloping Mode»! Воронка же подобной хернёй не занимается — она спокойно сливает списки по КЛАССИЧЕСКОМУ алгоритму, который эффективен ВСЕГДА. Наконец, этот придурок, судя по описанию, КОПИРУЕТ МАССИВЫ! Воронка же подобной хернёй ТОЖЕ не занимается — она читает элемент из файла ОДИН раз и записывает его в файл тоже ОДИН раз, никаких трепыханий в ОЗУ она не производит ВААПЩЕ!
Ну и, раз уж «умные люди» засрали мне карму до возможности «не более одного коммента в сутки», и мне ещё около недели придётся ждать, чтобы опубликовать третью часть «комми», напишу-ка я СЮДА обзорную заметку по статьям на Хабре. Впрочем, нет: пошлю-ка я её в Песочницу! Раз уж такие идиотские правила здесь придумали — пущай модераторы отдуваются! Хотя не уверен, что мне вообще можно писать в Песочницу, если я хоть такой кастрированный доступ имею… да, похоже, что нельзя! Умные люди бедной киске не дают украсть сосиски.(с) Ладно, напишем сюда… :)
Ух ты! У меня карма с рейтингом сравнялась: и там, и там по -42, Ох уж эти «умные люди»… :)
Обзор заметок на Хабре
Разумеется, лишь тех, которые на глаза попались и чем-то меня заинтересовали. Речь, собственно, о программировании.
Логи фронтенд-разработчика Хабра: рефакторим и рефлексируем
Мне всегда было интересно, как устроен Хабр изнутри
Абсолютно безразлично! А вот СНАРУЖИ порядок в хабах навести не мешало бы — проблема давно перезрела! Это же просто свалка!
Чем быстрее вы забудете ООП, тем лучше для вас и ваших программ
люди должны осознать ошибочность ООП и знать решения, которые можно использовать вместо него.
Шарахаемся из одной крайности в другую? Знакомо…
Данные важнее, чем код
Детский сад! Данные вполне могут сами быть кодом, а код крайне желательно иметь независимым от «цели, которой нужно достичь».
Аха, понятно: опять ООП рассматривается как ООП Страуструпа, а про ООП Маккарти никто уже и не вспоминает. Между тем, даже в комментах к этой заметке написано: С++ это не ООП, и сам Страуструп об этом писал в своей книжке.
Повсюду графы
ЩАЗ! Либо жалкие деревья, либо даже табличная эмуляция.
Давайте взглянем на определение инкапсуляции: Инкапсуляция — концепция ООП, связывающая данные и функции для манипулирования этими данными, позволяющая защитить их от внешнего вмешательства и неверного использования. Инкапсуляция данных привела к важной для ООП концепции сокрытия данных.
Господи, неужели так изуродовали определение за эти годы?! Инкапсуляция, в моём понимании, есть возможность абстрагироваться от несущественных (в данный момент) деталей чего-либо.
Хоть реляционная структура данных и не всегда бывает наилучшей, она обычно достаточно гибка.
Ну-ну… много раз писал? «Данные могут быть либо сложными, либо реляционными».
Обычно если данные имеют значительный объём, моя структура близка к базе данных.
Реляционной? Ну да, разумеется…
концепция Customer — это всего лишь набор данных в табличной форме
А туда же, «повсюду графы»…
А бизнесу нужны только деньги, ничего кроме денег. В программировании деньги в основном зарабатываются на рекламе. Все эти поисковики, мессенджены и пр. заточены на втюхивание китайских товаров.
И программистам нужно изображать собственную значимость, собственную востребованность — на любом дерьме!
Правильные языки никому не нужны, энтузиасты без финансирования даже если сделают, без агрессивного продвижения никто не будет такой язык использовать.
Именно! Ещё в феврале 2001 года я писал:
Допустим, кто-то напишет крутейший язык, супер-компилятор с него — и что? Кто это может оценить? Десяток-другой профессионалов? Ну, купят они его. А остальные — нет. Остальным надо, чтобы он, скажем, операторы работы с БД содержал, редактирования реестра, понимал всё написанное (причем, чайниками) на всех других языках, на дудке играл и т.д. Короче, нужно много красивых слов, за которыми может (что лучше всего) вообще ничего не стоять. Только тогда можно рассчитывать на хоть сколько-нибудь массовый спрос. А создатель действительно хорошего языка просто разорится! Что бы я посоветовал: сделать отдельно ядро для профи, отдельно (хотя это не говорить) остальную лапшу.
Почему нельзя сделать нормальный вменяемый язык для фронтенда с контролем типов? Вот и выросло поколение горе-программистов, не понимающих, зачем нужен статический контроль типов, проверка используемости процедур (или, как сейчас модно говорить, методов). Объяснять таким полезность контроля равносильно попытке объяснять глухому от рождения величие классической музыки. И это не их вина, это их беда.
Ну да, что-то в этом духе…
Может быть, требования к срокам и стоимости разработки стали жестче и теперь нельзя шлифовать код до идеала?
Сроки при разработке качественного продукта как раз СОКРАЩАЮТСЯ! Проблема в другом: большие деньги можно заработать (точнее, украсть) лишь на многократном выпуске дерьма! Билл Гейтс — классический тому пример.
Инкапсуляция это когда объект знает только про себя и не дает никому другому знать о себе. Вы ведь так это понимаете?
КАТЕГОРИЧЕСКИ не так! Задолбали уже все эти секреты и другие шпионские страсти! Ту же инкапсуляцию — прекрасная и полезная техника! — изуродовали до неузнаваемости! Да и в обсуждении потоком идут все эти «class Player, class Monster, attackPower, CombatManager, Герой, Меч, Злодей»… короче, [программисты] все умерли.(с)
ООП требует передавать повсюду длинные списки аргументов или непосредственно хранить ссылки на связанные объекты для быстрого доступа к ним.
Бред Сивой Кобылы! Плюс очередной холивар про goto, да ещё со ссылкой на Вирта. Объясняю. в стотысячный раз: goto — это ХОРОШИЙ инструмент! Несогласным предлагаю написать что-нибудь на ассемблере без jmp. А вот эти долбаные эксепшены — это дерьмо! Как идеологически, так и для практического применения.
Всегда относился с недоверием к статьям из серии «Почему вы не должны...». Лучше расскажите как стоит делать правильно.
Вот под этим подписываюсь руками и ногами! А про ООП когда-то очень хорошо сказал много лет назад один очень сильный программист: Объектное (в оригинале «визуальное») программирование создаёт у чайника иллюзию, что он тоже программист.
Трудно быть мейнтейнером проекта Open Source
Некоторые люди — полные придурки. Они повсюду, это естественно. По-моему, в программировании хороших людей намного больше, чем в других областях. Но всегда есть какой-то процент абсолютных мудаков. Это проблема — даже один токсичный мудак может долго отравлять проект не только своим присутствием, но даже и после бана. Им не лень ходить на релевантные ресурсы и всем рассказывать, насколько плохой проект X и какой мудак его автор.
И здесь подпишусь, за исключением «в программировании хороших людей намного больше». :)
Современные возможности C++, о которых надо знать всем программистам
Не читая говорю: НИ ОДНОЙ нет! Однако, проверим… :)
С тех пор, как в C++ 11 появилось ключевое слово auto, жизнь программистов стала легче.
Не «программистов», а «быдлокодеров», которым «не нужно снова описывать длинные объявления».
Лямбда-выражения — весьма полезный инструмент для тех случаев, когда в коде нужно выполнить какую-нибудь небольшую операцию, но для этого не хочется писать отдельную функцию.
См. выше.
Выражения инициализации переменных внутри конструкций if и switch
Вот НАХРЕНА это нужно? Мало приключений на свою задницу?
Выполнение вычислений во время компиляции с использованием constexpr
О, Господи! У кого какие проблемы при работе с препроцессором — поднимите руки!
Структуры данных tuple (кортеж) представляет собой коллекцию значений разных типов фиксированного размера.
Да? А struct чем провинился? Тем более, что элемент структуры МОЖЕТ быть структурой, а вот с tuple этот номер не пройдёт!
Умные указатели
Вот просто за одно название яйца бы оторвал! Если бездари криворукие неспособны работать с указателями, то это вовсе не означает, что указатели надо изымать из языка или, тем более, заменять всяким кастрированным убожеством. Это даже не читая, что «они дают гарантию безопасности по исключениям» — за исключения ещё одну пару яиц оторвать бы надобно!
Итоги
Никаких «новшеств C++» нет, И БЫТЬ НЕ МОЖЕТ! Ибо язык — дерьмо! Единственное, что у него положительного по сравнению с Си — строчные комментарии.
Матрёшка Си. Слойная система языка программы
А программирование уже преподают в школе и скоро начнут в детском саду.
Ну да: программисты вымерли — стали преподавать программирование. Строго по схеме: «Кто умеет — тот делает, кто не умеет — тот учит».
Речь соответствует человеческому мышлению.
Гениально! Ладно уж: раз начал — дочитаю…
Дочитал (точнее, долистал) — примерно такая же ахинея до самого конца. Как там у классиков: «Слушая твои стихи, особенно отчётливо понимаешь, что Пушкин умер».
Особого упоминания заслуживает язык MySQL.
Точно! Как же без этого дерьма? :) Тем более, что MySQL, насколько я помню — это РСУБД, а никакой не «язык».
Zenitchik
19.05.2019 16:41Ибо язык — дерьмо!
Чёткий симптом нуба.
Языков-дерьма не бывает. Это знает каждый, кто знает хотя бы пару их.
rybvv Автор
19.05.2019 21:39+1AndreyZavarin
Не годится. Во-первых, это ДРУГАЯ задача — нахождение кратчайшего пути, а надо искать гамильтонов цикл. Во-вторых, прикиньте размер таблицы для графа хотя бы в миллион узлов, а также время хотя бы на её заполнение. В-третьих, какая разница, какая там из экспонент быстрее? Нам нужен именно полином, причём невысокой степени — мы же практики! :)
Zenitchik
Чёткий симптом нуба. Языков-дерьма не бывает. Это знает каждый, кто знает хотя бы пару их.
Чёткий индикатор дилетанта-позёра. К тому же, не дружащего с логикой: если кто-то знает пару языков (или даже сотню) он НЕ МОЖЕТ знать, что «языков-дерьма не бывает». В ПРИНЦИПЕ не может! Что касается меня, мне доводилось программировать на трёх ассемблерах (Intel, PDP и БЭСМ), алголе, паскале (кстати, КЛАССИЧЕСКИЙ пример языка-дерьма!), фортране, бейсике и нескольких других. И я года два вёл на программистском форуме ветку «C vs C++», где утверждал, во-первых, что указатель на структуру покрывает все «классовые» потуги Страуструпа как бык овцу и, во-вторых, что я на чистом C повторю ЛЮБЫЕ действия, написанные на «плюсах», а вот то, что я сам напишу на чистом C, повторить на «плюсах» не сможет никто! Ну и про Паскаль где-то что-то валялось… ну вот, например:
Отдельно нужно сказать о Паскале. Язык — откровенное дерьмо, что бы там ни говорил Юра Ягупов про Воспета будет красота Pascala на сцене легендарного La Scala. Если посмотреть на отличия языков C и Pascal, поражает, что буквально всё сделано с точностью до наоборот (передача параметров, восстановление стека, вывод и т.п.). И все до единого отличия в пользу C! Мы не касаемся работы с указателями — это просто детский лепет. А как насчёт возможности декларировать функции с произвольным числом аргументов, типа printf, объявлять имена структур без уточнения их содержимого, возможность переходить на следующий case (case without break), определение размера массива по инициализации, возможность описывать extern, локализованные в блоке? Но самый яркий пример: нам как-то пришлось оформить нашу шахматную программу (написанную на чистом ассемблере) в виде функции для другой программы, написанной на Паскале. Восхитительно! В полностью отлаженной программе появилось более тысячи ошибок (!!!) Главная прелесть такая: один ассемблерный модуль содержит переменную, предназначенную для совместного использования с другим ассемблерным же модулем. Соответственно, там стоит PUBLIC. И Паскаль начинает ругаться на этот PUBLIC! ДА КАКОЕ ТВОЁ СОБАЧЬЕ ДЕЛО!!! Короче, Вирт ничего не понимал в программировании — по крайней мере, в период разработки языка. Отсылаем также к статье Кернигана «Почему Паскаль не является моим самым любимым языком программированя». Приведём только одну фразу оттуда: «Три из четырёх известных мне транслятора с языка Паскаль написаны на C».
Кстати, там же: Филипп Кан когда-то изрёк: «Программировать на Бэйсике — вредно как курить». Вот Вам ЦЕЛЫХ ТРИ языка-дерьма! Хотя лично я в «Васик» камень не брошу.
Ах, да — продолжение по графу-миллионнику:
0/64 N=5555555/1 L=79506323.00 (724/1048576) T=252973.5 sec
73024/64 N=5555555/1687 L=79127196.00 (477/1048576) T=271893.0 sec
Пошла глубина 64 — судя по всему, последняя. Ну, может на 128 запрыгнет, не знаю. В любом случае, скоростной УЖЕ уронил бета-границу в 7515 раз — почти на 4 порядка! Ну, где там «умные люди», обосравшие мой скоростной до оценки -41? Молчите, господа? То-то же! ;)Zenitchik
19.05.2019 22:50+1О-ё… Вы печислили такие мелочи, которые даже недостатками язык не поворачивается назвать.
Интересно, какова Ваша реакция на Forth или LISP.
Geenwor
Какое, однако, у Вас впечатляющее начало предыдущей статьи!