JS: написание функции, которая выполняет итерацию по списку строк и возвращает 10 наиболее часто встречающихся строк в списке

это хорошая проблема для уменьшения карты. :-)

const list = [
  "this",
  "is",
  "a",
  "test",
  "which",
  "word",
  "wins",
  "top",
  "i",
  "don't",
  "know",
  "off",
  "hand",
  "do",
  "you",
  "this",
  "a",
  "a",
  "this",
  "test",
  "a",
  "a",
  "do",
  "hand",
  "hand",
  "a",
  "whatever",
  "what",
  "do",
  "do"
];

const counts = list.reduce((a, c) => {
  a[c] = (a[c] || 0) + 1;
  return a;
}, {})
const items = Object.keys(counts).map(k => {
  return {
    word: k,
    count: counts[k]
  };
});
items.sort((a, b) => a.count > b.count ? -1 : 1);
const result = items.slice(0, 10).map(item => item.word);
console.info(result);

Попробуй это:

const list = [
    "this",
    "is",
    "a",
    "test",
    "which",
    "word",
    "wins",
    "top",
    "i",
    "don't",
    "know",
    "off",
    "hand",
    "do",
    "you",
    "this",
    "a",
    "a",
    "this",
    "test",
    "a",
    "a",
    "do",
    "hand",
    "hand",
    "a",
    "whatever",
    "what",
    "do",
    "do"
  ];


let counter = {}
for (let item of list){
    counter[item] = 1 + (counter[item] || 0)
}
console.info(counter);

let result = [];
let entries = Object.entries(counter);
let sorted = entries.sort((a, b) => b[1] - a[1]);

for(let i = 0; i < 10; i++){
    result.push(sorted[i][0])
}

console.info(result)

const list = [
  "this",
  "is",
  "a",
  "test",
  "which",
  "word",
  "wins",
  "top",
.
.
.
  "do",
  "do"
];

const newObjectArray = {};

list.forEach(item=>{
   newObjectArray[item]? newObjectArray[item]++: newObjectArray[item] = 1
});

// now sort based on the newObjectArray  values and return the first 10

Я думаю, что мы можем сделать следующие шаги для больших данных:

1. Сопоставление необработанного объекта со структурой карты;
2. Пройдитесь по карте, чтобы найти на этот раз 1 наиболее часто встречающуюся строку;
3. Удалить топ 1 с карты;
4. Повторить 2.

Вот код:

const list = [
    "this",
    "is",
    "a",
    "test",
    "which",
    "word",
    "wins",
    "top",
    "i",
    "don't",
    "know",
    "off",
    "hand",
    "do",
    "you",
    "this",
    "a",
    "a",
    "this",
    "test",
    "a",
    "a",
    "do",
    "hand",
    "hand",
    "a",
    "whatever",
    "what",
    "do",
    "do"
];

// mock 1 million data;
for (let i = 0; i < 1000000; i++) {
    list.push('a');
}

console.clear();
let resultsmap = new Map();

// Object to map with frequent times
function toMap() {
    for (let i = 0; i < list.length; i++) {
        let item = list[i];
        if (resultsmap.has(item)) {
            let count = resultsmap.get(item);
            resultsmap.set(item, count + 1);
        } else {
            resultsmap.set(item, 1);
        }
    }
}

// Found the top 1 for current map
function top1() {
    let maxCount = 0;
    let keyOfMaxCount = '';
    resultsmap.forEach((value, key) => {
        if (maxCount < value) {
            maxCount = value;
            keyOfMaxCount = key;
        }
    });

    return { key: keyOfMaxCount, value: maxCount };
}

toMap();

for(let i=0; i< 10; i++) {
    let topObj = top1();
    console.info(topObj);
    resultsmap.delete(topObj.key);
}

Для этого есть два подхода, причем первый (простая сортировка) уже реализован самостоятельно. Сложность времени: O (N log N), поскольку вы переопределяете весь массив N раз, а затем сортируете N элементов, которые занимают N log N раз. Космическая сложность: O(N)

Второй подход будет заключаться в использовании кучи счетчиков (очередь с минимальным приоритетом, которая сначала выталкивает наименьшие счетчики), после каждой вставки мы проверяем, что, если размер кучи больше 10, мы выталкиваем последний 1, а затем вместо сортируя, мы просто выталкиваем последние 10 элементов. Временная сложность: O (N log k), где N — длина списка, а K — самые верхние строки, в вашем случае это 10. Это потому, что мы следим за тем, чтобы размер кучи не превышал K и с каждым вставить в кучу, он сортирует себя за время O (log K), что дает нам O (N log k) общей временной сложности. Космическая сложность: O(N)

