Реализация быстрой проверки строки из файла в несколько гб

Здесь поможет фильтр Блума.

Может он этот файл будет пересобирать из новых кусков раз в сутки, откуда ты знаешь? Я не спорю с тем, что постановка задачи идиотская, но было бы интересно почитать и померяться алгоритмами ее решения без бд, а не читать 2 страницы о том какой автор идиот. Ты уж точно вроде не из тех, кто бы самоутверждался на этом.

Как говорится, задай вопрос на форуме и получи кучу ответов почему тебе это не нужно - от еды до программирования :) Автора треда не защищаю.

Может он этот файл будет пересобирать из новых кусков раз в сутки, откуда ты знаешь?

Или этот файл просто содержит набор всех запрещённых в рамках его задачи строк и проводится проверка новых не на уникальность, а на то, чтобы они были «легальными». Соответственно, пересборка файла не нужна или нужна крайне редко.

Я однажды искал решение быстро делать случайные выборки из мускула, в итоге узнал на SO про TABLESAMPLE в постгресе и теперь юзаю его. Вообще не программист, если что.

То есть я тоже изначально неправильно поставил задачу, но в процессе ее изучения нашел отличное решение.

Ну, я не автор треда и задачи такой нет, но как решается вопрос «чекнуть произвольную строку не длиннее n в массиве или файле на таком-то языке без использования бд» почитал бы. И я согласен что это никому не надо, просто интересно как бы оно должно было работать с вашей точки зрения (я согласен что в итоге выйдет самописная бд ну или простое дерево).

Плохо что анонимам редактировать нельзя, просто хотел добавить.

У меня как то была задача дергать из сонсоли n рандомных строк из большого файла с текстом и чтобы оно было быстрее sort -R и shuf -n. Спросил в похожем треде, и всеми любимый местный эдуард написал мелкую прогу на сях, жаль исходников не осталось.

Это сейчас вы все гнутилиты на расте переписали многопоточно, а тогда пригодилось :)

Ну, я не автор треда и задачи такой нет

Ну я аналогично (а заодно даже и близко не программист), но просто хотел пояснить, что задача вида «есть неизменный набор строк, есть постоянный ввод других строк, каждую из которых надо проверить на наличие в первоначальном наборе строк» не обязательно бессмысленна. Тем более, что вообще-то про возможность конвертации в БД как наиболее оптимальный путь самим ТС сразу сказано было :)

Если нужно проверять отсутствие строки - смотри в сторону фильтра Блума. Если наличие - строй индекс: хеш-таблица, дерево, префиксное дерево, что-то ещё.

Да, по сути сам ТС ни за что не отвечает. Патамучта по сути ТС не отвечающий за свои высказывания… А это плохо.

Имея при себе тетрадку с алгоритмами человек так же может уделать любого соперника без таковой тетрадки. Тут только вопрос времени на поиск нужного хода — будет ли второй игрок ждать так долго, пока первый листает странички.

А смысл решать высосанные из пальца задачи?

Меня возмущает отсутствие даже попытки сформулировать задачу должным образом. При том, как часто автор задаёт вопросы, и как давно он здесь, скидки на новичка он не заслуживает.

Читай, оптимизатор)

Ну так и читайте. memchr как раз «оптимизирован с SIMD инструкциями».

Я на баше такое делал. Делал индекс по файлу (позиции начал строк), случайное число, по смещению лезем в индекс, по смещению из индекса - в файл. Все за О(1).

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

Суть в том, что по БД ход будет искаться доли секунды.

По большому счёту шашки и шахматы сводятся к нескольким партиям, по пути которых нужно «заставить» следовать соперника. Если он (соперник) пойдёт «совсем» не правильно - значит он проиграл.

Да и ты правильно сказал - «человек». Чтобы там себе не приписывали люди - они такие какие есть и не более того.

Витчер, это уже перебор. Не стОит в каждом школоловопросе искать XY-problem и напирать на неё. Поцику надо просто проверять наличие рандомной строки в большом текстовом файле, всё. Что за этим стоит — неважно и не должно быть важно.

Повальная XY-мания — причина того, почему я никогда ничего не спрашиваю на русскоязычных форумах.

Собственно, да.

Правильная постановка вопроса позволит не решать за O(n) задачу, которую можно решать на O(1).

Способность и желание выявить XY выгодно отличает русские форумы от зарубежных, где только маны умеют растолковать да темы закрывать.

+100500

Когда желание выявить XY довлеет над желанием помочь, конструктивного ответа можно не дождаться никогда. А ведь вопрос был задан вполне однозначно (хотя какого-нибудь Розенталя автору тоже не мешало бы почитать). Какая вам в буй разница, зачем оно ему надо? Может, он NDA подписал или по другим своим мотивам не хочет делиться более общей картиной. Может, вся (вообще вся) задача в этом и заключается — аналог grep -q свелосипедить. Я в своё время вообще в похожих целях на чистом баше обратный индекс на текстовых файликах строил, но там и данных было чуть поменьше, и поиск был не по произвольной подстроке, а по последовательности целых слов. Зачем? Да просто чтобы показать, что прототип гугла можно и на шелл-скриптах наваять и что никакой rocket science в этом нет.

