Inline Functions and their Uses
It’s a good practice to divide the program into several functions such
that parts of the program don’t get repeated a lot and to make the code
easily understandable.
We all know that calling and returning from a function generates some overhead.
The overhead is sometimes to such an extent that it makes significant effect
on the overall speed of certain complex and function-oriented programs. In most
cases, we have only a few functions that have extensive use and make significant
impact on the performance of the whole program.
Not using functions is not an option, using function-like macros is an option,
but there is a better solution, to use Inline Functions.
Yes, like it sounds, inline functions are expanded at the place of calling
rather than being “really called” thus reducing the overhead. It
means wherever we call an inline function, compiler will expand the code there
and no actual calling will be done.
Member functions of classes are generally made inline as in many cases these
functions are short but any other function can be inline too. Functions are
made inline by preceding its definition with the keyword “inline”
as shown in the example below:
// precede the definition
// of function with "inline"
// it's optional to do so for
// the prototype
inline ret-type func-name(arg-list...)
{
...
...
...
}
Member functions (class) can be made inline as below:
class myclass
{
private:
...
...
public:
ret-type func-name(arg-list...);
...
...
};
inline ret-type myclass::func-name(arg-list...)
{
...
...
}
Or simply as
class myclass
{
private:
...
...
public:
inline ret-type myclass::func-name(arg-list...)
{
...
...
}
...
...
};
Short member functions are usually made inline as above.
Please mote one thing though, inline is a request to the compiler and not a
command which means it depends on the compiler and the conditions whether a
particular function will be really made “inline” or not.
As inlining increases duplication of parts of code, performance will be gained
at the expense of program size, which is pretty obvious. As I’ve said
not all functions make major impact on the overall performance of the program.
So we should carefully select which functions to inline and which not to, because
if we inline many functions we can’t be sure of whether it’d do
any better to the performance, but it’s for sure that program size will
increase unnecessarily.
Related Articles:
Search Engine and Ranking
Crawling
Start from an HTML, save the file, crawl its links
def collect_doc(doc)
-- save doc
-- for each link in doc
---- collect_doc(link.href)
Build Word Index
Build a set of tuples
{
word1 => {doc1 => [pos1, pos2, pos3], doc2 => [pos4]}
word2 => {...}
}
def build_index(doc)
-- for each word in doc.extract_words
---- index[word][doc] << style="font-weight: bold;" size="5">Search
Given a set of words, locate the relevant docs
A simple example ...
def search(query)
-- Find the most selective word within query
-- for each doc in index[most_selective_word].keys
---- if doc.has_all_words(query)
------ result << doc
-- return result
Ranking
There are many scoring functions and the result need to be able to combine these scoring functions in a flexible way
def scoringFunction(query, doc)
-- do something from query and doc
-- return score
Scoring function can be based on word counts, page rank, or where the location of words within the doc ... etc.
Scoring need to be normalized, say within the same range.
weight is between 0 to 1 and the sum of all weights equals to 1
def score(query, weighted_functions, docs)
-- scored_docs = []
-- for each weighted_function in weighted_functions
---- for each doc in docs
------ scored_docs[doc] += (weight_function[:func](query, doc) * weight_function[:weight])
-- return scored_docs.sort(:rank)
Start from an HTML, save the file, crawl its links
def collect_doc(doc)
-- save doc
-- for each link in doc
---- collect_doc(link.href)
Build Word Index
Build a set of
{
word1 => {doc1 => [pos1, pos2, pos3], doc2 => [pos4]}
word2 => {...}
}
def build_index(doc)
-- for each word in doc.extract_words
---- index[word][doc] << style="font-weight: bold;" size="5">Search
Given a set of words, locate the relevant docs
A simple example ...
def search(query)
-- Find the most selective word within query
-- for each doc in index[most_selective_word].keys
---- if doc.has_all_words(query)
------ result << doc
-- return result
Ranking
There are many scoring functions and the result need to be able to combine these scoring functions in a flexible way
def scoringFunction(query, doc)
-- do something from query and doc
-- return score
Scoring function can be based on word counts, page rank, or where the location of words within the doc ... etc.
Scoring need to be normalized, say within the same range.
weight is between 0 to 1 and the sum of all weights equals to 1
def score(query, weighted_functions, docs)
-- scored_docs = []
-- for each weighted_function in weighted_functions
---- for each doc in docs
------ scored_docs[doc] += (weight_function[:func](query, doc) * weight_function[:weight])
Collaborative Filtering
Given a set of user's rating on movies, how to recommend movies to a new user ?
Ideas from the book: Collective Intelligence chapter one
Given a set of ratings per user
[ person1 => {movieA => rating-1A, movieB => rating-1B},
person2 => {movieX => rating-2X, movieY => rating-2Y, movieA => rating-2A}
...
]
Determine similarity
person1 and person2 are similar if they have rate the same movies with similar ratings
person_distance =
square_root of sum of
-- for each movie_name in person1.ratings.keys
---- if (person2.ratings.keys contains movie_name)
------ square(person1.ratings[movie_name] - person1.ratings[movie_name])
Person similarity =
0 if no common movies in corresponding ratings
1 / (1 + person_distance) otherwise
How to find similar persons to personK ?
Calculate every other person's similarity to personK, and sorted by similarity.
How about movie similarity ?
Invert the set of rankings to ...
[ movieA => {person1 => rating-1A, person2 => rating-2A},
movieB => {person1 => rating-1B}
movieX => {person2 => rating-2X}
movieY => {person2 => rating-2Y}
...
]
movie_distance =
square_root of sum of
-- for each person_name in movieX.ratings.keys
---- if (movieX.ratings.keys contains person_name)
------ square(movieX.ratings[person_name] - movieY.ratings[person_name])
Movie similarity =
0 if no common persons in corresponding ratings
1 / (1 + movie_distance) otherwise
How to find similar movies to movieX ?
Calculate every other movie's similarity to movieX, and sorted by similarity.
Making recommendations
Lets say there is a new personK provide his ratings. How do we recommend movies that may interests him ?
User-based filtering
For each person in persons
-- similarity = person_similarity(personK, person)
-- For each movie_name in person.ratings.keys
---- weighted_ratings[movie_name] += (similarity * person.ratings[movie_name])
---- sum_similarity[movie_name] += similarity
For each movie_name in weighted_ratings.keys
-- weighted_ratings[movie_name] /= sum_similarity[movie_name]
return weighted_ratings.sort_by(:rating)
Item-based filtering
Pre-calculate the movie similarity
For each movie in movies
-- neighbors[movie] = rank_similarity(movie, no_of_close_neighbors)
{
movie1 => {movieA => similarity1A, movieB => similarity1B}
movie2 => {movieC => similarity2C, movieD => similarity2D}
}
At run time ...
personK => {movieX => rating-kX, movieY => rating-kY}
For each movie in personK.ratings.keys
-- for each close_movie in neighbors[movie]
---- weight_ratings[close_movie] += neighbors[movie][close_movie] * personK.ratings[movie]
---- similarity_sum[close_movie] += neighbors[movie][close_movie]
For each target_movie in weight_ratings.keys
-- weight_ratings[target_movie] /= similarity_sum[target_movie]
return weight_ratings.sort_by(:rating)
Ideas from the book: Collective Intelligence chapter one
Given a set of ratings per user
[ person1 => {movieA => rating-1A, movieB => rating-1B},
person2 => {movieX => rating-2X, movieY => rating-2Y, movieA => rating-2A}
...
]
Determine similarity
person1 and person2 are similar if they have rate the same movies with similar ratings
person_distance =
square_root of sum of
-- for each movie_name in person1.ratings.keys
---- if (person2.ratings.keys contains movie_name)
------ square(person1.ratings[movie_name] - person1.ratings[movie_name])
Person similarity =
0 if no common movies in corresponding ratings
1 / (1 + person_distance) otherwise
How to find similar persons to personK ?
Calculate every other person's similarity to personK, and sorted by similarity.
How about movie similarity ?
Invert the set of rankings to ...
[ movieA => {person1 => rating-1A, person2 => rating-2A},
movieB => {person1 => rating-1B}
movieX => {person2 => rating-2X}
movieY => {person2 => rating-2Y}
...
]
movie_distance =
square_root of sum of
-- for each person_name in movieX.ratings.keys
---- if (movieX.ratings.keys contains person_name)
------ square(movieX.ratings[person_name] - movieY.ratings[person_name])
Movie similarity =
0 if no common persons in corresponding ratings
1 / (1 + movie_distance) otherwise
How to find similar movies to movieX ?
Calculate every other movie's similarity to movieX, and sorted by similarity.
Making recommendations
Lets say there is a new personK provide his ratings. How do we recommend movies that may interests him ?
User-based filtering
For each person in persons
-- similarity = person_similarity(personK, person)
-- For each movie_name in person.ratings.keys
---- weighted_ratings[movie_name] += (similarity * person.ratings[movie_name])
---- sum_similarity[movie_name] += similarity
For each movie_name in weighted_ratings.keys
-- weighted_ratings[movie_name] /= sum_similarity[movie_name]
return weighted_ratings.sort_by(:rating)
Item-based filtering
Pre-calculate the movie similarity
For each movie in movies
-- neighbors[movie] = rank_similarity(movie, no_of_close_neighbors)
{
movie1 => {movieA => similarity1A, movieB => similarity1B}
movie2 => {movieC => similarity2C, movieD => similarity2D}
}
At run time ...
personK => {movieX => rating-kX, movieY => rating-kY}
For each movie in personK.ratings.keys
-- for each close_movie in neighbors[movie]
---- weight_ratings[close_movie] += neighbors[movie][close_movie] * personK.ratings[movie]
---- similarity_sum[close_movie] += neighbors[movie][close_movie]
For each target_movie in weight_ratings.keys
-- weight_ratings[target_movie] /= similarity_sum[target_movie]
return weight_ratings.sort_by(:rating)
Using a Stack to Reverse Numbers
Yeah, I heard many of you saying this and I know it’s no big deal to
reverse a number and neither is it using stack to do so. I am writing this just
to give you an example of how certain things in a program can be done using
stacks. So, let’s move on…
As many of you already know, a stack is a Data Structure in which data can
be added and retrieved both from only one end (same end). Data is stored linearly
and the last data added is the first one to be retrieved, due to this fact it
is also known as Last-In-First-Out data structure. For more info please read
Data
Structures: Introduction to Stacks.
Now, let’s talk about reversing a number, well reversing means to rearrange
a number in the opposite order from one end to the other.
Suppose we have a number
12345
then its reverse will be
54321
Ok, now let’s have a look at the example program which does this:
// Program in C++ to reverse
// a number using a Stack
// PUSH -> Adding data to the sat ck
// POP -> Retrieving data from the stack
#include<iostream.h>
// stack class
class stack
{
int arr[100];
// 'top' will hold the
// index number in the
// array from which all
// the pushing and popping
// will be done
int top;
public:
stack();
void push(int);
int pop();
};
// member functions
// of the stack class
stack::stack()
{
// initialize the top
// position
top=-1;
}
void stack::push(int num)
{
if(top==100)
{
cout<<"\nStack Full!\n";
return;
}
top++;
arr[top]=num;
}
int stack::pop()
{
if(top==-1)
{
return NULL;
}
return arr[top--];
}
// member function definition ends
void main()
{
stack st;
int num, rev_num=0;
int i=1, tmp;
cout<<"Enter Number: ";
cin>>num;
// this code will store
// the individual digits
// of the number in the
// Stack
while(num>0)
{
st.push(num%10);
num/=10;
}
// code below will retrieve
// digits from the stack
// to create the reversed
// number
tmp=st.pop();
while(tmp!=NULL)
{
rev_num+=(tmp*i);
tmp=st.pop();
i*=10;
}
cout<<"Reverse: "<<rev_num<<endl;
}
The above code is pretty much straightforward and I leave it up to you to understand
it!
P.S. If you experience any problems understanding it please first read the
article Data
Structures: Introduction to Stacks
Related Articles:
Classes and Structures in C++
In C, a structure (struct) gives us the ability to organize similar data together.
You may wonder what I said. It is so in C, this is because structure is one
of the few things which is more or less entirely different in the two languages
(C and C++).
In C++, the role of structures is elevated so much as to be same as that of
a class. In C, structure could only include data as variables and arrays but
in C++ they can also include functions, constructors, destructors etc. and in
fact everything else that a class can. Knowing this, it wouldn’t be wrong
to say that in C++, structures are an alternate way of defining a class. However
there are some differences.
Look at the following code:
// First difference between a class
// and a structure in C++
// define a structure
struct mystruct
{
char name[25];
int id_no;
};
void main()
{
mystruct a;
// in C, it is necessary to
// include the struct keyword
// Example:
// struct mystruct a;
...
...
...
}
In C, we must declare an object of a structure by using the keyword struct but
in C++ it is optional to do so (just like a class).
Another difference is the fact that all the data or functions inside a struct
are public by default contrary to a class, inside which scope is private by
default.
It is obvious from the following code:
// Second difference between a class
// and a structure in C++
// define a structure
struct mystruct
{
// public by default
// So convenient to start with
// public declarations
void func1();
void func2();
...
...
private:
// now private
int data1;
int data2;
...
...
};
// define a class
class myclass
{
// private by default
int data1;
int data2;
...
...
public:
// now public
void func1();
void func2();
...
...
};
While you’ve got the power, you should not define a class as a struct
since it is not a good practice. Structures and classes should be used as per
their original purposes to avoid unnecessary complications and misunderstandings.
Related Articles:
Subscribe to:
Posts (Atom)