我有一个键值对的数据结构，我想实现“GROUP BY”值。 键和值都是字符串。
所以我所做的就是给每个值(字符串)一个唯一的“质数”。然后，对于每个键，我都存储了与特定键具有的不同值相关联的所有素数的乘积。 因此，如果键“Anirudh”的值为“x”、“y”、“z”，那么我也会存储数字 M(Key) = 2*3*5 = 30。 稍后，如果我想按特定值“x”(比方说)进行分组，那么我只需遍历所有键，然后将 M(键)除以与“x”关联的质数。然后我检查余数是否为 0，如果它为零，则该特定“键”是值“x”的分组依据的一部分。
我知道这是最奇怪的做法。有些人对键值对进行排序(按值排序)。我还可以创建另一个已经按“值”分组的表(哈希表)。所以我想知道一个比我更好的方法(肯定有很多)。在我的方法中，随着特定键的唯一值的数量增加，素数的乘积也会增加(呈指数级增长)。
最佳答案
您的方法将始终执行 O(n) 来查找组成员，因为您必须遍历集合的所有元素以查找属于目标组的元素。如果您有很多元素，您的方法也有溢出公共(public)整数边界(32 位、64 位)的风险，因为您可能将大量素数相乘以形成 key 。
您会发现按照这种方法使用位掩码来跟踪组成员身份更有效，当然也更可预测。如果您有 16 个组，您可以使用位掩码用 16 位短整型表示。按照您的建议使用素数，您需要一个具有足够位的整数来容纳数字 32589158477190044730(前 16 个素数相乘)，这需要 65 位。
其他分组方法在第一次迭代中也是 O(n)(毕竟，每个元素必须至少测试一次组成员资格)。但是，如果您倾向于重复相同的组检查，您引用的其他方法(例如，为每个目标组保留一个列表或哈希表)会更有效，因为后续的组成员资格测试是 O(1)。
所以直接回答你的问题:
- 如果有多个群组成员资格查询(重复某些群组)，任何存储群组的解决方案(包括您在问题中建议的群组)都会比您的方法执行得更好。
- 如果没有重复查询组成员资格，存储组成员资格就没有优势
鉴于您的问题可能会出现重复查询:
- 如果您想交换内存以获得更快的速度，请使用诸如以组 ID 键控的列表之类的结构来存储组成员。
- 如果您想牺牲速度以使用更少的内存，请使用适当宽度的位数组来存储组成员。
关于sql - 如何在数学上做 "GROUP BY"？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9970976/