codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <ctime> std::vector<double> Sort(std::vector<double> weights, const double pounds) { std::sort(weights.begin(), weights.end()); std::vector<double>::iterator iter = weights.end(); double total=0; while(total < pounds) { --iter; total += *iter; } return std::vector<double>(iter, weights.end()); } std::vector<double> Heap(std::vector<double> weights, const double pounds) { std::make_heap(weights.begin(), weights.end()); std::vector<double> result; double total=0; while(total < pounds) { std::pop_heap(weights.begin(), weights.end()); result.push_back(weights.back()); total += weights.back(); weights.pop_back(); } return result; } std::vector<double> SoapBox(std::vector<double> weights, const double pounds) { std::greater<double> pred; std::vector<double> result(1, weights[0]); double total=weights[0]; double lightest=weights[0]; unsigned int i; for(i=0; i<weights.size() && total<pounds; ++i) { double curweight = weights[i]; result.push_back(curweight); total += curweight; if (curweight < lightest) curweight = lightest; } std::make_heap(result.begin(), result.end(), pred); for( ; i<weights.size(); ++i) { double curweight = weights[i]; if (curweight>lightest && total-lightest+curweight>=pounds) { do { std::pop_heap(result.begin(), result.end(), pred); total -= result.back(); result.pop_back(); lightest = result.front(); } while(total-lightest+curweight >= pounds); result.push_back(curweight); std::push_heap(result.begin(), result.end(), pred); total += curweight; if (curweight < lightest) curweight = lightest; } } return result; } struct PartitionPred { const double pounds; PartitionPred(const double lb) : pounds(lb) {} bool operator()(double lb) {return lb<pounds;} }; std::vector<double> NeilG(std::vector<double> weights, const double pounds) { std::vector<double>::iterator spared = weights.begin(); std::vector<double>::iterator dead = weights.end(); std::vector<double>::iterator mid; std::vector<double>::iterator i; double deadtotal = 0; while(dead > spared && *spared!=*(dead-1)) { ptrdiff_t count = std::distance(spared, dead); if (count > 5) count = 5; std::sort(spared, spared + count); double guess = spared[count/2]; mid = std::partition(spared, dead, PartitionPred(guess)); if (mid == spared) { for(i = spared+1; i<dead; ++i) { if (*i > guess) { mid = std::partition(spared, dead, PartitionPred(guess=*i)); break; } } } else if (mid == dead) { for(i = spared; i<dead; ++i) { if (*i > guess) { mid = std::partition(spared, dead, PartitionPred(guess=*i)); break; } } } double greaterweight=0; for(i=mid; i<dead; ++i) greaterweight += *i; if (deadtotal + greaterweight >= pounds) { spared = mid; } else { deadtotal += greaterweight; dead = mid; } } while(deadtotal<pounds && dead>spared) { --dead; deadtotal += *dead; } return std::vector<double>(dead, weights.end()); } #define COUNT 10000000 int main() { //srand(time_t(NULL)); //omitted for consistancy std::vector<double> weights; weights.reserve(COUNT); std::vector<double> result0, result1, result2, result3, result4; result1.reserve(20); result2.reserve(20); result3.reserve(20); result3.reserve(20); clock_t begin, end; double total; for(unsigned int i=0; i<COUNT; ++i) { double big = rand()*RAND_MAX + rand(); double inrange = big*100 /RAND_MAX/RAND_MAX + 100; weights.push_back(inrange); } result0 = Sort(weights, 3000); begin = clock(); result0 = Sort(weights, 3000); end = clock(); std::sort(result0.begin(), result0.end()); std::cout << "Sort: " << (end-begin) << " ticks: "; total =0; for(unsigned int i=0; i<result0.size(); ++i) total += result0[i]; std::cout << result0.size() << " people, " << total << "lb ("; for(unsigned int i=0; i<result0.size(); ++i) std::cout << (int(result0[i]*10000000)%10); std::cout << ")\n"; result1 = Heap(weights, 3000); begin = clock(); result1 = Heap(weights, 3000); end = clock(); std::sort(result1.begin(), result1.end()); std::cout << "Heap: " << (end-begin) << " ticks: "; total =0; for(unsigned int i=0; i<result1.size(); ++i) total += result1[i]; std::cout << result1.size() << " people, " << total << "lb ("; for(unsigned int i=0; i<result1.size(); ++i) std::cout << (int(result1[i]*10000000)%10); std::cout << ")\n"; result2 = SoapBox(weights, 3000); begin = clock(); result2 = SoapBox(weights, 3000); end = clock(); std::sort(result2.begin(), result2.end()); std::cout << "SoapBox: " << (end-begin) << " ticks: "; total =0; for(unsigned int i=0; i<result2.size(); ++i) total += result2[i]; std::cout << result2.size() << " people, " << total << "lb ("; for(unsigned int i=0; i<result2.size(); ++i) std::cout << (int(result2[i]*10000000)%10); std::cout << ")\n"; result3 = NeilG(weights, 3000); begin = clock(); result3 = NeilG(weights, 3000); end = clock(); std::sort(result3.begin(), result3.end()); std::cout << "NeilG: " << (end-begin) << " ticks: "; total =0; for(unsigned int i=0; i<result3.size(); ++i) total += result3[i]; std::cout << result3.size() << " people, " << total << "lb ("; for(unsigned int i=0; i<result3.size(); ++i) std::cout << (int(result3[i]*10000000)%10); std::cout << ")\n"; return 0; }
Private
[
?
]
Run code
Submit