Журнал LinuxFormat - перейти на главную

LXF154:Erlang

Материал из Linuxformat
Перейти к: навигация, поиск

Содержание

Erlang

Erlang - Опи­сы­ва­ет­ся сле­дую­щей фор­му­лой:функ­цио­наль­ный язык + про­цес­сы

Erlang: И сно­ва прак­ти­кум.Во­ды ре­ше­том не на­но­сишь­ся, а вот про­стые чис­ла Ан­д­рею Уша­ко­ву в не­го по­па­да­ют­ся – ну, не без со­дей­ст­вия Эра­тос­фе­на.

Наш эксперт

Ан­д­рей Уша­ков ак­тив­но при­бли­жа­ет тот день, ко­гда функ­цио­наль­ные язы­ки ста­нут мейн­ст­ри­мом.


В этом но­ме­ре мы про­дол­жим наш прак­ти­кум по функ­цио­наль­но­му про­грам­ми­ро­ванию на язы­ке Erlang и раз­бе­рем­ся, как нам ра­бо­тать с раз­ны­ми кол­лек­ция­ми, доступ­ны­ми в язы­ке и в биб­лио­те­ке Erlang.

Мы помним (LXF147), что кол­лек­ции пред­на­зна­че­ны для си­туа­ций, когда мы хо­тим об­ра­ба­ты­вать хранимые в них дан­ные одним и тем же спо­со­бом. Этим они кон­цеп­ту­аль­но от­ли­ча­ют­ся от дру­го­го фун­да­мен­таль­но­го со­став­но­го ти­па дан­ных функ­цио­наль­но­го про­грам­ми­ро­вания – кор­те­жей. Кон­цеп­ту­аль­ное от­ли­чие оз­на­ча­ет, что с точ­ки зрения тео­рии кол­лек­ции и кор­те­жи пред­на­зна­че­ны для хранения дан­ных, об­ра­бот­ка ко­то­рых бу­дет про­из­во­дить­ся по-раз­но­му: дан­ные в кол­лек­ци­ях об­ра­ба­ты­ва­ют­ся одним и тем же спо­со­бом, тогда как дан­ные в кор­те­жах об­ра­ба­ты­ва­ют­ся раз­ны­ми спо­со­ба­ми в за­ви­си­мо­сти от рас­по­ло­жения (по­зи­ции) дан­ных. Дру­ги­ми сло­ва­ми, кол­лек­ции пред­на­зна­че­ны для го­мо­ген­ных дан­ных (воз­мож­но, раз­ных ти­пов), а кор­те­жи – для ге­те­ро­ген­ных (воз­мож­но, имею­щих один и тот же тип) В ре­аль­ной жизни это не обя­за­тель­но, и грань ме­ж­ду кол­лек­ция­ми и кор­те­жа­ми силь­но раз­мы­та. Мы мо­жем ис­поль­зо­вать кор­те­жи для хранения го­мо­ген­ных дан­ных, как сде­ла­но, на­при­мер, в реа­ли­за­ции мас­си­вов в мо­ду­ле array. Ана­ло­гич­но, мы мо­жем ис­поль­зо­вать кол­лек­ции для хранения ге­те­ро­ген­ных дан­ных.

Пе­ред ис­поль­зо­ванием кол­лек­ций в сво­их про­грам­мах необ­хо­ди­мо по­ста­вить во­прос о ти­пе (и, воз­мож­но, реа­ли­за­ции это­го ти­па) ис­поль­зуе­мой кол­лек­ции. Этот во­прос от­но­сит­ся к пра­виль­но­му про­ек­ти­ро­ванию раз­ра­ба­ты­вае­мо­го при­ло­жения: ес­ли вы­брать непод­хо­дя­щий тип кол­лек­ции, то та­кой вы­бор мо­жет при­вес­ти к до­полнитель­ным за­тра­там – как во вре­мя реа­ли­за­ция, так и во вре­мя под­держ­ки при­ло­жения.

В язы­ке и биб­лио­те­ке Erlang доступ­ны сле­дую­щие ти­пы кол­лек­ций: спи­ски, мас­си­вы, мно­же­ст­ва и сло­ва­ри (точнее го­во­ря, спи­ски яв­ля­ют­ся сред­ст­вом са­мо­го язы­ка, а все осталь­ные кол­лек­ции доступ­ны че­рез биб­лио­теч­ные мо­ду­ли). Для мно­жеств и сло­ва­рей у нас есть несколь­ко реа­ли­за­ций: стан­дарт­ная реа­ли­за­ция (для ко­то­рой спо­соб хранения дан­ных не спе­ци­фи­ци­ро­ван, но в дан­ной вер­сии биб­лио­те­ки она ис­поль­зу­ет хэш-таб­ли­цы), реа­ли­за­ция на осно­ве упо­ря­до­чен­ных спи­сков и реа­ли­за­ция на осно­ве сба­лан­си­ро­ван­ных дво­ич­ных де­ревь­ев.

Те­перь за­дадимся во­просом: как пра­виль­но вы­брать тот или иной тип кол­лек­ции (и, воз­мож­но, ту или иную реа­ли­за­цию)? От­вет оче­ви­ден: все за­ви­сит от то­го, как планиру­ет­ся ис­поль­зо­вать вы­би­рае­мую кол­лек­цию и ка­кие к ней есть тре­бо­вания. Ес­ли осо­бых тре­бо­ваний нет или в пер­вую оче­редь необ­хо­ди­ма гиб­кость ра­бо­ты, ко­то­рая есть у спи­сков, то вы­бор оче­ви­ден – спи­ски. Ес­ли нужно хранить дан­ные в оп­ре­де­лен­но­м мес­те (по ин­дек­су) и уметь их из­ме­нять, не ме­няя мес­та (ин­дек­са), то наш вы­бор – мас­си­вы.

