Как я могу использовать Linq для выбора верхних / нижних N участников в голосовании по рейтингу?

Question

Я пытаюсь использовать Linq (и, в конечном итоге, параллельно Linq) вычислить верхние N бюллетеней в голосовании с выбором рейтинга / альтернативном голосовании

Я использую следующий код для генерации несколькихбюллетени со структурированным выводом.

Мой вопрос заключается в том, как я могу использовать Linq, чтобы сообщить мне любое из:

• Count() голосов за данного участника
• Фактические бюллетени для данного участника, где count() = n
• Фактические участники, которые не получили голосов

Я просто борюсь с первоначальным запросом и могу взломатьотдохните, как только у меня будет отправная точка.

Если у меня будет время, я с этим повеселюсь и отправлю бюллетени в Task Parallel Library / RX, где я могу вычислить результаты в режиме реального времени.

Код

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace RankedChoiceDataGenerator
{

    public static class ThreadSafeRandom
    {
        [ThreadStatic] private static Random Local;

        public static Random ThisThreadsRandom
        {
            get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); }
        }
    }
    static class MyExtensions
    {
        public static void Shuffle<T>(this IList<T> list)
        {
            int n = list.Count;
            while (n > 1)
            {
                n--;
                int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1);
                T value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }
    }

    public class BallotEntry
    {
        public int ContestantID { get; set; }
        public int OrderedPreferenceForContestant { get; set; }

        public override string ToString()
        {
            return "Contestant " +ContestantID + " was assigned to " + OrderedPreferenceForContestant + " place";
        }
    }

    // will be much more efficent as a struct
    public class Ballot
    {
        public BallotEntry[] Entries { get; set; }

        public override string ToString()
        {
            return "This ballot voted for " + Entries.Length + " positions";
        }
    }

    class MainClass
    {

        public static List<Ballot> BallotsToTally = new List<Ballot>();

        public static void Main(string[] args)
        {
            var numberOfBallots = 5;
            var thingsToVoteOn = 10;

            Random r = new Random();

            for (int i = 0; i < numberOfBallots ; i++)
            { 
                // One Ballot per voter
                Ballot b = new Ballot();

                // Voters can vote for as many or as few as they want
                int numOfEntries = r.Next(1, thingsToVoteOn );
                b.Entries = new BallotEntry[numOfEntries];

                // Ranked Vote simulation
                var randomSetOfThings = new List<int>(Enumerable.Range(1, thingsToVoteOn));
                randomSetOfThings.Shuffle();

                var preferenceOrder = new List<int>(Enumerable.Range(1, numOfEntries ));
                preferenceOrder.Shuffle();
                for (int n = 0; n < numOfEntries ; n++)
                {
                    b.Entries[n] = new BallotEntry();

                    // Choose a random thing
                    b.Entries[n].ContestantID = randomSetOfThings[n];

                    // Vote on the random thing using ranked vote
                    b.Entries[n].OrderedPreferenceForContestant = preferenceOrder[n ];
                }

                BallotsToTally.Add(b);
            }

            // Process ballots
            // Create Snapshot of Phase 1
            // find the bottom and top ranking items in the list



        }
    }
}

Answer 1

Это дает вам ответ на вопросы (1) и (3):

    var votesPerContestant =
        BallotsToTally
            .SelectMany(x => x.Entries.Select(y => y.ContestantID))
            .GroupBy(x => x)
            .Select(x => new { ContestantID = x.Key, Count = x.Count() })
            .ToDictionary(x => x.ContestantID, x => x.Count);

    var votesForContestant2 = votesPerContestant[2];

    var contestantsWithNoVotes =
        Enumerable
            .Range(1, thingsToVoteOn)
            .Where(x => !votesPerContestant.ContainsKey(x))
            .ToArray();

Я не знаю, что вы подразумеваете под «фактическими бюллетенями для данного участника, где count() = n»поэтому я не смог ответить на этот вопрос.

Теперь, так как вы пытаетесь создать систему голосования, маловероятно, что Parallel LINQ поможет, поскольку вам нужно сравнить всех кандидатов друг с другом И у вас есть относительнонебольшой набор значений для работы.Parallel LINQ работает лучше всего, когда вы выполняете независимые вычисления для большого набора значений.

Кроме того, я предполагаю, что вы хотите использовать либо TPL, либо Rx для имитации одного голосования, приходящего за раз и позволяющего системе производить статистикуна каком кандидате в данный момент побеждает?Это идеальный сценарий для Rx, но вам нужно больше подробностей о том, как вычислить победителя, чтобы я мог дать вам какие-либо предложения по этому поводу.

---

А вот код для определения победителя с использованием АльтернативыМетод голосования:

    var ballots = BallotsToTally.Select(x => x.Entries.OrderBy(y => y.OrderedPreferenceForContestant).Select(y => y.ContestantID).ToArray()).ToArray();
    var active = Enumerable.Range(1, thingsToVoteOn).ToList();
    var top = (IGrouping<int, int>)null;

    while (active.Count() > 0)
    {
        var votes =
            from a in active
            join v in ballots.Select(x => x.Where(y => active.Contains(y)).FirstOrDefault()).Where(x => x != 0) on a equals v into gvs
            select new { candidate = a, votes = gvs.Count() };

        var ranks =
            votes
                .OrderByDescending(x => x.votes)
                .ThenBy(x => x.candidate)
                .GroupBy(x => x.votes, x => x.candidate)
                .ToArray();

        top = ranks.First();

        Console.WriteLine(String.Join(Environment.NewLine, ranks.Select(x => $"{x.Key} votes for {String.Join(", ", x)}")));
        Console.WriteLine();

        foreach (var candidate in ranks.Last())
        {
            active.Remove(candidate);
        }
    }

    Console.WriteLine($"Winner(s) {top.Key} votes for {String.Join(", ", top)}");

Если мы начнем с:

    var numberOfBallots = 500;
    var thingsToVoteOn = 10;

..., то это примерный прогон:

64 votes for 5
54 votes for 2
51 votes for 1
50 votes for 7
49 votes for 4
48 votes for 8
47 votes for 6, 10
46 votes for 3
44 votes for 9

67 votes for 5
59 votes for 2
56 votes for 7
55 votes for 10
54 votes for 1
53 votes for 3
52 votes for 4, 6
49 votes for 8

69 votes for 5
66 votes for 7
64 votes for 2
62 votes for 10
58 votes for 4, 6
57 votes for 1
54 votes for 3

77 votes for 5
75 votes for 7
72 votes for 2
68 votes for 10
66 votes for 4
64 votes for 1
60 votes for 6

85 votes for 5
82 votes for 2
81 votes for 4
80 votes for 7
75 votes for 10
70 votes for 1

96 votes for 5
94 votes for 2
93 votes for 4
92 votes for 7
79 votes for 10

114 votes for 4
113 votes for 2
111 votes for 5
104 votes for 7

142 votes for 4
137 votes for 2, 5

261 votes for 4

Winner(s) 261 votes for 4