Алгоритм скоростного датирования для выбора пары дат

  

Давайте скажем, что 10 мальчиков и 10 девочек на скорости.   10 мальчиков выбирают 4 девочки и оценивают их.   10 девочек выбирают 4 мальчика и оценивают их.   В итоге возвратные пары будут возвращены.

Более подробные сведения, такие как тай-брейки, правила входных параметров и т. д., хорошо документированы. Ищите обзор кода, оптимизацию и лучшие практики.

final class Pair {

    private final String male;
    private final String female;

    public Pair(String male, String female) {
        this.male = male;
        this.female = female;
    }

    public String getMale() {
        return male;
    }

    public String getFemale() {
        return female;
    }

    @Override
    public String toString() {
        return male + "  dates: " + female;
    }
}

/**
 * 
 * Provides a thread safe solution Solves the speed date problem.
 * 
 * Example:
 * --------
 * - Lets say there are 10 boys and 10 girls in speed date
 * - 10 boys  select 4 girls and rank them.
 * - 10 girls select 4 boys  and rank them.
 * - in the end the winning pairs would be returned.
 * 
 * Complexity:
 * Time complexity: O(nlogn)
 * Space complexity: O(n)
 * 
 */
public class SpeedDateCompute {

    private final Map<String, List<String>> maleChoices;
    private final Map<String, List<String>> femaleChoices;

    /**
     * Does not make a deep copy of maps thus client is not expected to change maleChoice, femaleChoice.
     * Expects consistency in males and female maps, else results are unpredictable.
     * 
     * By consistency it means:
     * - The number of boys and girls should be the same.
     * - Each boy and each girl should make same number of choices
     * - Choices should mention "only existing members of opposite sex"
     * 
     * 
     * @param maleChoices
     * @param femaleChoices
     */
    public SpeedDateCompute(Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
        validate(maleChoices, femaleChoices);

        this.maleChoices = maleChoices;
        this.femaleChoices = femaleChoices;
    }

    private static class Edge {
        String male;
        String female;
        int malesPreference;  // what does male   ranks this female ?
        int femalePreference; // what does female ranks this male ?

        Edge (String male, String female, int malesPreference, int femalePreference) {
            this.male = male;
            this.female = female;
            this.malesPreference = malesPreference;
            this.femalePreference = femalePreference;
        }
    }