Тут сле­ду­ет за­ме­тить сле­дую­щее: спи­ски лег­ко по­зво­ля­ют по­лу­чить доступ к эле­мен­ту по оп­ре­де­лен­но­му ин­дек­су (для это­го слу­жит функ­ция lists:nth/2), но за­дать но­вое зна­чение в спи­ске по оп­ре­де­лен­но­му ин­дек­су так про­сто нель­зя (для это­го нет со­от­вет­ст­вую­щей функ­ции в мо­ду­ле lists). Что­бы по­ме­нять зна­чение по оп­ре­де­лен­но­му ин­дек­су в спи­ске, необ­хо­ди­мо дей­ст­во­вать, как в сле­дую­щем при­ме­ре. Пусть List = [1,2,3,4,5,6] – ис­ход­ный спи­сок, а N = 4 – ин­декс эле­мен­та, ко­то­рый необ­хо­ди­мо по­ме­нять (ин­дексы списка на­чи­нают­ся с 1); тогда ре­шение этой за­да­чи мо­жет быть сле­дую­щим:

{Part1, [Element | Part2]} = lists:split(N – 1, List).

P1 ++ [444] ++ P2.

Ре­зуль­та­том будет спи­сок, по­лу­чае­мый из ис­ход­но­го за­ме­ной 4-го эле­мен­та на зна­чение 444: [1,2,3,444,5,6]. Ес­ли требуется функ­цио­наль­ность мно­жеств ли­бо сло­ва­рей, сле­ду­ет вы­брать од­ну из реа­ли­за­ций мно­жеств и сло­ва­рей (в за­ви­си­мо­сти от то­го, ва­жен ли нам по­ря­док эле­мен­тов). Что ин­те­рес­но, ес­ли нам нуж­на кол­лек­ция на осно­ве пар ключ–зна­чение (для хранения та­ких пар и пред­на­зна­че­ны сло­ва­ри), то вме­сто сло­ва­ря мож­но вы­брать спи­ски (ес­ли нам важ­на их гиб­кость): мо­дуль lists со­дер­жит бо­га­тый на­бор функ­ций для ра­бо­ты со спи­ска­ми, хра­ня­щи­ми на­бо­ры ключ–зна­чение (в ви­де кор­те­жей, что ес­те­ст­вен­но). Не за­будем так­же, что все ти­пы кол­лек­ций со­дер­жат функ­ции from_list/1 и to_list/1 для кон­вер­та­ции сво­его со­дер­жи­мо­го в спи­ски и об­рат­но.

Рас­смот­рим несколь­ко при­ме­ров. Для начала реа­ли­зу­ем ал­го­ритм, из­вест­ный как «Ре­ше­то Эра­тосфе­на». Это ал­го­ритм на­хо­ж­дения всех про­стых чи­сел до неко­то­ро­го за­дан­но­го чис­ла, ав­тор­ст­во которо­го при­пи­сы­ва­ют древнегре­че­­ско­­му ма­те­ма­ти­ку Эра­тосфе­ну Ки­рен­ско­му. Ос­нов­ная его идея такова. Мы вы­пи­сы­ва­ем все чис­ла от 2 до N (где N оп­ре­де­ля­ет ин­те­ре­сую­щий нас диа­па­зон). Затем бе­рем пер­вое чис­ло (это бу­дет 2) и вы­чер­ки­ва­ем все чис­ла из спи­ска, крат­ные ему. Далее, бе­рем сле­дую­щее не вы­черк­ну­тое чис­ло (это бу­дет 3) и вы­чер­ки­ва­ем из спи­ска все чис­ла, крат­ные это­му чис­лу. И так будем по­сту­пать до тех пор, по­ка не упремся в границу диапазона.Тогда все не вы­черк­ну­тые чис­ла в спи­ске бу­дут яв­лять­ся про­сты­ми чис­ла­ми в заданном диа­па­зоне.

Из основ­ной идеи ал­го­рит­ма вид­но, что нам необ­хо­ди­мо иметь опе­ра­цию вы­чер­ки­вания. По­нят­но, что ее мож­но реа­ли­зо­вать так, что­бы чис­ло дей­ст­ви­тель­но «вы­чер­ки­ва­лось» (уда­ля­лось) из кол­лек­ции, но вряд ли та­кая реа­ли­за­ция бу­дет оп­ти­маль­ной (уда­ление эле­мен­та из кол­лек­ции – не са­мая лег­кая опе­ра­ция). По­это­му мы реа­ли­зу­ем опе­ра­цию вы­чер­ки­вания сле­дую­щим об­ра­зом: бу­дем хранить па­ру чис­ло–флаг, который по­ка­зы­вает, вы­черк­нуто ли дан­ное чис­ло из спи­ска или нет.

Те­перь вы­берем тип кол­лек­ции для хранения та­ких пар. На пер­вый взгляд ка­жет­ся, что иде­аль­ный ва­ри­ант в на­шем слу­чае – сло­варь (ас­со­циа­тив­ная кол­лек­ция для хранения пар ключ – зна­чение). Но да­вай­те уч­тем тот факт, что мы бу­дем ра­бо­тать с непре­рыв­ным ря­дом чи­сел в диа­па­зоне от 2 до N; по­это­му мож­но вы­брать в ка­че­­ст­ве кол­лек­ции мас­сив. При та­ком вы­бо­ре чис­ло ста­но­вит­ся ин­дек­сом мас­си­ва (точнее, чис­ло за вы­че­том 2, т. к. ну­ме­ра­ция эле­мен­тов мас­си­ва на­чи­на­ет­ся с 0), а флаг – зна­чением элемента мас­си­ва.

Вполне ло­ги­чен во­прос: а по­че­му бы не ис­поль­зо­вать в ка­че­­ст­ве кол­лек­ции спи­ски? Они ведь то­же яв­ля­ют­ся кол­лек­ци­ей с досту­пом к эле­мен­там по ин­дек­су! При­чи­на, по ко­то­рой мы не вы­би­ра­ем спи­ски в ка­че­­ст­ве кол­лек­ции для хранения – в том, что для спи­сков от­сут­ст­ву­ет опе­ра­ция уста­нов­ки зна­чения эле­мен­та по оп­ре­де­лен­но­му ин­дек­су, в от­ли­чие от мас­си­вов.

