encoding scheme – Coding efficiency of a code representing 50,000 characters, using unicode

I need to find the coding efficiency of a code representing 50,000 characters using unicode.
Here is what I did,

the number of characters is 50,000

and 2 raised to the power of 15 is 32,768

so bits used is 32,768 and bits needed is 50,000

so 32,768/50,000 multiplied by 100 is 65.536%.

I am completely new to this topic, sorry if I am wrong. Thank you.

memory efficiency – Object pool implementation c++

I’ve been trying to find a way to implement an object pool for my game. I’ve found a few examples on the internet and most of them use std::lists and an example of it in a book; Game development patterns and best practices that also use std::list.

I’ve been told, however, that it’s kind of pointless to use lists for object pooling since returning an object back to the pool means that memory has to be allocated again.

I have also seen people utilize std::stack but I assume the same issue exists.

Here’s the code I made for an object pool class following the book’s example:

    /* This object has only an int data type (value).
       One method to se it and another one to print it. */
class Object
{
    public: 

        Object()
        {
            SetValue();
            std::cout << "Constructed/Reset." << std::endl;
        }

            // Copy constructor
        Object( Object& other )
        {
            this->mValue = other.mValue;
            std::cout << "Constructed." << std::endl;
        }

        ~Object()
        {
            std::cout << "Destroyed." << std::endl;
        }

        void SetValue( int val = -1 )
        {
            mValue = val;
        }

        void PrintValue()
        {
            std::cout << this->mValue << std::endl;
        }

    private:
        int mValue;

};

class Pool
{
    public:
        Pool()
        {
            std::cout << "Pool created!n";
        }

        ~Pool()
        {
            std::cout << "Pool destroyed!n";
        }

        void Fill( int size )
        {
            for( int i = 0; i < size; i++ )
            {
                Object* obj = new Object();
                pool.push_back( obj );
            }
            std::cout << "Objects created!" << "nObjects in pool: "
                      << pool.size() << std::endl;
        }

        Object* AquireObject()
        {
            if( !pool.empty() )
            {
                Object* obj = pool.back();
                pool.pop_back();
                
                std::cout << "Object aquired!"
                          << "nNumber of objects in pool: " << pool.size() << std::endl;

                return obj;
            }
            else
            {
                std::cout << "Object created and aquired!"
                          << "nNumber of objects in pool: " << pool.size() << std::endl;
                return new Object();
            }
        }

        void ReleaseObject( Object* returningObject )
        {
            returningObject->SetValue();
            pool.push_back( returningObject );
            std::cout << "Object returned to the pool!"
                      << "nNumber of objects in pool: " << pool.size() << std::endl;
        }

        void Clear()
        {
            while( !pool.empty() )
            {
                Object* obj = pool.back();
                pool.pop_back();
                delete obj;
            }
            std::cout << "Objects deleted!"
                      << "nNumber of objects in pool: " << pool.size() << std::endl;
        }

    private:
        std::list<Object*> pool;
};

I also made a slightly different version that uses unique pointers instead:

    /* This object has only an int data type (value).
       One method to se it and another one to print it. */
class Object
{
    public: 

        Object()
        {
            SetValue();
            std::cout << "Constructed/Reset." << std::endl;
        }

            // Copy constructor
        Object( Object& other )
        {
            this->mValue = other.mValue;
            std::cout << "Constructed." << std::endl;
        }

        ~Object()
        {
            std::cout << "Destroyed." << std::endl;
        }

        void SetValue( int val = -1 )
        {
            mValue = val;
        }

        void PrintValue()
        {
            std::cout << this->mValue << std::endl;
        }

    private:
        int mValue;

};

    // Object pool using std::list
class Pool
{
    public:
        Pool() = default;
        ~Pool() = default;

            /* Fills the pool (list) with a given size using an Object class (previously defined)
               as a reference using its copy constructor.*/
        void Fill( int size, Object* obj )
        {
            for( int i = 0; i < size; i++ )
            {
                std::unique_ptr<Object> object = std::make_unique<Object>( *obj );
                pool.push_back( std::move( object ) );
            }
        }

            // Clears all items in the list.
        void PoolIsClosed()
        {
            pool.clear();
        }