    private static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge edge1, Edge edge2) {
            int val = rank (edge1.femalePreference - 1, edge1.malesPreference - 1)
                    - rank (edge2.femalePreference - 1, edge2.malesPreference - 1);
            return val;
        }

        /*
         * Ranking algorithm. 
         * 
         * Let notation (1,2) mean - femalePrerence is 1 and malePreference is 2.
         * (1, 1) means both rank each other as their best so this pair triumps over (2, 2)
         * but there is a tie between (1, 2) and (2, 1)
         * As a tie breaker we give preference to feelings of women 
         * thus (1,2) > (2, 1)
         * 
         * Thus the rule is expanded to 
         * 
         * (1, 1) > (1, 2) > (2, 1) > (2, 2)
         * 
         * This can be thought of as a matrix of the form
         * (lil lazy to retype the whole thing, plz check the link)
         * http://math.stackexchange.com/questions/720797/whats-the-name-of-this-sort-of-matrix
         * http://codereview.stackexchange.com/questions/44939/a-matrix-with-square-diagonals-and-transpose-being-increments-of-other
         * 
         * @param row   the female choice
         * @param col   the male choice
         * @return      
         */
        private int rank(int row, int col) {
            if (row == col) {
                return row * row;
            }

            int rank = (col) * (col) + 1 + (2 * row) ;

            if (row < col) {
                return rank;
            } else {
                return rank + 1;
            }
        }
    }

    private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
        if (maleChoices == null || femaleChoices == null) {
            if (maleChoices != null) {
                throw new NullPointerException("female choice map should not be null");
            }
            if (femaleChoices != null) {
                throw new NullPointerException("male choice map should not be null");
            }
            throw new NullPointerException("no choice map should be null.");
        }

        if (maleChoices.size() == 0 || femaleChoices.size() == 0) {
            if (maleChoices.size() == 0) {
                throw new IllegalArgumentException("male choice map should not be empty.");
            }
            if (femaleChoices.size() == 0) {
                throw new IllegalArgumentException("female choice map should not be empty.");
            }
            throw new IllegalArgumentException("no choice map should be empty.");
        }
    }


    public List<Pair> getPairs() {
        final Collection<Edge> edges = parseChoiceMaps();
        final List<Edge> sortedEdges = sort(edges);
        return createPairs(sortedEdges);
    }

    /**
     * Given a directed bipartite graph, it converts bipartite graph into 
     * undirected map.
     * 
     * @param choiceMap the bipartite graph of choices
     * @return 
     */                 
    private Collection<Edge> parseChoiceMaps() {

        final Map<String, Edge> combinedMaleChoice = new HashMap<String, Edge>();

        synchronized (maleChoices) {
            // parsing male choices.
            for (Entry<String, List<String>> maleChoice : maleChoices.entrySet()) {
                String maleName = maleChoice.getKey();
                List<String> females = maleChoice.getValue();
                for (int i = 0; i < females.size(); i++) {
                    // mark female preference as "size" thus assigning the worst rank as default.
                    combinedMaleChoice.put(maleName + females.get(i), new Edge(maleName, females.get(i), i + 1,
                            maleChoices.size()));
                }
            }
        }

        synchronized (femaleChoices) {
            // parsing female choices
            for (Entry<String, List<String>> femaleChoice : femaleChoices.entrySet()) {
                List<String> males = femaleChoice.getValue();
                for (int i = 0; i < males.size(); i++) {
                    String name = males.get(i) + femaleChoice.getKey();
                    // check if any male has chosen this female, else skip.
                    if (combinedMaleChoice.containsKey(name)) {
                        combinedMaleChoice.get(males.get(i) + femaleChoice.getKey()).femalePreference = i + 1;
                    }
                }
            }
        }

        return combinedMaleChoice.values();
    }


    private List<Edge> sort(Collection<Edge> edges) {
        final List<Edge> edgeList = new ArrayList<Edge>(edges);
        Collections.sort(edgeList, new EdgeComparator());
        return edgeList;
    }

    private List<Pair> createPairs(List<Edge> edges) {
        final Set<String> hookedUpMales = new LinkedHashSet<String>();
        final Set<String> hookedUpFemales = new LinkedHashSet<String>();

        for (Edge edge : edges) {            
            if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
                continue;
            }
            hookedUpMales.add(edge.male);
            hookedUpFemales.add(edge.female);
        }

        return mapSetsToPairs(hookedUpMales, hookedUpFemales);
    }

    private List<Pair> mapSetsToPairs(Set<String> hookedUpMales, Set<String> hookedUpFemales) {
        Iterator<String> maleItr = hookedUpMales.iterator();
        Iterator<String> femaleItr = hookedUpFemales.iterator(); 

        final List<Pair> pairs = new ArrayList<Pair>();

        while (maleItr.hasNext() && femaleItr.hasNext()) {
            pairs.add(new Pair(maleItr.next(), femaleItr.next()));
            maleItr.remove();   // just to optimize space
            femaleItr.remove(); // just to optimize space
        }
        return pairs;
    }


    public static void main(String[] args) {
        /*
         * Test case 1
         */
        Map<String, List<String>> maleChoice1 = new HashMap<String, List<String>>();
        Map<String, List<String>> femaleChoice1 = new HashMap<String, List<String>>();

        maleChoice1.put("male1", Arrays.asList("female1", "female2"));
        maleChoice1.put("male2", Arrays.asList("female2", "female1"));
        femaleChoice1.put("female1", Arrays.asList("male1", "male2"));
        femaleChoice1.put("female2", Arrays.asList("male2", "male1"));
        SpeedDateCompute speedDateCompute = new SpeedDateCompute(maleChoice1, femaleChoice1);
        List<Pair> actualValues = speedDateCompute.getPairs();
        assertEquals("male1", actualValues.get(0).getMale());
        assertEquals("female1", actualValues.get(0).getFemale());
        assertEquals("male2", actualValues.get(1).getMale());
        assertEquals("female2", actualValues.get(1).getFemale());

        /*
         * Test case 2
         */
        Map<String, List<String>> maleChoice2 = new HashMap<String, List<String>>();
        Map<String, List<String>> femaleChoice2 = new HashMap<String, List<String>>();
        maleChoice2.put("male1", Arrays.asList("female2", "female1"));
        maleChoice2.put("male2", Arrays.asList("female1", "female2"));
        maleChoice2.put("male3", Arrays.asList("female1", "female2"));
        femaleChoice2.put("female1", Arrays.asList("male2", "male1"));
        femaleChoice2.put("female2", Arrays.asList("male1", "male2"));
        femaleChoice2.put("female3", Arrays.asList("male1", "male2"));
        speedDateCompute = new SpeedDateCompute(maleChoice2, femaleChoice2);
        actualValues = speedDateCompute.getPairs();

        assertEquals("male1", actualValues.get(0).getMale());
        assertEquals("female2", actualValues.get(0).getFemale()); 
        assertEquals("male2", actualValues.get(1).getMale());
        assertEquals("female1", actualValues.get(1).getFemale());

        assertEquals(2, actualValues.size());
    }
}
11 голосов | спросил JavaDeveloper 26 MaramWed, 26 Mar 2014 10:07:37 +04002014-03-26T10:07:37+04:0010 2014, 10:07:37

