플로트 Vec에서 이진 검색을 수행하는 방법은 무엇입니까?

Question

Vec<u32> 사용자는 slice::binary_search 메서드를 사용합니다.

이유는 이해가 안되기 때문에 f32과 f64은 Ord을 구현하지 않습니다. 프리미티브 유형은 표준 라이브러리에 있기 때문에 직접 Ord을 구현할 수 없으므로이 방법을 사용할 수있는 것으로 보이지 않습니다.

어떻게 효과적으로 할 수 있습니까?

래퍼 구조체에 실제로 f64을 랩핑하고 Ord을 구현해야합니까? 이 작업을 수행하는 것이 매우 힘들어 보이며 아무런 이유없이 효율적으로 데이터 블록을 앞뒤로 전송하려면 많은 수의 transmute이 필요합니다.

Answer 1

이유가 모르겠다는 이유로 f32와 f64는 Ord를 구현하지 않습니다.

floating point is hard! 짧은 버전은 부동 소수점 숫자가 NaN - 숫자가 아닌 특별한 값을 갖는다는 것입니다. 부동 소수점 수에 대한 IEEE 사양에 따르면 1 < NaN, 1 > NaN 및 NaN == NaN은 모두 false입니다.

Ord 말한다하십시오 total order을 형성 유형

이

형질.

이는 비교가 전체 가질 필요가 있다는 것을 의미하십시오

≤

≤의 B 또는 b를하지만 우리는 단지 부동 소수점이 속성이없는 것을 보았다.

그래, 당신은 어떤 식 으로든 large number of NaN values을 비교하는 래퍼 유형을 만들어야합니다. 아마도 float 값이 결코 NaN이 아니며 일반 PartialOrd 특성을 호출한다고 단정 할 수 있습니다. 다음은 그 예입니다.

use std::cmp::Ordering; 

#[derive(PartialEq,PartialOrd)] 
struct NonNan(f64); 

impl NonNan { 
    fn new(val: f64) -> Option<NonNan> { 
     if val.is_nan() { 
      None 
     } else { 
      Some(NonNan(val)) 
     } 
    } 
} 

impl Eq for NonNan {} 

impl Ord for NonNan { 
    fn cmp(&self, other: &NonNan) -> Ordering { 
     self.partial_cmp(other).unwrap() 
    } 
} 

fn main() { 
    let mut v: Vec<_> = [2.0, 1.0, 3.0].iter().map(|v| NonNan::new(*v).unwrap()).collect(); 
    v.sort(); 
    let r = v.binary_search(&NonNan::new(2.0).unwrap()); 
    println!("{:?}", r); 
} 

Answer 2

슬라이스 방법 중 하나는 binary_search_by입니다. 사용할 수 있습니다. 당신은 그들이 NaN 결코 수있어 그래서 만약/f64f32는 partial_cmp의 결과를 풀다 수, PartialOrd을 구현 :

fn main() { 
    let values = [1.0, 2.0, 3.0, 4.0, 5.0]; 
    let location = values.binary_search_by(|v| { 
     v.partial_cmp(&3.14).expect("Couldn't compare values") 
    }); 

    match location { 
     Ok(i) => println!("Found at {}", i), 
     Err(i) => println!("Not found, could be inserted at {}", i), 
    } 
} 

Answer 3

https://github.com/emerentius/ord_subset 당신이 사용할 수있는 ord_subset_binary_search() 방법을 구현한다. 자신의 README에서

: 슬라이스 확장 방법

let mut s = [5.0, std::f64::NAN, 3.0, 2.0]; 
s.ord_subset_sort(); 
assert_eq!(&s[0..3], &[2.0, 3.0, 5.0]); 
assert_eq!(s.ord_subset_binary_search(&5.0), Ok(2)); 

assert_eq!(s.iter().ord_subset_max(), Some(&5.0)); 
assert_eq!(s.iter().ord_subset_min(), Some(&2.0));