            // Returns an instance of an object within the list.
        std::unique_ptr<Object> GetObject()
        {
            if( !pool.empty() )
            {
                std::unique_ptr<Object> object = std::move( pool.front() );
                pool.pop_front();
                
                std::cout << "Object retrieved." << "nObjects in pool: "
                          << pool.size() << std::endl;
                
                return object;
            }
            else
            {
                /* "WARNING: NOT ALL CONTROL PATHS RETURN A VALUE." */
                std::cout << "Pool is empty." << std::endl;
            }
        }

            // Returns an instance back to the object list.
        void returnToPool( std::unique_ptr<Object> returningObject )
        {
            pool.push_back( std::move( returningObject ) );
            
            std::cout << "Object returned." << "nObjects in pool: "
                      << pool.size() << std::endl;
        }

    private:
        std::list<std::unique_ptr<Object>> pool;
};

I want to know if an implementation like this is really pointless and if so, is there a simple-ish way to implement a basic object pool class?

I know that the boost library has its own implementation of an object pool… Has anyone of you used it before? I would love to know more about it, is it hard to use?..

I also found this object pool library: https://github.com/mrDIMAS/SmartPool which looks promising and kind of easy to use but I don’t know how it works under the hood, it was a bit complicated for me to understand. Any opinions about this one?

efficiency – Efficient method for finding 1’s in binary representations

Say I have a binary number of N bits, and I need to find every combination that have M 1’s. For example, if N = 3 and M = 1, then 100, 010, 001 are the allowed combinations. I have read that a more efficient way of finding these combinations for large N is by dividing the bits into two halves, and then combining combinations from each half such that the total number of 1’s is M. For example, if N = 3 and M = 2, and we divide the bits into lengths of two and one, the half with one only has the combinations 0 and 1, while the half with two have the combinations 00, 01, 10, 11. 0 can only be combined with 11, and 1 can only be combined with 01 and 10. Thus the only total combinations are 011, 101, and 110.

Why is this method more effficient?

python – AStar Implementation and Efficiency

This is my implementation of an AStar-like algorithm for maze solving.

A quick summary of the problem I am trying to solve with my algorithm might be: A simple binary maze is given to you to solve, you may only go in the standard cardinal directions: north, east, west and south. There is a twist, however: You may also break only one wall. Create a function solution(maze) which determines the minimal number of steps to reach the end defined at point (width-1, height-1) from the start point (0, 0).

class AStar:
    def __init__(self, maze):
        self.queue = ()
        self.visited = set()
        self.maze = maze
        self.end = len(self.maze)-1, len(self.maze(0))-1

    def forward(self):
        self.queue.append((0, 0, False, 0, 0, None))

        while self.queue:
            self.queue = sorted(self.queue, key=lambda x: x(-3)+x(-4))  #Might be suboptimal to sort every time...
            node = self.queue.pop(0)
            
            if node(0:2) == self.end:
                return node
            self.visited.add(node(0:2))

            new_nodes = self.rulebook(node)
            self.queue.extend(new_nodes)
    
    def rulebook(self, node):
        x, y, broken, cost, heuristic, _ = node
        new_nodes = ()

        #------RULES & ACTIONS-----#
        for direction in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            x_dir, y_dir = direction
            x_pdir = x + x_dir
            y_pdir = y + y_dir
            distance = self.distance((x_pdir, y_pdir), self.end)
            if (x_pdir, y_pdir) not in self.visited:
                if (x_pdir,y_pdir) not in self.visited:
                    if (x_pdir < len(self.maze) and y_pdir < len(self.maze(0))):
                        if (x_pdir >= 0 and y_pdir >= 0):
                            if self.maze(x_pdir)(y_pdir) == 1:
                                if not broken:
                                    new_nodes.append((x_pdir, y_pdir, True, cost+1, 
                                        distance, node))
                            elif self.maze(x_pdir)(y_pdir) == 0:
                                new_nodes.append((x_pdir, y_pdir, False, cost+1, 
                                    distance, node))
        return new_nodes
    def distance(self, node, end):
        #Chose the Taxicab Metric as it is more of a fit for the problem, 
        #as you cannot go diagonally in the problem statement.
        x = node(0)
        y = node(1)
        end_x = end(0)
        end_y = end(1)
        return abs(x - end_x) + abs(y - end_y)
    def backward(self, node):
        steps = 0
        while node != None:
            steps += 1
            node = node(-1)
        return steps

