How to increase efficiency

I have the following homework question:
Suppose you are given two sequences S1 and S2 of n elements, possibly containing duplicates, on which a total order relation is defined. Describe an efficient algorithm for determining if S1 and S2 contain the same set of elements. Analyze the running time of this method

To solve this question I have compared elemements of the two arrays using retainAll and a HashSet.

Set1.retainAll(new HashSet<Integer>(Set2));

This would solve the problem in constant time.
Do I need to sort the two arrays before the retainAll step to increase efficiency?

asked Nov 25 '18 at 21:33

user9589242

2

Sort order is irrelevant for a hash-based collection.

– chrylis
Nov 25 '18 at 21:35

1

To be honest, I see no algorithm in here so I think this will fail the assignment anyway.

– Antoniossss
Nov 25 '18 at 21:37

1

retainAll if we have two distinct sequences S1 = (1,2,3) and S2 = (1,1,2,3) do you consider them to contain the same set of elements?

– flakes
Nov 25 '18 at 21:41

As always, start by looking at this not as a programming question, but as a puzzle. Let's say I gave you two decks of cards, each with 200 items in it. I ask you whether they contain the same cards. How would you do it? Let's say I gave you two decks of 1000 cards -- what then? The question gives you a clue: you can sort the cards, as long as you tell me how long the sorting will take.

– yshavit
Nov 25 '18 at 22:00

