Highest voted questions tagged comparison - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T16:50:31Z https://cs.stackexchange.com/feeds/tag?tagnames=comparison&sort=votes http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/93467 18 Data structure or algorithm for quickly finding differences between strings JGut https://cs.stackexchange.com/users/89954 2018-06-25T05:48:50Z 2018-06-28T05:05:17Z <p>I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the array, I'm checking it against every string already in the array, which has a time complexity of $\frac{n(n-1)}{2} k$.</p> <p>Is there a data structure or algorithm that can compare strings to each other faster than what I'm already doing?</p> <p>Some additional information:</p> <ul> <li><p>Order matters: <code>abcde</code> and <code>xbcde</code> differ by 1 character, while <code>abcde</code> and <code>edcba</code> differ by 4 characters.</p></li> <li><p>For each pair of strings that differ by one character, I will be removing one of those strings from the array.</p></li> <li><p>Right now, I'm looking for strings that differ by only 1 character, but it would be nice if that 1 character difference could be increased to, say, 2, 3, or 4 characters. However, in this case, I think efficiency is more important than the ability to increase the character-difference limit.</p></li> <li><p>$k$ is usually in the range of 20-40.</p></li> </ul> https://cs.stackexchange.com/q/18346 5 More efficient algorithm for determining if one list is a sublist of another list Student https://cs.stackexchange.com/users/11640 2013-11-24T14:49:37Z 2013-11-26T21:23:38Z <p>I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.</p> <p>What if the list is sorted? </p> <p>An algorithm that can do this is by comparing every element of the first list with every element from the second list. I think there is an algorithm with a better complexity. Can anyone give me any idea?</p> https://cs.stackexchange.com/q/52663 4 How do I find the max and min value of an array in 3n/2−2 comparisons? David https://cs.stackexchange.com/users/45812 2016-02-04T01:21:40Z 2016-02-04T12:31:36Z <p>So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.</p> <p>What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method. </p> https://cs.stackexchange.com/q/65828 4 Is there a metric for the similarity of two image filters? Martin Thoma https://cs.stackexchange.com/users/2914 2016-11-10T10:00:27Z 2016-11-11T13:08:52Z <h2>Definitions</h2> <p>An image filter is a matrix $m \in \mathbb{R}^{k_1 \times k_2 \times k_3}$ which gets applied to an image $I \in \mathbb{R}^{l_1 \times l_2 \times l_3}$ as a discrete convolution </p> <p>$$I'(n_1, n_2, n_3) = \sum_{i=0}^{k_1} \sum_{j=0}^{k_2} \sum_{k=0}^{k_3} I[n_1-i - \lfloor \frac{k_1}{2} \rfloor, n_2 - j - \lfloor \frac{k_2}{2} \rfloor, n_3 - k - \lfloor \frac{k_3}{2} \rfloor] \cdot m[i, j, k]$$</p> <p>There are some well-known filters like Laplace filters, <a href="https://en.wikipedia.org/wiki/Prewitt_operator" rel="nofollow noreferrer">Prewitt filters</a>, ... (see <a href="https://martin-thoma.com/html5/graphic-filters/graphic-filters.htm" rel="nofollow noreferrer">my interactive example</a>)</p> <p>For example, for an RGB image $k_3 = 3$ and $k_1, k_2$ are width and height.</p> <h2>Question</h2> <p>Is there a metric to compare the similarity of image filters?</p> <h2>Context</h2> <p>Convolutional Neural Networks (CNNs) learn image filters. As they are randomly initialized, the filters they learn are different each time you train them. I am interested in quantifying those differences.</p> <p>I could, of course, use any metric for elements of $\mathbb{R}^{k_1 \times k_2 \times k_3}$. However, consider the filters</p> <p>\begin{align} m_1 &amp;= \begin{pmatrix}-1&amp;0&amp;1\\-1&amp;0&amp;1\\-1&amp;0&amp;1\end{pmatrix}\\ m_2 &amp;= \begin{pmatrix}1&amp;0&amp;-1\\1&amp;0&amp;-1\\1&amp;0&amp;-1\end{pmatrix}\\ m_3 &amp;= \begin{pmatrix}-0.9&amp;0.1&amp;1\\-0.9&amp;0.1&amp;1\\-0.9&amp;0.1&amp;1\end{pmatrix}\\ \end{align}</p> <p>For the image </p> <p><a href="https://i.stack.imgur.com/jusEA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jusEA.png" alt="enter image description here"></a></p> <p>$m_1$ produces</p> <p><a href="https://i.stack.imgur.com/O6DgJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/O6DgJ.png" alt="enter image description here"></a></p> <p>and $m_2$ produces</p> <p><a href="https://i.stack.imgur.com/BuBdQ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BuBdQ.png" alt="enter image description here"></a></p> <p>You can see a difference, but much less than for the result of $m_3$:</p> <p><a href="https://i.stack.imgur.com/Hb55C.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Hb55C.png" alt="enter image description here"></a></p> <p>This is probably not captured by most metrics. Another idea was to apply the metrics to the processed images on a given dataset, but this would make the results depend on the dataset and be computationally very intensive.</p> <p>(In case you want to try image filters yourself with Python: <a href="https://gist.github.com/MartinThoma/f51a1044c4abc6c7b81915ef96b7cfbd" rel="nofollow noreferrer">https://gist.github.com/MartinThoma/f51a1044c4abc6c7b81915ef96b7cfbd</a>)</p> https://cs.stackexchange.com/q/68164 4 Median-of-medians in O(log n) memory user12859 https://cs.stackexchange.com/users/0 2017-01-02T07:04:14Z 2018-01-28T22:52:57Z <p>Is there a way to use <a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow noreferrer">median-of-medians</a> to find a median in, <br> simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons?</p> <p>The user orlp on this site <a href="https://cs.stackexchange.com/a/68132/12859">seems to claim that there is</a>.</p> <p>Getting ​ ​O(log n) ​ ​<em>auxiliary</em> memory seems to be straightforward, <br> but I have no clue how that can be improved to O(log n) memory.</p> https://cs.stackexchange.com/q/106738 3 Why is finding minimum number of comparisons to sort $n$ elements so difficult? ryan https://cs.stackexchange.com/users/68251 2019-04-09T18:16:03Z 2019-04-09T23:40:43Z <p>In <em>The Art of Computer Programming</em> 2nd Ed, Vol 3, Section 5.3.1 then discuss a function <span class="math-container">$S(n)$</span> which is define as:</p> <blockquote> <p><span class="math-container">$S(n)$</span> : The minimum number of comparisons that suffice to sort <span class="math-container">$n$</span> elements.</p> </blockquote> <p>Further, the book regards <span class="math-container">$\lceil \lg n! \rceil$</span> as the <em>information theoretic lower bound</em> for <span class="math-container">$S(n)$</span>.</p> <p>Using <a href="https://en.wikipedia.org/wiki/Merge-insertion_sort" rel="nofollow noreferrer"><em>merge insertion</em></a> they also upper bound the number of comparisons by <span class="math-container">$F(n)$</span> where</p> <p><span class="math-container">$$F(n) = \sum_{k = 1}^{n} \lceil \lg \tfrac{3}{4} k \rceil$$</span></p> <p>So you can get the bound <span class="math-container">$\lceil \lg n! \rceil \leq S(n) \leq F(n)$</span>, and for any values <span class="math-container">$n$</span> where <span class="math-container">$\lceil \lg n! \rceil = F(n)$</span> you can find the exact value of <span class="math-container">$S(n)$</span>. </p> <p>My questions are:</p> <ol> <li><p>Why does <span class="math-container">$S(n)$</span> not always match the <em>information theoretic lower bound</em> <span class="math-container">$\lceil \lg n! \rceil$</span>? It seems like if this is all the bits of information we should need, that this is all the comparisons we would need. Why do they differ?</p></li> <li><p>Why is <span class="math-container">$S(n)$</span> so difficult to compute? It's discussed in the book some but the reasons are still unclear to me. Do you have to brute force and create every possible decision tree for a given <span class="math-container">$n$</span> and determine the longest path? Is there not a more efficient way? It seems that <span class="math-container">$S(n)$</span> has only been exactly computed for <span class="math-container">$n \leq 22$</span> (See <a href="https://oeis.org/A036604" rel="nofollow noreferrer">A036604 here</a>).</p></li> </ol> https://cs.stackexchange.com/q/96394 3 sort n numbers in the range [0,1] without multiplying or dividing Gabi G https://cs.stackexchange.com/users/92868 2018-08-19T21:46:50Z 2018-08-20T08:54:53Z <p>Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.</p> <p>It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.</p> <p>From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.</p> <p>However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason, I'm not sure if I'm right.</p> https://cs.stackexchange.com/q/111509 3 Minimum number of comparision to find the third largest element in an array of distinct integers? CS_GUY https://cs.stackexchange.com/users/106464 2019-07-05T05:09:43Z 2019-07-05T13:03:30Z <p>For the second largest element, I know that the formula is <span class="math-container">$n+ \lceil\log n \rceil -2$</span></p> <p>Is there any formula for the third largest element? and if so, what is the derivation?</p> https://cs.stackexchange.com/q/105124 3 Finding maximum takes at least $\lceil n/2 \rceil$ comparisons QWE https://cs.stackexchange.com/users/101224 2019-03-04T17:46:44Z 2019-03-04T18:05:40Z <p>We are given an array <span class="math-container">$A$</span> with <span class="math-container">$n$</span> elements, <span class="math-container">$n \in \mathbb{N}$</span> and all elements are in the set <span class="math-container">$\{1,2,3, \cdots, n \}$</span>.</p> <p>I want to prove that finding the maximum in <span class="math-container">$A$</span> (that is, outputting the index at which the maximum is found in <span class="math-container">$A$</span>) takes at least <span class="math-container">$\lceil n/2 \rceil$</span> comparison by assuming that there exists an algorithm that can find the maximum in at most <span class="math-container">$\lceil n/2 \rceil -1$</span> comparisons.</p> <p>I tried assuming that there is such an algorithm, then took as an initial input some particular array <span class="math-container">$A$</span> (just a basic one, namely <span class="math-container">$1,2,3,\cdots,n$</span>) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.</p> <p>I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.</p> <p>I thank you in advance!</p> https://cs.stackexchange.com/q/105118 3 Are comparison sort algos appropriate for SUBJECTIVE sorting? Chris Wilson https://cs.stackexchange.com/users/101219 2019-03-04T16:36:43Z 2019-03-04T21:26:59Z <p>I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their votes on a series of face-to-face matchups. (Spiderman vs. Jon Snow, etc. etc.). If this is designed well, we hope to attract a large audience and high participation.</p> <p>My first instinct was to use some variety of <a href="https://en.wikipedia.org/wiki/Comparison_sort" rel="nofollow noreferrer">comparison sort</a>--probably Bubble or Heap, given the manageable size. But as I brush up on the mechanics, all the literature I can find seems to be oriented toward stochastic sorts in which any pair of items can be definitely compared.</p> <p>Another curveball here is that, as more people participate, the ordered list can (but needn't mustn't) be informed by all the people who have already weighted in. This will probably be necessary since we can't expect every user to weigh for hundreds of matchups. I'm not clear on how to tell the algorithm which items are already somewhere near their appropriate place in the list thanks to a lot of preexisting votes.</p> <p>I'm sure I'm not the first to confront this issue since comparison algos are commonly used exact crowd wisdom on the best of, say, a few dozen photographs. I'm just not quite sure where to start. Am I looking for a variation on comparison sort with some addition search phrase for Google, or a different approach entirely?</p> <p>Thanks![Insert favorite fantasy sign-off.]</p> https://cs.stackexchange.com/q/102851 3 d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions CCOthers https://cs.stackexchange.com/users/93761 2019-01-14T12:31:14Z 2019-01-16T22:32:52Z <p>Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being <span class="math-container">$\sim |E|/|V|$</span>.</p> <p>Then for a fixed <span class="math-container">$|V|$</span>, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap? Where knowing the Fibonacci heap: delete_min = <span class="math-container">$O(\log |V |)$</span>, insert/decrease_key = <span class="math-container">$O(1)$</span> (amortized) and <span class="math-container">$|V|$</span> × delete_min + <span class="math-container">$(|V | + |E|)$</span> x insert <span class="math-container">$= O(|V|\log|V|+|E|)$</span>. </p> <p>On the other hand, d-ary heap implementation : delete_min = <span class="math-container">$O(\dfrac{d \log|V|}{\log d})$</span>, insert/ decrease_key =<span class="math-container">$O(\dfrac{\log|V|}{\log d}$</span>), and |V | × delete_min + (|V | + |E|) × insert = <span class="math-container">$O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$</span>. </p> <p>As trying to follow a provide solution, but I am not sure why it reduces to <span class="math-container">$O(\dfrac{\log|V|}{\log |E|/|V|})$</span>, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is <span class="math-container">$O(|E|)$</span>. How can we get the ratio as <span class="math-container">$O(\dfrac{\log|V|}{\log |E|/|V|})$</span> while Dijkstra with d-ary heap is <span class="math-container">$O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$</span>)? </p> <p><a href="https://i.stack.imgur.com/jh16R.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jh16R.png" alt="enter image description here"></a></p> https://cs.stackexchange.com/q/75120 3 How to determine the fewest number of comparisons for Heapsort? roughosing https://cs.stackexchange.com/users/71743 2017-05-08T19:14:57Z 2017-05-09T11:00:55Z <p>I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case.</p> <p>In its average case, Heapsort only requires $2n\log(n) - O(n)$ comparisons, although I don't know how to prove the best case scenario.</p> <p>Can someone possibly hint me where to start with my calculation, I have no idea how to prove fewest number of comparisons, always been either worst case or most comparisons up until now.</p> https://cs.stackexchange.com/q/47569 2 Fast comparison with a tolerance Yves Daoust https://cs.stackexchange.com/users/16034 2015-09-26T09:16:51Z 2015-09-27T04:46:06Z <p>I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.</p> <p>I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.</p> <p>$$K(r)\ne K(s)\implies |r-s|\ge 1.$$</p> <p>The converse,</p> <p>$$K(r)=K(s)\implies |r-s|&lt;1.$$</p> <p>may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)</p> <p>In my context (database search), the key being <em>discrete</em> and a <em>single</em> comparison for <em>equality</em> being sufficient are essential properties. </p> <p>The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.</p> <p>$$K(r):=\lfloor r\rfloor.$$</p> <p>Anyway this doesn't work as all values in range $[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test </p> <p>$$|r-s|&lt;1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$</p> <p>If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.</p> <p>I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain</p> <p>$$K(r)\ne L(s)\implies |r-s|\ge 1.$$</p> <p>Is this a known problem ? Is there a solution or a workaround ?</p> <p><strong>Update</strong>: the problem statement was reformulated in the original text.</p> https://cs.stackexchange.com/q/71122 2 Proving at least $n-1$ comparisons are needed to test if an array is sorted P. Jhon https://cs.stackexchange.com/users/67274 2017-03-04T13:15:11Z 2017-03-04T17:19:00Z <p>so I need to prove the following:</p> <p>Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.</p> <p>The problem comes with the following hint:</p> <p>Assume an algorithm exists that always correctly tests if the array is sorted using at most $n-2$ comparisons and show there must exist an input where this algorithm fails.</p> <p>Base on the hint, I tried proving this via contradiction and here is my attempt:</p> <p>Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons. Then, let A be an array of 2 random numbers $a$ and $b$. Given that we don't know the value of $a$ with relation to $b$ or vice versa, in order to find this relation, an thus find out if the array with n-distinct elements is sorted in increasing order, 1 comparison operation, namely between $a$ and $b$, is needed, but then $n-2 = 1-2 \neq 1$. Therefore we have arrived at a contradiction.</p> <p>While this attempt is most likely wrong, I am somewhat familiar with proofs by contradiction, but I don't see how deriving a contradiction from my initial assumption (the one from the hint) helps prove that $n-1$ comparisons are necessary.</p> https://cs.stackexchange.com/q/30506 2 Application of cosine similarity to detect plagiarism Kevi12 https://cs.stackexchange.com/users/22293 2014-10-02T11:57:39Z 2014-12-02T06:02:32Z <p>Can anyone tell me how using <a href="http://en.wikipedia.org/wiki/Cosine_similarity" rel="nofollow">cosine similarity</a> to see the correlation between two documents actually shows you if someone is plagiarising the other? I understand how cosine similarity works but don't understand how using this shows how closely related they are when the cosine deals with vectors and angles. How can this relate to a document?</p> https://cs.stackexchange.com/q/29250 2 Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate] user78219 https://cs.stackexchange.com/users/20986 2014-08-20T00:46:55Z 2014-08-26T17:58:42Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/3126/why-use-comparisons-instead-of-runtime-for-comparing-two-algorithms" dir="ltr">Why use comparisons instead of runtime for comparing two algorithms?</a> <span class="question-originals-answer-count"> 3 answers </span> </li> </ul> </div> <p>Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of asymptotical behavior of number of comparison operations, I don't quite understand why other costs of other types of operations are negligible.</p> <p>[Edit 2014-08-26]</p> <p>If I run the same mergesort implementation on two different computers (with possibly different architecture etc.), how to argue that running time of mergesort divided by the number of compares will approach (possibly different) constants as the problem size increases?</p> https://cs.stackexchange.com/q/24745 2 Cost of partitioning in quicksort Levi Botelho https://cs.stackexchange.com/users/17672 2014-05-15T07:44:10Z 2014-05-15T16:14:06Z <p>I'm reading "Algorithms Fourth Edition" by Sedgewick &amp; Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.</p> <p>When talking about the complexity of quicksort, the book says that the cost of partitioning, measured in the number of compares, is equal to <code>N + 1</code>, where <code>N</code> is equal to the number of elements in the collection to sort. We are assuming here that we just choose the first element in the collection to serve as the partition.</p> <p>My question is would the cost of partitioning not really be equal to <code>N - 1</code>? That is, that you choose an element to serve as the partition and you compare it with every <em>other</em> element in the array.</p> <p>--</p> <p>As requested, the partitioning process is defined as follows:</p> <ul> <li>The entry which will serve as partition is in its final place in the array.</li> <li>No entries in positions before the partition are greater than the partition value.</li> <li>No entries in positions after the partition are less than the partition value.</li> </ul> <p>At this point I'm guessing it is in fact a typo...</p> <p>--</p> <p>The partitioning algorithm is outlined as follows</p> <ul> <li>Take the leftmost array element as the "partitioning item"</li> <li>Scan the array from the left until an element greater than or equal to the partitioning item is found</li> <li>Scan from the right until an entry less than or equal to the partitioning item is found</li> <li>When both a right and left item are found, exchange them</li> <li>Repeat until the scan indexes cross</li> <li>Once the scan indexes cross, exchange the partitioning item with the rightmost entry in the lower side of the array.</li> </ul> <p>Note that the "cost" of the partitioning is being calculated in compares and not array accesses.</p> https://cs.stackexchange.com/q/104062 1 Sorting lower bounds for almost sorted array juleand https://cs.stackexchange.com/users/100184 2019-02-09T09:21:03Z 2019-02-10T04:14:07Z <p>Can't find a good way to tackle the problem. Would appreciate any help.</p> <p><span class="math-container">$A$</span> is an <span class="math-container">$n$</span> items array from an ordered set, in which every item is at most <span class="math-container">$\log n$</span> indices away from its position in the sorted array.</p> <p>Show that:</p> <ol> <li><p>The array can be sorted in <span class="math-container">$O(n\log\log n)$</span>.</p></li> <li><p>There is a lower bound of <span class="math-container">$\Omega(n\log\log n)$</span> for sorting <span class="math-container">$A$</span> using comparisons.</p></li> </ol> <p>The general idea is more important than details for both assertions.</p> https://cs.stackexchange.com/q/88874 1 What is the name for the comparison used in C's memcmp? user619818 https://cs.stackexchange.com/users/1024 2018-03-04T12:59:31Z 2018-03-05T18:48:56Z <p>The C <code>memcmp</code> function (and <code>strcmp</code>) does a comparison similar to the function below for comparing integers:</p> <pre><code>int compare(const int a, const int b) { if (a &gt; b) return 1; if (b &gt; a) return -1; return 0; } </code></pre> <p>Microsoft information for their <code>strcmp</code> says:</p> <blockquote> <p>The strcmp function performs an ordinal comparison of string1 and string2 and returns a value that indicates their relationship.</p> </blockquote> <p><a href="https://www.gnu.org/software/libc/manual/html_node/Comparison-Functions.html#Comparison-Functions" rel="nofollow noreferrer">The manual of GNU's libc</a> describes the comparison in this way:</p> <blockquote> <p>Your comparison function should return a value the way <code>strcmp</code> does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater".</p> </blockquote> <p>But doesn't define any name for this comparison type.</p> <p>What is the name for this comparison algorithm?</p> <p>And why doesn't <code>memcmp</code> simply return say 0 if a and b the same and 1 otherwise?</p> https://cs.stackexchange.com/q/108516 1 Turing machine - compare two words Adam Perinay https://cs.stackexchange.com/users/104439 2019-04-25T11:38:50Z 2019-04-25T13:11:48Z <p>I have a simple turing machine with single tape. I need to compare two words <code>&lt;w1&gt;$&lt;w2&gt;$</code> and write output. Language is all letters and numbers.</p> <p>I did comparation with the {a,b} language but there are more characters.</p> <p>Is only solution do it one by one in different branches? I mean read / mark the letter (enter the letter branch), go to the second word and read /mark the same letter, go to the first word, repeat? My problem with this solution is, when I want to change something I need to remake all branches. The other problems are the error handling, when I do not find the right letter I don't want crash. How handle that?</p> https://cs.stackexchange.com/q/69709 1 Identify similar functions Surcle https://cs.stackexchange.com/users/65673 2017-02-02T10:08:23Z 2017-02-02T21:43:07Z <p>I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and for each input $i$, $f(i) = g(i)$. Moreover, the two functions $f$ and $g$ could be implemented in a completely different way, e.g. different algorithms that solve the same problem.</p> <p>In my opinion, clone detection could be useful, but I cannot compare both tokens or ASTs since the implementations are completely different. A semantic comparison could be a possible solution, but are there other techniques that I can use?</p> https://cs.stackexchange.com/q/104477 1 An algorithm to drop low-priority items from a heap-based priority queue Alexey https://cs.stackexchange.com/users/27348 2019-02-17T17:56:33Z 2019-02-18T20:43:13Z <p>I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap all items whose priority is too low.)</p> <p>It is easy to make an algorithm that walks the heap level by level from bottom up, comparing the item weights to the threshold value and doing dropping-and-swapping. It will turn out to be extremely inefficient though if, for example, all items in the heap need to be dropped.</p> <p>It looks better to start by finding an item at the bottom level that is heavier than the threshold value and walk upwards from it until finding the highest element that needs to be dropped. Then the whole sub-heap under that element needs to be dropped. The space taken up by this sub-heap can be filled with elements moved from one or two bottom levels that are not in this sub-heap, and the sub-heap can be rebuilt. However, this method does not look perfect either, as most likely the dropped sub-heap will be filled with elements some of which need to be dropped too.</p> <p>Are there any efficient or well-studied algorithms for this?</p> https://cs.stackexchange.com/q/60055 1 How to compare two objects for percentage of equivalence Rockstar5645 https://cs.stackexchange.com/users/47461 2016-06-27T15:12:10Z 2016-06-28T11:46:34Z <p>I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find users with similar interests in songs, and I suggest them new songs based on that.</p> <p>Each user profile basically looks like this </p> <pre><code>userID: [the userid of the user] songs: [the list of songs that the user has rated] ratings: [the corresponding ratings each user gave to the song] </code></pre> <p>Each <strong>song</strong> is represented by a <strong>9 digit whole number</strong> and each <strong>rating</strong> is a <strong>whole number from 1 to 6</strong>. Basically put, I have to compare one user to the rest of the users to determine which of them match this user the best. By match, I mean gave the same songs similar ratings. To do this, I created a simple algorithm. </p> <pre><code>Step 1) Create a list, in which each entry maps our target user to each of the other users. Step 2) Now consider each entry, determine which songs both of the users have rated, and store those songs (along with the corresponding ratings each user gave them) in this entry itself Step 3) Now iterate through each entry and perform the following operations a) let percentage = 0 b) let num = [the number of songs that both users rated] c) iterate through each song (that both the users rated) and perform the following operations i) determine the score our target user gave this song and store it in variable a ii) determing the score the other user gave this song and store it in variable b iii) map a and b to new values based on this 1 --&gt; -3 2 --&gt; -2 3 --&gt; -1 4 --&gt; 1 5 --&gt; 2 6 --&gt; 3 iv) now calculate sum as sum = |a| + |b| where || is the absolute values v) now calculate degree as degree = sum/2 vi) now if a * b is less than 0 then calculate (percentage - degree) and store that value again in percentage if not then calculate (percentage - degree) and store that value again in percentage d) now calculate (50 + (percentage / (6*num))*100) and store that value in this entry as match Step 4) Now that I have my list of entries (along with the match between each pair of target user and other user) I sort the list in descending order of match and from that, I can determine which users have the closest match in taste by selecting from the first entries </code></pre> <p>Now for each user pair, I am completely neglecting the songs that one user rated and the other didn't, and that is okay for me. </p> <p>There are several problems with this method though, the biggest one being that this algorithm is very time consuming for a large set of users (say around 1,000,000). And also that I have to load in all the users, every time I need to find a set of matching users for just 1 user. And I need to do this repeatedly for that user, to update his/her list. </p> <p>Is there a way to make this more efficient? Can I assign a value to each user that takes into account all the songs that they rated, and use that number to compare the users? Is that even possible? I guess what I'm asking is, how can I compare and contrast this data, mathematically, to find similar users, efficiently. Also, can someone suggest a proper tag for this type of question? </p> <p><strong>EDIT</strong></p> <p>D.W. has suggested a solution, but how do I implement it? Can you provide more detail?</p> https://cs.stackexchange.com/q/100717 1 Optimize sorting matrix entries by row and column vibe https://cs.stackexchange.com/users/92694 2018-11-29T16:46:48Z 2019-04-30T08:01:35Z <p>I am writing a routine to store an <span class="math-container">$M$</span>-by-<span class="math-container">$N$</span> sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry <span class="math-container">$(i,j)$</span> should be inserted in the tree. I am defining the ordering of the matrix elements simliar to how C handles a row-major ordered dense matrix. In particular, a matrix element <span class="math-container">$(i_a,j_a)$</span> comes before <span class="math-container">$(i_b,j_b)$</span> if: <span class="math-container">$$N i_a + j_a &lt; N i_b + j_b$$</span> I need to write a routine which returns <span class="math-container">$-1$</span> if <span class="math-container">$(i_a,j_a)$</span> is less than <span class="math-container">$(i_b,j_b)$</span>, <span class="math-container">$+1$</span> if <span class="math-container">$(i_a,j_a)$</span> is greater than <span class="math-container">$(i_b,j_b)$</span> and <span class="math-container">$0$</span> if they are equal. I want this routine to be as fast as possible since I will be calling it hundreds of millions of times.</p> <p>I've tried two options so far, which I implement as macros to avoid the overhead of a function call.</p> <p><strong>Option 1:</strong> Comparing rows first and then compare columns</p> <pre><code>#define COMPARE(ia,ja,ib,jb) (ia &lt; ib ? -1 : (ia &gt; ib ? 1 : (ja &lt; jb ? -1 : ja &gt; jb))) </code></pre> <p>The worst case for this option is 4 comparisons between integers.</p> <p><strong>Option 2:</strong> Compare full linear index</p> <pre><code>#define COMPARE(ia,ja,ib,jb) (ia*N + ja &lt; ib*N + jb ? -1 : ia*N + ja &gt; ib*N + jb) </code></pre> <p>The worst case for this option is 2 multiplies, 2 adds, and 2 comparisons (assuming the compiler optimizes so that the quantities <span class="math-container">$N i_a + j_a$</span> and <span class="math-container">$N i_b + j_b$</span> are computed only once).</p> <p>So far, Option 1 is a clear winner, and runs faster by around 20-30% on tests I have done. </p> <p><strong>My question is: can anyone suggest a way to optimize this even more, by somehow improving on Option 1, or perhaps suggesting a completely different method of sorting matrix elements in the tree?</strong></p> <p>Profiling has shown that a significant amount of time is spent in this comparison function, so it is worth it to me to make it as fast as possible.</p> <p>Another idea I have is to use 2 levels of binary trees. The high-level tree uses only row indices for sorting. Then each node in that tree contains a pointer to another tree which uses the column indices for sorting. This way the comparison function only needs to compare two integers instead of 4. But having 2 levels of tree would make things more complicated. I have not implemented or benchmarked this approach yet.</p> https://cs.stackexchange.com/q/86928 1 Compare two atan2 Orient https://cs.stackexchange.com/users/20200 2018-01-18T16:38:52Z 2018-01-18T18:24:47Z <p>I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple concentric points on some step I get a pencil of radius vectors origins from the center of a circle. I need to sort them by angle (or at least to find minmax elements). I use the next formula to compare raduis vectors $\mathbf{v_i} = (x_i, \;y_i)$ and $\mathbf{v_j} = (x_j, \;y_j)$:</p> <p>$$atan2(y_i, \;x_i) &lt; atan2(y_j, \;x_j)$$</p> <p>I sure result can be achieved avoiding trigonometric functions. Can it be expressed without comparisons?</p> <p>Currently I can sort them by quadrants, if both points are in the same quadrant, then I just look at cross product sign, otherwise I compare quadrant numbers.</p> <p>PS: can someone create <code>point-location</code> tag?</p> https://cs.stackexchange.com/q/42246 1 comparison in speed between the processor and the hard disk samDroid https://cs.stackexchange.com/users/33404 2015-05-07T03:49:23Z 2015-05-07T04:02:43Z <p>I'm reading through William Stalling's operating system intrnals and design principles book. Talking about interrupts, it gives the following examples when comparing the speed of a processor and a hard disk:</p> <blockquote> <p>To give a specific example, consider a PC that operates at 1 GHz, which would allow roughly 10^9 instructions per second. A typical hard disk has a rotational speed of 7200 revolutions per minute for a half-track rotation time of 4 ms, which is 4 million times slower than the processor.</p> </blockquote> <p>My question is how was the result calculated? How did we know that the hard disk is 4 million times slower?</p> https://cs.stackexchange.com/q/110432 1 Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks Raymond https://cs.stackexchange.com/users/106292 2019-06-09T21:37:25Z 2019-06-09T21:37:25Z <p>I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are <strong>not sorting networks</strong>. In his paper "Smallest Compact Formulation for the Permutahedron" (An online version is available here <a href="http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf" rel="nofollow noreferrer">http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf</a>), he shows that any sorting network can be used to obtain an extended formulation for the permutahedron. This is done by expressing each comparator in the network by a set of linear constraints.</p> <p>In another paper, "Extended Formulations in Combinatorial Optimization," Conforti et al. discuss this formulation and show that it can also be applied to any comparator network, sorting networks being a special case (It's Theorem 6.8 in Section 6.5 in the version of the paper shown here <a href="http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf" rel="nofollow noreferrer">http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf</a>). I am interested in using this extended formulation to look at a specific class of comparator networks.</p> <p>My first question is this (basically a sanity check to make sure I understood the proof correctly and that it is valid).</p> <p>Can the extended formulation developed by Michael Goemans be applied to comparator networks that are not sorting networks such that in every vertex the input to the network will be a permutation of {1, 2, ... n} that the comparator network will sort? I believe that's what the proof in Conforti et al says but I just wanted to be sure.</p> <p>The networks I am most interested in studying have the following properties.</p> <ul> <li>The comparator network has n inputs and up to 2*n comparators</li> <li>Every line is connected to at least one comparator</li> <li>No two comparators are connected to the same two horizontal lines</li> <li>The output of the network is sorted</li> <li>The network is not a sorting network</li> </ul> <p>I am only interested in <strong>linear optimization</strong> over the input variables and I would like to know if there is a simpler way to solve this problem (the network described above) than running a linear program. Linear programming is fine but I just wanted to make sure I wasn't missing anything obvious.</p> <p>Does the comparator network described have any properties that make a simpler algorithm possible?</p> <p>Thank you,</p> https://cs.stackexchange.com/q/109304 1 How to justify using available code (in different language) for comparing algorithms [closed] Mostafa https://cs.stackexchange.com/users/95193 2019-05-13T14:33:41Z 2019-05-13T14:33:41Z <p>I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and the comparing one is in C++, and the code is publicly available. We did not re-implement the C++ code, to avoid any decrease in the efficiency of their algorithm, and to save time as well. Now the reviewer is responding: It is probable that there is a significantcant difference in performance between MATLAB and C++. The authors should make it clear if and how the results were normalized to ensure a fair comparison.''</p> <p>So my question is this: Is there any (scientific) ratio or similar comparison between the efficiency of MATLAB and C++?</p> <p>When we opted to use the available code, we thought it is completely OK since MATLAB is known to be slower. So using the comparing algorithm in a faster environment is OK. I should add that our algorithm is now performing much better than the comparing one.</p> https://cs.stackexchange.com/q/95403 1 Merge unstructured with structured data OPunktSchmidt https://cs.stackexchange.com/users/91816 2018-07-19T07:15:06Z 2018-07-19T07:20:47Z <p>We have a database with well-formated and structured data. From time to time we get Excel - files from our clients. This Excel Files have to be imported to the database. It it very important that we dont create duplicate data so we first need to check if the data record already exists in the database.</p> <p>The problem is: The records in the excel files do not contain a unique identifier. Although there are certain properties that are always included, but they are not suitable for easy comparison. In addition, the excel files contain many properties that are missing in other files and that we do not have in our database.</p> <p>We are talking about tens of thousands of records here. It is not an option that this happens manually by an employee. At the very least, a large part should be handled automatically and only a small part should be manually controlled.</p> <p>My question is very open. I do not know which solution I'm looking for exactly. Maybe there is a general generic algorithm for merging unstructured data with structured data?</p> https://cs.stackexchange.com/q/83457 1 finding best n players in minimum number of comparisons noman pouigt https://cs.stackexchange.com/users/36212 2017-11-05T06:55:03Z 2018-07-05T20:41:39Z <p>I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 players?</p> <p>I thought of using below approach to find out 2 best players.</p> <p>So for finding out the 3rd best player we can use the same approach i.e. players lost again best best player + players lost against 2nd best player should be again played against each other to find out the 3rd best player.</p> <p>Am I right if this would be the minimum number of comparisons to get 3rd best player?</p> <p>Or should I divide the players in square root of input size and then play in groups as <a href="http://www.geeksforgeeks.org/puzzle-9-find-the-fastest-3-horses/" rel="nofollow noreferrer">this</a>? </p> <p>Edit: When two players play better player always wins. You can design your own tournament strategy to figure out the best <code>n</code> players.</p> <p><a href="https://i.stack.imgur.com/nfotD.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/nfotD.jpg" alt="enter image description here"></a></p>