def solution(maze):
    astar = AStar(maze)
    end_node = astar.forward()
    steps = astar.backward(end_node)
    return steps

efficiency – Which of the query approaches are more efficient?

There are two relations, registered(participant,topic) and fee(participant,amount).
The primary key for registered is (participant, topic) and the primary key for fee is participant.

The premise is that of an academic conference. The relation registered stores the names of the participants and the names of the topics registered by them. On the other hand, the fee relation stores the names of participants and the fees that they have paid for the topics.

Also the participants are segregated into five categories depending on the amount of fees they paid. The fees paid under each category are Rs 1000, 2000, 3000, 4000 and 5000. It may be safely assumed that each category has equal number of participants.

Now the query that we are interested in is :

List all topics registered by participants who have paid more than a given amount, x

The query is presented in the following two approaches:

Approach 1 :

   create table r1 as select * from fee where amount > x ;
   select distinct topic
   from registered as R, r1 as T
   where R.participant = T.participant ; 

Approach 2 :

   select distinct topic
   from registered as R, fee as T
   where R.participant=T.participant and amount > x ;

Henceforth, I have two questions that have arisen…

(i) Which if the approaches is faster for x = 3000 , and why ?

(ii) Which approach has less disk access time ?


It would be great if I could have some help on the above problem. I’ll share my advances on the same :

Assuming there are m participants in each of the categories,the number of rows in relation fee would be 5m. In Approach 1, there’s a query running throw these 5m entries to extract out those which have a fees amount value greater than x ( = 3000, here ). Now in this context, this would mean table r1 that Approach 1 creates would have 2m entries ( due to the fact that there are only two categories above 3000 viz 4000 and 5000 ). So finally when we select distinct topics from the subsequent query we make 2m * 5m ( for R.participant = T.participant ) = 10m + 5m = 15m comparisons to ascertain the fact in approach 1.

Whereas in Approach 2, we don’t have any such table as r1 being created, and that makes the single select distinct topic query on registered and fee comparing participant names and a check for amount > x use 5m * 5m = 25m comparisons to retrieve the data we looking for in the query result.

So could this enable me to say that Approach (1) would work faster than Approach (2) for x=3000 in the given query ?

C++ Incredibly Precise Sorter | Efficiency and speed of sorting algorithms

Hey Guys,
I’m in the process of building a console program in C ++ that allows users to:

  • sort a sequence of numbers loaded from a TXT file
  • save sorted sequence in a new TXT file
  • measure the sorting time for individual algorithm

I decided to write such a program because I want to learn algorithms, how different sorting algorithms work and I was curious how efficient/fast each individual algorithm is.

At the moment I have implemented

  • Bubble Sort
  • Insertion Sort
  • IntroSort (from C++ STD)
  • Selection Sort
  • Merge Sort
  • Quicksort

This is a sample output of the program

   (Bubble Sort)  Took:  77817989 µs   (77817.989 ms) (77s) to sort 100000 numbers
(Insertion Sort)  Took:  24974911 µs   (24974.911 ms) (24s) to sort 100000 numbers
      (STD Sort)  Took:     33990 µs      (33.990 ms)  (0s) to sort 100000 numbers
(Selection Sort)  Took:  20961005 µs   (20961.005 ms) (20s) to sort 100000 numbers
    (Merge Sort)  Took:    364995 µs     (364.995 ms)  (0s) to sort 100000 numbers
     (Quicksort)  Took:     25993 µs      (25.993 ms)  (0s) to sort 100000 numbers

Here’s the code for the project on github, as there would be too much pasting on this page.

Okay, end of story about the project, I have a few questions for experienced programmers

  1. Could anyone do some little code review please?
    I wonder if I have built the project structure correctly. What could be changed in the code. What is coded incorrectly. What bad practices have I committed. e.t.c
  2. I wonder if the measurement results are reliable in any way. How the system speed or the order in which the sorting function is called affects the results
  3. I plan to implement even more sorting algorithms. In your opinion, what other features could I add to make the project more interesting and to impress the future employer?
  4. And one last thing. What is your honest opinion about this project?

