[ruby] O (n)보다 빠르게 배열 요소의 인덱스 가져 오기

Program / 글쓴이

나는 거대한 배열과 그것의 값을 가지고 있습니다. 배열 값의 인덱스를 얻고 싶습니다. Array#index그것을 얻기 위해 전화 하는 것보다 다른 방법 이 있습니까? 문제는 정말 거대한 배열을 유지하고 Array#index엄청난 시간을 호출 할 필요가 있기 때문입니다.

몇 번의 시도 끝에 값 자체 대신 필드가있는 구조체를 저장하여 요소 내부에 인덱스 를 캐싱(value, index) 하면 성능이 크게 향상 된다는 사실을 발견했습니다 (20 배 승리).

그래도 캐싱없이 en 요소의 인덱스를 찾는 더 편리한 방법이 있는지 궁금합니다 (또는 성능을 향상시키는 좋은 캐싱 기술이 있습니다).

답변

배열을 해시로 변환합니다. 그런 다음 열쇠를 찾으십시오.

array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a]    # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 1

답변

index 또는 rindex를 사용하지 않는 이유는 무엇입니까?

array = %w( a b c d e)
# get FIRST index of element searched
puts array.index('a')
# get LAST index of element searched
puts array.rindex('a')

색인 : http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-index

rindex : http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-rindex

답변

다른 답변은 배열에 여러 번 나열된 항목의 가능성을 고려하지 않습니다. 그러면 각 키가 배열의 고유 한 개체이고 각 값이 개체가있는 위치에 해당하는 인덱스 배열 인 해시가 반환됩니다.

a = [1, 2, 3, 1, 2, 3, 4]
=> [1, 2, 3, 1, 2, 3, 4]

indices = a.each_with_index.inject(Hash.new { Array.new }) do |hash, (obj, i)|
    hash[obj] += [i]
    hash
end
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5], 4 => [6] }

이렇게하면 중복 항목을 빠르게 검색 할 수 있습니다.

indices.select { |k, v| v.size > 1 }
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] }

답변

해시를 사용하지 않는 합당한 이유가 있습니까? 조회는 어레이 O(1)와 비교 O(n)됩니다.

답변

그것은 만약 정렬 된 배열은 이진 검색 알고리즘을 사용할 수있다 ( O(log n)). 예를 들어 다음 기능으로 Array 클래스를 확장합니다.

class Array
  def b_search(e, l = 0, u = length - 1)
    return if lower_index > upper_index

    midpoint_index = (lower_index + upper_index) / 2
    return midpoint_index if self[midpoint_index] == value

    if value < self[midpoint_index]
      b_search(value, lower_index, upper_index - 1)
    else
      b_search(value, lower_index + 1, upper_index)
    end
  end
end

답변

@sawa의 답변과 거기에 나열된 주석을 조합하면 배열 클래스에 “빠른”인덱스와 rindex를 구현할 수 있습니다.

class Array
  def quick_index el
    hash = Hash[self.map.with_index.to_a]
    hash[el]
  end

  def quick_rindex el
    hash = Hash[self.reverse.map.with_index.to_a]
    array.length - 1 - hash[el]
  end
end

답변

배열에 자연 순서가 있으면 이진 검색을 사용하십시오.

이진 검색을 사용하십시오.

이진 검색에는 O(log n)액세스 시간 이 있습니다.

이진 검색을 사용하는 방법에 대한 단계는 다음과 같습니다.

  • 배열 순서는 무엇입니까? 예를 들어, 이름별로 정렬되어 있습니까?
  • bsearch요소 또는 인덱스를 찾는 데 사용

코드 예

# assume array is sorted by name!

array.bsearch { |each| "Jamie" <=> each.name } # returns element
(0..array.size).bsearch { |n| "Jamie" <=> array[n].name } # returns index