Пример:

const list = [
  "this",
  "is",
  "a",
  ...
  "do"
];

const counts = {};

list.forEach(item=>{
   counts[item]? counts[item]++: counts[item] = 1;
});

// Now that counts is a map of {word -> count}, we need to add these into a priority queue and just pop.
// I will not be implementing a priority queue in this example, you can probably just find an npm package that implements it in a much more efficient way.

const priorityQueue = new PriorityQueue((a,b) => a.count - b.count); // you usually need to pass a comparator function

Object.entries(counts).forEach(([word, count]) => {
  priorityQueue.offer({word, count});
  if (priorityQueue.size() > 10)
    priorityQueue.pop();
}};

// now, just pop the first K (10) elements from the PriorityQueue:
for(let i=0; i<10; i++) {
  console.info(priorityQueue.pop())
}

Вот решение, которое позволяет избежать сортировки, собирая записи количества слов Map() в объекте по значению количества. Результатом будут последние 10 элементов в Object.entries() этого объекта. Следует отметить, что это основано на упорядочении объектных ключей, которое исторически было занижено, но, особенно для целочисленных ключей, используемых здесь, предлагает предсказуемое восходящее упорядочение в соответствии с обновлениями спецификации. – см.: Вводит ли ES6 четко определенный порядок перечисления свойств объекта?

Это решение имеет дополнительное преимущество, заключающееся в том, что оно возвращает массивы слов с одинаковым количеством, а не произвольное отсечение, которое вводят решения, использующие sort().

const input = [ "this", "is", "a", "test", "which", "word", "wins", "top", "i", "don't", "know", "off", "hand", "do", "you", "this", "a", "a", "this", "test", "a", "a", "do", "hand", "hand", "a", "whatever", "what", "do", "do"];

let counts = new Map(), i;
for (i = 0; i < input.length; i++) {
  counts.set(input[i], (counts.get(input[i]) ?? 0) + 1);
}

let countHash = {};
counts.forEach((count, word) => (countHash[count] ??= []).push(word));

let result = Object.entries(countHash);
if (result.length > 10) result = result.slice(result.length - 10);

