Как сделать «GROUP BY» математически?

Question

У меня есть структура данных пар ключ-значение, и я хочу реализовать значение "GROUP BY". И ключи, и значения являются строками.

Итак, я дал каждому значению (строке) уникальное «простое число». Затем для каждого ключа я хранил умножение всех простых чисел, связанных с различными значениями, которые имеет конкретный ключ. Поэтому, если ключ «Anirudh» имеет значения «x», «y», «z», то я также сохраняю число M (Key) = 2 * 3 * 5 = 30. Позже, если я хочу сделать группу по определенному значению «x» (скажем), то я просто переберу все ключи и разделю M (ключ) на простое число, связанное с «x». Затем я проверяю, равен ли остаток 0 и равен ли он нулю, то этот конкретный «ключ» является частью группы по значению «x».

Я знаю, что это самый странный способ сделать это. Некоторые люди сортируют пары ключ-значение (отсортированные по значениям). Я мог бы также создать другую таблицу (хэш-таблицу), уже сгруппированную по «значениям». Поэтому я хочу знать лучший метод, чем мой (их должно быть много). В моем методе по мере увеличения числа уникальных значений для определенного ключа произведение простого числа также увеличивается (что тоже экспоненциально).

Answer 1

Ваш метод всегда будет выполнять O (n), чтобы найти членов группы, потому что вам нужно перебирать все элементы коллекции, чтобы найти элементы, принадлежащие целевой группе.Ваш метод также рискует переполнить общие целочисленные границы (32, 64 бита), если у вас много элементов, поскольку вы умножаете потенциально большое количество простых чисел вместе, чтобы сформировать ваш ключ.

Вы найдете его более эффективным и, безусловно,более предсказуемо использовать битовую маску для отслеживания членства в группах, следуя этому подходу.Если у вас есть 16 групп, вы можете представить это с помощью 16-битного короткого кода, используя битовую маску.При использовании простых чисел, как вы предлагаете, вам понадобится целое число с достаточным количеством битов для хранения числа 32589158477190044730 (умножаются первые 16 простых чисел), что потребует 65 бит.

Другими подходами к группировке также являются O (n) дляпервая итерация (в конце концов, каждый элемент должен быть проверен хотя бы один раз для членства в группе).Однако если вы склонны повторять одни и те же групповые проверки, другие методы, на которые вы ссылаетесь (например, ведение списка или хэш-таблицы для целевой группы), гораздо эффективнее, поскольку последующие тесты на членство в группе - O (1).

Таким образом, чтобы непосредственно ответить на ваш вопрос:

• Если существует несколько запросов на членство в группе (повторение некоторых групп), любое решение, в котором хранятся группы (включая те, которые вы предлагаете в своем вопросе), будет работать лучше.чем ваш метод.
• Если нет повторных запросов для членства в группе, нет никакого преимущества для хранения членства в группе

Учитывая, что повторные запросы кажутся вероятными, основываясь на вашем вопросе:

• Используйте структуру, такую ​​как список, отключенный от идентификатора группы, для хранения членства в группе, если вы хотите обменять память, чтобы получить более высокую скорость.
• Используйте достаточно широкий битовый массив для хранения группычленство, если вы хотите торговать быстрее, чтобы использовать меньше памяти.

Answer 2

Если вы не знаете, о чем здесь идет речь, но это звучит похоже (но намного дороже в вычислительном отношении), чем битовый вектор или сумма степеней 2. Первое значение - «1», второе - «2»,третий "4" и так далее.Если вы получили «7», вы знаете, что это «первый» + «второй» + «третий».