在我的Python项目中,我有一个员工映射。键是“员工编号”,值是一个带有“员工信息”的对象,而值中的“位置”字段是“唯一”的,例如:
现在我想建立一个名为mapC的映射,将“员工编号”和“对象S”之间进行关联。
我必须在mapA对象中找到位置,然后获取指向该对象的键。然后使用此键和mapB中的objectS构建新的mapC。通过这种方式,时间复杂度为O(N^2)。
为了降低时间复杂度,首先我通过遍历mapA构建了一个键为“位置”、值为“员工编号”的mapD,然后可以轻松地获得mapC。
还有更好的解决方案吗?
另外,我想到了另一个问题:数据库中主键和外键的最佳数据结构是什么?
例如,这里有一张表:
mapA = {12: {name: 'John Ma', location: 'US'}, 25: {name: 'Richard Yan', location: 'Eng'}, ...}
还有另一个地图,键是 location
,值是另一个包含其他内容的对象。例如,
mapB = {'US': objectS1, 'Eng': objectS2, ...}
现在我想建立一个名为mapC的映射,将“员工编号”和“对象S”之间进行关联。
mapC = {12: objectS1, 25: objectS2 ...}
我必须在mapA对象中找到位置,然后获取指向该对象的键。然后使用此键和mapB中的objectS构建新的mapC。通过这种方式,时间复杂度为O(N^2)。
为了降低时间复杂度,首先我通过遍历mapA构建了一个键为“位置”、值为“员工编号”的mapD,然后可以轻松地获得mapC。
还有更好的解决方案吗?
另外,我想到了另一个问题:数据库中主键和外键的最佳数据结构是什么?
例如,这里有一张表:
| Username | Password | Email_Addr |
--------------------------------------
| Username1 | Password1 | Email 1 |
| Username2 | Password2 | Email 2 |
| Username3 | Password1 | Email 3 |
如果username
是第一主键,Password
是次要键,那么最好的数据结构是什么,以获得最佳性能?
我认为,为了简单起见,将用户名和密码合并为一个复合键。然后,我们按照以下比较函数对这些记录进行排序:
bool key_compare(string key1, string key2){
return key1+key2 > key2+key1;
}
这些信息存储在B_tree中。
编辑2
从这份文件得知,这两个索引可以用哈希表和倒排表实现。在上面的表格中,
哈希表保存用户名
和每个记录的地址,
{用户名1:'记录1地址',用户名2:'记录2地址'}
倒排表保存密码
和记录地址表的信息。
{密码1:['记录1地址','记录3地址'],密码2:['记录2地址']}
编辑1 我想了解数据库如何处理它们,例如MySQL... 除了B_tree之外还有什么哈希图?谢谢提前。
a_has_b
的表作为复合键集合是一个不错的解决方案。 - keenthinker