// output
for (let j = result.length - 1; j >= 0; j--) {
  console.info(JSON.stringify(result[j]));
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

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

let countArr = [];
counts.forEach((count, word) => (countArr[count] ??= []).push(word));

Object.entries(), вызванный для разреженного массива, учитывает дыры и возвращает только существующие [key, value] пары. (Это верно для Object.keys(), а также для итерации с использованием for...in).

const input = [ "this", "is", "a", "test", "which", "word", "wins", "top", "i", "don't", "know", "off", "hand", "do", "you", "this", "a", "a", "this", "test", "a", "a", "do", "hand", "hand", "a", "whatever", "what", "do", "do"];

let counts = new Map(), i;
for (i = 0; i < input.length; i++) {
  counts.set(input[i], (counts.get(input[i]) ?? 0) + 1);
}

let countArr = [];
counts.forEach((count, word) => (countArr[count] ??= []).push(word));

let result = Object.entries(countArr);
if (result.length > 10) result = result.slice(result.length - 10);

// output
for (let j = result.length - 1; j >= 0; j--) {
  console.info(JSON.stringify(result[j]));
}

// Output of this answer
 [
   [6, ['a']],
   [4, ['do']],
   [3, ['this', 'hand']],
   [2, ['test']],
   [1, ['is', 'which', 'word', 'wins', 'top', 'i', "don't", 'know', 'off', 'you', 'whatever', 'what']]
 ]

// Output using sort
 [
   [6, 'a'],
   [4, 'do'],
   [3, 'this'],
   [3, 'hand'],
   [2, 'test'],
   [1, 'is'],
   [1, 'which'],
   [1, 'word'],
   [1, 'wins'],
   [1, 'top']
 ]
// [ 1, 'i' ],
// [ 1, "don't" ],
// [ 1, 'know' ], 
// [ 1, 'off' ],
// [ 1, 'you' ], 
// [ 1, 'whatever' ],
// [ 1, 'what' ]

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

Предполагая, что list такой же, как в вашем примере, превратите его в массивную строку:

const search = list.join(' ');

Почему? Потому что тогда вы можете подсчитывать вхождения с помощью RegExp#match, например,

search.match(/\bhand\b/g).length;
//=> 3

Конечно, регулярное выражение должно быть построено динамически. Мы сделаем это позже.

Затем превратите list в уникальный список:

const uniq_list = [...new Set(list)];

Затем вы можете отсортировать uniq_list, подсчитав, сколько раз каждый элемент появляется в search:

const ordered_by_occurrence =
  uniq_list.sort((a, b) => {
    const count_a = search.match(new RegExp(`\\b${a}\\b`, 'g')).length;
    const count_b = search.match(new RegExp(`\\b${b}\\b`, 'g')).length;
    return count_a >= count_b ? -1 : 1;
  });

(Возврат первых n элементов упорядоченного списка тривиален.)

Я считаю, что следующее решение является самым быстрым на практике:

1. Сопоставьте строки n с их частотами, как вы уже сделали. O(n)
2. Преобразуйте карту в массив с парами строк/частот. O(n)
3. Преобразуйте массив в Max-heap на основе частоты, используя метод Флойда (т. е. вызвав max-heapify для всех индексов от ⌊n/2⌋ - 1 до 0). O(n)
4. Извлеките верхний элемент k раз. (В вашем случае k=10.) O(k log n)

(Я не привожу здесь никакого кода, потому что он в основном состоит из вызова библиотеки двоичной кучи (см. здесь высокооптимизированную реализацию).)

Анализ

Асимптотическая сложность равна O(n + k log n), что меньше O(n log k) решения, предоставленного Chaos Monkey. Для маленьких k (например, 10), вероятно, не будет существенной разницы. Разница становится более очевидной для больших k (пока k ≪ n; для гораздо больших k см. «Альтернатива» ниже). Также обратите внимание, что постоянный коэффициент для шагов 1 и 2 равен 1, а постоянный коэффициент для шага 3 также в среднем мал (1,8814), поэтому общий постоянный коэффициент меньше 4.

Альтернатива

Существует решение, которое решает задачу в O(n) в среднем, также с небольшим постоянным множителем, что гораздо эффективнее при больших k (т.е. когда k приближается к n/2). Недостатком является то, что (очень маловероятно) сложность в худшем случае равна O(n²):

1. Сопоставьте строки n с их частотами, как вы уже сделали. O(n)
2. Преобразуйте карту в массив с парами строк/частот. O(n)
3. Примените Quickselect (точно так же, как Quicksort, но просто рекурсивно на одной стороне раздела), чтобы найти k-ю по величине частоту. Все элементы слева еще больше, поэтому в результате получаются первые k элементы массива Quickselected. O(n) среднее, O(n²) худшее.

Можно реализовать вариант Quickselect с гарантированной O(n) сложностью, используя медиану медиан опорного выбора, но на практике это не очень хорошо, потому что постоянный коэффициент довольно высок. Но с академической точки зрения это было бы асимптотически оптимальным решением.

(Вот JavaScript-библиотека для Quickselect, хотя на первый взгляд реализация не выглядит идеальной для этого случая: хорошая реализация должна выполнять трехстороннее разбиение в стиле Дейкстры.)

Ориентир

Быстрый и грязный тест с n = 10^6, k = 10, измеряющий только время выполнения после шага 2 (поскольку шаги 1/2 являются общими для всех 5 методов):

Average time for Sort: 7.5 ms
Average time for ChaosMonkey: 10.25 ms
Average time for CountingSort: 5.25 ms
Average time for Mo B. Max-Heap: 4 ms
Average time for Mo B. Alternative (Quickselect): 3.25 ms

https://dotnetfiddle.net/oHRMsp

Мой вывод состоит в том, что для заданных параметров между разными методами нет большой разницы. Для простоты я бы просто придерживался метода сортировки, который также хорошо масштабируется как для n, так и для k.

(Много предостережений: он написан (неряшливо) на C#, а не на JavaScript; он не проверялся на корректность; отдельные методы не оптимизированы; время выполнения также может зависеть от распределения частот, реализованный Quickselect наивен в том, что он не оптимизирован для (здесь) распространенного случая, когда множество частот равны и т. д...)

Последнее замечание о космосе

Все проверенные методы используют дополнительное пространство O(n), потому что они сначала создают карту частот (а метод сортировки подсчетом использует дополнительное пространство O(n) для наихудшего случая поверх карты частот для подсчета). Задачу можно решить всего за O(1) дополнительного места, но за счет временной сложности O(kn²).

Вы можете сделать это так...

const list = 
  [ "this", "is", "a", "test", "which", "word", "wins", "top"
  , "i", "don't", "know", "off", "hand", "do", "you", "this"
  , "a", "a", "this", "test", "a", "a", "do", "hand"
  , "hand", "a", "whatever", "what", "do", "do"
  ];

const getTopTen = arr =>
  [...new Set(arr)]
    .map(txt=>({txt, n:arr.filter(t=>t===txt).length}))
    .sort((a,b)=>b.n-a.n)
    .slice(0,10)
    .map(({txt,n})=>txt);

console.info( getTopTen(list) );

.as-console-wrapper { max-height: 100% !important; top: 0; }

второе решение без сортировки:

const list = 
  [ "this", "is", "a", "test", "which", "word", "wins", "top"
  , "i", "don't", "know", "off", "hand", "do", "you", "this"
  , "a", "a", "this", "test", "a", "a", "do", "hand"
  , "hand", "a", "whatever", "what", "do", "do"
  ];

function getTopTen(arr)
  {
  let res = []
    , max = 10
    , cnt = [...new Set(arr)]
      .reduce((occ,txt) => {                  // making of { occurences , [ ...terms ] }
        let n = arr.filter(t=>t===txt).length  // count of sames terms
          , p = occ.find(x=>x.n===n)           
          ;
        if (!p) {                              // new occurence
          p = { n, t:[] }
          let i = occ.findIndex(x=>x.n<n)      // check is place   
          if (i<0) occ.push(p)                 // on bottom, or
          else     occ.splice(i,0,p)           // just in right place
          }
        p.t.push(txt)                          // add the term in his occ list
        return occ
      },[])
    ;
  for (let c of cnt) {        // keep only the 10 first elments
    for (let t of c.t)
      { res.push(t); if (!--max) break }  // break loop on  
    if (!max) break                      // quota zero
    }
  return res 
  }

console.info( getTopTen(list) );

.as-console-wrapper { max-height: 100% !important; top: 0; }

Поскольку наш диапазон (частота слов) ограничен длиной списка, у нас может быть алгоритм O(n) без логарифмического фактора, использующий сортировку подсчетом. Более того, если частоты значительно меньше n, наши итерации будут намного короче.

Код JavaScript:

function getTopK(freq, min, max, k){
  let i = min;
  let j = 0;
  let counts = [];
  let result = new Array(k);

  for (; i<=max; i++)
    counts[i] = [];

  for (i=0; i<freq.length; i++)
    counts[freq[i][1]].push(i);

  for (i=max; i>=min, j<k; i--){
    for (let m=0; m<counts[i].length; m++){
      result[j] = freq[counts[i][m]][0];
      j++;
      if (j == k)
        break;
    }
  }
  return result;
};

function f(list, k){
  let max = 0;

  const freq = list.reduce(function(acc, s){
    acc[s] = -~acc[s];
    max = Math.max(max, acc[s]);
    return acc;
  }, new Map())

  return getTopK(Object.entries(freq), 1, max, k);
}

var list = [
    "this",
    "is",
    "a",
    "test",
    "which",
    "word",
    "wins",
    "top",
    "i",
    "don't",
    "know",
    "off",
    "hand",
    "do",
    "you",
    "this",
    "a",
    "a",
    "this",
    "test",
    "a",
    "a",
    "do",
    "hand",
    "hand",
    "a",
    "whatever",
    "what",
    "do",
    "do"
];

console.info(JSON.stringify(f(list, 10)));

Если я правильно понял, временная сложность здесь должна быть O(n+k), где n — длина массива, а k — количество элементов, которые вы хотите вернуть.

const data = ["this", "is", "a", "test", "which", "word", "wins", "top", "i", "don't", "know", "off", "hand", "do", "you", "this", "a", "a", "this", "test", "a", "a", "do", "hand", "hand", "a", "whatever", "what", "do", "do"];

function getTopOccurrences(n, list) { 
    const [_, arr] = list.reduce(([obj, arr], current) => {
        const oldOccurrences = obj[current] || 0;
        const newOccurrences = oldOccurrences + 1;
        if (!arr[oldOccurrences]) { arr[oldOccurrences] = new Set(); }
        if (!arr[newOccurrences]) { arr[newOccurrences] = new Set(); }
        
        if (current in obj) {
            arr[oldOccurrences].delete(current);
        }
        arr[newOccurrences].add(current);
        obj[current] = newOccurrences;

        return [obj, arr];
    }, [{},[]]);

    const result = [];
    outer: for(let i = arr.length - 1, s = arr[i]; i >= 0; i--, s= arr[i]) {
        for (let word of s){
            result.push(word);
            n--;
            if (n <= 0) {
                break outer;
            }
        }
    }
    return result;
}

console.info(getTopOccurrences(10, data));