[ruby] 배열에서 중복 값을 찾아 반환하는 방법

arr 문자열 배열입니다.

["hello", "world", "stack", "overflow", "hello", "again"]

arr중복 이 있는지 확인하는 쉽고 편리한 방법은 무엇입니까? 그렇다면 어떤 것이 든 상관없이 그 중 하나를 반환합니까?

예 :

["A", "B", "C", "B", "A"]    # => "A" or "B"
["A", "B", "C"]              # => nil

답변

a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

나는 이것이 우아한 대답이 아니라는 것을 알고 있지만 그것을 좋아합니다. 아름다운 하나의 라이너 코드입니다. 거대한 데이터 세트를 처리하지 않으면 완벽하게 작동합니다.

더 빠른 솔루션을 찾고 계십니까? 여기 있습니다!

def find_one_using_hash_map(array)
  map = {}
  dup = nil
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1

    if map[v] > 1
      dup = v
      break
    end
  end

  return dup
end

선형, O (n)이지만 이제 여러 코드 줄을 관리하고 테스트 사례가 필요합니다.

더 빠른 솔루션이 필요하면 대신 C를 사용해보십시오.

그리고 여기에 요점이 다른 솔루션을 비교된다 https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

답변

첫 번째 옵션이 가장 빠른 몇 가지 방법으로이 작업을 수행 할 수 있습니다.

ary = ["A", "B", "C", "B", "A"]

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)

ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

그리고 O (N ^ 2) 옵션 (즉, 덜 효율적) :

ary.select{ |e| ary.count(e) > 1 }.uniq

답변

객체의 색인 (왼쪽에서 계산)이 객체의 색인 (오른쪽에서 계산)과 같지 않은 첫 번째 인스턴스를 찾으십시오.

arr.detect {|e| arr.rindex(e) != arr.index(e) }

중복이 없으면 반환 값은 nil입니다.

나는 이것이이 추가 개체의 생성에 의존하지 않기 때문에, 지금까지,뿐만 아니라 스레드에 게시 가장 빠른 해결책이라고 생각하고, #index그리고 #rindex큰-O 런타임 따라서보다 느린 N ^ 2이고, C로 구현 세르지오의, 그러나 “느린”부품이 C에서 작동한다는 사실로 인해 벽 시간이 훨씬 빨라질 수 있습니다.

답변

detect하나의 사본 만 찾습니다. find_all그들 모두를 찾을 것입니다 :

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }

답변

중복을 찾는 두 가지 방법이 더 있습니다.

세트 사용

require 'set'

def find_a_dup_using_set(arr)
  s = Set.new
  arr.find { |e| !s.add?(e) }
end

find_a_dup_using_set arr
  #=> "hello"

모든 중복 배열을 반환하는 select대신 사용하십시오 find.

사용하다 Array#difference

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

def find_a_dup_using_difference(arr)
  arr.difference(arr.uniq).first
end

find_a_dup_using_difference arr
  #=> "hello"

.first모든 복제본의 배열을 반환하려면 삭제하십시오 .

nil중복이 없으면 두 가지 방법이 모두 반환 됩니다.

루비 코어에 추가 할 것을 제안했습니다Array#difference . 자세한 내용은 여기 내 대답에 있습니다 .

기준

제안 된 방법을 비교해 봅시다. 먼저 테스트 할 배열이 필요합니다.

CAPS = ('AAA'..'ZZZ').to_a.first(10_000)
def test_array(nelements, ndups)
  arr = CAPS[0, nelements-ndups]
  arr = arr.concat(arr[0,ndups]).shuffle
end

다른 테스트 배열에 대한 벤치 마크를 실행하는 방법 :

require 'fruity'

def benchmark(nelements, ndups)
  arr = test_array nelements, ndups
  puts "\n#{ndups} duplicates\n"
  compare(
    Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
    Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
                     [nil]).first },
    Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
                     [nil]).first},
    Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
    Cary_set:  -> {find_a_dup_using_set(arr)},
    Cary_diff: -> {find_a_dup_using_difference(arr)}
  )
end

하나의 사본 만 반환되므로 @JjP의 답변을 포함하지 않았으며 답변을 수정하면 @Naveed의 이전 답변과 동일합니다. @Naveed의 답변 이전에 게시 된 동안 단 하나가 아닌 모든 복제본을 반환 한 @Marin의 답변도 포함하지 않았습니다 (사소한 점이지만 두 번만 반환하면 동일하므로 두 가지를 평가하는 포인트는 없습니다).

또한 모든 중복을 반환하는 첫 번째 답변 만 반환하도록 다른 답변을 수정했지만 하나를 선택하기 전에 모든 중복을 계산했기 때문에 본질적으로 성능에 영향을 미치지 않아야합니다.

각 벤치 마크에 대한 결과는 가장 빠름에서 가장 느리게 나열됩니다.

먼저 배열에 100 개의 요소가 있다고 가정합니다.

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

이제 10,000 개의 요소가있는 배열을 고려하십시오.

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1

benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0

benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

참고 find_a_dup_using_difference(arr)경우 훨씬 더 효율적이 될 것입니다 Array#difference그것이 루비 코어에 추가 된 경우 케이스가 될 것이다, C로 구현되었다.

결론

많은 답변이 합리적이지만 Set을 사용하는 것이 가장 좋습니다 . 중간 정도의 하드 케이스에서는 가장 빠르며, 가장 어려운 경우에는 가장 빠르며 계산 상 사소한 경우에만 빠릅니다.

Chris의 솔루션을 선택할 수있는 매우 특별한 경우는 수천 개의 작은 배열을 별도로 중복 제거하고 일반적으로 10 개 미만의 항목을 복제하려는 경우이 방법을 사용하려는 경우입니다. 세트 생성에 따른 작은 추가 오버 헤드를 피할 수 있습니다.

답변

아아 대부분의 대답은 O(n^2)입니다.

O(n)해결책 은 다음과 같습니다 .

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

이것의 복잡성은 무엇입니까?

O(n)첫 시합에 뛰어 들다
O(n)메모리를 사용 하지만 최소한의 양만 사용합니다

이제 배열에 얼마나 자주 중복 되는가에 따라 이러한 런타임이 실제로 더 나아질 수 있습니다. 예를 들어, 크기 배열이 다른 요소 O(n)의 모집단에서 샘플링 된 k << n경우 런타임과 공간 모두에 대한 복잡성 만 발생 O(k)하지만 원래 포스터가 입력을 검증하고 중복이 없는지 확인하려고합니다. 이 경우 O(n)대부분의 입력에 대해 요소가 반복되지 않기 때문에 런타임과 메모리 복잡성이 모두 발생합니다 .

답변

Ruby Array 객체에는 훌륭한 방법이 select있습니다.

select {|item| block } → new_ary
select → an_enumerator

첫 번째 형태는 여기서 당신이 관심을 갖는 것입니다. 테스트를 통과 한 객체를 선택할 수 있습니다.

루비 배열 객체에는 또 다른 방법이 count있습니다.

count → int
count(obj) → int
count { |item| block } → int

이 경우 중복 (배열에 두 번 이상 나타나는 객체)에 관심이 있습니다. 적절한 시험은 a.count(obj) > 1입니다.

만약 a = ["A", "B", "C", "B", "A"]다음,

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

하나의 객체 만 원한다고 진술 합니다. 하나를 선택하십시오.