generic flyweighting function I made this little function for flyweighting any type that has operator<. I followed the convention of make_unique and make_shared with make_one. Not sure if that's the best name.

// Create a single instance of an object, using
// operator< to determine equality.
// Note that we take a value instead of a constructor
// arguments because often we'll want to mutate a field,
// then create a new object, without passing in everything.
template<class T>
std::shared_ptr<const T> make_one(const T& value) {

  struct cmp {
    bool operator()(const T* a, const T* b) const {
      return *a < *b;
    }
  };

  static std::set<const T*, cmp > values;

  auto iter = values.find(&value);

  if(iter != values.end()) {
    return (*iter)->shared_from_this();
  }

  auto ptr = std::shared_ptr<T>(new T(value), [](T* p) {
    values.erase(p); delete p;
  });
  values.insert(ptr.get());
  return ptr;

}

Test code:

  struct Foo : std::enable_shared_from_this<Foo> {
    int x = 0;
    Foo(int x) : x(x) { }
    bool operator<(Foo rhs) const { return x < rhs.x; }
  };

  auto p0 = make_one(Foo{0});
  auto p1 = make_one(Foo{0});
  assert(p0 == p1);

  auto p2 = make_one(Foo{42});
  assert(p2 != p0);

Review goals:

Can I avoid requiring enable_shared_from_this?
Can I make it thread safe without too much trouble?
Any other ideas for improvement.

The first thing I would note is that you should point out non obvious features of your implementation. The nice thing that is not immediately obvious is that when all external references are gone the object is automatically deleted from the make_one()::values set.

This is not really a requirement of a flyweight.
But a nice little trick here.

So if the automatic deletion is required then the answers to the question are:

  Can I avoid requiring enable_shared_from_this?

No. I don't think so.

You could re-invent some reference counting model but that seems a lot of work in comparison to simply using the standard libraries.

As an alternative, You can get around it slightly by using std::set<std::weak_ptr<T>> the trouble here is that even though the resource would be cleaned up the actual space for the resource would be maintained after the object is destroyed.

If on the other hand automatic deletion is not required.

  Can I avoid requiring enable_shared_from_this?

Yes. there are simpler ways that this could be written if there is no requirement to delete upon all external references going away. Now if you want it again it will still be there.

template<class T>
T const& make_one(const T& value) {

    static std::set<T> values;

    auto result = values.insert(value);
    return *(result.first);
}

  Can I make it thread safe without too much trouble?

Yes simply add a lock on the make_one()

  Any other ideas for improvement.

You could add the ability to move an object into your make_once() rather than copy it each time. Even better would be to allow the construction of T from its parameters.

// Move an object in your set
template<typename T>
std::shared_ptr<const T> make_one(T&& value)

// Emplace a value in your set
template<typename T, typename... Args>
std::shared_ptr<const T> make_one(Args&&... value)


Removing bytes from a byte array I am reading from a Networkstream, and the response code is:

private async void GetResponse(NetworkStream stream)
{
  while (true)
  {
    var readBuffer = new byte[4096];
    var asyncReader = await stream.ReadAsync(readBuffer, 0, readBuffer.Length);
    var result = RemoveBytes(readBuffer, new byte[] { 130, 119, 126, 118, 48, 49, 12, 19, 14 });
    List<byte> l = null;
    var w = 1;
    while (w > 0)
    {
      w = FindPattern(result, new byte[] { 1, 0, 131 }, new[] { false, true, false });
      if (w <= 0) continue;
      l = result.ToList();
      l.RemoveAt(w);
      l.RemoveAt(w);
      l.RemoveAt(w);
      Buffer.BlockCopy(l.ToArray(), 0, result, 0, result.Length - 3);
    }
    if (l != null) txtBoxMessagesIn.Text += Encoding.ASCII.GetString(l.ToArray()) + Environment.NewLine;
    if (asyncReader <= 0) break;
  }
}

I initially remove a group of know bytes using:

public static byte[] RemoveBytes(byte[] input, byte[] pattern)
{
  if (pattern.Length == 0) return input;
  var result = new List<byte>();
  int i;
  for (i = 0; i <= input.Length - pattern.Length; i++)
  {
    var foundMatch = !pattern.Where((t, j) => input[i + j] != t).Any();
    if (foundMatch) i += pattern.Length - 1;
    else result.Add(input[i]);
  }
  for (; i < input.Length; i++)
  {
    result.Add(input[i]);
  }
  return result.ToArray();
}

Then I have the following method to search for a pattern with a wilcard in a byte array:

public static int FindPattern(byte[] body, byte[] pattern, bool[] wild, int start = 0)
{
  var foundIndex = -1;
  if (body.Length <= 0 || pattern.Length <= 0 || start > body.Length - pattern.Length || pattern.Length > body.Length) return foundIndex;
  for (var index = start; index <= body.Length - pattern.Length; index += 4)
    if (wild[0] || (body[index] == pattern[0]))
    {
      var match = true;
      for (var index2 = 1; index2 <= pattern.Length - 1; index2++)
      {
        if (wild[index2] || (body[index + index2] == pattern[index2])) continue;
        match = false;
        break;
      }
      if (!match) continue;
      foundIndex = index;
      break;
    }
  return foundIndex;
}

I think the remove bytes method is fine, but the way I search for the wilcard pattern and copy the array seems a bit clunky. Credit to the author of the wildcard search code which can be found here.

You aren't using braces {} for the outer loops body which is bad, bad, bad. You should always use them although they are optional it just will make your code less error prone.

If you decide not to use them, you should stick to your style. Right now you are mixing them.

Using a guard clause is a good idea, but if one needs to scroll to the right to see each condition its suboptimal.

Use some vertical space to group related code together makes your code much more readable and easier to maintain.

By adding a method which returns an IEnumerable<int> containing the start positions of the possible patterns will improve readability like so

private static IEnumerable<int> GetPatternStartings(byte[] body, byte[] pattern, bool[] wild, int start = 0)
{
    for (var index = start; index <= body.Length - pattern.Length; index += 1)
    {
        if (wild[0] || (body[index] == pattern[0]))
        {
            yield return index;
        }
    }
}

The name of the method could/should be adjusted but I couldn't come up with a better one.

If we would now add a method to check if there really is a pattern like so

private static bool IsPattern(byte[] body, byte[] pattern, bool[] wild, int bodyIndex)
{
    for (var index = 1; index <= pattern.Length - 1; index++)
    {
        if (wild[index] || (body[bodyIndex + index] == pattern[index])) continue;

        return false;
    }

    return true;
}

we can then implement the mentioned points and change the former FindPattern() method to

public static int FindPattern(byte[] body, byte[] pattern, bool[] wild, int start = 0)
{
    var foundIndex = -1;

    if (body.Length <= 0
        || pattern.Length <= 0
        || start > body.Length - pattern.Length
        || pattern.Length > body.Length)
    { return foundIndex; }

    foreach (int patternStart in GetPatternStartings(body, pattern, wild, start))
    {
        if (IsPattern(body, pattern, wild, patternStart)) { return patternStart; }
    }

    return foundIndex;

}

So let us take a look at this

private async void GetResponse(NetworkStream stream)
{
  while (true)
  {
    var readBuffer = new byte[4096];
    var asyncReader = await stream.ReadAsync(readBuffer, 0, readBuffer.Length);
    var result = RemoveBytes(readBuffer, new byte[] { 130, 119, 126, 118, 48, 49, 12, 19, 14 });
    List<byte> l = null;
    var w = 1;
    while (w > 0)
    {
      w = FindPattern(result, new byte[] { 1, 0, 131 }, new[] { false, true, false });
      if (w <= 0) continue;
      l = result.ToList();
      l.RemoveAt(w);
      l.RemoveAt(w);
      l.RemoveAt(w);
      Buffer.BlockCopy(l.ToArray(), 0, result, 0, result.Length - 3);
    }
    if (l != null) txtBoxMessagesIn.Text += Encoding.ASCII.GetString(l.ToArray()) + Environment.NewLine;
    if (asyncReader <= 0) break;
  }
}

The call to ToList() and 3 times RemoveAt() together with the Buffer.BlockCopy() will slow down the whole thing.
if (w <= 0) continue; the continue should better be a break. There is no need to evaluate again the while condition. In addition this condition should be (w < 0) if the pattern should be found at the start too.
the pattern and wild to be used in FindPattern() should be created at the start of the method. It won't change.
w is a poorly named variable, let us use patternIndex instead.

Applying this will lead to

private async void GetResponse(NetworkStream stream)
{
    byte[] pattern = new byte[] { 1, 0, 131 };
    bool[] wild = new bool[] { false, true, false };
    int patternLength = pattern.Length;

    while (true)
    {
        var readBuffer = new byte[4096];
        var asyncReader = await stream.ReadAsync(readBuffer, 0, readBuffer.Length);
        var result = RemoveBytes(readBuffer, new byte[] { 130, 119, 126, 118, 48, 49, 12, 19, 14 });

        var patternIndex = 1;
        while (patternIndex > 0)
        {
            patternIndex = FindPattern(result, pattern, wild);
            if (patternIndex < 0) { break; }

            byte[] current = new byte[result.Length - patternLength];
            Buffer.BlockCopy(result, 0, current, 0, patternIndex);
            Buffer.BlockCopy(result, patternIndex + patternLength, current, patternIndex, result.Length - patternIndex - patternLength);
            result = current;
        }

        if (result != null && result.Length > 0)
        {
            txtBoxMessagesIn.Text += Encoding.ASCII.GetString(l.ToArray()) + Environment.NewLine;
        }
        if (asyncReader <= 0) { break; }
    }
}

So now we are finished, aren't we ? NO !

Lets check this RemoveBytes() method, because I see a pattern there.

After renaming the method to RemovePattern we can have 2 overloaded ones like so

private static byte[] RemovePattern(byte[] input, byte[] pattern)
{
    return RemovePattern(input, pattern, new bool[pattern.Length]);
}

private static byte[] RemovePattern(byte[] input, byte[] pattern, bool[] wild)
{
    int patternLength = pattern.Length;
    var patternIndex = -1;

    while ((patternIndex = FindPattern(input, pattern, wild)) >= 0)
    {
        byte[] current = new byte[input.Length - 3];
        Buffer.BlockCopy(input, 0, current, 0, patternIndex);
        Buffer.BlockCopy(input, patternIndex + patternLength, current, patternIndex, input.Length - patternIndex - patternLength);
        input = current;
    }
    return input;
}

You see, I have extracted the removal to a separate method. Now the former GetResponse() method will become this

private async void GetResponse(NetworkStream stream)
{
    byte[] pattern = new byte[] { 1, 0, 131 };
    bool[] wild = new bool[] { false, true, false };
    byte[] responsePattern = new byte[] { 130, 119, 126, 118, 48, 49, 12, 19, 14 };
    int patternLength = pattern.Length;

    while (true)
    {
        var readBuffer = new byte[4096];
        var asyncReader = await stream.ReadAsync(readBuffer, 0, readBuffer.Length);

        var result = RemovePattern(readBuffer, responsePattern);
        result = RemovePattern(result, pattern, wild);

        if (result != null && result.Length > 0)
        {
            txtBoxMessagesIn.Text += Encoding.ASCII.GetString(l.ToArray()) + Environment.NewLine;
        }
        if (asyncReader <= 0) { break; }
    }
}


