Как стать автором
Обновить

Комментарии 41

Прогоните пожалуйста данную статью через антиплагиат. Мне интересно насколько она оригинальна по мнению сервиса, от которого нынче зависят судьбы дипломов: как мне кажется, шинглы используемые в данном тексте встречаются, например, по всему хабру, много раз и в различных сочетаниях.
image

"Вместо тысячи слов" :) большое спасибо.

Из того, что в статье используются те или иные слова (например, шингл) в каких-то сочетаниях совершенно не следует, что статья неоригинальна. Я могу даже сказать сильнее — все статьи на хабре преимущественно состоят из слов, которые уже где-то использованы. Если вам кажется, что какая-то часть текста заимствована (пусть даже с перефразировкой), то подскажите. Нам самим интересно ;)

Нет, мне не кажется что она заимствована. Тем не менее, я помню хайп по поводу использования "антиплагиата", и мне хотелось увидеть его в действии на действительно оригинальном материале, пусть и с обилием лексики, часто употребляемой на конкретном сайте. Спасибо, моё любопытство вполне удовлетворено :)

Если мои воспоминания об O-нотации не покрылись ещё хмурой дымкой инея, то превзойти O(1), обозначающего поиск за постоянное время независимо от объёма данных, можно лишь уменьшая время поиска при увеличении объёма данных. Вы точно-точно добились именно такого эффекта?
У O(1) можно либо константу уменьшить (о которой часто забывают), либо вообще обойтись без поиска (т.е. константу свести к нулю). В нашем случае иногда читать с диска не требуется, что можно считать вторым случаем.

Про O(0) — это, конечно, была шутка.
При рассказе об O-нотации первым делом обычно объясняют, что это характеристика того, как изменяется трудоёмкость алгоритма в зависимости от роста объёма данных. Именно поэтому там в скобочках единица, а не другое число, именно поэтому не бывает чего-то вроде O(3*n). Так что о константе времени поиска не «забывают», просто её конкретное значение не имеет отношения к O.
И как мне кажется, лучше даже в шутку не создавать кому-то проблемы с правильным пониманием смысла этой важной характеристики.
Не редки ситуации, когда алгоритм с O(n) лучше навороченного с O(logn) в частном случае только лишь за счёт константы.
Что является убедительным контрпримером для всех, кто считает О-нотацию единственным критерием оценки производительности. Мы же, как люди воспитанные, не будем создавать такого впечатления, навязывать О-нотации несвойственные ей обязанности и не станем грубо пихать ей в скобки всякого лишнего ненужного.
мгновенная вставка/удаление/обновление
ну вот же О(0), какая такая шутка?
Вопрос немного не по теме. Насколько Ваша система устойчива к синонимизаторам?
В свое время уникальный диплом писался заменой банально о=>o, потом можно было пользоваться вставками с невидимым шрифтом или удаленными словами, чуть позже вполне прокатывал метод автосинонимизации с ручной ловлей наиболее сомнительных косяков, позже мы завязали бороться с системой и начали писать дипломы по старинке… правда результаты по антиплагиату получались хуже, но зато понабрались лишних знаний:)
Как сейчас с синонимизацией?
«Карл у клары украл кораллы» будет одним плагиатом с «Петр Афанасльевич у Василия Ивановича своровал материал скелета колонии коралловых полипов» или нет?:)
Про перефраз в прошлом году мы публиковали статью:«Трое в лодке, нищета и собаки», или как Антиплагиат ищет парафраз Уже полгода как на проде. Будет ещё одна статья на близкую тему.

Омоглифы (замену банального о=>o) мы стали ловить ещё где-то в 2011 году. Полноценно проблему решили примерно в 2015. Ещё встречается, но довольно редко. На новых языках или если где недосмотрели в новых чекерах. Но довольно быстро затыкаем, как только обнаруживаем.

Про технические способы обнаружения обхода мы выпустим полноценную статью в этом году. И, видимо, не одну!
А саму файловую систему каким-то образом настраивали?
Полноценного тестирования на разных файловых системах с тюнингом их параметров не делали. ИМХО, кроме размера кластера и внутреннего кэширования там мало что на результат влияет в нашем случае (чтения большого файла).