3 ответа


10

Этот код действительно красив и хорошо документирован. Есть очень мало частей, которые можно критиковать:

  • Не используйте объекты, где они неприменимы. Класс SpeedDateCompute по существу характеризуется только его кодом getPairs. Мы могли бы также сделать это static и вызывать его как SpeedDateCompute.getPairs(maleChoices, femaleChoices).

    Такие классы однокомпонентного метода, которые кодируют алгоритм, должны быть только реальными, если нам нужно передать алгоритм вокруг как объект.

  • Ваш validate слишком сложный. Этот рефакторинг дает почти как хорошие сообщения об ошибках, но менее запутанно читать.

    private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
        if (femaleChoices == null) {
            throw new NullPointerException("female choice map should not be null");
        }
        if (maleChoices == null) {
            throw new NullPointerException("male choice map should not be null");
        }
    
        if (maleChoices.size() == 0) {
            throw new IllegalArgumentException("male choice map should not be empty.");
        }
        if (femaleChoices.size() == 0) {
            throw new IllegalArgumentException("female choice map should not be empty.");
        }
    }
    
  • Синхронизация по maleChoices и femaleChoices мало смысла. В вашей документации уже указано, что клиент « не должен изменять« maleChoice, femaleChoice ». Я бы оставил это с этим и надеюсь, что любые пользователи этого класса не настолько безумны, чтобы делиться этими данными между потоками. Синхронизация - довольно дорогостоящая операция, поэтому я бы хотел избежать ее, если она не нужна, и выгрузить ответственность за клиента.

  • Ключи в combinedMaleChoice - это простая совпадение мужских и женских имен. Хотя на практике это маловероятно, это может привести к столкновениям (в строках "AA" + "B" vs. "A" + "AB"). Вместо этого вы можете использовать Map<String, Map<String, Edge>> или разделитель, который гарантированно не встречается в имени: maleName + "\0" + femaleName

    Это часть более крупной проблемы, которая не уникальна. Для реального кода вам нужен уникальный идентификатор. Это одна из причин, по которой я хотел бы инкапсулировать вовлеченных лиц в собственный класс, например:

    public static abstract class Person<Likes extends Person> {
        private final String name;
        private final List<Likes> likes = new ArrayList<>();
    
        public Person(String name) {
            this.name = name;
        }
    
        public String name() {
            return this.name;
        }
    
        public List<Likes> likes() {
            return this.likes;
        }
    
        public List<Likes> likes(List<Likes> others) {
            this.likes.addAll(others);
            return this.likes;
        }
    
        @Override
        public String toString() {
            return this.name();
        }
    
        // "equals" defaults to pointer equivalence, which is what we want
    }
    
    public static class Male extends Person<Female> {
        public Male(String name) {
            super(name);
        }
    
        @Override
        public boolean equals(Object that) {
            return that instanceof Male && super.equals(that);
        }
    }
    
    public static class Female extends Person<Male> {
        public Female(String name) {
            super(name);
        }
    
        @Override
        public boolean equals(Object that) {
            return that instanceof Female && super.equals(that);
        }
    }
    

    Это также позволяет нам лучше использовать систему типов, чем полагаться на String s - недостатком является то, что клиенту потребуется больше код инициализации для подготовки кода Person.

  • Нет существенной разницы между Pair и Edge. Я бы объединил оба в один класс.

  • Вы сделали код намного сложнее, чем нужно, разделив логику на createPairs и mapSetsToPairs. Вы создаете два LinkedHashSet s, а затем итерации по ним параллельно. Мы можем сделать все это в одном цикле:

    private List<Pair> createPairs(List<Edge> edges) {
        final Set<String> hookedUpMales = new HashSet<>();
        final Set<String> hookedUpFemales = new HashSet<>();
        final List<Pair> hookedUpPairs = new ArrayList<>();
    
        for (Edge edge : edges) {
            if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
                continue;
            }
            hookedUpPairs.add(new Pair(edge.male, edge.female));
            hookedUpMales.add(edge.male);
            hookedUpFemales.add(edge.female);
        }
    
        return hookedUpPairs;
    }
    
  • Если вы ориентируетесь на Java 7, вам не нужно указывать все дженерики и вместо этого использовать оператор бриллианта:

    // final List<Edge> edgeList = new ArrayList<Edge>(edges);
    final List<Edge> edgeList = new ArrayList<>(edges);
    
  • Ваши тесты не работают. Хотя вы гарантируете, что вы вернете оптимальные пары, вы не гарантируете никакого заказа, когда две пары имеют одинаковые предпочтения. Поэтому в вашем первом тесте actualValues.get(0).getMale() может быть male2, а не male1. Вместо этого:

    1. Проверьте правильность количества возвращенных пар.
    2. Проверьте, что набор пар contains ожидаемая пара. Это означает, что вы должны переопределить equals и hashCode для класса Pair.
  • В parseChoiceMaps вы назначаете i + 1 в качестве предпочтения, а затем уменьшайте это значение при расчете своего ранга. Этот индекс перетасовывает серверы без цели и может быть удален с использованием нулевых настроек

Я немного переработал, в том числе. вводя класс Person и объединяющий Edge и Pair, и результат на самом деле довольно приятный: http: //ideone.com/RSTcUu

Дальнейшие наблюдения:

  • ВашJavaDoc содержит Markdown-подобные списки. IIRC, вы можете использовать ограниченное подмножество HTML для форматирования.

  • Ваш алгоритм ранжирования кажется ужасно ошибочным. Я понимаю, что вам нужен какой-то абсолютный порядок, но измененное расстояние Манхэттена или Евклидово расстояние, вероятно, сделало бы лучшую работу. Например, с помощью f = 10, m = 0 (где f является предпочтение женщины, m мужчина предпочтение), мы получаем ранг 22. Теперь у нас может быть другое ребро с f = 0, m = 9. Я ожидаю, что это второе ребро будет отсортировано до первого. Но он имеет ранг 101, что намного хуже! Другими словами, выбор самцов взвешен более тяжело.

    Связанная проблема заключается в том, что вы назначаете предпочтение женщинам, даже если они не проявляют интереса к этому конкретному мужчине. Например, рассмотрим следующее:

    male1 likes female1
    male2 likes female2
    female1 likes male1
    female2 likes male1
    

    Ожидается спаривание male1 – female1, как и у друг друга. Однако male2 – female2 сомнительно. Из-за вашей реализации обратное неверно:

    male1 likes female1
    male2 likes female1
    female1 likes male1
    female2 likes male2
    

    возвращает только male1 – female1.

    Лучшее ранжирование, использующее женские рейтинги для разрыва связей, может быть измененным расстоянием Манхэттена:

    rank = (m + f) * max + f
    

    или эвклидовое расстояние:

    rank = (int) (Math.sqrt(m*m + f*f) * max + f)
    

    где max - максимальная оценка, участвующая в этом сравнении.

ответил amon 26 MarpmWed, 26 Mar 2014 19:27:08 +04002014-03-26T19:27:08+04:0007 2014, 19:27:08
8

Вычислительно говоря, у меня нет ничего, чтобы добавить то, что уже было сказано. @amon действительно сделал полный обзор вашего кода. Однако в вашем коде есть серьезные социологические и /или этические недостатки. Я бы сказал, что, с гендерной точки зрения, его можно было бы сделать более общим:

  • Сексуальная ориентация: Прежде всего, вы предполагаете, что мальчики любят девушек, а девочки любят мальчиков. Это неверно. Вы должны были бы учитывать и гомосексуальных, и бисексуальных людей. Это означало бы, что ваши экземпляры Person также должны иметь переменную, определяющую, что такое сексуальная ориентация экземпляра. Вы могли бы использовать процент, чтобы приблизительно представить, интересуются ли субъекты мужчинами или женщинами; этот процент можно было бы учитывать в алгоритме оценки.
  • Пол: , если мы ограничимся только биологией и биологическими ценностями, вы полностью игнорируете межпозвоночных людей. Это может быть очень оскорбительным, поскольку многим из них трудно найти место в обществе и попытаться соответствовать одному полу, в то время как нет «преданного» пола для межпозвоночных людей. Это может показаться оскорблением. Кроме того, некоторые пытаются предположить интерсексуальную идентичность вместо того, чтобы пытаться соответствовать «мужчинам» и «женщине».
  • Пол: , мы можем смело предположить, что сокращение людей до того, что у них между ногами, - плохая идея. Поэтому вы могли бы рассмотреть их пол. Тем не менее, у вас возникнут проблемы: существует столько гендер, сколько мы можем думать (например, недавно добавленный Facebook 56 гендерных вариантов вместо того, чтобы закончить« мужчин »и« женщин »). С нынешним дизайном ваш код станет слишком сложным, если вы попытаетесь представить даже самые известные.

В заключение, одним из решений было бы сделать два списка Individual s. Это не только было бы более уважительно относиться ко многим людям в мире, но вы также могли бы избавиться от своего кода Male и Female: это сделает ваш код более общим, хотя, вероятно, короче и проще. Всюду вы имеете имена переменных, содержащие male или female, вы можете заменить их на person1 и person2 или individual1 и individual2. Более того, такая типичность позволит вашему коду быть адаптирована к более сложным проблемам (например, проблема Ménage à trois .)

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

ответил Morwenn 26 MarpmWed, 26 Mar 2014 20:01:25 +04002014-03-26T20:01:25+04:0008 2014, 20:01:25
5

Выглядит хорошо, я не работал с логикой ваших алгоритмов, но, как правило, смотрел, можно ли сделать что-то более эффективно, и ничто не привлекло мое внимание.

Один комментарий, который у меня есть, относится к вашему методу validate (), он проверяет наличие пустых и пустых карт, но я считаю, что у вас есть дополнительное требование, чтобы они были одного размера? Если это так, это должно быть частью метода validate ().

ответил Dan 26 MarpmWed, 26 Mar 2014 16:19:32 +04002014-03-26T16:19:32+04:0004 2014, 16:19:32

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132