Comments 119
Не масштабируется, к сожалению. Если на N багов нужно было 3 недели, то на 100*N нужно уже больше 5 лет.
Кстати, в статье не описана (точнее, просто упомянута) ещё одна важная вещь: после разгребания авгиевых конюшен каким-то образом нужно было не создать их снова.
Я в своей жизни несколько раз так делал (разгребал конюшни до самого дна). Ни разу мне не удалось в тех случаях добиться, чтобы они не создавались снова, так что у меня есть некоторое чувство выгорания в отношении таких ситуаций.
Проще, если никто не пользуется.
Так же стоит заметить, что если никто не хочет даже читать эти 200к задач, то кто удостоверится, что баги из старой системы не будут с хирургической точностью перенесены в новую, потому что «Ой, а я думал, это должно так работать. Всегда же так работало.»
Мне кажется, вы думаете о какой-то конкретной системе, которую, вполне возможно, давно стоит переписать. Но в общем случае это, как мне кажется, довольно спорный совет :)
И опять же на мой взгляд вы вряд ли наберёте 200 тысяч или тем более 2 миллиона багов если у вас нет каких-то серьёзных проблем с архитектурой/технологией.
Пример придумать легко. Берем какую-нибудь буровую платформу. Целиком, не только софт, что там в чипах живет. Я подозреваю, что 2 миллиона багов и требований (опять же, не только софтовых) ко всей этой конструкции — это будет даже мало.
Можно повторить то же самое для любой большой и дорогой железки, которую десятками лет строят.
А если эти сотни тысяч багов — минорные глюки, которые проявляются в очень специфических условиях?
И это как раз самая проблема.
Баг, который легко воспроизводится со 100% шансом — это просто. А вот баг, который появляется раз в месяц, при непонятно каких условиях (слишком много входящих и сложная логика), и непонятно как его воспроизвести — вот это жопа.
А оно не параллелится. Как вы будете сортировать баги на похожие, если вы не видите все? Более того, Θ(n) — это моя фантазия. Возможно, там хуже, чем Θ(n), например, Θ(n²). В этой ситуации на 100-кратный объём нужно уже 534 человеко-года...
После окончания сортировки в пределах одной категории ищутся дубликаты.
Да, это не ускорение работы в два раза, но всё равно ускорение, так как с итогом первого этапа уже можно начинать работать, пока не закончен второй.
А как вы можете договориться о категориях, не зная, что именно вы категоризируете?
Для начала нужно определить категории, а для этого нужно сканирование.
На самом деле мы можем сделать простую штуку: мы знаем, что лучший алгоритм сортировки, использующий сравнение, не может быть быстрее, чем θ(n*log n). Теоретически, сортировку можно параллелить (тем же quicksort'ом), но для начала надо придумать функцию сравнения, а она для сложных объектов (вида багрепорта), мягко говоря, нетривиальна.
Если бы она была тривиальна, то первой бы задачей было выявление дупликатов (после чего последующая обработка становится проще). Но она не тривиальна, и выработка подходящей метрики для описания/категоризации/сортировки требует проверки этой метрики на всех багрепортах.
Можно даже примерно оценить алгоритмическую сложность. Алгоритм: читаем все багрепорты, как только в голове созрела метрика (каждые C репортов) проверяем эту метрику на существующих (прочитанных багрепортах) и пытаемся применить ко всем остальным. Она фейлится на каком-то багрепорте. Каждая следующая метрика фейлится на всё более позднем багрепорте, т.е. с каждой новой версией надо проверять больше, а придумывать меньше.
В целом получается, что нам надо примерно θ(n*n) просмотров багрепортов для создания разумной системы классификации.
Что делает из 3 недели на N багрепортов 500+ лет для 100*N багрепортов.
А как вы можете договориться о категориях, не зная, что именно вы категоризируете?
Я подозреваю, что если объектов действительно много и они хорошо перемешаны, можно заране не договариваться. Просто после того, как каждый выделит категории из своей (достаточно большой) кучки, то, скорее всего, окажется, что эти категории в достаточно сильной степени совпадают.
Итог:
животные делятся на:
а) принадлежащих Императору,
б) набальзамированных,
в) прирученных,
г) молочных поросят,
д) сирен,
е) сказочных,
ж) бродячих собак,
з) включённых в эту классификацию,
и) бегающих как сумасшедшие,
к) бесчисленных,
л) нарисованных тончайшей кистью из верблюжьей шерсти,
м) прочих,
н) разбивших цветочную вазу,
о) похожих издали на мух.Однако классификацию книг как-то сумели сделать, не сравнивая каждую книгу с каждой (те самые θ(n*n))
Вот классификация. Она чуть лучше, чем верблюжья шерсть, но...
000 ОБЩИЙ КЛАСС
100 ФИЛОСОФИЯ И ПСИХОЛОГИЯ
200 РЕЛИГИЯ
300 ОБЩЕСТВЕННЫЕ НАУКИ
400 ЯЗЫК
500 ЕСТЕСТВЕННЫЕ НАУКИ И МАТЕМАТИКА
600 ТЕХНИКА (ПРИКЛАДНЫЕ НАУКИ)
700 ИСКУССТВО ИЗОБРАЗИТЕЛЬНОЕ И ДЕКОРАТИВНОЕ ИСКУССТВО
800 ЛИТЕРАТУРА И РИТОРИКА
900 ГЕОГРАФИЯ И ИСТОРИЯ
Теперь вопрос, в какую категорию попадают, например, ноты?
А тексты песен к этим нотам?
А танцы к этим песням?
Надеюсь, вы чувствуете "офигенность" классификации.
Так это именно вопрос цели классификации.
Именно эта библиотечная, насколько я понимаю, была придумана во первых, давно и, во вторых, больше для удобства и однозначности расстановки по шкафам. А удобство поиска в каталоге 'найти что-то по теме' — это немного меньше учитывали.
В современных условиях можно категории для нужд хранения просто лексикографически по ISBN использовать, а поиск — полнотекстовым индексированием делать.
Возражаю, это композиторское искусство — математика. Ноты — лишь язык записи.
/s
То есть 700, 500 и 400 одновременно. :/
Честно?
А вот до него ничего не было.
Насчёт музыки, музыкальные инструменты точно были и до Пифагора, но классификация звуков по высоте с сопутствующей теорией интервалов вроде как до Пифагора отсутствовала в принципе.
А почему музыка входит в изобразительные искусства (7)?
Чтобы храниться в той части библиотеки, что в здании факультета изящных искусств находится.
А почему тогда тегория не "искусство"?
А кто бы сказал. Tут (Wikipedia): 'Class 700 — Arts and recreation'
EDIT: Пройдя по ссылкам на оригинальную статью (gutenberg.org)
700 — Fine Arts
700.
А для решения проблемы вводится институт тэгов. Автор присваивает книге кроме абстрактной категории и чуть менее абстрактного жанра ведро уже вполне конкретных тэгов от общих к частным (general tag «Попаданцы», targeting tag «Попаданцы в прошлое»), те, на которых менее N вхождений за месяц с первого появления автоматически удаляются для предотвращения захламления.
Так работает, например, каталогизатор author.today, и работает вполне успешно.
Тот же принцип транспортабелен куда угодно ещё, в те же багрепорты с выбором тэгов внутри категории от более популярных к менее популярным (пример от балды: категория «интерфейс», тэги «мышь», «зависание», «основной функционал», и специалист может присвоить очерёдность даже не читая).
Спасибо за пример. Это хороший алгоритм, но если вы попытаетесь его выполнять руками, то вам придётся (с заменой "месяца" на "шутк") проверять вот это "N", т.е. у вас будет как раз N*N.
Дальше на все это дело вешаем скрипт, первого числа каждого месяца сносящий все подтаблицы, у которых дата создания больше месяца и меньше десяти записей.
P.S. пардон за синтаксис запроса, но нормальные БД уже наглухо забыты в памяти в пользу корпоративной «самописки», на которой всё стоит.
P.S.2. Для того же самого руками и в оффлайне: заводим картотеку с лотками-тэгами и подписью маркером на скотче. В конце месяца на глаз смотрим, где карточек маловато и вытрясаем их оттуда, отдирая скотч — лоток свободен.
Вообще для меня странно, что тэги не ввели ещё в доинтернетную эпоху.
А, так если есть база данных, то выполнение алгоритма мы можем переложить на неё, без проблем. Там и сортировка, и выборка за O(1) по индексированным полям, и невероятные возможности.
Но исходный пост же был про "распечатать и вдумчиво перекладывать по стопочкам". При этом тривиальные задачи становятся весьма и весьма сложными для исполнителя. Я про это и говорил — ручная реализация алгоритмов, применимых на больших данных (больше, чем голове может удержаться), это эквивалент запросов в базу, в которых промежуточное представление больше оперативной памяти. Можно, но сложно.
те, на которых менее N вхождений за месяц с первого появления автоматически удаляются для предотвращения захламления.
Все расставляют от балды и как можно больше, потом оставляем самые актуальные. Грубо говоря, в «Попаданцы в параллельные миры» 10 вхождений будет, а условный тег «плоская земля» не приживется.
К этому же прикрутить подсказчик и детектор дублирования тега по ключевым словам (начинаешь набирать «попаданцы», сразу вылезает веер уже имеющихся тегов с этим словом).
Есть децентрализованной алгоритм и для такого. Только вот не знаю, будет ли кто-то заморачиваться — общая для всех карта категорий, каждый может добавить свою, но необходимо одобрение других участников при помощи голосования (2/3 от количества людей голосуют ЗА)
P. S. Хотя ваш пример немного надуманный, при приёме людей на работу все таки важно оценивать их адекватность, чтобы в таких примерах не надо было про умолчанию предполагать их тупость
Можно сначала разделить баги на две-три больших категории. Это будет О(n), но затраты на одну классификацию будут минимальны. Затем уже параллелим каждую категорию, выделяем подкатегории, их каждую тоже параллельно обрабатываем. Уже при обработке подкатегорий нужна будет единая система тегов, но так как первый сортировщик просмотрел все репорты, он сможет её составить, пока идёт сортировка на подкатегории.
Дубликаты вычислить по пересечениям тегов
Предполагается, что у сортировщика такая память, что он помнит всё. Если не помнит — вот тут вот и начинается n*n.
n^2 не нужно.
Грубо говоря, у нас есть операция попарного 'сравнения': "Относится ли issue A к той же группе, что issue B".
Дальше смотрим, как строится бинарное дерево сортировки. Там n^2 попарных сравнений, если я правильно помню, не требуется. Если приблизительно похожим способом генерировать категории (то что похоже — в левую кучку, не похоже — в правую. Время от времени issue-корень-категории меняем, чтобы перебалансировать глубину классификации) — то будет приблизительно с той же сложностью.
Когда у нас уже существуют группы, разложить issue по дереву/списку групп — это либо θ(n), либо θ(log n), либо даже θ(len(group)).
Тут же сиутация о другом. Формирование осмысленной (полезной) группы — это проверка применимости группы в сравнении с остальными группами и багами (т.е. n). Получается, что для множества групп мы имеем n*g операций. Если g (число групп) функция от n, то получаем n*n.
Зачем со всеми остальными то? Это как утверждать, что при сортировке надо очередной элемент сравнивать со всеми остальными, хотя это далеко не так. Нет, понятно, что для чисел и прочих подобных им само отношение порядка помогает. Но группировки требование " каждый-с каждым" тоже сомнительно.
В моем примере: если в текущем корне дерева некий баг от которого настал конец света — то в левую сторону от него будут все похожие баги (т.е. которые тоже к концу света приводят), с дальнейшим дроблениям по причинам. А в правую сторону — те, что не приводят. И сравнивать первые со вторыми как бы уже не надо.
Тут нужно понимать, что какую-то группировку мы так или иначе получим. Хотя бы в виде 'номер категории — последняя цифра номера бага'. Берем и пользуемся.
Если нам 'какая-то' не нужна, и к ней есть некие требования по 'разумности', то эти самые требования сразу лимитируют, что с чем сравнивать стоит или не стоит.
Это задача кластеризации. Если задачи более-менее хорошо перемешаны перед разделением всего пула на нескольких разработчиков, то кластеры будут примерно одинаковые у всех. Можно сделать промежуточную синхронизацию, скажем, после обработки 10% от пула. Дальнейшее расхождение уже не будет слишком большим
Каким образом вы синхронизируете опыт мышления и выбранный алгоритм кластеризации между людьми?
Один решил поделить баги на
принадлежащих Императору,
прирученных,
набальзамированных,
сказочных,
второй поделил на
бегающих как сумасшедшие,
бесчисленных,
бродячих собак,
прочих
третий поделил на
нарисованных тончайшей кистью из верблюжьей шерсти,
разбивших цветочную вазу,
похожих издали на мух.
И?
+ В реальности вам не нужно фейлить алгоритм при первой же ошибке. Обычно достаточно добавить категорию «другое», куда складываются все фейлы. Главное чтобы её размер не оказался слишком большим.
По итогу почти линейный алгоритм такой:
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'). Параллелится по количеству категорий.
За какое время вы создадите систему классификации?
В операции добавления категории в существующую систему классификации, в общем случае, создание новой категории — это не θ(1), ни в коем случае. Если вы хотите осмысленную, полезную классифοикацию. Если у вас создание новой категории — это θ(n), то у вас проход по списку issue — θ(n), создание категории θ(n/С), итого, сложность алгоритма θ(n*n)
Новые могут добавляться только на шаге 3 при просмотре категории «другое», и обрабатываться, соответственно, только для элементов отсюда.
Да, категоризация будет неидеальна, придётся сделать выбор между квадратичной скоростью и идеальной категоризацией.
"Проходимся по тикетам, составляем список категорий."
Вот я утверждаю, что операция "составляем список категорий" состоит из добавления новых категорий, одной за одной. Число и тип категорий либо не имеет отношения с содержимому входных данных (является константным), либо зависит от него (и в этом случае добавление категорий — функция от числа входных данных).
Использование sampling тут может помочь только если мы уверены в распределении в исходных данных. Предположим, что у нас 100к багов, среди них есть 100, заслуживающих 5 важных категорий. Сколько должно быть багов просмотрено, чтобы получить эти 5 категорий с (хотя бы) 3 сигма?
100000 багов, на первом шаге просмотрим 1000, выделим 10 категорий
на втором шаге пройдёмся по всем ста тысячам
Предположим 20000 из 100000 попадут в «другое».
На 3 шаге рекурсивно применяем тот же алгоритм, когда будем просматривать категорию «другое» рассмотрим ещё 1000 дефектов оттуда. Выделим ещё 2-3 новые категории для них.
Пройдёмся по 20000 дефектов, из них в «другом» останется 7000 и т.д. до разумного предела
Если предел — 100 багов, то все 5 важных категорий гарантированно выявятся.
UPD. Ну и если константа в первом шаге не очень большая, размер сэмпла можно увеличивать, вплоть до всех 100000 элементов.
Вы при этом предполагаете, что созданные категории создаются и остаются. Может оказаться, что первая категория — "бальзамированные", вторая "носятся как бешенные", а третья — "принадлежат Императору". А потом появляется категория "издалека похожие на муху".
Если избегать такой системы категоризации, категории надо переделывать после обнаружения неудачности старой модели. Если сохранять наработанную — ну, что ж, "мифические" и "сирены" — две разумные категории для багов.
Предположим, что у нас 100к багов, среди них есть 100, заслуживающих 5 важных категорий.
Как бы не может быть. 100 из 100k — это категория 'прочие' из-за явной редкости.
Хотя, по большому счету, мы во всем этом обсуждении забываем вопрос 'а какой цели эта категоризация служить должна?' и что слово "категория" у нас означает.
Кому какой баг назначим? Значит категорий не более количество человек в проекте.
В каком модуле бага? Значит категорий не больше количество модулей
итд итп.
Как видно, в некоторых вариантах категории вообще создаются не глядя на сами баги.
O(n * log(n)) если быть точным. Либо O(n * k * log(n)) при использовании тегов вместо категорий
При этом неявно предполагается равномерность распределения важности. Потому что может оказаться, что из 100к багов 95к — это трейсы, а 5к — заполненные человеком багрепорты. Вы делаете sample для 50 багов, они все оказываются трейсами. Ваша система категорий полностью пропускает всё важное (оставшиеся 5к багов, которые и требуют внимания).
Короче, если у вас есть a priori знание про входные данные, то существуют алгоритмы сортировки быстрее, чем θ(n log n). Если нет — требуется как минимум, полное сканирование, плюс раздумия.
100к багов 95к — это трейсы, а 5к — заполненные человеком багрепорты.
Которые успешно попадают в 5% 'прочие'. Которой категории потом, если уж нас так ручные багрепорты заинтересовали (после сортировки по категориям) и присваивается приоритет 'важная'. Если же ручные багрепорты интересуют больше еще до начала сортировки — то и соответствующая категория создается сразу.
Кроме того, если заранее есть требование 'все что 5% — должно заметить и поместить в собственную категорию', то и размер sample исходя из этого требования подсчитывается.
И таки да, это скучно, утомительно, но можно и нужно параллелить.
А как работают интернет-поисковики? Вроде задача вполне похожая.
Интернет-поисковики работают совсем не так. Они не требуют специального человека, который три недели перекладывает бумажки между разными стопками. Вместо этого они делают индекс и смотрят на кросс-ссылки. А ещё на чёртову магию, которую мы не видим, но в любом случае — это автоматизированный процесс.
А тут статья о том, что некоторые вещи можно сделать только вручную, хоть и муторно.
Так в том то и суть масштабирования: делаем автоматизацию. Пишем похожую магию/обучаем МЛ. Баги структурируем по какому-то шаблону. Недостающие данные заполняем мясными роботами. Заполнение по шаблону хорошо параллелится. Как пример шаблона — шаги для воспроизведения, раздел интерфейса/часть функциональности.
Натравяем алгоритм, получаем профит?
Да, дорого, да не имеет смысл делать для задач которые можно сделать одним человеком за три недели. Но если стоит вопрос про 5 лет — можно пойти таким путем. В конце концов, интернет то парсит и каталогизирует не один человек.
Кстати, раньше же вроде был ручной каталог сайтов. Который заменили поисковики. Как пример подобной эволюции.
Особенно это критично, если чинить надо что-то, что используется во всём проекте, собственно поэтому такие баги зачастую висят годами, так как трогать реально страшно, а новый герой ещё не родился.
Что очень много волшебных и крутых вещей делается не тогда, когда ты бегаешь по конференциям и ищешь волшебные тулзы которые все сделают за тебя, а когда ты просто садишься и работаешь.
А потом в выводе "012345578910".
Лентяю лень потом баги искать, поэтому он выберет второй вариант.
Там в цикле же i <= 10, то есть десятка в конце будет выведена в любом из вариантов. Или я опять попался на граничном условии ошибки на единицу? :/
Лентяй напишет 1 вариант, потому что это требует от него меньше мыслей. "Мне надо сделать это 10 раз, ну значит сделаю это 10 раз". Для того, чтобы подумать мысль "что-то слишком много раз я это делаю" надо иметь привычку думать эту мысль.
Вдруг кому интересно будет:
В багзилле LibreOffice около 14000 подтвержденных баг репортов
Из них около 800 МЕТА баг репортов, в которые прикрепляют обычные, на манер ящика в каталоге
Также из тех 14000 есть около 4000 багрепортов, которые не отнесены ни к одному МЕТА
Те люди, которые волонтерствуют в QA проекта, в последнее время стараются сортировать баг репорты сразу, как их читают и комментируют. К сожалению тут нет единой политики, кто-то прописывает МЕТА, кто-то нет.
В месяц поступает по 650-750 баг репортов. Часто не все они даже просто читаются, не говоря уж о тэгировании и сортировке.
Так вот, эта вот сортировка крайне скучное занятие. Меня тошнить начинает, когда десяток репортов пометишь в день. Просто пропишешь МЕТА, без ответа репортеру и анализа самого репорта.
При этом это реально полезное дело, некоторые МЕТА мониторят активные разработчики, которые могут или сразу пофиксить проблему или, например, пояснить, что это вообще не бага
Но я не уверен, что люди в нём продуктивны, скорее их изнуряет необходимость выполнения ритуалов.
Чтобы не просела поисковая выдача, не потерся траффик, и сайт не попал под фильтр, я лично написал 5,5к перманентных редиректов со старой страницы на новую, страница мать его за страницей.
И реально, когда на том же тостере спрашивают, а что делать в похожей ситуации. Все ждут какие-то регулярки, какую-то магию или «само пройдет», а фишка в том, что надо сесть и написать все редиректы ручками.
Может все карты одинаковые просто.
Скорее всего, предлагается не выбрать а запомнить как бы «случайным» образом выбранную карту — т.е. либо перемешать, сдвинуть, взять верхнюю карту, либо фокусник или его подсадкда раздает по карте нескольким «случайным» зрителям, и потом опять «случайно» выбор участия падает на зрителя с нужной картой. Ну или каким то иным похожим способом.
Поскольку если бы был только фокусник и только жертва, то заставить его самому выбрать нужную карту из колоды можно только внушением.
Вы можете перетасовывать и снимать сколько угодно, если все карты одинаковые, вы всегда выберете нужную. Ну и Фокусник может показать Вам другую колоду с помощью ловкости рук, для того чтобы Вы совсем не думали об этом.
Описание можно найти по фразе «how to force a card», колода карт при жтом может быть самой обычной.
Кстати, как только прочитал «Кладёт в каждую упаковку тройку крестей.» стало понятно что это не случайно выбранная карта. У Пена и Теллера это что-то вроде «inside joke», они всегда именно эту карту впихивают тому кому фокус показывают. Они об этом в инервью не раз говорили.
Автор, добавьте на Penn & Teller ссылку, а то тем кто не в теме фокусов наверняка непонятно о ком идёт речь в тексте
«Теллер рассказывает об этом в статье о семи секретах магии…
Мы с моим напарником Пенном однажды ...»
А гуманитарии от программистов часто ожидают именно волшебства. Вот есть крупный продукт, который 10 лет писали абы как, забивая на чистый код, авто-тесты и технический долг, а потом ждут, что вот придет новый крутой программист, сделает «вжух» и все проблемы исчезнут.
И это самое неприятное — объяснять людям, что магии не бывает.
Затем мы изготовили из пенопласта потайную перегородку (это один из тех немногочисленных материалов, за которые не могут уцепиться тараканы)
а за какие ещё материалы не могут уцепиться тараканы?
Программирование — это скучная магия