По­сле это­го неболь­шо­го об­су­ж­дения ал­го­рит­ма и неко­то­рых де­та­лей его реа­ли­за­ции пе­рей­дем к делу. Как и во всех прочих при­ме­рах, реа­ли­за­ция на­чи­на­ет­ся с объ­яв­ления мо­ду­ля:

-module(eratos_sieve).

Сле­дую­щий шаг то­же вполне оче­ви­ден: объ­яв­ление экс­пор­ти­руе­мых функ­ций. В на­шем при­ме­ре доста­точ­но экс­пор­ти­ро­вать все­го лишь од­ну функ­цию: get_primes/1, воз­вра­щаю­щую спи­сок всех про­стых чи­сел от 2 до N, где N яв­ля­ет­ся вход­ным па­ра­мет­ром функ­ции.

-export([get_primes/1]).

Те­перь пе­рей­дем к реа­ли­за­ции ал­го­рит­ма. Начнем с экс­пор­ти­руе­мой функ­ции get_primes/1. Она вы­пол­ня­ет две за­да­чи: фор­ми­ру­ет ссылку на мас­сив Sieve [англ. ре­ше­то] с вы­черк­ну­ты­ми и не вы­черк­ну­ты­ми но­ме­ра­ми и пре­вра­ща­ет ре­ше­то в спи­сок про­стых чи­сел. Пер­вую за­да­чу ре­ша­ет функ­ция process_iteration/3, вто­рую за­да­чу ре­ша­ет функ­ция create_number_list/4.

Об­ра­ти­те внимание, как мы соз­да­ем ис­ход­ный мас­сив, в ко­то­ром еще нет вы­черк­ну­тых чи­сел: мы ис­поль­зу­ем функ­цию array:new/1, в ко­то­рую пе­ре­да­ем спи­сок пар ключ–зна­чение (спи­сок кор­те­жей из двух эле­мен­тов). В на­шем слу­чае мы соз­да­ем мас­сив фик­си­ро­ван­но­го раз­ме­ра, все эле­мен­ты ко­то­ро­го име­ют зна­чение по умол­чанию, рав­ное true (true оз­на­ча­ет, что со­от­вет­ст­вую­щее чис­ло еще не вы­черк­ну­то).

get_primes(MaxNumber) ->

Sieve = process_iteration(array:new([{size, MaxNumber-1}, {fixed, true}, {default, true}]), 2, MaxNumber), create_number_list(Sieve, 2, MaxNumber, []).

Ос­нов­ная за­да­ча ал­го­рит­ма – вы­черк­нуть все не про­стые чис­ла из спи­ска чи­сел (сфор­ми­ро­вать ре­ше­то). Ее ре­ша­ет функ­ция process_iteration/3. Эта функ­ция яв­ля­ет­ся ре­кур­сив­ной функ­ци­ей (функ­ци­ей с хво­сто­вой ре­кур­си­ей), ка­ж­дая ите­ра­ция ко­то­рой об­ра­ба­ты­ва­ет оче­ред­ное про­стое чис­ло из спи­ска (вы­чер­ки­ва­ет все чис­ла, крат­ные об­ра­ба­ты­вае­мо­му чис­лу). Эта функ­ция со­дер­жит два ва­ри­ан­та. Пер­вый ва­ри­ант об­ра­ба­ты­ва­ет си­туа­цию, когда мы не мо­жем най­ти оче­ред­ное про­стое чис­ло (а это оз­на­ча­ет, что мы дош­ли до кон­ца спи­ска); этот ва­ри­ант яв­ля­ет­ся не ре­кур­сив­ным и по­зво­ля­ет нам за­кон­чить ре­кур­сив­ное вы­чер­ки­вание чи­сел. Вто­рой ва­ри­ант яв­ля­ет­ся ре­кур­сив­ным, и на ка­ж­дой ите­ра­ции для за­дан­но­го про­сто­го чис­ла (че­рез один из па­ра­мет­ров), вы­чер­ки­вает все чис­ла, крат­ные за­дан­но­му про­сто­му чис­лу.

Опе­ра­цию вы­чер­ки­вания мо­жно слег­ка оп­ти­ми­зи­ро­вать: оче­вид­но, что для текуще­го простого чис­ла p вы­чер­ки­вать ­надо, на­чи­ная с чис­ла p2, так как все составные чис­ла до p2 уже вы­черк­ну­ты. По­сле вы­чер­ки­вания всех крат­ных чи­сел, функ­ция process_iteration/3 вы­зы­ва­ет­ся для сле­дую­ще­го про­сто­го (не вы­черк­ну­то­го) чис­ла.

process_iteration(Sieve, not_found, _MaxNumber) -> Sieve;

process_iteration(Sieve, Current, MaxNumber) ->

NewSieve = erase_multiple(Sieve, Current*Current, MaxNumber, Current), process_iteration(NewSieve, find_next_prime(Sieve, Current+1, MaxNumber), MaxNumber).

В кон­це ка­ж­дой ите­ра­ции функ­ции process_iteration/3 нам необ­хо­ди­мо най­ти сле­дую­щее про­стое (не вы­черк­ну­тое) чис­ло от­но­си­тель­но за­дан­но­го про­сто­го чис­ла. За эту за­да­чу от­ве­ча­ет функ­ция find_next_prime/3. В ней по­сле­до­ва­тель­но про­смат­ри­ва­ет­ся спи­сок чи­сел (при по­мо­щи хво­сто­вой ре­кур­сии), на­чи­ная с неко­то­ро­го за­дан­но­го чис­ла, и вы­би­ра­ет­ся пер­вое не вы­черк­ну­тое чис­ло. Ес­ли в ка­кой-то мо­мент мы пе­ре­бра­ли весь спи­сок и не на­шли ни од­но­го не вы­черк­ну­то­го чис­ла, то мы воз­вра­ща­ем атом not_found (за это от­ве­ча­ет пер­вый ва­ри­ант этой функ­ции). Это зна­чение оп­ре­де­ля­ет вы­бор пер­во­го ва­ри­ан­та функ­ции process_iteration/3, что оз­на­ча­ет окон­чание опе­ра­ции вы­чер­ки­вания (фор­ми­ро­вания реше­та).

