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
Is divisi notation needed for brass or woodwind in an orchestra?
Put the phone down / Put down the phone
Asserting that Atheism and Theism are both faith based positions
Connection Between Knot Theory and Number Theory
How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?
Pre-Employment Background Check With Consent For Future Checks
Started in 1987 vs. Starting in 1987
What is the period/term used describe Giuseppe Arcimboldo's style of painting?
What properties make a magic weapon befit a Rogue more than a DEX-based Fighter?
Why does a 97 / 92 key piano exist by Bosendorfer?
Error in master's thesis, I do not know what to do
If the Dominion rule using their Jem'Hadar troops, why is their life expectancy so low?
Reason why a kingside attack is not justified
Would this string work as string?
Should I warn a new PhD Student?
Is there a distance limit for minecart tracks?
Air travel with refrigerated insulin
Index matching algorithm without hash-based data structures?
Can you describe someone as luxurious? As in someone who likes luxurious things?
Magnifying glass in hyperbolic space
Not hide and seek
How to preserve electronics (computers, ipads, phones) for hundreds of years?
Can Gdal.Translate() return an object instead of writing a file?
What should be the ideal length of sentences in a blog post for ease of reading?
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
New contributor
$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
New contributor
$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
New contributor
$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
New contributor
New contributor
New contributor
asked 6 hours ago
SmileyCraftSmileyCraft
1311
1311
New contributor
New contributor
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.
$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.
$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.
$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.
$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.
edited 1 hour ago
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