У меня есть сценарий, в котором мне нужно сравнить ключи вектора. У меня есть 2 значения в каждом ключе вектора.

Нужно найти векторный ключ, в котором

  1. первое значение вектора должно быть больше, чем все первые значения каждого ключа вектора
  2. и второе значение вектора должно быть меньше, чем все вторые значения каждого ключа вектора

Пожалуйста, ниже приведен пример кода:

let mut queue : HashMap, Vec> = HashMap::new();

queue.insert(vec![5 as u8, queue.keys().len() as u8], vec![0]);
queue.insert(vec![10 as u8, queue.keys().len() as u8], vec![1]);
queue.insert(vec![10 as u8, queue.keys().len() as u8], vec![2]);
queue.insert(vec![3 as u8, queue.keys().len() as u8], vec![2]);
queue.insert(vec![4 as u8, queue.keys().len() as u8], vec![3]);
queue.insert(vec![6 as u8, queue.keys().len() as u8], vec![4]);

let key= queue
    .iter()
    .max_by(|a, b| {
        a.0.cmp(&b.0)
    })
    .map(|(k, _v)| k);

println!("{:?}", key);

Я получаю этот вывод Some([10, 2]). Но я хочу получить на выходе Some([10, 1]). `

вот моя карта : {[10, 1]: [1], [4, 4]: [3], [6, 5]: [4], [10, 2]: [2], [3, 3]: [2], [5, 0]: [0]}

Sonu

Ответов: 2

Ответы (2)

Вам нужна функция сравнения max_by, которая сравнивает первый элемент, чтобы найти наибольший, и второй, чтобы найти наименьший. Давайте сначала разберемся с первым критерием: первый элемент должен быть наибольшим.

a.0[0].cmp(&b.0[0])

a.0 и b.0, как вы, вероятно, уже догадались, выбирают ключ из предоставленной пары ключ-значение. Затем мы используем обычную индексацию [], чтобы получить первый элемент вектора.

Для целей вопроса я предполагаю, что нам нужно лексикографическое упорядочивание, также называемое словарным порядком. То есть, вы перечислили два критерия, и я предполагаю, что первый имеет приоритет, так что, например, [10, 2] должен быть предпочтительнее [9, 1], поскольку первый элемент больше, несмотря на то, что второй не меньше.

С учетом этого предположения мы можем расширить наше сравнение. Чтобы изменить порядок (т. е. выбрать наименьший, а не наибольший элемент), мы можем просто поменять порядок аргументов.

b.0[1].cmp(&a.0[1])

Тогда мы хотим использовать это сравнение только в том случае, если первое нас не устроило, т.е. если первое было равно.

match a.0[0].cmp(&b.0[0]) {
  Ordering::Equal => b.0[1].cmp(&a.0[1]),
  x => x
}

Если мы подставим это в вашу функцию max_by, мы получим [10, 1], как и хотелось.

Но на самом деле мы можем сделать еще лучше. Смотрите, лексикографическое упорядочивание встречается довольно часто, настолько часто, что оно встроено в Rust. Мы можем использовать метод Ordering::then следующим образом.

a.0[0].cmp(&b.0[0]).then(b.0[1].cmp(&a.0[1]))

И это работает идентично предыдущему примеру.

Полный пример:

let mut queue : HashMap, Vec> = HashMap::new();

queue.insert(vec![5 as u8, queue.keys().len() as u8], vec![0]);
queue.insert(vec![10 as u8, queue.keys().len() as u8], vec![1]);
queue.insert(vec![10 as u8, queue.keys().len() as u8], vec![2]);
queue.insert(vec![3 as u8, queue.keys().len() as u8], vec![2]);
queue.insert(vec![4 as u8, queue.keys().len() as u8], vec![3]);
queue.insert(vec![6 as u8, queue.keys().len() as u8], vec![4]);

let key = queue
  .iter()
  .max_by(|a, b| {
    a.0[0].cmp(&b.0[0]).then(b.0[1].cmp(&a.0[1]))
  })
  .map(|(k, _v)| k);

println!("{:?}", key);

HashMap - неправильная структура данных для этой задачи. Чтобы решить эту задачу, вы должны получить доступ к каждому элементу карты. Если вы контролируете свои данные, то вместо этого вам следует хранить их в BTreeMap. Тогда решение вашей проблемы будет выглядеть так:

fn get_first_of_max(queue: &BTreeMap, Vec>) -> Option> {
    let max_key_prefix = queue.keys().rev().next()?;
    queue.range((
        Bound::Included(vec![max_key_prefix[0], 0]), 
        Bound::Unbounded,
    )).next().map(|x| x.0.to_owned())
}

С учетом того, что вы делаете со своими значениями, я бы также предпочел (u8, usize) для ключа. В сочетании с вышеизложенным вы получите:

use std::collections::BTreeMap;
use std::ops::Bound;

fn get_first_of_max(queue: &BTreeMap<(u8, usize), Vec>) -> Option<(u8, usize)> {
    let max_key_prefix = queue.keys().rev().next()?;
    queue.range((
        Bound::Included((max_key_prefix.0, 0)), 
        Bound::Unbounded,
    )).next().map(|x| x.0.to_owned())
}

fn main() {
    let mut queue = BTreeMap::new();

    queue.insert((5, queue.keys().len()), vec![0]);
    queue.insert((10, queue.keys().len()), vec![1]);
    queue.insert((10, queue.keys().len()), vec![2]);
    queue.insert((3, queue.keys().len()), vec![3]);
    queue.insert((4, queue.keys().len()), vec![4]);
    queue.insert((6, queue.keys().len()), vec![5]);

    println!("{:?}", get_first_of_max(&queue));
}

2022 WebDevInsider