Есть один карточный трюк, который запомнился мне навсегда. Вот его краткое описание: доброволец выбирает карту и запечатывает её в конверт. Затем фокусник предлагает добровольцу выбрать чай. У него есть десятки коробок чая, и все они упакованы в пластик. Доброволец выбирает одну из коробок, срывает обёртку и выбирает один из упакованных пакетиков с чаем. Потом он вскрывает упаковку, и… внутри оказывается его карта.
Если вы не хотите знать, в чём хитрость этого трюка, то дальше не читайте.
Секрет трюка прозаичен, но меня он привёл в восторг. К выбору карты добровольца подталкивают. Однако выбор из этих десятков коробок с чаем на самом деле свободный, и выбор чайного пакетика внутри коробки тоже делается свободно. Здесь нет никакой ловкости рук: фокусник не касается коробок или выбранного добровольцем чайного пакетика. Карта на самом деле находится внутри этой упаковки чайного пакетика.
Вся хитрость заключается в подготовке. Перед выполнением фокуса фокусник покупает десятки коробок чая, вскрывает каждую и разворачивает каждую упаковку с чайным пакетиком. Кладёт в каждую упаковку тройку крестей. Снова запечатывает упаковку. Возвращает упаковки обратно в коробку. Снова запечатывает каждую коробку. И повторяет так сотни раз. На это уходят часы, может быть, даже дни.
«Фокусом» это является именно потому, что такая подготовка выглядит настолько скучной, настолько невозможно монотонной, что когда мы видим трюк, то не можем представить, что кто-то проделал бы столь скучную работу, чтобы добиться такого простого эффекта.
Теллер рассказывает об этом в статье о семи секретах магии:
Вас обманет фокус, если в него нужно вложить больше времени, денег и труда, чем захотели бы вложить в него вы (или любой другой здравомыслящий зритель). Мы с моим напарником Пенном однажды достали 500 живых тараканов из цилиндра, стоявшего на столе шоу Дэвида Леттермана. На подготовку этого трюка мы потратили несколько недель. Мы наняли энтомолога, предоставившего нам медленно движущихся тараканов, которые хорошо бы смотрелись на камеру (те, которые живут в наших домах, не будут ждать, пока оператор успеет взять крупный план). Энтомолог научил нас, как доставать насекомых, не вереща при этом, как девятилетние девочки. Затем мы изготовили из пенопласта потайную перегородку (это один из тех немногочисленных материалов, за которые не могут уцепиться тараканы) и придумали хитрую процедуру установки перегородки в шляпу. Вы считаете, что здесь больше возни, чем того стоит фокус? Для вас — возможно, но не для фокусников.
[То самое видео про тараканов с таймкодом, начало трюка на 7:23]
Новички в технической отрасли часто спрашивают меня, в чём секреты успеха в ней. На самом деле их не так много, однако этот секрет — готовность делать нечто столь ужасно монотонное, что это покажется магией — работает и с технологиями.
Наша отрасль одержима автоматизацией, упрощением процессов и эффективностью. В одном из фундаментальных для инженерной культуры текстов Ларри Уолла «Достоинства программиста» упоминается и лень:
Лень: качество, заставляющее вас предпринимать огромные усилия для снижения суммарных затрат энергии. Она заставляет вас писать облегчающие труд программы, которые оказываются полезными для других людей, и документировать написанное вами, чтобы не пришлось отвечать на слишком много вопросов.
Я не могу не согласиться: возможность перекладывать монотонные задачи на программу — одна из лучших особенностей знания кодинга. Однако иногда проблемы нельзя решить автоматизированием. Если ты готов к скучной, однообразной работе, то в глазах других ты будешь выглядеть волшебником.
Например, однажды я пришёл в команду, которая поддерживала утопавшую в багах систему. У них было что-то около двух тысяч открытых баг-репортов. У багов не было никаких меток, категорий и приоритетов. Команда не могла прийти к договорённости о том, какие проблемы нужно устранять первым делом. В результате они, по сути, выбирали баги случайным образом, но было непонятно, важна ли каждая отдельная проблема. Новые баг-репорты невозможно было обрабатывать эффективно, потому что поиск дубликатов оставался практически невозможным. Поэтому количество открытых тикетов продолжало увеличиваться. Команда месяцами буксовала на месте. Передо мной поставили задачу решения этой проблемы: снять команду с мели, обратить тренд количества открытых тикетов, найти способ постепенно снизить его до нуля.
И я использовал тот же трюк, что и фокусник, то есть трюка никакого и не было: я занялся работой. Я распечатал все проблемы — по одной странице на каждую проблему. Я прочитал каждую страницу. Я занял огромный кабинет и начал раскладывать на полу стопки листов. Я писал на стикерах метки и приклеивал их к стопкам. Я перемещал страницы из одной стопки в другую. Я записывал на маркерной доске длинные столбцы номеров тикетов; я представлял себя героем Бена Аффлека из фильма «Расплата». Я провёл в этом кабинете почти три недели, и вышел из него тогда, когда просмотрел, пометил, категоризировал и приоритезировал каждый баг.
Сразу после этого тренд пошёл в обратную сторону: мы мгновенно смогли закрыть несколько сотен тикетов как дубликаты, а на оценку новых репортов теперь требовались считанные минуты, а не целый день. Если не ошибаюсь, чтобы снизить количество до нуля, понадобился год или больше, но процесс был достаточно спокойным. Люди говорили, что я совершил невозможное, но они ошибались: я просто сделал нечто столь скучное, что никто другой не хотел этим заниматься.
Иногда программирование кажется магией: ты произносишь какое-то таинственное заклинание, и армия роботов исполняет твою волю. Но иногда магия рутинна. Если ты готов и желаешь заниматься скучной работой, то сможешь выполнить невозможное.
Наша компания предлагает облачные серверы для любых задач и на любой операционной системе. Создавайте собственные конфигурации в течение минуты, минимальный тариф — всего 6.5 рублей в день!
Зарегистрируйтесь по ссылке выше или кликнув на баннер и получите 10% скидку на первый месяц аренды сервера любой конфигурации!
amarao
Не масштабируется, к сожалению. Если на N багов нужно было 3 недели, то на 100*N нужно уже больше 5 лет.
Kanut79
Я бы сказал что с определённого количества незакрытых багов уже проще переписать систему с нуля. И 200000 багов это уже точно достаточно :)
А так, да что-то здравое в статье есть. То есть очень часто "скучная работа" это решение проблемы. Но точно так же очень часто её никто не хочет делать.
amarao
Кстати, в статье не описана (точнее, просто упомянута) ещё одна важная вещь: после разгребания авгиевых конюшен каким-то образом нужно было не создать их снова.
Я в своей жизни несколько раз так делал (разгребал конюшни до самого дна). Ни разу мне не удалось в тех случаях добиться, чтобы они не создавались снова, так что у меня есть некоторое чувство выгорания в отношении таких ситуаций.
Nikobraz
А сколько их создастся в процессе тоже еще не считали.
fougasse
Проще, если никто не пользуется.
Kanut79
Ну это естественно зависит от конкретной ситуации. Но если у вас огромное количество багов и оно ещё и непрерывно растёт, то на мой взгляд переписать это вполне себе вариант.
И естественно что миграция с одной версии на другую это не то чтобы тривиальная задача. Но и не то чтобы в принципе нерешаемая.
mrise
Я всегда думал, что переписывать систему имеет смысл чтобы избавиться от ограничений предыдущей системы, а не чтобы очистить беклог. Если эти 200к багов проявляются из-за ошибочной или устаревшей архитектуры — да, согласен, это разумно. Но в статье о этом ничего не сказано. А если эти сотни тысяч багов — минорные глюки, которые проявляются в очень специфических условиях?
Так же стоит заметить, что если никто не хочет даже читать эти 200к задач, то кто удостоверится, что баги из старой системы не будут с хирургической точностью перенесены в новую, потому что «Ой, а я думал, это должно так работать. Всегда же так работало.»
Мне кажется, вы думаете о какой-то конкретной системе, которую, вполне возможно, давно стоит переписать. Но в общем случае это, как мне кажется, довольно спорный совет :)
Kanut79
Баги это на мой взгляд не то чтобы относятся к бэклогу. Но это конечно зависит от того как дефинировать этот самый бэклог.
И опять же на мой взгляд вы вряд ли наберёте 200 тысяч или тем более 2 миллиона багов если у вас нет каких-то серьёзных проблем с архитектурой/технологией.
Ну за исключением случаев когда у вас просто работают абсолютно некомпетентные люди и их не заменить. Но в такой ситуации уже наверное ничего не поможет...
К счастью я в своей профессиональной карьере не встречал даже системы с 2000 открытых багов находящихся хотя бы примерно в поле моей ответственности или поле ответственности моей команды/отдела :)
inkelyad
Пример придумать легко. Берем какую-нибудь буровую платформу. Целиком, не только софт, что там в чипах живет. Я подозреваю, что 2 миллиона багов и требований (опять же, не только софтовых) ко всей этой конструкции — это будет даже мало.
Можно повторить то же самое для любой большой и дорогой железки, которую десятками лет строят.
Kanut79
Я думаю что даже в таких крупных системах вы не найдёте в сумме 2 миллиона багов. 200 тысяч может быть и возможно, но на мой взгляд очень маловероятно.
Ну и когда мы говорим о таких системах, то вряд ли вся эта система целиком находится в зоне ответственности одной команды/отдела/фирмы. То есть вы вряд ли увидите эти 200 тысяч багов собранными где-то в одном месте и так чтобы их все должны были исправлять одни и те же люди.
Firz
Да 200 000 багов это что-то нереальное, если только это не автогенерация какая-нибудь. Даже если находить и вносить в систему один баг каждые 30 минут, понадобится 34 года нонстоп работы по 8 часов в день без перерывов и выходных.
HellWalk
И это как раз самая проблема.
Баг, который легко воспроизводится со 100% шансом — это просто. А вот баг, который появляется раз в месяц, при непонятно каких условиях (слишком много входящих и сложная логика), и непонятно как его воспроизвести — вот это жопа.
LoadRunner
А распараллелить если?
amarao
А оно не параллелится. Как вы будете сортировать баги на похожие, если вы не видите все? Более того, ?(n) — это моя фантазия. Возможно, там хуже, чем ?(n), например, ?(n?). В этой ситуации на 100-кратный объём нужно уже 534 человеко-года...
LoadRunner
Каждый сортирует по категориям (заранее договориться об их количестве и какие они).
После окончания сортировки в пределах одной категории ищутся дубликаты.
Да, это не ускорение работы в два раза, но всё равно ускорение, так как с итогом первого этапа уже можно начинать работать, пока не закончен второй.
amarao
А как вы можете договориться о категориях, не зная, что именно вы категоризируете?
Для начала нужно определить категории, а для этого нужно сканирование.
На самом деле мы можем сделать простую штуку: мы знаем, что лучший алгоритм сортировки, использующий сравнение, не может быть быстрее, чем ?(n*log n). Теоретически, сортировку можно параллелить (тем же quicksort'ом), но для начала надо придумать функцию сравнения, а она для сложных объектов (вида багрепорта), мягко говоря, нетривиальна.
Если бы она была тривиальна, то первой бы задачей было выявление дупликатов (после чего последующая обработка становится проще). Но она не тривиальна, и выработка подходящей метрики для описания/категоризации/сортировки требует проверки этой метрики на всех багрепортах.
Можно даже примерно оценить алгоритмическую сложность. Алгоритм: читаем все багрепорты, как только в голове созрела метрика (каждые C репортов) проверяем эту метрику на существующих (прочитанных багрепортах) и пытаемся применить ко всем остальным. Она фейлится на каком-то багрепорте. Каждая следующая метрика фейлится на всё более позднем багрепорте, т.е. с каждой новой версией надо проверять больше, а придумывать меньше.
В целом получается, что нам надо примерно ?(n*n) просмотров багрепортов для создания разумной системы классификации.
Что делает из 3 недели на N багрепортов 500+ лет для 100*N багрепортов.
inkelyad
Я подозреваю, что если объектов действительно много и они хорошо перемешаны, можно заране не договариваться. Просто после того, как каждый выделит категории из своей (достаточно большой) кучки, то, скорее всего, окажется, что эти категории в достаточно сильной степени совпадают.
amarao
Итог:
животные делятся на:
inkelyad
Однако классификацию книг как-то сумели сделать, не сравнивая каждую книгу с каждой (те самые ?(n*n))
amarao
Вот классификация. Она чуть лучше, чем верблюжья шерсть, но...
000 ОБЩИЙ КЛАСС
100 ФИЛОСОФИЯ И ПСИХОЛОГИЯ
200 РЕЛИГИЯ
300 ОБЩЕСТВЕННЫЕ НАУКИ
400 ЯЗЫК
500 ЕСТЕСТВЕННЫЕ НАУКИ И МАТЕМАТИКА
600 ТЕХНИКА (ПРИКЛАДНЫЕ НАУКИ)
700 ИСКУССТВО ИЗОБРАЗИТЕЛЬНОЕ И ДЕКОРАТИВНОЕ ИСКУССТВО
800 ЛИТЕРАТУРА И РИТОРИКА
900 ГЕОГРАФИЯ И ИСТОРИЯ
Теперь вопрос, в какую категорию попадают, например, ноты?
Vsevo10d
Никогда не мог для себя решить, что хуже — УДК, РЛС или ОКВЭД.
zetroot
КЛАДР/ФИАС туда же добавьте
Bellerogrim
Общий класс? :)
amarao
А руководство по жонглированию?
Xobotun
Я бы ставил на 700 искусство. :D
Там же должны быть подкатегории, это же
7\d{2}
.eimrine
Мне не хватает ума чтобы понять ни статью, ни ваши к ней комментарии, но ноты это конечно же математика. Потому что по факту, и музыка и математика были открыты Пифагором в качестве одного акта творения: до тех пор пока он не продемонстрировал современникам октаву и прочие музыкальные интервалы, у современников как-то и не было причин интересоваться математическими операциями как чем-то имеющим отношение к реальному миру.
amarao
А тексты песен к этим нотам?
Keeper7
Литература. Туда же всю поэзию до кучи.
amarao
А танцы к этим песням?
Надеюсь, вы чувствуете "офигенность" классификации.
inkelyad
Так это именно вопрос цели классификации.
Именно эта библиотечная, насколько я понимаю, была придумана во первых, давно и, во вторых, больше для удобства и однозначности расстановки по шкафам. А удобство поиска в каталоге 'найти что-то по теме' — это немного меньше учитывали.
В современных условиях можно категории для нужд хранения просто лексикографически по ISBN использовать, а поиск — полнотекстовым индексированием делать.
TheSprightlyDuke
Предположу, что это могло бы зависеть (может даже и зависит) от того, что в основе. Грубо говоря, что «большими буквами».
Xobotun
Возражаю, это композиторское искусство — математика. Ноты — лишь язык записи.
/s
То есть 700, 500 и 400 одновременно. :/
eimrine
Я всегда думал что математика — язык и ничего более. До сих пор не понимаю, почему её не учат как гуманитарную науку, чтобы зубодробительные вычисления — только технарям, а историю математики, Латех и устоявшиеся обозначения типичных вещей — совершенно всем. С этой точки зрения ноты и композиторское искусство — абсолютно неделимые вещи.
dimaviolinist
«музыка и математика были открыты Пифагором»
Честно?
А вот до него ничего не было.
eimrine
Были некоторые знания у египетских жрецов, руководством которых были построены пирамиды, как минимум это тригонометрия. Но поскольку на данные знания был наложен нехилый такой пэйволл с NDA, а доставать их из египетского междусобойчика пришлось методом Прометея — то логичнее считать открывателем (не путать с изобретателем) математики именно Пифагора, а не анонимных египетских жрецов-копирастов. Даже если какая-то торговля и была до Пифагора, не он же открыл числа в конце-концов, разделение чисел на рациональные и иррациональные в торговле уже не нужно, зато нужно в музыке, ведь ноты с иррациональным соотношением частот звучат всегда диссонансно. После понимания иррациональных чисел появилось понимание деления, что открыло возможность античным грекам замерить окружность Земли, вычислить расстояние до Солнца, и дальше короче завертелось.
Насчёт музыки, музыкальные инструменты точно были и до Пифагора, но классификация звуков по высоте с сопутствующей теорией интервалов вроде как до Пифагора отсутствовала в принципе.
farafonoff
Очень просто ноты: 780 — Музыка; Жонглирование думаю в 790 Развлекательные и исполнительские виды искусства.
amarao
А почему музыка входит в изобразительные искусства (7)?
inkelyad
Чтобы храниться в той части библиотеки, что в здании факультета изящных искусств находится.
amarao
А почему тогда тегория не "искусство"?
inkelyad
А кто бы сказал. Tут (Wikipedia): 'Class 700 — Arts and recreation'
EDIT: Пройдя по ссылкам на оригинальную статью (gutenberg.org)
amarao
А, это ещё и прелести перевода. Спасибо.
Wizard_of_light
УДК 666 — стекольная и керамическая промышленность. Не боги горшки обжигают
Veselyi_kot
700.
А для решения проблемы вводится институт тэгов. Автор присваивает книге кроме абстрактной категории и чуть менее абстрактного жанра ведро уже вполне конкретных тэгов от общих к частным (general tag «Попаданцы», targeting tag «Попаданцы в прошлое»), те, на которых менее N вхождений за месяц с первого появления автоматически удаляются для предотвращения захламления.
Так работает, например, каталогизатор author.today, и работает вполне успешно.
Тот же принцип транспортабелен куда угодно ещё, в те же багрепорты с выбором тэгов внутри категории от более популярных к менее популярным (пример от балды: категория «интерфейс», тэги «мышь», «зависание», «основной функционал», и специалист может присвоить очерёдность даже не читая).
amarao
Спасибо за пример. Это хороший алгоритм, но если вы попытаетесь его выполнять руками, то вам придётся (с заменой "месяца" на "шутк") проверять вот это "N", т.е. у вас будет как раз N*N.
Veselyi_kot
Простейший, неоптимизированный, но колхозно-рабочий пример: на каждый тэг — создается отдельная таблица БД с тремя полями — названием книги, ссылкой и датой внесения в каталог, плюс общая таблица тэгов с названиями тэгов и прозрачными ссылками на эти подтаблицы (так, чтобы запрос типа «ТэгБаза.Тэг42.ИменаКниг [1, 100]» незаметно для пользователя перебрасывало в таблицу Тэг42, и вся логика шла через общую базу).
Дальше на все это дело вешаем скрипт, первого числа каждого месяца сносящий все подтаблицы, у которых дата создания больше месяца и меньше десяти записей.
P.S. пардон за синтаксис запроса, но нормальные БД уже наглухо забыты в памяти в пользу корпоративной «самописки», на которой всё стоит.
P.S.2. Для того же самого руками и в оффлайне: заводим картотеку с лотками-тэгами и подписью маркером на скотче. В конце месяца на глаз смотрим, где карточек маловато и вытрясаем их оттуда, отдирая скотч — лоток свободен.
Вообще для меня странно, что тэги не ввели ещё в доинтернетную эпоху.
amarao
А, так если есть база данных, то выполнение алгоритма мы можем переложить на неё, без проблем. Там и сортировка, и выборка за O(1) по индексированным полям, и невероятные возможности.
Но исходный пост же был про "распечатать и вдумчиво перекладывать по стопочкам". При этом тривиальные задачи становятся весьма и весьма сложными для исполнителя. Я про это и говорил — ручная реализация алгоритмов, применимых на больших данных (больше, чем голове может удержаться), это эквивалент запросов в базу, в которых промежуточное представление больше оперативной памяти. Можно, но сложно.
QDeathNick
Сомневаюсь, что по любой существующей классификации книг можно хотя бы найти дубли. Одну книгу разные библиотекари могут тегировать по разному.
Veselyi_kot
Именно поэтому — нужен фрагмент
Все расставляют от балды и как можно больше, потом оставляем самые актуальные. Грубо говоря, в «Попаданцы в параллельные миры» 10 вхождений будет, а условный тег «плоская земля» не приживется.
К этому же прикрутить подсказчик и детектор дублирования тега по ключевым словам (начинаешь набирать «попаданцы», сразу вылезает веер уже имеющихся тегов с этим словом).
MetromDouble
Есть децентрализованной алгоритм и для такого. Только вот не знаю, будет ли кто-то заморачиваться — общая для всех карта категорий, каждый может добавить свою, но необходимо одобрение других участников при помощи голосования (2/3 от количества людей голосуют ЗА)
P. S. Хотя ваш пример немного надуманный, при приёме людей на работу все таки важно оценивать их адекватность, чтобы в таких примерах не надо было про умолчанию предполагать их тупость
morijndael
Можно сначала разделить баги на две-три больших категории. Это будет О(n), но затраты на одну классификацию будут минимальны. Затем уже параллелим каждую категорию, выделяем подкатегории, их каждую тоже параллельно обрабатываем. Уже при обработке подкатегорий нужна будет единая система тегов, но так как первый сортировщик просмотрел все репорты, он сможет её составить, пока идёт сортировка на подкатегории.
Дубликаты вычислить по пересечениям тегов
amarao
Предполагается, что у сортировщика такая память, что он помнит всё. Если не помнит — вот тут вот и начинается n*n.
inkelyad
n^2 не нужно.
Грубо говоря, у нас есть операция попарного 'сравнения': "Относится ли issue A к той же группе, что issue B".
Дальше смотрим, как строится бинарное дерево сортировки. Там n^2 попарных сравнений, если я правильно помню, не требуется. Если приблизительно похожим способом генерировать категории (то что похоже — в левую кучку, не похоже — в правую. Время от времени issue-корень-категории меняем, чтобы перебалансировать глубину классификации) — то будет приблизительно с той же сложностью.
amarao
Когда у нас уже существуют группы, разложить issue по дереву/списку групп — это либо ?(n), либо ?(log n), либо даже ?(len(group)).
Тут же сиутация о другом. Формирование осмысленной (полезной) группы — это проверка применимости группы в сравнении с остальными группами и багами (т.е. n). Получается, что для множества групп мы имеем
n*g
операций. Если g (число групп) функция от n, то получаемn*n
.inkelyad
Зачем со всеми остальными то? Это как утверждать, что при сортировке надо очередной элемент сравнивать со всеми остальными, хотя это далеко не так. Нет, понятно, что для чисел и прочих подобных им само отношение порядка помогает. Но группировки требование " каждый-с каждым" тоже сомнительно.
В моем примере: если в текущем корне дерева некий баг от которого настал конец света — то в левую сторону от него будут все похожие баги (т.е. которые тоже к концу света приводят), с дальнейшим дроблениям по причинам. А в правую сторону — те, что не приводят. И сравнивать первые со вторыми как бы уже не надо.
Тут нужно понимать, что какую-то группировку мы так или иначе получим. Хотя бы в виде 'номер категории — последняя цифра номера бага'. Берем и пользуемся.
Если нам 'какая-то' не нужна, и к ней есть некие требования по 'разумности', то эти самые требования сразу лимитируют, что с чем сравнивать стоит или не стоит.
MetromDouble
Это задача кластеризации. Если задачи более-менее хорошо перемешаны перед разделением всего пула на нескольких разработчиков, то кластеры будут примерно одинаковые у всех. Можно сделать промежуточную синхронизацию, скажем, после обработки 10% от пула. Дальнейшее расхождение уже не будет слишком большим
amarao
Каким образом вы синхронизируете опыт мышления и выбранный алгоритм кластеризации между людьми?
Один решил поделить баги на
принадлежащих Императору,
прирученных,
набальзамированных,
сказочных,
второй поделил на
бегающих как сумасшедшие,
бесчисленных,
бродячих собак,
прочих
третий поделил на
нарисованных тончайшей кистью из верблюжьей шерсти,
разбивших цветочную вазу,
похожих издали на мух.
И?
luckman
В реальности категории всё-таки будут пересекаться, если каждый владеет предметной областью. Для определения категорий достаточно просмотреть небольшой процент дефектов.
arheops
Проблема не в том, что каждый НЕ владеет предметной областью.
Проблема в том, что каждый владеет ей ПО РАЗНОМУ.
Вы не можете распаралеллить их на одинаковых людей, потому будут разные критерии. И БОЛЬШИНСТВО критериев НЕ совпадет.
kukovik
Список категорий можно сразу сделать общим и пополняемым.
luckman
Не очень понял про сравнение задач категоризации и сортировки. Первую вполне можно решить за линейное время, если каждый отдельный объект мы умеем категоризировать за O(1).
+ В реальности вам не нужно фейлить алгоритм при первой же ошибке. Обычно достаточно добавить категорию «другое», куда складываются все фейлы. Главное чтобы её размер не оказался слишком большим.
По итогу почти линейный алгоритм такой:
1. Проходимся по тикетам, составляем список категорий.
Сложность — O(n). причём константа перед n может быть меньше единицы (перебираем не все тикеты, используем категорию «другое»). Также можно распараллелить методом, который выше написал inkelyad
1*) Если первую часть параллелили, нужно собраться и просмотреть все категории, сложность O(k * k), где k — кол-во категорий, k << n (единственная синхронная часть в алгоритме)
2. Проходимся по всем тикетам, категоризируем. Сложность либо O(n), либо O(n * k), в зависимости от скорости определения принадлежности элемента категории. Если вместо категорий — теги, то сложность O(n * k). Параллелится
3. Внутри каждой категории ищем дубликаты. Тут можно выбирать — либо решить за O(t * t) (t — кол-во тикетов в категории), либо применить шаги 1 и 2 с сабкатегориями k' внутри k за O(t * k'). Параллелится по количеству категорий.
amarao
За какое время вы создадите систему классификации?
В операции добавления категории в существующую систему классификации, в общем случае, создание новой категории — это не ?(1), ни в коем случае. Если вы хотите осмысленную, полезную классиф?икацию. Если у вас создание новой категории — это ?(n), то у вас проход по списку issue — ?(n), создание категории ?(n/С), итого, сложность алгоритма ?(n*n)
luckman
В этом алгоритме нет операции добавления категории. Категории определяются один раз на шаге 1 и 1*.
Новые могут добавляться только на шаге 3 при просмотре категории «другое», и обрабатываться, соответственно, только для элементов отсюда.
Да, категоризация будет неидеальна, придётся сделать выбор между квадратичной скоростью и идеальной категоризацией.
amarao
"Проходимся по тикетам, составляем список категорий."
Вот я утверждаю, что операция "составляем список категорий" состоит из добавления новых категорий, одной за одной. Число и тип категорий либо не имеет отношения с содержимому входных данных (является константным), либо зависит от него (и в этом случае добавление категорий — функция от числа входных данных).
Использование sampling тут может помочь только если мы уверены в распределении в исходных данных. Предположим, что у нас 100к багов, среди них есть 100, заслуживающих 5 важных категорий. Сколько должно быть багов просмотрено, чтобы получить эти 5 категорий с (хотя бы) 3 сигма?
luckman
Опять же, рекурсивный алгоритм и категория «другое» решает эту проблему.
100000 багов, на первом шаге просмотрим 1000, выделим 10 категорий
на втором шаге пройдёмся по всем ста тысячам
Предположим 20000 из 100000 попадут в «другое».
На 3 шаге рекурсивно применяем тот же алгоритм, когда будем просматривать категорию «другое» рассмотрим ещё 1000 дефектов оттуда. Выделим ещё 2-3 новые категории для них.
Пройдёмся по 20000 дефектов, из них в «другом» останется 7000 и т.д. до разумного предела
Если предел — 100 багов, то все 5 важных категорий гарантированно выявятся.
UPD. Ну и если константа в первом шаге не очень большая, размер сэмпла можно увеличивать, вплоть до всех 100000 элементов.
amarao
Вы при этом предполагаете, что созданные категории создаются и остаются. Может оказаться, что первая категория — "бальзамированные", вторая "носятся как бешенные", а третья — "принадлежат Императору". А потом появляется категория "издалека похожие на муху".
Если избегать такой системы категоризации, категории надо переделывать после обнаружения неудачности старой модели. Если сохранять наработанную — ну, что ж, "мифические" и "сирены" — две разумные категории для багов.
inkelyad
Как бы не может быть. 100 из 100k — это категория 'прочие' из-за явной редкости.
Хотя, по большому счету, мы во всем этом обсуждении забываем вопрос 'а какой цели эта категоризация служить должна?' и что слово "категория" у нас означает.
Кому какой баг назначим? Значит категорий не более количество человек в проекте.
В каком модуле бага? Значит категорий не больше количество модулей
итд итп.
Как видно, в некоторых вариантах категории вообще создаются не глядя на сами баги.
luckman
> По итогу почти линейный алгоритм такой:
O(n * log(n)) если быть точным. Либо O(n * k * log(n)) при использовании тегов вместо категорий
0xd34df00d
Но полное сканирование не нужно. Берёте рандомный сэмпл, выделяете категории, запускаете воркеров. При обнаружении воркером чего-то плохо категоризуемого есть варианты — от согласования новой категории с другими воркерами до забивания — 1-2 процента ошибок в такой задаче вообще не важны.
amarao
При этом неявно предполагается равномерность распределения важности. Потому что может оказаться, что из 100к багов 95к — это трейсы, а 5к — заполненные человеком багрепорты. Вы делаете sample для 50 багов, они все оказываются трейсами. Ваша система категорий полностью пропускает всё важное (оставшиеся 5к багов, которые и требуют внимания).
Короче, если у вас есть a priori знание про входные данные, то существуют алгоритмы сортировки быстрее, чем ?(n log n). Если нет — требуется как минимум, полное сканирование, плюс раздумия.
arheops
Вероятность выбрать трейс 0.95, на 50 выборках вероятность НЕ попасть на человека — 7.6% всего.
inkelyad
Которые успешно попадают в 5% 'прочие'. Которой категории потом, если уж нас так ручные багрепорты заинтересовали (после сортировки по категориям) и присваивается приоритет 'важная'. Если же ручные багрепорты интересуют больше еще до начала сортировки — то и соответствующая категория создается сразу.
Кроме того, если заранее есть требование 'все что 5% — должно заметить и поместить в собственную категорию', то и размер sample исходя из этого требования подсчитывается.
LoadRunner
Вы решаете абстрактную задачу, я конкретную. О чём спор вообще?
orrollo
параллелится. есть берется бумажка сверху (первая проблема) и у неё выделяется несколько тегов. из них волевым осмысленным решением выбирается один. после чего всем N членам команды раздается K/N тикетов и они отвечают да или нет (правая стопка/левая) — насчет наличия в вопросе выбранного тега. по итогу — стопки справа складываются вместе, стопки слева тоже. Процесс повторяется с самого начала.
И таки да, это скучно, утомительно, но можно и нужно параллелить.
myz0ne
А как работают интернет-поисковики? Вроде задача вполне похожая.
amarao
Интернет-поисковики работают совсем не так. Они не требуют специального человека, который три недели перекладывает бумажки между разными стопками. Вместо этого они делают индекс и смотрят на кросс-ссылки. А ещё на чёртову магию, которую мы не видим, но в любом случае — это автоматизированный процесс.
А тут статья о том, что некоторые вещи можно сделать только вручную, хоть и муторно.
myz0ne
Так в том то и суть масштабирования: делаем автоматизацию. Пишем похожую магию/обучаем МЛ. Баги структурируем по какому-то шаблону. Недостающие данные заполняем мясными роботами. Заполнение по шаблону хорошо параллелится. Как пример шаблона — шаги для воспроизведения, раздел интерфейса/часть функциональности.
Натравяем алгоритм, получаем профит?
Да, дорого, да не имеет смысл делать для задач которые можно сделать одним человеком за три недели. Но если стоит вопрос про 5 лет — можно пойти таким путем. В конце концов, интернет то парсит и каталогизирует не один человек.
Кстати, раньше же вроде был ручной каталог сайтов. Который заменили поисковики. Как пример подобной эволюции.
nixtonixto
Иногда после закрытия одного бага, вылазят сразу несколько новых, которые раньше маскировались закрытым багом…
salkat
А бывает и наоборот
anonymous
Запросто. Дремучий легаси (а здесь судя по описанию именно такой) как правило имеет кучу лихо закрученных зависимостей, в том числе совсем не явных и/или крайне не очевидных. И починив в одном месте запросто можно сломать в другом (и не одном), причём сам чинивший об этом и не узнает. И в итоге будет новая проблема, что делать — откатывать фикс, или чинить новые баги?
Особенно это критично, если чинить надо что-то, что используется во всём проекте, собственно поэтому такие баги зачастую висят годами, так как трогать реально страшно, а новый герой ещё не родился.
Cost_Estimator
Позволю себе придраться.
N багов = 3 недели.
100*N багов = 300 недель.
300 / 52 ? 5.769 лет.
5.769 лет > 5 лет.
Если ваше высказывание верно, то все-таки масштабируется.
amarao
Под словом "масштабируется" подразумевается что-то лучшее, чем ?(n), хотя есть подозрение, что такая задача — ?(n*n).
saboteur_kiev
Легко масштабируется, если посмотреть не на отдельно взятый пример, а на суть того, что человек хотел сказать.
Что очень много волшебных и крутых вещей делается не тогда, когда ты бегаешь по конференциям и ищешь волшебные тулзы которые все сделают за тебя, а когда ты просто садишься и работаешь.
CheatEx
Так создание багов тоже не масштабируется.
wolfy_str
Всё масштабируется. К сожалению, программисты постепенно забывают математику. Если для N нужно 3 недели, то для 100N потребуется как раз 300 недель, что если разделить на 52 недели в год будет как раз больше 5 лет) математика 5 класса, которую вы не заметили