루비 비트 제품

Question

나는 2 개의 정수를 취하여 비트 곱을 반환하는 함수를 작성해야하는 과제를 가지고있다. 비트 곱은이 두 숫자 사이의 모든 숫자의 비트 합계 (&)와 같습니다. 예를 들어

: 251 및 253의 비트 제품은 다음과 같습니다

irb(main):164:0> 251 & 252 
=> 248 
irb(main):165:0> 252 & 253 
=> 252 
irb(main):166:0> 248 & 252 
=> 248 # this a bitwise & of these two between 251 & 253 

내 기능 :

def solution(m,n) 
    (m..n).to_a.inject{|sum, x| sum &= x} 
end 

테스트 :

irb(main):160:0> (251..253).to_a.inject{|sum, x| sum &= x} 
=> 248 #same result 

프로그램의 평가 :

정확성 100 %
성능

사람이이 기능의 성능을 무엇을 설명시겠습니까 0 %? 미리 감사드립니다!

편집

이후 성능 당신은, 예를 들어, 정말 큰 입력을위한 기능의 분석을 제공하고/더/더 효율적인 솔루션을 제안 비판 할 수 있습니다, 여기에 정의되지?

p.s. 의견 얘들 아, 그 권고를 따를 것입니다!

Answer 1

내 댓글에 최대에 따라, 당신은 벤치 마크를 사용하여 실험 할 수 있습니다

다음

def solution(m,n) 
    (m..n).to_a.inject{|sum, x| sum &= x} 
end 

def solution2(m,n) 
    (m..n).reduce(:&) 
end 

n = 50000 
Benchmark.bm(7) do |b| 
    b.report("orig:") { n.times do; solution(128,253); end } 
    b.report("new: ") { n.times do; solution2(128,253); end } 
end 

내가 무엇을 얻을 :

   user  system  total  real 
orig:  1.560000 0.000000 1.560000 ( 1.557156) 
new:  0.640000 0.000000 0.640000 ( 0.634063) 

당신은 위의 실험을 할 수 있지만 선택의 여지가하지 표시 빠른 알고리즘을 찾은 다음 성능 측정기에 등록 할 때까지 테스트를 실행하십시오.

Answer 2

여기에서 가장 명백한 성능 문제는 배열 (to_a) 로의 변환입니다. 꼭 필요한 것은 아닙니다. reduce 및 inject (동일하게 표시) 전화는 Enumerable, Range 모두 포함 할 수 있습니다. 은 근본적으로 유한 요소 (논쟁의 여지가 있지만 대부분 사실입니다)를 생성 할 수있는 모든 요소입니다. Range은 정수 집합으로 처리되는 경우 적합합니다.

이 범위의 요소로 배열을 반복하려면 먼저 배열을 만들고 요소를 채 웁니다 (반복하여 Range). 그런 다음 작업 결과를 적용한 결과 배열을 반복합니다. 그래서 iterating, 채우기, 사용, 배열을 목적으로 배열을 만듭니다. 범위가 클 경우에는이를 수행하는 데 상당한 메모리 할당이 필요합니다.

다음은 비판적이지만 코드의 양을 줄이기 위해 Ruby에서 연산자의 내부 구현에 대한 지식이 필요합니다. a&b을 쓸 때 a.&(b) : 실제로 숫자로 & 메서드를 호출하고 있습니다.

는 sum 당신이 블록에 도착하는 것은 실제로 거기에 무엇을 할당 할 필요가 없습니다, 정말 accumulator의 일종 아니라, sum는 중간 값, 실제로는 반환 값이어야합니다 새로운 요소를 추가 한 결과입니다. 할당은 할당 된 값을 반환하므로이 방식으로도 작동합니다. 이 블록은 사소하다

(251..253).inject{|sum, x| sum & x } # => 248, as expected 

...하고 밝혀 : 그 증명이 하나의 값을 다른 값으로의 메소드를 호출한다. inject은 각 반복마다 한 쌍의 값을 취하므로 메서드 이름을 지정하고 상황을 처리하도록 할 수 있습니다. 루비의 메소드 이름은 일반적으로 다음과 같은 기호로 참조됩니다 :

(251..253).inject(:&) # => 248, as expected 

좋아, 두 배 정도 적은 코드가 적은 작업을 완료하고 덜 객체는, 그럼에도 불구하고 동일한 결과를했다.

def solution(m,n) 
    (m..n).inject(:&) 
end 

우리는 inject을 자세히 살펴 보지 않았습니다. 성능 측면에서 inject을 이길 수 있습니까?

[11] pry(main)> show-source Range#inject 

From: enum.c (C Method): 
Owner: Enumerable 
Visibility: public 
Number of lines: 34 

...a bunch of C code here