Истории из жизни

[igorbor]

Пришла однажды тетка устраиваться на работу. Судя по ее рассказам и резюме, был у нее вполне солидный опыт в программировании. Говорила она, что предпочитает работу, связанную по возможности с разработкой всяческих хитрых алгоритмов. И попросил я ее набросать мне алгоритм для определения того, является ли число простым или нет. (Задачка эта чем мне нравится - что там можно много всяческих оптимизаций придумать. Скажем, если человек в лоб делит на все предыдущие числа - это одно. Если четные пропускает - уже лучше. Если останавливается на половине - это уже что-то, а если додумывается до корня квадратного - то просто атас.)

Сначала она спросила меня, что такое простое число. Ну ладно, думаю, может быть, она образование получала не в России (мы с ней на русском разговаривали), и, соответственно, определение знает на английском или там на каком еще языке. Простое число, говорю, это число, которое делится только на себя, ну и на единицу, понятно. Вот 2, скажем - простое, а 4 - непростое. Понятно? - спрашиваю. Конечно, говорит, понятно. А делать-то, спрашивает, чего надо?

Напишите мне, говорю, алгоритм, который бы позволил для любого числа определить - простое оно или нет? И обьясняю для наглядности - вот, скажем, про 2, 3 и 4 я знаю, а вот, скажем, 37? Вот и придумайте алгоритм, который бы позволил определить, является ли число 37 простым или нет. Можете, говорю, блок-схемы рисовать, можете на псевдокоде - что Вам удобнее. Бумага-карандаш у Вас есть? не буду мешать, говорю, 15 минут Вам хватит? Да, говорит, хватит. Спасибо.

Пошел, кофе выпил, сигарету выкурил. Возвращаюсь, спрашиваю: готово? Еще пять минут, говорит.

Хорошо. Пошел, потрепался с мужиками. Возвращаюсь еще минут через 10. Готово?

Да, говорит. Готово. Является.

Comments

[lake-of-fire.livejournal.com]

На самом деле нужно как можно быстрее :-)

Для первой задачи существует несколько решений, самым "адванцед" из них является "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

Как вам оно?

[igorbor.livejournal.com]

по поводу первой задачи - я примерно это и имел ввиду, когда говорил об иерархии, только красивого слова trie я не знал :)

По поводу второго решения - это же сколько памяти понадобится, а? жуть просто!

И самое главное - я не очень понял, каким образом Ваше решение поможет в случае, когда в маске для поиска есть не только '?', но и '*'. Там же позиции букв перестают быть определенными, верно?

[lake-of-fire.livejournal.com]

по поводу первой задачи - я примерно это и имел ввиду, когда говорил об иерархии, только красивого слова trie я не знал :)

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 :-)

[lake-of-fire.livejournal.com]

a(??x98)s not 99

[igorbor.livejournal.com]

Что-то я, видимо, недопонимаю.


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.


Если я понимаю правильно, то каждое слово должно участвовать в стОльких списках, сколько в нем букв. Это значит, что общее количество узлов в списках будет равно (размер словаря)*(средняя длина слова). Это и есть "очень много" :)

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

[lake-of-fire.livejournal.com]

Obyasnite mne pozhaluista, pliz:

Это значит, что общее количество узлов в списках будет равно (размер словаря)*(средняя длина слова). Это и есть "очень много" :)

Esli ya xranu vse slova v obichnom spiske, v Unicode razve eto ne znachit chto obshee kol-vo zanimaemoi'; pamiati budet ravniatsa 2*(размер словаря)*(средняя длина слова) bytes?.

[igorbor.livejournal.com]

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

[lake-of-fire.livejournal.com]

Aga :-)
Zadacha - napisat' xoroshiy elektronniy slovar' :-)

[igorbor.livejournal.com]

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

[lake-of-fire.livejournal.com]

v tom to i delo
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 :-))

[igorbor.livejournal.com]

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

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

[lake-of-fire.livejournal.com]

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

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

[igorbor.livejournal.com]

Да. Признаю. Недодумал. Особенно "on * account", конечно, здорово. Прям хоть покупай. Дорого?

[lake-of-fire.livejournal.com]

:-))
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.

[lake-of-fire.livejournal.com]

дополнительные списки
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 :-)]