Timeline for How many bits/questions does it take to identify the most frequent number in an array?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2017 at 22:37 | comment | added | Hauke Reddmann | @Emil: But note that with the following comparisons for n=6 which are not exactly elegant: IF (4=5&4=6) ELSEIF (3=4&3=5)V(3=4&3=6)V(3=5&3=6) ELSEIF (1=2) ELSEIF (2=3&2=4)V(2=3&2=5)V(2=3&2=6) ELSEIF (2=4&2=5)V(2=4&2=6)V(2=5&2=6) ELSEIF (1=3V1=4V1=5V1=6) ELSEIF (2=3V2=4V2=5V2=6) ELSEIF (3=4V3=5V3=6) ELSEIF 4=5 ELSE ENDIF (with the obvious assignments) I still get a giant speedup vs. the "elegant" matrix code, even though I stored all comparison first. It would be interesting if a straightforward nested IF over all cases would be faster. Here I don't need any nesting. | |
| Dec 6, 2017 at 22:07 | comment | added | Hauke Reddmann | @Emil: OK, if I will still need O(m^2) then you answered my questions in the negative - no effective speedup is possible. (Of course, the factual speedup due to the prefactors is still rather impressive - the n=3 IF version runs 5x faster than the matrix-sum-max version.) | |
| Dec 6, 2017 at 22:01 | comment | added | Hauke Reddmann | @domotorp - The first if checks 2=3 and 2=4. The second 3=4. Two IF but three comparisons. | |
| Dec 6, 2017 at 20:42 | comment | added | domotorp | @Hauke: In the question you write that "Two for n=4", but in your first comment you write that the "factual costs are 3" [in the n=4 case] - so it would be nice to state your problem more explicitly. | |
| Dec 6, 2017 at 13:24 | comment | added | Emil Jeřábek | I still don’t quite understand what you are saying. If you formally allow arbitrary queries, but regardless of that count the number of equality queries that are needed to implement them, how is that any different from just only allowing equality queries? Anyway, it is easy to show that in that case, any algorithm needs at least $\binom{n-1}2$ equality queries in the worst case, hence you basically cannot beat the trivial $\binom n2$ algorithm that compares everybody to everybody. | |
| Dec 6, 2017 at 9:57 | comment | added | Hauke Reddmann | @Nate: Been there, done that: codegolf.stackexchange.com/questions/42529/… But this optimizes the program length (or rather language? :-), rather than the runtime... | |
| Dec 6, 2017 at 9:46 | comment | added | Hauke Reddmann | @Nate: Actually, if the numbers are not too large, this algorithm geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time is perfect. Unfortunately, my numbers may be huge. I thus made a code that "relabels" them first, and indeed it works in O(m) (m arraylength) time. Even more unfortunately, the prefactor is so huge that this becomes relevant only when m is 100 or so (and I rarely would need more than 10) and my cheap O(m^2) code (write all comparisons into a m*m matrix, sum over col, then max over row) is faster. | |
| Dec 6, 2017 at 9:33 | comment | added | Hauke Reddmann | @Jay: Sorry, not exactly! It finds a "strong" majority but I'd like to know a "weak" majority. Note 3 in the wiki seems very relevant. THX. | |
| Dec 6, 2017 at 9:27 | comment | added | Hauke Reddmann | @Emil: Extremely good point, which I did not phrase very well. I do allow unrestricted queries, and they do solve trivially, but this is cheating. :-) For example, the n=4 case I solve by IF 2nd=oneoflasttwo 2 ELSE 3rd=4th 3 ELSE 1 ENDIF. This is very OK as an algorithm but the factual costs are 3 when stated in = operations, and THAT I want to know. | |
| Dec 5, 2017 at 22:53 | comment | added | Nate Eldredge | Seems like a good question for CodeGolf.SE :-) | |
| Dec 5, 2017 at 17:32 | comment | added | Jay Pantone | Maybe this answers your question? Boyer-Moore majority vote algorithm | |
| S Dec 5, 2017 at 15:02 | history | suggested | Mikhail Tikhomirov |
tags: -nt, +co, comp. complexity
|
|
| Dec 5, 2017 at 14:23 | review | Suggested edits | |||
| S Dec 5, 2017 at 15:02 | |||||
| Dec 5, 2017 at 12:58 | comment | added | Emil Jeřábek | What kind of queries do you allow? (With no restrictions, one can trivially find the answer using a single $n$-valued query, or $\log_2 n$ binary queries.) | |
| Dec 5, 2017 at 10:30 | history | asked | Hauke Reddmann | CC BY-SA 3.0 |