Вычисление статистического режима - PullRequest
Новая
       27

Вычисление статистического режима

2 голосов
/ 04 февраля 2009

В настоящее время я пытаюсь проверить, существует ли какой-либо элемент, встречающийся в n / k раз или более, с учетом несортированного массива A длины N и целого числа k.

Я думал об этой проблеме, чтобы вычислить режим, а затем сравнить его с n / k. Однако я не знаю, как быстро вычислить этот режим. Мой окончательный результат должен быть n log (k), но я понятия не имею, как это сделать. Самый быстрый, который я смог найти, был n k ...

Ответы [ 5 ]

6 голосов
/ 04 февраля 2009

Используйте хеш-таблицу для подсчета частоты каждого значения: 

uint[int] counts;
foreach(num; myArray) {
     counts[num]++;
}

int mostFrequent;
uint maxCount = 0;
foreach(num, count; counts) {
    if(count > maxCount) { 
        mostFrequent = num;
        maxCount = count;
    }
}
2 голосов
/ 05 февраля 2009

Установите m = n / k с округлением в большую сторону. Выполните быструю сортировку, но отбросьте подсписки длиной менее m.

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

В рекурсии будет O (log (k)) уровней, и каждый уровень занимает O (n) время.

1 голос
/ 19 октября 2012

Расчет статистического режима в F # .net для набора данных (целых чисел) с одним режимом 

let foundX (num: int, dList) = List.filter (fun x -> x = num) dList
let groupNum dList =
    dList
    |> (List.map (fun x -> foundX (x, dList)))
    |> (List.maxBy (fun x -> x.Length))

let Mode (dList: int List) = 
    let x = groupNum dList
    x.Head

//using Mode
let data = [1;1;1;1;1;1;1;1;2;2;3;3;3;1;4;4;4;4;4]
Mode data;;`

1 голос
/ 04 февраля 2009

Просто обход массива и ведение счета в хэше / словаре (и возвращение true, когда n / k найден, иначе false) будет O (n)

изменить, что-то вроде: 

counts = {}
for n in numbers:
    if ( counts.has_key( n ) ):
        counts[ n ] += 1
    else:
        counts[ n ] = 1
    if ( counts[ n ] >= n / k ):
        return true
return false
0 голосов
/ 04 февраля 2009

псевдокод: 

 found = false
 value = null
 B = new hashtable
 for (i =0, j = A[i]; i < |A| and !found; ++i, j=A[i])
    if B contains key j
       B[j] = B[j] + 1
       if B[j] > |A|/k
          found = true
          value = j
       endif
    else 
       B[j] = 1
    endif
 end for

Предполагая, что ваша хеш-таблица имеет O (1) insert / lookup, это должно быть O (n)

...