Not always does a single line mean time=1. The HashSet construction needs O(n) and so does retainAll (in general, it needs O(n²), but with the HashSet, it's faster). Moreover, you line produces no result at all. +++ In general, hashing is faster than using order, but you've been given comparable elements. So you're supposed to use the order.

– maaartinus
Nov 26 '18 at 2:10

add a comment |

To solve this question I have compared elemements of the two arrays using retainAll and a HashSet.

Set1.retainAll(new HashSet<Integer>(Set2));

This would solve the problem in constant time.
Do I need to sort the two arrays before the retainAll step to increase efficiency?

asked Nov 25 '18 at 21:33

user9589242

2

Sort order is irrelevant for a hash-based collection.

– chrylis
Nov 25 '18 at 21:35

1

To be honest, I see no algorithm in here so I think this will fail the assignment anyway.

– Antoniossss
Nov 25 '18 at 21:37

1

retainAll if we have two distinct sequences S1 = (1,2,3) and S2 = (1,1,2,3) do you consider them to contain the same set of elements?

– flakes
Nov 25 '18 at 21:41

As always, start by looking at this not as a programming question, but as a puzzle. Let's say I gave you two decks of cards, each with 200 items in it. I ask you whether they contain the same cards. How would you do it? Let's say I gave you two decks of 1000 cards -- what then? The question gives you a clue: you can sort the cards, as long as you tell me how long the sorting will take.

– yshavit
Nov 25 '18 at 22:00

Not always does a single line mean time=1. The HashSet construction needs O(n) and so does retainAll (in general, it needs O(n²), but with the HashSet, it's faster). Moreover, you line produces no result at all. +++ In general, hashing is faster than using order, but you've been given comparable elements. So you're supposed to use the order.

– maaartinus
Nov 26 '18 at 2:10

add a comment |

To solve this question I have compared elemements of the two arrays using retainAll and a HashSet.

Set1.retainAll(new HashSet<Integer>(Set2));

This would solve the problem in constant time.
Do I need to sort the two arrays before the retainAll step to increase efficiency?

asked Nov 25 '18 at 21:33

user9589242

To solve this question I have compared elemements of the two arrays using retainAll and a HashSet.

Set1.retainAll(new HashSet<Integer>(Set2));

This would solve the problem in constant time.
Do I need to sort the two arrays before the retainAll step to increase efficiency?

java performance processing-efficiency coding-efficiency

asked Nov 25 '18 at 21:33

user9589242

asked Nov 25 '18 at 21:33

user9589242

asked Nov 25 '18 at 21:33

user9589242

asked Nov 25 '18 at 21:33

user9589242

asked Nov 25 '18 at 21:33

user9589242

2

Sort order is irrelevant for a hash-based collection.

– chrylis
Nov 25 '18 at 21:35

1

To be honest, I see no algorithm in here so I think this will fail the assignment anyway.

– Antoniossss
Nov 25 '18 at 21:37

1

retainAll if we have two distinct sequences S1 = (1,2,3) and S2 = (1,1,2,3) do you consider them to contain the same set of elements?

– flakes
Nov 25 '18 at 21:41

As always, start by looking at this not as a programming question, but as a puzzle. Let's say I gave you two decks of cards, each with 200 items in it. I ask you whether they contain the same cards. How would you do it? Let's say I gave you two decks of 1000 cards -- what then? The question gives you a clue: you can sort the cards, as long as you tell me how long the sorting will take.

– yshavit
Nov 25 '18 at 22:00

Not always does a single line mean time=1. The HashSet construction needs O(n) and so does retainAll (in general, it needs O(n²), but with the HashSet, it's faster). Moreover, you line produces no result at all. +++ In general, hashing is faster than using order, but you've been given comparable elements. So you're supposed to use the order.

– maaartinus
Nov 26 '18 at 2:10

add a comment |

2

Sort order is irrelevant for a hash-based collection.

– chrylis
Nov 25 '18 at 21:35

1

To be honest, I see no algorithm in here so I think this will fail the assignment anyway.

– Antoniossss
Nov 25 '18 at 21:37

1

retainAll if we have two distinct sequences S1 = (1,2,3) and S2 = (1,1,2,3) do you consider them to contain the same set of elements?

– flakes
Nov 25 '18 at 21:41

As always, start by looking at this not as a programming question, but as a puzzle. Let's say I gave you two decks of cards, each with 200 items in it. I ask you whether they contain the same cards. How would you do it? Let's say I gave you two decks of 1000 cards -- what then? The question gives you a clue: you can sort the cards, as long as you tell me how long the sorting will take.

– yshavit
Nov 25 '18 at 22:00

Not always does a single line mean time=1. The HashSet construction needs O(n) and so does retainAll (in general, it needs O(n²), but with the HashSet, it's faster). Moreover, you line produces no result at all. +++ In general, hashing is faster than using order, but you've been given comparable elements. So you're supposed to use the order.

– maaartinus
Nov 26 '18 at 2:10

Sort order is irrelevant for a hash-based collection.

– chrylis
Nov 25 '18 at 21:35

To be honest, I see no algorithm in here so I think this will fail the assignment anyway.

– Antoniossss
Nov 25 '18 at 21:37

retainAll if we have two distinct sequences S1 = (1,2,3) and S2 = (1,1,2,3) do you consider them to contain the same set of elements?

– flakes
Nov 25 '18 at 21:41

As always, start by looking at this not as a programming question, but as a puzzle. Let's say I gave you two decks of cards, each with 200 items in it. I ask you whether they contain the same cards. How would you do it? Let's say I gave you two decks of 1000 cards -- what then? The question gives you a clue: you can sort the cards, as long as you tell me how long the sorting will take.

– yshavit
Nov 25 '18 at 22:00

Not always does a single line mean time=1. The HashSet construction needs O(n) and so does retainAll (in general, it needs O(n²), but with the HashSet, it's faster). Moreover, you line produces no result at all. +++ In general, hashing is faster than using order, but you've been given comparable elements. So you're supposed to use the order.

– maaartinus
Nov 26 '18 at 2:10

add a comment |

1 Answer
1

active

oldest

votes

I suspect from the code you've posted that you are missing the point of the assignment. The idea is not to use a Java library to check if two collections are equal (for that you could use collection1.equals(collections2). Rather the point is to come up with an algorithm for comparing the collections. The Java API does not specify an algorithm: it's hidden away in the implementation.

Without providing an answer, let me give you an example of an algorithm that would work, but is not necessarily efficient:

for each element in coll1

    if element not in coll2

        return false

    remove element from coll2

return coll2 is empty

The problem specifies that the sequences are ordered (i.e. total order relation is defined) which means you can do much better than the algorithm above.

In general if you are asked to demonstrate an algorithm it's best to stick with native data types and arrays - otherwise the implementation of a library class can significantly impact efficiency and hide the data you want to collect on the algorithm itself.

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

add a comment |

Your Answer

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: "1"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53472232%2fhow-to-increase-efficiency%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

Without providing an answer, let me give you an example of an algorithm that would work, but is not necessarily efficient:

for each element in coll1

    if element not in coll2

        return false

    remove element from coll2

return coll2 is empty

The problem specifies that the sequences are ordered (i.e. total order relation is defined) which means you can do much better than the algorithm above.

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

add a comment |

Without providing an answer, let me give you an example of an algorithm that would work, but is not necessarily efficient:

for each element in coll1

    if element not in coll2

        return false

    remove element from coll2

return coll2 is empty

The problem specifies that the sequences are ordered (i.e. total order relation is defined) which means you can do much better than the algorithm above.

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

add a comment |

Without providing an answer, let me give you an example of an algorithm that would work, but is not necessarily efficient:

for each element in coll1

    if element not in coll2

        return false

    remove element from coll2

return coll2 is empty

The problem specifies that the sequences are ordered (i.e. total order relation is defined) which means you can do much better than the algorithm above.

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

Without providing an answer, let me give you an example of an algorithm that would work, but is not necessarily efficient:

for each element in coll1

    if element not in coll2

        return false

    remove element from coll2

return coll2 is empty

The problem specifies that the sequences are ordered (i.e. total order relation is defined) which means you can do much better than the algorithm above.

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

answered Nov 25 '18 at 22:01

sprinter

16.8k32961

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

add a comment |

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

Thanks to everyone for their input, this is my new solution 1) Use two index variables i and j, set their initial values to 0 2) If S1[i] is less then than S2[j] the algorithm increments i. 3) If S1[i] is greater than S2[j] the algorithm increments j. 4) If both are same then print either one of them and the algorithm increments both I and j. I'm not sure how to avoid duplicates and make this more efficient. I think the algorithm takes O(m +n) time

– user9589242
Nov 25 '18 at 23:46

@user9589242 If the two elements aren't equal you don't need to increment either index: at that point you know the sets don't contain the same elements. Also note that this assumes the sets are sorted first. Just because there exists an order relation doesn't mean it's been applied.

– sprinter
Nov 26 '18 at 0:23

Thank you sprinter it makes sense now :)

– user9589242
Nov 26 '18 at 3:12

@user9589242 Please accept the answer if it resolved your issue

– sprinter
Nov 27 '18 at 4:06

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

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.

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');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Ytukyg