Raskite dabartinę vidurkį iš sveikųjų skaičių srauto

Galimas dublikatas:
Mobilus medijos algoritmas C

Atsižvelgiant į tai, kad iš duomenų srauto skaitomi sveikieji skaičiai. Raskite iki šiol efektyviai perskaitytų elementų mediana.

Aš perskaičiau, kad galime naudoti didžiausią kairėje pusėje esantį krūvą, kad pateiktume elementus, kurie yra mažesni už efektyviąją medianą, o minimali krūva dešinėje pusėje - elementai, kurie yra didesni nei veiksminga mediana.

Apdorojus gaunamą elementą, elementų skaičius krūvose skiriasi ne daugiau kaip vienu elementu. Kai abiejose kasyklose yra tas pats elementų skaičius, mes nustatome vidutinius krūvos duomenis kaip efektyvią medianą. Kai krūvos nėra subalansuotos, mes renkamės efektyvią medianą iš krūvos, kurioje yra daugiau elementų, šaknų.

Bet kaip mes sukurtume didžiausią krūvą ir minimalų krūvą, tai yra, kaip mes žinome efektyvią medianą čia? Manau, mes įterpime 1 elementą į maksimalų krūvą, o po to kitą 1 elementą min. Visiems elementams. Ištaisykite mane, jei aš neteisingai.

203
18 мая '12 в 20:56 2012-05-18 20:56 Luv yra nustatytas gegužės 18 d., 12 val
@ 8 atsakymai

Yra daug skirtingų sprendimų, kaip rasti srautinių duomenų vidurkį, trumpai apibūdinsiu juos atsakymo pabaigoje.

Konkrečio sprendimo (maksimalaus krūvos / krūvos tirpalo) detalių klausimas ir tai, kaip veikia krūvos sprendimas:

Pirmuosius du elementus pridėkite mažesnę vertę kairėje pusėje, o dešinėje - mažesnę. Tada apdorokite srauto duomenis po vieną,

 Step 1: Add next item to one of the heaps if next item is smaller than maxHeap root add it to maxHeap, else add it to minHeap Step 2: Balance the heaps (after this step heaps will be either balanced or one of them will contain 1 more item) if number of elements in one of the heaps is greater than the other by more than 1, remove the root element from the one containing more elements and add to the other one 

Tada bet kuriuo metu galite apskaičiuoti mediana taip:

  If the heaps contain equal amount of elements; median = (root of maxHeap + root of minHeap)/2 Else median = root of the heap with more elements 

Dabar kalbėsiu apie visą problemą, kaip buvo žadėta atsakymo pradžioje. Medianos darbo suradimas iš duomenų srauto yra sudėtinga problema, o ieškant veiksmingo, tikslaus sprendimo su atminties apribojimais, tikriausiai nėra įmanoma bendrojo atvejo. Kita vertus, jei duomenys turi tam tikrų savybių, kurias galime naudoti, galime sukurti veiksmingus specializuotus sprendimus. Pavyzdžiui, jei žinome, kad duomenys yra neatsiejama rūšis, mes galime naudoti rūšiavimo skaičiavimus , kurie gali suteikti jums nuolatinį atminties pastovaus laiko algoritmą. . Galiausiai, jei nėra tikslios medianos ir pakanka aproksimacijos, galite tiesiog pabandyti įvertinti duomenų tikimybės tankio funkciją ir apskaičiuoti medianą naudodami šį.

350
18 мая '12 в 21:15 2012-05-18 21:15 atsakymą pateikė Hakan Serce, gegužės 18 d., 12 d., 21:15 2012-05-18 21:15

Jei negalite vienu metu laikyti visų atminties elementų, ši problema tampa daug sudėtingesnė. Norint išspręsti krūvą, reikia, kad vienu metu laikytumėte visus atminties elementus. Tai neįmanoma daugelyje realaus pasaulio taikomųjų programų.