Win+NTFS и Linux+BTRFS при дефолтных параметрах на одинаковом железе на глаз выдают примерно одинаковые результаты.

HDD сразу в пролёте. SSD — наше всё. Optane — пока не завезли.
SATA, конечно, хуже NVME, но тестировали полноценно только на первом. В NVME, конечно, скорость будет повыше. Индекс просто перестал быть узким местом в поиске, упираемся в последующие стадии.
Overlapped IO дает прирост производительности?
FILE_FLAG_NO_BUFFERING, FILE_FLAG_WRITE_THROUGH для SSD имеет смысл?
Как я понимаю, .net'овский async в итоге задействует Overlapped IO. Если это так, то в моих замерах потоковая скорость немного проседает, но и cpu также меньше грузится. Пока глубоко не исследовал. Упоминал в конце статьи про Async/await.

FILE_FLAG_NO_BUFFERING в dotnet'е в явном виде нет, работает(?) как хак. Нет, не смотрел, но спасибо за наводку.

FILE_FLAG_WRITE_THROUGH в нашем случае, как я понимаю, не актуален, т.к. запись идёт последовательно и большими объёмами. А с ним скорость в этом сценарии будет меньше. Или я не прав?
Как я понимаю, .net'овский async в итоге задействует Overlapped IO.

Да.

Да, для FILE_FLAG_NO_BUFFERING можно определить константу и передать в параметрах FileStream. Там дополнительные требования к размеру буфера возникают. В вашем сценарии файловый кэш Windows особого смысла, мне кажется, не имеет. В статье про последовательные методы доступа по вашей ссылке приведены тесты с ним.

А вот FILE_FLAG_WRITE_THROUGH — конечно, спорный вопрос. Перечитал справку — если его использовать вместе с FILE_FLAG_NO_BUFFERING, то будет отключено кэширование метаданных, а это негативно отразится на производительности.
Overlapped IO даёт прирост только при одновременной обработке множества запросов, и при условии что диск нагружен ещё не на 100%. Причём «множество» тут — это более 1000, до этой цифры простая многопоточность, как правило, будет выглядеть лучше.

Ну автор использует же пул FileStream для SSD для той же цели.
Насколько я помню, overlapped I/O в .net реализован через I/O Completion Ports.
Читал в MSDN Magazine, что их имеет смысл использовать даже в случае единственного рабочего потока — из-за обработки на уровне ядра.
Да, из имеет смысл использовать даже в случае единственного потока. Но при этом одновременных задач все равно должно выполняться много.
НЛО прилетело и опубликовало эту надпись здесь
Вы нас озадачили. :)
НЛО прилетело и опубликовало эту надпись здесь
Отличный вопрос. Не готов на него сейчас ответить. Действительно, скорость прирастёт и объём уменьшится (правда не на 25%).

Про уникальные слова я не понял идею. Можете разъяснить?
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Универсальная и популярная схема, но не очень гибкая. Кроме того, рашдинг по шинглам имеет свои проблемы именно на больших индексах.

Когда допилим, обязательно будет отдельная статья на эту тему.
Сейчас да, 40 бит будет достаточно. 48 — с лихвой. Но при росте объёма хотя бы на пару порядков упрёмся уже в этот новый потолок.

Про уникальные слова. Шингл — это хэш нескольких слов. У нас есть списки стоп-шинглов и «тяжёлых» шинглов, о чём написано выше в статье. Про алгоритм генерации шинглов в общих чертах есть здесь.
Теоретически, частота коллизий возрастёт примерно в 65536 раз, но статистические показатели коллизионных наборов, в частности, наиболее типичный размер (математическое ожидание) множества с коллизионным хешем и размер «рекордной команды» (множество, максимальное по размеру из встреченных с одним хешем) возрастут не так радикально, как мне кажется

Забавно, студентом делал на кафедре "научный" проект по отлавливанию плагиата и использовал шинглы. Не знал, что серьёзные системы тоже на них построены.

