Created
July 22, 2012 13:15
-
-
Save scientific-coder/3159657 to your computer and use it in GitHub Desktop.
Optimization Contest
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/bash | |
DATA=../data_2000_50000.in | |
NB_RUN=10 | |
for SOURCE in $(ls *.cxx); | |
do | |
EXEC=${SOURCE%.cxx} | |
[ ! -e ${EXEC} ] && g++-snapshot -std=c++11 ${SOURCE} -o ${EXEC} -O4 -march=native -Wno-deprecated | |
echo -ne ${EXEC}'\t' | |
for i in $(seq ${NB_RUN}); | |
do | |
./${EXEC} <${DATA}; | |
done |fgrep TOTAL |cut -f 2 -d ' ' |sort -n |head -n 1 | |
done | sort -n -k 2 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <unordered_set> | |
#include <unordered_map> | |
#include <list> | |
#include <iterator> | |
#include <algorithm> | |
#include <queue> | |
#include <sys/time.h> | |
#include <unistd.h> | |
#include <boost/pending/disjoint_sets.hpp> | |
#include <boost/property_map/property_map.hpp> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-boost.cxx -o iptv-boost -O4 -march=native | |
/* should use boost::graph | |
or special purpose data structure for disjoint sets | |
for storing nodes if I have to make my own disjoint sets data structure, I'd use binomial heaps because they can be searched efficiently for a node and merged efficiently. Baring a binomial heap implementation, it is possible to use: | |
- heaps for efficient search, but slow merge | |
- unordered lists for slow search, but fast merge (splice) | |
for storing edges a C++11 priority_queue | |
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings. | |
*/ | |
// for interning | |
std::unordered_set<std::string> city_names; | |
// undirected ->could reorder nodes | |
struct edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
bool operator<(edge const& o)const{ return cost > o.cost;} | |
std::string const* n1; | |
std::string const* n2; | |
std::size_t cost; | |
}; | |
template<typename IStream > IStream& operator>>(IStream& is, edge& e){ | |
std::string tmp; | |
bool ok(false); | |
if(is >> tmp) { | |
e.n1= &(*(city_names.insert(tmp).first)); | |
if(is >> tmp) { | |
e.n2= &((*city_names.insert(tmp).first)); | |
if(is >> e.cost){ | |
ok= true; | |
} | |
} | |
} | |
if(!ok){ is.setstate(std::ios::failbit);} | |
return is; | |
} | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
std::cin >> nb_cities >> nb_links; | |
std::istream_iterator<edge> b(std::cin), end; | |
std::priority_queue<edge> edges_todo; | |
std::for_each(b, end | |
,[&edges_todo](edge const& ed){edges_todo.push(ed);}); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
typedef std::unordered_map<std::string const*,std::size_t> rank_t; // => order on Element | |
typedef std::unordered_map<std::string const*,std::string const*> parent_t; | |
rank_t rank_map; | |
parent_t parent_map; | |
boost::associative_property_map<rank_t> rank_pmap(rank_map); | |
boost::associative_property_map<parent_t> parent_pmap(parent_map); | |
boost::disjoint_sets<boost::associative_property_map<rank_t> | |
,boost::associative_property_map<parent_t> > trees(rank_pmap, parent_pmap); | |
std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);}); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1); merges_done != city_names.size() | |
; edges_todo.pop()) { | |
edge const& t(edges_todo.top()); | |
auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2)); | |
if(s1 != s2) { | |
trees.link(s1, s2); | |
total+= t.cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <strstream> | |
#include <unordered_set> | |
#include <unordered_map> | |
#include <utility> | |
#include <list> | |
#include <iterator> | |
#include <algorithm> | |
#include <queue> | |
#include <sys/time.h> | |
#include <unistd.h> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-buffered-read.cxx -o buffered-read -O4 -march=native | |
/* | |
for storing edges a C++11 priority_queue | |
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings. | |
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
*/ | |
// for interning | |
std::unordered_set<std::string> city_names; | |
// undirected ->could reorder nodes | |
struct edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
bool operator<(edge const& o)const{ return cost > o.cost;} | |
std::string const* n1; | |
std::string const* n2; | |
std::size_t cost; | |
}; | |
template<typename IStream > IStream& operator>>(IStream& is, edge& e){ | |
std::string tmp; | |
bool ok(false); | |
if(is >> tmp) { | |
e.n1= &(*(city_names.insert(tmp).first)); | |
if(is >> tmp) { | |
e.n2= &((*city_names.insert(tmp).first)); | |
if(is >> e.cost){ | |
ok= true; | |
} | |
} | |
} | |
if(!ok){ is.setstate(std::ios::failbit);} | |
return is; | |
} | |
// https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
template<typename V> | |
struct disjoint_sets{ | |
typedef std::pair<V, std::size_t> parent_rank_t; | |
std::unordered_map<V,parent_rank_t> data; | |
void make_set(V const& v) | |
{ data[v]=std::make_pair(v, 1); } | |
V find_set(V const& v) { | |
V & p(data[v].first); | |
if(p != v) {p= find_set(p);} | |
return p; | |
} | |
void link(V const& v1, V const& v2) { | |
V root1(find_set(v1)), root2(find_set(v2)); | |
if(root1 == root2) { return; } | |
parent_rank_t & p1(data[root1]); | |
parent_rank_t & p2(data[root2]); | |
if(p1.second < p2.second) { p1.first= root2; } | |
else if (p1.second > p2.second) {p2.first= root1; } | |
else { | |
p2.first= root1; | |
++p1.second; | |
} | |
} | |
}; | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
// EDIT: OK you want to pay by C rules, I'll bite ! :) | |
// must use std::strstream as std::istringstream makes a copy :( | |
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2); | |
std::cin >> nb_cities >> nb_links; | |
const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2 | |
+ max_nb_chars_cost+1)+1); | |
char* buff= new char[buff_size]; | |
std::cin.read(buff, buff_size); | |
std::istrstream buff_stream(buff); | |
std::istream_iterator<edge> b(buff_stream), end; | |
std::priority_queue<edge> edges_todo; | |
std::for_each(b, end | |
,[&edges_todo](edge const& ed){edges_todo.push(ed);}); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
delete [] buff; | |
disjoint_sets<std::string const*> trees; | |
std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);}); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1); merges_done != city_names.size() | |
; edges_todo.pop()) { | |
edge const& t(edges_todo.top()); | |
auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2)); | |
if(s1 != s2) { | |
trees.link(s1, s2); | |
total+= t.cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <strstream> | |
#include <unordered_map> | |
#include <utility> | |
#include <iterator> | |
#include <algorithm> | |
#include <cstdint> | |
#include <sys/time.h> | |
#include <unistd.h> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-crazy.cxx -o iptv-crazy -O4 -march=native -ftree-vectorizer-verbose=3 | |
// clang++ -std=c++11 iptv_crazy.cxx -o iptv_crazy -O4 -march=native | |
/* | |
for storing edges a radix sorted vector | |
Cheating : exploiting 8 chars names and assuming ASCII strict (7 bits) and cost <=30 (255 actually) | |
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
Could remove unordered map by storing ptr to city struct instead of the int name. The city struct would contain city name, representative city ptr and set size cf knuth standford graph miles_span.pdf p8 | |
*/ | |
std::vector<int64_t> unique_names; | |
// undirected ->could reorder nodes | |
struct /*alignas(16)*/ edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
int64_t n1 __attribute__ ((__aligned__(16))); | |
int64_t n2_cost; | |
}; | |
int64_t read_name(char *& c){ | |
int64_t res(0); | |
for(int i(0); i!=8 && (*c != ' '); ++i, ++c, res<<=7 ) | |
{ res|= *c; } | |
res<<=1;// now we have 8 clear bits as LSB | |
unique_names.push_back(res); | |
return res; | |
} | |
void make_names_unique(){ | |
// 7 significant bytes, byte 0 is clear we skip it | |
std::vector<std::size_t> names_buckets(257*7, 0); | |
std::vector<int64_t> tmp_names(unique_names.size()); | |
for(std::size_t i(0); i != unique_names.size(); ++i){ | |
for(int n_byte(0); n_byte != 7; ++n_byte) | |
{ ++names_buckets[257*n_byte +1+ ((unique_names[i]>>(8*(n_byte+1))) & 0xFF)]; } | |
} | |
for(int n_byte(0); n_byte != 7; ++n_byte){ | |
for(int i(1); i!=257; ++i){ names_buckets[257*n_byte+ i] += names_buckets[257*n_byte+ i-1]; } | |
} | |
for(int n_byte(0); n_byte != 7; ++n_byte, unique_names.swap(tmp_names)){ | |
for(std::size_t i(0); i != unique_names.size(); ++i) | |
{ tmp_names[names_buckets[257*n_byte + ((unique_names[i]>>(8*(n_byte+1))) & 0xFF)]++] = unique_names[i];} | |
} | |
// data ordered back into unique_names, now make_it unique | |
unique_names.resize(std::distance(unique_names.begin() | |
,std::unique(unique_names.begin(), unique_names.end()))); | |
} | |
template<typename CharIt, typename CharSize, typename EdgesIt, typename EdgesSize> | |
void read_edges(CharIt buff_it, CharSize buff_size, EdgesIt edges_out, EdgesSize nb_links){ | |
std::vector<edge> edges_to_sort(nb_links); | |
std::vector<std::size_t> buckets(257, 0);// could be 31+1 (instead of 256+1)per spec | |
for(std::size_t i(0); i != nb_links; ++i, ++buff_it){ | |
edges_to_sort[i].n1 = read_name(buff_it); | |
++buff_it;// skip ' ' | |
edges_to_sort[i].n2_cost = read_name(buff_it); | |
++buff_it;// skip ' ' | |
char c1, c2; | |
c1=*buff_it; | |
++buff_it; | |
c2= *buff_it; | |
if(c2 == '\n'){ edges_to_sort[i].n2_cost |= c1-'0'; } | |
else { | |
edges_to_sort[i].n2_cost |= (c1-'0')*10+ (c2-'0'); | |
++buff_it; // to \n | |
} | |
++buckets[(edges_to_sort[i].n2_cost & 0xFF)+1]; | |
} | |
for(std::size_t i(1); i!=256; ++i) { buckets[i]+= buckets[i-1]; } | |
for(std::size_t i(0); i!= nb_links; ++i) | |
{ *(edges_out+((buckets[edges_to_sort[i].n2_cost & 0xFF])++))= edges_to_sort[i];} | |
} | |
// https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
template<typename V> | |
struct disjoint_sets{ | |
typedef std::pair<V, std::size_t> parent_rank_t; | |
std::unordered_map<V,parent_rank_t> data; | |
void make_set(V const& v) | |
{ data[v]=std::make_pair(v, 1); } | |
V find_set(V const& v) { | |
V & p(data[v].first); | |
if(p != v) {p= find_set(p);} | |
return p; | |
} | |
void link(V const& v1, V const& v2) { | |
V root1(find_set(v1)), root2(find_set(v2)); | |
if(root1 == root2) { return; } | |
parent_rank_t & p1(data[root1]); | |
parent_rank_t & p2(data[root2]); | |
if(p1.second < p2.second) { p1.first= root2; } | |
else if (p1.second > p2.second) {p2.first= root1; } | |
else { | |
p2.first= root1; | |
++p1.second; | |
} | |
} | |
}; | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
// EDIT: OK you want to play by C rules, I'll bite ! :) | |
// must use std::strstream as std::istringstream makes a copy :( | |
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2); | |
// 8 chars for city names ? | |
// if ASCII, I can use std::int64_t ! | |
std::cin >> nb_cities >> nb_links; | |
const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2 | |
+ max_nb_chars_cost+1)+1); | |
char* buff= new char[buff_size]; | |
std::cin.read(buff, buff_size); | |
std::size_t actual_size(std::cin.gcount()); | |
std::vector<edge> edges_todo(nb_links); | |
//skip \n | |
read_edges(buff+1, actual_size, edges_todo.begin(), nb_links); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
delete [] buff; | |
make_names_unique(); | |
disjoint_sets<int64_t> trees; | |
std::for_each(unique_names.begin(), unique_names.end(), [&trees](int64_t const c){trees.make_set(c);}); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1), i(0); merges_done != unique_names.size(); ++i) { | |
edge const& t(edges_todo[i]); | |
auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2_cost & ~0xFF)); | |
if(s1 != s2) { | |
trees.link(s1, s2); | |
total+= t.n2_cost & 0xFF; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <unordered_set> | |
#include <list> | |
#include <iterator> | |
#include <algorithm> | |
#include <queue> | |
#include <sys/time.h> | |
#include <unistd.h> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-first-take.cxx -o iptv-first-take -O4 -march=native | |
/* optimization options are *very* important : | |
On my laptop with Intel CPU Atom N550 | |
without the options: | |
data file parsed in 651 ms. | |
2587 | |
minimum spanning tree computed in 2782 ms. | |
with -O4 -march=native: | |
data file parsed in 437 ms. | |
2587 | |
minimum spanning tree computed in 296 ms. | |
*/ | |
/* should use boost::graph | |
or special purpose data structure for disjoint sets | |
for storing nodes if I have to make my own disjoint sets data structure, I'd use binomial heaps because they can be searched efficiently for a node and merged efficiently. Baring a binomial heap implementation, it is possible to use: | |
- heaps for efficient search, but slow merge | |
- unordered lists for slow search, but fast merge (splice) | |
for storing edges a C++11 priority_queue | |
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings. | |
*/ | |
// for interning | |
std::unordered_set<std::string> city_names; | |
// undirected ->could reorder nodes | |
struct edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
bool operator<(edge const& o)const{ return cost > o.cost;} | |
std::string const* n1; | |
std::string const* n2; | |
std::size_t cost; | |
}; | |
template<typename IStream > IStream& operator>>(IStream& is, edge& e){ | |
std::string tmp; | |
bool ok(false); | |
if(is >> tmp) { | |
e.n1= &(*(city_names.insert(tmp).first)); | |
if(is >> tmp) { | |
e.n2= &((*city_names.insert(tmp).first)); | |
if(is >> e.cost){ | |
ok= true; | |
} | |
} | |
} | |
if(!ok){ is.setstate(std::ios::failbit);} | |
return is; | |
} | |
template<typename V> | |
struct disjoint_sets { | |
// could be single linked lists | |
typedef std::list<V> subset_t; | |
typedef std::list<subset_t> set_t; | |
template<typename It> | |
disjoint_sets(It b, It e){ | |
// we get iterators to std::string, not the std::string const* that V is | |
std::transform(b, e, std::back_inserter(s) | |
,[]( typename std::iterator_traits<V>::value_type const& str) | |
{return subset_t(1, &str);}); | |
} | |
// returns true in case of a merge | |
bool merge_if_distinct(V const& v1, V const& v2) { | |
typename set_t::iterator it1(s.end()), it2(s.end()); | |
for(typename set_t::iterator it(s.begin()) | |
; it != s.end() && (it1 == s.end() || it2 == s.end()); ++it) { | |
for(typename subset_t::iterator sit(it->begin()) | |
; (sit != it->end()) && (it1 == s.end() || it2 == s.end()); ++sit) { | |
if(*sit == v1) { it1= it; } | |
if(*sit == v2) { it2= it; } | |
} | |
} | |
if(it1 == it2) { return false;} | |
it1->splice(it1->begin(), *it2); | |
s.erase(it2); | |
return true; | |
} | |
// cannot use size() to know if only one elt left as size() shouldn't be efficient since splice is. The caller will count the merges. | |
set_t s; | |
}; | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
std::cin >> nb_cities >> nb_links; | |
std::istream_iterator<edge> b(std::cin), end; | |
std::priority_queue<edge> edges_todo; | |
std::for_each(b, end | |
,[&edges_todo](edge const& ed){edges_todo.push(ed);}); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
disjoint_sets<std::string const*> trees(city_names.begin(), city_names.end()); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1); merges_done != city_names.size() | |
; edges_todo.pop()) { | |
edge const& t(edges_todo.top()); | |
if(trees.merge_if_distinct(t.n1, t.n2)){ | |
total+= t.cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <strstream> | |
#include <unordered_set> | |
#include <unordered_map> | |
#include <utility> | |
#include <list> | |
#include <iterator> | |
#include <algorithm> | |
#include <queue> | |
#include <sys/time.h> | |
#include <unistd.h> | |
#include <cstdint> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-int-names.cxx -o iptv-int-names -O4 -march=native | |
/* | |
for storing edges a C++11 priority_queue | |
Cheating : exploiting 8 chars names and assuming ASCII (even 8 bits extensions) | |
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
*/ | |
std::unordered_set<int64_t> city_names; | |
// undirected ->could reorder nodes | |
struct edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
bool operator<(edge const& o)const{ return cost > o.cost;} | |
union city_t { | |
int64_t as_int; | |
char as_chars[8] ; | |
}; | |
city_t n1; | |
city_t n2; | |
std::size_t cost; | |
}; | |
// FAST and FURIOUS HACK: *very fragile* do no use in production, only to show off :) | |
template<typename IStream > IStream& operator>>(IStream& is, edge& e){ | |
std::string tmp; | |
bool ok(false); | |
e.n1.as_int= e.n2.as_int= 0; | |
if(is.get(e.n1.as_chars, 8, ' ')) { | |
is.get();// skip ' ' | |
if(is.get(e.n2.as_chars, 8, ' ')) { | |
is.get();// skip ' ' | |
char c1,c2; | |
if(is.get(c1)){ | |
if(is.get(c2)){ | |
if (c2=='\n') { e.cost= c1-'0'; } | |
else { | |
e.cost= (c1-'0')*10+ (c2-'0'); | |
is.get();// skip '\n' | |
} | |
ok= true; | |
city_names.insert(e.n1.as_int); | |
city_names.insert(e.n2.as_int); | |
} | |
} | |
} | |
} | |
if(!ok){ is.setstate(std::ios::failbit);} | |
return is; | |
} | |
// https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
template<typename V> | |
struct disjoint_sets{ | |
typedef std::pair<V, std::size_t> parent_rank_t; | |
std::unordered_map<V,parent_rank_t> data; | |
void make_set(V const& v) | |
{ data[v]=std::make_pair(v, 1); } | |
V find_set(V const& v) { | |
V & p(data[v].first); | |
if(p != v) {p= find_set(p);} | |
return p; | |
} | |
void link(V const& v1, V const& v2) { | |
V root1(find_set(v1)), root2(find_set(v2)); | |
if(root1 == root2) { return; } | |
parent_rank_t & p1(data[root1]); | |
parent_rank_t & p2(data[root2]); | |
if(p1.second < p2.second) { p1.first= root2; } | |
else if (p1.second > p2.second) {p2.first= root1; } | |
else { | |
p2.first= root1; | |
++p1.second; | |
} | |
} | |
}; | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
// EDIT: OK you want to pay by C rules, I'll bite ! :) | |
// must use std::strstream as std::istringstream makes a copy :( | |
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2); | |
// 8 chars for city names ? | |
// if ASCII, I can use std::int64_t ! | |
std::cin >> nb_cities >> nb_links; | |
const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2 | |
+ max_nb_chars_cost+1)+1); | |
char* buff= new char[buff_size]; | |
std::cin.read(buff, buff_size); | |
std::istrstream buff_stream(buff); | |
buff_stream.get();// skip '\n' | |
std::istream_iterator<edge> b(buff_stream), end; | |
std::priority_queue<edge> edges_todo; | |
std::for_each(b, end | |
,[&edges_todo](edge const& ed){edges_todo.push(ed);}); | |
delete [] buff; | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
disjoint_sets<int64_t> trees; | |
std::for_each(city_names.begin(), city_names.end(), [&trees](int64_t const c){trees.make_set(c);}); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1); merges_done != city_names.size() | |
; edges_todo.pop()) { | |
edge const& t(edges_todo.top()); | |
auto s1(trees.find_set(t.n1.as_int)), s2(trees.find_set(t.n2.as_int)); | |
if(s1 != s2) { | |
trees.link(s1, s2); | |
total+= t.cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <strstream> | |
#include <utility> | |
#include <iterator> | |
#include <cstring> | |
#include <cstdint> | |
#include <vector> | |
#include <sys/time.h> | |
#include <unistd.h> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-lazy.cxx -o iptv-lazy -O4 -march=native -ftree-vectorizer-verbose=3 | |
// clang++ -std=c++11 crazy.cxx -o crazy -O4 -march=native | |
/* | |
for storing edges a radix sorted vector | |
Cheating : exploiting 8 chars names and assuming ASCII strict (7 bits) and cost <=30 (255 actually) | |
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
Could remove unordered map by storing ptr to city struct instead of the int name. The city struct would contain city name, representative city ptr and set size cf knuth standford graph miles_span.pdf p8 | |
*/ | |
// 8 chars for city names ? | |
// if ASCII, I can use std::int64_t ! | |
union name_t { | |
int64_t as_int; | |
char as_chars[8]; | |
}; | |
struct city { | |
name_t name; | |
city(int64_t n){name.as_int=n; component_repr=this; component_size=1;} | |
city* next_hashlist; | |
city* component_repr; | |
std::size_t component_size; | |
static std::vector<city*> hash_map; | |
static std::vector<city> cities; | |
static city* get(int64_t name){ | |
// int16_t const key(name ^ (name >> 16) ^ (name >> 32) ^ (name >> 40)); | |
int32_t const keytmp(name ^ (name >> 32)); | |
int16_t const key(keytmp ^ (keytmp >> 16)); | |
city* ptr= hash_map[key]; | |
while(ptr && ( ptr->name.as_int != name)) { ptr= ptr->next_hashlist; } | |
if(!ptr){ | |
cities.push_back(city(name)); | |
cities.back().next_hashlist= hash_map[key]; | |
cities.back().component_repr= &cities.back(); | |
ptr= hash_map[key]= &cities.back(); | |
} | |
return ptr; | |
} | |
city* repr(){ | |
if(component_repr != this){component_repr= component_repr->repr();} | |
return component_repr; | |
} | |
void link_with(city* other){ // we already have repr and they are different | |
if(component_size < other->component_size){ component_repr= other;} | |
else if (component_size > other->component_size) {other->component_repr= this;} | |
else { | |
other->component_repr= this; | |
++component_size; | |
} | |
} | |
}; | |
std::vector<city*> city::hash_map= std::vector<city*>(0xFFFF+1, 0); | |
std::vector<city> city::cities; | |
struct edge { | |
std::pair<city*, city*> parse(){ | |
name_t name; | |
name.as_int=0; | |
char const*next = (char const*)rawmemchr(to_parse,' '); | |
memcpy(name.as_chars, to_parse, (next-to_parse)); | |
city* c1(city::get(name.as_int)); | |
char const* next_name(next+1); | |
next = (char const*)rawmemchr(next_name,' '); | |
memcpy(name.as_chars, next_name, (next-next_name)); | |
return std::make_pair(c1, city::get(name.as_int)); | |
} | |
int cost; | |
edge* next=0; | |
char const* to_parse; | |
}; | |
// https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
std::vector<edge> edges_store; | |
// array of lists of edges of the same cost(= array index), first is head, second is tail | |
std::vector<std::pair<edge*, edge*> > edges_todo(100, std::pair<edge*, edge*>(0,0)); | |
void read_edges(char const* buff_it, std::size_t buff_size, std::size_t nb_links){ | |
edges_store.resize(nb_links); | |
for(std::size_t i(0); i != nb_links; ++i, ++buff_it){ | |
edge& e(edges_store[i]); | |
e.to_parse= buff_it; | |
buff_it=(char const*)rawmemchr(buff_it, '\n'); | |
e.cost= (buff_it[-1]- '0') + ((buff_it[-2] == ' ') ? 0 : (10*(buff_it[-2]- '0'))); | |
if(edges_todo[e.cost].first){ | |
e.next=edges_todo[e.cost].first; | |
edges_todo[e.cost].first=&e; | |
}else{ edges_todo[e.cost].first=edges_todo[e.cost].second=&e; } | |
} | |
{ | |
int i,j,res; | |
for(res=0; (res!= edges_todo.size()) && !(edges_todo[res].first); ++res) {} | |
for(i=res; i!=edges_todo.size() ; i=j) { | |
for(j=i+1; (j!= edges_todo.size()) && !(edges_todo[j].first) ; ++j) {} | |
edges_todo[i].second->next=edges_todo[j].first; | |
} | |
edges_todo[0]= edges_todo[res]; | |
} | |
} | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
std::size_t nb_cities, nb_links; | |
// EDIT: OK you want to play by C rules, I'll bite ! :) | |
// must use std::strstream as std::istringstream makes a copy :( | |
const std::size_t max_nb_chars_city_name(8), max_nb_chars_cost(2); | |
std::cin >> nb_cities >> nb_links; | |
const std::size_t buff_size(nb_links*((max_nb_chars_city_name+1)*2 | |
+ max_nb_chars_cost+1)+1); | |
char* buff= new char[buff_size]; | |
std::cin.read(buff, buff_size); | |
std::size_t actual_size(std::cin.gcount()); | |
//skip \n | |
read_edges((char const*)buff+1, actual_size, nb_links); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
city::cities.reserve(nb_cities); | |
std::size_t total(0), merges_done(1); // start at 1 because we need nb-1 merges to have one last set | |
for(edge* e_it(edges_todo[0].first); (merges_done != nb_cities) && e_it; e_it= e_it->next) { | |
std::pair<city*, city*> cities(e_it->parse()); | |
city* repr1(cities.first->repr()); | |
city* repr2(cities.second->repr()); | |
if(repr1 != repr2){ | |
repr1->link_with(repr2); | |
total+= e_it->cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <iostream> | |
#include <unordered_set> | |
#include <unordered_map> | |
#include <utility> | |
#include <list> | |
#include <iterator> | |
#include <algorithm> | |
#include <queue> | |
#include <sys/time.h> | |
#include <unistd.h> | |
void affiche(const char *s,struct timeval tvStart, struct timeval tvStop){ | |
long int diff = tvStop.tv_usec - tvStart.tv_usec; | |
if (diff < 0) | |
diff += 1000000; | |
printf("%s: %ld microseconds\n",s,diff); | |
} | |
// g++-snapshot -std=c++11 iptv-wikipedia.cxx -o iptv-wikipedia -O4 -march=native | |
/* | |
for storing edges a C++11 priority_queue | |
for efficient nodes compares, we intern the city names and use pointers to the interned canonical strings. | |
for disjoint sets https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
*/ | |
// for interning | |
std::unordered_set<std::string> city_names; | |
// undirected ->could reorder nodes | |
struct edge { | |
// as priority queue returns the max elts, we simply use > for operator< to get the min elt | |
bool operator<(edge const& o)const{ return cost > o.cost;} | |
std::string const* n1; | |
std::string const* n2; | |
std::size_t cost; | |
}; | |
template<typename IStream > IStream& operator>>(IStream& is, edge& e){ | |
std::string tmp; | |
bool ok(false); | |
if(is >> tmp) { | |
e.n1= &(*(city_names.insert(tmp).first)); | |
if(is >> tmp) { | |
e.n2= &((*city_names.insert(tmp).first)); | |
if(is >> e.cost){ | |
ok= true; | |
} | |
} | |
} | |
if(!ok){ is.setstate(std::ios::failbit);} | |
return is; | |
} | |
// https://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
template<typename V> | |
struct disjoint_sets{ | |
typedef std::pair<V, std::size_t> parent_rank_t; | |
std::unordered_map<V,parent_rank_t> data; | |
void make_set(V const& v) | |
{ data[v]=std::make_pair(v, 1); } | |
V find_set(V const& v) { | |
V & p(data[v].first); | |
if(p != v) {p= find_set(p);} | |
return p; | |
} | |
void link(V const& v1, V const& v2) { | |
V root1(find_set(v1)), root2(find_set(v2)); | |
if(root1 == root2) { return; } | |
parent_rank_t & p1(data[root1]); | |
parent_rank_t & p2(data[root2]); | |
if(p1.second < p2.second) { p1.first= root2; } | |
else if (p1.second > p2.second) {p2.first= root1; } | |
else { | |
p2.first= root1; | |
++p1.second; | |
} | |
} | |
}; | |
int main(int argc, char* argv[]) { | |
struct timeval tv_start,tv_inter,tv_end; | |
gettimeofday(&tv_start,NULL); | |
// these are not needed in fact, it's 2012 already ! | |
std::size_t nb_cities, nb_links; | |
std::cin >> nb_cities >> nb_links; | |
std::istream_iterator<edge> b(std::cin), end; | |
std::priority_queue<edge> edges_todo; | |
std::for_each(b, end | |
,[&edges_todo](edge const& ed){edges_todo.push(ed);}); | |
gettimeofday(&tv_inter,NULL); | |
affiche("reading ",tv_start,tv_inter); | |
disjoint_sets<std::string const*> trees; | |
std::for_each(city_names.begin(), city_names.end(), [&trees](std::string const& c){trees.make_set(&c);}); | |
std::size_t total(0); | |
// start at 1 because we need nb-1 merges to have one last set | |
for(std::size_t merges_done(1); merges_done != city_names.size() | |
; edges_todo.pop()) { | |
edge const& t(edges_todo.top()); | |
auto s1(trees.find_set(t.n1)), s2(trees.find_set(t.n2)); | |
if(s1 != s2) { | |
trees.link(s1, s2); | |
total+= t.cost; | |
++merges_done; | |
} | |
} | |
std::cout << total << std::endl; | |
gettimeofday(&tv_end,NULL); | |
affiche("MST algorithm",tv_inter,tv_end); | |
affiche("TOTAL",tv_start,tv_end); | |
return 0; | |
} |
On my workstation:
iptv-lazy 3476
iptv-crazy 9086
iptv-int-names 17294
iptv-buffered-read 41698
iptv-wikipedia 94125
iptv-boost 95588
iptv-first-take 182498
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
On my netbook:
iptv-lazy 11989
iptv-crazy 36613
iptv-int-names 80247
iptv-buffered-read 187721
iptv-wikipedia 456548
iptv-boost 469965
iptv-first-take 721145