{
"cmd": "g++ -std=c++17 \"${file}\" -o \"${file_path}/${file_base_name}\" && \"${file_path}/${file_base_name}\"",
"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
"working_dir": "${file_path}",
"selector": "source.c, source.c++",
"shell": true,
"variants":
[
{
"name": "Run",
"cmd": "g++ -std=c++17 \"${file}\" -o \"${file_path}/${file_base_name}\" && \"${file_path}/${file_base_name}\""
}
]
}
Category: Uncategorized
Vector back inserter example + algorithm
The problem is pretty simple: there is a list of time ranges for meetings and need to show the meetings as continuous block in calendar.
As per modern c++ I have used std::back_inserter_iterator for vector instead of passing vector by value or by reference. This approach is much cleaner, modern and saves a lot of copying of data compared to old style.
// i/p: [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
// o/p: [(0, 1), (3, 8), (9, 12)]
#include <iostream>
#include <vector>
#include <algorithm>
struct Meeting; // define meeting
using it = std::vector<Meeting>::iterator;
// use an back inserter iterator to pass as function argument instead
// of passing vector by reference or creating vector on heap
using bi = std::back_insert_iterator<std::vector<Meeting>>;
struct Meeting{
int start_time, end_time;
// default constructor
Meeting() = default;
// parameterized constructor
Meeting(int start_time, int end_time):start_time{start_time},end_time{end_date}{}
// override < operator used for sorting.
bool operator <(const Meeting &other) const{
return start_date < other.start_date;
}
static void merge(it start, it finish, bi merged_meeting_bi){
int start_time = start->start_time;
int end_time = start->end_time;
while(start < finish){
start++;
if(start->start_time > end_time){
merged_meeting_bi = {start_time, end_time}; // create meeting using parameterized constructor
start_time = start->start_time;
end_time = start->end_time;
}else{
end_time = std::max(start->end_time, end_time);
}
}
}
};
int main(){
std::vector<Meeting> meetings{{0, 1}, {3, 5}, {4, 8}, {10, 12}, {9, 10}};
std::vector<Meeting> merged_meetings;
auto bi = std::back_insert_iterator<std::vector<Meeting>>(merged_meetings);
auto start = meetings.begin();
auto finish = meetings.end();
// sort by first time
std::sort(start, finish);
for(const auto &meeting : meetings){
std::cout << meeting.start_time << ' ' << meeting.end_time << '\n';
}
Meeting::merge(start, finish, bi);
for(const auto & meeting: merged_meetings){
std::cout << meeting.start_time << ' ' << meeting.end_time << '\n';
}
return 0;
}
Dutch National Flag – Algorithm + TDD
The algorithm is pretty simple and achievable in O(n) time where n is the number of elements. Instead of using indexes, I am using 3 set of iterators and added bunch of test cases.
#include <gtest/gtest.h>
#include <algorithm> // random_shuffle
#include <vector>
#include <numeric> // accumulate
using it = std::vector<int>::iterator; // using typedef
void dnf(it less, it equal, it greater, int pivot){
while(equal <= greater){
if(*equal < pivot){
std::iter_swap(less, equal);
less++;
equal++;
}else if(*equal == pivot){
equal++;
}else{
std::iter_swap(equal, greater);
greater--;
}
}
}
TEST(RandomTest, dnfTest){
std::vector<int> v{2, 2, 0, 1, 1, 0, 2, 1, 0, 1, 0, 1, 0, 2, 2};
int pivot = 1;
for(int i = 0; i < 1000; i++){
dnf(v.begin(), v.begin(), v.end()-1, 1);
std::string output = std::accumulate(std::next(v.begin()), v.end(),
std::to_string(*v.begin()),
[](std::string s, int i){return s+= std::to_string(i);});
EXPECT_EQ(output, "000001111122222");
}
}
TEST(RandomTestTwoNumbers, dnfTest){
std::vector<int> v{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1};
int pivot = 1;
for(int i = 0; i < 1000; i++){
dnf(v.begin(), v.begin(), v.end()-1, 1);
std::string output = std::accumulate(std::next(v.begin()), v.end(),
std::to_string(*v.begin()),
[](std::string s, int i){return s+= std::to_string(i);});
EXPECT_EQ(output, "000000001111111");
}
}
TEST(RandomTestTwoNumbersMidPivot, dnfTest){
std::vector<int> v{0, 0, 0, 0,0,9,9,9,9,9,9,9,9};
int pivot = 1;
for(int i = 0; i < 1000; i++){
dnf(v.begin(), v.begin(), v.end()-1, 1);
std::string output = std::accumulate(std::next(v.begin()), v.end(),
std::to_string(*v.begin()),
[](std::string s, int i){return s+= std::to_string(i);});
EXPECT_EQ(output, "0000099999999");
}
}
TEST(RandomTestTwoNumbersHighPivot, dnfTest){
std::vector<int> v{0, 0, 0, 0,0,9,9,9,9,9,9,9,9};
int pivot = 10;
for(int i = 0; i < 1000; i++){
dnf(v.begin(), v.begin(), v.end()-1, 1);
std::string output = std::accumulate(std::next(v.begin()), v.end(),
std::to_string(*v.begin()),
[](std::string s, int i){return s+= std::to_string(i);});
EXPECT_EQ(output, "0000099999999");
}
}
int main(int argc, char**argv, char**envArg)
{
testing::InitGoogleTest(&argc, argv);
return(RUN_ALL_TESTS());
}
Iterators – look and say sequence algorithm
Look and say sequence is fun little exercise.. here is the code
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
std::string looknsay(int num){
// initialize vector with vector of ints.
// add default seed value to it [1].
std::vector<std::vector<int>> look_n_say_seq{{1}};
// iterate over until the number n is reached.
for(int n = 0; n <= num; n++){
auto latest_sequence = look_n_say_seq.back();
std::vector<int> next_sequence;
// keep a pair of iterators to move across the latest sequence from vector.
auto i = latest_sequence.begin();
auto j = latest_sequence.begin();
while(i < latest_sequence.end()){
for(;*i==*j && j < latest_sequence.end();++j){}
// distance will give the count
next_sequence.push_back(std::distance(i, j));
// *i will give the actual number to iterate on
next_sequence.push_back(*i);
i = j;
}
// insert newly created sequence into the vector.
look_n_say_seq.push_back(next_sequence);
}
auto latest_sequence = look_n_say_seq.back();
// accumulate - join vector of ints to make string and return
return std::accumulate(std::next(latest_sequence.begin()),
latest_sequence.end(),
std::to_string(*latest_sequence.begin()),
[](std::string s, int i){return s += std::to_string(i);});
}
int main(){
std::cout << looknsay(0) << '\n';
std::cout << looknsay(1) << '\n'; // 11
std::cout << looknsay(2) << '\n'; // 21
std::cout << looknsay(3) << '\n'; // 1211
std::cout << looknsay(4) << '\n'; // 111221
std::cout << looknsay(5) << '\n'; // 312211
}
Implicit type conversion – tricky scenario
Here are some of the scenarios where the implicit type conversion can be unintuitive and tricky.
- implicit conversion between int, float and bool
#include <iostream> void print(char x){ std::cout << "in the print method that has char arg\n"; } void print(int x){ std::cout << "in the print method that has int arg\n"; } void print(bool x){ std::cout << "in the print method that has bool arg\n"; } int main(){ int x =1; char ch = 'c'; char * c = &ch; print(*c); // in the print method that has char arg print(*c+1); //in the print method that has int arg return 0; }
Quick Concepts Part 1 – Introduction to RDMA
This is the first post in a three post series on getting started. By the end of the getting started series my goal is to get you ready to start coding with a sample program that will demonstrate the performance benefits of RDMA. In this post I will review RDMA concepts in a simple minded way. Later I intend to come back and do more detailed posts on each concept.
What is RDMA
RDMA is Remote Dynamic Memory Access which is a way of moving buffers between two applications across a network. RDMA differs from traditional network interfaces because it bypasses the operating system. This allows programs that implement RDMA to have:
- The absolute lowest latency
- The highest throughput
- Smallest CPU footprint
How Can We Use It
To make use of RDMA we need to have a network interface card that implements an RDMA engine.
We call this an HCA…
View original post 912 more words
Supercharged Computing 