java - Improving Intersection Algorithm -

-

i have algorithm build intersection of 2 sorted lists. if compare java.util.bitset in performance test, algorithm slow. 

    public static list<integer> intersection(list<integer> list1, list<integer> list2) {             int size1 = list1.size(), size2 = list2.size();             int capacity = size1 < size2 ? size1 : size2;             list<integer> intersection = new arraylist<integer>(capacity);             int i1 = 0, i2 = 0;             while (i1 < size1 && i2 < size2) {                 if (list1.get(i1) < list2.get(i2))                     i1++;                 else if (list2.get(i2) < list1.get(i1))                     i2++;                 else {                     intersection.add(list2.get(i2++));                     i1++;                 }             }             return intersection;         }

anyone sees improvement?

thanks

are inputs function of type arraylist?

  • if are, algorithmically there nothing wrong method. i'd make 2 changes:
    1. i'd change argument types arraylist<integer> list1, arraylist<integer> list2;
    2. i'd call list1.get(i1) , list2.get(i2) once. may or may not make difference performance, stylistically prefer factor out.
  • if need support list, i'd rewrite function in terms of 2 iterators, since calling get(index) expensive.

finally, when testing performance, make sure follow advice given in how write correct micro-benchmark in java?


Comments

Post a Comment

Popular posts from this blog

Hatching array of circles in AutoCAD using c# -

-
i beginner in autocad plugins .i have created array of circle using following code. now, have hatch circles in array .how that??how hatch circles @ once? moreover, how can return hatch method , use hatch objects.sorry language.thanks in advance. [assembly: commandclass(typeof(beamsection.class1))] namespace beamsection { public class class1 { //class1 obj = new class1(); [commandmethod("beamatsupport")] public void addlightweightpolyline() { // current document , database document acdoc = application.documentmanager.mdiactivedocument; database accurdb = acdoc.database; promptpointresult ppr = acdoc.editor.getpoint("\nselect starting point "); var ucs = acdoc.editor.currentusercoordinatesystem; point3d startingpt = ppr.value.transformby(ucs); list<double> radius = new list<double>(); radius.add(0.5);
Read more

ios - UITEXTFIELD InputView Uipicker not working in swift -

-
hello trying pop uipickerview view programmatically when user clicks on textfield. have tried doesn't doing anything. isn't working. nothing happening when click textfield class userprofiletableviewcontroller: uitableviewcontroller,uitextfielddelegate,uipickerviewdelegate,uipickerviewdatasource { var itempicker: uipickerview! = uipickerview() @iboutlet weak var gendertxtfield: uitextfield! var gender = ["male","female"] override func viewdidload() { super.viewdidload() gendertxtfield.delegate = self itempicker!.delegate = self itempicker!.datasource = self itempicker!.backgroundcolor = uicolor.blackcolor() self.gendertxtfield.inputview = itempicker } func numberofcomponentsinpickerview(pickerview: uipickerview) -> int{ return 1 } // returns # of rows in each component.. func pickerview(pickerview: uipickerview, numberofrowsincomponent component:
Read more

Python Pig Latin Translator -

-
so have been working on @ codecademy.com while trying learn python. don't know if blind , can't see why won't work or what. here's code won't let me use. function print variable if had typed in , print "empty" if didn't type anything. print "welcome english pig latin translator!" original = raw_input("what's name?") if len(original) > 0 print original else print "empty" if len(original) > 0 else the above lines contains syntax errors. try: if len(original) > 0: else: note added colons, ( : ).
Read more