Index matching algorithm without hash-based data structures?
$begingroup$
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.
Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.
For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.
Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.
So my question is whether there is a linear algorithm for this task that does not use any hashsets.
search-algorithms hash-tables permutations
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft 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$
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.
Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.
For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.
Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.
So my question is whether there is a linear algorithm for this task that does not use any hashsets.
search-algorithms hash-tables permutations
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft 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$
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.
Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.
For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.
Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.
So my question is whether there is a linear algorithm for this task that does not use any hashsets.
search-algorithms hash-tables permutations
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.
Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.
For example, if $a=[9,4,3,7]$ and $b=[3,4,7,9]$, then the output should be $[3,1,0,2]$.
Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.
So my question is whether there is a linear algorithm for this task that does not use any hashsets.
search-algorithms hash-tables permutations
search-algorithms hash-tables permutations
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
SmileyCraftSmileyCraft
1261
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
SmileyCraftSmileyCraft
1261
asked 5 hours ago
SmileyCraftSmileyCraft
1261
1261
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
SmileyCraft is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
SmileyCraft 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$
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $Theta(nlog n)$ time in worst case for any algorithm. This can be seen in the case when array $a$ is sorted while array $b$ is not. Then knowing the index $I(k)$ of the same element in $b$ for the $k$-th element of $a$ for all $k$, we can sort $b$ in linear time by putting $b_{I(k)}$ in $k$-th position.
The following is a formal formulation of the conclusion above in the comparison computation model.
Let $mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,fin E$, $mathcal O$ outputs -1 if $eprec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from ${0, 1,cdots, n-1}$ to $E$. To output $I(0), I(1), cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0le kle n-1$, it will take $Theta(nlog n)$ queries against $mathcal O$ in the worst case.
whether there is a linear algorithm for this task that does not use any hashsets.
A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
answered 2 hours ago
Apass.JackApass.Jack
13k1939
$endgroup$
$begingroup$
I don't think OP is asking for an ordering of the elements ofa. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).
$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
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.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
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
});
}
});
SmileyCraft 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%2fcs.stackexchange.com%2fquestions%2f105808%2findex-matching-algorithm-without-hash-based-data-structures%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$
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $Theta(nlog n)$ time in worst case for any algorithm. This can be seen in the case when array $a$ is sorted while array $b$ is not. Then knowing the index $I(k)$ of the same element in $b$ for the $k$-th element of $a$ for all $k$, we can sort $b$ in linear time by putting $b_{I(k)}$ in $k$-th position.
The following is a formal formulation of the conclusion above in the comparison computation model.
Let $mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,fin E$, $mathcal O$ outputs -1 if $eprec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from ${0, 1,cdots, n-1}$ to $E$. To output $I(0), I(1), cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0le kle n-1$, it will take $Theta(nlog n)$ queries against $mathcal O$ in the worst case.
whether there is a linear algorithm for this task that does not use any hashsets.
A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
answered 2 hours ago
Apass.JackApass.Jack
13k1939
$endgroup$
$begingroup$
I don't think OP is asking for an ordering of the elements ofa. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).
$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
add a comment |
$begingroup$
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $Theta(nlog n)$ time in worst case for any algorithm. This can be seen in the case when array $a$ is sorted while array $b$ is not. Then knowing the index $I(k)$ of the same element in $b$ for the $k$-th element of $a$ for all $k$, we can sort $b$ in linear time by putting $b_{I(k)}$ in $k$-th position.
The following is a formal formulation of the conclusion above in the comparison computation model.
Let $mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,fin E$, $mathcal O$ outputs -1 if $eprec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from ${0, 1,cdots, n-1}$ to $E$. To output $I(0), I(1), cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0le kle n-1$, it will take $Theta(nlog n)$ queries against $mathcal O$ in the worst case.
whether there is a linear algorithm for this task that does not use any hashsets.
A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
answered 2 hours ago
Apass.JackApass.Jack
13k1939
$endgroup$
$begingroup$
I don't think OP is asking for an ordering of the elements ofa. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).
$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
add a comment |
$begingroup$
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $Theta(nlog n)$ time in worst case for any algorithm. This can be seen in the case when array $a$ is sorted while array $b$ is not. Then knowing the index $I(k)$ of the same element in $b$ for the $k$-th element of $a$ for all $k$, we can sort $b$ in linear time by putting $b_{I(k)}$ in $k$-th position.
The following is a formal formulation of the conclusion above in the comparison computation model.
Let $mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,fin E$, $mathcal O$ outputs -1 if $eprec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from ${0, 1,cdots, n-1}$ to $E$. To output $I(0), I(1), cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0le kle n-1$, it will take $Theta(nlog n)$ queries against $mathcal O$ in the worst case.
whether there is a linear algorithm for this task that does not use any hashsets.
A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
answered 2 hours ago
Apass.JackApass.Jack
13k1939
$endgroup$
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $Theta(nlog n)$ time in worst case for any algorithm. This can be seen in the case when array $a$ is sorted while array $b$ is not. Then knowing the index $I(k)$ of the same element in $b$ for the $k$-th element of $a$ for all $k$, we can sort $b$ in linear time by putting $b_{I(k)}$ in $k$-th position.
The following is a formal formulation of the conclusion above in the comparison computation model.
Let $mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,fin E$, $mathcal O$ outputs -1 if $eprec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from ${0, 1,cdots, n-1}$ to $E$. To output $I(0), I(1), cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0le kle n-1$, it will take $Theta(nlog n)$ queries against $mathcal O$ in the worst case.
whether there is a linear algorithm for this task that does not use any hashsets.
A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
answered 2 hours ago
Apass.JackApass.Jack
13k1939
edited 1 hour ago
answered 2 hours ago
Apass.JackApass.Jack
13k1939
answered 2 hours ago
Apass.JackApass.Jack
13k1939
answered 2 hours ago
Apass.JackApass.Jack
13k1939
13k1939
$begingroup$
I don't think OP is asking for an ordering of the elements ofa. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).
$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
add a comment |
$begingroup$
I don't think OP is asking for an ordering of the elements ofa. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).
$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
$begingroup$
I don't think OP is asking for an ordering of the elements of
a. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).$endgroup$
– smac89
1 hour ago
$begingroup$
I don't think OP is asking for an ordering of the elements of
a. It sounds more like he is asking for a mapping i.e. map element of a to it's position in b; not order elements of a according to their position in b. Ordering will require O(nlogn) as you have astutely observed, but mapping can be done in O(n).$endgroup$
– smac89
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
Exactly, I don't think OP is asking for an ordering of the element of $a$. Please read my answer carefully, especially the formal formulation. Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
$begingroup$
This answer abstracts "distinct integers" as "distinct elements" with a strict total order. There could be other computation models for "distinct integers" without "hashset".
$endgroup$
– Apass.Jack
58 mins ago
add a comment |
SmileyCraft is a new contributor. Be nice, and check out our Code of Conduct.
SmileyCraft is a new contributor. Be nice, and check out our Code of Conduct.
SmileyCraft is a new contributor. Be nice, and check out our Code of Conduct.
SmileyCraft is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f105808%2findex-matching-algorithm-without-hash-based-data-structures%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
