Efficiently aggregating nested data
$begingroup$
Problem
Given the following data:
[
{
"users": [
{
"id": "07bde76f-aff0-407d-9241-a12b323d4af8",
"transactions": [
{
"category": "purchase"
},
{
"category": "unknown"
}
]
},
{
"id": "40aa040f-7961-4e06-a31b-32052be67fcc",
"transactions": [
{
"category": "sale"
},
{
"category": "unknown"
}
]
}
],
"groups": [
{
"id": "00c61181-b133-4be9-9d44-dc3c224b3beb",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
},
{
"id": "eb959ff1-da1d-41e5-b5b7-45fef3dbc2df",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
}
]
},
{
"users": [
{
"id": "af095f1c-fe43-43fb-9571-dabe2dd56bcf",
"transactions": [
{
"category": "bill"
}
]
}
],
"groups": [
{
"id": "c5bafe16-c5ec-428e-8c7c-30cbd9963750",
"transactions": [
{
"category": "fee"
},
{
"category": "cash"
}
]
}
]
}
]
... I want to produce the following output:
{
"groups_atm": 2,
"groups_fee": 1,
"groups_cash": 3,
"users_purchase": 1,
"users_unknown": 2,
"users_bill": 1,
"users_sale": 1
}
Implementation
I've approached this by first mapping over transactions and summing their occurrences:
const sum = (transactions) =>
transactions.map((transaction) => transaction.category).reduce((acc, transactionCategory) => {
return {
...acc,
[transactionCategory]: (acc[transactionCategory] || 0) + 1,
};
}, tally);
... then aggregating by scope ("user", "group") per element of the data list and merge the counts by category:
const aggregate = (datum, tally) =>
['user', 'group'].reduce((acc, scope) => {
const aggregates = datum[`${scope}s`].reduce(
(agg, data) => sum(agg, data.transactions),
{},
);
return {
...acc,
[scope]: acc[scope] ? merge(acc[scope], aggregates) : aggregates,
};
}, tally);
const difference = (arrA, arrB) => arrA.filter((x) => !arrB.includes(x));
const intersection = (arrA, arrB) => arrA.filter((x) => arrB.includes(x));
const merge = (objA, objB) => {
const acc = {};
const aKeys = Object.keys(objA);
const bKeys = Object.keys(objB);
intersection(aKeys, bKeys).forEach((key) => (acc[key] = objA[key] + objB[key]));
difference(aKeys, bKeys).forEach((key) => (acc[key] = objA[key]));
difference(bKeys, aKeys).forEach((key) => (acc[key] = objB[key]));
return acc;
};
... then re-reducing over the whole dataset:
const aggregates = data.reduce((acc, datum) => aggregateScope(datum, acc), {});
... and finally reformatting the aggregates to match the expected output:
const format = (aggregates) =>
Object.keys(aggregates).reduce((acc, scope) => {
Object.keys(aggregates[scope]).forEach((category) => {
acc[`${scope}_${category}`] = aggregates[scope][category];
});
return acc;
}, {});
Questions
- what are alternative ways of breaking down the problem?
- what is it's Big O complexity? Can it be reduced?
- can
mergebe avoided? - are there language features (JS/ES6) that can make this more idiomatic?
- is "aggregation" the correct terminology?
javascript mapreduce
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Problem
Given the following data:
[
{
"users": [
{
"id": "07bde76f-aff0-407d-9241-a12b323d4af8",
"transactions": [
{
"category": "purchase"
},
{
"category": "unknown"
}
]
},
{
"id": "40aa040f-7961-4e06-a31b-32052be67fcc",
"transactions": [
{
"category": "sale"
},
{
"category": "unknown"
}
]
}
],
"groups": [
{
"id": "00c61181-b133-4be9-9d44-dc3c224b3beb",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
},
{
"id": "eb959ff1-da1d-41e5-b5b7-45fef3dbc2df",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
}
]
},
{
"users": [
{
"id": "af095f1c-fe43-43fb-9571-dabe2dd56bcf",
"transactions": [
{
"category": "bill"
}
]
}
],
"groups": [
{
"id": "c5bafe16-c5ec-428e-8c7c-30cbd9963750",
"transactions": [
{
"category": "fee"
},
{
"category": "cash"
}
]
}
]
}
]
... I want to produce the following output:
{
"groups_atm": 2,
"groups_fee": 1,
"groups_cash": 3,
"users_purchase": 1,
"users_unknown": 2,
"users_bill": 1,
"users_sale": 1
}
Implementation
I've approached this by first mapping over transactions and summing their occurrences:
const sum = (transactions) =>
transactions.map((transaction) => transaction.category).reduce((acc, transactionCategory) => {
return {
...acc,
[transactionCategory]: (acc[transactionCategory] || 0) + 1,
};
}, tally);
... then aggregating by scope ("user", "group") per element of the data list and merge the counts by category:
const aggregate = (datum, tally) =>
['user', 'group'].reduce((acc, scope) => {
const aggregates = datum[`${scope}s`].reduce(
(agg, data) => sum(agg, data.transactions),
{},
);
return {
...acc,
[scope]: acc[scope] ? merge(acc[scope], aggregates) : aggregates,
};
}, tally);
const difference = (arrA, arrB) => arrA.filter((x) => !arrB.includes(x));
const intersection = (arrA, arrB) => arrA.filter((x) => arrB.includes(x));
const merge = (objA, objB) => {
const acc = {};
const aKeys = Object.keys(objA);
const bKeys = Object.keys(objB);
intersection(aKeys, bKeys).forEach((key) => (acc[key] = objA[key] + objB[key]));
difference(aKeys, bKeys).forEach((key) => (acc[key] = objA[key]));
difference(bKeys, aKeys).forEach((key) => (acc[key] = objB[key]));
return acc;
};
... then re-reducing over the whole dataset:
const aggregates = data.reduce((acc, datum) => aggregateScope(datum, acc), {});
... and finally reformatting the aggregates to match the expected output:
const format = (aggregates) =>
Object.keys(aggregates).reduce((acc, scope) => {
Object.keys(aggregates[scope]).forEach((category) => {
acc[`${scope}_${category}`] = aggregates[scope][category];
});
return acc;
}, {});
Questions
- what are alternative ways of breaking down the problem?
- what is it's Big O complexity? Can it be reduced?
- can
mergebe avoided? - are there language features (JS/ES6) that can make this more idiomatic?
- is "aggregation" the correct terminology?
javascript mapreduce
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Problem
Given the following data:
[
{
"users": [
{
"id": "07bde76f-aff0-407d-9241-a12b323d4af8",
"transactions": [
{
"category": "purchase"
},
{
"category": "unknown"
}
]
},
{
"id": "40aa040f-7961-4e06-a31b-32052be67fcc",
"transactions": [
{
"category": "sale"
},
{
"category": "unknown"
}
]
}
],
"groups": [
{
"id": "00c61181-b133-4be9-9d44-dc3c224b3beb",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
},
{
"id": "eb959ff1-da1d-41e5-b5b7-45fef3dbc2df",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
}
]
},
{
"users": [
{
"id": "af095f1c-fe43-43fb-9571-dabe2dd56bcf",
"transactions": [
{
"category": "bill"
}
]
}
],
"groups": [
{
"id": "c5bafe16-c5ec-428e-8c7c-30cbd9963750",
"transactions": [
{
"category": "fee"
},
{
"category": "cash"
}
]
}
]
}
]
... I want to produce the following output:
{
"groups_atm": 2,
"groups_fee": 1,
"groups_cash": 3,
"users_purchase": 1,
"users_unknown": 2,
"users_bill": 1,
"users_sale": 1
}
Implementation
I've approached this by first mapping over transactions and summing their occurrences:
const sum = (transactions) =>
transactions.map((transaction) => transaction.category).reduce((acc, transactionCategory) => {
return {
...acc,
[transactionCategory]: (acc[transactionCategory] || 0) + 1,
};
}, tally);
... then aggregating by scope ("user", "group") per element of the data list and merge the counts by category:
const aggregate = (datum, tally) =>
['user', 'group'].reduce((acc, scope) => {
const aggregates = datum[`${scope}s`].reduce(
(agg, data) => sum(agg, data.transactions),
{},
);
return {
...acc,
[scope]: acc[scope] ? merge(acc[scope], aggregates) : aggregates,
};
}, tally);
const difference = (arrA, arrB) => arrA.filter((x) => !arrB.includes(x));
const intersection = (arrA, arrB) => arrA.filter((x) => arrB.includes(x));
const merge = (objA, objB) => {
const acc = {};
const aKeys = Object.keys(objA);
const bKeys = Object.keys(objB);
intersection(aKeys, bKeys).forEach((key) => (acc[key] = objA[key] + objB[key]));
difference(aKeys, bKeys).forEach((key) => (acc[key] = objA[key]));
difference(bKeys, aKeys).forEach((key) => (acc[key] = objB[key]));
return acc;
};
... then re-reducing over the whole dataset:
const aggregates = data.reduce((acc, datum) => aggregateScope(datum, acc), {});
... and finally reformatting the aggregates to match the expected output:
const format = (aggregates) =>
Object.keys(aggregates).reduce((acc, scope) => {
Object.keys(aggregates[scope]).forEach((category) => {
acc[`${scope}_${category}`] = aggregates[scope][category];
});
return acc;
}, {});
Questions
- what are alternative ways of breaking down the problem?
- what is it's Big O complexity? Can it be reduced?
- can
mergebe avoided? - are there language features (JS/ES6) that can make this more idiomatic?
- is "aggregation" the correct terminology?
javascript mapreduce
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Problem
Given the following data:
[
{
"users": [
{
"id": "07bde76f-aff0-407d-9241-a12b323d4af8",
"transactions": [
{
"category": "purchase"
},
{
"category": "unknown"
}
]
},
{
"id": "40aa040f-7961-4e06-a31b-32052be67fcc",
"transactions": [
{
"category": "sale"
},
{
"category": "unknown"
}
]
}
],
"groups": [
{
"id": "00c61181-b133-4be9-9d44-dc3c224b3beb",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
},
{
"id": "eb959ff1-da1d-41e5-b5b7-45fef3dbc2df",
"transactions": [
{
"category": "atm"
},
{
"category": "cash"
}
]
}
]
},
{
"users": [
{
"id": "af095f1c-fe43-43fb-9571-dabe2dd56bcf",
"transactions": [
{
"category": "bill"
}
]
}
],
"groups": [
{
"id": "c5bafe16-c5ec-428e-8c7c-30cbd9963750",
"transactions": [
{
"category": "fee"
},
{
"category": "cash"
}
]
}
]
}
]
... I want to produce the following output:
{
"groups_atm": 2,
"groups_fee": 1,
"groups_cash": 3,
"users_purchase": 1,
"users_unknown": 2,
"users_bill": 1,
"users_sale": 1
}
Implementation
I've approached this by first mapping over transactions and summing their occurrences:
const sum = (transactions) =>
transactions.map((transaction) => transaction.category).reduce((acc, transactionCategory) => {
return {
...acc,
[transactionCategory]: (acc[transactionCategory] || 0) + 1,
};
}, tally);
... then aggregating by scope ("user", "group") per element of the data list and merge the counts by category:
const aggregate = (datum, tally) =>
['user', 'group'].reduce((acc, scope) => {
const aggregates = datum[`${scope}s`].reduce(
(agg, data) => sum(agg, data.transactions),
{},
);
return {
...acc,
[scope]: acc[scope] ? merge(acc[scope], aggregates) : aggregates,
};
}, tally);
const difference = (arrA, arrB) => arrA.filter((x) => !arrB.includes(x));
const intersection = (arrA, arrB) => arrA.filter((x) => arrB.includes(x));
const merge = (objA, objB) => {
const acc = {};
const aKeys = Object.keys(objA);
const bKeys = Object.keys(objB);
intersection(aKeys, bKeys).forEach((key) => (acc[key] = objA[key] + objB[key]));
difference(aKeys, bKeys).forEach((key) => (acc[key] = objA[key]));
difference(bKeys, aKeys).forEach((key) => (acc[key] = objB[key]));
return acc;
};
... then re-reducing over the whole dataset:
const aggregates = data.reduce((acc, datum) => aggregateScope(datum, acc), {});
... and finally reformatting the aggregates to match the expected output:
const format = (aggregates) =>
Object.keys(aggregates).reduce((acc, scope) => {
Object.keys(aggregates[scope]).forEach((category) => {
acc[`${scope}_${category}`] = aggregates[scope][category];
});
return acc;
}, {});
Questions
- what are alternative ways of breaking down the problem?
- what is it's Big O complexity? Can it be reduced?
- can
mergebe avoided? - are there language features (JS/ES6) that can make this more idiomatic?
- is "aggregation" the correct terminology?
javascript mapreduce
javascript mapreduce
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 15 hours ago
Dominic Campos
asked 15 hours ago
Dominic CamposDominic Campos
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 hours ago
Dominic CamposDominic Campos
63
asked 15 hours ago
Dominic CamposDominic Campos
63
63
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Dominic Campos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Way way too complex
One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.
The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.
I could not make a good assessment due to its complexity and bugs.
Your code does not run.
- The name
aggregateScopeinaggregatesshould beaggregate
sumthrowsTypeError map is not a function
Patching those problems it still did not run.
The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.
Questions.
You have some questions.
what are alternative ways of breaking down the problem?
Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)
what is it's Big O complexity?
I am guessing its It more than $O(n)$ and less than or equal to $O(n^2)$ where $n$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.
I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big $O(n^3)$ for the given dataset of 11 category items
Can it be reduced?
Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).
are there language features (JS/ES6) that can make this more idiomatic?
- Use
for ofloops to iterate. - Use bracket notations to create named properties.
- Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
- No more than one iterator per line. You quickly lose track of how complex it gets.
Is all that comes to mind, that and K.I.S.S.
An alternative example solution
I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal $O(n)$ solution.
function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>answered 11 hours ago
Blindman67Blindman67
7,2761521
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Dominic Campos is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211616%2fefficiently-aggregating-nested-data%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Way way too complex
One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.
The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.
I could not make a good assessment due to its complexity and bugs.
Your code does not run.
- The name
aggregateScopeinaggregatesshould beaggregate
sumthrowsTypeError map is not a function
Patching those problems it still did not run.
The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.
Questions.
You have some questions.
what are alternative ways of breaking down the problem?
Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)
what is it's Big O complexity?
I am guessing its It more than $O(n)$ and less than or equal to $O(n^2)$ where $n$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.
I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big $O(n^3)$ for the given dataset of 11 category items
Can it be reduced?
Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).
are there language features (JS/ES6) that can make this more idiomatic?
- Use
for ofloops to iterate. - Use bracket notations to create named properties.
- Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
- No more than one iterator per line. You quickly lose track of how complex it gets.
Is all that comes to mind, that and K.I.S.S.
An alternative example solution
I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal $O(n)$ solution.
function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>answered 11 hours ago
Blindman67Blindman67
7,2761521
$endgroup$
add a comment |
$begingroup$
Way way too complex
One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.
The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.
I could not make a good assessment due to its complexity and bugs.
Your code does not run.
- The name
aggregateScopeinaggregatesshould beaggregate
sumthrowsTypeError map is not a function
Patching those problems it still did not run.
The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.
Questions.
You have some questions.
what are alternative ways of breaking down the problem?
Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)
what is it's Big O complexity?
I am guessing its It more than $O(n)$ and less than or equal to $O(n^2)$ where $n$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.
I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big $O(n^3)$ for the given dataset of 11 category items
Can it be reduced?
Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).
are there language features (JS/ES6) that can make this more idiomatic?
- Use
for ofloops to iterate. - Use bracket notations to create named properties.
- Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
- No more than one iterator per line. You quickly lose track of how complex it gets.
Is all that comes to mind, that and K.I.S.S.
An alternative example solution
I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal $O(n)$ solution.
function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>answered 11 hours ago
Blindman67Blindman67
7,2761521
$endgroup$
add a comment |
$begingroup$
Way way too complex
One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.
The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.
I could not make a good assessment due to its complexity and bugs.
Your code does not run.
- The name
aggregateScopeinaggregatesshould beaggregate
sumthrowsTypeError map is not a function
Patching those problems it still did not run.
The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.
Questions.
You have some questions.
what are alternative ways of breaking down the problem?
Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)
what is it's Big O complexity?
I am guessing its It more than $O(n)$ and less than or equal to $O(n^2)$ where $n$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.
I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big $O(n^3)$ for the given dataset of 11 category items
Can it be reduced?
Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).
are there language features (JS/ES6) that can make this more idiomatic?
- Use
for ofloops to iterate. - Use bracket notations to create named properties.
- Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
- No more than one iterator per line. You quickly lose track of how complex it gets.
Is all that comes to mind, that and K.I.S.S.
An alternative example solution
I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal $O(n)$ solution.
function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>answered 11 hours ago
Blindman67Blindman67
7,2761521
$endgroup$
Way way too complex
One way to help workout how to solve a problem is to solve it in your head (or on paper) first. That way you know the problem from the top to the bottom. Then use that approach in your script.
The code looks like you started at the top with no clear idea of the solution, and solve many separate problems as you encountered them. The result is unreadable and way to complex.
I could not make a good assessment due to its complexity and bugs.
Your code does not run.
- The name
aggregateScopeinaggregatesshould beaggregate
sumthrowsTypeError map is not a function
Patching those problems it still did not run.
The hell of a zillion iterators is not easy to traverse so I stopped trying to work it out at that point.
Questions.
You have some questions.
what are alternative ways of breaking down the problem?
Its just a set of nested arrays and named objects. The names are fixed, so its just a process of stepping over each array in turn storing the counts in a named map (see example)
what is it's Big O complexity?
I am guessing its It more than $O(n)$ and less than or equal to $O(n^2)$ where $n$ is the number of category items. As there is only a small sample dataset and the code does not work I can not give a accurate evaluation.
I did count 18 different iteration function calls throughout your code. With 2 or 7 iterations each, nested to about 6 levels. If I use that and average (2 + 7) / 2 = 4.5 per iterator then its 4.56 approx steps, so that's a big $O(n^3)$ for the given dataset of 11 category items
Can it be reduced?
Yes, it can be O(n) as there is no need to search, and no need to compare items (see example).
are there language features (JS/ES6) that can make this more idiomatic?
- Use
for ofloops to iterate. - Use bracket notations to create named properties.
- Keep your functions ordered. From bottom to top, it makes it easier to locate functions and follow the code.
- No more than one iterator per line. You quickly lose track of how complex it gets.
Is all that comes to mind, that and K.I.S.S.
An alternative example solution
I am not that conventional when it comes to code, so not quite idiomatic. less is good in my book and helps find the optimal $O(n)$ solution.
function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>function aggregateTransactionCategories(data, types) {
const result = {};
const mapCategories = (type, transactions) => {
for (const cats of transactions) {
const name = type + "_" + cats.category;
result[name] = result[name] ? result[name] + 1 : 1;
}
}
for (const type of types) {
for (const entries of data) {
for (const entry of entries[type]) {
mapCategories(type, entry.transactions);
}
}
}
return result;
}
setTimeout(() =>
log(aggregateTransactionCategories( data, ["groups", "users"]))
,0
);
const data = [{
users: [
{ id: "07bd", transactions: [{category: "purchase"}, {category: "unknown"}] },
{ id: "40aa", transactions: [{category: "sale"}, {category: "unknown"}] }
],
groups: [
{ id: "00c6", transactions: [{category: "atm"}, {category: "cash"}] },
{ id: "eb95", transactions: [{category: "atm"}, {category: "cash"}] }
]
}, {
users: [
{ id: "af09", transactions: [{category: "bill"}] }
],
groups: [
{ id: "c5ba", transactions: [{category: "fee"}, {category: "cash"}] }
]
}
];
//Just displays the result and not related to the problem
function log(data) {
for(const [name, value] of Object.entries(data)) {
displayResult.appendChild(Object.assign(
document.createElement("div"),{
textContent : name + ": " + value + ","
}
))
}
}<code id="displayResult"></code>answered 11 hours ago
Blindman67Blindman67
7,2761521
answered 11 hours ago
Blindman67Blindman67
7,2761521
answered 11 hours ago
Blindman67Blindman67
7,2761521
answered 11 hours ago
Blindman67Blindman67
7,2761521
7,2761521
add a comment |
add a comment |
Dominic Campos is a new contributor. Be nice, and check out our Code of Conduct.
Dominic Campos is a new contributor. Be nice, and check out our Code of Conduct.
Dominic Campos is a new contributor. Be nice, and check out our Code of Conduct.
Dominic Campos is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211616%2fefficiently-aggregating-nested-data%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
