Вопрос по list-comprehension, list, erlang – Erlang: первый элемент в списке, соответствующий некоторому условию (без оценки остальных элементов)

5

В качестве простого примера, предположим, у меня есть список номеровL и я хочу найти первый элемент, который больше определенного числаX, Я мог бы сделать это со списком пониманий, как это:

([email protected])24> L = [1, 2, 3, 4, 5, 6].              
[1,2,3,4,5,6]
([email protected])25> X = 2.5.
2.5
([email protected])26> [First | _] = [E || E  X].  
[3,4,5,6]
([email protected])27> First.
3

Но это кажется потенциально очень неэффективным, поскольку список может быть очень длинным, и первый матч может быть на ранней стадии. Так что я'Интересно, а) Есть ли эффективный способ сделать это, чтобы победить?t оценить остальные элементы в списке после того, как найдено первое совпадение? или б) Когда это компилируется, оптимизирует ли Erlang остальные сравнения?

Вот как я бы достиг того, что яищу в С:

int first_match(int* list, int length_of_list, float x){
    unsigned int i;
    for(i = 0; i < length_of_list, i++){
        if(x > list[i]){ return list[i]; } /* immediate return */
    }
    return 0.0; /* default value */
}

Ваш Ответ

3   ответа
3

Вот'с чем я был в состоянии придумать. Я'еще хотел бы знать, если естьs лучший ответ и / или если самая простая вещь оптимизируется (чем больше я думаю об этом, тем больше я сомневаюсь в этом).

-module(lazy_first).

-export([first/3]).

first(L, Condition, Default) ->
  first(L, [], Condition, Default).

first([E | Rest], Acc, Condition, Default) ->
  case Condition(E) of
    true -> E;
    false -> first(Rest, [E | Acc], Condition, Default)
  end;

first([], _Acc, _Cond, Default) -> Default.

Пример:

14> lazy_first:first([1, 2, 3, 4, 5], fun(E) -> E > 2.5 end, 0.0).
3
15> lazy_first:first([1, 2, 3, 4, 5], fun(E) -> E > 5.5 end, 0.0).
0.0

редактировать

Вот'Версия без аккумулятора.

first([E | Rest], Condition, Default) ->
  case Condition(E) of
    true -> E;
    false -> first(Rest, Condition, Default)
  end;

first([], _Cond, Default) -> Default.
Действительно хороший момент :) Это на самом деле немного упрощает. dantswain
Можно'не решить вопрос о том, есть лиЭто встроенный ярлык, но это, безусловно, похоже на правильный способ бросить свой собственный ... кроме вашего аккумулятора кажется ненужным. macintux
12

ну как то

firstmatch(YourList, Number) -> 
   case lists:dropwhile(fun(X) -> X =< Number end, YourList) of
     [] -> no_solution;
     [X | _] -> X
   end.
Ницца. Это более лаконично, чем мое решение. Я должен был сделать небольшой взгляд, чтобы убедиться, чтоdropwhile фактически останавливает оценку после первого неудачного матча. Я обернул его в функцию, которая позволяет вам указать условие как функцию (без необходимости инвертировать логику):gist.github.com/3807110 dantswain
3

Вот'быстрое решение:

first_greater([],_) -> undefined;
first_greater([H|_], Num) when H > Num -> H;
first_greater([_|T], Num) -> first_greater(T,Num).

Похожие вопросы