두리스트가 동일한 지 비교하는 관용적 인 방법은 무엇입니까? (. 얕은하지 체크, 내가 <code>Kernel.==/2</code>에 의존 할 수 요소)

Question

나는 그들의 요소가 동일한 지 여부를 확인해야 두 개의 목록이 현재

, 내가 가진 :

[l1 -- l2] ++ [l2 -- l1] == [] 

그것은 조금 overcomplicated 보인다 나에게는 꽤 관용적이지 않다. 내가 놓친 게 있니? 평등을 위해 두 목록을 비교하는 더 좋은 방법이 있습니까? 이것은 당신의 Kernel.--/2 기반 솔루션을 O(n^2) 대신 O(n log n) 시간에 실행됩니다

Enum.sort(l1) == Enum.sort(l2) 

: 내가 생각할 수있는

Answer 1

가장 짧은 방법은 목록을 분류하고 비교하는 것입니다.

목록에 중복을 포함 할 수 있고 그 개수를 추적해야하므로 일반 데이터 구조를 사용할 수 없습니다. 우리는 그들을 비교하는 각 요소의 주파수를 계산지도를 사용할 수 있습니다 :

iex(1)> l1 = ~w|a a b|a 
[:a, :a, :b] 
iex(2)> l2 = ~w|a b|a 
[:a, :b] 
iex(3)> m1 = l1 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end) 
%{a: 2, b: 1} 
iex(4)> m2 = l2 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end) 
%{a: 1, b: 1} 
iex(5)> m1 == m2 
false 
iex(6)> l2 = ~w|a b a|a 
[:a, :b, :a] 
iex(7)> m2 = l2 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end) 
%{a: 2, b: 1} 
iex(8)> m1 == m2 
true 

이 또한 O(n log n)은 그래서 당신은 벤치 마크 데이터의 종류와 두 솔루션을 할 수 있습니다 당신이보고해야하는 더 잘 수행합니다.

Answer 2

도그 버트의 해결책은 적절하지만, 아직 오크 쉬에 있습니다.

얼랑에서이 될 것이다 :

이

lists:sort(List1) == lists:sort(List2) 

깊은 비교가 매우 거의 동일한 보이지만, 각 목록 내에서 구조를 통과해야한다 물론.

고려해야 할 한 가지 요인은 목록의 순서는 매우 자주 은이고 의미는입니다. 문자열이 좋은 예입니다. 플레이어 순위, 시작 위치, 게임 단축키 위치 및 마지막으로 사용 된 가장 긴 캐시 목록이 그 예입니다. 따라서 은입니다. 비교의 의미는 다음과 같습니다. "에 동일한 번호와 유형의이 포함되어 있습니까?" "두 목록이 의미 상으로 동일합니까? 은입니까?"

비교 고려 아나그램 :

철자 바꾸기 비교 잘 작동하지만 전혀 의미 론적 하나

lists:sort("AT ERR GET VICE") == lists:sort("IT ERR ETC GAVE") 

.