DFA creation from string I have fairly simple Python 3 code that creates a DFA from a string.

It works great, but I believe it can be made more efficient. There are a total of 3 loops:

First iterates over the string
Second iterates the alphabet the string can be composed from. In this scenario it is always length 26. The standard English alphabet.
Third iterates over the string again

From what I believe, I can only break out of the third loop and only if a prefixed string is found.

My comments provide a good explanation of what I am doing in the code.

def create_from_text(self, text):
    """
        Create/edit the DFA from the provided text
    """

    # We start by editing the first state to accept the first character in
    # the text provided. After that we check the next character and create
    # a new state that goes to the 2nd character. Here we check if a
    # character that does not go to the 2nd character will create a prefix
    # of the text in combination with an any number of characters preceeding
    # it that . e.g. (oopoops)
    #       oo -> o     We want a `p` but got `o`.
    #                   But we check if, starting with 2nd character, `o`,
    #                   any combination after that, appended with the bad
    #                   character creates a prefix of the text. The first
    #                   found will always be the best match.
    #                   `oo` is a prefix of `oopoops` so we can start back
    #                   at index 2 since `oo` is of length 2. We mark the
    #                   state we are on with that state at that character.

    self.states[0].transitions[text[0]] = 1
    for i in range(len(text)):
        if i == 0:
            continue
        new_state = State(i)
        for j in self.alphabet:
            if j == text[i]:
                # Easiest part, just set the transition to the next state
                new_state.addTransition(i + 1, j)
            else:
                # Now do that check we spoke of earlier
                found = False
                for k in range(len(text)):
                    if k == 0:
                        continue
                    try:
                        if text.index(text[k:i] + j) == 0 and k <= i:
                            new_state.addTransition(len(text[k:i] + j), j)
                            found = True
                            break
                    except ValueError:
                        pass

                if not found:
                    new_state.addTransition(0, j)

        self.states.append(new_state)

    # Make every transition in the last state point to itself
    last_state = State(len(self.states))
    for j in self.alphabet:
        last_state.addTransition(len(self.states), j)
    self.states.append(last_state)

A sample output for string oopoops:

Number of states: 1
Accepting states: 0
Alphabet: abcdefghijklmnopqrstuvwxyz
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 6 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 7 0 0 0 0 0 0 0
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7

Run time on a string of 2048 characters was about 5 minutes.

Constructors should be class methods

Your method suggests, that an instance of the respective class is being created using the given text.
Thus you should make it a classmethod:

@classmethod
def create_from_text(cls, text):
    …

Comments vs. docstrings

Your multi-line comment describes the underlying algorithm.
You should summarize it in the method's docstring and move the complete description to your respective documentation docs.

Useful comments

This is useless:

# Easiest part, just set the transition to the next state
# Now do that check we spoke of earlier

while that may be helpful:

# Make every transition in the last state point to itself

Loop variables

While the i in for i in range(len(text)) is pretty self-explanatory, the j in for j in self.alphabet: is not.
What is j? Another index? A word? A character?
Consider renaming j to index, word or char respectively.

PEP 8

You follow it consistently with the exception of self.addTransition.

Iteration over strings.

Instead of

for i in range(len(text)):
    …
    if j == text[i]:

Use enumerate:

for index, char in enumerate(text):
    …
    if j == char:


Simulate round-robin tournament draw I decided to implement the round robin algorithm in Python. My code takes a list of teams as input and prints the schedule.

This is my first try to write something by my own after taking some online courses, so I am absolutely sure that this code must be significantly improved.

Here it is:

import random

def simulate_draw(teams):
    if len(teams) % 2 == 0:
        simulate_even_draw(teams)
    else:
        simulate_odd_draw(teams)

def simulate_even_draw(teams):
    dic = {}
    for i in range(len(teams)):
        dic[i] = teams[i]

    games = []
    arr1 = [i+1 for i in range(int(len(teams)/2))]
    arr2 = [i+1 for i in range(int(len(teams)/2), len(teams))][::-1]

    for i in range(len(teams)-1):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        zipped = list(zip(arr1, arr2))
        games.append(zipped)
        zipped = []

    for game in games:
        for gm in list(game):
            r = random.sample(gm, len(gm))
            print(dic[r[0]-1] + ' plays ' + dic[r[1]-1])

def simulate_odd_draw(teams):
    dic = {}
    for i in range(len(teams)):
        dic[i] = teams[i]
    dic[i+1] = ''
    games = []
    arr1 = [i+1 for i in range(int((len(teams)+1)/2))]
    arr2 = [i+1 for i in range(int((len(teams)+1)/2), len(teams)+1)][::-1]
    for i in range(len(teams)):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        zipped = list(zip(arr1, arr2))
        games.append(zipped)
        zipped = []
    for game in games:
        for gm in list(game):
            r = random.sample(gm, len(gm))
            if len(teams)+1 not in r:
                print(dic[r[0]-1] + ' plays ' + dic[r[1]-1])

I think that big blocks of code that largely repeat themselves inside 2 functions may be united in one function, but not sure how to implement it.

Making the code testable and tested

The first step to improve your code is to try to make it testable. By doing so, you usually have to deal with Separation of Concerns: in your case, you have to split the logic doing the output from the logic computing games. The easiest way to do so it to rewrite slightly the simulate_XXX functions to return values instead of writing them.

