![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
reverse engineering the neocortex
May. 6th, 2016 11:56 pmawesome
reverse prefix search
Nov. 16th, 2015 01:53 pmстолкнулся с проблемой, из которой, кажется, получится хороший вопрос для интервью на продвинутого девелопера.
проблема такая: есть относительно длинная строка, например "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, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
проблема такая: есть относительно длинная строка, например "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, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
Андрей Карпатый написал новую статью про нейронные сети, на этот раз про то, как научить сетку отличать плохое селфи от хорошего.
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, и получается, что сетки скорее не чёрный ящик, а серый, потому что кое-что понятно.
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, и получается, что сетки скорее не чёрный ящик, а серый, потому что кое-что понятно.
асинхронные протоколы
May. 5th, 2009 02:09 pmпара примеров, с которыми недавно столкнулся.
1. на кампусе развелось много брошенных велосипедов. как определить, брошен велосипед, или нет? а вот: в один прекрасный день на все велосипеды лепятся стикеры. через несколько дней те велосипеды, на которых стикеры остались, забирают. этот же способ работает и с едой, забытой в холодильнике (тёма как-то открывал конкурс на тему, что делать с едой).
2. рутовый пароль, хранимый в запечатанном конверте на видном месте. если какая-то срочная нештатная ситуация - разрывай конверт и используй. пришедший админ, увидев разорванный конверт, будет разбираться.
1. на кампусе развелось много брошенных велосипедов. как определить, брошен велосипед, или нет? а вот: в один прекрасный день на все велосипеды лепятся стикеры. через несколько дней те велосипеды, на которых стикеры остались, забирают. этот же способ работает и с едой, забытой в холодильнике (тёма как-то открывал конкурс на тему, что делать с едой).
2. рутовый пароль, хранимый в запечатанном конверте на видном месте. если какая-то срочная нештатная ситуация - разрывай конверт и используй. пришедший админ, увидев разорванный конверт, будет разбираться.