Thank you very much in advance for any help

optimization – In a language interpreted line by line – is optimizing similar lines of code within a module into functions better in terms of efficiency?

Python does not interpret line by line. The default Python implementation (CPython) compiles the entire module to bytecode and then runs it. However, the CPython implementation does not place an emphasis on optimizations. The interpreter will do exactly what you tell it to do, which means that small changes to your code can have a big performance effect. In particular, function or method calls are relatively “slow” in CPython.

But in absolute terms, it doesn’t matter for performance. You’re writing code for GUI automation. The interaction with the GUI will be far slower than calling a function or parsing some lines of code. This is a bit like being on a journey between two cities. You are proposing to take a shortcut that will save you a minute on this tour, when you’ll actually spend an hour waiting in an airport to board a flight.

So performance doesn’t really matter here. What does matter? Maintainability. Instead of copy and pasting the same code four times, it is usually better to clearly separate the things that stay the same from the things that differ between instances of this code. A function is the perfect tool to express that. Thus, while your alternative solution with a function might run 200 nanoseconds slower, it is the objectively better approach here.

In reality, writing maintainable code with good abstractions is good for performance. When your code is easy to understand, it is easier to understand how performance can be improved, and to implement those improvements. For example, if you find that there’s a faster alternative for the checkExists() method, you’ll now only have to update it in one place. Of course, most code is not performance-critical, so such optimizations are unlikely to have a noticeable effect.

c – efficiency difference of & vs == in if

I was reading some code and stumpbled over a weird if assignment:

#define compVal 1
uint someVal;
...
someVal = 1; //or 0, large 1 not allowed!
...
if (someVal & compVal)
...

so the code should only allow someVal to become 0 or 1 so I guess we could consider it to be boolean. The guy who wrote the code is farely famous to write incredible efficient code however I wonder whether that
is any better than

if (someVal == compVal)
...

or what probably would be the most efficient but in that case less well readable:

if(someVal)
...

any thoughts about that regarding resource efficiency, readability etc?

Thanks!

c++ – Does wrapping functions/’things’ in classes reduce efficiency?

Do you have an application where you need to squeeze out the last bit of performance from the user’s computer? Chances are that you don’t. For 99.9% of your code the nanoseconds that you might waste by wrapping things in a class don’t matter.

And when it matters, you will likely find that optimisation is a lot easier if something is wrapped in a class and you have just one place to optimise.

What you really should think about: Development time. If you want speed, then writing code that is easier to maintain and develop saves you time, which you can use to find places where you can save milliseconds instead of nanoseconds.

r – Replacing for loop for higher efficiency

I’m trying to find an efficient way to replace a for loop in my code. I’ve found a workaround but I’m sure there is a more “R-friendly” way to do this.


