опять греп же. Для тех, которые есть, что-то найдется. Если нет, ничего не найдется

про греп было много статей что виснет, может уже исправили, но все ли обновились

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

у тебя есть список строк и ты хочешь проверить, есть ли они в файле?

ну что-то вроде Опять есть уже финальный формата FILE_1 и есть еще 417 строк формата FILE_2 И в идеале узнать есть ли какая-то из 417 строк в FILE_1 Тем же грепом grep -wvFf file7 file1 > output

без -v

если output пустой, значит никого не нашлось

кто найдется, тот попадет в output

не верю я в линейный проход

Этот алгоритм работает за O(n) - линейней некуда

после сортировки - да, линейно

но сама сортировка это не линейно 8)

без сортировки

а без сортировки каждый с каждым

Если придераться за O(n+m) - n - количество строк в первом файле, m - количество строк во втором

for line in source: if line not in f2_set

я вижу n*m

Где там каждый с каждым?

хотя .. я не знаю, за какое время работает in для сетов

f2_set - это set проверка на вхождение во множество работает за O(1)

ок, тогда тонкое время это создание сета

оно медленнее, чем линейное

без -v

без v в out положит то что повторяется, а с v то уберет в FILE_1 если буде совпадение, я правильно все понял?

O(n) время создание сэта

ок, я не силен в волшебных алгоритмах, когда поиск в словаре делается за константу (которая на самом деле достаточно большая, чтобы в нее поместился какой-то логарифм)

я человек простой - нужно для N объектов придумать хэш без коллизий, значит минимум logN

https://wiki.python.org/moin/TimeComplexity

слова пхпешника

Слова человека, который писал под sed/awk и знает как выставить иерархию регулярок

А и да

Да там будет константа но в 99.99% случаев время будет O(n)

На sed шахматы даже писали

The Average Case times listed for dict objects assume that the hash function for the objects is sufficiently robust to make collisions uncommon.

Слова человека, который писал под sed/awk и знает как выставить иерархию регулярок

не всегда стоит юзать регулярки, если можно обойтись без них

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

не всегда стоит юзать регулярки, если можно обойтись без них

Оке, а как мне конпелятор совсем без регулярок написать ?

Но это будет быстрее чем сортировка

не писал на пхп, но знакомые пхпешники юзали регулярки всегда и всюду

ну вот говорится, что там константа, но реально эта константа зависит от количества элементов - чтобы не было коллизий.

отсюда и мнение такое

если ты зафиксируешь количество элементов, то сразу получишь эту константу. Но на практике ее можно сразу оценить снизу - и эта оценка будет логарифм

не писал на пхп, но знакомые пхпешники юзали регулярки всегда и всюду

Потому что в PHP с самого начала были нормальные регулярки а в питоне до какой-то там 3.x версии много чего в регулярках не было.

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

условно - поиск в дереве это логарифм. Но если мы скажем "для дерева глубиной не более 5, это константа"

и это будет честно

Там нету никакого дерева

а для дерева не глубже 6 - другая константа

там нет, там есть вычисление хэша

а я их типа не осилил, как они считают, а я считаю и без них есть жизнь

я просто привожу другую аналогию

так, через 10 минут мне уже домой уходить, а надо бы хоть чуть-чуть поработать

я уже привёл идеальную хеш функцию - сами числа.

Git доступен ?

https://github.com/

За VPN доступен

а без впн у кого-то работает ?

я просто привожу другую аналогию

Дело ваше.

а без впн у кого-то работает ?

да

я вполне юзаю регулярки, типа http://ix.io/1pRm

а без впн у кого-то работает ?

да

Работает

Git доступен ?

github, gitlab, aur

Узбекистан, UzbekTelecom

Мда

Git доступен ?

да

а с грепом приходится придумывать находу

Сочувствую so 2 speak. Можно уже сразу vps с тор мостами покупать

а что не так, то яндекс упал, то теперь гит

ERROR: S client not available

а с грепом приходится придумывать находу

А с sed — нет

на зато получилась интересная дискуссия, но я для себя решил, что в идеале надо написать какой-нибудь красивый алгоритм, так как возможно такая задача некоторое время будет встречаться часто

Git доступен ?

да, все норм из России

на зато получилась интересная дискуссия, но я для себя решил, что в идеале надо написать какой-нибудь красивый алгоритм, так как возможно такая задача некоторое время будет встречаться часто

не красивый, а эффектифный?

А с sed — нет

а что не так? он юзает другие либы для регекспов

не красивый, а эффектифный?

естественно, подумываю даже на С побаловаться, в свободное время

а что не так, то яндекс упал, то теперь гит

Лол. Я в начале не понял

Думал вы про вебморду

А не про то, как на неё закидывать коммит

Есть же ssh

я про греп, вы добавили что сед поступает иначе

Да, sed поступает несколько иначе

Даже чем ed

на зато получилась интересная дискуссия, но я для себя решил, что в идеале надо написать какой-нибудь красивый алгоритм, так как возможно такая задача некоторое время будет встречаться часто

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

я про греп, вы добавили что сед поступает иначе

Artsi0m Niktonov: в опёнке есть man 7 regex, в посикс манах тоже что-то подобное находилось

это ж физически логично, или память или проц

быстрее не получится

и не факт что файл всосанный в память ускорит обработку

это ж физически логично, или память или проц

Или память проца

что?

Что ?

память проца?

Ну, кэш L1, L2, L3 и т.д.

И регистры в конце концов

128 гиг ты вдуешь в кэш?

И стек .pop и .push

128 гиг ты вдуешь в кэш?

Зачем ? Я туда лучше программу запихаю

Или то, что её запускает

Не проще читать из файла блоками?

кэш измеряется в мегабайтах

Или то, что ей абстракции создаёт

Или то, что ей память раздаёт