Once it it done, you can easily write tests for the function computing the games (in order to make this easier to implement, I've extracted out the randomising part as well).

At this stage, we have something like:

import random

def simulate_draw(teams):
    """Return the list of games."""
    if len(teams) % 2 == 0:
        return simulate_even_draw(teams)
    else:
        return simulate_odd_draw(teams)

def simulate_even_draw(teams):
    """Return the list of games."""
    matches = []
    dic = {}
    for i in range(len(teams)):
        dic[i] = teams[i]

    games = []
    arr1 = [i+1 for i in range(int(len(teams)/2))]
    arr2 = [i+1 for i in range(int(len(teams)/2), len(teams))][::-1]

    for i in range(len(teams)-1):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        zipped = list(zip(arr1, arr2))
        games.append(zipped)
        zipped = []

    for game in games:
        for gm in list(game):
            r = gm # remove randomness for now - random.sample(gm, len(gm))
            a, b = dic[r[0]-1], dic[r[1]-1]
            matches.append((a, b))
            # print(a + ' plays ' + b)
    return matches

def simulate_odd_draw(teams):
    """Return the list of games."""
    matches = []
    dic = {}
    for i in range(len(teams)):
        dic[i] = teams[i]
    dic[i+1] = ''
    games = []
    arr1 = [i+1 for i in range(int((len(teams)+1)/2))]
    arr2 = [i+1 for i in range(int((len(teams)+1)/2), len(teams)+1)][::-1]
    for i in range(len(teams)):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        zipped = list(zip(arr1, arr2))
        games.append(zipped)
        zipped = []
    for game in games:
        for gm in list(game):
            r = gm # remove randomness for now - random.sample(gm, len(gm))
            if len(teams)+1 not in r:
                a, b = dic[r[0]-1], dic[r[1]-1]
                matches.append((a, b))
                # print(a + ' plays ' + b)
    return matches

def displays_simulated_draws(teams):
    """Print the list of games."""
    for gm in simulate_draw(teams):
        a, b = random.sample(gm, len(gm))
        print(a + ' plays ' + b)

def test_simulate_draw():
    """Small tests for simulate_draw."""
    # TODO: Use a proper testing framework
    TESTS = [
        ([], []),
        (['A'], []),
        (['A', 'B', 'C', 'D'], [('A', 'C'), ('D', 'B'), ('A', 'B'), ('C', 'D'), ('A', 'D'), ('B', 'C')]),
        (['A', 'B', 'C', 'D', 'E'], [('A', 'E'), ('B', 'C'), ('A', 'D'), ('E', 'C'), ('A', 'C'), ('D', 'B'), ('A', 'B'), ('D', 'E'), ('B', 'E'), ('C', 'D')]),
    ]
    for teams, expected_out in TESTS:
        # print(teams)
        ret = simulate_draw(teams)
        assert ret == expected_out

if __name__ == '__main__':
    test_simulate_draw()
    displays_simulated_draws(['A', 'B', 'C', 'D'])

Now we can start improving the code in a safer way.

Remove what's not required

dic[i+1] = '' is not required, we can remove it.

Also, resetting zipped to the empty string is not required, we can remove it. Maybe we could get rid of zipped altogether.

Finally, we call for gm in list(game) when game is already a list. We can remove the call to list.

Loop like a native

I highly recommend Ned Batchelder's talk "Loop like a native" about iterators. One of the most simple take away is that whenever you're doing range(len(iterable)), you can probably do things in a better way: more concise, clearer and more efficient.

In your case, we could have:

for i in range(len(teams)):
    dic[i] = teams[i]

replaced by

for i, team in enumerate(teams):
    dic[i] = team

And we could do:

for _ in teams:

instead of

for i in range(len(teams))

(Unfortunately, this can hardly be adapted to the "even" situation)

Note: "_" is a usual variable names for values one does not plan to use.

Dict comprehension

The dictionnary initiation you perform via dict[index] = value in a loop could be done using the Dictionnary Comprehension syntactic sugar.

Instead of:

dic = {}
for i, team in enumerate(teams):
    dic[i] = team

we you can write:

dic = {i: team for i, team in enumerate(teams)}

Now it is much more obvious, it also corresponds to:

dic = dict(enumerate(teams))

Finally, we can ask ourselves how we use this dictionnary: the answer is "to get the team at a given index". Do we really need a dictionnay for this ? I do not think so. We can get rid of the dic variable and use teams directly.

At this stage, we have:

import random

def simulate_draw(teams):
    """Return the list of games."""
    if len(teams) % 2 == 0:
        return simulate_even_draw(teams)
    else:
        return simulate_odd_draw(teams)

def simulate_even_draw(teams):
    """Return the list of games."""
    matches = []
    games = []
    half_len = int(len(teams)/2)
    arr1 = [i+1 for i in range(half_len)]
    arr2 = [i+1 for i in range(half_len, len(teams))][::-1]
    for i in range(len(teams)-1):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        games.append(list(zip(arr1, arr2)))
    for game in games:
        for gm in game:
            r = gm # remove randomness for now - random.sample(gm, len(gm))
            a, b = teams[r[0]-1], teams[r[1]-1]
            matches.append((a, b))
            # print(a + ' plays ' + b)
    return matches

def simulate_odd_draw(teams):
    """Return the list of games."""
    matches = []
    games = []
    half_len = int((len(teams)+1)/2)
    arr1 = [i+1 for i in range(half_len)]
    arr2 = [i+1 for i in range(half_len, len(teams)+1)][::-1]
    for i in range(len(teams)):
        arr1.insert(1, arr2[0])
        arr2.append(arr1[-1])
        arr2.remove(arr2[0])
        arr1.remove(arr1[-1])
        games.append(list(zip(arr1, arr2)))
    for game in games:
        for gm in game:
            r = gm # remove randomness for now - random.sample(gm, len(gm))
            if len(teams)+1 not in r:
                a, b = teams[r[0]-1], teams[r[1]-1]
                matches.append((a, b))
                # print(a + ' plays ' + b)
    return matches

def displays_simulated_draws(teams):
    """Print the list of games."""
    for gm in simulate_draw(teams):
        a, b = random.sample(gm, len(gm))
        print(a + ' plays ' + b)

def test_simulate_draw():
    """Small tests for simulate_draw."""
    # TODO: Use a proper testing framework
    TESTS = [
        ([], []),
        (['A'], []),
        (['A', 'B', 'C', 'D'], [('A', 'C'), ('D', 'B'), ('A', 'B'), ('C', 'D'), ('A', 'D'), ('B', 'C')]),
        (['A', 'B', 'C', 'D', 'E'], [('A', 'E'), ('B', 'C'), ('A', 'D'), ('E', 'C'), ('A', 'C'), ('D', 'B'), ('A', 'B'), ('D', 'E'), ('B', 'E'), ('C', 'D')]),
    ]
    for teams, expected_out in TESTS:
        # print(teams)
        ret = simulate_draw(teams)
        assert ret == expected_out

if __name__ == '__main__':
    test_simulate_draw()
    displays_simulated_draws(['A', 'B', 'C', 'D'])

The right tool for the task

The part:

    arr2.remove(arr2[0])
    arr1.remove(arr1[-1])

could/should probably be written with pop:

    arr2.pop(0)
    arr1.pop()

And now, these line can be merged with arrXX.append(arrYYY[ZZ]):

for i in range(len(teams)-1):
    arr1.insert(1, arr2.pop(0))
    arr2.append(arr1.pop())
    games.append(list(zip(arr1, arr2)))

Removing useless steps

A loop is used to fill an array. Another one is used to iterate over the array. We could try to use a single loop to do everything (disclaimer: this is not always a good idea as far as readability goes).

This removes the need for a few calls to list.

At this stage, we have:

def simulate_even_draw(teams):
    """Return the list of games."""
    matches = []
    half_len = int(len(teams)/2)
    arr1 = [i+1 for i in range(half_len)]
    arr2 = [i+1 for i in range(half_len, len(teams))][::-1]
    for i in range(len(teams)-1):
        arr1.insert(1, arr2.pop(0))
        arr2.append(arr1.pop())
        for gm in zip(arr1, arr2):
            matches.append((teams[gm[0]-1], teams[gm[1]-1]))
    return matches

def simulate_odd_draw(teams):
    """Return the list of games."""
    matches = []
    half_len = int((len(teams)+1)/2)
    arr1 = [i+1 for i in range(half_len)]
    arr2 = [i+1 for i in range(half_len, len(teams)+1)][::-1]
    for i in range(len(teams)):
        arr1.insert(1, arr2.pop(0))
        arr2.append(arr1.pop())
        for gm in zip(arr1, arr2):
            if len(teams)+1 not in gm:
                matches.append((teams[gm[0]-1], teams[gm[1]-1]))
    return matches

Better indices

You generate a list of indices using i+1 and then use val - 1 when you use them. You can make your life easier twice.

Iterable unpacking

Instead of using indices to get elements from an iterable with a know number of elements, you can use iterable unpacking.

You'd get

def simulate_even_draw(teams):
    """Return the list of games."""
    half_len = int(len(teams)/2)
    arr1 = [i for i in range(half_len)]
    arr2 = [i for i in range(half_len, len(teams))][::-1]
    matches = []
    for i in range(len(teams)-1):
        arr1.insert(1, arr2.pop(0))
        arr2.append(arr1.pop())
        for a, b in zip(arr1, arr2):
            matches.append((teams[a], teams[b]))
    return matches

def simulate_odd_draw(teams):
    """Return the list of games."""
    half_len = int((len(teams)+1)/2)
    arr1 = [i for i in range(half_len)]
    arr2 = [i for i in range(half_len, len(teams)+1)][::-1]
    matches = []
    for i in range(len(teams)):
        arr1.insert(1, arr2.pop(0))
        arr2.append(arr1.pop())
        for a, b in zip(arr1, arr2):
            if len(teams) not in (a, b):
                matches.append((teams[a], teams[b]))
    return matches

True divisions

Instead of using "/" and convert the float result to int, you can use "//" which is an integer division.

Other way to compute indices

We could write something like:

indices = list(range(len(teams)))
half_len = len(indices)//2
arr1 = indices[:half_len]
arr2 = indices[:half_len-1:-1]

and

indices = list(range(len(teams)+1))
half_len = len(indices)//2
arr1 = indices[:half_len]
arr2 = indices[:half_len-1:-1]

Altough, if we don't care about order, we could use the more direct:

arr1 = indices[:half_len]
arr2 = indices[half_len:]

Remove the duplicated logic

Don't repeat yourself is a principle of software development that you could easily apply here. Indeed, we have 2 functions that look very similar.

This is trickier than expected and I have to go. I may continue another day.

Batteries included

The Python standard library contains many useful things. Among them, we have the very interesting module itertools which itself contains combinations which is what you want.


Using mutable keyword to implement an owner-pointer class (C++03) For a couple of days, I have been trying to implement an own templated class called owner_ptr (for my little project) whose instances has ownership over a dynamically allocated object (or array). I want this template to support the deletion of dynamically allocated arrays too and also make it possible to pass ownership between owner_ptr objects. I've tried out many things and ideas (the last one was this) but each of them had some drawbacks.

The necessity of passing ownership between owner_ptr objects causes that you must modify the pointer of the passed owner_ptr object during copy-constructing or assignment (you have to set the pointer to NULL). Copy-constructor and assignment operator with const-reference is necessary to make this class work with std::vector.

template <typename T>
class owner_ptr
{
    /* Private members */

public:
    owner_ptr(const owner_ptr<T>&);
    owner_ptr& operator=(const owner_ptr<T>&);

   /* Other public member functions */
}

But how can I modify the objects if I have const-reference to them? The problem can be solved if I store the encapsulated pointer as a mutable member variable.

Here is my implementation:

template <typename T>
class owner_ptr
{
    mutable T* p;

    T* get_ownership() const
    {
        T* tmp = p;
        p = NULL;
        return tmp;
    }

public:
    explicit owner_ptr(T* ptr = NULL) : p(ptr) {}
    owner_ptr(const owner_ptr<T>& orig) : p(orig.get_ownership()) { }

    owner_ptr& operator=(const owner_ptr<T>& rhs)
    {
        if (this != &rhs)
        {
            this->pass(rhs.get_ownership());
        }
        return *this;
    }

    void pass(T* ptr = NULL)
    {
        if (p != ptr)
        {
            delete p;
            p = ptr;
        }
    }

    T* get() const { return p; }
    T* operator->() const { return p; }
    T& operator*() const { return *p; }

    ~owner_ptr()
    {
        this->pass();
    }
};

And a specialization for arrays (almost the same):

template <typename T>
class owner_ptr<T[]>
{
    mutable T* p;

    T* get_ownership() const
    {
        T* tmp = p;
        p = NULL;
        return tmp;
    }

public:
    explicit owner_ptr(T* ptr = NULL) : p(ptr) {}
    owner_ptr(const owner_ptr<T[]>& orig) : p(orig.get_ownership()) { }

    owner_ptr& operator=(const owner_ptr<T[]>& rhs)
    {
        if (this != &rhs)
        {
            this->pass(rhs.get_ownership());
        }
        return *this;
    }

    void pass(T* ptr = NULL)
    {
        if (p != ptr)
        {
            delete[] p;
            p = ptr;
        }
    }

    T* get() const { return p; }
    T* operator->() const { return p; }
    T& operator*() const { return *p; }
    T& operator[](int i) const { return p[i]; }

    ~owner_ptr()
    {
        this->pass();
    }
};

I tested the code and it seems to be working. std::vector also accepts this template, so I can use it for creating heterogeneous containers.

My questions:

Is it a bad idea to use mutable to solve the ownership-passing
problem? Are there any scenarios where it can cause undefined behaviour?
Is there anything that I implemented incorrectly in the template?
Any affect on performance?
Before C++11, why did we have only the silly std::auto_ptr which couldn't be used with std::vector?

NOTE: I'm doing this for learning purposes. This question is totally independent from the features and smart-pointers of C++11.

OK. Lets ignore that you are screwing around with mutable.

No Strong Exception Guarantee.

void pass(T* ptr = NULL)
{
    if (p != ptr)
    {
        delete[] p;   // if p throws then your object is left in
                      // an invalid state and you have leaked the
                      // pointer `ptr`
        p = ptr;
    }
}

You should do this in an exception safe way. Which requires the use of a temporary.

void pass(T* ptr = NULL)
{
    if (p != ptr)
    {
        T* tmp = p;
        p = ptr;
        delete[] tmp;   // now it is safe to delete.
                        // even if it throws this object is consistent
                        // and you have not leaked ptr.
    }
}

Double ownership check

Both this method and the previous check for self assignment. Because this function calls the above function you perform a self assignment check twice when you use the assignment operator.

owner_ptr& operator=(const owner_ptr<T>& rhs)
{
    if (this != &rhs)  // Check here
    {
        this->pass(rhs.get_ownership());  // Check inside pass()
    }
    return *this;
}

I would change both of these methods to call a private method that does the check and work.

owner_ptr& operator=(const owner_ptr<T[]>& rhs)
{
    private_pass(rhs.get_ownership());
    return *this;
}

void pass(T* ptr = NULL)
{
    private_pass(ptr);
}
private:
void private_pass(T* ptr)
{
    if (p != ptr)
    {
        T* tmp = p;
        p = ptr;
        delete[] tmp;
    }
}

No Throwing methods

Since the get_ownership() method is guaranteed not to throw you should probably mark it as such.

T* get_ownership() throw();

Questions:

  Is it a bad idea to use mutable to solve the ownership-passing problem?

Probably. Mutable is really for designating members that are not part of the objects actual state (ie temporary caches).

  Are there any scenarios where it can cause undefined behaviour?

Don't think so. You will just loose out on certain optimizations.

  Is there anything that I implemented incorrectly in the template?

Don't see anything.

  Any affect on performance?

Yes. As noted above the compiler can not apply certain optimizations when a member is marked mutable.

  Before C++11, why did we have only the silly std::auto_ptr which couldn't be used with std::vector?

Because the language did not have the features required to implement modern smart pointers. The auto_ptr was the first attempt at a smart pointer and it worked to a certain extent it just had limitations.

It took them 8 years to improve the language enough so that smart pointers could be implemented properly.


SQL query with nested subqueries The following query is taking over 800ms to run, and returning 300 rows. When deployed to SQL Azure, it takes much longer on an affordable price tier.

SELECT
    Tests.Id,
    Tests.Title,
    Tests.AuthorId,
    Tests.[Status],
    Users.FirstName + ' ' + Users.LastName AS AuthorName,
    (SELECT
        COUNT(1)
     FROM Results LEFT JOIN Users ON Results.UserId = Users.Id
     WHERE
        Results.TestId = Tests.Id AND
        Results.MarkedBy IS NULL AND
        Results.QuestionNumber >= 1 AND
        EXISTS (
          (SELECT ClassName FROM UserClasses WHERE UserClasses.UserId = Users.Id)
          INTERSECT
          (SELECT ClassName FROM TestClasses WHERE TestClasses.TestId = Tests.Id)
          INTERSECT
          (SELECT ClassName FROM UserClasses WHERE UserId = @teacherId)
        )
    ) AS UnmarkedCount,
    (CASE WHEN EXISTS (SELECT 1 FROM Results WHERE Results.TestId = Tests.Id)
      THEN CAST(1 AS BIT)
      ELSE CAST(0 AS BIT) END
    ) AS AnyResults,
    (SELECT Stuff((SELECT ',' + ClassName FROM
      (
        (SELECT ClassName FROM TestClasses WHERE TestClasses.TestId = Tests.Id)
        INTERSECT
        (SELECT ClassName FROM UserClasses WHERE UserId = @teacherId)
      ) x FOR XML PATH ('')),1,1,'')
    ) AS Classes
FROM
    Tests INNER JOIN Users ON Tests.AuthorId = Users.Id
WHERE
    Users.SchoolId = @schoolId AND Tests.Status <= 4

An overview of the schema:

Users include students and teachers.
UserClasses matches many users to many class names.
TestClasses matches many tests to many class names.
Each test in Tests can have multiple Results - one per question per student.

The query returns a list of tests, using subqueries to find:

UnmarkedCount: How many unmarked results exist for this test, where the intersection of the following is not empty:

The classes of the student of this result
The test's classes
The teacher's classes

AnyResults: Are there any results for this test?
Classes: As a comma-separated list, which of the teacher's classes are assigned to this test?

Note that if we remove the condition where three queries are intersected, the execution time is reduced to 150ms. However, this logic is required.

How could this be improved?

Further Details:

Query Execution Plan

This is an extract from the query execution plan, where the heavy lifting seems to occur. I can't see anywhere suggesting indexes.

Business logic

The procedure returns a list of all tests at a given school. For each test, it calculates:

UnmarkedCount: How many results are not yet marked for students in classes which are both allocated to this test and taught by the current user?
Classes: Which of the classes allocated to this test does the current user teach?

Let's just focus on this part, because that's where your performance goes:

SELECT
    COUNT(1)
FROM Results LEFT JOIN Users ON Results.UserId = Users.Id
WHERE
    Results.TestId = Tests.Id AND
    Results.MarkedBy IS NULL AND
    Results.QuestionNumber >= 1 AND
    EXISTS (
      (SELECT ClassName FROM UserClasses WHERE UserClasses.UserId = Users.Id)
      INTERSECT
      (SELECT ClassName FROM TestClasses WHERE TestClasses.TestId = Tests.Id)
      INTERSECT
      (SELECT ClassName FROM UserClasses WHERE UserId = @teacherId)
    )

That pattern of EXISTS (... INTERSECT ...) is better written as a chain of INNER JOIN.

The query optimizer of your database already did that internally as well, but it chose the wrong order for the join, resulting in overly large temporary result sets. Especially when joining UserClasses straight on Results without applying the more selective filter by @teacherId first.

SELECT
    COUNT(1)
FROM Results
INNER JOIN TestClasses ON
    TestClasses.TestId = Tests.Id AND
    TestClasses.TestId = Results.TestId
INNER JOIN UserClasses AS TeacherClass ON
    TeacherClass.UserId = @teacherId AND
    TeacherClass.ClassName = TestClasses.ClassName
INNER JOIN UserClasses AS UserClass ON
    UserClass.UserId = Results.UserId AND
    UserClass.ClassName = TestClasses.ClassName
WHERE
    Results.MarkedBy IS NULL AND
    Results.QuestionNumber >= 1

I reordered the JOIN clauses to ensure that the product remains as small as possible after each single step. Further, I eliminated the unnecessary join on the User schema.

However, you don't actually need full INNER JOIN either. If your database system supports that, you can safely replace the 2nd and 3rd of the INNER JOIN with LEFT SEMI JOIN operators instead.

So much for fixing the inner select. But as a matter of fact, now we don't even need to do it as a subquery any more, but can just handle if as a LEFT JOIN with COUNT and GROUP BY on the outmost query.

Whether this actually gains any performance needs to be tested.

There are also a couple of flaws in your database scheme:

Take the UserClasses table schema. You are abusing it to describe both the roles of teacher and student for any given class, without distinguishing between these two. I suspect you coded the user role into the Users schema instead, but it would have been better to store different roles in different schemes.

You are apparently storing class names as string literals in multiple schemes, this is an indirect violation of the 2NF, but even worse, it requires string comparisons to match the corresponding columns against each other. This should be refactored ASAP.

There also appears to be a possible design flaw in Results. If the same test is reused by two different classes, and a pupil is enrolled into both, his test results are now shared between both classes. Test results should probably linked to a specific enrollment to a class, rather than just to the generic test. This also allows to simplify this query further, as the most expensive part of joining on UserClass for querying pupil enrollment is then obsolete.


Slow two-strings comparer I have 2 strings for example:

abcabc and bcabca

or

aaaabb and abaaba

I checked that second string is the same or not like first string but shifted.
bcabca = ..abca + bc...

using System;

public class TOPSES
{
    static string t1, t2;
    static char[] t1c;
    static char[] t2c;

    static void Main()
    {
        int t;
        t = int.Parse(Console.ReadLine());

        while (t > 0)
        {
            t1 = Console.ReadLine();
            t2 = Console.ReadLine();

            string result = "no";

            t1c = t1.ToCharArray();
            t2c = t2.ToCharArray();

            result = ChangeString(t1c[0], 0);

            Console.WriteLine(result);
            t--;
        }
    }

    public static string ChangeString(char letter, int startIndex)
    {
        int index = t2.IndexOf(letter, startIndex);
        if (index == -1)
            return "no";
        else
        {
            string newString = t2.Remove(0, index);
            newString += t2.Remove(index, t2.Length - index);

            if (t1 != newString)
                return ChangeString(letter, ++index);

            return "yes";
        }
    }
}

How can I improve this code to make it faster? Also, it will be nice if someone could explain what makes this 'program' slow.

This program is organized in a bizarre way.

t1, t2, t1c, and t2c are static variables, which essentially make them "global" state.  This makes your code difficult to follow.
t2c is a write-only variable — assigned but never used.
t1c is only barely used — you're only ever interested in the first character.
It's not obvious what the purpose of ChangeString() is.  What are you changing?  At first glance, it appears to transform the input (which consists of a single letter and a startIndex) into a "yes"/"no" string.

I would expect the program to follow this outline:

using System;

public class TOPSES
{
    public static void Main()
    {
        for (int t = int.Parse(Console.ReadLine()); t >= 0; t--)
        {
            string s1 = Console.ReadLine(),
                   s2 = Console.ReadLine();
            Console.WriteLine(IsRotation(s1, s2) ? "yes" : "no");
        }
    }

    public static bool IsRotation(string s1, string s2)
    {
        …
    }
}

Notes:

Main() should be public.
A for loop gathers all the code related to t together, to make it easy to see what it's for.
Avoid unnecessarily separating declarations and assignments.

The algorithm you use is also too complicated: you're looking for places in t2 that start with the initial character of t1, then checking if t2, if sliced and reassembled there, matches t1.  But why use string.IndexOf(Char, Int) when you could just do string.IndexOf(string)?

public static bool IsRotation(string s1, string s2)
{
    return s1.Length == s2.Length &&
           (s2 + s2).IndexOf(s1) >= 0;
}

This involves just one string concatenation, and no slicing and dicing.


Rails query for all questions in tournaments that a user participates in I'm new to rails and this is the situation I'm in: I have a User model that has many tournaments, a Tournament has many users and questions and a Question belongs to a tournament. I'm trying to write a query for all questions that are in tournaments the user is a part of, for example if we have the user A in tournament 1 which has questions alpha, beta, gamma and another tournament 2 with questions omega and delta, I want to display alpha, beta and gamma. So far this is what I've come up with:

def user_questions
  first_questions = scope.joins(:tournament)\
                         .merge(Tournament.where(id: user.tournaments.first.id))
  user.tournaments.each do |tournament|
    current_questions = scope.joins(:tournament)\
                             .merge(Tournament.where(id: tournament.id))
    first_questions = first_questions.or(current_questions)
  end

  first_questions
end

(Imagine scope is Question) Now this works but even I can see this code isn't that good, to put it mildly. I'm looking for suggestions on how to improve it.

Ok, so based on what your said your associations are you can do

class User
  has_many :tournaments
  has_many :questions, through: :tournaments
end

u = User.first
questions = u.questions

If you don't want that for some reason you can do

class User
  has_many :tournaments
end

class Question
  belongs_to :tournament
end

u = User.first
questions = Question.where(tournament_id: u.tournament_ids)

Rails will convert that into a where tournament_id in (?) sql statement


Python: Find pairs of numeric palindromes that sum up to another palindrome I am trying to identify and print pairs of 4 digit palindromes that sum up to a 5 digit palindrome.

This is what I have so far

def isPalindrome(x):
    return str(x)==str(x)[::-1]

palindrome = [x for x in range(1000, 10000) if isPalindrome(x)]

for x in palindrome:
    for y in palindrome:
        if (9999 < x+y < 100000) and isPalindrome(x+y):
            print(x, y, x+y)

I am estimating the time complexity for this to be O(n^2),because I am traversing the list twice. Is it possible to improve on this?

Two opportunities for optimization that suggest themselves to me:

Seems like you should be able to produce an exhaustive list of 4-digit palindromes by taking every 2-digit number and then appending its mirror to it, rather than having to iterate through every 4-digit number and throw most of them out.  That would let you build your palindrome list in about one-hundredth the time (you'll be iterating over 90 two-digit numbers instead of 9000 four-digit numbers in that first loop).
A lot of the sums you're checking will be too small (i.e. they'll be 4 digits); none will be too big (9999+9999=19998).  You can minimize the work you do on those sums by iterating from largest to smallest and breaking the inner loop once the sum gets too small.

An alternative to the nested for loops would be using one of the itertools functions to generate all the combinations as a set of tuples, but I don't think that'd get you any performance wins.


Faster way of replacing strings in large pandas dataframe with regex I want to replace all instances of a location with just the location keyword itself, eg "Foxclore Road" with "road", "Chesture Avenue" with "avenue". The file is several GBs, with many million rows. Current working code, three methods:

startTime = time.time()
mergedAllCrimes['crime_location_approx'] = mergedAllCrimes.crime_location_approx.str.replace(r'.*(?i)road$', 'road')
endTime = time.time()
print(endTime - startTime)

startTime = time.time()
mergedAllCrimes.crime_location_approx = mergedAllCrimes.crime_location_approx.apply(lambda x: 'road' if 'road' in str.lower(x) else x)
endTime = time.time()
print(endTime - startTime)

startTime = time.time()
allCrimes.loc[allCrimes['crime_location_approx'].str.contains('Road', case=False), 'crime_location_approx'] = 'road'
endTime = time.time()
print(endTime - startTime)

my times are:

14.287408590316772
1.9554557800292969
5.129802942276001

respectively

Problem is, the second two methods (while faster), replace "Broadway" with "road", hence the need for a regex to search at the end of a string.

Is there any way to make the regex conditional method much faster? If I have a large list of replacements, it could end up taking a long time.

There is not much to say about your code then, Regex is slow.

A non-regex solution could be to use Python's endswidth, this works the same as r"road$"

mergedAllCrimes.crime_location_approx = mergedAllCrimes.crime_location_approx.apply(lambda x: 'road' if x.lower().endswith('road') else x)

I'm assuming all the conditional words are at the end of the string


Finding the count of negative sub-arrays for a given array I want to improve my implementation for the following problem:

  You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that sub-array is negative. Count the number of "Negative sub-arrays" in the input array.

  Note: Subarrays are contiguous chunks of the main array. For example if the array is {1,2,3,5} then some of the subarrays are {1}, {1,2,3}, {2,3,5}, {1,2,3,5} etc. But {1,2,5} is not an subarray as it is not contiguous.

  Input Format:

  The first line consists an integer n. The next line will contain n space seperated integers. Value of n will be at most \$100\$. The numbers in the array will range between \$-10000\$ to \$10000\$.

  Output Format:

  Print the answer to the problem.

I am using two loops. It's clearing the test cases, but can I do it with only one loop?

import java.io.*;
import java.util.*;

   public class Solution {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte T = Byte.parseByte(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[T];
        for(int i = 0; i < T; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int sum = 0, count = 0;;
        for(int i = 0; i < T; i++){
             sum = 0;
             sum += arr[i];// If the number itself is negative count++
              if(sum < 0){
                    count++;
                }
            for(int j = i + 1; j < T; j++){
                sum += arr[j];
                if(sum < 0){// If the most recent sum is -ve, count++
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

Simplifications

If you look at your main loop:

    int sum = 0, count = 0;;
    for(int i = 0; i < T; i++){
         sum = 0;
         sum += arr[i];// If the number itself is negative count++
          if(sum < 0){
                count++;
            }
        for(int j = i + 1; j < T; j++){
            sum += arr[j];
            if(sum < 0){// If the most recent sum is -ve, count++
                count++;
            }
        }
    }

you can see that there are two blocks of code that do the same thing.  You can remove one block by noticing that starting the j loop at i instead of i+1 will do the initial check of the number itself.  Another thing you could do is move the int sum declaration inside the for loop.  So the final result would look like this:

    int count = 0;
    for (int i = 0; i < T; i++) {
        int sum = 0;
        for (int j = i; j < T; j++) {
            sum += arr[j];
            if (sum < 0) {// If the most recent sum is -ve, count++
                count++;
            }
        }
    }

Complexity

As far as your complexity question, I don't believe that you can solve this problem with better than an \$O(n^2)\$ solution, so your two loops seem fine.


PHP mysqli code for login form Can you check my code if I wrote like a professional?

connection page.
form sign page.
plan page.
log out page.

First I create the database and tables, then the connection file, then the form sign in page, then the plan page, finally the log out page

Database educate (create table users):

CREATE TABLE users(
id INT AUTO_INCREMENT,
username VARCHAR(50) NOT NULL,
password VARCHAR(100) NOT NULL,
PRIMARY KEY(id)
);

Conection.php:

<?php
$servername = 'localhost';
$username = 'root';
$password = '';
$db = 'educate';
//I added @ to delete error message that comming from  MySQL
$conn = @new mysqli($servername,$username,$password,$db);
if($conn->connect_error) die('Connection faild');
?>

Form signin.php:

<?php
//Check the cookie
if(!empty($_COOKIE['user'])) { header ('location: plan.php'); }
?>

<?php
//Check the inputs
function test_input($data) {
$data = trim($data);
//return a $data with whitespace stripped from the beginning and end of
$data
$data = stripslashes($data); //emoves backslashes
$data = htmlspecialchars($data);
//converts some predefined characters to  HTML entities
return $data;
}
?>

<?php
$username = $password = $password_hash = '';
$usernameErr = $passwordErr = '';

//Connection file
require ('connection.php');

if($_SERVER['REQUEST_METHOD'] == 'POST'){

if(empty($_POST['username'])){
$usernameErr = 'Username cannot be empty';
}else{
$username = test_input($_POST['username']);
}

if(empty($_POST['password'])){
$passwordErr = 'Password cannot be empty';
}else{
$password = test_input($_POST['password']);
$password_hash = md5($password);
}

//Select the data from DB('educate')
$sql = " SELECT username, password FROM users WHERE username='$username'
AND  password='$password_hash' ";

$result = $conn->query($sql);

if($result->num_rows === 0) {
$usernameErr = 'Username is error';
$password = 'Password is error';
} elseif($result->num_rows === 1) {
//Set cookie (one hour) and moved to  another    page
SETCOOKIE('user', $username, time() + (60*60) );
header('location: plan.php');
}

}
?>

<form action="#" method="post">
Username: <input type="text" name="username" placeholder="username">
<?php echo $usernameErr; ?>

Password: <input type="password" name="password" placeholder="password">
<?php echo $passwordErr; ?>

<input type="submit" value="Login">
</form>

Logout.php:

<?php
setcookie('user',"", time() - (30*30) );
header('location: form signin.php');
?>

Did you know that anyone can set a cookie whenever they like? Imagine someone will set the "user" cookie to "admin".

Use any of popular PHP frameworks instead. They're here for a reason.

I'd also advise to use prepared statement if you absolutely have to write this kind of code yourself.

$query = "SELECT username, password FROM users WHERE username=? AND password=?";
if ($pst = $conn->prepare($query)) {
  $pst->bind_param("ss", $username, $password_hash);
  $pst->execute();
  if ($pst->num_rows) {
    // logged in
  }
}


Concatenating two substrings to provide the largest possible palindromic string The code extracts two substrings from different strings and concatinating them to provide the largest possible palindromic string.

Objective:

  You have two strings, (a) and (b). Find a string, (c), such that:
  (c)=(d)+(e).

  (d),(e) can be expressed as  where (d) is a non-empty substring of (a)
  and (e) is a non-empty substring of (b). (c) is a palindromic string.
  The length of is as long as possible. For each of the pairs of strings
  (a) and (b) received as input, find and print string  on a new line.
  If you're able to form more than one valid string , print whichever
  one comes first alphabetically. If there is no valid answer, print -1
  instead.

How can I improve the performance of this code, reducing the compile time and keeping the functionality the same?

import java.io.*;
import java.util.*;

public class Solution {
    boolean isPalindrome(String s) {
  int n = s.length();
  for (int i=0;i<(n / 2);++i) {
     if (s.charAt(i) != s.charAt(n - i - 1)) {
         return false;
     }
  }

  return true;
}

    public static void main(String[] args) {

        String result="";
         Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int a=0; a<n; a++)
            {int length1, length2, i,c,d,j;
        int max_length=0;
        String string1 = in.next();
        String sub1,sub2;
        String string2 = in.next();
        length2=string2.length();
        length1 = string1.length();

      for( c = 0 ; c <length1 ; c++ )
      {
         for( i = length1-c ; i >0 ; i-- )
         {
            sub1 = string1.substring(c, c+i);
            for( d = 0 ; d < length2 ; d++ )
      {
         for( j = length2-d ; j >0 ; j-- )
         {
            sub2 = string2.substring(d, d+j);
            String temp=sub1+sub2;
              Solution obj= new Solution();
             if(temp.length()>=max_length && obj.isPalindrome(temp)==true)

                 {
                 if (max_length==temp.length())
                  {   if(temp.compareTo(result)<0)
                     {
                     result=temp;
                  }}
                 else {
                     max_length=temp.length();
                 result=temp;
                  }
             }
         }
      }
         }
      }
             if(max_length==0)
                 System.out.println(-1);
             else
                 {
       System.out.println(result);
             result="";
             }
        }    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    }
}

Minor tweak

    boolean isPalindrome(String s) {
  int n = s.length();
  for (int i=0;i<(n / 2);++i) {
     if (s.charAt(i) != s.charAt(n - i - 1)) {
         return false;
     }
  }

Your indentation is all over the map.  Copy/paste error?

More importantly, you can save some math by writing this

    public static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }

        return true;
    }

Perhaps a good compiler would optimize them out, but your original was doing four math operations per iteration where this only does two (and an extra at declaration).  Not counting the comparisons for either.

Small tweak

I'd rewrite main as

        try (Scanner in = new Scanner(System.in))
        {
            for (int n = in.nextInt(); n > 0; n--)
            {
                String string1 = in.next();
                String string2 = in.next();

                String palindrome = findLongestPalindrome(string1, string2);
                if (palindrome.isEmpty())
                {
                    System.out.println(-1);
                }
                else
                {
                    System.out.println(palindrome);
                }
            }
        }

Putting the algorithm in a separate method makes it easier to test and cleans up main by a lot.

We don't need a separate loop variable for the test cases here.  If we decrement instead of increment, we can simplify that logic.

Putting the Scanner in a try-with-resources eliminates a compiler warning about never closing the Scanner.

Major tweaks

      for( c = 0 ; c <length1 ; c++ )
      {
         for( i = length1-c ; i >0 ; i-- )
         {
            sub1 = string1.substring(c, c+i);
            for( d = 0 ; d < length2 ; d++ )
      {
         for( j = length2-d ; j >0 ; j-- )
         {
            sub2 = string2.substring(d, d+j);
            String temp=sub1+sub2;
              Solution obj= new Solution();
             if(temp.length()>=max_length && obj.isPalindrome(temp)==true)

                 {
                 if (max_length==temp.length())
                  {   if(temp.compareTo(result)<0)
                     {
                     result=temp;
                  }}
                 else {
                     max_length=temp.length();
                 result=temp;
                  }
             }
         }
      }
         }
      }

I changed to

    public static String findLongestPalindrome(String a, String b) {
        String result = "";
        for (int aStart = 0 ; aStart < a.length() ; aStart++ )
        {
            char firstLetter = a.charAt(aStart);
            for (int bEnd = b.lastIndexOf(firstLetter); bEnd >= 0 ; bEnd = b.lastIndexOf(firstLetter, bEnd - 1) )
            {
                for (int aEnd = a.length() ; aEnd > aStart ; aEnd-- )
                {
                    String aSubstr = a.substring(aStart, aEnd);
                    int requiredLength = Math.max(result.length() - aSubstr.length(), 0);
                    for (int bStart = 0 ; bStart <= bEnd - requiredLength; bStart++ )
                    {
                        String candidate = aSubstr + b.substring(bStart, bEnd + 1);

                        if (candidate.length() >= result.length() && isPalindrome(candidate))
                        {
                            if (candidate.length() == result.length() && candidate.compareTo(result) >= 0)
                            {
                                continue;
                            }

                            result = candidate;
                        }
                    }
                }
            }
        }

        return result;
    }

Changed arbitrary parameter names to match the problem statement.

Changed loop index variables to match their meaning relative to the parameters.

Using lastIndexOf to find the endpoint of the second string means that we can skip a lot of substrings that will never work.  The original code had to take the substrings, join them, and then check if the result is a palindrome on all substrings.  This reduces down to only possible substrings.

Determining the requiredLength allows us to skip joining and checking substrings that are too short to work.

I declared variables just in time to be initialized.  This makes it easier to see what's happening.

An alternative algorithm

The obvious brute force solution is to check every possible start and end points for both strings.  You optimized this by starting with the longest possible substrings, and I added tweaks to optimize that more.  But I actually think that was the wrong way to go.  Note that you still have to iterate over every letter to check if it is a palindrome.  You can save checking some of the substrings if you integrate the palindrome check with taking the substrings.  Instead of four nested loops with a linear time check in the middle, we can use just three nested loops.  Iterate up to the correct solution rather than check down to it.


Several approaches to a logging class I'm making a personal logger and so far I have come up with 3 solutions.
I have them simplified in this example to highlight my dilemma. I want to know the pros and cons of my approaches and ways to make them better. Also should I be flushing the stream as often as possible and why?

TempLog

This version will be created and destroyed on every log. Endline forced on destruction.

class TempLog
{
public:
    std::ostream& log()
    {
        return std::cout;
    }
    ~TempLog()
    {
        std::cout << "\n";
    }
};

SingletonLog_ver_1

If the endline is forced in this manner using the same ostream from outside the logger will result in bad output. Also it feels somewhat dishonest but due to my lack of experience I don't trust my feeling.

class SingletonLog_ver_1
{
public:
    static SingletonLog_ver_1 instance()
    {
        static SingletonLog_ver_1 instance;
        return instance;
    }

    std::ostream& log()
    {
        static bool firstLine = true;
        if (firstLine)
            firstLine = false;
        else
            std::cout << "\n";

        return std::cout;
    }

private:
    SingletonLog_ver_1() {};
};

SingletonLog_ver_2

Now while I like what is happening here more than the previous two examples it seems like the least elegant code. Is there another more elegant way to achieve this kind of functionality?

class SingletonLog_ver_2
{
public:
    static SingletonLog_ver_2 instance()
    {
        static SingletonLog_ver_2 instance;
        return instance;
    }

    std::pair<std::ostream&, std::unique_ptr<TempObj_NewLine>> log()
    {
        return std::pair<std::ostream&, std::unique_ptr<TempObj_NewLine>>(std::cout, std::make_unique<TempObj_NewLine>());
    }

private:
    SingletonLog_ver_2() {};
};

TempObj_NewLine

class TempObj_NewLine
{
public:
    TempObj_NewLine() {};
    ~TempObj_NewLine()
    {
        std::cout << "\n";
    }
};

Use of the 3 loggers:

int main()
{
    TempLog().log() << "first log!" << " first log, same line.";
    TempLog().log() << "second log." << "second line.";

    SingletonLog_ver_2::instance().log().first << "first line singleton log!"<< " first line, again.";
    SingletonLog_ver_2::instance().log().first << "second line singleton log!";

    SingletonLog_ver_1::instance().log() << "first line singleton - hacky endline." << " first line, again.";
    SingletonLog_ver_1::instance().log() << "second line singleton - hacky endline";

    std::cin.get();
}

Singletons

There are several ways to make something a singleton. You are doing it by removing the public constructor, and forcing users to get an instance through a static member function. That works, but there are alternatives. You can create a regular class, and provide a global instance of that class. Just like so:

class Log {
    ...
};

Log logInstance;

You then just refer to logInstance instead of SingletonLog::instance().

Proper naming

Your class has a function log(), however that function does not log anything. Instead, it just returns a std::ostream reference. A more appropriate name for the function would then be get_stream().

If you intend to always use it as SingletonLog::instance().log() << "some string", then it might be better to just add an operator <<() overload to your logging class. This has several advantages:

It's less typing: SingletonLog::instance() << "some string", or when using the alternative way of making a singleton: logInstance << "some string".
You can actually read the contents of the string in your class, and check whether it ends with a newline or not.

Flushing

Whether or not to flush depends on what you want to log. If you log a lot of information, flushing adds considerable overhead. However, if you want to be sure that any errors that are logged are not lost when your program terminates abnormally, then it might be prudent to flush the output stream after every write to the log.

Other suggestions

Do you really want to use the << operator? If you rather like to use the printf() style, then consider making use of fmtlib, which provides a type-safe way to format strings the printf() or Python .format() way. Your logging class could look like:

#include <fmt/format.h>

class Log {
    template <typename... Args>
    void log(const std::string &format, const Args &... args) {
        std::cout << fmt::format(format, args...);
    }
};

Log logInstance;

And use it like:

logInstance.log("First line: {}\nSecond line: {}\n", "first entry", "second entry");


Multidimentional array initialization I am initializing a PHP array as follows

$newArray = array();
$newArray['2014-13-03']['SMD']['IMPR'] = 5;
$newArray['2014-13-03']['SMD']['CLICK'] = 10;

I just wanted to check if you think this is a wrong way to insert data into an array. It is working just fine, but I still wanted to check from an optimization standpoint.

I would do the definition inline with the declaration:

$newArray = array(
    '2014-13-03' => array(
        'SMD' => array(
            'IMPR' => 10,
            'CLICK' => 10
        )
    )
);

If you wanted to lean towards the more compact side, you could achieve almost the same clarity with something like:

$newArray = array('2014-13-03' => array('SMD' => array(
    'IMPR' => 10,
    'CLICK' => 10
)));

In addition to a bit more clarity (at least in my opinion), this has the advantage of it being more difficult to accidentally mess up the data. Since the parents keys aren't repeated, the keys are either right for both leaves or wrong for both leaves. That should help prevent a rather odd potential bug.

By the way, that's a rather odd data structure unless this is just an example. Three levels deep for such a sparse data set is kind of excessive.

From an optimization standpoint, it's not going to matter how you do it. You're in the realm of microseconds at most. Really it's just the parser that's going to differ on it anyway since I would imagine the parser will change any reasonable incantation of this to the same instructions (I have not confirmed that though).

By the way, $newArray is a terrible variable name in anything but example code. If your real code is using that, change it to a descriptive name.


calculate tree height (arbitrary tree) - python Given an array as input, we have to calculate the tree height. For example, input [4, -1, 4, 1, 1] means that there are 5 nodes with numbers from 0 to 4, node 0 is a child of node 4, node 1
is the root, node 2 is a child of node 4, node 3 is a child of node 1 and node 4 is a child of node 1.
I have a very low performing code that loops over the input more than once:
def height(array):
        di= {array.index(-1):-1}
        while (len(di)<len(array)):
                for i, p in enumerate(array):
                        if p in di.keys():
                                di[i] = di[p] - 1
        max_distance = -1
        for val in di.values():
                if val < max_distance:
                        max_distance = val
        max_distance = abs(max_distance)
        return max_distance

Another method I'm trying is I group the child nodes together like this:
input [9, 7, 5, 5, 2, 9, 9, 9, 2, -1] I group then to {9: [0, 5, 6, 7], 7: [1], 5: [2, 3], 2: [4, 8], -1: [9]} But I'm stuck and have no idea if I'm on the right track or what to do after this. Please let me know what you think. Much appreciated!

Standard indentation is four spaces.
Missing spaces here and there.
Unnecessary parentheses after while.
Can't handle empty trees.
Name di is really unclear, i and p could also be better.
Using .keys() like that is pointless.
Using negative values is pointless and confusing. Using abs on the result is particularly confusing, as it suggests that the value you give it could be negative or positive. Since you know it's negative, that should've been just -max_distance.
No need to reinvent max.

Rewritten accordingly:
def height(array):
    depth = {-1: 0}
    while len(depth) <= len(array):
        for child, parent in enumerate(array):
            if parent in depth:
                depth[child] = depth[parent] + 1
    return max(depth.values())

For performance, instead of repeatedly searching for children with finished parents, first do one pass to collect each parent's children. Then when you finish a parent, simply go through its previously collected children to finish them, too. This is then linear instead of quadratic time.
Or if the limits are small enough (so far you still haven't answered the comment asking about that), you could use a simple recursive depth(node) function decorated with functools.cache, apply it to all nodes, and take the max. Also linear time.


Filling in gym membership prices by joining PANDAS dataframes I have two dataframes, df which contains a list of members in addition to the type of contract that they purchased on a given date, df is about 10 000 entries. I have another df_prices which contains the average price of a given contract for a given year and month.

df resembles:

    Member Nbr      Date-Joined         Contract Type
1           1        2010-03-31     1 Year Membership
2           1        2011-04-16     1 Year Membership
3           1        2012-08-06     1 Year Membership
4           1        2013-08-21     1 Year Membership
5           1        2014-08-31     1 Year Membership
6           2        2015-09-03     1 Year Membership
7           2        2012-12-10     4 Month Membership
8           2        2013-03-13     1 Year Membership
9           3        2014-03-15     1 Year Membership
10          3        2010-02-09     1 Year Membership
...
10095    7374        2016-02-29     1 Month Membership
10096    7375        2016-03-01     1 Year Membership
10097    7376        2016-03-01     1 Month Membership
10098    7378        2016-03-04     1 Month Membership
10099    7379        2016-03-06     1 Month Membership
10100    7380        2016-03-05     1 Year Membership
10101    7387        2016-03-10     3 Month Membership

and df_prices

          Date                   Description      Amount
0   2010-01-31            1 Month Membership   54.036316
1   2010-01-31             1 Year Membership  325.000000
2   2010-01-31            4 Month Membership  147.642353
3   2010-01-31            7 Month Membership  227.890000
5   2010-02-28            1 Month Membership   55.283846
6   2010-02-28             1 Year Membership  333.250000
7   2010-02-28            4 Month Membership  146.257358
8   2010-02-28            6 Month Membership  165.000000
9   2010-02-28            7 Month Membership  223.905714
10  2010-02-28                     Pool Only  250.000000
...
462 2015-12-31            4 Month Membership  146.390000
463 2015-12-31            6 Month Membership  204.815000
464 2016-01-31            1 Month Membership   45.037143
465 2016-01-31             1 Year Membership  265.000000
466 2016-01-31            3 Month Membership  112.927273
467 2016-01-31            4 Month Membership  147.413333
468 2016-01-31            6 Month Membership  204.093333
469 2016-02-29            1 Month Membership   45.699444
470 2016-02-29             1 Year Membership  265.000000
471 2016-02-29            3 Month Membership  110.285556
472 2016-02-29            4 Month Membership  139.477500
473 2016-02-29            6 Month Membership  202.650000

I have written some code in python that fills a list based on a customers join date and contract type and adds it to df, which is exactly what I want. The problem that I'm facing is that is is extremely slow to finish, and was hoping for some help to optimize it, especially as I plan on using a this on a larger dataset.

Here is what I have:

#### Standard Libraries ####
import time

#### Third-party libraries ####
import pandas as pd
import numpy as np

def Main():
    start = time.time()
    location = '/home/lukasz/Documents/Xtreme Fitness/Members/AllMembers.xlsx'
    location2 = '/home/lukasz/Documents/Xtreme Fitness/' + \
                'AverageContractPrice.xlsx'

    df = pd.read_excel(location)
    df_prices = pd.read_excel(location2)
    df_prices.fillna(method='ffill',inplace=True)

    prices = []

    for i in range(len(df)):
        df_date = df.loc[i, 'Date-Joined'].year * 1000 + \
                  df.loc[i, 'Date-Joined'].month
        df_contract = df.loc[i, 'Member Type']

        for j in range(len(df_prices)):
            if (df_prices.loc[j, 'Date'].year * 1000 + \
                df_prices.loc[j, 'Date'].month == df_date and
                df_prices.loc[j, 'Description'] == df_contract):

                # print("%s, %s" % (i, df_prices.loc[j, 'Amount']))
                prices.append(df_prices.loc[j, 'Amount'])

    prices
    df.to_excel(location, index=False)
    end = time.time()
    print(end-start)

if __name__ == '__main__':
    Main()

Consider a left side merge to match member data with corresponding prices by contract type and date. No for loops or external list needed for this approach:

df = pd.read_excel(location)
df_prices = pd.read_excel(location2)
df_prices.fillna(method='ffill',inplace=True)

finaldf = pd.merge(df, df_prices, left_on=['Date-Joined','Contract Type'],
                   right_on=['Date','Description'],
                   how='left')[['Member Nbr','Date-Joined','Contract Type','Amount']]

finaldf.to_excel(location, index=False)


Bash script to download sequentially numbered images This is a pretty basic bash script (3.2 on Mac). I am downloading 584 images from a site in order to create an album.

#!/bin/bash

urlFirst="http://150.216.68.252:8080/adore-djatoka/resolver?url_ver=Z39.88-2004&rft_id=http://150.216.68.252/ncgre000/00000012/00011462/00011462_ac_0"
urlSecond=".jp2&svc_id=info:lanl-repo/svc/getRegion&svc_val_fmt=info:ofi/fmt:kev:mtx:jpeg2000&svc.format=image/jpeg&svc.level=6"

for i in {1..584}
do
    printf -v j "%03d" $i

    url=$urlFirst$j$urlSecond

    wget $url -O $j".jpeg"

done

What improvements should be made to this?

I understand that I could remove the variables in most cases but for debug purposes it was helpful to have them, as I could add basic echo statements.

I'm not very well versed in Bash scripting though (lots of basic scripts) - any improvements or best practices from Bash I'm missing would be appreciated.

I would write it this way:

#!/bin/bash

url_template="http://150.216.68.252:8080/adore-djatoka/resolver?url_ver=Z39.88-2004&svc_id=info:lanl-repo/svc/getRegion&svc_val_fmt=info:ofi/fmt:kev:mtx:jpeg2000&svc.format=image/jpeg&svc.level=6&rft_id=http://150.216.68.252/ncgre000/00000012/00011462/00011462_ac_%04d.jp2"

for i in {1..584}; do
    wget -O $(printf '%03d.jpeg' $i) "$(printf "$url_template" $i)"
done

Specifically,

At first glance, I thought that $urlFirst and $urlSecond were two URLs, until I figured out what was happening.
If there is another leading 0, then %04d is more appropriate than %03d.
The web server isn't going to care about the order of the parameters in the query string.  For the benefit of humans, though, it would be nicer to put the parameter that changes either first or last.
Fewer variables is nice.  I do everything by interpolation.  You can get a feel for what the wget command does, without tracing which variable came from where.


Cross-domain with requirejs text plugin there is my implementation for cross domain call using the requireJs text plug-in

htaccess file in the template folder of my cross-domain site

Header set Access-Control-Allow-Origin "*"

textremote.js

define(['text','module'],function (text, module) {

    // Load the cross-domain url from the config
    var remoteUrl         = module.config().remoteUrl;

    // Store the current parseName function into a var
    var originalParseName = text.parseName;

    // Redefine the parseName function
    text.parseName = function(name) {

        // Use the original parseName
        var parsed = originalParseName(name);

        // append the cross-domain url to parsed.moduleName
        parsed.moduleName = remoteUrl+parsed.moduleName;

        return parsed;
    }

    // Force CORS to be true
    text.useXhr = function () {
        return true;
    }
});

In the main config (I remove the non related config)

require.config(
    {
        textremote  : "libs/textremote",

        // this config will be accessible in textremote.js through the module parameters
        config : {
        "textremote" : {
            remoteUrl : "http://www.cross-domain-asset.com/template/"
        }
    },
    }
)

initialization

This ensure that textremote is load first and will ovveride the text.parseUrl and text.useXhr before any usage.

require(['textremote'],function(){
    require(['libs/app'], function(app){
        app.initialize();
    });
})

Usage example

text!demo.tpl will pass through textremote and text plugin and use
http://www.cross-domain-asset.com/template/demo.tpl

// Filename: app.js
define([
  'router', // Request router.js
  'backbone',
  'marionette',
  'underscore',
  'text!demo.tpl'
], function(Router,backbone,marionette,_, demoTemplate){
  var initialize = function(){
    // Pass in our Router module and call it's initialize function
    Router.initialize();

   /* ... */

  }

  return {
    initialize: initialize
  };
});

That it, So far this is working well for me. But I would like to improve it or know if better approach exists.

On a side note, I will add code to allow multiple cross-domain usage and caching.

We've had bad experiences in our company for RequireJS. IMO, it has been marketed somewhat wrongly.

RequireJS becoming a script loader - somewhat wrong

True, it does the duties of a script loader. For small apps, this is fine. But when your application begins to grow, as in our case, It's another story. You'll easily end up with a lot of HTTP requests which will choke the static server to the point that you will get script timeout errors. There'll be unnecessary delay in your app due to all the loading and waiting.

RequireJS as a build-tool - better

So what we did was just settle for RequireJS being a build tool. For a dev setup, we allowed it to run as script-loader, a lot of module requests hitting the server. But when it came to deployment, we optimize using the r.js optimizer. This meant grabbing all the needed modules into one machine, let the r.js optimizer run, and end up with one file which you'll use on your page. In addition, we'll be using Almond instead of RequireJS as we don't need the full functionality of RequireJS after it is compiled.

Conclusion

Small scale, it's fine. Large scale, I'd think of something better.


Game where you guess whether an article is from theOnion or notTheOnion How can I make my code better?

function generateRandNum(min, max) {
    minimum = Math.ceil(min);
    maximum = Math.floor(max);
    return Math.floor(Math.random() * (maximum - minimum)) + minimum;
}

function generateNewPost(json_data) {
    var rand_num = generateRandNum(0, json_data.length);
    console.log("generateNew length: ", json_data.length);
    var rand_post = json_data[rand_num];
    return rand_post;
}

var post_title = document.getElementById("post-title");
var onion_button = document.getElementById("onion-chosen");
var not_onion_button = document.getElementById("not-onion-chosen");
var score_display = document.getElementById("score");

var req = new XMLHttpRequest();
var json_url = "https://api.myjson.com/bins/s474n";
var score = 0;

req.open('GET', json_url);
req.onload = function() {

    if (req.status === 200) {
        var json_data = JSON.parse(req.responseText);
        var rand_post = generateNewPost(json_data);

        post_title.innerHTML = rand_post.content;
        score_display.innerHTML = score;

        onion_button.onclick = function() {
            if (rand_post.sub === "theonion") {
                score++;
                score_display.innerHTML = score;
            } else {
                score--;
                score_display.innerHTML = score;
            }

            // update title
            rand_post = generateNewPost(json_data);
            var index = json_data.indexOf(rand_post);

            console.log("Index: ", index);
            console.log("Length of json_data: ", json_data.length);
            json_data.splice(index, 1);
            console.log("Length of json_data after splice: ", json_data.length);

            post_title.innerHTML = rand_post.content;

        }

        not_onion_button.onclick = function() {
            if (rand_post.sub === "nottheonion") {
                score++;
                score_display.innerHTML = score;
            } else {
                score--;
                score_display.innerHTML = score;
            }

            // update title
            rand_post = generateNewPost(json_data);
            var index = json_data.indexOf(rand_post);

            console.log("Index: ", index);
            console.log("Length of json_data: ", json_data.length);
            json_data.splice(index, 1);
            console.log("Length of json_data after splice: ", json_data.length);

            post_title.innerHTML = rand_post.content;
        }

    } else {
        console.log("Error");
    }
};

req.send();

Avoid repetitive code

Dair has covered this already above. Basically, whenever code looks like it's been copy-pasted, it needs to be rewritten.

Another case of unnecessary repetition is the lines:

    post_title.innerHTML = rand_post.content;
    score_display.innerHTML = score;

You use these to display the first post and the starting score. These two lines are also present in your onclick methods. This means if you or someone else needed to change how these elements are displayed, for example, they would have to repeat making the same changes to your code but in multiple places. Well-written code never forces anyone to do this. Essentially, each task accomplished by your code should be written down once, and only once!

Use your data when you have it

Your generateNewPost function accesses json_data using a random number as the index:

var rand_post = json_data[rand_num];

But after calling generateNewPost, you search json_data  again for the index that 'generateNewPost' has already used:

var index = json_data.indexOf(rand_post);

As a result, your code does an unnecessary search of json_data every time the user clicks an answer. To save doing this search, generateNewPost should return the index as part (or all) of its output:

function generateNewPost(json_data) {
    var rand_num = generateRandNum(0, json_data.length);
    var rand_post = json_data[rand_num];
    return [rand_post, rand_num];
}

Which would be accessed like this:

var new_post = generateNewPost(json_data)
var rand_post = new_post[0]
var index = new_post[1]

This is not necessary here as shown below. But it might be helpful to remember it when creating more complex functions.

Keep things abstract until you need them

The two actions you want for json_data, that is, reading a random entry, and deleting an entry, both need only an index. So it makes sense to keep an integer index as your rand_post, rather than passing around the post content as a string. Further, as generating random numbers and accessing entries in a JSON object are fairly standard methods, they do not need to be wrapped in a function.

tl;dr

Your code can be simplified by:

Using a single function to initialize the display and handle both onclick events.
Trusting future readers of you code to understand a one-line version of your generateNewPost function, which is fairly standard.

As below:

var post_title = document.getElementById("post-title");
var onion_button = document.getElementById("onion-chosen");
var not_onion_button = document.getElementById("not-onion-chosen");
var score_display = document.getElementById("score");

var req = new XMLHttpRequest();
var json_url = "https://api.myjson.com/bins/s474n";
var score = 0;
var index = -1;
var options = ["nottheonion", "theonion"]

req.open('GET', json_url);
body.onload = function() {
    var json_data = JSON.parse(req.responseText);
    onion_button.onclick = update(1);
    not_onion_button.onclick = update(0);
    update(null);
}

update = function(user_entry) {
    if (user_entry != null) {
        if (options[user_entry] == json_data[index].sub) {
            score++;
        } else {
            score--;
        }
        json_data.splice(index, 1);
    }
    index = parseInt((Math.random() * (json_data.length - 1), 10)
    post_title.innerHTML = json_data[index].content;
    score_display.innerHTML = score;
}

Note:
It can also help anyone who needs to modify or work with your code to include a comment block showing the expected format of any objects passed from elsewhere, eg. from your url api.myjson.com. It might look like this:

/*
[
  { content: #string#, sub: "notheonion" / "theonion" }, ...
]
*/


How to chain exceptions? I have some function like:

void foo() { ... }

int main() {
  ...
  try {
    ...
    foo();
    ...
  } catch (const std::exception &e) {
    std::cout << "Fatal error: e.what() << std::endl();
    return;
  }
  ...
}

If an exception is thrown from foo, I'd like to know it. Also I want to know the reason of the original exception. I can split the code like this:

int main() {
  ...
  try {
    ...
  } catch (const std::exception &e) {
    std::cout << "Fatal error: " << e.what() << std::endl;
    return;
  }

  try {
    foo();
  } catch (const std::exception &e) {
    std::cout << "Fatal error (foo): " << e.what() << std::endl;
    return;
  }

  try {
    ...
  } catch (const std::exception &e) {
    std::cout << "Fatal error: " << e.what() << std::endl;
    return;
  }
  ...
}

It doesn't look good. Instead, I can update foo:

void foo()
{
  try {
    ..
  } catch (const std::exception &) {
    std::cout << "Foo failed. The reason is:" << std::endl;
    throw;
  }
}

However, I do not like solution, too (maybe, because error logging is split).  What is the right way to raise the exception upward?

You can re-throw an exception:

int main() {
    ...
    try {
        ...
        try
        {
            foo();
        }
        catch(std::exception const& e) {
            std::cout << "Fatal error: " << e.what() << std::endl;

            throw; // re-throw the exception.
                   // or you could throw a different exception.
        }
        ...
    } catch (const std::exception &e) {
        std::cout << "Fatal error: " << e.what() << std::endl;
        return;
    }
    ...
}


Calling PHP file using Ajax I like to know if there will be any performance issue if an xmlhttp object is created every time.  For example, in the below code:

function currentTime(){
    var obj = null;

    if(window.XMLHttpRequest){
        obj = new XMLHttpRequest();
    } else {
        obj = new ActiveXObject("Microsoft.XMLHTTP");
    }

    obj.open("GET", "current_time.php", true);
    obj.send(null);
    obj.onreadystatechange = function(){

        if(obj.readyState == 4 && obj.status == 200){
            var element = document.getElementById("current_time");
            element.innerHTML = obj.responseText;
        }
    };
}

setInterval("currentTime();", 1000);

or

var obj = null;
function createObj(){
    if(window.XMLHttpRequest){
        obj = new XMLHttpRequest();
    } else {
        obj = new ActiveXObject("Microsoft.XMLHTTP");
     }
}

function currentTime(){
     obj.open("GET", "current_time.php", true);
     obj.send(null);
     obj.onreadystatechange = function(){

        if(obj.readyState == 4 && obj.status == 200){
            var element = document.getElementById("current_time");
            element.innerHTML = obj.responseText;
        }
    };
}

createObj();
setInterval("currentTime();", 1000);

In the first example, the XMLHttpRequest object is created every time (1 sec).

In the second example, the object is created once.

But the second version has problems also because the obj variable is in the global namespace. It might be a good idea to abstract this into a function which contains a reference to the XMLHttpRequest object, and avoids polluting globals as in the first example.

var CurrentTime = function() {
    this.requestObj = (window.XMLHttpRequest) ? new XMLHttpRequest() : new ActiveXObject("Microsoft.XMLHTTP");
    this.element = document.getElementById("current_time");
};

CurrentTime.prototype.get = function() {
    var self = this;
    this.requestObj.open("GET", "current_time.php", true);
    this.requestObj.send(null);
    this.requestObj.onreadystatechange = function() {
        if (self.requestObj.readyState == 4 && self.requestObj.status == 200) {
            self.element.innerHTML = self.requestObj.responseText;
        }
    };
};

var currentTime = new CurrentTime();
setInterval(currentTime.get.apply(currentTime), 1000);

You could also pass the location of the PHP file to this CurrentTime function for further abstraction, however I think this is good as is. The apply method is used to set the context of the method to the currentTime variable and not the window, so that you don't get TypeErrors. :)


Converting a string to two strings I have the following code that converts a string that looks like:

  aaa-bbb|ccc-ddd|eee-fff

to two strings that look like:

  aaa|ccc|eeeandbbb|ddd|fff

The code works fine, but I am wondering if I probably missed some string/array functions that can makes the job in fewer operations / or with faster runtime.

var id = "HEL-CAS|MAD-STO|XXX-YYY"
var splittedId = id.split('|');
var from = "",
  to = "";
$(splittedId).each(function(a, b) {
  from = from + b.split("-")[0] + "|";
  to = to + b.split("-")[1] + "|";
});
from = from.substring(0, from.length - 1);
to = to.substring(0, to.length - 1);

You can use some ES6 functions and have something like:

var s = 'HEL-CAS|MAD-STO|XXX-YYY';
var s1 = [];
var s2 = []

for (var v of s.split('|').map(str => str.split('-'))) {
  s1.push(v[0])
  s2.push(v[1])
}

s1.join('|')
s2.join('|')


Thread-safe singleton class using std::shared_ptr in C++(11) What I am trying to accomplish is to create an efficient thread-safe singleton base class (as stated in the title).

So this is my singleton class, which is used via inheritance (see below).

#pragma once
#ifndef SINGLETON_HEADER_INCLUDED
#define SINGLETON_HEADER_INCLUDED
#include <memory>

template <class T>
class singleton
{
public:
        static T *get_instance(void)
        {
                if(instance.get() == 0 || instance == (NULL && 0) || !instance) {
                        instance = std::shared_ptr<T>(new T());
                }
                return instance;
        }

        static delete_instance(void)
        {
                delete instance;
                instance = (NULL && 0);
                return;
        }

protected:
        singleton(void);
        virtual ~singleton(void);

private:
        singleton(const singleton&);
        singleton& operator = (const singleton&);

        static volatile std::shared_ptr<T> instance;
};

template <class T> template *singleton<T>::instance = 0;

#endif

Here is the class in use:

#include "singleton.hpp"

class opengl_renderer : public singleton<opengl_renderer>
{
        friend class singleton<opengl_renderer>;
        etc...
};

So basically, I am looking for some tips and reviews on my class -> I feel as if it isn't working the way I imagine it should. But it is functional at its current state.

Your code doesn’t compile, and if it would compile, it would crash.

You are trying to assign a shared_ptr to a raw pointer. You are also trying to delete a shared_ptr and this leads me to believe that you don’t understand what a smart pointer actually does.

In fact, your code contains a multitude of errors. More on that below.

First, about the use of shared_ptr. In fact, a shared pointer denotes shared ownership, and this is patently not the case here: the singleton is the owner, nobody else.

A shared pointer is inappropriate here, what you want is a unique_ptr.

Then, don’t expose a pointer to the user, expose a reference via get_instance (i.e. habe get_instance() return T&. And I would rename get_instance to plain instance (which is more C++-y), and rename the private field to something else.

Finally, reconsider your usage of a singleton in the first place. The singleton is generally considered an anti-pattern and real, legitimate uses are so rare that it doesn’t pay to have a singleton base class.

Detailed code critique

if(instance.get() == 0 || instance == (NULL && 0) || !instance) {

This is doing the same check three times. Why? Once is enough – the latter is the correct usage.

But this code isn‘t thread-safe anyway, in fact, it’s not making any effort to be thread-safe at all.

return instance;

As already said, you cannot cast a shared_ptr to a plain pointer.

static delete_instance(void)

That doesn’t compile, it’s missing a return value. Also, who is going to call this method? It should never be called probably, so just delete it.

delete instance;

As mentioned above, this doesn’t work, and is meaningless. The whole point of a smart pointer is that you don’t need manual deletion.

instance = (NULL && 0);

This code makes no sense. What is it supposed to do?

virtual ~singleton(void);

You have declared the destructor but you haven’t defined it. The implementation will be empty but you still need to define it.

static volatile std::shared_ptr<T> instance;

volatile probably isn’t meaningful here. In particular, its meaning is unrelated to cross-thread access (unfortunately). But even if it was related to cross-thread access, this wouldn’t make your code thread-safe, it would simply mean that threads would read the most up-to-date version of the variable.

friend class singleton<opengl_renderer>;

What do you need this line for?


What's the fastest way to get the points I want out of a huge blob? In MATLAB I have a set of 5393280 points in the form of a decimal-valued vector (x,y,z). How do I represent them in a way that I can quickly collect all the points within some rectangular x-y domain?

Right now I'm representing them as a 3-column matrix, sorted by x-values, and using the following code to extract a rectangular region:

mtx_region = mtx_pointList( dxLowerBound < mtx_pointList(:,1) & ...
                            dxUpperBound > mtx_pointList(:,1) & ...
                            dyLowerBound < mtx_pointList(:,2) & ...
                            dyUpperBound > mtx_pointList(:,2), : );

However, I suspect that this is slowing my code down considerably.

What is a better way?

Prefiltering all relevant x-values with a binary search could speed up the process.

[a,A]=myFind2(mtx_region(:,1),dxLowerBound,dxUpperBound);

xpoints=mtx_region(a:A,:);
mtx_region = xpoints(     dyLowerBound < xpoints(:,2) & ...
                            dyUpperBound > xpoints(:,2), : );

Binary search on sorted arrays is already discussed here.

function [b,c]=myFind2(x,A,B)
a=1;
b=numel(x);
c=1;
d=numel(x);
while (a+1<b||c+1<d)
    lw=(floor((a+b)/2));
    if (x(lw)<A)
        a=lw;
    else
        b=lw;
    end
    lw=(floor((c+d)/2));
    if (x(lw)<=B)
        c=lw;
    else
        d=lw;
    end
end
end


Creating URL with Builder pattern What do you think about this piece of code? How would you design the builder pattern in this situation?

#ifndef CPP_URL
#define CPP_URL
#include<iostream>
#include<vector>
#include<map>
using std::string;

enum protocol  {
  HTTP,
  HTTPS
};

static string map(protocol scheme) {
  switch(scheme) {
    case HTTP:
      return "http";
    default:
      return "https";
  }
}

static int defaultPort(protocol scheme) {
  switch (scheme) {
    case HTTP:
      return 80;
    default:
      return 440;
  }
}

class url final {
private:
  using list = std::vector<std::string>;
  using pairs = std::map<std::string, std::string>;
  const list paths;
  const pairs queries;
  const protocol scheme;
  const string domain;
  const string fragment;
  const string username;
  const string password;
  mutable int port;
public:
  class builder {
   friend url;
   private:
      protocol scheme;
      pairs queries;
      list paths;
      string domain;
      string fragment;
      string username;
      string password;
      int port = -1;
   public:
     builder& setScheme(protocol);
     builder& setFragment(const string&);
     builder& setDomain(const string&);
     builder& setUsername(const string&);
     builder& setPassword(const string&);
     builder& setPort(int port);
     builder& addQuery(const string&, const string&);
     builder& addPath(const string&);
     url& build() const;
  };
  explicit url(const url::builder&);
  string build() const;
};

using builder = url::builder;

inline builder& builder::setScheme(protocol scheme) {
  this->scheme = scheme;
  return *this;
}

inline builder& builder::setUsername(const string& username) {
  this->username = username;
  return *this;
}

inline builder& builder::setPassword(const string& password) {
  this->password = password;
  return *this;
}

inline builder& builder::setFragment(const string& fragment) {
  this->fragment = fragment;
  return *this;
}

inline builder& builder::setDomain(const string& domain) {
  this->domain = domain;
  return *this;
}

inline builder& builder::setPort(int port) {
  this->port = port;
  return *this;
}

inline builder& builder::addQuery(const string& key, const string& value) {
  queries.insert(std::pair<string, string>(key, value));
  return *this;
}

inline builder& builder::addPath(const string& path) {
  paths.insert(paths.begin(), path);
  return *this;
}

inline url& builder::build() const {
  return *(new url(*this));
}

inline url::url(const builder& object)
    : paths(object.paths)
    , queries(object.queries)
    , scheme(object.scheme)
    , domain(object.domain)
    , fragment(object.fragment)
    , username(object.username)
    , password(object.password)
    , port(object.port)
    {}

string url::build() const {
  string url = map(scheme).append("://");
  if (!username.empty()) {
    url.append(username);
    if (!password.empty()) {
      url.append(":").append(password);
    }
    url.append("@");
  }
  url.append(domain);
  if (port == -1)
    port = defaultPort(scheme);
  url.append(":").append(std::to_string(port));
  for (string path : paths) {
    url.append("/");
    url.append(path);
  }
  auto it = queries.begin();
  if (it != queries.end()) {
    url.append("?").append(it->first)
      .append("=").append(it->second);
    for(it++; it != queries.end(); it++) {
      url.append("&").append(it->first)
        .append("=").append(it->second);

    }
  }
  if (!fragment.empty()) {
    url.append("#").append(fragment);
  }
  return url;
};

#endif

This is how we can use that:

   url url = url::builder()
    .setScheme(HTTPS)
    .setDomain(YOUTUBE_DOMAIN)
    .addPath(WATCH_PATH)
    .addQuery(CATEGORY, ITEM)
    .build();
  std::cout<<url.build()<<std::endl;

Include the required headers

You use std::string extensively, but you don't include <string>. This is allowed to work (any standard header is allowed to act as if it includes any or all others), but it's not required to work (and didn't, for me).

Use the proper defaults

Right now, your code defaults to https on port 440, but the normal default for https is port 443. I'd tend to include the port in the result if and only if it's explicitly specified. Otherwise, it's probably better to let the browser sort out the port, since most know quite a few more than your code does.

Fluent Interface

I'm not particularly excited about fluent interfaces in general, but if you're going to use one, I'd prefer to get rid of the set on the beginnings of most of the setters. If you have something like:

auto uri = builder().scheme(HTTPS).domain("www.google.com").build();

...you don't really need a set on the beginning of each to make it apparent what you intend.

Consider unique types for the parts of a URL/URI

I tend to wonder whether we wouldn't be better served by a set of tiny classes, one for each type of element in a URL, with each able to (for example) insert itself to a stream, with the url class basically just a set of those. At least for some of the obvious cases, I'd also at least consider using overloaded operators instead of named functions. For example, a fairly minimalist version might look something like this:

struct protocol {
    enum prot { http, https } p_;

    protocol(prot p) : p_(p) {}

    friend std::ostream &operator<<(std::ostream &os, protocol const &p) {
        switch (p.p_) {
        case http: return os << "http://";
        case https: return os << "https://";
        }
    }
};

struct query {
    std::string k;
    std::string v;
};

class queries {
    std::vector<query> queries_;
public:
    void add(query const &q) { queries_.push_back(q); }

    friend std::ostream &operator<<(std::ostream &os, queries const &q) {
        std::string sep = "?";
        for (auto const & f : q.queries_) {
            os << sep << f.k << "=" << f.v;
            sep = "&";
        }
        return os;
    }
};

class path {
    std::vector<std::string> components;
public:
    void add(std::string const &path) {
        components.push_back(path);
    }

    friend std::ostream &operator << (std::ostream &os, path const &p) {
        for (auto const & s : p.components)
            os << s << "/";
        return os;
    }
};

class url {
    protocol prot_;
    path path_;
    queries q_;
public:
    url(protocol::prot p) : prot_(p) {}

    url &operator/(std::string const &p) { path_.add(p); return *this; }
    url &operator&(query const &q) { q_.add(q); return *this; }

    friend std::ostream &operator<<(std::ostream &os, url const &u) {
        return os << u.prot_ << u.path_ << u.q_;
    }
};

int main() {
    url u = url(protocol::http) / "www.youtube.com" / "watch" & query{"v", "tpnrd0xGRsw"};
    std::cout << u;
}

Note how url's operator<< (roughly equivalent to your build) is now almost trivially simple--and if we add in types for a fragment, port, user name, and so on, it'll remain almost equally trivial, because most of the complexity will be delegated to each of those classes instead of being crammed together into the one giant "build" that knows everything about a URL and how all the pieces need to be delimited and such. Instead, it needs to know the order of the components in a URL, but that's about it. All the details of how to write each piece are delegated to the type for that piece (most of which are individually pretty trivial too).

More syntactic sugar

After some further thought, I've decided that a little more syntactic sugar probably won't rot our teeth too badly. It might be worth adding a couple of tiny functions like this:

url http() { return url(protocol::http); }
url https() { return url(protocol::https); }

This way we can generate a url something like this:

url u = https() / "www.youtube.com" / "watch" & query{"v", "tpnrd0xGRsw"};

Seems a tad cleaner to me, anyway.


Entity collection best practice (separation of concerns, dependency injection, ...) I build a collection to ensure only valid entities in an array so I don't have to validate after every function / method call as I could rely on the collection to have only valid entities stored.

class WorldCollection implements Collection, ArrayAccess {

    private $container = array();
    private $oValidator;

    public function __construct (Validator $oWorldValidator) {
        $this->oValidator = $oWorldValidator;
    }

    public function offsetExists ($offset) {
        return isset($this->container[$offset]);
    }

    public function offsetGet ($offset) {
        return isset($this->container[$offset]) ? $this->container[$offset] : null;
    }

    /**
     * READ ME
     */
    public function offsetSet ($offset, $value) {
        $this->oValidator->validate($value)
        if (is_null ($offset)) {
            $this->container[] = $value;
        } else {
            $this->container[$offset] = $value;
        }
    }

    public function offsetUnset ($offset) {
        unset($this->container[$offset]);
    }
}

As I want to separate concerns and follow dependency injection I inject the Validator in the constructor of the collection and validate in the ofsetSet method to ensure only valid values will be stored.

class WorldValidator implements Validator {

    public function validate($aWorld) {
        if (!is_array($aWorld)) {
            throw new WorldValidationException('invalid type', WorldValidationException::ERROR_CODE_INVALID_TYPE);
        }

        return true;
    }
}

(The validator is simplified for example purpose.)

Did I seperate it right? Or should I handle this
kind of validation differently?
Should I catch the validation exception to not disturb the program
flow? If so should I store the exception and offer a getErrors
method?
Should I rename the collection ValidWorldCollection and extend
from WorldCollection?
Should the InvalidWorldException extend RuntimeException or
LogicException? Same for WorldValidationException in the
validator
Should I create a World Class and exclude the Validation from the
Collection using instanceof ?
Should I have used a more appropriate Spl DataStructure?
(SplObjectStorage?)  Or is it all a waste of time?

Design

Dependency injection is very useful when you have multiple implementations of a given dependency. If you don't plan implementing another Validator, then it's probably premature abstraction. I'll assume here that you have other Validator implementations.

Let me answer your questions:

The separation itself is good.
An exception is meant to be catched "whenever possible", and it is not possible in WorldCollection, since you don't know how to handle it. You need to wonder what you want your application to do when the data does not validate.

If you want WorldCollection::offsetSet to not do anything when the validation fails, then WorldValidator::validate should simply return true or false, and no exception should be thrown.

If the exception is to be catched later on in the code, then don't do anything in WorldCollection::offsetSet, since another code will take care of the issue.

You can easily mix those two approaches in order to catch some of the exception at some point, and other ones later on (which means WorldValidator::validate should always throw an exception, and return nothing).
Only if you plan on having other WorldCollections. I don't think so.
LogicException should only be launched if there is a flow in your program, ie. an exception that would never be thrown in a perfect program. RuntimeException is a base class used for errors such as OutOfBounds or Overflow. I'd use InvalidArgumentException.
I didn't understand the question. Note that instanceof is never good design, and exists to work around design errors.
ArrayAccess is a reasonable choice, it lets you do foreach on your data easily, whereas with Iterator you would have to implement a ton of methods. SplObjectStorage could be used, but only if you don't need the keys ArrayAccess provides.

Implementation

Do you want only one exception with different types, such as ERROR_CODE_INVALID_TYPE?

Why don't you use multiple exceptions?
If you want to stick with one exception, don't pass "invalid type" in the constructor, since it is always going to be the same message. Prefer to override Exception::__toString() to return "invalid type" when the type is ERROR_CODE_INVALID_TYPE.

Use offsetExists in offsetGet instead of repeating yourself?
Consider using NULL instead of null, and TRUE instead of true, even if they are case-insensitive.
$this->oValidator->validate($value) forgot a semicolon?
Don't use return if you're not going to check the return value.