Vietoj to, kadangi matote skaičius, sekite, kiek kartų matote kiekvieną sveikąjį skaičių. Darant prielaidą, kad yra 4 baitai, 2 ^ 32 kibirai arba ne daugiau kaip 2 ^ 33 sveikieji skaičiai (raktas ir skaitiklis kiekvienam int), kuris yra 2 ^ 35 baitai arba 32 GB. Tai tikriausiai bus daug mažesnė, nes jums nereikia saugoti rakto arba skaityti tiems įrašams, kurie yra 0 (pavyzdžiui, kaip nutylėjimą pythone). Kiekvienam naujam sveikam skaičiui įterpti reikia laiko.

border=0

Tada bet kuriuo momentu rasti medianą tiesiog naudokite skaičiavimus, kad nustatytumėte, kuris sveikasis skaičius yra vidutinis. Tai užima pastovų laiką (nors ir didelę pastovią, bet vis dėlto pastovų).

46
22 мая '12 в 0:19 2012-05-22 00:19 atsakymas įteiktas Andrew C , gegužės 22 d., 12 val. 0:19 2012-05-22 00:19

Jei įvesties dispersija yra statistiškai paskirstyta (pavyzdžiui, normalus, log-normal ... ir tt), tada mėginių ėmimas kolektoriu yra pagrįstas būdas apskaičiuoti procentilius / medianus iš savavališkai ilgo numerių srauto.

 int n = 0; // Running count of elements observed so far #define SIZE 10000 int reservoir[SIZE]; while(streamHasData()) { int x = readNumberFromStream(); if (n < SIZE) { reservoir[n++] = x; } else { int p = random(++n); // Choose a random number 0 >= p < n if (p < SIZE) { reservoir[p] = x; } } } 

„Rezervuaras“ yra veikiantis, vienodas (teisingas) visų įvesties duomenų pavyzdys, nepriklausomai nuo dydžio. Mediano (arba bet kokio procentilio) suradimas yra paprastas bako rūšiavimo ir įdomaus objekto klausimo klausimas.

Kadangi rezervuaras yra fiksuotas dydis, rūšiavimas gali būti laikomas veiksmingu O (1) - ir šis metodas veikia tiek pastoviu laiku, tiek atmintimi.

40
22 мая '12 в 2:05 2012-05-22 02:05 atsakė Colm MacCárthaigh gegužės 22 d., 12:05 , 2012-05-22 02:05

Efektyviausias būdas apskaičiuoti gauto srauto procentilę yra P² algoritmas: Raj Jain, Imrich Chlamtac: P² algoritmas, skirtas dinaminiams skaičiavimams ir histogramoms be taupymo stebėjimų. „Commun. ACM 28 (10): 1076-1085 (1985)

Algoritmas yra tiesiogiai įgyvendinamas ir veikia labai gerai. Tačiau tai yra sąmata, todėl reikia tai nepamiršti. Iš abstrakčios:

Siūlomas heuristinis algoritmas, skirtas dinamiškai apskaičiuoti medijos ir kitų kvantų qf. Įvertinimai atliekami dinamiškai, kai atliekami stebėjimai. Pastabos nėra išsaugomos; todėl algoritmas turi labai mažą ir fiksuotą saugojimo reikalavimą, neatsižvelgiant į stebėjimų skaičių. Dėl to jis idealiai tinka įgyvendinti kvintiliniame luste, kurį galima naudoti pramoniniuose valdikliuose ir įrašymo įrenginiuose. Algoritmas toliau plečiasi į histogramos grafiką. Analizuojamas algoritmo tikslumas.

25
22 мая '12 в 2:14 2012-05-22 02:14 atsakymą pateikė Hellblazer gegužės 22 d., 12 val

Ši problema pasižymi tiksliu sprendimu, kuris reikalauja, kad atmintyje būtų saugomi tik n neseniai matyti objektai. Jis greitai ir gerai svarstomas.

