Index matching algorithm without hash-based data structures?(When) is hash table lookup O(1)?The theoretical...
Do I have to take mana from my deck or hand when tapping this card?
Error in master's thesis, I do not know what to do
Why is "la Gestapo" feminine?
Writing in a Christian voice
How to test the sharpness of a knife?
Trouble reading roman numeral notation with flats
Output visual diagram of picture
Showing mass murder in a kid's book
Derivative of an interpolated function
Offset in split text content
How do you justify more code being written by following clean code practices?
Mortal danger in mid-grade literature
Hashing password to increase entropy
Is there a distance limit for minecart tracks?
Make a Bowl of Alphabet Soup
New Order #2: Turn My Way
Can Gdal.Translate() return an object instead of writing a file?
How do I lift the insulation blower into the attic?
Sort with assumptions
Index matching algorithm without hash-based data structures?
Capacitor electron flow
Can you take a "free object interaction" while incapacitated?
What is the meaning of "You've never met a graph you didn't like?"
What is the purpose of using a decision tree?
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
1311
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
1311
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
1311
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
1311
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
1311
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
1311
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
1311
asked 6 hours ago
SmileyCraftSmileyCraft
1311
1311
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
2 hours 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
2 hours 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
2 hours 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
2 hours 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
2 hours 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
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
2 hours 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