More efficient way to narrow down a range I need to get data from a spreadsheet where there are three parameters.  A product ID which is multiple rows, within the rows of product ID, there is another set of rows with the charge type, within that set of rows, there is a charge I want to find, which may also span multiple rows.  If the charge does span multiple rows, I take the first one.

I have a function called New_Rng which takes the sheet object, the range within the sheet to be searched, and the string to look for, and returns the range which encompasses the first and last occurrence of the search string.

I'm doing multiple calls to wind up with the value that I need, but I know it's not efficient.

This is what I have now:

dim fndRng as range
dim shtz as new workshseet
dim ctr as long

    ctr = 4

    set shtz = sheets("DATA")

    Set fndRng = shtz .range(StartRange, shtz .Cells(LastRow,LastColumn))

    If Not fndRng Is Nothing Then Set fndRng = New_Rng(shtz, fndRng, shtz.Cells(ctr, searchVal)

    If Not fndRng Is Nothing Then Set fndRng = fndRng.Offset(0, (SchCol1 - SchCol2))
    If Not fndRng Is Nothing Then Set fndRng = New_Rng(shtz, fndRng, SVal2)
    If Not fndRng Is Nothing Then Set fndRng = fndRng.Offset(0, (SchCol2 - SchCol3 ))
    If Not fndRng Is Nothing Then Set fndRng = New_Rng(shtz, fndRng, val3)
    If Not fndRng Is Nothing Then Set fndRng = fndRng.Offset(0, (SchCol3  - SchCol4))
    If Not fndRng Is Nothing Then
        For Each zell In fndRng
            If zell.Row = fndRng.Row Then LoadVar(ctr, 0) = zell.value
        Next zell
    End If

I know there's a better way, but I can't figure it out.

Worksheets have a CodeName property - View Properties window (F4) and the (Name) field (the one at the top) can be used as the worksheet name. This way you can avoid Sheets("mySheet") and instead just use mySheet. This will eliminate the shtz variable, which isn't telling us anything.

Speaking of variable names, try to give them more meaningful names - it makes it easier to follow what is happening.

Like this snippet

Sheet1.Cells(counter, searchVal))

I can tell searchVal has to be an integer, but if I saw it anywhere else, I'd think it's a string.

Also with your search columns being SchCol1 - I'm sure there's a better way to do that. Maybe productColumn and such.

I have to think your series of If Not Nothing is because you were getting errors. I also have to imagine you're passing all of these values to the above code? All the columns and all the search strings?

So, the easiest way to make this more efficient is to bring it into an array. In my example, I'm returning a string instead of a range, because I assume that's what you're after. Either way, it's an example.

Option Explicit
Sub RichardU()
    Dim lastRow As Long
    Dim lastColumn As Long
    Dim searchValues As Variant
    Dim searchArray As Variant
    Dim foundRange As Range
    Dim startRange As Range

    lastRow = 10
    lastColumn = 4
    Set startRange = Sheet1.Cells(1, 1)

    searchValues = Sheet1.Range(Cells(1, 7), Cells(1, 10))
    searchArray = Sheet1.Range(startRange, Sheet1.Cells(lastRow, lastColumn))

    Set foundRange = FindInArray(searchArray, searchValues(1, 1), searchValues(1, 2), searchValues(1, 3))

End Sub

Function FindInArray(ByVal valueArray As Variant, ByVal firstString As String, ByVal secondString As String, ByVal thirdString As String) As String
    Dim rowIndex As Long
    With valueArray
        For rowIndex = LBound(valueArray) To UBound(valueArray)
            If valueArray(rowIndex, 1) = firstString And valueArray(rowIndex, 2) = secondString And valueArray(rowIndex, 3) = thirdString Then
                FindInArray = valueArray(rowIndex, 4)
                Exit Function
            End If
        Next
    End With
End Function

So what you're doing here is bringing the entire search range into an array, passing that array to your function and matching all of the search strings at once.

You will probably have to build in some error handling. And if you want the range instead of the string, you can still bring it all into the array and return where the range would be as a pair of coordinates

Option Explicit
Sub RichardU()
    Dim lastRow As Long
    Dim lastColumn As Long
    Dim searchValues As Variant
    Dim searchArray As Variant
    Dim foundCoordinates As Variant
    Dim foundRange As Range
    Dim startRange As Range

    lastRow = 10
    lastColumn = 4
    Set startRange = Sheet1.Cells(1, 1)

    searchValues = Sheet1.Range(Cells(1, 7), Cells(1, 10))
    searchArray = Sheet1.Range(startRange, Sheet1.Cells(lastRow, lastColumn))

    foundCoordinates = FindInArray(searchArray, searchValues(1, 1), searchValues(1, 2), searchValues(1, 3))
    Set foundRange = Sheet1.Range(Cells(foundCoordinates(1) + 1), Cells(foundCoordinates(1) + 1, foundCoordinates(2) + 2))

End Sub

Function FindInArray(ByVal valueArray As Variant, ByVal firstString As String, ByVal secondString As String, ByVal thirdString As String) As Variant
    Dim rowIndex As Long
    Dim foundCoordinates() As Long
    ReDim foundCoordinates(1 To 2)
    With valueArray
        For rowIndex = LBound(valueArray) To UBound(valueArray)
            If valueArray(rowIndex, 1) = firstString And valueArray(rowIndex, 2) = secondString And valueArray(rowIndex, 3) = thirdString Then
                foundCoordinates(1) = rowIndex
                foundCoordinates(2) = 4
                FindInArray = foundCoordinates
                Exit Function
            End If
        Next
    End With
End Function

You'd just change the offsets I used to match your sheet layout.

So I was thinking about it, and I think the best way for you to simplify this would be to use a function to get the row index that matches -

Function FindArrayRow(ByVal valueArray As Variant, ByVal searchValues As Variant) As Long
    Dim rowIndex As Long
    With valueArray
        For rowIndex = LBound(valueArray) To UBound(valueArray)
            If valueArray(rowIndex, 1) = searchValues(0) And valueArray(rowIndex, 2) = searchValues(1) And valueArray(rowIndex, 3) = searchValues(2) Then
                FindArrayRow = rowIndex
                Exit Function
            End If
        Next
    End With
End Function

You would just return the row number in the array, adjust it for wherever your array started on the sheet, and use it to get the target column that you were initially looking for.


Project Euler #1 in Java Project Euler #1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Here is my solution:
public class MultipleFinder {

    private static final int MAX_NUMBER = 1000;
    private static final int[] MULTIPLES = new int[] { 3, 5 };

    public static void main(String[] args) {
        long time = System.nanoTime();
        int sum = 0;
        for(int multiple : MULTIPLES) {
            sum += triangle((MAX_NUMBER - 1) / multiple) * multiple;
        }
        sum -= triangle((MAX_NUMBER - 1) / (MULTIPLES[0] * MULTIPLES[1])) * (MULTIPLES[0] * MULTIPLES[1]);
        System.out.println("Result: " + sum + "\nTime used for calculation in nanoseconds: " + (System.nanoTime() - time));
    }

    private static int triangle(int i) {
        return (i + 1) * i / 2;
    }

}

Output:

 Result: 233168
 Time used for calculation in nanoseconds: 51764

Questions:

Is there a way to increase efficiency?
Is there a way to change the code so that I get the correct solution when I add a multiple?

Discussing performance of methods which are almost entirely in the main method, is sort of pointless. Java performance requires hot-spot compiling, and that does not really happen until methods are run many, many times. The main method is run just once, so is seldom compiled efficiently. Perhaps it's only ever interpreted.

In terms of efficiency, the algorithm you are using is documented as being the best for this puzzle. Essentially there is no better way.

Your subsequent question about how to incorporate additional multiples is complicated....

the way the algorithm works right now, is to calculate the sum of multiple sequences. One sequence is:

3, 6, 9, 12, 15, ...

The second sequence is:

5, 10, 15, 20, .....

The algorithm works by taking the sum of the two sequences, and subtracting the 'double-count', those values that are double-counted because they intersect (like 15, above).

If you have multiple sequences, say, 3, 5, and 7, you will need to sum up all the individual sequences, then subtract the double, and triple counts.

You will need to subtract the intersection with 3*5 (15), as well as 3*7 (21), and also the triple-add 3*5*7 (105)

As you add numbers in to the multiples, you will need to find more of the combinations of parameters that intersect, and need to be subtracted.


Transform a MongoDb parent reference tree into a deep nested tree Given a mongodb collection that stores trees as nodes with parent references this methods returns a deep nested tree where every child nodes are stored in a property childs[Seq]

  def getTree(rootId: BSONObjectID): Future[CategoryTreeNode] = {

    def collect(parent: CategoryTreeNode): Future[CategoryTreeNode] = {

      // Query the database - returns a Future[Seq[CategoryTreeNode]]
      getChilds(parent._id.get).map {

        // Seq[CategoryTreeNode]
        childs =>
          Future.sequence(
            childs.map(child => collect(child)) // Recursion
          ).map(childSeq => parent.copy(childs = Some(childSeq)))

      }.flatMap(x => x).map(y => y)

    }

    // Find the root node and start the recursion
    findOne[CategoryTreeNode](Json.obj("_id" -> rootId)).map(maybeNode => maybeNode match {
      case None => throw new RuntimeException("Current node not found by id!")
      case Some(node) => collect(node)
    }).flatMap(x => x)

  }

flatMap (x => x) would probably better be written as flatten.
map (x => x) is essentially a no-op, and could be removed.
map ( ... ) flatten is equivalent to flatMap (...)
It doesn't seem useful to put a type into a comment – you can specify the type for parameters of lambdas as well:

{ (childs: Seq[CategoryTreeNode]) => ...

However, this style is generally discouraged. It would be more useful to store the future from the DB in a variable which gets typed explicitly.
Higher-order method like map should not be invoked with a leading .: do collection map (x => ...) instead of collection.map(x => ...) (source).
(foo => foo match { ... }) can be simplified to (_ match { ... })
(child => collect(child)) can be simplified to (collect(_)) or even just collect

Together, I'd clean up your code to this:

def getTree(rootId: BSONObjectID): Future[CategoryTreeNode] = {
  def collect(parent: CategoryTreeNode): Future[CategoryTreeNode] = {
    // Query the database
    val ourChilds: Future[Seq[CategoryTreeNode]] = getChilds(parent._id.get)
    ourChilds flatMap { childs =>
      Future.sequence(childs map collect) map { childSeq =>
        parent.copy(childs = Some(childSeq))
      }
    }
  }

  // Find the root node and start the recursion
  findOne[CategoryTreeNode](Json.obj("_id" -> rootId)) flatMap (_ match {
    case None => throw new RuntimeException("Current node not found by id!")
    case Some(node) => collect(node)
  })
}


To 'this' or not to 'this'? I was given a homework and I have 2 solutions: one that uses this and other one that doesn't.

I tested both solutions on jsPerf but sometimes it says the version with this is faster or sometimes the other one. So I think I cannot really rely on jsPerf. Anyway, should performance be always the top priority?

By the way, here is the problem statement:

  Write a function addg that adds from many invocations, until it sees an empty invocation.

  Something like:

  addg();                // undefined

  addg(2)();             // 2

  addg(2)(7)();          // 9

  addg(3)(0)();          // 3

  addg(1)(2)(4)(8)();    // 15

  addg(5)(4)(-2)();      // 7

Here are my 2 solutions:

version with this:

function add(a,b){
  return a+b;
}

function addg(val){
  var numbers = [];

  this.addToCollection = function(val){
    numbers.push(val);

    if(typeof val !== 'number'){  // in case of ()
      var sum = 0,
          l = numbers.length;

      numbers.forEach(function(num, i){
        if(i === l-1){
          return;
        } else {
          sum = add(sum, num);
        }
      });

//       console.log(numbers);

      if(numbers.length === 1 && numbers[0] === undefined){
        return undefined;
      } else {
        return sum;
      }

    } else {  // in case of (n)
      return this.addToCollection;  // return the function each time so you can apply it to other numbers in the chain
    }

  };

  return this.addToCollection(val);
}

console.log(addg());                // undefined
console.log(addg(2)());             // 2
console.log(addg(2)(7)());          // 9
console.log(addg(3)(0)());          // 7
console.log(addg(1)(2)(4)(8)());    // 15
console.log(addg(5)(4)(-2)());      // 7

version without this:

function add(a,b){
  return a+b;
}

function addg(val){
  var numbers = [];

  function addValues(val){
    numbers.push(val);

    if(typeof val !== 'number'){  // in case of ()

      var sum = 0,
          l = numbers.length;

      numbers.forEach(function(num, i){
        if(i === l-1){
          return;
        } else {
          sum = add(sum, num);
        }
      });

//       console.log(numbers);

      if(numbers.length === 1 && numbers[0] === undefined){
        return undefined;
      } else {
        return sum;
      }

    } else {  // in case of (n)
      return addValues; // return the function each time so you can apply it to other numbers in the chain
    }
  }

  return addValues(val);

}

console.log(addg());                // undefined
console.log(addg(2)());             // 2
console.log(addg(2)(7)());          // 9
console.log(addg(3)(0)());          // 7
console.log(addg(1)(2)(4)(8)());    // 15
console.log(addg(5)(4)(-2)());      // 7

I would like to know which version is better and why. If you have any suggestions for improving my code, please feel free to let me know.

First and foremost:

  Anyway, should performance be always the top priority?

Definitely not.  Don't write things that are needlessly unperformant, but only be overly concerned with performance when you have a reason to be.  Most of the time JS execution time is irrelevant, because you're waiting for user interaction, or for a network request, or something else that makes the execution time of the JS pretty unimportant.

I'd be more concerned with writing code that's clear, expressive, and maintainable than performant.

Regarding your usage of this, though, you definitely shouldn't be using this as you are in the first example.  You're leaking into the global scope.  When addg is run, what is this?  If you were calling obj.addg(), this would be obj, but since you're just calling addg(), this is the global scope A.K.A. window (in the browser).

With your first version if you run this in your console you'll see:

addg();
//undefined
addToCollection;
//function!  Whoops

That's not what you want.  You don't need to assign the internal addToCollection function anywhere, so don't.

An add function is a bit pointless.  You're adding undefined to the array of numbers in the () case, then adding special logic to exclude it from the sum, later, but instead you should just not add undefined at all.  Only do numbers.push(val) if typeof val === 'number'.

But, then, do you really need to keep an array of numbers at all?


Math Problem Solving This program takes the first number you input and divides by 2, then takes the result and multiplies by 4. I decided to use classes and file writing because I just learned it yesterday. Please critique.

# Write a program with two functions.
# The first function should take an integer as a parameter and return the result of the
# integer divided by 2.
# The second function should take an integer as a parameter and return the result of
# the integer multiplied by 4. Call the first function, save the result as a variable,
# and pass it as a parameter to the second function

myList = []

class Math:
    def __init__(self, x):
        self.number1 = x

#The try and excepts were created just in case I change the input to be mine instead of users's
#Divide the input

    def divide(self):
        try:
            self.division = self.number1 // 2
            return self.division
        except (TypeError, NameError):
            print("Unsupported format")

#Multiply the returned input

    def multiply(self):
        try:
            self.multiplication = self.division * 4
            myList.append(self.multiplication)
        except (AttributeError, NameError):
            print("First variable was not recognized")

while True:
    try:
        myNumber = Math(int(input("What number do you choose?"
                              "\nThis number will be divided by 2"
                              "\nThen it will be multiplied by 4\n")))
        myNumber.divide()
        myNumber.multiply()
        print(myList)
        tryAgain = input("Would you like to try again? "
                         "Press any key to continue. Press N to exit\n")

        if tryAgain == "N".lower():
            with open("data.txt", "w") as myData:
                myData.write("My data is: " + str(myList))
            break

    except(NameError,ValueError):
        print("Invalid Input")

Your coding style could be improved, for instance you could respect the naming conventions detailed in the PEP8.

Using classes is not judicious (Python is not Java). You could use simple functions. I understand that this is an exercise but it looks weird.

A function can have parameters and return a value. For instance with divide, you can write:

def divide(number):
    return number // 2

You can do the same for multiply.
To use those functions:

number = ...
result = multiply(divide(number))

Catching TypeError, NameError and AttributeError is not a good practice because they are generally raised because the developer (you) had made an error. This is not the user fault, so the message you display to the user is not useful.

If you really want a class here, you can store the list of results in instead of the user input.

class Math(object):
    def __init__(self):
        self.results = []

    def divide(self, number):
        return number // 2

    def multiply(self, number):
        return number * 4

    def calc(self, number):
        result = self.multiply(self.divide(number))
        self.results.append(result)

You can use this class like this:

my_math = Math()
my_math.calc(5)
my_math.calc(8)
print(my_math.results)
# -> [8, 16]

I'm repeating myself: divide and multiply should be functions, not methods here.


Parse complex text files using Python I'm looking for a simple way of parsing complex text files into a pandas DataFrame. Below is a sample file, what I want the result to look like after parsing, and my current method.

Is there any way to make it more concise/faster/more pythonic/more readable?

I have also put this question on Stack Overflow. I eventually wrote a blog article to explain this to beginners.

Here is a sample file:

Sample text

A selection of students from Riverdale High and Hogwarts took part in a quiz. This is a record of their scores.

School = Riverdale High
Grade = 1
Student number, Name
0, Phoebe
1, Rachel

Student number, Score
0, 3
1, 7

Grade = 2
Student number, Name
0, Angela
1, Tristan
2, Aurora

Student number, Score
0, 6
1, 3
2, 9

School = Hogwarts
Grade = 1
Student number, Name
0, Ginny
1, Luna

Student number, Score
0, 8
1, 7

Grade = 2
Student number, Name
0, Harry
1, Hermione

Student number, Score
0, 5
1, 10

Grade = 3
Student number, Name
0, Fred
1, George

Student number, Score
0, 0
1, 0

Here is what I want the result to look like after parsing:

                                         Name  Score
School         Grade Student number
Hogwarts       1     0                  Ginny      8
                     1                   Luna      7
               2     0                  Harry      5
                     1               Hermione     10
               3     0                   Fred      0
                     1                 George      0
Riverdale High 1     0                 Phoebe      3
                     1                 Rachel      7
               2     0                 Angela      6
                     1                Tristan      3
                     2                 Aurora      9

Here is how I currently parse it:

import re
import pandas as pd

def parse(filepath):
    """
    Parse text at given filepath

    Parameters
    ----------
    filepath : str
        Filepath for file to be parsed

    Returns
    -------
    data : pd.DataFrame
        Parsed data

    """

    data = []
    with open(filepath, 'r') as file:
        line = file.readline()
        while line:
            reg_match = _RegExLib(line)

            if reg_match.school:
                school = reg_match.school.group(1)

            if reg_match.grade:
                grade = reg_match.grade.group(1)
                grade = int(grade)

            if reg_match.name_score:
                value_type = reg_match.name_score.group(1)
                line = file.readline()
                while line.strip():
                    number, value = line.strip().split(',')
                    value = value.strip()
                    dict_of_data = {
                        'School': school,
                        'Grade': grade,
                        'Student number': number,
                        value_type: value
                    }
                    data.append(dict_of_data)
                    line = file.readline()

            line = file.readline()

        data = pd.DataFrame(data)
        data.set_index(['School', 'Grade', 'Student number'], inplace=True)
        # consolidate df to remove nans
        data = data.groupby(level=data.index.names).first()
        # upgrade Score from float to integer
        data = data.apply(pd.to_numeric, errors='ignore')
    return data

class _RegExLib:
    """Set up regular expressions"""
    # use https://regexper.com to visualise these if required
    _reg_school = re.compile('School = (.*)\n')
    _reg_grade = re.compile('Grade = (.*)\n')
    _reg_name_score = re.compile('(Name|Score)')

    def __init__(self, line):
        # check whether line has a positive match with all of the regular expressions
        self.school = self._reg_school.match(line)
        self.grade = self._reg_grade.match(line)
        self.name_score = self._reg_name_score.search(line)

if __name__ == '__main__':
    filepath = 'sample.txt'
    data = parse(filepath)
    print(data)

There are a few performance tricks we can apply here:

add __slots__ to the class definition should help with memory and performance as well:

class _RegExLib:
    """Set up regular expressions"""
    # use https://regexper.com to visualise these if required
    _reg_school = re.compile(r'School = (.*)\n')
    _reg_grade = re.compile(r'Grade = (.*)\n')
    _reg_name_score = re.compile(r'(Name|Score)')

    __slots__ = ['school', 'grade', 'name_score']

    def __init__(self, line):
        # check whether line has a positive match with all of the regular expressions
        self.school = self._reg_school.match(line)
        self.grade = self._reg_grade.match(line)
        self.name_score = self._reg_name_score.search(line)

using next() instead of .readline() should be faster as it uses a lookahead buffer internally:

with open(filepath, 'r') as file:
    line = next(file)
    while line:
        reg_match = _RegExLib(line)

        if reg_match.school:
            school = reg_match.school.group(1)

        if reg_match.grade:
            grade = reg_match.grade.group(1)
            grade = int(grade)

        if reg_match.name_score:
            value_type = reg_match.name_score.group(1)
            line = next(file, None)
            while line and line.strip():
                number, value = line.strip().split(',')
                value = value.strip()
                dict_of_data = {
                    'School': school,
                    'Grade': grade,
                    'Student number': number,
                    value_type: value
                }
                data.append(dict_of_data)
                line = next(file, None)

        line = next(file, None)

Some of the code style and other notes:

file is a builtin (in Python 2.x only), consider a different variable name
define your regular expression strings as raw strings
you can probably replace .* wildcard with a more concrete \d+ for the "grade" regex: Grade = (\d+)\n


My own getline function for reading strings from files I am a newbie to C++ and I want to do some cool stuff with it. Here I have implemented my own getline function which reads from a file. so what do you think of this getline function?

#include <iostream>
#include <fstream>
using namespace std;

class Foo {
private:
    char ch;
public:
    void getline(fstream& in, string& word, char delimeter ='\n'){
        word = "";
        while(in.get(ch)){
            word += ch;
            if(ch==delimeter)
                break;
        }
    }
};
int main(){
    Foo one;
    string temp;
    fstream obj("file.txt", ios::in | ios::out | ios::trunc );

    obj<<"this is our$ world";
    obj.seekg(0);
    one.getline(obj, temp,'$');
    cout<<temp<<endl;
}

Free the Functions!

First, as others have pointed out, this gains nothing from being a class--it probably makes more sense as a free function.

Good Inheritors Would Rather Switch than Fight!

Second, this specifies that its argument must be an fstream. This seems rather pointless. One of the major points of streams is that most functions can (and do) handle various kinds of streams by working with the base classes--usually std::istream and std::ostream. This lets your code work with any stream that provides the interface you need (in this case, just the ability to read, so an istream suffices).

Return Status

With those changed, the big shortcoming I see in this getline compared to std::getline is that it fails to return anything that can be interpreted as the status of the attempt at reading.

For example, in a typical case I might read and process all the lines of text from a file using a loop something like this:

std::ifstream input("input.txt");
std::string line;

while (std::getline(input, line))
    process(line);

If I want to read all the lines from a file with this getline, I guess I can do something like this:

while (getline(input, line), input.good())
    process(line);

That should work, but it's a bit clumsy at best, and sufficiently strange that most people would probably find it more difficult to understand. I think it would be better to do like most I/O routines, and return a reference to the stream you read from:

std::istream &getline(std::istream& in, string& word, char delimeter ='\n'){
    char ch;

    word = "";
    while(in.get(ch)){
        word += ch;
        if(ch==delimeter)
            break;
    }
    return in;
}

Spelling

The word you're spelling as "delimeter" is actually spelled "delimiter".

Delimiter Usage

Your code has behavior that differs from std::getline in a way I think reduces its utility. std::getline normally reads the delimiter from the stream, but does not include that delimiter in the output string (where your code does include the closing delimiter in the output string). At least when I've used it, including that delimiter wouldn't be very useful--I'd usually have to delete it if I read a string with this code. I'd probably omit it, and (if necessary) provide an overload that saved it (but still probably separately from the string it read).

Delimiter Specification

Probably the single biggest problem I have with std::getline is that you can only specify one specific character as the delimiter. If I were going to write one, I think I'd allow the user to pass something like a string, so they could (for example) pass "\t\r\n\v" as the delimiter, to have the function read to the next white-space.

Although it's more advanced, you could go even further, and let the user specify the delimiter as a regular expression, so they could specify arbitrarily complex patterns instead of just a few specific characters.


Keras stacked LSTM model for multiclass classification I am working on a multiple classification problem and after dabbling with multiple neural network architectures, I settled for a stacked LSTM structure as it yields the best accuracy for my use-case. Unfortunately the network takes a long time (almost 48 hours) to reach a good accuracy (~1000 epochs) even when I use GPU acceleration.

At this point, I would like some feedback about my code and my results, did I miss something? and hopefully some suggestions on how to further speed-up and improve the training process/code.

My code is the following:

# -*- coding: utf-8 -*-
import keras
import numpy as np
from time import time
from utils import dmanip, vis
from keras.models import Sequential
from keras.layers import LSTM, Dense
from keras.utils import to_categorical
from keras.callbacks import TensorBoard
from sklearn.preprocessing import LabelEncoder
from tensorflow.python.client import device_lib
from sklearn.model_selection import train_test_split

###############################################################################
####################### Extract the data from .csv file #######################
###############################################################################
# get data
data, column_names = dmanip.get_data(file_path='../data_one_outcome.csv')

# split data
X = data.iloc[:, :-1]
y = data.iloc[:, -1:].astype('category')

###############################################################################
########################## init global config vars ############################
###############################################################################
# check if GPU is used
print(device_lib.list_local_devices())

# init
n_epochs = 1500
n_comps = X.shape[1]

###############################################################################
################################## Keras RNN ##################################
###############################################################################
# encode the classification labels
le = LabelEncoder()
yy = to_categorical(le.fit_transform(y))

# split the dataset
x_train, x_test, y_train, y_test = train_test_split(X, yy, test_size=0.35,
                                                    random_state=True,
                                                    shuffle=True)

# exapand dimensions
x_train = np.expand_dims(x_train, axis=2)
x_test = np.expand_dims(x_test, axis=2)

# define model
model = Sequential()
model.add(LSTM(units=n_comps, return_sequences=True,
               input_shape=(x_train.shape[1], 1),
               dropout=0.2, recurrent_dropout=0.2))
model.add(LSTM(64, return_sequences=True, dropout=0.2, recurrent_dropout=0.2))
model.add(LSTM(32, dropout=0.2, recurrent_dropout=0.2))
model.add(Dense(4 ,activation='softmax'))

# print model architecture summary
print(model.summary())

# compile model
model.compile(loss='binary_crossentropy', optimizer='adam', metrics=['accuracy'])

# Create a TensorBoard instance with the path to the logs directory
tensorboard = TensorBoard(log_dir='./logs/rnn/{}'.format(time()))

# fit the model
history = model.fit(x_train, y_train, epochs=n_epochs, batch_size=100,
                    validation_data=(x_test, y_test), callbacks=[tensorboard])

# plot results
vis.plot_nn_stats(history=history, stat_type="accuracy", fname="RNN-accuracy")
vis.plot_nn_stats(history=history, stat_type="loss", fname="RNN-loss")

The resulting accuracy and loss functions are:

My data is essentially a big matrix (38607, 150), where 150 is the number of features and 38607 is the number of samples, with a target vector including 4 classes.

If I understand your problem, your samples are 150-dimensional vectors
which is to be classified into one of four categories. If so, an LSTM
architecture is a very poor fit because there are no relations
between your samples. I.e what is in the n:th sample doesn't impact
what is in the n + 1:th sample.

Try something like this instead:

from keras.layers import Dense
from keras.models import Sequential
from keras.utils import to_categorical
import numpy as np

n = 38607
d = 150
k = 4

# Generate data
X = np.random.randn(n, d)
Y = to_categorical(np.random.randint(k, size = n), k)

model = Sequential()
model.add(Dense(128, input_dim = d, activation = 'relu'))
model.add(Dense(64, activation = 'relu'))
model.add(Dense(4, activation = 'softmax'))
model.compile(
    loss = 'binary_crossentropy',
    optimizer='adam', metrics=['accuracy'])
model.summary()

model.fit(X, Y, epochs = 100, batch_size = 128, verbose = 1)

I haven't used any test data so the model quickly overfits (accuracy >
25% implies overfitting). Which brings me to my next point. On your
graphs, you get better performance on the test data than on the
training data which is very suspect. I suggest you try and train your
network without any dropout first to see if it behaves as expected
before adding it back.


