1. Куча / Говнокод #18822

    +2

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    8. 8
    9. 9
    %%% O(n log n)
nub([]) -> [];
nub([H|T]) ->                    
    case lists:member(H, T) of
        true ->
            nub(T);
        false ->
            [H|nub(T)]
    end.

    кто-то услышал про логлинейный nub, и решил, что у него тоже получится

    Запостил: CHayT, 06 Октября 2015

    Комментарии (16) RSS

    • ava bormand 06.10.2015 18:47 # +2

      Но получилось O(n^2)?
      Ответить

    • ava roman-kashitsyn 06.10.2015 19:49 # +4

      нубы, сэр
      Ответить

      • ava CHayT 06.10.2015 22:43 # 0

        что интересно, lists:member в эрланге реализован как BIF
        но внутри там никакой магии, обычный линейный алгоритм
        Ответить

        • ava roman-kashitsyn 06.10.2015 23:59 # 0

          Ну, видимо, для пирфоманса. Если средняя программа станет чуть быстрее, почему бы и нет.
          Ответить

    • ava roman-kashitsyn 06.10.2015 19:56 # 0

      > логлинейный nub
      А есть пример реализации?
      Какие ограничения на элементы списка? Они должны быть Ord или достаточно Eq?
      Ответить

      • ava CHayT 06.10.2015 22:39 # 0

        необходимо и достаточно Ord
        реализация: map head . group . sort
        Ответить

        • ava roman-kashitsyn 06.10.2015 23:55 # 0

          Ну, это-то понятно. В целях уменьшения числа аллокаций можно и самому merge sort написать, с set union вместо обычного мёржа.
          Я просто думал, что есть какой-нибудь более изящний divide-and-conquer алгоритм, который ещё и относительный порядок сохраняет.
          Ответить

    • ava wvxvw 07.10.2015 18:11 # +1 

      :- use_module(library(heaps)).

no_duplicates_helper(Heap, _, []) :- empty_heap(Heap).
no_duplicates_helper(Heap, X, Refined) :-
    get_from_heap(Heap, X, _, Newheap),
    no_duplicates_helper(Newheap, X, Refined).
no_duplicates_helper(Heap, X, [Y | Refined]) :-
    get_from_heap(Heap, Y, _, Newheap),
    dif(X, Y),
    no_duplicates_helper(Newheap, Y, Refined).

no_duplicates(List, Refined) :-
    findall(E-E, member(E, List), Pairs),
    list_to_heap(Pairs, Heap),
    no_duplicates_helper(Heap, [], Refined).

%% ?- no_duplicates([2, 3, 1, 4, 3, 4, 1, 4, 3, 1, 4, 3, 1], X).
%% X = [1, 2, 3, 4]

      Практически наверняка в Эрланге найдется куча.
      Ответить

      • ava roman-kashitsyn 07.10.2015 19:00 # 0

        Это очень длинный sort unique пирамидальной сортировкой.
        Ответить

        • ava wvxvw 07.10.2015 19:21 # 0

          Ну так это же ОП-у и требовалось. А так если искать самый короткийс способ, то в том же Прологе:
          sort(0, @<, In, Out)

          но тут же суть нужно было передать.
          Ответить

    • ava CHayT 24.11.2015 00:11 # 0

      кстати, в дохлом страусе уже официально появились концепты?
      этот говнокод меня натолкнул на мысль, что было бы круто специализировать имплементацию в зависимости от констрейнтов типов (к примеру, если есть Ord ебашим логлинейный nub, если только Eq -- квадратичный)
      на крестовых концептах и хаскельных closed type families прям руки чешутся оптимизированную библиотеку алгоритмов запилить, которая бы сама за меня все алгебраические свойства операций учитывала
      Ответить

    • ava guest 22.01.2016 02:35 # +1

      сори, что новичком назвал. 2011
      Ответить

      • ava guest 22.01.2016 02:37 # 0

        это из-за аватарки. борманд хоть и меняет анимешные авы все время, но его перепутать сложно
        Ответить

    Добавить комментарий