vaticanoptimist
BAN USERfrom stackoverflow.com/questions/5095781/how-pthread-mutex-lock-is-implemented
In Linux, for example, a system called Futex (Short for Fast Userspace Mutex) is used.
In this system an atomic increment and test operation is performed on the mutex variable in user space.
If the result of the operation indicates that there was no contention on the lock, the call to pthread_mutex_lock returns without ever context switching into the kernel, so the operation of taking a mutex can be very fast.
Only if contention was detected does a system call (called futex) and context switch into the kernel occurs that puts the calling process to sleep until the mutex is released.
Disadvantages of Locks:
1) adds overhead for each access, even when the chances for collision are very rare.
2) deadlock, where two threads each hold a lock on resources that the other needs before releasing its lock.
3) if one thread holding a lock dies before unlocking the resources, all other threads that are waiting on it will be blocked forever
4) high priority threads cannot proceed if a low priority thread is holding the common lock
etc....
for 1-10K, use counting sort - O(n);
for 10K between 1-50K, use radix sort - O(nk); n = 10K, k = 5;
I think this is O(n) implementation, i ve run it and it works!
#include <iostream>
#include <string>
#include <cctype>
#include <utility>
#include <limits>
int main () {
std::string s = "aabbcdccefff";
std::string::const_iterator iter = s.begin();
int i = 0;
int array[26];
for (i = 0; i < 26; ++i) {
array[i] = 0;
}
for (i = 1; iter != s.end(); ++iter, ++i) {
int index = (int) *iter - 'a';
if (array[index] == 0) {
array[index] = i;
} else if (array[index] > 0) {
array[index] *= -1;
}
}
int min_value = std::numeric_limits<int>::max();
int min_index = -1;
for (i = 0; i < 26; ++i) {
if (array[i] > 0) {
if (array[i] < min_value) {
min_value = array[i];
min_index = i;
}
}
}
std::cout << (char) (97 + min_index) << std::endl;
}
RepNatalieLutz, Applications Developer at Absolute Softech Ltd
Pitch trending story topics and continually look for ways to push breaking and/or viral stories forward with new angles ...
- vaticanoptimist October 09, 2013