배열에서 중복 값을 찾아 반환하는 방법
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) }
중복 항목이 없으면 반환 값은 0이 됩니다.
하지 않기 지금까지 중 합니다.#index그리고.#rindexC에서 구현됩니다.은 N, C.big-O이 N^2므 N^2로 C.big-O 타보 "Sergio 느린 " 에만 " 부때 "로 실행되기 수 .
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모든 중복 항목의 배열을 반환합니다.
모두 두메드모두반니다됩환서다니▁return를 합니다.nil중복이 없는 경우
저는 루비 코어에 추가할 것을 제안했습니다.더 많은 정보는 여기 제 답변에 있습니다.
벤치마크
제안된 방법을 비교해 보겠습니다.먼저 테스트할 어레이가 필요합니다.
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의 답변도 포함하지 않았습니다. @Naveed의 답변은 하나가 아닌 모든 중복을 반환했습니다(작은 점이지만 하나만 반환하면 둘 다 동일하기 때문에 둘 다를 평가하는 것은 의미가 없습니다).
또한 모든 중복 항목을 반환하는 다른 답변도 처음 발견된 항목만 반환하도록 수정했지만, 선택하기 전에 모든 중복 항목을 계산했기 때문에 성능에 근본적으로 영향을 미치지 않습니다.
각 벤치마크의 결과는 가장 빠른 것부터 가장 느린 것까지 나열되어 있습니다.
먼저 배열에 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#differenceRuby 코어에 추가된 경우 C에 구현되었습니다.
결론
대부분의 답은 합리적이지만 세트를 사용하는 것이 가장 좋은 선택입니다.그것은 중경도의 경우에서 가장 빠르고, 가장 어려운 경우에서 가장 빨리 관절을 접합하고 계산적으로 사소한 경우에서만 - 어쨌든 당신의 선택이 중요하지 않을 때 - 이길 수 있습니다.
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)의 양인 모리최, 그나의한양만소러메▁the.
이제 어레이에 중복이 얼마나 자주 있는지에 따라 이러한 런타임이 훨씬 더 좋아질 수 있습니다.예를 들어 크기의 배열이O(n)은 의 모 단 에 추 었 습 되 니 다 출 표 집 이 본 서 ulation ▁of ▁from ▁has ▁pop ▁been ▁sampled ▁a 다 의니 습k << n다른 요소들만 런타임과 공간 모두에 대한 복잡성이 됩니다.O(k)그러나 원본 포스터가 입력 내용을 검증하고 중복이 없는지 확인하려고 할 가능성이 높습니다.이 경우 런타임 및 메모리 복잡성 모두O(n)대부분의 입력에 대해 요소가 반복되지 않을 것으로 예상하기 때문입니다.
메서드인 Ruby Array를 .select.
select {|item| block } → new_ary
select → an_enumerator
첫 번째 양식은 여기서 여러분의 관심을 끄는 것입니다.테스트에 합격한 개체를 선택할 수 있습니다.
에는 Ruby Array라는 메서드가 .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"]
하나의 개체만 원한다고 말합니다.하나만 골라주세요.
find_all을 반환합니다.array의 모든 요소를 포함하는enum그 때문에block아닙니다false.
갖기 위해duplicate요소들
>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }
=> ["A", "B", "B", "A"]
또는 중복uniq요소들
>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"]
루비 2.7 도입
다음과 같은 방식으로 사용할 수 있습니다.
ary = ["A", "B", "C", "B", "A", "A"]
ary.tally.select { |_, count| count > 1 }.keys
# => ["A", "B"]
ary = ["A", "B", "C"]
ary.tally.select { |_, count| count > 1 }.keys
# => []
Ruby 2.7도 도입되었으며, 이 방법들을 결합할 수 있습니다.
ary = ["A", "B", "C", "B", "A", "A"]
ary.tally.filter_map { |el, count| el if count > 1 }
# => ["A", "B"]
이와 같은 것이 효과가 있을 것입니다.
arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
select { |k,v| v > 1 }.
collect { |x| x.first }
즉, 모든 값을 해시에 넣습니다. 여기서 key는 배열 요소이고 value는 발생 횟수입니다.그런 다음 두 번 이상 발생하는 모든 요소를 선택합니다.만만하다.
이 스레드가 Ruby에 대한 구체적인 내용이라는 것은 알고 있지만, ActiveRecord를 사용하는 Ruby on Rails의 맥락에서 이 작업을 수행하는 방법을 찾고 있었기 때문에 제 솔루션도 공유하려고 했습니다.
class ActiveRecordClass < ActiveRecord::Base
#has two columns, a primary key (id) and an email_address (string)
end
ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys
위의 명령은 이 예제의 데이터베이스 테이블(레일즈에서는 "active_record_classes")에서 중복되는 모든 전자 메일 주소의 배열을 반환합니다.
a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys
이것은O(n)절차.
또는 다음 행 중 하나를 수행할 수 있습니다.또한 O(n)이지만 한 번만 반복됩니다.
a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]
a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]
이 코드는 중복된 값의 목록을 반환합니다.해시 키는 이미 표시된 값을 확인하는 효율적인 방법으로 사용됩니다.값이 표시되었는지 여부를 기준으로 원래 배열ary는 두 개의 배열로 분할됩니다. 첫째는 고유한 값을 포함하고 둘째는 중복된 값을 포함합니다.
ary = ["hello", "world", "stack", "overflow", "hello", "again"]
hash={}
arr.partition { |v| hash.has_key?(v) ? false : hash[v]=0 }.last.uniq
=> ["hello"]
좀 더 복잡한 구문을 사용하더라도 다음과 같은 형식으로 단축할 수 있습니다.
hash={}
arr.partition { |v| !hash.has_key?(v) && hash[v]=0 }.last.uniq
중복 부품을 찾기 위한 레거시 dBase 테이블과 같은 대규모 데이터 세트에 대한 저의 견해는 다음과 같습니다.
# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is
# duplicated is much more convenient in the real world application
# Takes about 6 seconds to run on my data set
# - not too bad for an export script handling 20000 parts
h = {};
# or for readability
h = {} # result hash
ps.select{ |e|
ct = ps.count(e)
h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn't print in the console
r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]
r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)
each_with_object너의 친구야!
input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]
# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}
# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}
a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c
결과.
d
=> ["A", "B", "C"]
두 개의 배열을한다면 () 빠른 방법은 교차 연산자를 입니다.&Ruby's Array 클래스에서 제공합니다.
# Given
a = ['a', 'b', 'c', 'd']
b = ['e', 'f', 'c', 'd']
# Then this...
a & b # => ['c', 'd']
이는 매우 빠르게 실행됩니다(2.3마일(약 2.3마일). 자체 어레이에 백업을 푸시하는 데 1초도 걸리지 않음)
회사에서 파일로 가져온 230만 개의 ID로 이 작업을 수행해야 했습니다. 정렬된 목록으로 가져왔으며 루비별로 정렬할 수도 있습니다.
list = CSV.read(path).flatten.sort
dup_list = []
list.each_with_index do |id, index|
dup_list.push(id) if id == list[index +1]
end
dup_list.to_set.to_a
def duplicates_in_array(array)
hash = {}
duplicates_hash = {}
array.each do |v|
hash[v] = (hash[v] || 0 ) + 1
end
hash.keys.each do |hk|
duplicates_hash[hk] = hash[hk] if hash[hk] > 1
end
return duplicates_hash
end
이렇게 하면 어레이의 각 중복 항목이 포함된 해시가 반환되고 중복된 시간이 반환됩니다.
예:
array = [1,2,2,4,5,6,7,7,7,7]
duplicates_in_array(array)
=> {2=>2, 7=>4}
저는 복제품이 몇 개이고 무엇인지 알아야 했기 때문에 Naveed가 이전에 게시한 내용을 기반으로 한 기능 구축을 작성했습니다.
def print_duplicates(array)
puts "Array count: #{array.count}"
map = {}
total_dups = 0
array.each do |v|
map[v] = (map[v] || 0 ) + 1
end
map.each do |k, v|
if v != 1
puts "#{k} appears #{v} times"
total_dups += 1
end
end
puts "Total items that are duplicated: #{total_dups}"
end
- 요소 배열을 입력으로 하는 복제 방법을 만들자.
- 메서드 본문에서 두 개의 새 어레이 개체를 생성합니다. 하나는 표시되고 다른 하나는 중복됩니다.
- 마지막으로 지정된 배열의 각 개체를 통해 반복할 수 있으며, 반복할 때마다 표시된 배열에 존재하는 개체를 찾을 수 있습니다.
- seeen_array에 개체가 있으면 중복 개체로 간주되고 해당 개체를 duplication_array에 밀어넣습니다.
- 개체가 seek에 없으면 고유 개체로 간주되고 해당 개체를 seek_array로 밀어넣습니다.
코드 구현에서 시연해 보겠습니다.
def duplication given_array
seen_objects = []
duplication_objects = []
given_array.each do |element|
duplication_objects << element if seen_objects.include?(element)
seen_objects << element
end
duplication_objects
end
이제 중복 메소드 호출 및 출력 반환 결과 -
dup_elements = duplication [1,2,3,4,4,5,6,6]
puts dup_elements.inspect
[1,2,3].uniq!.nil? => true [1,2,3,3].uniq!.nil? => false
위의 내용은 파괴적입니다.
언급URL : https://stackoverflow.com/questions/8921999/how-to-find-and-return-a-duplicate-value-in-array
'programing' 카테고리의 다른 글
| Bash 스크립트: 파일에서 고유한 줄 수 (0) | 2023.05.27 |
|---|---|
| T-SQL을 사용하여 MD5 해시 문자열 생성 (0) | 2023.05.27 |
| bash : 잘못된 대체 (0) | 2023.05.27 |
| 마이크로소프트를 구성합니다.사용자 이름으로 전자 메일 주소를 허용하는 AsNet.Identity (0) | 2023.05.27 |
| express.js에서 HTTPS 사용 (0) | 2023.05.22 |