Ну получит он, допустим, своё O(n). Не устроит нагрузка — раскроет новые детали задачи. Не раскроет — хрен с ним, вам-то, судари, какая печаль?

Повальная XY-мания — причина того, почему я никогда ничего не спрашиваю на русскоязычных форумах

Достаточно растолковать проблематику, тогда коллективный разум будет не XY problem искать, а оптимальное решение.

В любом случае, неполную задачу нельзя однозначно правильно и наиболее оптимально решить.

А в данном конкретном ТС пары слов не может связать и хамит при этом.

Может, вся (вообще вся) задача в этом и заключается — аналог grep -q свелосипедить

Так не понятно же. Как на это отвечать? В зависимости от конкретной цели вариантов может быть огромное множетсво.

А если строки файла это IP адреса и ТС хочет написать свой «роскомнадзор» ?

Поржал.

Тогда по этическим соображениям не следует ему помогать.

Это бы всё объяснило, кстати.

Это бы всё объяснило, кстати.

Согласен к стати. Если ТС не хочет объяснить суть своей поделки - значит хочет сделать какое-то западло. А это плохо.

На известную из стартового поста проблематику («как лучше пропарсить файл, чтобы проверять наличие в нём произвольных строк с минимальной нагрузкой») вполне ответил @gorky — фильтр Блума. Собственно, на этом уже можно проводить /thread.

Он ответил уже когда тема была помечена решенной более полусуток.

В любом случае, если файл более нескольких мегабайт лучше класть в БД.

А смысл решать высосанные из пальца задачи?

Ну так и не решай, пропусти тред. От ваших издевательств тоже смысла никакого нет.

У меня такое чувство, что пометил он ее решенной только от вашей реакции. Между тем, про блума вспомнили аж на 3 странице!

Ага, выгодно.

• У меня в гноме трей глючит.

• Гном говно, ставь КДЕ.

Да нормальная реакция была, какахами его уже потом закидали.

Да нормальная реакция была

«Я не понял твою задачу, но тебе надо генерить уиды».

Скорее всего уиды ему и нужны.

Скорее всего

Или нет, ты этого не знаешь. В любом случае, если бы HIS не писал тут комментарии «ололо какой автор тупой, а я умный», а писал что-то по делу (он этого не может, очевидно), было бы лучше. На каждом форуме есть такой чувак с раздутым ЧСВ, но все ответы которого сводятся к каким-то общим фразам не имеющим смысла.

Я посмотрел список его тредов и комментарии, везде одна вода и нет ничего по технической части, самый шедевр - ‘Меня за знания про нейросети забанили в прошлой реинкарнации…’.

и хамит при этом

По делу хамит, кстати. HIS как обычно до второй страницы тупил и докапывался, хотя задачу достаточно объяснили уже в первых постах.

Как бы так сказать… Есть такие предметные области, в которых класть в БД можно разве что на этапе прототипирования, а в «боевых» решениях допустимы только самопальные велосипеды. Я бы тоже впендрячил файл в тот же скулайт+FTI и горя не знал, но иногда надо велосипедить того же Блума, не мы такие, жизнь такая. ©

Скорее всего уиды ему и нужны.

Схренали такой вывод? Мне вот видится, что он делает некий статанализ. И уиды в этом случае мимо кассы.

Статанализ делают в БД, если боярышником не закидываться. Мне думается, что если автор не сумасшедший быдлокод пилит по генерации уидов с проверкой уникальности (меня таким не удивить, слышал, видел), то это проверка серийных номеров или чего-то в этом роде. И в том, и в другом случае это ад.

Видишь сколько разных варианов рождает сознание? По-этому и нужно нормально задачу формулировать. Правильно отведа на этот бред попросту не существует.

ТС пока, судя по постам, познаёт мир, ему что до эмбеда, что до брутального хайлоада как раком до луны.

По-этому и нужно нормально задачу формулировать.

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

+10⁶⁶⁶.

Завтра он спросит, каким ножом лучше порезать курицу

Скорее он спросил как удобнее доставать куски.

Про то что это куски курицы ничего не сказано и нужно ли их нарезать, а не разрывать к примеру - тоже.

Твои фантазии мало кому интересны, хотя вичер вон повелся сначала. Иди дальше рассказывай истории уровня «меня забанили за знания о нейросетях».

• заведи таблицу в postgreql: create table xxx(id bytea, note text, primary ley(id));
• бери от строки хеш sha3_512
• выбирай из таблицы запись с id равным этому хешу
• если записи нет - делай insert в таблицу
• все

может он не может в обучение? я слышал бывает такая проблема у некоторых людей. человек же не виноват в том, некое знание или навык ему недоступны. нас (посторонних) это может здорово раздражать (мягко говоря), но он это делает не со злого умысла…

хотя… есть ли у ТС такие особенности нам неизвестно

Такая особенность есть у большинства людей, называется она — «лень». Проявляется у всех по-разному.