df<-structure(list(YY = c(2020, 2020, 2021, 2021, 2021), DD = c(6, 
13, 19, 28, 3), MM = c("Fev", "Fev", "Fev", "Fev", "Mar"), Date = structure(c(18664, 
18671, 18677, 18686, 18689), class = "Date"), `ID (FIFA)` = c("FRA D1", 
"FRA D1", "FRA D1", "FRA D1", "FRA D1"), Country = c("France", 
"France", "France", "France", "France"), League = c("Ligue 1", 
"Ligue 1", "Ligue 1", "Ligue 1", "Ligue 1"), Season = c("2020/2021", 
"2020/2021", "2020/2021", "2020/2021", "2020/2021"), HOME = c("Lyon", 
"Lyon", "Brest", "Marseille", "Lyon"), AWAY = c("Strasbourg", 
"Montpellier", "Lyon", "Lyon", "Rennes"), `Final Scores` = c(3, 
1, 2, 1, 1), ...12 = c(0, 2, 3, 1, 0), ...13 = c("H", "A", "A", 
"D", "H"), ...14 = c(NA_character_, NA_character_, NA_character_, 
NA_character_, NA_character_), `ET/Pen/Awd` = c(NA_character_, 
NA_character_, NA_character_, NA_character_, NA_character_), 
    `1st Half Scores` = c(NA_real_, NA_real_, NA_real_, NA_real_, 
    NA_real_), ...17 = c(NA_real_, NA_real_, NA_real_, NA_real_, 
    NA_real_), ...18 = c(NA_character_, NA_character_, NA_character_, 
    NA_character_, NA_character_), ...19 = c(NA_character_, NA_character_, 
    NA_character_, NA_character_, NA_character_), `2nd Half Scores` = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...21 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...22 = c(NA_character_, 
    NA_character_, NA_character_, NA_character_, NA_character_
    ), ...23 = c(NA_character_, NA_character_, NA_character_, 
    NA_character_, NA_character_), FTMoneyline...24 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...25 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...26 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), `Payout, %...27` = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), FTMoneyline...28 = c(1.45, 
    1.38, 6.5, 5, 1.61), ...29 = c(5.25, 5.5, 4.85, 4.2, 4.4), 
    ...30 = c(8, 8, 1.5, 1.7, 5.9), `Payout, %...31` = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), `FT TG 2.5...32` = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...33 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), `FT TG 2.5...34` = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), ...35 = c(NA_real_, 
    NA_real_, NA_real_, NA_real_, NA_real_), OUTCOME = c(1, 3, 
    3, 2, 1), REFGAME = c("G236038", "G236098", "G236155", "G236247", 
    "G236276"), m1 = c(4.9, 4.96, 4.28333333333333, 3.63333333333333, 
    3.97), sd = c(3.28899680753874, 3.34287301583533, 2.54771139129481, 
    1.72143351115671, 2.17708520733572), indxcol = c(1L, 1L, 
    3L, 3L, 1L), sp1 = c(-3.8, -4.12, 1.65, 0.8, -2.79), sp2 = c(2.75, 
    2.5, -3.35, -2.5, 1.5), ovr = c(0.513136288998362, 3.14558629776023, 
    2.66983875231297, 2.63305322128851, 1.78822651188164), wavg = c(0.357142857142857, 
    0.369623655913978, 0.377431906614786, 0.385321100917431, 
    0.36943744752309), ospr = c(5.51724137931035, 5.79710144927536, 
    4.33333333333333, 2.94117647058824, 3.66459627329193)), row.names = c(NA, 
-5L), class = c("tbl_df", "tbl", "data.frame")) 

The objective of my script is to count for each HOME team how many times in the previous games it was the bookmaker’s lowest decimal odds (odds are in col df(28:30)), and how many times it actually corresponded to the OUTCOME of the game.
This way I can get an accuracy ratio (r/t*100).

Here is the code with the for loop part I want to replace:

    if(is.null(nrow(df))|nrow(df)==0){
      r<-0
      return(r)
    }
    r<- 0
    t<- 0
    for(i in nrow(df):1){
      if(grep(team,df(i,))==9 & which.min(df(i,28:30))((1))==1){
        t<-t+1
        if(df(i,"OUTCOME")==1){
          r<-r+1
        }
      } else if(grep(team,df(i,))==10 & which.min(df(i,28:30))((1))==3){
        t<-t+1
        if(df(i,"OUTCOME")==3){
          r<-r+1
        }
      }
    }
    if(r==0 | t==0){
      return(0)
    }
    return(r/t*100) 

And here is the workaround I’ve found but it doesn’t look optimal:

    r<- 0
    t<- 0
    df1<- df(grepl(team,df$HOME) & apply(df(28:30),1,which.min)==1,)
    if(is.null(nrow(df1))|nrow(df1)==0){
      r<-0
      return(r)
    }
    r1 <-df1(df1("OUTCOME")==1,)
    df2<- df(grepl(team,df$AWAY) & apply(df(28:30),1,which.min)==3,)
    if(is.null(nrow(df2))|nrow(df2)==0){
      r<-0
      return(r)
    }
    r2<- df2(df2("OUTCOME")==3,)
    t<- sum(nrow(df1),nrow(df2))
    r<-sum(nrow(r1),nrow(r2))
    if(r==0 | t==0){
      return(0)
    }
    return(r/t*100)