Indeksuojamas skiplistas palaiko O (ln n) įterpimą, ištrynimą ir indeksuotą paiešką savavališkiems elementams išlaikant tvarkingą tvarką. Kartu su FIFO eilute , kuri seka pirmąjį senąjį įrašą, sprendimas yra paprastas:

 class RunningMedian: 'Fast running median with O(lg n) updates where n is the window size' def __init__(self, n, iterable): self.it = iter(iterable) self.queue = deque(islice(self.it, n)) self.skiplist = IndexableSkiplist(n) for elem in self.queue: self.skiplist.insert(elem) def __iter__(self): queue = self.queue skiplist = self.skiplist midpoint = len(queue) // 2 yield skiplist[midpoint] for newelem in self.it: oldelem = queue.popleft() skiplist.remove(oldelem) queue.append(newelem) skiplist.insert(newelem) yield skiplist[midpoint] 

Čia pateikiamos nuorodos į visą darbo kodą (lengvai suprantama klasės versija ir optimizuota generatoriaus versija su indeksuotu kodekų skiplistu):

24
22 мая '12 в 8:36 2012-05-22 08:36 atsakė Raymondui Hettingeriui gegužės 12 d., 12 val

Intuityvus būdas pagalvoti apie tai yra tai, kad jei turėtumėte visiškai subalansuotą dvejetainį paieškos medį, tada šaknis būtų medianinis elementas, nes būtų toks pats mažesnių ir didesnių elementų skaičius. Dabar, jei medis nėra užpildytas, tai nebus taip, nes paskutiniame lygyje elementų nebus.

Todėl galime gauti mediana ir du subalansuotus dvejetainius medžius, po vieną elementams, mažesniems už medianą, ir vieną elementams, viršijantiems medianą. Du medžiai turi būti vienodo dydžio.

Kai gauname naują sveikų skaičių iš duomenų srauto, mes jį lyginame su mediana. Jei ji yra didesnė nei mediana, ją pridedame prie norimo medžio. Jei abiejų medžių dydžiai skiriasi daugiau nei 1, pašaliname dešiniojo medžio min elementą, tampa nauja mediana, o seną medianą įdedame į kairįjį medį. Panašiai ir mažesnėms.

15
22 мая '12 в 21:59 2012-05-22 21:59 atsakymas Irene Papakonstantinou, gegužės 22 d., 12 val., 9:59 val. 2012-05-22 21:59

Efektyvus yra žodis, kuris priklauso nuo konteksto. Šios problemos sprendimas priklauso nuo užklausų, atliktų dėl įterpimų skaičiaus, skaičiaus. Tarkime, kad iki galo įterpsite N skaičių ir K kartų, jus domina mediana. Krūvos algoritmo sudėtingumas būtų O (N log N + K).

Apsvarstykite šią parinktį. Užpildykite masyvo numerius ir už kiekvieną užklausą, paleiskite tiesinį atrankos algoritmą (tarkim, naudodami greitojo rūšiavimo atskaitos tašką). Dabar turite algoritmą su O (KN) vykdymo trukme.

Dabar, jei K yra pakankamai mažas (nelyginės užklausos), pastarasis algoritmas iš tiesų yra efektyvesnis ir atvirkščiai.

6
21 мая '12 в 23:50 2012-05-21 23:50 atsakymą pateikė Petras , gegužės 21 d., 12 val. 23:50 2012-05-21 23:50

Ar negalite tai padaryti su viena krūva? Atnaujinimas: ne. Žr. Komentarą.

Neišvengiamas: po to, kai nuskaitomi 2*n įėjimai 2*n minimali krūva yra didžiausia n iš jų.

Kilpa: perskaitykite 2 įrašus. Pridėti juos į krūvą ir ištrinkite min. Tai atkuria invariantą.

Todėl, kai skaitomi 2n įėjimai, krūvos min yra n. Dviejų elementų, esančių aplink vidurinę padėtį, vidurkis reikalauja šiek tiek papildomų komplikacijų ir apdorojimo užklausų po nelyginio įvesties skaičiaus.

-1
22 мая '12 в 0:12 2012-05-22 00:12 Atsakymą duos Darius Bacon gegužės 22 d., 12 val. 0:12 2012-05-22 00:12

Kiti klausimai apie žymių arba Užduoti klausimą