Комментарии 41
Прогоните пожалуйста данную статью через антиплагиат. Мне интересно насколько она оригинальна по мнению сервиса, от которого нынче зависят судьбы дипломов: как мне кажется, шинглы используемые в данном тексте встречаются, например, по всему хабру, много раз и в различных сочетаниях.
Из того, что в статье используются те или иные слова (например, шингл) в каких-то сочетаниях совершенно не следует, что статья неоригинальна. Я могу даже сказать сильнее — все статьи на хабре преимущественно состоят из слов, которые уже где-то использованы. Если вам кажется, что какая-то часть текста заимствована (пусть даже с перефразировкой), то подскажите. Нам самим интересно ;)
Нет, мне не кажется что она заимствована. Тем не менее, я помню хайп по поводу использования "антиплагиата", и мне хотелось увидеть его в действии на действительно оригинальном материале, пусть и с обилием лексики, часто употребляемой на конкретном сайте. Спасибо, моё любопытство вполне удовлетворено :)
Если мои воспоминания об O-нотации не покрылись ещё хмурой дымкой инея, то превзойти O(1), обозначающего поиск за постоянное время независимо от объёма данных, можно лишь уменьшая время поиска при увеличении объёма данных. Вы точно-точно добились именно такого эффекта?
У O(1) можно либо константу уменьшить (о которой часто забывают), либо вообще обойтись без поиска (т.е. константу свести к нулю). В нашем случае иногда читать с диска не требуется, что можно считать вторым случаем.
Про O(0) — это, конечно, была шутка.
Про O(0) — это, конечно, была шутка.
При рассказе об O-нотации первым делом обычно объясняют, что это характеристика того, как изменяется трудоёмкость алгоритма в зависимости от роста объёма данных. Именно поэтому там в скобочках единица, а не другое число, именно поэтому не бывает чего-то вроде O(3*n). Так что о константе времени поиска не «забывают», просто её конкретное значение не имеет отношения к O.
И как мне кажется, лучше даже в шутку не создавать кому-то проблемы с правильным пониманием смысла этой важной характеристики.
И как мне кажется, лучше даже в шутку не создавать кому-то проблемы с правильным пониманием смысла этой важной характеристики.
Не редки ситуации, когда алгоритм с O(n) лучше навороченного с O(logn) в частном случае только лишь за счёт константы.
Что является убедительным контрпримером для всех, кто считает О-нотацию единственным критерием оценки производительности. Мы же, как люди воспитанные, не будем создавать такого впечатления, навязывать О-нотации несвойственные ей обязанности и не станем грубо пихать ей в скобки всякого лишнего ненужного.
мгновенная вставка/удаление/обновлениену вот же О(0), какая такая шутка?
Вопрос немного не по теме. Насколько Ваша система устойчива к синонимизаторам?
В свое время уникальный диплом писался заменой банально о=>o, потом можно было пользоваться вставками с невидимым шрифтом или удаленными словами, чуть позже вполне прокатывал метод автосинонимизации с ручной ловлей наиболее сомнительных косяков, позже мы завязали бороться с системой и начали писать дипломы по старинке… правда результаты по антиплагиату получались хуже, но зато понабрались лишних знаний:)
Как сейчас с синонимизацией?
«Карл у клары украл кораллы» будет одним плагиатом с «Петр Афанасльевич у Василия Ивановича своровал материал скелета колонии коралловых полипов» или нет?:)
В свое время уникальный диплом писался заменой банально о=>o, потом можно было пользоваться вставками с невидимым шрифтом или удаленными словами, чуть позже вполне прокатывал метод автосинонимизации с ручной ловлей наиболее сомнительных косяков, позже мы завязали бороться с системой и начали писать дипломы по старинке… правда результаты по антиплагиату получались хуже, но зато понабрались лишних знаний:)
Как сейчас с синонимизацией?
«Карл у клары украл кораллы» будет одним плагиатом с «Петр Афанасльевич у Василия Ивановича своровал материал скелета колонии коралловых полипов» или нет?:)
Про перефраз в прошлом году мы публиковали статью:«Трое в лодке, нищета и собаки», или как Антиплагиат ищет парафраз Уже полгода как на проде. Будет ещё одна статья на близкую тему.
Омоглифы (замену банального о=>o) мы стали ловить ещё где-то в 2011 году. Полноценно проблему решили примерно в 2015. Ещё встречается, но довольно редко. На новых языках или если где недосмотрели в новых чекерах. Но довольно быстро затыкаем, как только обнаруживаем.
Про технические способы обнаружения обхода мы выпустим полноценную статью в этом году. И, видимо, не одну!
Омоглифы (замену банального о=>o) мы стали ловить ещё где-то в 2011 году. Полноценно проблему решили примерно в 2015. Ещё встречается, но довольно редко. На новых языках или если где недосмотрели в новых чекерах. Но довольно быстро затыкаем, как только обнаруживаем.
Про технические способы обнаружения обхода мы выпустим полноценную статью в этом году. И, видимо, не одну!
А саму файловую систему каким-то образом настраивали?
Полноценного тестирования на разных файловых системах с тюнингом их параметров не делали. ИМХО, кроме размера кластера и внутреннего кэширования там мало что на результат влияет в нашем случае (чтения большого файла).
Win+NTFS и Linux+BTRFS при дефолтных параметрах на одинаковом железе на глаз выдают примерно одинаковые результаты.
HDD сразу в пролёте. SSD — наше всё. Optane — пока не завезли.
SATA, конечно, хуже NVME, но тестировали полноценно только на первом. В NVME, конечно, скорость будет повыше. Индекс просто перестал быть узким местом в поиске, упираемся в последующие стадии.
Win+NTFS и Linux+BTRFS при дефолтных параметрах на одинаковом железе на глаз выдают примерно одинаковые результаты.
HDD сразу в пролёте. SSD — наше всё. Optane — пока не завезли.
SATA, конечно, хуже NVME, но тестировали полноценно только на первом. В NVME, конечно, скорость будет повыше. Индекс просто перестал быть узким местом в поиске, упираемся в последующие стадии.
Overlapped IO дает прирост производительности?
FILE_FLAG_NO_BUFFERING, FILE_FLAG_WRITE_THROUGH для SSD имеет смысл?
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 в нашем случае, как я понимаю, не актуален, т.к. запись идёт последовательно и большими объёмами. А с ним скорость в этом сценарии будет меньше. Или я не прав?
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, что их имеет смысл использовать даже в случае единственного рабочего потока — из-за обработки на уровне ядра.
Насколько я помню, overlapped I/O в .net реализован через I/O Completion Ports.
Читал в MSDN Magazine, что их имеет смысл использовать даже в случае единственного рабочего потока — из-за обработки на уровне ядра.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Отличный вопрос. Не готов на него сейчас ответить. Действительно, скорость прирастёт и объём уменьшится (правда не на 25%).
Про уникальные слова я не понял идею. Можете разъяснить?
Про уникальные слова я не понял идею. Можете разъяснить?
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Сейчас да, 40 бит будет достаточно. 48 — с лихвой. Но при росте объёма хотя бы на пару порядков упрёмся уже в этот новый потолок.
Про уникальные слова. Шингл — это хэш нескольких слов. У нас есть списки стоп-шинглов и «тяжёлых» шинглов, о чём написано выше в статье. Про алгоритм генерации шинглов в общих чертах есть здесь.
Про уникальные слова. Шингл — это хэш нескольких слов. У нас есть списки стоп-шинглов и «тяжёлых» шинглов, о чём написано выше в статье. Про алгоритм генерации шинглов в общих чертах есть здесь.
Теоретически, частота коллизий возрастёт примерно в 65536 раз, но статистические показатели коллизионных наборов, в частности, наиболее типичный размер (математическое ожидание) множества с коллизионным хешем и размер «рекордной команды» (множество, максимальное по размеру из встреченных с одним хешем) возрастут не так радикально, как мне кажется
Забавно, студентом делал на кафедре "научный" проект по отлавливанию плагиата и использовал шинглы. Не знал, что серьёзные системы тоже на них построены.
Гм… Серьезные системы?) Странно…
Автор и его компания заюзала как раз таки самые базовые вещи. И самое главное — они разобрались в этом. По-сути — у них «массивы» через хэши «массивами» погоняют. И все. А разве нужно что-то еще? И явственно тут «попахивает» «ненормальным» программированием. А уж то что нет аджайла, и ваще на гите этого нет, и даже ни единого нода нет, и «покетов» нет — так это же вообще ужасно! Какая же это серьезная система?))) Это ж поделка из прошлого века. Нельзя так!
Просто автор взял и выкинул все невменяемое фуфло, и оставил только то что нужно, и что очень быстро работает. И таки словил дзен. Оперируя всего лишь суммарно максимум пятнадцатью абстракциями. Вот и все.
И выводы ужасные конечно… Все бд — шлак. Или узкозаточены под что-то, и только под что-то. И при этом — крайне избыточны. Еще и глючные. Все фреймворки — шлак. Если нужно быстро — пиши свое. И т.д. и т.п.
По меркам хабры — автор просто взял и втоптал в грязищщу «многовековые» «труды» местных писак. Всего навсего написав чуть ли не на паскале 5000 строк абсолютно простого кода так, что у этих писак никогда в жизни не получится по-определению.
Браво, автор! Браво!
Автор и его компания заюзала как раз таки самые базовые вещи. И самое главное — они разобрались в этом. По-сути — у них «массивы» через хэши «массивами» погоняют. И все. А разве нужно что-то еще? И явственно тут «попахивает» «ненормальным» программированием. А уж то что нет аджайла, и ваще на гите этого нет, и даже ни единого нода нет, и «покетов» нет — так это же вообще ужасно! Какая же это серьезная система?))) Это ж поделка из прошлого века. Нельзя так!
Просто автор взял и выкинул все невменяемое фуфло, и оставил только то что нужно, и что очень быстро работает. И таки словил дзен. Оперируя всего лишь суммарно максимум пятнадцатью абстракциями. Вот и все.
И выводы ужасные конечно… Все бд — шлак. Или узкозаточены под что-то, и только под что-то. И при этом — крайне избыточны. Еще и глючные. Все фреймворки — шлак. Если нужно быстро — пиши свое. И т.д. и т.п.
По меркам хабры — автор просто взял и втоптал в грязищщу «многовековые» «труды» местных писак. Всего навсего написав чуть ли не на паскале 5000 строк абсолютно простого кода так, что у этих писак никогда в жизни не получится по-определению.
Браво, автор! Браво!
Серьезность для меня определяется объемами данных, которые сейчас есть в системе и нагрузкой, которую они держат.
И да, ничего нет плохого в массивах. Замена Array на List или какую-то доменную модель не делает приложение круче.
У ребят конкретная узкая задача и они выжимают максимум из железа используя собственные решения. По-моему всё отлично.
И да, ничего нет плохого в массивах. Замена Array на List или какую-то доменную модель не делает приложение круче.
У ребят конкретная узкая задача и они выжимают максимум из железа используя собственные решения. По-моему всё отлично.
Периодически приходится писать разъяснения для партнеров, статьи которые по сути представляют собой цитаты из нормативки (кто попадает под требования по КИИ, какие законом требуются меры защиты и тд) плюс простейшие комментарии для понимания, о чем требования. Юристы ругаются и говорят, что плагиат — мол было в интернете уже. И возразить нечего. Но зачастую иначе и не напишешь. Тот же 152-фз описан со всех сторон, но очень многие о нем умудрились не услышать за прошедшее время
Поэтому чисто для интереса. Когда вы в публикациях встречаете цитаты из той же нормативки — вы их тоже учитываете как плагиат или исключаете из анализа?
Поэтому чисто для интереса. Когда вы в публикациях встречаете цитаты из той же нормативки — вы их тоже учитываете как плагиат или исключаете из анализа?
У нас есть специальное выделение легитимных заимствований нормативно-правовых документов, реализовано как поиск по системам с нормативкой типа Гарант. Такое заимствование называется «цитированием» и отмечается зеленым цветом. В целом 100% = Заимствование + Цитирование + Оригинальный текст. Цитированием так же считается: корректно оформленное цитирование, общеупотребимые фразы, библиография.
Важно отмечать и такое заимствование, т.к. может оказаться что вся работа состоит из цитрований и своих мыслей совсем нет. Мы стараемся предоставить эксперту максимальный объем информации чтобы он смог вынести взвешенное решение.
Важно отмечать и такое заимствование, т.к. может оказаться что вся работа состоит из цитрований и своих мыслей совсем нет. Мы стараемся предоставить эксперту максимальный объем информации чтобы он смог вынести взвешенное решение.
Спасибо.
Уточню. Цитаты не всегда идут так как в нормативке. Скажем часто по требованию компактности статьи списки объединяются в один абзац или вырезается часть текста (без потери смысла естественно)
Не скажу, что часто, но за этот год я штуки две написал публикации чисто повторы. Люди не знают, не любят сами читать нормативные акты — поэтому приходится так делать. Иногда сидишь и думаешь — ну как бы так написать в очередной раз, чтобы отличалось хоть чуть.
Уточню. Цитаты не всегда идут так как в нормативке. Скажем часто по требованию компактности статьи списки объединяются в один абзац или вырезается часть текста (без потери смысла естественно)
Не скажу, что часто, но за этот год я штуки две написал публикации чисто повторы. Люди не знают, не любят сами читать нормативные акты — поэтому приходится так делать. Иногда сидишь и думаешь — ну как бы так написать в очередной раз, чтобы отличалось хоть чуть.
Если у вас хеш 64-битный, id документа допустим тоже и триллион уникальных шинглов, то получается первый индекс(«1 массив индекса») весит как минимум 1*10^12*(8+8)/1024/1024/1024/1024 или примерно 14.5 тб?!
Вы верно подметили масштаб проблемы.
Можете описать немного подробнее как происходит поиск? Есть у вас огромный отсортированый массив hash->docId который устроен так чтоб несколько элементов влезали целиком в кластер на диске. Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?
Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?Хеш-таблица
disclaimer
да, в таком случае фактически используется хэш от хэша, но функции хэширования, в общем случае, разные и это не тот случай, когда таким образом пытаются «улучшить» хэширование или добиться каких-то других экзотических целей
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Триллион маленьких шинглов