Какой самый быстрый и правильный способ обнаружить отсутствие дубликатов в массиве JSON? - PullRequest
Новая
       25

Какой самый быстрый и правильный способ обнаружить отсутствие дубликатов в массиве JSON?

2 голосов
/ 27 марта 2020

Мне нужно проверить, все ли элементы уникальны в массиве serde_json::Value. Поскольку этот тип не реализует Hash, я пришел к следующему решению: 

use serde_json::{json, Value};
use std::collections::HashSet;

fn is_unique(items: &[Value]) -> bool {
    let mut seen = HashSet::with_capacity(items.len());
    for item in items.iter() {
        if !seen.insert(item.to_string()) {
            return false;
        }
    }
    true
}

fn main() {
    let value1 = json!([1, 2]);
    assert!(is_unique(&value1.as_array().unwrap()));
    let value2 = json!([1, 1]);
    assert!(!is_unique(&value2.as_array().unwrap()));
}

Я предполагаю, что он должен работать, только если serde_json построен с функцией preserve_order (чтобы объекты сериализовались в один и тот же порядок каждый раз), но я не уверен на 100%.

Основной контекст использования :

JSON Проверка схемы. Реализация ключевого слова " uniqueItems ".

Пример использования

Дедупликация массивов JSON для оптимизации JSON Вывод схемы на них.

Например, входные данные [1, 2, {"foo": "bar"}]. Прямой вывод может вывести это: 

{
    "type": "array", 
    "items": {
        "anyOf": [
            {"type": "integer"}, 
            {"type": "integer"},
            {"type": "object", "required": ["foo"]}
        ]
    }
}

значения в items/anyOf могут быть уменьшены только до двух значений.

Вопрос : Что будет наиболее эффективный и правильный способ проверить, что в произвольном массиве JSON нет дубликатов?

Я использовал serde_json = "1.0.48"

Rust : 1.42.0

Детская площадка

Ответы [ 2 ]

3 голосов
/ 27 марта 2020

Преобразование каждого элемента массива в строку довольно дорого - требуется как минимум одно выделение строки на элемент, и, скорее всего, больше. Также трудно убедиться, что отображения (или «объекты» на языке JSON) представлены в канонической форме.

Более быстрая и надежная альтернатива - реализовать Hash для Value самостоятельно. Вам нужно определить оболочку нового типа, поскольку вы не можете реализовать стороннюю черту для внешнего типа. Вот простой пример реализации: 

use serde_json::Value;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;

#[derive(PartialEq)]
struct HashValue<'a>(pub &'a Value);

impl Eq for HashValue<'_> {}

impl Hash for HashValue<'_> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        use Value::*;
        match self.0 {
            Null => state.write_u32(3_221_225_473), // chosen randomly
            Bool(ref b) => b.hash(state),
            Number(ref n) => {
                if let Some(x) = n.as_u64() {
                    x.hash(state);
                } else if let Some(x) = n.as_i64() {
                    x.hash(state);
                } else if let Some(x) = n.as_f64() {
                    // `f64` does not implement `Hash`. However, floats in JSON are guaranteed to be
                    // finite, so we can use the `Hash` implementation in the `ordered-float` crate.
                    ordered_float::NotNan::new(x).unwrap().hash(state);
                }
            }
            String(ref s) => s.hash(state),
            Array(ref v) => {
                for x in v {
                    HashValue(x).hash(state);
                }
            }
            Object(ref map) => {
                let mut hash = 0;
                for (k, v) in map {
                    // We have no way of building a new hasher of type `H`, so we
                    // hardcode using the default hasher of a hash map.
                    let mut item_hasher = DefaultHasher::new();
                    k.hash(&mut item_hasher);
                    HashValue(v).hash(&mut item_hasher);
                    hash ^= item_hasher.finish();
                }
                state.write_u64(hash);
            }
        }
    }
}

Значение для None выбирается случайным образом, чтобы исключить вероятность его столкновения с другими записями. Для вычисления хэшей для чисел с плавающей запятой я использовал ordered-float ящик. Для отображений код вычисляет ha sh для каждой пары ключ / значение и просто XOR объединяет эти хэши, что не зависит от порядка. Немного прискорбно, что нам нужно жестко закодировать хеш, используемый для хэширования записей карты. Мы могли бы абстрагироваться от этого, определив нашу собственную версию черты Hash, а затем извлечь конкретные реализации std::hash::Hash из нашей пользовательской черты Hash, но это немного усложняет код, поэтому я бы не стал этого делать если вам не нужно.

Мы не можем получить Eq, поскольку Value не реализует Eq. Однако я считаю, что это всего лишь упущение, поэтому я подал вопрос о добавлении Eq реализации (для которого был принят PR, поэтому он появится в каком-то будущем выпуске).

0 голосов
/ 27 марта 2020

Зависит от того, отсортирован массив JSON или нет. Если он отсортирован, вы можете использовать бинарный поиск, чтобы проверить соответствие значения другим значениям. Для сортировки вы можете использовать сортировку слиянием. Общая сложность будет O (nlogn + logn). Или вы можете выполнить итерацию последовательно и проверить наличие дублирующихся строк O (n ^ 2).

...