How to efficiently select a random element from a Scala immutable HashSet -

-

i have scala.collection.immutable.hashset want randomly select element from.

i solve problem extension method this:

implicit class hashsetextensions[t](h: hashset[t]) {   def nextrandomelement (): option[t] = {     val list = h.tolist     list match {       case null | nil => none       case _ => (list (random.nextint (list.length)))     }   } }

...but converting list slow. efficient solution?

warning answer experimental use only. real project should use own collection types.

so did research in hashset source , think there little opportunity someway extract inner structure of valuable class hashtrieset without package violation.

i did come code, extended ben reich's solution:

package scala.collection  import scala.collection.immutable.hashset import scala.util.random  package object random {   implicit class hashsetrandom[t](set: hashset[t]) {     def randomelem: option[t] = set match {       case trie: hashset.hashtrieset[t] => {         trie.elems(random.nextint(trie.elems.length)).randomelem       }       case _ => some(set.size) collect {         case size if size > 0 => set.iterator.drop(random.nextint(size)).next       }     }   } }

file should created somewhere in src/scala/collection/random folder

note scala.collection package - thing makes elems part of hashtrieset visible. solution think, run better o(n). current version should have complexity o(ln(n)) of immutable.hashset's operation s.

another warning - private structure of hashset not part of scala's standard library api, change version making code erroneous (though it's didn't changed since 2.8)


Comments

Post a Comment

Popular posts from this blog

java - Custom OutputStreamAppender not run: LOGBACK: No context given for <MYAPPENDER> -

-
i wish write custom appender on basis of outputstreamappender . wrote following class package tests; import java.io.ioexception; import java.io.outputstream; import ch.qos.logback.core.outputstreamappender; public class myappender<e> extends outputstreamappender<e> { public myappender() { system.out.println("myappender created"); setoutputstream(new outputstream() { @override public void write(int b) throws ioexception { throw new unsupportedoperationexception(); } }); } } then wrote following runner: package tests; import org.slf4j.loggerfactory; import ch.qos.logback.classic.logger; public class runner { private static final logger log = (logger) loggerfactory.getlogger(runner.class); public static void main(string[] args) { //log.addappender(new myappender<iloggingevent>()); log.info("hello world"); } } finall...
Read more

java - UML - How would you draw a try catch in a sequence diagram? -

-
Image
is there standard way of drawing try catch sequence diagrams? i've made attempt based on this feel end result doesn't feel right. code diagram based around: public static void save () { try { filehandle filehandle = gdx.files.external(file); filehandle.writestring(boolean.tostring(constantshandler.soundenabled)+"\n", false); (int = 0; < 5; i++) { filehandle.writestring(integer.tostring(constantshandler.highscores[i])+"\n", true); } } catch (throwable e) { } } my attempt note: know still need add loop. that's ok. fragments meant show conditional control flow in sequence diagram. superstructures puts limitations on use of fragments (see pp. 467 of ss2.1.1). should use critical region try part above. , option catch . however, keep telling can take quite freedom in using uml. it's language , such changes in life time. long reader ge...
Read more

c++ - No viable overloaded operator for references a map -

-
i trying use map can make tag names reference number. when try , use it, in code error (6 in total every time reference map): src/main.cpp:25:45: error: no viable overloaded operator[] type 'std::map<std::string, std::string>' const char* idcs = node.child_value(tagmap[3]); this code: #include "pugi/pugixml.hpp" #include <iostream> #include <string> #include <map> int main() { pugi::xml_document doca, docb; std::map<std::string, pugi::xml_node> mapa, mapb; std::map<std::string, std::string> tagmap {{"1", "data"}, {"2", "entry"}, {"3", "id"}, {"4", "content"}}; if (!doca.load_file("a.xml") || !docb.load_file("b.xml")) { std::cout << "can't find input files"; return 1; } (auto& node: doca.child(tagmap[1]).children(tagmap[2])) { co...
Read more