c++ - What is the most efficient way of selecting a random element from a long (and reasonably) sparse vector? -


i have long, reasonably sparse boolean vector, want iteratively select random elements from, , wondering efficient way of doing be.

the vector can around 100,000 elements long, , 1 in every 20 elements "true" @ 1 time.

the selection of 1 of these elements, result in making other elements available selection; can't single, initial pass of boolean vector indices of available elements , shuffle vector , pop elements, because list of available elements changes.

i have worked out couple of ideas, can't tell best. insight appreciated.

method 1:

given input boolean vector create boolean vector b    // store selected elements create int vector c        // store available element indices  while stopping condition not met:     each element in a:         if "true":             append index of c     generate random integer between 0 , length of     set i-th element of c in "false"     set i-th element of c in b "true"     compute new "true" values of

method 2:

given input boolean vector create boolean vector b    // store selected elements create int vector c        // store available element indices  each element in a:     if "true":         append index of c shuffle c while stopping condition not met:     pop element of c     set i-th element of c in "false"     set i-th element of c in b "true"     compute new "true" values of     if new values in computed:         append index of new available element c          shuffle c

because not every selection results in change set of available elements, think method 2 potentially better 1, except fact not sure how effort shuffling long vector cause.

method 3:

given input boolean vector create boolean vector b    // store selected elements while stopping condition not met:     generate random integer between 0 , length of     if "true" in a:         set in "false"         set in b "true"         compute new "true" values of

this final way seems bit naive , simple, figured if there 1 in every 20 elements being true (except last group of elements, when no more can added ones selected), on average need 20 tries find selectable element, less effort doing full pass of input vector, or shuffling vector of available indices (especially if vectors in question quite long). finding last few hard, keep track of how many have been selected, , once amount left gets below level change how selected final lot.

does have idea might more efficient? implementation in c++ if makes difference.

thanks help

you can change representation of sparse vector following -

  1. primary vector (the vector have right now)
  2. true vector (a list of "true" indices)

your operations become -

insert:        check if in primary vector     if false, set true , add true vector  delete:     check if in primary vector     if true, set false , remove true vector swapping     last element , reducing size

(you need pointers primary vector true vector this).

random:     generate random index j size of (true vector)     return true vector[j]

all operations can done o(1) complexity.


Comments

Post a Comment

Popular posts from this blog

python - Operations inside variables -

this question has answer here: evaluating mathematical expression in string 12 answers i want make python script finds maximum possible output using 2 operations. problem says there syntax error @ 2nd last line, in b in there. how can fix it? x = 0 = int(input("1st number:")) c = int(input("2nd number:" )) e = int(input("3rd number:" )) in range(4): if == 0: b = "+" elif == 1: b = "-" elif == 2: b = "/" else: b = "*" j in range(4): if j == 0: d = "+" elif j == 1: d = "-" elif j == 2: d = "/" else: d = "*" k = b c d e print(k) if you're after variables e on single line, couldn...
Read more

Generic Map Parameter java -

i having lot of methods of type: public static list<eduusers> getdetails(class c, map<string, integer> params) { list<eduusers> details = null; session session = hibernateutil.getsessionfactory().opensession(); transaction tx = null; try { tx = session.begintransaction(); criteria cr = session.createcriteria(c); (map.entry<string, integer> entry : params.entryset()) { cr.add(restrictions.eq(entry.getkey(), entry.getvalue())); } details = cr.list(); tx.commit(); } catch (exception asd) { log.debug(asd.getmessage()); if (tx != null) { tx.commit(); } } { session.close(); } return details; } i trying have generic method them , have written far: public static <t> list<t> getdetails(class<t> c, class<t> b) { l...
Read more

arrays - What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it? -

what arrayindexoutofboundsexception mean , how rid of it? here code sample triggers exception: string[] name = {"tom", "dick", "harry"}; for(int = 0; i<=name.length; i++) { system.out.print(name[i] +'\n'); } your first port of call should documentation explains reasonably clearly: thrown indicate array has been accessed illegal index. index either negative or greater or equal size of array. so example: int[] array = new int[5]; int boom = array[10]; // throws exception as how avoid it... um, don't that. careful array indexes. one problem people run thinking arrays 1-indexed, e.g. int[] array = new int[5]; // ... populate array here ... (int index = 1; index <= array.length; index++) { system.out.println(array[index]); } that miss out first element (index 0) , throw exception when index 5. valid indexes here 0-4 inclusive. correct, idiomatic for statement here be: for (int index = 0; index <...
Read more