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

[igorbor]

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

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

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

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

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

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

Comments

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