java - Runtime of this implementation to find k most frequently recurring words in a string -


here's algorithm:

(a) make wordoccurrence class contains string sentence , int numberofoccurrences. let's assume sentence has n words. make class implement comparable, , make comparator numberofoccurrences first, , (arbitrarily,) alphabetical (natural) ordering of word second.

(b) iterate through sentence .split(‘ ‘) (or in place iteration save space). create new wordoccurrence object each unique word, updating occurrence , placing wordoccurrence objects treemap<wordoccurrence>.

(c) create new wordoccurrence object each unique word, placing wordoccurrence objects treemap<wordoccurrence> (and updating words' occurrences along way).

(d) call highestkey() on treemap, , place returned word resultant list. call lowerkey returned word (k - 1) times, placing words same resultant list.

(e) return resultant list.

my question: runtime of this? understanding:

step (b) takes o(n) time.

step (c) takes o(n*log(n)), each of n words, insertion o(log n).

step (d) takes o(k*log(n)), each call of highestkey() or lowerkey() takes o(log n) time.

so total runtime be: o(n + n*log(n) + k*log(n), o(n*log n).

is there tighter bound algorithm, or way o(n)?

thanks.

yours poor approach several reasons:

  • swaddling in object going make constant factor here unreasonably high. you're creating @ least 2 objects per word in string; given average english word 6 letters, can figure out average blowup.
  • you can use treemap<string, integer> instead of using wordoccurrence thingamajig. still horrible first reason, reduces amount of code have write.
  • your reasoning not take consideration fact keys strings , hence variable-length. not think affects anything, mark down if teaching assistant.
  • for data structure, use hash table instead. can use hashmap in java instead , better. might @ trove or hashmap values ints instead of integers.

also, there data structure called suffix tree. can build suffix tree on string in linear time , explore figure out distinct words , count of each. can linear-time selection find top k. loses hash table in practise, in theory avoids constant-time-lookup hash tables.


Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more

jsf - How to ajax update an item in the footer of a PrimeFaces dataTable? -

this visual of table have: +---------+------------+-------------------+ | header1 | header2 | header3 | +---------+------------+-------------------+ | row | input | calc'ed output | | row b | input b | calc'ed output b | | etc.. | etc.. | etc.. | +---------+------------+-------------------+ | total: total calc'ed output | +------------------------------------------+ and stripped-down code: <p:datatable id="mytable" value="#{mybean.somelist}" var="currentitem"> <p:column headertext="header1"> <h:outputtext value="#{currentitem.name}" /> </p:column> <p:column headertext="header2"> <pe:inputnumber value="#{currentitem.inputval}"> <p:ajax event="change" listener="#{mybean.changelistener}" update="outputval outputtotal...
Read more

django - CSRF verification failed. Request aborted. CSRF cookie not set -

error: reason given failure: csrf cookie not set. in general, can occur when there genuine cross site request forgery, or when django's csrf mechanism has not been used correctly. post forms, need ensure: browser accepting cookies. view function uses requestcontext template, instead of context. in template, there {% csrf_token %} template tag inside each post form targets internal url. if not using csrfviewmiddleware, must use csrf_protect on views use csrf_token template tag, accept post data. you're seeing section of page because have debug = true in django settings file. change false, , initial error message displayed. can customize page using csrf_failure_view setting. did find, nothing helped, must foolish(( my template <form method="post">{% csrf_token %} {% field in form %} <div class="control-group"> {{ field }} </div> {% endfor %} <input type=...
Read more