我正试图找到按类别分组的最佳方法，并在O(n(中迭代产品，以从类别中获得一些见解。
我有样本数据：
[
{
"code": 25754,
"description": "ADAPTADOR BLUETOOH USB RECEPTOR DE AUDIO P2",
"price": 5.0,
"stock": 10,
"category": {
"id": 1,
"name": "Adapters"
}
},
{
"code": 20212,
"description": "ADAPTADOR CONECTOR HDMI FEMEA L / FEMEA",
"price": 2.8,
"stock": 20,
"category": {
"id": 2,
"name": "Eletronics"
}
},
]
我需要颠倒关系，有一个相应产品的类别列表，为此我写了这个解决方案
function group_by_categories(products) {
const categories = {}
for (const product of products) {
const { category, ...cleanedProduct } = product
categories[category.id] = categories[category.id] || category
categories[category.id].products = categories[category.id].products || []
categories[category.id].products.push(cleanedProduct)
}
return Object.values(categories)
}
// returns
[
{ id: 1, name: 'Adapters', products: [ [Object] ] },
{ id: 2, name: 'Eletronics', products: [ [Object] ] }
]
但我在两件事上挣扎。
这是扭转关系的最佳方式吗？我如何在另一种语言(如C(中复制这一点，因为我没有对象可以用作唯一键？
一旦您有了这种类型的数据，迭代类别和产品的唯一方法(例如，查看一个类别有多少项(是O(n²(？
我感谢所有的帮助，即使你只能回答一个问题。另外，很抱歉我的英语不好，我在这里尽量讲清楚。
所以您有3个问题。1( 使用代码/id作为键，2(使用集合而不是数组，3(使用适当的数据结构以避免重复您已经完成的工作。
- 你真的只是想映射连接，而不是所有的数据。我相信代码可能是产品独有的，所以这是您的关键。您的类别id也可能是唯一的，所以您只需要考虑这一点。映射结构应该只关注最少量的唯一数据。这可能会大大提高性能，而且复制的数据量可能是您的1/10到1/100(当然，很难将其准确转化为节省的时间(。当然，与O(N^2(性能相比，这只是一个小问题，但仅凭这一点就可能使速度加快一点
- 您应该使用集合以及散列(对象(。这里的想法是
O(1)查找、O(1)大小检查、O(1)包含测试(IE：类别X中是否有代码Y？(，以及O(1)映射回原始数据(代码Y是包含此信息的产品(
另一个关键是你真的只想映射连接，而不是所有的数据。我相信代码可能是产品独有的，所以这是您的关键。您的类别映射结构应该只关注最少量的唯一数据(这也会大大提高性能(。
请记住，如果您可以访问实际的数据库，这可能是更理想的解决方案，那么在95%左右的时间里，一旦您开始想要进行更复杂的查询。我想说，你几乎肯定应该使用一个，可能有一个数据库可以满足你的需求。
话虽如此，如果你不需要太多的查询，你需要的就是这个。看起来你需要回答以下三个问题：
- 给定代码，记录(示例数据(是什么？这只是一个简单的
code:product对象。即：{25754: {code: ..., price: ..., stock: ..., ...}, {20212: {code: ..., price: ..., stock: ..., ...}} - 给定一个类别，该类别中的代码是什么？在这种情况下，您有一个
category_id:set(codes)查找。将代码添加到集合而不是列表/数组非常重要。集合具有要添加/删除/包含的O(1)，而列表/数组具有O(1)添加、O(N)删除和O(N)包含检查 - 给定一个类别，有多少属于该类别？这只是一个
data[category].size检查(在某些语言中是长度而不是大小(
主要是使用字典和集合来提高性能。
建立查找的时间可能是O(P)，其中P是乘积的总数。对于您需要执行的每个查询，查询的性能应该是O(1)
为了避免O(N^2)性能，查找应该只计算一次。如果需要从类别中添加/删除产品，则应调整查找本身，而不是每次都重新生成。这可能意味着将其存储在数据库中，在首次运行应用程序时构建并将其保存在内存中，或者如果产品数量不多，则根据每个请求构建(只使用最少量的数据来构建，可能更实用(。一般来说，即使有1000个产品，构建类别查找并对其进行迭代也可能需要几毫秒的时间。
基本上，在你写出方法之后，你的类别代码应该看起来像他的。
...
category_lookup = build_category_lookup() # O(P)
product_lookup = build_product_lookup() # O(P)
...
products_for_category = product_lookup[category_id] # O(1)
products_count = products_for_category.length # O(1) | C: sizeof(products_for_category)
...
(现在大部分代码都是用ruby编写的，所以snake_case(