Erlang에서리스트를 오른쪽으로 회전

Question

이제 Sequential Erlang (그리고 함수형 프로그래밍)에 익숙해졌습니다. 그래서 BIF의 도움없이 다음 두 가지 기능을 구현하고 싶습니다. (내가 여기 해달라고 부탁하는)

-export(leftrotate/1, rightrotate/1). 
%%(1) left rotate a lits 
leftrotate(List, 0) -> 
    List; 
leftrotate([Head | Tail], Times) -> 
    List = append(Tail, Head), 
    leftrotate(List, Times -1). 

append([], Elem)-> 
    [Elem]; 
append([H|T], Elem) -> 
    [H | append(T, Elem)]. 

%%right rotate a list, how? 
%% 

나는이 연습에서 BIF을 사용하지 않으 하나는 left_rotate이다 (필자는 솔루션과 함께 올라와있다있는) 다른 하나는 right_rotate입니다. 올바른 순환 게재는 어떻게해야합니까?

관련 질문과 약간 더 중요한 질문. 내 구현 중 하나가 효율적인지 알 수 있습니까? 예 : BIF의 도움을 받아 구현하면 불필요한 재귀를 피할 수 있습니다.

BIF는 일부 기능을 향상시키기 위해 만들어 졌다고 생각합니다. 능률적 인 프로그래밍이 좋지 않은 효율성 (또는 우리가 '기능적 방식'으로 수행하는 경우 성능이 최적이 아님) 당신은 기능적인 관점에서 생각하려는 경우

Answer 1

는 아마도 바로 왼쪽 회전의 관점에서 회전 구현하는 것이 좋습니다 :

rightrotate(List, 0) -> 
    List; 
rightrotate(List, Times) -> 
    lists:reverse(leftrotate(lists:reverse(List), Times)). 

이 최고의 아이디어 나 아무것도 :)

Answer 2

우선이다라고하지

 
-module(foo). 

-export([left/2, right/2]). 

left(List, Times) -> 
    left(List, Times, []). 

left([], Times, Acc) when Times > 0 -> 
    left(reverse(Acc), Times, []); 
left(List, 0, Acc) -> 
    List ++ reverse(Acc); 
left([H|T], Times, Acc) -> 
    left(T, Times-1, [H|Acc]). 

right(List, Times) -> 
    reverse(foo:left(reverse(List), Times)). 

reverse(List) -> 
    reverse(List, []). 

reverse([], Acc) -> 
    Acc; 
reverse([H|T], Acc) -> 
    reverse(T, [H|Acc]). 

: 구현은

둘째, 나는 당신에게 뭔가를 제안 (... 빈리스트에 그것을 시도) 약간의 버그가 같은

셋째, 당신의 기능을 벤치마킹, 당신이 할 수있는 일이 : 나는 비판적으로 코드를 테스트, 그래서 그것을 보이지 않았다

 
test(Params) -> 
    {Time1, _} = timer:tc(?MODULE, function1, Params), 
    {Time2, _} = timer:tc(?MODULE, function2, Params), 
    {{solution1, Time1}, {solution2, Time2}}. 

, 그냥 아이디어를 얻을. 또한 "역순"기능을 직접 구현할 수도 있습니다. 그것은 꼬리 재귀를 사용하여 사소한 것입니다. 시도하지 않으시겠습니까?

Answer 3

왼쪽 :

lrl([], _N) -> 
    []; 

lrl(List, N) -> 
    lrl2(List, List, [], 0, N). 

% no more rotation needed, return head + rotated list reversed 
lrl2(_List, Head, Tail, _Len, 0) -> 
    Head ++ lists:reverse(Tail); 

% list is apparenly shorter than N, start again with N rem Len 
lrl2(List, [], _Tail, Len, N) -> 
    lrl2(List, List, [], 0, N rem Len); 

% rotate one 
lrl2(List, [H|Head], Tail, Len, N) -> 
    lrl2(List, Head, [H|Tail], Len+1, N-1). 

오른쪽 :

목록 당신이 회전로, 항목 순서를 변경해야하는 경우 사용할 올바른 표현되지 않기 때문에 귀하의 구현이 효율적으로되지 않습니다

lrr([], _N) -> 
    []; 

lrr(List, N) -> 
    L = erlang:length(List), 
    R = N rem L,      % check if rotation is more than length 
    {H, T} = lists:split(L - R, List), % cut off the tail of the list 
    T ++ H.        % swap tail and head 

Answer 4

. (수천 개의 작업이 포함 된 라운드 로빈 스케줄러를 상상해보십시오. 앞자리를 차지하고 끝나면 끝까지 배치하십시오.)

그래서 우리는 실제로이 작업을 수행하는 데 최소한의 오버 헤드로 어떤 방법이 될지 물어보고 있습니다. 어쨌든 목록에. 그렇다면 우리가 제거하고자하는 오버 헤드로서 무엇이 자격이됩니까? 하나는 더 많은 객체를 consing (할당)하거나 다른 방법으로 계산함으로써 약간의 계산을 절약 할 수 있습니다. 또한 계산 과정에서 필요 이상으로 큰 라이브 설정을 종종 할당 할 수 있습니다.