Гм… Серьезные системы?) Странно…
Автор и его компания заюзала как раз таки самые базовые вещи. И самое главное — они разобрались в этом. По-сути — у них «массивы» через хэши «массивами» погоняют. И все. А разве нужно что-то еще? И явственно тут «попахивает» «ненормальным» программированием. А уж то что нет аджайла, и ваще на гите этого нет, и даже ни единого нода нет, и «покетов» нет — так это же вообще ужасно! Какая же это серьезная система?))) Это ж поделка из прошлого века. Нельзя так!

Просто автор взял и выкинул все невменяемое фуфло, и оставил только то что нужно, и что очень быстро работает. И таки словил дзен. Оперируя всего лишь суммарно максимум пятнадцатью абстракциями. Вот и все.

И выводы ужасные конечно… Все бд — шлак. Или узкозаточены под что-то, и только под что-то. И при этом — крайне избыточны. Еще и глючные. Все фреймворки — шлак. Если нужно быстро — пиши свое. И т.д. и т.п.

По меркам хабры — автор просто взял и втоптал в грязищщу «многовековые» «труды» местных писак. Всего навсего написав чуть ли не на паскале 5000 строк абсолютно простого кода так, что у этих писак никогда в жизни не получится по-определению.

Браво, автор! Браво!
Серьезность для меня определяется объемами данных, которые сейчас есть в системе и нагрузкой, которую они держат.
И да, ничего нет плохого в массивах. Замена Array на List или какую-то доменную модель не делает приложение круче.
У ребят конкретная узкая задача и они выжимают максимум из железа используя собственные решения. По-моему всё отлично.
Периодически приходится писать разъяснения для партнеров, статьи которые по сути представляют собой цитаты из нормативки (кто попадает под требования по КИИ, какие законом требуются меры защиты и тд) плюс простейшие комментарии для понимания, о чем требования. Юристы ругаются и говорят, что плагиат — мол было в интернете уже. И возразить нечего. Но зачастую иначе и не напишешь. Тот же 152-фз описан со всех сторон, но очень многие о нем умудрились не услышать за прошедшее время
Поэтому чисто для интереса. Когда вы в публикациях встречаете цитаты из той же нормативки — вы их тоже учитываете как плагиат или исключаете из анализа?
У нас есть специальное выделение легитимных заимствований нормативно-правовых документов, реализовано как поиск по системам с нормативкой типа Гарант. Такое заимствование называется «цитированием» и отмечается зеленым цветом. В целом 100% = Заимствование + Цитирование + Оригинальный текст. Цитированием так же считается: корректно оформленное цитирование, общеупотребимые фразы, библиография.
Важно отмечать и такое заимствование, т.к. может оказаться что вся работа состоит из цитрований и своих мыслей совсем нет. Мы стараемся предоставить эксперту максимальный объем информации чтобы он смог вынести взвешенное решение.
Спасибо.
Уточню. Цитаты не всегда идут так как в нормативке. Скажем часто по требованию компактности статьи списки объединяются в один абзац или вырезается часть текста (без потери смысла естественно)
Не скажу, что часто, но за этот год я штуки две написал публикации чисто повторы. Люди не знают, не любят сами читать нормативные акты — поэтому приходится так делать. Иногда сидишь и думаешь — ну как бы так написать в очередной раз, чтобы отличалось хоть чуть.
Если у вас хеш 64-битный, id документа допустим тоже и триллион уникальных шинглов, то получается первый индекс(«1 массив индекса») весит как минимум 1*10^12*(8+8)/1024/1024/1024/1024 или примерно 14.5 тб?!
Вы верно подметили масштаб проблемы.
Можете описать немного подробнее как происходит поиск? Есть у вас огромный отсортированый массив hash->docId который устроен так чтоб несколько элементов влезали целиком в кластер на диске. Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?
Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?
Хеш-таблица
disclaimer
да, в таком случае фактически используется хэш от хэша, но функции хэширования, в общем случае, разные и это не тот случай, когда таким образом пытаются «улучшить» хэширование или добиться каких-то других экзотических целей
Как работает Hashtable например в той же java я знаю. Но как работатет поиск тут не пойму.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.