HackerRank Implement Queue using two stacks Solution Challenge

Problem Statement - Implement a Queue using two Stacks

I implemented dequeue() in \$O(1)\$ at the cost of enqueue() in \$O(n)\$

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

struct Queue{
    stack<int> s1,s2;

    int dequeue(){
        int x = s1.top();
        s1.pop();
        return x;
    }

    void peek(){
        cout<< s1.top()<<"\n";
    }

    void enqueue(int data){
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }

        s1.push(data);

        while(!s2.empty()){
            s1.push(s2.top());
            s2.pop();
        }
    }
};

int main() {
    int t; cin>>t;
    Queue q;

    while(t--){
        int k; cin>>k;
        switch(k){
            case 1:
                int x; cin>>x;
                q.enqueue(x);
                break;
            case 2:
                q.dequeue();
                break;
            case 3:
                q.peek();
        }
    }
    return 0;
}

There are 15 test cases. This code runs properly for the first 5 test cases then I get a 'Time Limit Exceeded' message for the rest of test cases.

This means the complexity of my program is too much.

So I tried reversing it, I made enqueue() as \$O(1)\$ and dequeue() as \$O(n)\$ but even that did not change anything.

What should I do to reduce time complexity of this code?

Algorithmic complexity for combined operations

Containers are interesting elements in most programming languages: they have an internal state, namely their elements and therefore their size.

This introduces an additional state compared to usual algorithmic asymptotical complexity analysis. For example, a naive implemented std::vector::push_back will yield \$\mathcal O(n^2)\$ complexity if push_back increases the capacity only by one:

// pseudo-code, also very bad performance and no error handling, do not use!
void vector::push_back(T value){
    if(_size == _capacity) {
         // has to move all elements and is therefore O(n)
         reserve(_capacity + 1);
    }
    _data[_size++] = value;
}

While trivial, this code has a severe problem: we have to copy all elements in ever iteration. If we use push_back in a loop, we end up with a quadratic complexity.

The real push_back has therefore some tricks up in its sleeves, as the standard dictates that it will have \$O(1)\$ amortized complexity. More about that later in this review.

However, this small introduction should give you a hint about the central flaw in your current approach.

A hidden quadratic term

  I implemented dequeue() in \$O(1)\$ at the cost of enqueue() in \$O(n)\$

For this task, it's much more important to see the cost on both functions for \$k\$ enqueued elements, not a single one.

So let's envision the queue {1,2,3,4}. How many steps do we need?

to enqueue 1:
  1. put `1`  in `s1`
to enqueue 2:
  1. move `1` from `s1` to `s2`
  2. put `2` in `s1`
  3. move `1` from `s2` to `s1`
- to enqueue 3:
  1. move `1` from `s1` to `s2`
  2. move `2` from `s1` to `s2`
  3. put `3` in `s1`
  4. move `2` from `s2` to `s1`
  5. move `1` from `s2` to `s1`
- to enqueue 4:
  1. move `1` from `s1` to `s2`
  2. move `2` from `s1` to `s2`
  3. move `3` from `s1` to `s2`
  4. put `4` in `s1`
  5. move `3` from `s2` to `s1`
  6. move `2` from `s2` to `s1`
  7. move `1` from `s2` to `s1`

We see that the \$n\$th element will take \$2(n-1)\$ swaps. Therefore, if we insert a total of \$n\$ elements into our queue, we end up with \$\mathcal O(n^2)\$ to complete all enqueues.

We need to do better.

A better queue with two stacks

So let's get back to the drawing board. What do we need?

We need to enqueue
We need to dequeue
We need to peek.

None of those terms indicates that we need to have all data in one stack. So first of all, we need to use better names, because s1 and s2 are pretty bland and non-descriptive:

class Queue{
    stack<int> in;
    stack<int> out;

    void flip();   // < new

public:
    void enqueue(int);
    int  dequeue();
    int  peek();
};

