Click here to Skip to main content
15,306,209 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 
GeneralRe: How do you understand cryptic code? Pin
honey the codewitch7-Jul-21 4:38
mvahoney the codewitch7-Jul-21 4:38 
AnswerRe: How do you understand cryptic code? Pin
NightPen7-Jul-21 6:44
MemberNightPen7-Jul-21 6:44 
AnswerRe: How do you understand cryptic code? Pin
hur10forcer108-Jul-21 2:38
Memberhur10forcer108-Jul-21 2:38 
GeneralHow hard can tallying ranked voting be? Pin
swampwiz6-Jul-21 4:38
Memberswampwiz6-Jul-21 4:38 
GeneralRe: How hard can tallying ranked voting be? Pin
Slacker0076-Jul-21 5:54
professionalSlacker0076-Jul-21 5:54 
GeneralRe: How hard can tallying ranked voting be? Pin
Matthew Dennis6-Jul-21 6:13
sysadminMatthew Dennis6-Jul-21 6:13 
GeneralRe: How hard can tallying ranked voting be? Pin
PIEBALDconsult6-Jul-21 6:22
professionalPIEBALDconsult6-Jul-21 6:22 
GeneralRe: How hard can tallying ranked voting be? Pin
Jon McKee6-Jul-21 15:13
professionalJon McKee6-Jul-21 15:13 
If we use bit groupings for the ranks of each candidate, that would look something like:
Bits per candidate: floor(log_2(candidateCount)) + 1
Bits per vote: candidateCount * bitsPerCandidate
Total space for election: voters * bitsPerVote

So given 300,000,000 voters with 12 candidates:
space = 300,000,000 * 12 * (floor(log_2(12)) + 1)
space = 14,400,000,000 bits or 1.8 GB

Given the same amount of voters with 24 candidates:
space = 300,000,000 * 24 * (floor(log_2(24)) + 1)
space = 36,000,000,000 bits or 4.5 GB

Space definitely isn't the issue. What about the algorithm?

1) Bin every vote by first-pick candidate.
2) If no bin is >50% of the votes, re-bin the lowest bin and repeat #2.
3) The >50% bin is your winner.

I honestly don't see why this would be an issue. Worst case scenario something like v+(c-2)*(v/2) run-time where v is the vote count and c is the number of candidates. v/2 is just a napkin-math average since the redistributed bins would start out small and grow as the candidate list got shorter.

Again, just a bunch of napkin math so I probably missed something but I never bought the "it's too hard to compute" excuse either Unsure | :~ And I'm sure there are clever tricks to reduce the time required.

EDIT: For reference, if processing a vote takes:
1 microsecond: 30 minutes to determine a winner @ 300M votes, 12 candidates
1 millisecond: 20 days, 20 hours to determine a winner @ 300M votes, 12 candidates

And this is a single-threaded, un-optimized, brute-force approach.


modified 6-Jul-21 21:48pm.

GeneralRe: How hard can tallying ranked voting be? Pin
Dan Neely7-Jul-21 2:53
MemberDan Neely7-Jul-21 2:53 
GeneralRe: How hard can tallying ranked voting be? Pin
Jon McKee7-Jul-21 7:09
professionalJon McKee7-Jul-21 7:09 
GeneralRe: How hard can tallying ranked voting be? Pin
Dan Neely7-Jul-21 7:17
MemberDan Neely7-Jul-21 7:17 
GeneralRe: How hard can tallying ranked voting be? Pin
Jon McKee7-Jul-21 7:57
professionalJon McKee7-Jul-21 7:57 
GeneralRe: How hard can tallying ranked voting be? Pin
RDM Jr7-Jul-21 9:16
MemberRDM Jr7-Jul-21 9:16 
GeneralThought of the Day Pin
OriginalGriff6-Jul-21 4:16
mveOriginalGriff6-Jul-21 4:16 
GeneralRe: Thought of the Day Pin
dandy726-Jul-21 4:32
Memberdandy726-Jul-21 4:32 
GeneralRe: Thought of the Day Pin
W Balboos, GHB6-Jul-21 4:36
mveW Balboos, GHB6-Jul-21 4:36 
GeneralRe: Thought of the Day Pin
Kschuler6-Jul-21 5:19
MemberKschuler6-Jul-21 5:19 
GeneralRe: Thought of the Day Pin
jeron16-Jul-21 5:33
Memberjeron16-Jul-21 5:33 
PraiseRe: Thought of the Day Pin
megaadam6-Jul-21 5:41
professionalmegaadam6-Jul-21 5:41 
GeneralRe: Thought of the Day Pin
jeron16-Jul-21 7:44
Memberjeron16-Jul-21 7:44 
GeneralRe: Thought of the Day Pin
DRHuff6-Jul-21 11:14
MemberDRHuff6-Jul-21 11:14 
GeneralRe: Thought of the Day Pin
Daniel Pfeffer6-Jul-21 11:23
professionalDaniel Pfeffer6-Jul-21 11:23 
GeneralBreath Analysis Pin
grralph16-Jul-21 1:57
Membergrralph16-Jul-21 1:57 
GeneralRe: Breath Analysis Pin
SeeSharp26-Jul-21 2:11
MemberSeeSharp26-Jul-21 2:11 
GeneralRe: Breath Analysis Pin
grralph16-Jul-21 22:09
Membergrralph16-Jul-21 22:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.


Straw Poll

On which operating systems are you writing code?
Let's see if things have changed since we last ran this. "writing code" meaning editing, building, and running the code on that OS.
  Results   820 votes