Count pairs in list of integers such that their addition is equal to the input value
0
$begingroup$
Given a List<int>, the problem I am trying to solve is:
Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.
The bottleneck is a nested for() loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
edited 4 mins ago
200_success
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon 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 |
0
$begingroup$
Given a List<int>, the problem I am trying to solve is:
Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.
The bottleneck is a nested for() loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
edited 4 mins ago
200_success
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1and the input value is2, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago
add a comment |
0
0
0
$begingroup$
Given a List<int>, the problem I am trying to solve is:
Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.
The bottleneck is a nested for() loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
edited 4 mins ago
200_success
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given a List<int>, the problem I am trying to solve is:
Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.
The bottleneck is a nested for() loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
c# performance k-sum
edited 4 mins ago
200_success
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 mins ago
200_success
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 mins ago
200_success
129k15153415
edited 4 mins ago
200_success
129k15153415
edited 4 mins ago
200_success
129k15153415
129k15153415
asked 56 mins ago
silverspoonsilverspoon
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 56 mins ago
silverspoonsilverspoon
101
asked 56 mins ago
silverspoonsilverspoon
101
101
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
silverspoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1and the input value is2, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago
add a comment |
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1and the input value is2, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago
1
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1 and the input value is 2, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1 and the input value is 2, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago
add a comment |
0
active
oldest
votes
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
});
}
});
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
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%2f212818%2fcount-pairs-in-list-of-integers-such-that-their-addition-is-equal-to-the-input-v%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
silverspoon 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.
draft saved
draft discarded
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%2f212818%2fcount-pairs-in-list-of-integers-such-that-their-addition-is-equal-to-the-input-v%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
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1and the input value is2, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
49 mins ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
6 mins ago