algorithm - why '*' faster than hash find, c++ -

-

i learnt data structure, can tell me why hash slow, thank you!

this problem leetcode: https://leetcode.com/problems/happy-number/

bool ishappy(int n) {     unordered_map<int, int> m;     m[0] = 0, m[1] = 1, m[2] = 4, m[3] = 9, m[4] = 16, m[5] = 25,\     m[6] = 36, m[7] = 49, m[8] = 64, m[9] = 81;     int temp, mark = 0;   //temp next n, mark detect circle      while(n){         temp = 0;         if(n == 1) return true;         if(n < 10){             if(mark == n)                return false;             mark = n;         }         //calc next n         while(n){             temp += (n%10)*(n%10); // 4 ms             //temp += m[n%10];       // 8 ms             n /= 10;         }         n = temp;     } }

why not? hashing efficient because of constant fetch time on average. that's it.

there no guarantee it's faster *. note key not directly used key hash table(this called "direct-address table" has own drawbacks). in general, there calculation key hash key: hash_key = hash(your_key). time totally depends on how hash implemented. once hash key calculated, it's matter of indexing table.

as matter of fact, common implementation of hashing involves modulus(%) operation slower '*'. think this: c = % b equivalent c = – b * (a / b).

you might ask 2 %(as in * case) vs 1 %(as in map case)? guess n%10 optimized compute once in first case.


Comments

Post a Comment

Popular posts from this blog

qt - Using float or double for own QML classes -

-
i've created components , helper methods using c++ , qt used in qml gui. of methods calculate gui elements (size, transformations, scene graph items creation). target arm 32 bit using opengl / eglfs render output. opengl using float , qml using real (defined double ). what should use in c++ do not lose precision? if use qreal ( double ) shouldn't lose precision. if git grep float in qtbase.git , can find out bit more: dist/changes-5.2.0-**************************************************************************** dist/changes-5.2.0-* important behavior changes * dist/changes-5.2.0-**************************************************************************** dist/changes-5.2.0- dist/changes-5.2.0- - qt compiled qreal typedef'ed double on dist/changes-5.2.0: platforms. qreal float on arm chipsets before. guarantees more dist/changes-5.2.0- consistent behavior between platforms qt supports, binary dist/chan...
Read more

Create Outlook appointment via C# .Net -

-
i need create outlook appointment using microsoft.office.interop.outlook , while can work locally on own workstation , works if run web application via server's browser, not work when connect server externally. hence, think might permission issue. i changed application pool identity " localsystem " don't access denied error. unfortunately, doesn't work. the app behaves if appointment created, appointment doesn't appear in outlook. here include file on top of aspx.cs page using outlook = microsoft.office.interop.outlook; here code using pop appointment. outlook.application apptapp = new outlook.application(); outlook.appointmentitem appt = apptapp.createitem(outlook.olitemtype.olappointmentitem) outlook.appointmentitem; appt.subject = txtfirstname.text + " " + txtlastname.text; appt.body = txtcomment.text; appt.alldayevent = false; appt.start = datetime.parse(txtreminderdate.text + " 8:00 am"); appt.end = datetime.p...
Read more

ios - Swift Array Resetting Itself -

-
i have 2 arrays: pointhistory , datehistory . have nstimer , , when timer runs out, action called. in action appending int pointhistory , , current date string datehistory . here timer action: func timeraction() { let steppervalue = int(stepper.value) employee.numberofpoints = steppervalue networking.saveemployee(employee, completion: { (error) -> void in if error != nil { let alert = uialertcontroller(title: "error", message: "there error updating \(self.employee.name)'s points", preferredstyle: .alert) let alertaction = uialertaction(title: "ok", style: .cancel, handler: nil) alert.addaction(alertaction) self.presentviewcontroller(alert, animated: true, completion: nil) } }) var dateformatter = nsdateformatter() dateformatter.dateformat = "mm-dd-yyyy" dateformatter.timezone = nstimezone.localtimezone() var date = nsdate() var ...
Read more