MJRTY - Un algoritmo di voto a maggioranza rapida non funziona [chiuso]

Question

MJRTY - Un algoritmo di voto a maggioranza rapida non funziona [chiuso]

#1 da (2 voti)
#2 da (0 voti)

0

L'algoritmo MJRTY si propone di risolvere il problema di trovare l'elemento di maggioranza in un flusso (un elemento che comprende più del 50% del flusso). Moore ha proposto di risolvere questo problema utilizzando solo 2 informazioni e una singola scansione dei dati. Immagina di avere un flusso di nomi ("matt", "timon", "matt", "matt", "rob", "ben", ...) e volevi sapere se qualche nome appariva in più della metà del flusso. Boyer e Moore hanno proposto quanto segue:

count = 0
majority = ""

for val in stream:
    if count == 0:
        majority = val
        count = 1
    elif val == majority:
        count += 1
    else:
        count -= 1
print majority if count > 0 else "no majority!"

se stream = A A A A B B B B C = > risultato = C, ma non è la verità.

passo dopo passo

step    val majority    count
0   A   A   1
1   A   A   2
2   A   A   3
3   A   A   4
4   B   A   3
5   B   A   2
6   B   A   1
7   B   A   0
8   C   C   1

Informazioni su questo algotithm: link

algorithms stream-processing

posta couatl 23.02.2015 - 16:14

fonte

2 risposte

0

Input          count          majority
A                1              A
A                2              A
A                3              A 
A                4              A
B                3              A
B                2              A
B                1              A
B                0              A
C                1              C

Il conteggio non è maggiore di 0. "nessuna maggioranza!"

risposta data 23.02.2015 - 16:35

fonte

Leggi altre domande sui tag algorithms stream-processing

formato standard per descrivere i programmi di apertura Organizzazione dei componenti C ++ [chiuso]

score 2 · Accepted Answer

L'algoritmo di Boyle-Moore funziona solo se esiste una maggioranza, in effetti. È utile se si può presumere che vi sia una maggioranza, ad esempio quando si elaborano stringhe binarie composte da 0 o 1 : se la lunghezza della stringa è dispari, è necessario avere una maggioranza.

La sequenza A A A A B B B B C ha 9 elementi, quindi è necessario avere almeno 5 occorrenze di un elemento per avere la maggioranza e non ce l'hai. Il risultato non è quindi significativo.