3

я использую dictionary в C# для быстрой проверки существования элемента в массиве по ключу, по факту значение ключа мне не нужно, выглядит это так:

public void update_object_select_contour(MyObject myObject)
    {
        List<Vector2i> list_position_tmp = myObject.list_position;
        Dictionary<string, byte> dictionary_position_tmp = new Dictionary<string, byte>();
        for (int i = 0; i < list_position_tmp.Count; i++)
        {
            dictionary_position_tmp.Add(list_position_tmp[i].ToString(), 0);
        }
        if(dictionary_position.ContainsKey(new Vector2i(5, 5).ToString()))
        {
            //Поиск элемента по ключу
        }
    }

То есть я закидываю координаты точек в dictionary и потом проверяю есть ли они там по нужному мне поиску и у меня есть 2 вопроса:

1) Какую структуру хранения данных можно использовать для этого?(пытался найти деревья в C#, так и не нашел) Хотелось бы чтобы выглядело это примерно так:

Dictionary<string>

2) Какой лучше использовать ключ для хранения положений координат? Как я знаю преобразовывать пары к тексту и хранить как текст не лучшая идея

1
  • 2
    Чем не подошёл HashSet<T>?
    – A K
    11 авг 2019 в 9:07

1 ответ 1

5

Вы используете словарь. Словарь - это когда у вас есть ключ и есть значение, ассоциированное с ключом.

То, что вам нужно, называется HashSet<T>.

Если вы хотите хранить в HashSet<T> координаты, то тогда координаты желательно должны быть целыми числами, так как дробные числа могут быть не равны даже если они были посчитаны по одной и той же формуле просто из за наличия погрешности.

Но вот с целыми числами проще. Но тут нужно иметь ввиду, так как, если вы будете хранить координаты в HashSet<T>, который использует хеш функцию для хранения и хеш функцию и функцию эквивалентности для поиска элементов, вас в классе координат надо перегрузить методы Equals и GetHashCode. Вот пример:

public class Coordinates2D
{
    public int X { get; }
    public int Y { get; }

    public Coordinates2D(int x, int y)
    {
        X = x;
        Y = y;
    }

    protected bool Equals(Coordinates2D other)
    {
        return X == other.X && Y == other.Y;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Coordinates2D) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (X * 397) ^ Y;
        }
    }
}

Теперь этот класс можно использовать в HashSet<Coordinates2D>

var set = new HashSet<Coordinates2D>();

set.Add(new Coordinates2D(10, 25));

Console.WriteLine(set.Contains(new Coordinates2D(1, 1))); // false
Console.WriteLine(set.Contains(new Coordinates2D(10, 25))); // true

Вывод очевиден

...

7
  • Попробовал данный метод хеширования, спасибо, работает, НО я нашел более оптимальный способ хеширования public override int GetHashCode() { return (x << 13) ^ y; } позволяет убрать повторения хешей на 8192 по х и 8192 по y, помогло ускорить программу, возможно кому то пригодится тоже 13 авг 2019 в 8:58
  • @ИльяАнтипанов я эти методы для эквивалетности и хеширования просто сгенерировал решарпером. По поводу вашего x << 13 что то есть у меня сомнения по поводу этого метода, как насчет коллизий в этом случае?
    – tym32167
    13 авг 2019 в 9:01
  • @ИльяАнтипанов кстати, если вы заметили, я сделал координаты неизменяемым классом. Если у вас он тоже неизменяемый, то можно хеш предрассчитать и закешировать.
    – tym32167
    13 авг 2019 в 9:08
  • я понимаю что это был пример, но на официальном мануале метод хеширования был вообще [docs.microsoft.com/ru-ru/dotnet/api/… (x ^ y). Попробовал и этот метод использовать в программе но коллизий там была куча и программа открывалась медленно. А с (x<<13)^y мы убираем коллизии если х и у будут меньше 8192, если будут уже больше 8192 то начнут появлятся коллизии. 13 авг 2019 в 9:18
  • а, ну, если у вас числа не больше 8192, тогда наверное для координат нет смысла использовать int, short должно быть достаточно. Ну или если вас int устраивает, то да, сдвиг будет работать.
    – tym32167
    13 авг 2019 в 9:24

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.