find_next_prime(_Sieve, Current, MaxNumber) when Current > MaxNumber -> not_found;

find_next_prime(Sieve, Current, MaxNumber) ->

case array:get(Current-2, Sieve) of

true -> Current;

false -> find_next_prime(Sieve, Current+1, MaxNumber)

end.

Сле­дую­щая функ­ция, ко­то­рую мы рас­смот­рим – это функ­ция для вы­чер­ки­вания чи­сел erase_multiple/4. В этой функ­ции мы про­хо­дим по мас­си­ву (при по­мо­щи хво­сто­вой ре­кур­сии) и вы­чер­ки­ва­ем чис­ла, крат­ные за­дан­но­му чис­лу (опе­ра­ция вы­чер­ки­вания оз­на­ча­ет, что мы уста­нав­ли­ва­ем зна­чение false по ин­дек­су, со­от­вет­ст­вую­ще­му чис­лу).

erase_multiple(Sieve, Current, MaxNumber, _Delta) when Current > MaxNumber -> Sieve;

erase_multiple(Sieve, Current, MaxNumber, Delta) ->

erase_multiple(array:set(Current-2, false, Sieve), Current+Delta, MaxNumber, Delta).

И, на­конец, остал­ся по­следний не рас­смот­рен­ный на­ми ме­тод: create_number_list/4. Этот ме­тод слу­жит для пре­об­ра­зо­вания мас­си­ва фла­гов, вы­черк­ну­то или не вы­черк­ну­то чис­ло, со­от­вет­ст­вую­щее ин­дек­су в спи­ске про­стых чи­сел. В этом ме­то­де мы по­сле­до­ва­тель­но идем по мас­си­ву фла­гов (при по­мо­щи хво­сто­вой ре­кур­сии), и ес­ли флаг ра­вен true (т. е. со­от­вет­ст­вую­щее чис­ло не вы­черк­ну­то), то мы до­бав­ля­ем это чис­ло в на­ча­ло спи­ска про­стых чи­сел. Пройдя весь мас­сив фла­гов, мы пе­ре­во­ра­чи­ва­ем спи­сок (при по­мо­щи lists:reverse/1), что­бы про­стые чис­ла шли в нем в по­ряд­ке воз­рас­тания, и воз­вра­ща­ем его. На­помним так­же сле­дую­щее со­от­но­шение ме­ж­ду чис­лом и со­от­вет­ст­вую­щим ему ин­дек­сом фла­га в мас­си­ве: т. к. мы рас­смат­ри­ва­ем диа­па­зон чи­сел от 2 до N, а ну­ме­ра­ция эле­мен­тов мас­си­ва на­чи­на­ет­ся с 0, то зна­чение вы­ра­жения «чис­ло ми­нус его ин­декс» рав­но 2.

create_number_list(_Sieve, Current, MaxNumber, Dest) when Current > MaxNumber -> lists:reverse(Dest);

create_number_list(Sieve, Current, MaxNumber, Dest) ->

case array:get(Current-2, Sieve) of

true -> create_number_list(Sieve, Current+1, MaxNumber, [Current]++Dest);

false -> create_number_list(Sieve, Current+1, MaxNumber, Dest)

end.

Те­перь по­ра все от­ком­пи­ли­ро­вать и удосто­ве­риться в коррект­ности на­шей реа­ли­за­ции ал­го­рит­ма. Для это­го за­пустим сре­ду вы­полнения Erlang и ском­пи­ли­ру­ем мо­дуль eratos_sieve (ко­ман­дой c(eratos_sieve).). Про­ве­рим, что все ра­бо­та­ет пра­виль­но: так, на­при­мер, вы­зов eratos_sieve:get_primes(20). воз­вра­ща­ет все про­стые чис­ла в диа­па­зоне от 2 до 20: [2, 3, 5, 7, 11, 13, 17, 19].

На осно­ве при­ве­ден­но­го вы­ше при­ме­ра да­вай­те ре­шим сле­дую­щий при­мер, в ка­че­­ст­ве ­которо­го возь­мем за­да­чу но­мер 35 с сайта Project Euler (http://projecteuler.net/problem=35). Ус­ло­вие этой за­да­чи вы­гля­дит сле­дую­щим об­ра­зом.

Чис­ло 197 на­зы­ва­ет­ся цик­ли­че­­ским про­стым чис­лом, по­то­му что все чис­ла, по­лу­чаю­щие­ся из это­го чис­ла при по­мо­щи цик­ли­че­­ских пе­ре­ста­но­вок цифр (это бу­дут чис­ла 197, 971 и 719), яв­ля­ют­ся про­сты­ми. Су­ще­ст­ву­ет толь­ко 13 та­ких про­стых чи­сел мень­ше 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97. Сколь­ко су­ще­ст­ву­ет цик­ли­че­­ских про­стых чи­сел мень­ше 1 000 000?

Из усло­вия за­да­чи по­нят­но, что пер­вым ша­гом бу­дет по­иск всех про­стых чи­сел мень­ше 1 000 000 – имен­но то, что де­ла­ет пре­ды­ду­щий при­мер. По­сле это­го для ка­ж­до­го про­сто­го чис­ла мы бу­дем стро­ить все его цик­ли­че­­ские пе­ре­ста­нов­ки и про­ве­рять, яв­ля­ют­ся ли они про­сты­ми. По­нят­но, что предварительно мы выясним, не об­ра­ба­ты­ва­лось ли дан­ное про­стое чис­ло.

Начнем реа­ли­за­цию как обыч­но: с объ­яв­ления мо­ду­ля и спи­ска экс­пор­ти­руе­мых функ­ций.

-module(problem_035).

-export([solve/1]).

Спи­сок экс­пор­ти­руе­мых функ­ций со­дер­жит у нас толь­ко од­ну функ­цию – solve/1. Эта функ­ция воз­вра­ща­ет ко­ли­че­­ст­во цик­ли­че­­ских про­стых чи­сел, мень­ших, чем зна­чение па­ра­мет­ра функ­ции MaxNumber. Ра­бо­та функ­ции solve/1 со­сто­ит из сле­дую­щих двух ша­гов: соз­дание спи­ска всех про­стых чи­сел, мень­ших зна­чения MaxNumber, и соз­дание мно­же­ст­ва цик­ли­че­­ских про­стых чи­сел из спи­ска про­стых чи­сел (ко­ли­че­­ст­во цик­ли­че­­ских про­стых чи­сел рав­но раз­ме­ру это­го мно­же­ст­ва). Пер­вый шаг ре­ша­ет­ся при по­мо­щи функ­ции eratos_sieve:get_primes/1 из пре­ды­ду­ще­го при­ме­ра. Для вто­ро­го ша­га мы вво­дим функ­цию find_circular_primes/1.

solve(MaxNumber) ->

PrimeNumbers = eratos_sieve:get_primes(MaxNumber),

sets:size(find_circular_primes(PrimeNumbers)).

Функ­ция find_circular_primes/1 яв­ля­ет­ся ин­тер­фейс­ной функ­ци­ей к функ­ции find_circular_primes/3. В ней из спи­ска про­стых чи­сел, по­лу­чен­но­го на пре­ды­ду­щем ша­ге, мы стро­им мно­же­ст­во про­стых чи­сел. По­ми­мо это­го, мы соз­да­ем пустое мно­же­ст­во для хранения цик­ли­че­­ских про­стых чи­сел.

find_circular_primes(PrimeNumbers) ->

find_circular_primes(PrimeNumbers, sets:from_list(PrimeNumbers), sets:new()).

Функ­ция find_circular_primes/3 яв­ля­ет­ся цен­траль­ной для по­строения мно­же­ст­ва цик­ли­че­­ских про­стых чи­сел. Функ­ция принима­ет три па­ра­мет­ра: спи­сок необ­ра­бо­тан­ных про­стых чи­сел, мно­же­ст­во всех про­стых чи­сел, мень­ших за­дан­но­го, и мно­же­ст­во цик­ли­че­­ских про­стых чи­сел. Си­туа­ция, когда спи­сок необ­ра­бо­тан­ных про­стых чи­сел пуст, яв­ля­ет­ся усло­ви­ем окон­чания об­ра­бот­ки (а также шаб­ло­ном для вы­бо­ра должного ва­ри­ан­та функ­ции).

Ос­нов­ной ва­ри­ант этой функ­ции ре­кур­сив­но об­ра­ба­ты­ва­ет (при по­мо­щи хво­сто­вой ре­кур­сии) спи­сок необ­ра­бо­тан­ных про­стых чи­сел по­эле­мент­но. На ка­ж­дой ите­ра­ции мы про­ве­ря­ем, не на­хо­дит­ся ли текущее про­стое чис­ло во мно­же­ст­ве цик­ли­че­­ских про­стых чи­сел (что оз­на­ча­ет, что мы это чис­ло уже об­ра­бо­та­ли). Ес­ли про­вер­ка да­ет по­ло­жи­тель­ный ре­зуль­тат, то мы про­сто пе­ре­хо­дим к сле­дую­щей ите­ра­ции. В про­тив­ном слу­чае, мы стро­им спи­сок всех чи­сел, по­лу­чае­мых из об­ра­ба­ты­вае­мо­го про­сто­го чис­ла цик­ли­че­­ским сдви­гом цифр (этот спи­сок вклю­ча­ет и об­ра­ба­ты­вае­мое про­стое чис­ло), про­ве­ря­ем, все ли чис­ла из по­стро­ен­но­го спи­ска яв­ля­ют­ся про­сты­ми чис­ла­ми, и ес­ли все чис­ла из по­стро­ен­но­го спи­ска яв­ля­ют­ся про­сты­ми, до­бав­ля­ем их во мно­же­ст­во цик­ли­че­­ских про­стых чи­сел. По­сле че­го пе­ре­хо­дим к сле­дую­щей ите­ра­ции.

find_circular_primes([], _PrimeSet, CircularPrimeSet) -> CircularPrimeSet;

find_circular_primes([PrimeNumber | Rest], PrimeSet, CircularPrimeSet) ->

case sets:is_element(PrimeNumber, CircularPrimeSet) of

false ->

CircularNumbers = create_circular_numbers(PrimeNumber), NewCircularPrimeSet = check_and_add_numbers(CircularNumbers, PrimeSet, CircularPrimeSet),

find_circular_primes(Rest, PrimeSet, NewCircularPrimeSet);

true -> find_circular_primes(Rest, PrimeSet, CircularPrimeSet)

end.

Функ­ция check_and_add_numbers/3 про­ве­ря­ет, яв­ля­ют­ся ли чис­ла из спи­ска, по­стро­ен­но­го при по­мо­щи цик­ли­че­­ско­­го сдви­га цифр ис­ход­но­го про­сто­го чис­ла, про­сты­ми чис­ла­ми. Ес­ли все чис­ла яв­ля­ют­ся про­сты­ми, это оз­на­ча­ет, что все они яв­ля­ют­ся и цик­ли­че­­ски­­ми про­сты­ми чис­ла­ми. В таком слу­чае, мы все эти чис­ла до­бав­ля­ем во мно­же­ст­во цик­ли­че­­ских про­стых чи­сел. Для про­вер­ки спи­ска це­лых чи­сел мы ис­поль­зу­ем функ­цию lists:all/2, для до­бав­ления этих чи­сел во мно­же­ст­во цик­ли­че­­ских про­стых чи­сел – функ­цию lists:foldl/3.

check_and_add_numbers(Numbers, PrimeSet, CircularPrimeSet) ->

Check = lists:all(fun(Number) -> sets:is_element(Number, PrimeSet) end, Numbers),

if

Check == true -> lists:foldl(fun(Number, Dest) -> sets:add_element(Number, Dest) end, CircularPrimeSet, Numbers);

Check == false -> CircularPrimeSet

end.

Функ­ция create_circular_numbers/1 соз­да­ет спи­сок всех воз­мож­ных чи­сел, по­лу­чен­ных из ис­ход­но­го чис­ла цик­ли­че­­ским сдви­гом цифр. Для это­го мы пре­об­ра­зу­ем чис­ло в спи­сок всех цифр, со­став­ляю­щих это чис­ло (при по­мо­щи get_digits/1), по­сле че­го соз­да­ем спи­сок всех воз­мож­ных цик­ли­че­­ских пе­ре­ста­но­вок по­лу­чен­но­го спи­ска цифр (при по­мо­щи get_circular_shifts/1), и, на­конец, все эле­мен­ты (спи­ски цифр) спи­ска всех цик­ли­че­­ских пе­ре­ста­но­вок цифр пре­об­ра­зу­ем об­рат­но в чис­ла (при по­мо­щи lists:map/2 и get_number/1).

create_circular_numbers(Number) ->

lists:map(fun(Digits) -> get_number(Digits) end, get_circular_shifts(get_digits(Number))).

Функ­ция get_digits/1 пре­об­ра­зу­ет чис­ло в спи­сок всех его цифр. Для это­го чис­ло пре­об­ра­зу­ет­ся в стро­ку (в спи­сок сим­во­лов, со­став­ляю­щих стро­ко­вое пред­став­ление чис­ла) при по­мо­щи BIF integer_to_list/1, по­сле че­го стро­ка пре­об­ра­зу­ет­ся в спи­сок цифр при по­мо­щи техники кон­ст­руи­ро­вания спи­сков [List Comprehensions].

get_digits(Number) -> [Char-$0 || Char <- integer_to_list(Number)].

Сле­дую­щая функ­ция яв­ля­ет­ся об­рат­ной функ­ци­ей к пре­ды­ду­щей функ­ции, т. е. пре­об­ра­зу­ет спи­сок цифр в чис­ло, со­стоя­щее из этих цифр. Для это­го мы пре­об­ра­зу­ем спи­сок цифр в спи­сок сим­во­лов стро­ко­во­го пред­став­ления со­от­вет­ст­вую­ще­го чис­ла (т. е. в стро­ку), по­сле че­го пре­об­ра­зу­ем по­лу­чен­ную стро­ку в це­лое чис­ло при по­мо­щи BIF list_to_integer/1.

get_number(Digits) -> list_to_integer([Digit+$0 || Digit <- Digits]).

Функ­ция get_circular_shifts/1 яв­ля­ет­ся ин­тер­фейс­ной функ­ци­ей к функ­ции get_circular_shifts/3. Она воз­вра­ща­ет спи­сок, эле­мен­та­ми ко­то­ро­го яв­ля­ют­ся спи­ски, по­лу­чен­ные из ис­ход­но­го спи­ска при по­мо­щи всех воз­мож­ных цик­ли­че­­ских пе­ре­ста­но­вок эле­мен­тов.

get_circular_shifts(Source) -> get_circular_shifts(Source, Source, []).

И, на­конец, по­след­няя функ­ция (get_circular_shifts/3) де­ла­ет всю ра­бо­ту по фор­ми­ро­ванию спи­ска, эле­мен­та­ми ко­то­ро­го яв­ля­ют­ся спи­ски, по­лу­чен­ные из ис­ход­но­го спи­ска при по­мо­щи всех воз­мож­ных цик­ли­че­­ских пе­ре­ста­но­вок эле­мен­тов.

Цик­ли­че­­ская пе­ре­ста­нов­ка эле­мен­тов оз­на­ча­ет, что один или несколь­ко эле­мен­тов из на­ча­ла спи­ска идут в конец спи­ска в том же по­ряд­ке, в ко­то­ром они шли в на­ча­ле спи­ска. Так, на­при­мер, для спи­ска [1, 2, 3, 4] спи­ски [2, 3, 4, 1] и [3, 4, 1, 2] по­лу­ча­ют­ся из ис­ход­но­го спи­ска цик­ли­че­­ской пе­ре­ста­нов­кой од­но­го и двух эле­мен­тов со­от­вет­ст­вен­но. Спи­сок [3, 4, 1, 2] по­лу­ча­ет­ся из спи­ска [2, 3, 4, 1] цик­ли­че­­ской пе­ре­ста­нов­кой од­но­го эле­мен­та. Этот при­мер по­ка­зы­ва­ет нам, что мы мо­жем ре­кур­сив­но (при по­мо­щи хво­сто­вой ре­кур­сии) реа­ли­зо­вать дан­ный ал­го­ритм: мы на­чи­на­ем с ис­ход­но­го спи­ска, на ка­ж­дом ша­ге цик­ли­че­­ской пе­ре­ста­нов­кой од­но­го эле­мен­та по­лу­ча­ем но­вый спи­сок, и об­ра­бот­ку за­кан­чи­ваем, когда мы вернем­ся к ис­ход­но­му спи­ску. По­нят­но, что на ка­ж­дом ша­ге мы за­по­ми­на­ем по­лу­чен­ный спи­сок.

От­ме­тим еще сле­дую­щее: усло­ви­ем окон­чания ра­бо­ты функ­ции яв­ля­ет­ся си­туа­ция, когда но­вый спи­сок, по­лу­чен­ный из те­ку­ще­го цик­ли­че­­ской пе­ре­ста­нов­кой од­но­го эле­мен­та, сов­па­да­ет с ис­ход­ным спи­ском (эту си­туа­цию об­ра­ба­ты­ва­ет со­от­вет­ст­вую­щий ва­ри­ант функ­ции get_circular_shifts/3). Од­на­ко, когда мы на­чи­на­ем ра­бо­ту, у нас те­ку­щий спи­сок то­же сов­па­да­ет с ис­ход­ным спи­ском. Что­бы раз­ре­шить эту си­туа­цию, мы вво­дим еще один ва­ри­ант функ­ции (что важ­но пе­ред ва­ри­ан­том, за­кан­чи­ваю­щим ра­бо­ту). Этот ва­ри­ант об­ра­ба­ты­ва­ет си­туа­цию, когда те­ку­щий спи­сок сов­па­да­ет с ис­ход­ным спи­ском и спи­сок, ко­то­рый хранит все спи­ски, по­лу­чен­ные цик­ли­че­­ской пе­ре­ста­нов­кой, пуст (что ло­гич­но, т. к. мы толь­ко на­ча­ли).

get_circular_shifts(Source, Source, []) ->

[Head | Tail] = Source,

get_circular_shifts(Source, Tail ++ [Head], [Source]);

get_circular_shifts(Source, Source, Dest) -> Dest;

get_circular_shifts(Source, Current, Dest) ->

[Head | Tail] = Current,

get_circular_shifts(Source, Tail ++ [Head], [Current] ++ Dest).

Те­перь про­ве­рим, что все у нас ра­бо­та­ет пра­виль­но. Для это­го за­пуска­ем сре­ду вы­полнения Erlang и ком­пи­ли­ру­ем мо­дуль eratos_sieve (по­лу­чен­ный в пре­ды­ду­щем при­ме­ре) и мо­дуль problem_035 (для ком­пи­ля­ции вы­пол­ня­ем ко­ман­ду c(module_name). в кон­со­ли сре­ды вы­полнения Erlang, где module_name – имя со­от­вет­ст­вую­ще­го мо­ду­ля). Для ра­бо­ты необ­хо­ди­мо, что­бы оба от­ком­пи­ли­ро­ван­ных мо­ду­ля рас­по­ла­га­лись в од­ной ди­рек­то­рии (по сути, это ог­раничение не яв­ля­ет­ся обя­за­тель­ным, и его мож­но обой­ти; как это сде­лать, мы по­го­во­рим на од­ном из бу­ду­щих уро­ков). Зна­я, что ко­ли­че­­ст­во цик­ли­че­­ских про­стых чи­сел, мень­ших 100, рав­но 13, вво­дим в кон­со­ли сре­ды вы­полнения Erlang ко­ман­ду problem_035:solve(99). и по­лу­ча­ем желаемый ре­зуль­тат – 13. Те­перь ре­шим на­шу ис­ход­ную за­да­чу: оп­ре­де­лить ко­ли­че­­ст­во цик­ли­че­­ских про­стых чи­сел, мень­ших 1 000 000. Для это­го введем в кон­со­ли сре­ды вы­полнения Erlang ко­ман­ду problem_035:solve(999999). – ре­зуль­тат будет 55.

Ка­ж­дый мо­жет зай­ти на сайт Project Euler в за­да­чу но­мер 35 (http://projecteuler.net/problem=35), вве­сти дан­ный от­вет и убе­дить­ся, что он пра­виль­ный (прав­да, для это­го ему при­дет­ся за­ре­ги­ст­ри­ро­вать­ся).

Се­го­дня мы на прак­ти­че­­ских за­да­чах по­ра­бо­та­ли с раз­ны­ми ти­па­ми кол­лек­ций. Не сле­ду­ет за­бы­вать, что к вы­бо­ру ти­па кол­лек­ций при реа­ли­за­ции то­го или ино­го ал­го­рит­ма сле­ду­ет под­хо­дить вдум­чи­во: этот вы­бор влия­ет на реа­ли­за­цию ал­го­рит­ма. Пред­ставь­те, на­при­мер, что ес­ли в ал­го­рит­ме «Ре­ше­та Эра­тосфе­на» мы вме­сто мас­си­вов ре­ши­ли бы ис­поль­зо­вать сло­ва­ри; как из­менилась бы реа­ли­за­ция это­го ал­го­рит­ма? (Чи­та­тель мо­жет для ин­те­ре­са по­про­бо­вать пе­ре­пи­сать реа­ли­за­цию ал­го­рит­ма с ис­поль­зо­ванием лю­бой дру­гой кол­лек­ции и сравнить по­лу­чен­ный ре­зуль­тат с ис­ход­ной реа­ли­за­ци­ей.) Наш прак­ти­кум на этом не за­кан­чи­ва­ет­ся: в сле­дую­щем но­ме­ре мы зай­мем­ся «чер­ной ма­ги­ей» би­то­вых строк.

По­лез­ные за­мет­ки

Спи­ски

Спи­ски – фун­да­мен­таль­ный тип дан­ных, встро­ен­ный в язык. Спи­сок – это упо­ря­до­чен­ная кол­лек­ция, хра­ня­щая на­бор эле­мен­тов в по­ряд­ке их рас­по­ло­жения в спи­ске (в по­ряд­ке их по­зи­ции в спи­ске); это наиболее бо­га­тый по воз­мож­но­стям тип кол­лек­ций в язы­ке Erlang. Для об­ра­бот­ки спи­сков доступ­ны следующие воз­мож­но­сти:

  • Опе­ра­ция со­от­вет­ст­вия шаб­ло­ну [Pattern Matching]. С ее по­мо­щью мож­но вы­де­лить пер­вые N эле­мен­тов с на­ча­ла спи­ска и его оста­ток. Име­ет сле­дую­щий син­так­сис: [Head1, Head2, …, HeadN , Rest], где Head1, Head2, …, HeadN – эле­мен­ты с на­ча­ла спи­ска, Rest – спи­сок, со­дер­жа­щий оста­ток (ис­ход­ный спи­сок ми­нус N эле­мен­тов с на­ча­ла ис­ход­но­го спи­ска). По­зво­ля­ет об­ра­ба­ты­вать спи­ски ре­кур­сив­но.
  • Опе­ра­ция кон­ст­руи­ро­вания спи­сков [List Comprehensions]. Дан­ная опе­ра­ция по­зво­ля­ет генери­ро­вать спи­сок из де­кар­то­ва про­из­ве­дения несколь­ких мно­жеств ис­точников, с при­менением к это­му про­из­ве­дению фильт­ров. Име­ет сле­дую­щий син­так­сис: [Expr, Qualifier1, …, QualifierN], где Expr – про­из­воль­ное вы­ра­жение для фор­ми­ро­вания эле­мен­тов конеч­но­го спи­ска, Qualifier1, …, QualifierN – ли­бо генера­тор (как спи­сков, так и би­то­вых строк), ли­бо фильтр.
  • На­бор функ­ций для ра­бо­ты со спи­ска­ми, оп­ре­де­лен­ный в мо­ду­ле lists. Он по­зво­ля­ет ре­шать прак­ти­че­­ски лю­бые за­дачи, ко­то­рые мо­гут встре­тить­ся при ра­бо­те со спи­ска­ми. Сле­ду­ет за­ме­тить, что дан­ный на­бор функ­ций не по­зво­ля­ет за­дать но­вый объ­ект для оп­ре­де­лен­ной по­зи­ции (по оп­ре­де­лен­но­му ин­дек­су).
  • Опе­ра­то­ры “++” и “--” для соз­дания сум­мы и раз­но­сти двух спи­сков.

Мас­си­вы

  • Мас­сив – это кол­лек­ция уров­ня биб­лио­те­ки язы­ка Erlang, свя­зы­ваю­щая хранимые эле­мен­ты с их по­зи­ци­ей (ин­дек­сом) в мас­си­ве. Мас­си­вы, в от­ли­чие от спи­сков, по­зво­ля­ют из­ме­нять зна­чение эле­мен­та по оп­ре­де­лен­но­му ин­дек­су. Функ­ции для ра­бо­ты с мас­си­ва­ми оп­ре­де­ле­ны в мо­ду­ле array (и это един­ст­вен­ный спо­соб ра­бо­тать с ними). При ра­бо­те с функ­ция­ми из это­го мо­ду­ля сле­ду­ет помнить, что ну­ме­ра­ция эле­мен­тов массивов на­чи­на­ет­ся с 0 (в от­ли­чие от эле­мен­тов спи­сков).

Мно­же­ст­ва

  • Мно­же­ст­во – это кол­лек­ция уров­ня биб­лио­те­ки язы­ка Erlang, обес­пе­чи­ваю­щая уникаль­ность хранимых эле­мен­тов (это оз­на­ча­ет, что во мно­же­ст­ве не мо­гут хранить­ся дуб­ли­ка­ты лю­бо­го объ­ек­та).

В биб­лио­те­ке язы­ка Erlang су­ще­ст­ву­ет три реа­ли­за­ции мно­жеств: стан­дарт­ная реа­ли­за­ция (для ко­то­рой пред­став­ление дан­ных не оп­ре­де­ле­но, но в дан­ной вер­сии ис­поль­зу­ет­ся хэш-таб­ли­ца), реа­ли­за­ция на осно­ве упо­ря­до­чен­но­го спи­ска и реа­ли­за­ция на осно­ве сба­лан­си­ро­ван­но­го де­ре­ва. Разница ме­ж­ду стан­дарт­ной реа­ли­за­ци­ей и дву­мя дру­ги­ми в том, что в стан­дарт­ной реа­ли­за­ции по­ря­док хранения эле­мен­тов не за­дан, тогда как в двух дру­гих реа­ли­за­ци­ях ис­поль­зу­ет­ся ес­те­ст­вен­ный по­ря­док хранения эле­мен­тов.

Функ­ции для ра­бо­ты со стан­дарт­ной реа­ли­за­ци­ей мно­жеств оп­ре­де­ле­ны в мо­ду­ле sets, функ­ции для ра­бо­ты с реа­ли­за­ци­ей на осно­ве упо­ря­до­чен­но­го спи­ска – в мо­ду­ле ordsets, функ­ции для ра­бо­ты с реа­ли­за­ци­ей на осно­ве сба­лан­си­ро­ван­но­го дво­ич­но­го де­ре­ва – в мо­ду­ле gb_sets.

Сло­ва­ри

  • Сло­варь – это ас­со­циа­тив­ная кол­лек­ция, хра­ня­щая па­ры ключ–зна­чение. В язы­ке Erlang сло­ва­ри оп­ре­де­ля­ют­ся на уровне биб­лио­те­ки. Су­ще­ст­ву­ют две реа­ли­за­ции сло­ва­рей: стан­дарт­ная реа­ли­за­ция (для ко­то­рой пред­став­ление дан­ных не оп­ре­де­ле­но, но в дан­ной вер­сии ис­поль­зу­ет­ся хэш-таб­ли­ца) и реа­ли­за­ция на осно­ве упо­ря­до­чен­но­го спи­ска.

Разница ме­ж­ду стан­дарт­ной реа­ли­за­ци­ей и реа­ли­за­ци­ей на осно­ве упо­ря­до­чен­но­го спи­ска в том, что в первой по­ря­док хранения эле­мен­тов не за­дан, тогда как во второй эле­мен­ты расположе­ны в со­от­вет­ст­вии с ес­те­ст­вен­ным по­ряд­ком хранения клю­чей.

Функ­ции для ра­бо­ты со стан­дарт­ной реа­ли­за­ци­ей сло­ва­рей оп­ре­де­ле­ны в мо­ду­ле dict, функ­ции для ра­бо­ты с реа­ли­за­ци­ей сло­ва­рей на осно­ве упо­ря­до­чен­но­го спи­ска – в мо­ду­ле orddict. Реа­ли­за­ции сло­ва­ря на осно­ве сба­лан­си­ро­ван­но­го дво­ич­но­го де­ре­ва в биб­лио­те­ке язы­ка Erlang нет (в от­ли­чие от со­от­вет­ст­вую­щей реа­ли­за­ции мно­же­ст­ва), но за­то при­сут­ст­ву­ет про­сто мо­дуль для ра­бо­ты со сба­лан­си­ро­ван­ным дво­ич­ным де­ре­вом gb_trees. Эту функ­цио­наль­ность в неко­то­рой сте­пени мож­но счи­тать реа­ли­за­ци­ей сло­ва­ря на осно­ве сба­лан­си­ро­ван­но­го дво­ич­но­го де­ре­ва. И, что вполне оче­вид­но, дан­ные в та­ком де­ре­ве хра­нят­ся в со­от­вет­ст­вии с ес­те­ст­вен­ным по­ряд­ком клю­чей.

Персональные инструменты
купить
подписаться
Яндекс.Метрика