I'll implement the methods outside of the class declaration to keep the code segments short, but you're free to place them inline again. Note that I switched from a struct to a class, because its Queues job to make sure that in and out are handled correct; no one else should be able to change them.

What will we use in and out for? Well, as long as we have elements in out, we will use them for dequeue and peek. And whatever gets enqueued gets pushed right ontop of in, no questions asked.

The critical part is how to get an element from in to out, right? I let you think about that for some paragraphs, but you may also stop here and try it yourself; the declaration above contains a clue.

So, let's have a look at my proposal for the definition of enqueue(), peek and dequeue():

void Queue::enqueue(int value) {
    in.push(value);
}

int Queue::peek() {
    if (out.empty()) {
        flip();
    }
    return out.top();
}

int Queue::dequeue() {
    if (out.empty()) {
        flip();
    }
    int value = out.top();
    out.pop();
    return value;
}

Note that the additional private method flip is yet missing. However, I will state the envisioned complexity:

enqueue is \$\mathcal O(1)\$ (amortized)
dequeue is \$\mathcal O(1)\$ (amortized)
peek is \$\mathcal O(1)\$ (amortized)

Intrigued? Great. So let's check flip:

void Queue::flip() {
    while(not in.empty()) {
        out.push(in.top());
        in.pop();
    }
}

flip takes all elements in in and moves them to out. It thereby changes the order of the elements, so that the top in in will be the last to get moved out of out. Note that we call flip only when out is empty.

Amortized analysis

*"Wait a second! That's \$\mathcal O(n)\$" I hear you say. And that's completely correct. However, how often do we need to call flip? Or, rather more important, how often do elements get moved?

The answer on the latter question is: exactly one time from in to out. At no point will they move back. The number of flip calls is much trickier, though, but it doesn't really matter. At worst, flip may need to flip all elements, for example if we use it as follows:

for(int i = 0; i < 100; ++i) {
    queue.enqueue(i);
}
for(int i = 0; i < 100; ++i) {
    queue.dequeue(); // first dequeue will flip
}

However, only the first dequeue will flip. All others will yield the element immediately. Therefore, if we enqueue \$n\$ elements and then dequeue all of them, we end up with dequeue()'s complexity as:

$$\frac{n\mathcal O(1) + \mathcal O(n)}{n} = \mathcal O(1).$$

We can compare that with your original variant:
$$\frac{n\mathcal O(n)}{n} = \mathcal O(n)$$

This is why your code exceeded the time limit.

Further review on code

There are some other findings that don't need as much detail as the algorithm, but nonetheless can be improved:

there are some unused includes (<vector>)
using namespace std is considered bad practice
the names are misleading or at least not self-descriptive
peek() usually returns a value and does not print
the struct Queue should have been a class Queue due to the assumption that the elements are always in the right order.


Sample scraping Project Gutenberg using Beautiful Soup and requests I am trying to learn web scraping in Python using Beautiful Soup and requests. My program goes to the book page on Project Gutenberg with the given book number (Example). It then finds the link for the given format (text in this case) and then writes the contents of the book to a file on the hard disk.

How and what can I improve in this code?

import requests
from bs4 import BeautifulSoup
def go_gutenberg(file_format,book_no):
       url = "https://www.gutenberg.org/ebooks/"
       r =requests.get(url+str(book_no))
       r_html  = r.text
       soup = BeautifulSoup(r_html,"html.parser")
       for file in soup.find_all('a',class_="link"):
         if file_format in file.text:
           get_book=file.get('href')
           g = requests.get("https:"+get_book)

           with open("C:\\Users\\syed\\Documents\\Gutenberg\\Book"+str(book_no)+".txt",'wb') as open_file:
               for chunk in g.iter_content(10000):
                    open_file.write(chunk)

def main():
go_gutenberg("Text",1000)

if __name__=="__main__":main()

And this is sample HTML of the book links:

Plain Text UTF-8

Easy stuff

There are a lot of stylistic issues (indentation, spacing between operators, etc.) that violate PEP 8, you can use tools like pylint to find what they are.

Moving on

 r_html = r.text

Do you really need this? You don't save any characters (not that it is always about saving characters) and you use r_html once. I would just get rid of the line.

I would also say the same about:

url = "https://www.gutenberg.org/ebooks/"

Just get rid of it. Also, in this instance in particular I would get rid of it, because when I read it, I believe there might be a way to abstract it. "Maybe let the user change the url, somehow?") There isn't a particularly good way to "abstract" this url out in particular.

Furthermore, it is considered good practice to use format instead of the addition of strings so:

"https://www.gutenberg.org/ebooks/" + str(book_no)

Becomes:

"https://www.gutenberg.org/ebooks/%d" % book_no

This on the other hand:

"C:\\Users\\syed\\Documents\\Gutenberg\\Book"

Seems like it can be abstracted, what if the user wants to change the location? Maybe by default use this location, but allow the user to change it. Create a default argument to "C:\\Users\\syed\\Documents\\Gutenberg\\Book" but give the user the option to specify it.

Same with:

for chunk in g.iter_content(10000):

What is 10000? Maybe make a default argument for this with the value of 10000 and the name of (possibly) chunk_size?


Listening from Mongodb always and triggering I am using classes for the first time. In this program I want the object to run infinitely so that any change in the MongoDB will trigger the function and do the necessary processing.

I am little confused about the using of the self. Please give me feedback on my code.Thanks!

class first_level:

    def __init__(self):

        import pymongo
        connection = pymongo.MongoClient("mongodb://localhost")

        self.test_3_dec = connection.test_3_dec
        self.test1 = self.test_3_dec.test1
        self.test2 = self.test_3_dec.test2

    def listener_function(self):

        cursor = self.test2.find({},{"check_bit":True,"_id":True})

        for bit in cursor:
            if bit["check_bit"]==0:
                self.update_function(bit["check_bit"],bit["_id"])

    def update_function(self,value,value2):

        self.test1.insert({"_id":value2,"bit":value})

        self.test2.update({"_id":value2},{"$set":{"check_bit":1}})

obj = first()

while True:
    obj.listener_function()

I'm in doubt if your code actually works as you instantiate using obj = first(), but your class is named first_level(). This kind of indicates that either you've left out code, or you have broken code.

Anyway, here are some pointers for you:

Imports should go at start of file – It's generally considere bad style to import stuff within classes or functions
The connection you create is forgotten – You should store the connection, as it is killed when __init__ is completed. You should use something like self.connection = pymongo.... If your code actually is working, then it is because the self.testXXX keeps it alive
Vertical space is good, but you've got too much – The common policy is to have two blank lines in front off functions and classes, and single lines in front of different part you want to differentiate a little from other blocks.
Increase horizontal space – After commas or colons you could benefit from adding spaces. Instead of insert({"_id":value2,"bit":value}) do insert({"_id": value2, "bit": value})
Add comments and/or docstrings – It is hard to read what your code actually does, and why it does it. This should be commented upon.
Avoid busy tight loops – Doing while True with a single function not doing much, is a tight busy loop, and should usually be avoided. At least if doing it this way, you should add a sleep somewhere to avoid hogging resources.

A better solution related to MongoDb

However instead of doing a busy loop with some code which I don't fully grasp, I believe you should look into the monitoring of the mongodb. This would allow you to get notified when commands are executed against the mongodb.

At least, that is how I read the documentation, with little knowledge of mongodb. And this pattern of adding a listener, and then waiting for it to respond is a bettern pattern rather than busy waiting and changing stuff to check if it is alive.


Centered finite difference approximation for edge enhancement I implemented a centered finite difference approximation for edge enhancement in images. The difference approximation has a step size h of the partial derivatives in the x- and y-directions of a 2D-image. However, the function that calculates the difference approximation is slow on big images.

Here is the code:

import matplotlib.pyplot as plt
from matplotlib import cm
import matplotlib
from skimage import io
import numpy as np

# read image as a numpy array
sample_img = io.imread('samlpe.png')

def findiff(image, stepsize):
    # Padding to handle the boundaries when incrementing with step size
    padded_img = np.pad(image, pad_width=1, mode='constant', constant_values=0)
    img = padded_img.astype(float)
    M, N = img.shape # Get the dimensions of the image.
    pdfx = np.zeros(shape=(M, N))
    pdfy = np.zeros(shape=(M, N))
    img_lst = []
    for x in range(M-1):
        for y in range(N-1):
            pdfx[x][y] = (img[x][y + stepsize] - img[x][y - stepsize]) / (2 * stepsize) # partial with relation to x
            pdfy[x][y] = (img[x + stepsize][y] - img[x - stepsize][y]) / (2 * stepsize) # partial with relation to y

    img_lst.append(pdfx)
    img_lst.append(pdfy)
    return img_lst

fig, img_lst = plt.subplots(1, 2)
imgs = findiff(sample_img, 1)
img_lst[0].imshow(imgs[0], cmap="gray")
img_lst[1].imshow(imgs[1], cmap="gray")
img_lst[0].set_title('pdfx')
img_lst[1].set_title('pdfy')
plt.show()

This solution works for step size=1. How can I improve this code? Can I avoid the nested loops? How can I generalize the function so that it can handle different step sizes?

I'm new to Python by the way.

I'm not yet very comfortable with Python style and so on, so I'm going to focus only on speeding up the code.

First of all, the indexing

img[x] extracts a line from the image. Then img[x][y] extracts a pixel from that line. In contrast, img[x,y] directly extracts a single pixel from the image. Thus, we can rewrite your indexing expressions reduces the amount of work to be done:

pdfx[x,y] = (img[x, y + stepsize] - img[x, y - stepsize]) / (2*stepsize) # partial with relation to x
pdfy[x,y] = (img[x + stepsize, y] - img[x - stepsize, y]) / (2*stepsize) # partial with relation to y

Let's time the difference:

import timeit
timeit.timeit("imgs = findiff(sample_img, 1)", number=30, globals=globals())

The original code gives 3.46 seconds, the code with changed indexing gives 2.37 seconds. That is a significant difference!

Next, let's remove the double loop

You should always leverage the vectorized operations in Numpy. In this case it is not difficult. The lines of code become longer, but with practice one immediately sees what is being computed. This is the modified function:

def findiff(image, stepsize):
    # Padding to handle the boundaries when incrementing with step size
    padded_img = np.pad(image, pad_width=stepsize, mode='constant', constant_values=0)
    img = padded_img.astype(float)
    pdfx = (img[stepsize:-stepsize, 2*stepsize:] - img[stepsize:-stepsize, 0:-2*stepsize]) / (2*stepsize) # partial with relation to x
    pdfy = (img[2*stepsize:, stepsize:-stepsize] - img[0:-2*stepsize, stepsize:-stepsize]) / (2*stepsize) # partial with relation to x
    img_lst = []
    img_lst.append(pdfx)
    img_lst.append(pdfy)
    return img_lst

Note the computation of pdfx and pdfy. Here we do exactly the same computations as before, but we extract an array containing all the elements that appear on the left hand side of the minus operator as you go through the original loop, and another array containing all the right hand side elements. Note that img[stepsize:-stepsize, stepsize:-stepsize] is the original image before padding (since we add stepsize pixels to each side). On the LHS we want to index pixels stepsize elements to the right, that is img[stepsize:-stepsize, (stepsize:-stepsize)+stepsize] == img[stepsize:-stepsize, 2*stepsize:]. On the RHS we want to index pixels stepsize elements to the left which we obtain in a similar way.

The modified function runs in 0.021 seconds. That is two orders of magnitude faster than the loop code!

Note that the output images now are of the same size as the input image, not of the size of the padded input image as before. This is more useful in general. But if it is desired to output images with padding then it is possible to instead do:

pdfx = np.zeros(shape=(M, N))
pdfx[stepsize:-stepsize, stepsize:-stepsize] = ...

Another change in the code above is the use of pad_width=stepsize in the call to np.pad, so that the indexing works correctly for step sizes larger than 1.


jQuery make DRY two almost identical on click function Is there a simple way to DRY this jQuery code?

  $('ul.icons li.size').click(function() {
    $('ul.icons li.size').not(this).removeClass('selected');
    $(this).toggleClass('selected');
  });

  $('ul.icons li.color').click(function() {
    $('ul.icons li.color').not(this).removeClass('selected');
    $(this).toggleClass('selected');
  });

You need to have a group selector and just use this context to have the clicked list element:

  $('ul.icons li.size, ul.icons li.color').click(function() {
      $(this).addClass('selected')      // add to clicked li
             .siblings('li')           // get all other lis
             .removeClass('selected');  // remove the class
   });


JavaScript clicker game I'm studying JavaScript and jQuery and I did an implementation of a simple cat clicker game:

class Cat {
  constructor(name, picture) {
    let self = this;

    self.name = name;
    self.picture = picture;
    self.count = 0;

    let mainDiv = $('#cats');
    let catDiv = $('

');

    mainDiv.append(catDiv);

    self.img = $(`<img src="${self.picture}">`);
    catDiv.append(self.img);

    self.counter = $('

');
    catDiv.append(self.counter);

    self.img.click(function() {
      self.count++;
      self.counter.text(`You clicked ${self.name} ${self.count} times.`);
      self.counter.css("font-size", "+=0.5");
    });
  }
}

$(document).ready(function() {
  new Cat('Kimmy', 'http://newmediarockstars.com/wp-content/uploads/2014/07/femcat.png');
  new Cat('Logan', 'http://svoctopussy.com/wp-content/uploads/2013/02/Grumpy-Cat.jpg');
});

Cat Clicker

I wanted it to be dynamic, so if I want to add more cats, I just have to instance a new object of the Cat class, like it's done in the document.ready function.

The Cat constructor adds a new cat in the HTML (it appends the cats div), using div, h1, img and p. Everytime you click the img (), the p element text is updated with the click count.

I'm a complete beginner in JS. What can I refactor here to make the code more legible and idiomatic?

EDIT: In the third line, there's a let self = this;. I did that because I needed to access the Cat instance inside the img.click callback function. I don't know if that's how it's done nor how I can improve that.

In the third line, there's a let self = this;. I did that because I needed to access the Cat instance inside the img.click callback function.

Use an arrow function, which won't rebind this. The self alias can then be removed.

this.img.click = () => {
  this.count++;
  ...
}

Your examples don't save the Cats anywhere, access any properties on them, pet them, or otherwise interact with them -- if adding a cat to the DOM is all you need, the constructor doesn't need to attach anything to this (which is equivalent to exposing things as public properties).

  The Cat constructor adds a new cat in the HTML (it appends the cats div), using div, h1, img and p.

Putting that behaviour in the constructor is not ideal. People reading your code probably expect new Cat(...) to return a cat, but not necessarily for it to put that cat somewhere. Besides being unexpected, this isn't very flexible: what if I want to put a cat somewhere else on the page?

It's probably better to separate creating the cat (and its click handler) from actually attaching it anywhere. You could add another method in the Cat class, like this:

  attach(element) {
    element.append(this.catDiv);
  }

but I think all you need in this example is a function:

function createCat(name, picture) {
  let clickCount = 0;

  const $cat = $('<div/>');    // $var is just a naming convention for jQuery variables
  const $img = $('<img/>', { src: picture }).appendTo($cat);
  const $counter = $('<p/>').appendTo($cat);

  $img.click(() => {
    clickCount++;
    $counter
      .text(`You clicked ${name} ${clickCount} times.`)
      .css("font-size", "+=0.5");    // Most jQuery methods can be chained
  });

  return $cat;    // return the cat div, not yet attached to the DOM
}

$(function() {    // equivalent to $(document).ready(function() {
  const $main = $('#cats');

  $main.append(createCat('Kimmy', 'http://newmediarockstars.com/wp-content/uploads/2014/07/femcat.png'));
  $main.append(createCat('Logan', 'http://svoctopussy.com/wp-content/uploads/2013/02/Grumpy-Cat.jpg'));
});


Print matrix in spiral order I have a task formulated like this

  Please print a matrix in spiral order, clockwise from outer rings to inner rings.

I decided to implement it in Clojure.

(def matrix '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)))

(def big-matrix '(
    ( 1   2  3  4  5  6  7  8  9 )
    ( 32 33 34 35 36 37 38 39 10 )
    ( 31 56 57 58 59 60 61 40 11 )
    ( 30 55 72 73 74 75 62 41 12 )
    ( 29 54 71 80 81 76 63 42 13 )
    ( 28 53 70 79 78 77 64 43 14 )
    ( 27 52 69 68 67 66 65 44 15 )
    ( 26 51 50 49 48 47 46 45 16 )
    ( 25 24 23 22 21 20 19 18 17 ))
)

(defn get-str
  ([] "")
  ([a] a)
  ([a b] (str a " " b)))

(defn print-first-row [matrix] (reduce get-str (first matrix)))
(defn print-last-elements [matrix] (reduce get-str (map last matrix)))
(defn print-last-row-reversed [matrix] (reduce get-str (reverse (last matrix))))
(defn print-first-elements-reversed [matrix] (reduce get-str (reverse (map first matrix))))

(defn spiral (
    [matrix]
      (spiral matrix :first-row)
  )(
    [matrix op]
      (if (not (empty? matrix))
      (cond
        (= op :first-row) (str (print-first-row matrix) " " (spiral (rest matrix) :last-els))
        (= op :last-els)  (str (print-last-elements matrix) " " (spiral (map butlast matrix) :last-row))
        (= op :last-row)  (str (print-last-row-reversed matrix) " " (spiral (butlast matrix) :first-els))
        (= op :first-els) (str (print-first-elements-reversed matrix) " " (spiral (map rest matrix) :first-row)))
      )
  )
)

(spiral matrix)
(spiral big-matrix)
(spiral '())

Output:

For the first matrix the function call (spiral matrix) returns string "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 "

The task itself is pretty simple but I am pretty new to Clojure so I would like to hear any possible improvements for this code. Thanks!

First, some style notes:

When defining a sequential piece of data, it's conventional to use a vector instead of a list:

(def matrix [[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16]])

This avoids having to write those pesky 's.
It's conventional to leave no whitespace between an opening bracket and its first contained element, and similarly between a closing bracket and its last contained element:

(def big-matrix
  [[1 2 3 4 5 6 7 8 9]
   [32 33 34 35 36 37 38 39 10]
   [31 56 57 58 59 60 61 40 11]
   [30 55 72 73 74 75 62 41 12]
   [29 54 71 80 81 76 63 42 13]
   [28 53 70 79 78 77 64 43 14]
   [27 52 69 68 67 66 65 44 15]
   [26 51 50 49 48 47 46 45 16]
   [25 24 23 22 21 20 19 18 17]])

If you think it's more readable, though, you could align the single-digit numbers in the first row with the double-digit numbers in the other rows (as you did in your question):

[ 1  2  3  4  5  6  7  8  9]

It's conventional to indent the function body the same amount as the argument vector in multi-arity functions, and to indent the "then" part of an if expression by two spaces. If you don't have an "else" expression, it's conventional to use when instead of if.

Also, it's conventional to use the idiom (seq ,,,) instead of the more verbose (not (empty? ,,,)) and to use case instead of cond when you're comparing a value to several constants:

(defn spiral
  ([matrix]
   (spiral matrix :first-row))
  ([matrix op]
   (when (seq matrix)
     (case op
       :first-row (str (print-first-row matrix) " " (spiral (rest matrix) :last-els))
       :last-els  (str (print-last-elements matrix) " " (spiral (map butlast matrix) :last-row))
       :last-row  (str (print-last-row-reversed matrix) " " (spiral (butlast matrix) :first-els))
       :first-els (str (print-first-elements-reversed matrix) " " (spiral (map rest matrix) :first-row))))))

Your approach of converting everything to strings as early as possible and then implementing your logic as string concatenation causes a lot of verbosity in your code. I would instead try to work with richer data (sequences of numbers, in this case) as much as possible:

(defn first-row [matrix] (first matrix))
(defn last-elements [matrix] (map last matrix))
(defn last-row-reversed [matrix] (reverse (last matrix)))
(defn first-elements-reversed [matrix] (reverse (map first matrix)))

(defn drop-first-row [matrix] (rest matrix))
(defn drop-last-elements [matrix] (map butlast matrix))
(defn drop-last-row [matrix] (butlast matrix))
(defn drop-first-elements [matrix] (map rest matrix))

(defn spiral
  ([matrix]
   (spiral matrix :first-row))
  ([matrix op]
   (when (seq matrix)
     (case op
       :first-row (concat (first-row matrix)
                          (spiral (drop-first-row matrix) :last-els))
       :last-els  (concat (last-elements matrix)
                          (spiral (drop-last-elements matrix) :last-row))
       :last-row  (concat (last-row-reversed matrix)
                          (spiral (drop-last-row matrix) :first-els))
       :first-els (concat (first-elements-reversed matrix)
                          (spiral (drop-first-elements matrix) :first-row))))))

Then you can use clojure.string/join to convert to a string as the last step:

(require '[clojure.string :as str])

(str/join " " (spiral matrix))
;=> "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10"

This solution still has a lot of repetition, though; you basically have four of everything, one for each direction of the spiral. You could eliminate this repetition by just taking the top row each iteration, then rotating the rest of the matrix by an angle of \$\tau/4\$ counterclockwise.

So first you need a function to perform that sort of rotation. To visualize the algorithm I'm going to use, get a square physical object and hold it in front of you. Rotate it by an angle of \$\tau/2\$ around the axis passing through its top-left corner and its bottom-right corner. Then rotate it by an angle of \$\tau/2\$ around the axis passing through the midpoints of its left and right sides. You should see that this is equivalent to rotating the object by an angle of \$\tau/4\$ counterclockwise around the axis perpendicular to its surface.

Coming back to matrices, that first rotation is just transposing the matrix, and the second rotation is just reversing the order of its rows. Clojure has a built-in reverse function, and you could write a transpose function yourself, but there's already one available in core.matrix, so I'm just going to use that. Add the library to your dependencies:

[net.mikera/core.matrix "0.52.1"]

The transpose function is in the clojure.core.matrix namespace:

(require '[clojure.core.matrix :as m])

And now we can write our rotate function easily:

(defn rotate [matrix]
  (reverse (m/transpose matrix)))

Now that all the pieces in place, we can write our spiral function. If the matrix is empty ((seq matrix) returns nil), we just return nil. Otherwise, the spiral sequence of the matrix is equal to the concatenation of the first row of the matrix with the spiral of the rotation of the rest of the matrix:

(defn spiral [matrix]
  (when (seq matrix) (concat (first matrix) (-> matrix rest rotate spiral))))

I'm using the thread-first macro -> here because I think it makes it easier to read. Sanity check:

(str/join " " (spiral matrix))
;=> "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10"


Solving maze problem with backtracking solution using stack I solved the maze backtracking question using a stack however could not find any other solution like that anywhere (to validate my solution is actually a valid one).
The problem statement is as follows -

  Imagine a robot sitting on the upper left corner of grid with r rows
  and c columns. The robot can only move right or down but certain cells
  are "off limit" such that the robot cannot step on them. design an
  algorithm to find a path for the robot from the top left to the bottom
  right

My Solution (java) is as follows -

public static boolean solve(boolean[][] maze) {
        int maxY = maze.length-1;
        int maxX = maze[0].length-1;
        int[] end = new int[]{maxY, maxX};
        int[] currentPosition = new int[]{0, 0};
        Stack<int[]> lastPosition = new Stack<>();
        lastPosition.push(currentPosition);
        while ( (currentPosition[0] != end[0] || currentPosition[1] != end[1])
                && !lastPosition.isEmpty()) {
            // get current position coordinates
            int y = currentPosition[0];
            int x = currentPosition[1];

            // Try moving right
            if(x+1 <= maxX && maze[y][x+1]) {
                currentPosition = new int[]{y,x+1}; // Move one step right
                lastPosition.push(currentPosition);
            } else if(y+1 <= maxY && maze[y+1][x]) { // Try moving down
                currentPosition = new int[]{y+1,x}; // Move one step down
                lastPosition.push(currentPosition);
            } else {
                maze[y][x] = false; // Mark as dead end (so we will not try to reach here again)
                currentPosition = lastPosition.pop();
            }
        }

        return !lastPosition.isEmpty();
    }

It looks like it works well (I tested it against several mazes to make sure), it should also run in O(rc) time at worst case (which is fine for the a maze of rc size) but everything else I've seen uses recursion or other methods to solve this problem. Am I missing something?

Will appreciate any kind of guidance.

Your solution looks correct. Your don't need to find a similar implementation to validate yours. You just need to verify yours works correctly, by stepping through the logic as if with a debugger, and verifying all execution paths, and considering all possible corner cases.

By the way, recursive solutions use a stack too, just implicitly. They take advantage of the function call stack, which stores the program state every time you step into a function, and pops it when leaving a function, returning to the caller. Manually implementing a stack based solution is typically less convenient, but more powerful and efficient, because you have full control over the stack and its entries, which can be perfectly sized.

Although your solution works, I would write it slightly differently:

The logic would be slightly easier to understand if all the conditions of the movement were organized in the same if-else chain inside the loop
Instead of adding the next position to the stack, it's more conventional to add the current one
The Stack class is no longer recommended in Java, use Deque and ArrayDeque instead
Instead of int[] end = new int[]{maxY, maxX};, a shorter more convenient form exists: int[] end = {maxY, maxX};. (Unfortunately this form works only at initialization, it doesn't work for assignment in general.)
It's more natural to store coordinates as (x, y) pair instead of (y, x) pair

Like this:

public static boolean solve(boolean[][] maze) {
    int maxY = maze.length - 1;
    int maxX = maze[0].length - 1;

    Deque<int[]> stack = new ArrayDeque<>();
    int x = 0;
    int y = 0;

    while (true) {
        if (x == maxX && y == maxY) {
            // Found the exit!
            return true;
        } else if (x + 1 <= maxX && maze[y][x + 1]) {
            // Try moving right
            stack.push(new int[]{x + 1, y});
            x++;
        } else if (y + 1 <= maxY && maze[y + 1][x]) {
            // Try moving down
            stack.push(new int[]{x, y + 1});
            y++;
        } else if (!stack.isEmpty()) {
            // Mark as dead end (so we will not try to reach here again)
            maze[y][x] = false;
            int[] current = stack.pop();
            x = current[0];
            y = current[1];
        } else {
            // No way to go -> impossible to reach the exit
            return false;
        }
    }
}


Implementing 3Blue1Brown's description of Fourier transform in Python+numpy I have implemented the 3Blue1Brown's description of Fourier transform in Python+numpy for irregular and unsorted data, as described here.

import numpy as np
import matplotlib.pyplot as plt

def polarToRectangular(radii, angles):
    return radii * np.exp(1j * angles)

def frequencyGenerator(time, steps = 100):
     = time.max() - time.min()
    M = np.arange(1, steps + 1)[:, np.newaxis]
    return M /

def easyFourierTransform(time, values, frequency = None, steps = 100):
    if frequency is None:
        ft = frequencyGenerator(time, steps)
        frequency = ft.reshape(ft.shape[0])
    else:
        ft = frequency[:, np.newaxis]

    # sorting the inputs
    order = np.argsort(time)
    ts = np.array(time)[order]
    Xs = np.array(values)[order]

     = (ts - time.min()) * 2 * np.pi * ft
    Y = polarToRectangular(Xs, )[:, :-1] * np.diff(ts)
    amplitude = np.abs(Y.sum(axis=1))
    return frequency, amplitude

I'm thinking maybe I can suggest this to be added to numpy/scypy. However, I'm not sure if this small piece of code is qualified to be added upstream. I was wondering if you could help me know:

Is this code correct? Does it actually return the Fourier transform? I want to be sure there are no logical errors.
Is this a performant code or there is any way to improve performance?
Is the formating good enough? Should I comply with PEP8 standard or numpy/scipy require different best practices?
Is this novel or it has been done before? (not necessarily relevant to this forum but still my question)

Keywords: nonuniform, uniformly, unevenly, sampled, distributed

P.S. Updated version of the code plus examples in this Jupyter notebook.

As I already mentioned in a comment below your question, scipy has contribution guidelines that tell you what they expect from your code before even thinking about including it into scipy. The major keywords are:

Unit tests
Documentation
Code style

Testing

The first point of this list would also help you to answer your question about the algorithm's correctness automatically. This answers to What data should I use to test an FFT implementation, and what accuracy should I expect? on the Signal Processing Stack Exchange can help you to get an idea on how that might look like. The documentation of the relevant functions (e.g. numpy.fft.fft) in the scipy stack and their associated tests can provide further hints. Since my knowledge on FT, DFT, FFT, WTF (;-) ), and the likes is a bit "rusty", you maybe have to look for ressources more appropriately matching what you intend to do.

Documentation

The documentation part is comparatevely simple. Again, there are guidelines on how to document code associated with the scientific Python stack (everything surrounding numpy/scipy). An example:

def polar_to_complex(radii, angles):
    """Return r-phi coordinates to complex numbers

    Parameters
    ----------
    radii, angles: array_like
        radial and angular component of the polar coordinates. Both input have
        to have the same shape

    Returns
    -------
    out: ndarray
        complex representation of the given r-phi coordinates
    """
    return radii * np.exp(1j * angles)

This is also commonly called numpydoc oder NumPy-style documentation. It's a very feature rich style and I highly recommend to have a look at the ressource linked above to learn more.

Regarding type annotations: they are just that, annotations or hints. They are not checked during runtime, i.e. the Python interpreter does not care about your carefully crafted type hints. Static code analysis tools like mypy and pylint are the tools that would make use of them to tell you about flaws that can be checked without actually running your code, hence the name "static code analysis". If you really want to make sure that all the inputs are how you expect them to be, you will have to write your own validation code raising appropriate exceptions at runtime to tell whoever uses your library incorrectly that they're doing so.

Style

The contribution guidelines clearly describe that your code is supposed to conform to PEP 8 conventions. There is also a hint to use automatic tooling in order to check your code in that regard. In case you don't like there suggestion on what tool to use, fear not! This answer on Code Review meta lists quite a few other tools that can help you in your endeavours to write beautiful Python code. Among others, they should tell you to use lower_case_with_underscore names for function and variable names, avoid whitespace around = when used in keyword-arguments, and that there should be two blank lines between functions at the module level.

Performance

I have not actively checked the performance of your implementation compared to what's already implemented in numpy/scipy, but from my experience and since Fourier transformations are a very widely used tool, I highly suspect that such a simple implementation will be no match for current state-of-the-art implementations likely present in numpy/scipy. As I said, I did not check, so I might be wrong here.

If I were to guess, sorting is likely the single most costly operation in your algorithm, but again I have not measured it. If you are willing to look into this, cProfile and timeit are likely the modules to look at.


Does my Game class have too many responsibilities? I've been working on a game so as to fill out something that I can put on a CV and I was writing the main Game class. This shouldn't be a god class, but it should simply be a class that ties together the "wiring" of the game, i.e, it should start listening for input events and should start the game loop and wire any inputs to the associated handlers.

/**
 * The main class for the Game.
 * This class should start the game loop as well as display updates.
 * @author Dan
 *
 */
public class Game implements Disposable {
    private final DisplayWindow _display;
    private final Disposable _displayUpdates;
    private final Scheduler _scheduler;

    /**
     * Create the Game.
     * @param displayService - the service to use for the Display
     * @param width - the initial width of the display
     * @param height - the initial height of the display
     */
    public Game(Scheduler gameScheduler, DisplayWindow displayWindow) {
        _display = displayWindow;
        _scheduler = gameScheduler;

        // Wait for the display to open correctly
        try {
            if(!_display.isOpen().get(500, TimeUnit.MILLISECONDS)) {
                System.err.println("failed to initialize OpenGL display!");
                System.exit(2);
            }
        } catch (Exception e) {
            System.err.println("OpenGL took too long to respond!");
            e.printStackTrace(System.err);
            System.exit(1);
        }

        // schedule display to update @ 60 fps
        int frameInterval = (int) ((1f / displayWindow.getTargetFramesPerSecond()) * 1000f);
        _displayUpdates = _scheduler.schedule(() -> displayWindow.update(), frameInterval);

    }

    public void startGameLoop() throws InterruptedException {
        while(true) {

            // Check to see if the window is closed
            // Bear in mind it's OK to wait here because
            // if it takes way too long we can assume that
            // openGL has stopped responding
            try {
                if(_display.isClosing().get(500, TimeUnit.MILLISECONDS)) {
                    break;
                }
            } catch (Exception e) {
                // Terminate
                System.err.println("OpenGL took too long to respond!");
                e.printStackTrace(System.err);
                System.exit(1);
            }
            Thread.sleep(1);
        }
    }

    public void dispose() {
        _display.dispose();
        _displayUpdates.dispose();
    }
}

Here are a few signatures you might want to know while reviewing:

Future<bool> _display.isOpen()
Future<bool> _display.isClosing()
Disposable _scheduler.schedule(...)

Obviously the while(true) { Thread.sleep(1); } needs some changing so it actually has a legitimate timestep.

I just wanted to get this out of the way before writing an entire application based on this class doing the functionality it does.

I like to trash people when their classes do too many things.  I was disappointed when I saw your class because it is not so bad.

However, I don't think this class should check if the display did open.  You should only create the Game once you know that the display is ready.

I'm not sure Game is an appropriate class name.

Naming member variables starting with an underscore comes from some other language; it is not standard Java.

You write too many comments.  Let the code speak for itself and you won't have to worry about keeping the code and the comments in sync.

The comment at the beginning at the class is clearly deprecated.
// schedule display to update @ 60 fps might not be true.


Merge Sort in Java with Test cases I've become a bit rusty in Java. This is an attempt at brushing up my skills.

  In computer science, merge sort is an efficient, general-purpose,
  comparison-based sorting algorithm.

Questions

How can I improve my test cases? (TestNG)
I've used Java-11 here, can I use better idioms?
Can this implementation improved for performance?
Can style / readability improved?

Code

Sorting.java

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;

public class Sorting {

    /**
     * Day 08 - Merge Sort
     *
     * @param data       data array
     * @param comparator comparator of given data type
     * @param ascending  sort order
     * @param <T>        data type
     * @return sorted array (in place)
     */
    public static <T> T[] mergeSort(T[] data, Comparator<T> comparator, boolean ascending) {
        Objects.requireNonNull(data);
        Objects.requireNonNull(comparator);
        if (data.length <= 1) return data;
        var actualComparator = ascending ? comparator : comparator.reversed();
        return mergeSort(data, actualComparator, 0, data.length - 1);
    }

    private static <T> T[] mergeSort(T[] data, Comparator<T> comparator, int start, int stop) {
        if (start >= stop) return data;
        int pivot = start + (stop - start) / 2;
        mergeSort(data, comparator, start, pivot);
        mergeSort(data, comparator, pivot + 1, stop);
        return merge(data, comparator, start, pivot, stop);
    }

    private static <T> T[] merge(T[] data, Comparator<T> comparator, int start, int pivot, int stop) {
        T[] left = Arrays.copyOfRange(data, start, pivot + 1);
        T[] right = Arrays.copyOfRange(data, pivot + 1, stop + 1);
        int lPos = 0;
        int rPos = 0;
        int pos = start;
        while (lPos < left.length && rPos < right.length) {
            if (comparator.compare(left[lPos], right[rPos]) <= 0) {
                data[pos++] = left[lPos++];
            } else {
                data[pos++] = right[rPos++];
            }
        }
        while (lPos < left.length) {
            data[pos++] = left[lPos++];
        }
        while (rPos < right.length) {
            data[pos++] = right[rPos++];
        }
        return data;
    }
}

TestMergeSorting.java

import org.testng.Assert;
import org.testng.annotations.Test;

public class TestMergeSorting {
    @Test
    public void testMergeSort() {
        Assert.assertEquals(asc(6, 5, 9, 3, 2, 1), ar(1, 2, 3, 5, 6, 9));
        Assert.assertEquals(asc(1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 2));
        Assert.assertEquals(asc(2, 1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 2, 2));
        Assert.assertEquals(asc(1, 1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 1, 2));
        Assert.assertEquals(asc(3, 2, 1), ar(1, 2, 3));
        Assert.assertEquals(asc(1, 2, 3), ar(1, 2, 3));
        Assert.assertEquals(asc(2, 0, -1, 2, 1), ar(-1, 0, 1, 2, 2));

        Assert.assertEquals(dsc(1, 2, 3), ar(3, 2, 1));
        Assert.assertEquals(dsc(3, 2, 1), ar(3, 2, 1));
        Assert.assertEquals(dsc(2, 0, -1, 2, 1), ar(2, 2, 1, 0, -1));

        Assert.assertEquals(asc(2, 1), ar(1, 2));
        Assert.assertEquals(asc(1), ar(1));
        Assert.assertEquals(asc(), ar());
        Assert.assertEquals(dsc(1), ar(1));
        Assert.assertEquals(dsc(), ar());
    }

    @Test(expectedExceptions = {NullPointerException.class})
    public void testNullExcept() {
        Sorting.mergeSort(null, Integer::compare, true);
    }

    private static Integer[] ar(Integer... objects) {
        return objects;
    }

    private static Integer[] asc(Integer... objects) {
        return Sorting.mergeSort(objects, Integer::compare, true);
    }

    private static Integer[] dsc(Integer... objects) {
        return Sorting.mergeSort(objects, Integer::compare, false);
    }
}

One thing I noticed, the sorting routine is modifying the array and returning the array.  I would suggest either make the functions void or create a new array to do the merge in.  A sort function with a void return type automatically tells the user that the sort is in place.  Where as, a return type of an array, tells the user that a new array is created, but that the original array isn't touched.


Operator overloading for Boost interval (vectors) I am a complete newbie to C++ and programming in general. I need to write something for scientific purposes and as such, performance is crucial.

I introduced two types, matrices and vectors with intervals as entries, and now want to make them "able to work with", i.e. define basic operations. The type definitions:

#include <eigen3/Eigen/Dense>
#include <boost/numeric/interval.hpp>

namespace bn = boost::numeric;
namespace bi = bn::interval_lib;

// Interval typedefs
using Interval = bn::interval<
        double,
        bi::policies<
            bi::save_state<bi::rounded_transc_std<double> >,
            bi::checking_base<double>
        >
    >;

using Matrix = Eigen::Matrix<Interval, 3, 3>;
using Vector = Eigen::Matrix<Interval, 3, 1>;

Luckily, matrix products work without extra definitions (although I need to call a.lazyProduct(b), otherwise I receive an "operator unambiguous" error, which I don't understand), but inner products and multiplications with constants do not. It seems that I have to manually overload the multiplications, which I did as follows:

Vector operator* (const double& x, const Vector& y)
  {
  Vector res;
  for(int i = 0; i<3;i++) {
    res[i] = x*y[i];
  }
  return res;
  }

Matrix operator* (const double& x, const Matrix& y)
  {
  Matrix res;
  for(int i = 0; i<3; i++) {
    for(int j = 0; j<3; j++){
      res(i,j) = x* y(i,j);
    }
  }
  return res;
  }

Interval inner_prod(const Vector& x, const Vector& y){
  Interval res(0.0);
  for(int i = 0; i<3; i++){
    res += x[i]*y[i];
  }
  return res;
}

Interval inner_prod(const std::vector<double>& x, const Vector& y){
  Interval res(0.0);
  for(int i = 0; i<3; i++){
    res += x[i] * y[i];
  }
  return res;
}

sizes are hard-coded as I will not be working with any others. I would love to have some feedback and improvement suggestions that focus on performance. Also for the inner product, I was hoping there was a way to make use of std::inner_product for possible better performance, but I can't figure out how.

The boost/numeric/interval.hpp header gives a definition for multiplication of intervals with scalars, I must have made some mistake before that this didn't work. That just leaves my custom types.

I'll start by saying I haven't used boost::numeric, so what I say here is based on a quick skim of its documentation and source.

Instead of writing the constant 3 in so much of the code, we should be using rows() or cols() as appropriate (or perhaps even RowsAtCompileTime and ColsAtCompileTime).

Don't pass simple value types by reference - double values should be simply passed by value.

In fact, since Eigen::Matrix has a member that multiplies by a scalar, we can simplify these functions by simply calling that.  All we have to do is swap the argument order:

Vector operator*(double x, Vector y)
{
    return y *= x;
}

Matrix operator*(double x, const Matrix& y)
{
    return y * x;
}

We can also simplify the dot-product function by using the standard inner_product algorithm.  We need to know that a vector's start and end iterators are obtained by data() and data() + size() respectively:

#include <numeric>

Interval inner_prod(const Vector& x, const Vector& y)
{
    return std::inner_product(x.data(), x.data() + x.size(),
                              y.data(), Interval{});
}

Interval inner_prod(const std::vector<double>& x, const Vector& y)
{
    if (x.size() != y.size())
        return {};              // or throw an exception, or something
    return std::inner_product(x.begin(), x.end(),
                              y.data(), Interval{});
}


PHP Dictionary class accepting objects as keys I started creating a Dictionary class that accepts objects as there keys:

class Dictionary
    implements ArrayAccess
{
    private $_keys = array();

    private $_values = array();

    public function offsetExists( $key )
    {
        return false !== array_search( $key, $this->_keys, true );
    }

    public function offsetGet( $key )
    {
        if( false === ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            throw new OutOfBoundsException( 'Invalid dictionary key' );
        }

        if( !isset( $this->_values[ $index ] ) )
        {
            throw new LogicException( 'No matching value found for dictionary key' );
        }

        return $this->_values[ $index ];
    }

    public function offsetSet( $key, $value )
    {
        if( false !== ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            $this->_values[ $index ] = $value;
        }
        else
        {
            $this->_keys[] = $key;
            $this->_values[] = $value;
        }
    }

    public function offsetUnset( $key )
    {
        if( false === ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            throw new OutOfBoundsException( 'Invalid dictionary key' );
        }

        if( !isset( $this->_values[ $index ] ) )
        {
            throw new LogicException( 'No matching value found for dictionary key' );
        }

        array_splice( $this->_keys, $index, 1 );
        array_splice( $this->_values, $index, 1 );
    }
}

It works pretty well for the very elementary test cases I've done so far. However, I'm worried about three things:

Can you think of a situation where $this->_keys and $this->_values will not be synchronized with each other anymore, thus leading to data corruption? I thought maybe there could occur a situation where something might happen between the two array_splices, for instance, in:

public function offsetUnset( $key )
{
    ...

    array_splice( $this->_keys, $index, 1 );
    array_splice( $this->_values, $index, 1 );

... leading to data corruption.
I feel array_search() might be inefficient, but I specifically don't want to resort to using spl_object_hash() as keys (and thereby circumventing the need for an internal keys and values array) as I belief this is not bulletproof, as it doesn't guarantee hash uniqueness for objects at all.
I feel array_splice() might be inefficient, but I don't want to resort to unset() as I feel this could lead to unwieldy internal arrays keys eventually. I'd like to keep the internal arrays keys as tightly packed as possible.

Looking forward to your feedback.

First, I do have to say that you look like you are re-inventing the wheel. You can get all of that with SplObjectStorage. Since you're using OutOfBoundsException, you're already using the Spl types.

To your specific questions:

It is hard to think of such a situation, but that doesn't mean that it is inconceivable.
While spl_object_hash is not guaranteed unique, it is highly likely that you will run out of memory far before encountering a hash collision. As the documents state: A string that is unique for each currently existing object and is always the same for each object. It is both faster and cheaper than keeping/maintaining your own internal state.
Yes, the internal keys will not be quite as ordered in the internal arrays, but it will only make a substantial difference if you actually have a problem keeping the two arrays synced — basically, if you can get #1 to work consistently and without fail, then unset will not matter here.