---

first_last([First|Tail]) -> 
    put_last(First, Tail). 

put_last(Item, []) -> 
    [Item]; 
put_last(Item, [H|Tl]) -> 
    [H|put_last(Item,Tl)]. 

빈 목록과 같은 코너 케이스를 무시; 위의 코드는 최종 결과 목록을 직접 무시합니다. 할당 된 쓰레기는 거의 없습니다. 최종 목록은 스택이 풀릴 때 작성됩니다. 비용은이 작업 중에 전체 입력 목록 및 구성 목록에 더 많은 메모리가 필요하지만 짧은 일시적인 문제입니다.Java와 Lisp의 피해로 인해 과도한 절약 문제를 해결할 수 있지만 Erlang에서는 실시간 속성에 대한 모든 꿈을 죽이는 글로벌 GC가 위험하지 않습니다. 어쨌든, 나는 일반적으로 위의 접근 방식을 좋아한다./1은 (는 BIF 목록 호출 역 :

---

last_first(List) -> 
    last_first(List, []). 

last_first([Last], Rev) -> 
    [Last|lists:reverse(Rev)]; 
last_first([H|Tl], Rev) -> 
    last_first(Tl, [H|Rev]). 

이 방법은 우리가 목록에 통과 한 후 폐기 목사라는 임시 목록을 사용하여, 역/2,하지만 아무것도하지 않는 재미있다). 이 임시 목록을 생성함으로써 목록을 두 번 탐색하지 않아도됩니다. 마지막 항목을 제외하고 모든 것을 포함하는 목록을 작성하고 마지막 항목을 가져 오는 데 한 번 더 시간을줍니다.

Answer 5

효율성 문제는 과도한 재귀 (함수 호출이 저렴함)와는 관계가 없으며 목록을 보거나 다시 작성하는 것과 관련이 있습니다. 목록의 끝 부분에 무언가를 추가 할 때마다 추가 목록을 구현할 때 명백한 것처럼 전체 목록을 걸어서 복사해야합니다. 따라서 N 개의 단계를 거치면 전체 목록을 N 번 복사해야합니다. 목록을 사용할 수 있습니다 : 하나의 단계에서 전체 회전을 수행하는 split (다른 답변 중 하나에서 볼 수 있듯이)을 사용할 수 있지만 회전해야하는 단계의 수를 미리 알지 못하면 어떻게됩니까?

목록은 실제로이 작업을위한 이상적인 데이터 구조가 아닙니다. 대신 머리에 하나, 꼬리에 하나씩 두 개의 목록을 사용하면 한 목록에서 다른 목록으로 요소를 이동하여 쉽게 회전 할 수 있습니다.

그래서 조심스럽게 표준 라이브러리에서 아무것도를 호출 피하고, 우리는이 :

rotate_right(List, N) -> 
    to_list(n_times(N, fun rotate_right/1, from_list(List))). 

rotate_left(List, N) -> 
    to_list(n_times(N, fun rotate_left/1, from_list(List))). 

from_list(Lst) -> 
    {Lst, []}. 

to_list({Left, Right}) -> 
    Left ++ reverse(Right). 

n_times(0, _, X) -> X; 
n_times(N, F, X) -> n_times(N - 1, F, F(X)). 

rotate_right({[], []}) -> 
    {[], []}; 
rotate_right({[H|T], Right}) -> 
    {T, [H|Right]}; 
rotate_right({[], Right}) -> 
    rotate_right({reverse(Right), []}). 

rotate_left({[], []}) -> 
    {[], []}; 
rotate_left({Left, [H|T]}) -> 
    {[H|Left], T}; 
rotate_left({Left, []}) -> 
    rotate_left({[], reverse(Left)}). 

reverse(Lst) -> 
    reverse(Lst, []). 
reverse([], Acc) -> 
    Acc; 
reverse([H|T], Acc) -> 
    reverse(T, [H|Acc]). 

모듈 큐는이 같은 데이터 구조 무언가를 제공합니다. 나는 이것을 참고하지 않고 이것을 썼다. 그래서 그것들은 아마 더 똑똑 할 것이다.

Answer 6

코드에 대한 빠른 의견. 내가 추가로 호출하는 함수의 이름을 변경합니다. 기능적 상황에서 추가는 일반적으로 하나의 요소가 아닌 목록의 끝에 새 목록을 추가하는 것을 의미합니다. 혼란을 가중시키지 마십시오.

앞서 언급 한 바와 같이 : split은 BIF가 아니며 erlang으로 작성된 라이브러리 함수입니다. BIF가 실제로 무엇인지는 제대로 정의되지 않았습니다.

분할 또는 분할과 같은 솔루션은 상당히 멋지게 보입니다. 누군가가 이미 목록을 지적했듯이이 유형의 작업을위한 최상의 데이터 구조는 아닙니다. 물론 당신이 그것을 사용하고있는 것에 달려 있습니다.