109: (animated-1)
столкнулся с проблемой, из которой, кажется, получится хороший вопрос для интервью на продвинутого девелопера.

проблема такая: есть относительно длинная строка, например "lasdkfbvaouvyaou". и есть в базе таблица с миллиардом записей, в которой хранятся потенциальные подстроки, например "la", "las", "lasdk". надо их все найти как можно быстрее.

поверхностное гуглование нашло только кошмарное решение, гордо опубликованное на http://www.loganbibby.com/2011/03/reverse-pattern-matching-in-mysql

это решение сканирует всю таблицу, весь миллиард, вне зависимости от существования индексов.

чисто датабазное решение, которое приходит в голову, это поиск по индексу для каждой подстроки типа "l", "la", "las", и так далее. это даёт O(M log N), где M - количество букв в строке, а N - количество записей в таблице.

если надо лучше, то придётся в памяти строить trie, и делать по нему лукап. для дополнительного ускорения, вместо традиционного trie, где дети лежат в списке, можно держать детей в Dictionary, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
109: (animated-1)
Андрей Карпатый написал новую статью про нейронные сети, на этот раз про то, как научить сетку отличать плохое селфи от хорошего.

It does not get confused or discouraged, it just does its best with what it's been given - also see It can't be bargained with. It can't be reasoned with. And it absolutely will not stop, ever, until you are dead.

видео про визуализацию того, что происходит в промежуточных слоях сетки. pretty awesome, и получается, что сетки скорее не чёрный ящик, а серый, потому что кое-что понятно.

109: (Default)
пара примеров, с которыми недавно столкнулся.

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

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

Profile

109: (Default)
109

December 2016

S M T W T F S
    1 23
45678910
11121314151617
18192021222324
25262728293031

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags