Как получить первые n элементов на группу в отсортированном списке с помощью Ramda JS - PullRequest
Новая
       11

Как получить первые n элементов на группу в отсортированном списке с помощью Ramda JS

1 голос
/ 14 января 2020

Я довольно новичок в Ramda JS и функциональном программировании, поэтому я надеялся понять, есть ли более эффективный способ добиться следующего.

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

const footballers = [
  {
    name: "Mesut Ozil",
    team: "Arsenal",
    pay: 1400000
  },
  {
    name: "Lionel Messi",
    team: "Barcelona",
    pay: 7300000
  },
  {
    name: "Kylian Mbappe",
    team: "PSG",
    pay: 1500000
  },
  {
    name: "Alexis Sanchez",
    team: "Manchester United",
    pay: 1990000
  },
  {
    name: "Philippe Coutinho",
    team: "Barcelona",
    pay: 2000000
  },
  {
    name: "Neymar",
    team: "PSG",
    pay: 2700000
  },
  {
    name: "Luis Suarez",
    team: "Barcelona",
    pay: 2500000
  },
  {
    name: "Antoine Griezmann",
    team: "Atletico Madrid",
    pay: 2900000
  },
  {
    name: "Gareth Bale",
    team: "Real Madrid",
    pay: 2200000
  },
  {
    name: "Cristiano Ronaldo",
    team: "Juventus",
    pay: 4100000
  }
]

Я могу sh упорядочить этот список за плату, но ограничить каждую команду максимум двумя игроками в финальном списке. В настоящее время мое решение должно сортировать список дважды. В данный момент он сортируется в начале, а затем в окончательном списке, но он также может сортироваться после группировки по командам. Я полагаю, что есть более разумное (но все еще читаемое) решение, которое требует только одного вида, но я не уверен, что это такое. 

const byPayAsc = ascend(prop('pay')) // spare, for checking
const byPayDes = descend(prop('pay'))
const sortByPay = sort(byPayDes)

const groupedByTeam = compose(values, groupBy(prop('team')))
const topTwoPlayers = map(take(2))

const topTwoHighestPaidPlayersPerTeam = pipe( 
  sortByPay,
  groupedByTeam, 
  topTwoPlayers, 
  flatten, 
  sortByPay
)

topTwoHighestPaidPlayersPerTeam(footballers)

Мое текущее расследование обнаружило несколько вариантов:

  • Я слышал о преобразователях, которые, я думаю, могли бы обеспечить преимущество только однократного просмотра списка.
  • Мне также было интересно, можно ли было бы использовать функцию сортировки для объединения сгруппированных списков?
  • Или я мог бы написать редуктор до l oop через список списков и взять 2 лучших на команду.

Что такое идиоматический c способ сделать это с Рамдой JS.

Ответы [ 4 ]

1 голос
/ 15 января 2020

Ради простоты я бы просто написал пользовательскую функцию filter ... 

const playersPerTeam = (n) => {
  const teams = {};
  
  const predicate = (({ team }) => {
    teams[team] = (teams[team] || 0) + 1;
    
    return teams[team] <= n;
  });
  
  return R.filter(predicate);
};

const fn = R.pipe(
  R.sort(R.descend(R.prop('pay'))),
  playersPerTeam(2),
);

// ------

const data = [
  {
    name: "Mesut Ozil",
    team: "Arsenal",
    pay: 1400000
  },
  {
    name: "Lionel Messi",
    team: "Barcelona",
    pay: 7300000
  },
  {
    name: "Kylian Mbappe",
    team: "PSG",
    pay: 1500000
  },
  {
    name: "Alexis Sanchez",
    team: "Manchester United",
    pay: 1990000
  },
  {
    name: "Philippe Coutinho",
    team: "Barcelona",
    pay: 2000000
  },
  {
    name: "Neymar",
    team: "PSG",
    pay: 2700000
  },
  {
    name: "Luis Suarez",
    team: "Barcelona",
    pay: 2500000
  },
  {
    name: "Antoine Griezmann",
    team: "Atletico Madrid",
    pay: 2900000
  },
  {
    name: "Gareth Bale",
    team: "Real Madrid",
    pay: 2200000
  },
  {
    name: "Cristiano Ronaldo",
    team: "Juventus",
    pay: 4100000
  },
];

console.log(
  fn(data),
);
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js" integrity="sha256-xB25ljGZ7K2VXnq087unEnoVhvTosWWtqXB4tAtZmHU=" crossorigin="anonymous"></script>
1 голос
/ 15 января 2020

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

const { descend, prop, take, sort, reduceBy, pipe, values, reduce } = R

const sorter = descend(prop('pay'))

// this is used by `R.reduceBy` below to build up the sorted list with a max size
const addToGroup = (size, compare) => (group, a) =>
  take(size, sort(sorter, [a, ...group]))

const sortByTeam = reduceBy(addToGroup(2, sorter), [], prop('team'))

// recursively merges two sorted(!) lists by the given comparator
const mergeListsBy = compare => {
  const go = (xs, ys) =>
    xs.length == 0 ? ys :
    ys.length == 0 ? xs :
    compare(xs[0], ys[0]) < 0 ? [xs[0], ...go(xs.slice(1), ys)] :
                                [ys[0], ...go(xs, ys.slice(1))]
  return go
}

const run = pipe(sortByTeam, values, reduce(mergeListsBy(sorter), []))

////

const footballers = [{"name": "Mesut Ozil", "pay": 1400000, "team": "Arsenal"}, {"name": "Lionel Messi", "pay": 7300000, "team": "Barcelona"}, {"name": "Kylian Mbappe", "pay": 1500000, "team": "PSG"}, {"name": "Alexis Sanchez", "pay": 1990000, "team": "Manchester United"}, {"name": "Philippe Coutinho", "pay": 2000000, "team": "Barcelona"}, {"name": "Neymar", "pay": 2700000, "team": "PSG"}, {"name": "Luis Suarez", "pay": 2500000, "team": "Barcelona"}, {"name": "Antoine Griezmann", "pay": 2900000, "team": "Atletico Madrid"}, {"name": "Gareth Bale", "pay": 2200000, "team": "Real Madrid"}, {"name": "Cristiano Ronaldo", "pay": 4100000, "team": "Juventus"}]

console.log(run(footballers))
<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
1 голос
/ 15 января 2020

Односортное решение

Подход, который на самом деле избегает второго рода, безусловно, возможен. Вот одна версия, которая делает это: 

const topTwoHighestPaidPlayersPerTeam = pipe (
  sort (descend (prop ('pay'))),
  reduce (
    ({result, counts}, player, {team} = player) => ({
      result: counts [team] >= 2 ? result : [...result, player], 
      counts: {...counts, [team]: (counts[team] || 0) + 1}
    }),
    {result: [], counts: {}}
  ),
  prop ('result')
)

const footballers = [{"name":"Mesut Ozil","team":"Arsenal","pay":1400000},{"name":"Lionel Messi","team":"Barcelona","pay":7300000},{"name":"Kylian Mbappe","team":"PSG","pay":1500000},{"name":"Alexis Sanchez","team":"Manchester United","pay":1990000},{"name":"Philippe Coutinho","team":"Barcelona","pay":2000000},{"name":"Neymar","team":"PSG","pay":2700000},{"name":"Luis Suarez","team":"Barcelona","pay":2500000},{"name":"Antoine Griezmann","team":"Atletico Madrid","pay":2900000},{"name":"Gareth Bale","team":"Real Madrid","pay":2200000},{"name":"Cristiano Ronaldo","team":"Juventus","pay":4100000}]

const result = topTwoHighestPaidPlayersPerTeam(footballers)

console .log (result)
<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
<script> const {pipe, sort, descend, prop, reduce} = R                   </script>

Мы начинаем со стандартной сортировки по заработной плате, а затем перебираем их, отслеживая количество команд в группе вместе с результатами, добавляя команду всякий раз, когда подсчитываем меньше нашего максимума в 2. Мы отслеживаем это, накапливая объект с результатами и подсчетами. В конце мы просто извлекаем свойство results. Хотя это можно сделать с помощью filter вместо reduce, функция, переданная в filter, должна будет поддерживать состояние counts, что кажется плохим соответствием для filter.

Немного более очевидная версия 

      result: counts [team] < 2 ? [...result, player] : result,

не будет работать, потому что изначально количество команд не определено, а undefined < 2 дает false. Вместо этого мы могли бы выбрать эту версию, если она кажется более понятной: 

      result: (counts [team] || 0) < 2 ? [...result, player] : result,

Почему нам, вероятно, не следует использовать это решение

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

Решение с двумя сортировками по-прежнему O (n log (n)); выполнение чего-либо дважды не меняет показатель общей производительности c. Так что эта версия не асимптотически быстрее двухсортиментной. Но код не так читаем как Скотт Кристофер или Ори Дрори. Если мы не измерили и не можем указать на c узких мест, добавление сложности в наш код по соображениям производительности кажется полной тратой.

Поэтому я бы порекомендовал решение от Ori Drori по этому поводу. И у Скотта Кристофера также есть интересный подход.

Но этот вид техники все еще часто полезен для поддержания некоторого дополнительного состояния при сворачивании списка значений.

1 голос
/ 15 января 2020

Ваша идея повторной сортировки верна, поскольку группировка игроков по командам меняет первоначальную сортировку.

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

Однако, чтобы проверить идею, этот фрагмент преобразовывает элементы массива в пары [index, player] после сортировки, но перед группировкой по команде игрока. , Когда вы выравниваете группы обратно в массив, используя R.values ​​и R.chain (с R.take), вы конвертируете пары обратно в объект, используя R.fromPairs. Поскольку в ES6 обход целочисленных ключей объекта идет по возрастанию, исходный порядок восстанавливается, и теперь вы получаете массив путем повторного вызова R.values. 

const { pipe, sort, descend, prop, toPairs, groupBy, path, values, chain, take, fromPairs } = R

const topTwoHighestPaidPlayersPerTeam = pipe( 
  sort(descend(prop('pay'))), // sort descending by pay
  toPairs, // convert to pairs if [index, player object]
  groupBy(path([1, 'team'])), // group by the team
  values, // get an array of an arrays 
  chain(take(2)), // flatten and take the 1st two items of each group
  fromPairs, // convert to an object of objects with original index as key
  values // convert to an array in the correct order
)

const footballers = [{"name":"Mesut Ozil","team":"Arsenal","pay":1400000},{"name":"Lionel Messi","team":"Barcelona","pay":7300000},{"name":"Kylian Mbappe","team":"PSG","pay":1500000},{"name":"Alexis Sanchez","team":"Manchester United","pay":1990000},{"name":"Philippe Coutinho","team":"Barcelona","pay":2000000},{"name":"Neymar","team":"PSG","pay":2700000},{"name":"Luis Suarez","team":"Barcelona","pay":2500000},{"name":"Antoine Griezmann","team":"Atletico Madrid","pay":2900000},{"name":"Gareth Bale","team":"Real Madrid","pay":2200000},{"name":"Cristiano Ronaldo","team":"Juventus","pay":4100000}]

const result = topTwoHighestPaidPlayersPerTeam(footballers)

console.log(result)
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js"></script>
...