Index matching algorithm without hash-based data structures?(When) is hash table lookup O(1)?The theoretical...
Make a Bowl of Alphabet Soup
What is it called when someone votes for an option that's not their first choice?
Unfrosted light bulb
How do you say "Trust your struggle." in French?
Why didn’t Eve recognize the little cockroach as a living organism?
Offset in split text content
How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?
Why does a 97 / 92 key piano exist by Bosendorfer?
What is the period/term used describe Giuseppe Arcimboldo's style of painting?
Why is "la Gestapo" feminine?
PTIJ: Which Dr. Seuss books should one obtain?
How to split IPA spelling into syllables
A seasonal riddle
How to test the sharpness of a knife?
Reasons for having MCU pin-states default to pull-up/down out of reset
Writing in a Christian voice
Output visual diagram of picture
How do you justify more code being written by following clean code practices?
Trouble reading roman numeral notation with flats
Travelling in US for more than 90 days
Can you describe someone as luxurious? As in someone who likes luxurious things?
Why can't I get pgrep output right to variable on bash script?
Non-Borel set in arbitrary metric space
Pre-Employment Background Check With Consent For Future Checks
Index matching algorithm without hash-based data structures?
(When) is hash table lookup O(1)?The theoretical upper bounds for duplicate detection in a set of objects?How are hash tables O(1) taking into account hashing speed?What Exactly Does the Term “Key” Mean with Regards to a Hash Table?Static hash tables“Hash” Probing?Algorithmic Design to Undo Rotation of ArrayDirect addressing on a huge arrayCan hash tables handle variable sized entries?Hash table open addressing without dummy
$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 6 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 6 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 6 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 6 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 6 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 6 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 6 hours ago
SmileyCraftSmileyCraft
1261
asked 6 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
2 hours 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
1 hour 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
2 hours 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
1 hour 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
2 hours 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
1 hour 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
2 hours 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
1 hour 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
2 hours 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
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
2 hours 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
2 hours 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
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
1 hour 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
