![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Истории из жизни
Пришла однажды тетка устраиваться на работу. Судя по ее рассказам и резюме, был у нее вполне солидный опыт в программировании. Говорила она, что предпочитает работу, связанную по возможности с разработкой всяческих хитрых алгоритмов. И попросил я ее набросать мне алгоритм для определения того, является ли число простым или нет. (Задачка эта чем мне нравится - что там можно много всяческих оптимизаций придумать. Скажем, если человек в лоб делит на все предыдущие числа - это одно. Если четные пропускает - уже лучше. Если останавливается на половине - это уже что-то, а если додумывается до корня квадратного - то просто атас.)
Сначала она спросила меня, что такое простое число. Ну ладно, думаю, может быть, она образование получала не в России (мы с ней на русском разговаривали), и, соответственно, определение знает на английском или там на каком еще языке. Простое число, говорю, это число, которое делится только на себя, ну и на единицу, понятно. Вот 2, скажем - простое, а 4 - непростое. Понятно? - спрашиваю. Конечно, говорит, понятно. А делать-то, спрашивает, чего надо?
Напишите мне, говорю, алгоритм, который бы позволил для любого числа определить - простое оно или нет? И обьясняю для наглядности - вот, скажем, про 2, 3 и 4 я знаю, а вот, скажем, 37? Вот и придумайте алгоритм, который бы позволил определить, является ли число 37 простым или нет. Можете, говорю, блок-схемы рисовать, можете на псевдокоде - что Вам удобнее. Бумага-карандаш у Вас есть? не буду мешать, говорю, 15 минут Вам хватит? Да, говорит, хватит. Спасибо.
Пошел, кофе выпил, сигарету выкурил. Возвращаюсь, спрашиваю: готово? Еще пять минут, говорит.
Хорошо. Пошел, потрепался с мужиками. Возвращаюсь еще минут через 10. Готово?
Да, говорит. Готово. Является.
Сначала она спросила меня, что такое простое число. Ну ладно, думаю, может быть, она образование получала не в России (мы с ней на русском разговаривали), и, соответственно, определение знает на английском или там на каком еще языке. Простое число, говорю, это число, которое делится только на себя, ну и на единицу, понятно. Вот 2, скажем - простое, а 4 - непростое. Понятно? - спрашиваю. Конечно, говорит, понятно. А делать-то, спрашивает, чего надо?
Напишите мне, говорю, алгоритм, который бы позволил для любого числа определить - простое оно или нет? И обьясняю для наглядности - вот, скажем, про 2, 3 и 4 я знаю, а вот, скажем, 37? Вот и придумайте алгоритм, который бы позволил определить, является ли число 37 простым или нет. Можете, говорю, блок-схемы рисовать, можете на псевдокоде - что Вам удобнее. Бумага-карандаш у Вас есть? не буду мешать, говорю, 15 минут Вам хватит? Да, говорит, хватит. Спасибо.
Пошел, кофе выпил, сигарету выкурил. Возвращаюсь, спрашиваю: готово? Еще пять минут, говорит.
Хорошо. Пошел, потрепался с мужиками. Возвращаюсь еще минут через 10. Готово?
Да, говорит. Готово. Является.
no subject
May I "counterinteract?" :-)
Immeetsa slovar', t.e. obshirniy nabor slov (strokovix simvolov).
Zadacha #1: Opredelit' naxoditsa li dannoe slovo W v etom slovare.
Zadacha #2: Nai'ti gruppu slov G(w) otvechayushee dannomu kluchu R, esli etot kluch = regular expression, tipa "*s*".
Kak? :-)
no subject
Первая задача зависит, конечно, от того, как построен словарь, а это, в свою очередь, зависит от того, какие слова и сколько в нем находятся. Если речь идет об обычном словаре, я бы его построил, наверное, иерархически, и тогда проверка, находится ли слово в нем, осуществяется поиском по дереву, то есть трудоемкость, очевидно, log(dict_size)
А вообще в зависимости от наиболее типичных сценариев можно придумать различные оптимизации. Например, если слова чаще НЕ НАХОДИТСЯ в словаре, можно использовать что-нибудь типа фильтра Блюма - и так далее.
По поводу второй задачи - честно говоря, в самом общем случае ничего, кроме перебора, мне в голову не приходит. Опять же зависит от конкретной задачи, наверное, при определенных условиях будет выгодно использовать обратные ключи (так это называется, да?) - но это потребует дополнительной памяти для словаря и для поиска. Нужно смотреть на конкретную задачу, но вот так, сходу - прямой поиск со сравнением, пожалуй.
А как нужно на самом деле?
no subject
Для первой задачи существует несколько решений, самым "адванцед" из них является "trie", то есть все слова вставляются в дерево из букв, на каждом ноде находятся все слова имеющие заданную букву на заданной позиции (позиция в данном случае = TreeDepth). Это решение используют на сегодняшний день все коммерческие базы данных, насколько мне известно. Правда есть ешё и "Patricia trees" и "DACG trees" но все они являются вариациями на тему тех же самых "tries".
Это решение нисколько не оптимизирует вторую задачу.
2. Опять же, вы правы, обычно для того чтоб найти любой "subset" отвечающий какому либо правилу надо идти чесать весь "set". НО - у меня есть другое решение. Вот оно:
У нас есть массив состоящий из конечного числа слов. Каждое слово состоит из конечного числа букв. Число всех букв находящихся в массиве ("Алфавит")тоже конечное. Делаем следующее:
1. Assign a unique 4-byte ID to each word
2. Assign a unique 4-byte ID to each letter
{Это нумируем, типа}
3. Create a 2D array |Alphavit| X Max(L) (Max(L) being the length of the longest word in the set)
4. Each cell (i, j) will contain pointers to all wordIDs that contain the letter j in position i.
Takim obrazom, kogda my ishem "abc", we need to intersect the array pointed to by the cell (1,'a') with the array pointed to by (2, 'b') and with the array (3, 'c').
Kogda my ishem "a?c" -
- Get array of (1,'a')
- For i=0 to Length_Of_Matrix Get array of (2, Alphavit[i])
- intersect
- Get array of (3, 'c')
- intersect
Как вам оно?
no subject
По поводу второго решения - это же сколько памяти понадобится, а? жуть просто!
И самое главное - я не очень понял, каким образом Ваше решение поможет в случае, когда в маске для поиска есть не только '?', но и '*'. Там же позиции букв перестают быть определенными, верно?
no subject
Da, ya tak i poniala, konechno vy byli pravi. Izvinite esli ya neyasno virazilas' - eto vse moyo kosnoyazichie.
По поводу второго решения - это же сколько памяти понадобится, а? жуть просто!
Na samom dele net.
Na samom dele 4*SizeOf(Alphavit)*MaxL = bytes dlia soxraneniya
matrizi (MaxL = dlina maksimalnogo slova)
I 4*L bytes dlia kazhdogo slova (L = dlina slova)
eto v 2 raza bol'she chem sushestvuyushii' na segodnia Unicode.
Po moemu uskorenie poiska opravdivaet takie zatrati.
И самое главное - я не очень понял, каким образом Ваше решение поможет в случае, когда в маске для поиска есть не только '?', но и '*'. Там же позиции букв перестают быть определенными, верно?
Ne sovsem.
Na samom dele vse rabotaet nemnozhko inache chem tut napisano.
Esli ya ishu "a*s" znachit ya ishu "vse slova imeyushie 'a' v 1oy pozicii i 's' otstoyashii' ot 'a' v [1,2,...] MatrixWidth pozicii
To est' imeya matricu shirinoy v 100, ya ishu:
as
a?s
a??s
...
a(?? x 99)s
Na dele voobshe ves' poisk osushetsvlaetsa posredstvom sostavleniya "marshruta" (DACG) po etoi' samoi' matrice, to est' "ishi bukvu takuyu to na rasstoyanii takom to (ot currentPosition)". Ya ishu 'a' na rasstoyanii 0 ot current position i s na rasstoyanii "unknown" ot a. Eto rasstoyanie imeet granizi - ot 1 do MatrixWidth - Length(RestOfKey). Na kazhdoi' iz etix pozicii' nado vziat' wordIDArray pointed to by letter 's' and intersect with previous results. The results of all such intersections should be appended.
i vse :-)
no subject
no subject
3. Create a 2D array |Alphavit| X Max(L) (Max(L) being the length of the longest word in the set)
4. Each cell (i, j) will contain pointers to all wordIDs that contain the letter j in position i.
Если я понимаю правильно, то каждое слово должно участвовать в стОльких списках, сколько в нем букв. Это значит, что общее количество узлов в списках будет равно (размер словаря)*(средняя длина слова). Это и есть "очень много" :)
Конечно, все зависит от соотношения цены памяти и процессора. Возможно, для каких-то задач удвоить память под словарь - вполне приемлимо.
no subject
Это значит, что общее количество узлов в списках будет равно (размер словаря)*(средняя длина слова). Это и есть "очень много" :)
Esli ya xranu vse slova v obichnom spiske, v Unicode razve eto ne znachit chto obshee kol-vo zanimaemoi'; pamiati budet ravniatsa 2*(размер словаря)*(средняя длина слова) bytes?.
no subject
no subject
Zadacha - napisat' xoroshiy elektronniy slovar' :-)
no subject
no subject
kogda ishesh ne slovo
a gruppu slov otvechayushix kakomu to kriteriju.
naprimer advers*
kogda xochesh nayti i adverse i adversity i adversing i ...
ili naprimer ???
kogda xochesh nai'ti vse slova iz trex bukv :-)
neuzheli it is not useful?
A klient tak xotel, tak xotel...
i tak platil, taaak platil.. do six por plotit, mezhdu prochim :-))
no subject
Насчет второго - слов из трех букв - я опять же не понимаю, какой в этом практический смысл. Кроссворды составлять? Хотя хозяин - барин, безусловно.
no subject
Ne skazhite, sudar'. Kak naschet naprimer, ivrita?
Kak naschet "go", "going", "undergo", "overgo"?
A kogda vy ne uvereni kak pravilno pishetsa slovo? Vy dumaete vse polzovateli umeyut bistro-bistro bez oshibok napisat' "elektrofikaziya"? :-))
A kak byt' s idiomami / phrasal verbs? "on my / his account?" Est' u nas takoi' headword v slovare. I kak zhe bednomu polzovatelju nayti prosto 'on somebody's account'?
ne znayu, koroche, mi tut u sebia pervuju versiyu zafigachili - narod tashitsa.
I vaashe - moyo delo predlagat'. Oni sami pokupayut kogda nado :-)
S uvazheniem
Gera
no subject
no subject
Spasibo na dobrom slove :-)
U nas est' seychas pervaya versiya kotoruyu mi budem besplatno razdavat' kak prilozhenie k prodayusheysa knige-slovaru.
Ya mogu vam poslat' installatziyu esli vam eto interesno.
Tam konechno more vsego sdelannogo ne tak kak ya xotela no na to ona i pervaya versiya.
no subject
it is not "in addition to"
it is "instead of"
Vot v chem fishka :-)
Kak by "alternative encoding" tipa ;-)
[nu... ved' xochetsja zh nemnozhko pogorditsa :-)]