One-shot events in C# I have a class that performs some long-running operation.

This class exposes a Completed event. I'd like clients that use this class to register to get notified ONLY ONCE when the class completes doing its operation.

Would you consider this code appropriate to handle this case:

public class TutorialController
{
    public event Action Complete;

    protected void OnComplete()
    {
        if (Complete != null)
        {
            Complete();
        }

        // Reset to null.
        Complete = null;
    }
}

The usage of "client" code is:

TutorialController controller = new TutorialController();
controller.Complete += ... // Register to get notified.

// Once this is done, it will raise Complete() and clear it.
controller.DoLongOperation();

Due to the current design, the Complete event actually triggers another callback that is passed from the outside:

public void SomeMethod(Action action)
{
    // Code similar to this.
    controller.Complete += () => { action(); };
}

The action passed in is ONLY RELEVANT for the current invocation of the controller, that is - after it would run and complete once, it's no longer needed to notify me of this event (with the current "action" parameter). The next invocation will pass its own action, and so on.

Note that the event sender is an object that is kept around throughout the lifetime of the app, otherwise it would be collected and each time I would get a new copy and register on its event.

Other answers are great, but this is really re-inventing the wheel. What you are looking for is the observer pattern. .NET has great in-built capabilities with observer through System.Observer<T> and System.Observable<T>. You can also get the library Rx-Main through NuGet to gain the ability to compose these, LINQ-style, into operations that can be filtered or exploded or modified as you see fit.

In .NET's Observable<T>, the Observable<T> produces values once it is subscribed to (unless it is a hot observable - that's out of scope of this answer). It will then send an OnComplete 'message' to the subscribed Observer<T> when it has finished. It also has the ability to send an OnError(Exception) notification to the Observer, but only if the exception occurs during the subscription. Exceptions during observation are not implicitly caught.

Before we get onto that, it's worth nothing that you also have Task<T>. It's really worth realizing what you are trying to do here. I feel that putting a Completed event on your class is a code smell as it's breaking encapsulation, and you should really bind the completion to the lifecycle of the method invocation (i.e, make it a return). Semantically speaking, if your method will only produce one result (i.e, "I've finished"), then you should return a Task (or Task<T>). This lets users use async/await.

If your method is going to have a sequence of results before finishing (i.e, it's got an IEnumerable perhaps?) then you should return an IObservable<T>.

Here's how I would lay it out in both cases.

public class TutorialController
{
    public async Task DoLongOperation()
    {
        return Task.Run(() => ....);
    }
}

Task.Factory.StartNew(controller.DoLongOperation()).ContinueWith(() => ...);

Replace the ellipsis with the rest of your DoLongOperation method's code. If your DoLongOperation needs to return a single result, change the return to a Task<T>. By the way, you should only use Task.Run if your long operation is CPU-bound or partially IO/CPU bound.

If your DoLongOperation returns multiple results - for example, it's getting a list of things from an external resource such as a web resource - you should instead return IObservable<T>. With ReactiveExtensions, the asynchronous composition is very useful and makes IObservable<T> better than Task<IEnumerable<T>> in this case.

public class TutorialController
{
    public IObservable<T> DoLongOperation()
    {

        return Observable.Create(() => ...);
    }
}

var results = Observable.Subscribe(p => OnNext(p), e => OnException(e), () => OnCompleted());

IObservable<T> leaves the a/synchronous nature of the call up to the caller, so you don't need async on this method.

If you provide the rest of your code for your DoLongOperation I can help convert it to IObservable. But really, the code you have right now seems like a hugeeee code smell. For one, it's mutable, and it's DEFINITELY not thread safe.

By the way one guarantee this code gives you over say @Memleak's answer is that you can invoke Subscribe on a completed Observable and no exceptions will be thrown there is no opportunity for side-effects, which is key in asynchrony. This is infinitely better than having two separate units of functionality in a single function based on whether something has already been Disposed/Completed or not. This adheres to the idea that disposables should fail silently if they have already been disposed of.

As @Jeroen rightly mentioned in chat, .NET events are an implementation of the observer pattern. But Rx's IObservable / TPL's Task allows you to compose asynchronous events and has a notion of completeness - .NET events do not. This is more useful for your use case.


Solving Subset-Product in Python I've written a python script that solves a restricted variant of Subset Product by using integer factorization. The purpose of the script is for my empirical observations of the similarities between factorization and the NP-complete problem.

The code compares two sets (or lists) from the original input arr and the factor list res. Because of the comparison, it is able to find the divisors and multiply them to see if they arrive to the target product.

Before using the code be aware that input must be positive integers only.

print('Solves restricted Subset Product')
print('Where only non-repeating integers exist in list')
print('Subset Product Solver')
arr = list(map(int, input('Enter numbers WITH SPACES: ').split(' ')))
print('enter your target integer: ')
target = int(input())

# Here I am using the same algorithm
# for integer factorization for a
# restricted variant of subset product

res = [];
for i in range(1, target+1):
  if target % i == 0:
    res.append(i)

compare_sets = set(res) & set(arr)

# These lines of code multiply all elements
# in compare_sets.

def multiplyList(compare_sets) :

    # Multiply elements one by one
    result = 1
    for x in compare_sets:
         result = result * x
    return result

# Driver code

k = multiplyList(compare_sets)

# This loop is intended to comb through the
# compare_sets list. To make sure I don't go
# over and miss the target integer

for i in compare_sets:
    if k / i == target:
      if len(compare_sets) > 1:
        compare_sets.remove(i)
        print('yes, a subset product exists')
        print(compare_sets)
        quit()

if k == target:
 if len(compare_sets) > 1:
  print('yes, a subset product exists')
  print(set(res) & set(arr))
  quit()
else:
  print('no')
  quit()

print('no')

Question

Are my variable names funky and should be re-written?
 What part of the code is the worst in terms of time complexity (ignoring factoring)?
What more efficient "pythonic" methods can I use to improve the code?

res = [];
for i in range(1, target+1):
  if target % i == 0:
    res.append(i)

This has a couple notable things. First, Python doesn't use semi-colons in the vast majority of cases. They aren't necessary. Also, whenever you have a loop whose only purpose is to create a list, you'll likely want a list comprehension instead:

res = [i for i in range(1, target + 1) if target % i == 0]

Whatever is on the left end (i in this case) gets appended to a new list. It can also be "guarded" using an if on the right end. Once you get used to seeing this syntax, it tends to read really nicely.

I also wouldn't write target+1 without any spaces. PEP8 recommends one space on each side of a binary operator unless you have a good reason to omit them.

result = 1
for x in compare_sets:
     result = result * x
return result

The line in the loop could make use of a compound-assignment operator to be more terse:

result *= x

This loop though is just carrying out a transformation of an "accumulator" (result). This is the ideal case for reduce:

from operator import mul
from functools import reduce

result = reduce(mul, compare_sets)

reduce is a function from Functional Programming. It and map are the standard ways of working with lists at a low level in FP. Python decided to tuck it away in functools, but it's a very useful function. And mul is just:

def mul(a, b):
    "Same as a * b."
    return a * b

operator contains many similar "first order" versions of operators for cases like this.

I wouldn't have top-level code like you do here. If you try to load this file by importing it or opening it in a REPL, the whole thing is forced to run, even if you just wanted to use or test a single function. Everything that isn't a function or constant definition should ideally be tucked away inside a main. That way you can control when the code is executed. I'd also be hesitant to call quit here. That also makes code harder to work with. Again, if you have this open in a REPL, quit will kill the REPL. I'd just change those quits to returns once this is inside a main.

And your naming isn't too bad. I would use much more descriptive names than i and k though unless those are straight from the equations involved (and even then description always helps).


Printing all primes < 1,000,000 to a text file It takes a long time to execute and the CPU usage for the executable is about 25% while it is executing. Any ideas on how to make this faster?

primes.c:

#include <stdio.h>
#include "primes.h"

/* COUNT will be how many numbers to
 * check and see if they are prime */
#define COUNT 1000000

int main(void)
{
  FILE *ftp;
  /* open the file for writing*/
  ftp = fopen("primes.txt", "w");

  printPrimes(ftp, COUNT);
  return 0;
}

primes.h:

#include <stdbool.h>

bool isPrime(int number)
{
  int i;
  for (i = 1; i <= number; i++)
  {
    /* if i is not 1 and i is not the number itself,
     * ...then, check to see if the number divided
     * by i has a remainder of 0 */

    /* If the number divided by i (i != 1 or itself
     * has a remainder of zero, return false
     * (the number is NOT prime */

    if (i != 1 && i != number && (number % i == 0))
    {
      return false;
    }

  }
    /* If number is NOT found to be NOT prime, return true */
      return true;
}

void printPrimes(FILE *ftp, int count)
{
  int number;
  /* is the prime number, the first prime, second, etc
   * that is the value the places variable holds */
  int place = 0;

  /* print all primes starting at true and going to count */
  for (number = 2; number <= count; number++)
  {
    /* if the number is prime */
    if (isPrime(number))
    {
    place++;
    /* print to number to the file*/
    fprintf(ftp, "%d. %d\n", place, number);
    }
  }
}

You are doing brute-force trial division, and not particularly smartly. For example, you only need to test odd candidate factors up to sqrt(number).

When you want to find many prime numbers, a much better algorithm to use is the sieve-of-eratosthenes. It involves just addition, no division, and skips processing of numbers that are already known to be composite.


Removing n elements from array starting from index This method removes n elements starting from a given index, from an array of a given type. If n is positive it removes elements forwards, if it is negative it removes them backwards (e.g. for an array {1,2,3,4,5} Remove(2,2) results in {1,2,5}; Remove (2,-2) results in {1,4,5})

It there a better way to do it?

public static class ArrayExtensions
{
    public static T[] RemoveAt<T>(this T[] array, int idx, int len)
    {
        T[] newArray;

        if (len > 0)
        {
            if (idx + len > array.Length)
                len = array.Length - idx;

            newArray = new T[array.Length - len];
            if (idx > 0)
                Array.Copy(array, 0, newArray, 0, idx);

            if (idx < array.Length - 1)
                Array.Copy(array, idx + len, newArray, idx, array.Length - idx - len);
        }
        else
        {
            newArray = new T[array.Length + len];
            if (idx > 0)
                Array.Copy(array, 0, newArray, 0, idx + len);

            if (idx < array.Length - 1)
                Array.Copy(array, idx, newArray, idx + len, array.Length - idx);
        }

        return newArray;
    }
}

I believe that if the len < 0, it's better to adjust idx and len values. This will eliminate two branches of code.

Another suggestion is to use more readable variable names.
For instance, method arguments could be named startIndex and length respectively.

public static T[] RemoveAt<T>(this T[] array, int startIndex, int length)
{
    if (array == null)
        throw new ArgumentNullException("array");

    if (length < 0)
    {
        startIndex += 1 + length;
        length = -length;
    }

    if (startIndex < 0)
        throw new ArgumentOutOfRangeException("startIndex");
    if (startIndex + length > array.Length)
        throw new ArgumentOutOfRangeException("length");

    T[] newArray = new T[array.Length - length];

    Array.Copy(array, 0, newArray, 0, startIndex);
    Array.Copy(array, startIndex + length, newArray, startIndex, array.Length - startIndex - length);

    return newArray;
}


Select Queries From Parent-Child Tables Model I have two tables (parent-child model): Loans & Transactions.

Each Loan row has multiple Transaction rows.

I want to select all rows from Loans together with most recent row from Transactions.

Here is my select to achieve this.

SELECT
    L.*, T.*
FROM Loans L
CROSS APPLY
(
    SELECT TOP 1 * FROM Transactions AS T
    WHERE L.LoanID = T.LoanID
    ORDER BY CRTime DESC
) T

Another approach

SELECT
    L.*, T.*
FROM Loans L
INNER JOIN
(
    SELECT MAX(TransactionID) AS TransactionID, LoanID FROM Transactions AS T
    GROUP BY LoanID
) T
ON T.LoanID = L.LoanID
INNER JOIN Transactions TS
ON TS.TransactionID = T.TransactionID

Any ideas on improving it?

Side question: Can you suggest best practices for comparing two queries running times?

Select *
Generally, it is advised against using SELECT *. The answers to this stackoverflow question explain why SELECT * is considered harmful.
Your queries might return different values
The first query takes the transaction record with the latest CRTime, the second uses the highest ID. These are likely returning the same rows right now, but I would use the CRTime. The rows might not have been inserted in time order, so the most recent time and the highest ID might not result in the same record.
I would recommend the first query
I would recommend the first query because it avoids that second join that the second query has. Other than changing the SELECT *s to list all the columns and making sure the tables are properly indexed, I don't think there is much you can do to improve it. That's a pretty nice query.
Select * and Indexing
One of the problems pointed out in the linked SO question is that fact that using SELECT * can cause the query to not use indexing properly as it brings back more columns than you need.
Checking runtimes
I found this stackoverflow question had some good answers regarding comparing SQL runtimes/performance.


URL decode function optimization I have the following mockup that I need some feedback on how I might improve the url_decode function to make it faster and use less memory. There are a couple of requirements.  I have to use the StringArg and StringReturn structs. I also need to completely decode the string.  I am aware of double encoded attacks, but this is for data mining and I need to get the string fully decoded, hence the while loop.

Please have a look at function StringReturn* url_decode(char* line) and suggest anything that I can do to improve the speed or reduce the memory used.

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <ctype.h>

struct StringArg
{
    int length;
    char* data;
    StringArg(const char* inData)
    {
        length = strlen(inData);
        data = new char[length+1];
        strcpy(data, inData);
    }
};

struct StringReturn
{
    int size;
    char* data;
    StringReturn(int inSize)
    {
        size = inSize;
        data = new char[size+1];
    }
};

StringArg* stringArg(char* line)
{
    return new StringArg(line);
}

StringReturn* stringReturnInfo(int size)
{
    return new StringReturn(size);
}

StringReturn* url_decode(char* line)
{
        StringArg *str;
        str = stringArg(line);

        int lengths = str->length;
        char* urlData = new char[lengths+1];
        char* fmt = new char[4];
        memcpy(urlData, str->data, str->length);
        urlData[lengths] = 0;
        bool bFoundChar = false;

        int j = 0;

        do
        {
                j = 0;
                bFoundChar = false;
                for (int i = 0; i < lengths; i++)
                {
                        char ch = urlData[i];
                        if (ch == '+')
                        {
                                urlData[j++] = ' ';
                        }
                        else if (ch == '%' && i+2 < lengths &&  isxdigit(urlData[i+1]) &&  isxdigit(urlData[i+2]))
                        {
                                bFoundChar = true;
                                fmt = new char[4];

                                fmt[0] = urlData[++i];
                                fmt[1] = urlData[++i];
                                fmt[2] = 0;

                                urlData[j++] = (char)strtol(fmt, NULL, 16);

                        }
                        else {
                                urlData[j++] = ch;
                        }
                }
                lengths = j;
        }while (bFoundChar);

        StringReturn *ret = stringReturnInfo(j);
        ret->size = j;

        memcpy(ret->data, urlData, j);
        delete urlData;
        delete fmt;

        return ret;

}

void test_decode(char* line)
{
    StringReturn *str = url_decode(line);
    printf(str->data);
}

int main(int argc, const char * argv[])
{

    test_decode("bob.com?url=http%3A%2F%2Fsteve.com%3Furl%3Dhttp%253A%252F%252Fjohn.com");

    return 0;
}

This is doomed to failure:

struct StringArg
{
    int length;
    char* data;
    StringArg(const char* inData)
    {
        length = strlen(inData);
        data = new char[length+1];
        strcpy(data, inData);
    }
};

This can only lead to disaster. It is unlikely it is more efficient than std::string and is much more likely to lead to memory leaks.

Use std::string it will work is correct and has been optimized very heavily you can not beat it using your own hand written one. This is a premature optimization.

Same Again:

struct StringReturn
{
    int size;
    char* data;
    StringReturn(int inSize)
    {
        size = inSize;
        data = new char[size+1];
    }
};

Don't pass pointers around:

StringArg* stringArg(char* line)
{
    return new StringArg(line);
}

Use std::unique_ptr to encapsulate the pointer object so that it does correct memory management. If you are doing things correctly the resulting code optimizes to a no-op and if you don't do things correctly it saves your ass. In fact I would just throw away your string classes and use std::string. The copy construction from a return is nearly always elided by NRVO and thus is much more efficient than you seem to think.

Same Again

StringReturn* stringReturnInfo(int size)
{
    return new StringReturn(size);
}

Manually copying a C-string is very painful. Use std::string

    int lengths = str->length;
    char* urlData = new char[lengths+1];
    char* fmt = new char[4];
    memcpy(urlData, str->data, str->length);
    urlData[lengths] = 0;

    // Or you can do:

    std::string urlData = line;

Also your code is not exception safe.
Please use RIAA to make sure that there are no leaks (or use std::string that does this already).

The definition of a URL can be found here: http://tools.ietf.org/html/rfc3986
Pretending the '+' is a space is only valid in the path section of a URI and not valid in the query or fragment parts of the URI thus scanning the whole string for '+' is not correct.

  I also need to completely decode the string. I am aware of double encoded attacks

The specification does not allow for double (or nested) encoding. If it decodes to another '%' then that is the value. You don't try and re-interpret that value.


How to group custom events I have a number of custom events that a class might or might not subscribe to.

Action<Game1, MoveEventArgs> MoveEvent;
Action<Game1, InitializeEventArgs> InitializeEvent;
Action<Game1, DrawEventArgs> DrawEvent;
Action<Game1, LoadContentEventArgs> LoadContentEvent;

Each event is currently very similar just containing a number of properties such as:

public class MoveEventArgs : EventArgs
{
    public Vector2 Direction { get; set; }
}

public class LoadContentEventArgs : EventArgs
{
    public ContentManager Content { get; set; }
}

Some have more some have less. These are likely to be either expanded on or changed in the future if I need to pass more information.

A method subscribing to these events will generally access these arguments using them in someway that is specific to that event. For example a move event may look like this.

public void Move(object o, MoveEventArgs e)
{
    spriteInfo.Position = new Vector2(
        spriteInfo.Position.X + e.Direction.X, spriteInfo.Position.Y + e.Direction.Y
    );
}

And a content event may look like this.

public virtual void LoadContent(object o, LoadContentEventArgs e)
{
    spriteInfo.Texture = e.Content.Load<Texture2D>(spriteInfo.TextureName);
}

I would like to bundle these in someway so I can easily pass them into other functions. Such as in a list or dictionary.

I have come up with two solutions.
The first is to change my event declarations from:

Action<Game1, InitializeEventArgs> InitializeEvent;
public virtual void Initialize(object o, InitializeEventArgs e) { }

to:

Action<Game1, EventArgs> InitializeEvent;
public virtual void Initialize(object o, EventArgs e)
{
    InitializeEventArgs initializeEventArgs = (InitializeEventArgs)e;
}

This will allow me to create data stuctures using the type Action<Game1, EventArgs> but will mean I lose the typing on my event subscriber methods possibly resulting in cast exceptions.

The second is creating a struct with my Events in which I can pass to classes/methods.

public struct Events
{
    public Action<Game1, MoveEventArgs> MoveEvent { get; set; }
    public Action<Game1, InitializeEventArgs> InitializeEvent { get; set; }
    public Action<Game1, DrawEventArgs> DrawEvent { get; set; }
    public Action<Game1, LoadContentEventArgs> LoadContentEvent { get; set; }
}

Which I can then use to subscribe to the event in the appropriate class/method using:

Events.InitializeEvent += Initialize;

This seems good but it could potentially become a very large struct especially if I were to have a large number of events.

So I guess my main question is does anyone have improvements for these ideas or something different?

Review Solution 1
Sacrificing usability for the common consumer of your API in order to gain some usability for specific consumers that happen to subscribe on a multitude of events, should never be considered best practice.

Action<Game1, EventArgs> InitializeEvent;
public virtual void Initialize(object o, EventArgs e)
{
    // the average consumer does not want to cast here
    // if he only wants to be subscribed to this event ->
    InitializeEventArgs initializeEventArgs = (InitializeEventArgs)e;
}

Review Solution 2
Grouping events together is a better approach, since the common consumer is not impacted. It is an augmentation, rather than a substitution, of the event pattern. Though your implementation using a struct is viable, I would opt to use a more common approach - the Callback Interface.

public struct Events
{
    public Action<Game1, MoveEventArgs> MoveEvent { get; set; }
    public Action<Game1, InitializeEventArgs> InitializeEvent { get; set; }
    public Action<Game1, DrawEventArgs> DrawEvent { get; set; }
    public Action<Game1, LoadContentEventArgs> LoadContentEvent { get; set; }
}

Proposed Solution
You should determine whether to use either events, a callback interface or a mixture of both.
Let's assume you would like consumers to be able to subscribe to single events, and allow specific consumers to subscribe to all of them. The mixture of events and a callback interface could be implemented as follows.
Create event arguments
public class MoveEventArgs : EventArgs { /* .. impl */ }
public class InitializeEventArgs : EventArgs { /* .. impl */ }
public class DrawEventArgs : EventArgs { /* .. impl */ }
public class LoadContentEventArgs : EventArgs { /* .. impl */ }

Create a callback interface that bundles handlers for all the relevant events.
 public interface IGameListener
 {
      void OnMove(Game1 game, MoveEventArgs e);
      void OnInitialize(Game1 game, InitializeEventArgs e);
      void OnDraw(Game1 game, DrawEventArgs e);
      void OnLoadContent(Game1 game, LoadContentEventArgs e);
 }

As discussed, you may want to create an adapter. This allows derived classes to decide which event handlers to override.
public abstract class GameAdapter : IGameListener
{
      public virtual void OnMove(Game1 game, MoveEventArgs e) {}
      public virtual void OnInitialize(Game1 game, InitializeEventArgs e) {}
      public virtual void OnDraw(Game1 game, DrawEventArgs e) {}
      public virtual void OnLoadContent(Game1 game, LoadContentEventArgs e) {}
}

Game1 uses events and allows for registration of specific listeners. If you don't like to 'pollute' the game with these actions, you could let a mediator perform the registration of the callback interface. Argument checks are omitted for brevity.
 public class Game1
 {
        public event Action<Game1, MoveEventArgs> MoveEvent;
        public event Action<Game1, InitializeEventArgs> InitializeEvent;
        public event Action<Game1, DrawEventArgs> DrawEvent;
        public event Action<Game1, LoadContentEventArgs> LoadContentEvent;

        public void Register(IGameListener listener)
        {
            MoveEvent += listener.OnMove;
            InitializeEvent += listener.OnInitialize;
            DrawEvent += listener.OnDraw;
            LoadContentEvent += listener.OnLoadContent;
        }

        public void Unregister(IGameListener listener)
        {
            MoveEvent -= listener.OnMove;
            InitializeEvent -= listener.OnInitialize;
            DrawEvent -= listener.OnDraw;
            LoadContentEvent -= listener.OnLoadContent;
        }

        // other instance code ..
 }


Maximum sum of hourglass in an array I am solving some questions on HackerRank for practice purposes. This morning I solved one called Maximum sum of hourglass in an array.

Given an array:

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

the hourglass sum is 7 and we need to find the maximum sum of all hourglass in an array.

My implementation:

#include <vector>
#include <iostream>
#include <climits>

using std::vector;

int hourglassSum(vector<vector<int>> &arr) {
    int highestSum = INT_MIN;
    for (size_t i = 1; i < arr.size() - 1; ++i) {
        int sum = 0;
        for (size_t j = 1; j < arr.at(i).size() - 1; ++j) {
            sum = arr.at(i - 1).at(j - 1) +
                  arr.at(i - 1).at(j) +
                  arr.at(i - 1).at(j + 1) +
                  arr.at(i).at(j) +
                  arr.at(i + 1).at(j - 1) +
                  arr.at(i + 1).at(j) +
                  arr.at(i + 1).at(j + 1);
            if (sum > highestSum) {
                highestSum = sum;
            }
        }
    }
    return highestSum;
}

int main() {
    vector<vector<int>> nums =
        {{1, 1, 1, 0, 0, 0}, // 0
         {0, 1, 0, 0, 0, 0}, // 1
         {1, 1, 1, 0, 0, 0}, // 2
         {0, 0, 2, 4, 4, 0}, // 3
         {0, 0, 0, 2, 0, 0}, // 4
         {0, 0, 1, 2, 4, 0}}; // 5
    vector<vector<int>> nums2 =
        {{0, -4, -6, 0, -7, -6},
         {-1, -2, -6, -8, -3, -1},
         {-8, -4, -2, -8, -8, -6},
         {-3, -1, -2, -5, -7, -4},
         {-3, -5, -3, -6, -6, -6},
         {-3, -6, 0, -8, -6, -7}};
    std::cout << hourglassSum(nums) << std::endl;  // expected 19
    std::cout << hourglassSum(nums2) << std::endl;  // expected -19
}

My questions:

I think the runtime of this code is O(n*m), does anyone think there is a better way of doing this?
Does the code look efficient and readable?

Thanks

Readability

The vector initialization in main would be more readable if the {{ and }} were broken out onto separate lines.

    vector<vector<int>> nums = {
        {1, 1, 1, 0, 0, 0}, // 0
        {0, 1, 0, 0, 0, 0}, // 1
        {1, 1, 1, 0, 0, 0}, // 2
        {0, 0, 2, 4, 4, 0}, // 3
        {0, 0, 0, 2, 0, 0}, // 4
        {0, 0, 1, 2, 4, 0}
    }; // 5
    vector<vector<int>> nums2 =
    {
         {0, -4, -6, 0, -7, -6},
         {-1, -2, -6, -8, -3, -1},
         {-8, -4, -2, -8, -8, -6},
         {-3, -1, -2, -5, -7, -4},
         {-3, -5, -3, -6, -6, -6},
         {-3, -6, 0, -8, -6, -7}
    };

Complexity

The function int hourglassSum(vector<vector<int>> &arr) is too complex (does too much) it would be better if it was 2 functions:

int singleHourglassSum(vector<vector<int>> &arr, size_t i, size_t j)
{
    int hourglassSum =
            arr.at(i - 1).at(j - 1) +
            arr.at(i - 1).at(j) +
            arr.at(i - 1).at(j + 1) +
            arr.at(i).at(j) +
            arr.at(i + 1).at(j - 1) +
            arr.at(i + 1).at(j) +
            arr.at(i + 1).at(j + 1);

    return  hourglassSum;
}

int maxHourglassSum(vector<vector<int>> &arr) {
    int highestSum = INT_MIN;
    for (size_t i = 1; i < arr.size() - 1; ++i) {
        int sum = 0;
        for (size_t j = 1; j < arr.at(i).size() - 1; ++j) {
            sum = singleHourglassSum(arr, i, j);
            if (sum > highestSum) {
                highestSum = sum;
            }
        }
    }
    return highestSum;
}

Keep in mind the Single Responsibility Principle:

The Single Responsibility Principle states:

  that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.


Parsing text from reports I want to parse some reports from multiple devices, reports looks like this:

VR            Destination      Mac                Age  Static  VLAN          VID   Port
VR-Default    192.168.11.13    90:e2:ba:3c:95:c0    2      NO  intra1        350   49
VR-Default    192.168.1.1      00:0e:a6:f7:b6:b5    0      NO  main          602   1
VR-Default    192.168.1.2      00:0d:88:63:bf:d1    3      NO  main          602   1
VR-Default    192.168.1.14     00:1c:f0:c7:d2:52    4      NO  main          602   1
etc...
Dynamic Entries  :          19             Static Entries            :          0
Pending Entries  :           1
In Request       :     3888802             In Response               :       4531
and some more data...
Rx Error         :           0             Dup IP Addr               :         0.0.0.0
and some more...

I need only vr, destination, mac, age, static, vlan, vid and port fields.
I can parse it using split function and regexes, but split fails if one field (e.g. Age) is empty.
perldoc says I can use unpack:

my $template = 'A13xA16xA18xA4xA7xA13xA5xA*';
for my $line ( split /\n/, $data ) {
   chomp $line;
   my ($vr, $destination, $mac, $age, $static, $vlan, $vid, $port) = unpack $template, $line;
...
}

But it dies on lines with length < 84. And I got to check string length every time (Or maybe using eval on unpack? Is it better?). And again I got to use regexes or index to find the end of main table and skip headers.
The code will looks like:

#!/usr/bin/perl
use strict;
use warnings;
my $arp = <<'ARP';
VR            Destination      Mac                Age  Static  VLAN          VID   Port
VR-Default    192.168.11.13    90:e2:ba:3c:95:c0    2      NO  intra1        350   49
VR-Default    192.168.1.1      00:0e:a6:f7:b6:b5    0      NO  main          602   1
VR-Default    192.168.1.2      00:0d:88:63:bf:d1    3      NO  main          602   1
VR-Default    192.168.1.14     00:1c:f0:c7:d2:52    4      NO  main          602   1

Dynamic Entries  :          19             Static Entries            :          0
Pending Entries  :           1
In Request       :     3888802             In Response               :       4531
Rx Error         :           0             Dup IP Addr               :         0.0.0.0
ARP
my $template = 'A13xA16xA18xA4xA7xA13xA5xA*';
for my $line ( split /\n/, $arp ) {
   last if index( $line, 'Dynamic E' ) == 0;
   next if length $line < 84;
   chomp $line;
   my ($vr, $destination, $mac, $age, $static, $vlan, $vid, $port) = unpack $template, $line;
   next if $mac eq 'Mac';
   print "$mac - $destination\n";
}

My question is: how would you parse this data? split, regexes, unpack, substr or something else?

If a problem has been encountered before by someone else, chances are that there is a CPAN module for that (DataExtract::FixedWidth).

If you don't want to use a CPAN module, then my next choice would be to use regular expressions.

use strict;

# Strips leading and trailing whitespace from all parameters
sub strip {
    for (@_) { s/^\s+//; s/\s+$//; }
    @_;
}

# Extracts data from lines of text in tabular format.
#
# First parameter is a regular expression for capturing fixed-width fields.
#
# Subsequent parameters are the lines of tabular data, the first of which holds
# the column headings.  Any line that does not match the regular expression,
# as well as subsequent lines, are discarded.
#
# Returns a list (one element per input line) of hashes (keyed by column names).
sub extract_table {
    my ($fmt, $first_line) = (shift, shift);

    my (@headers) = strip($first_line =~ $fmt);

    my @table;
    for my $line (@_) {
        my (@fields) = $line =~ $fmt;
        last unless @fields;

        my %data;
        @data{@headers} = strip(@fields);
        push @table, \%data;
    }
    return @table;
}

my $fmt = qr/^(.{14})(.{17})(.{19})(.{5})(.{8})(.{14})(.{6})(.*)/;

# Take lines of input from a reasonable source (STDIN or a filename
# argument on the command line)
my @table = extract_table($fmt, <>);

use Data::Dumper;
print Dumper(\@table);

Note that chomp() is unnecessary since we're stripping whitespace characters anyway.


Back up or restore home directory I am currently trying to learn bash scripting and I've made a script that backs up or restores my home folder. My main question is whether my code is readable or very messy. I would love to learn to write my scripts understandable to others and also optimally. This script isn't made for sharing right now. Any tips on how I can make it better in any way? (Of course, the answer is yes, but I'm looking for specifics.) This is my first real script, so please don't be harsh.

#!/bin/bash

# Find where device is mounted and print so the user can check if correct.
BACKUP_DEV_UUID=#ENTER UUID HERE#
BACKUP_DEV_NODE=$(sudo blkid | grep $BACKUP_DEV_UUID | cut -f1 -d':')
if [[ ! $BACKUP_DEV_NODE =~ /dev/* ]]; then
    echo "Error, device not connected"
    exit 0
fi
MOUNT_POINT=$(mount | grep $BACKUP_DEV_NODE | cut -f3 -d' ')
echo "Mount point is: $MOUNT_POINT"

# Determine if you want to backup, restore of quit. Then fix full path.
echo -e "Input 1 to backup, 2 to restore, anything else to quit"
read -p "Enter choice: " -n1 fc
echo -e ""
case $fc in
    1) echo "Backup chosen"
    FULL_PATH=$MOUNT_POINT/$(hostname)_backup/home/$USER
    if [[ ! -d $FULL_PATH ]]; then
        echo "Backup path doesn't exist, creating"
        mkdir -p $FULL_PATH
    fi
    ;;

    2) echo "Restore chosen"
    # Choose hostname and username folders
    echo "Select appropriate hostname folder"
    select hn in $MOUNT_POINT/*_backup;
    do
        echo "Picked hostname folder: $HOSTNAME_VAR"
        echo "Select appropriate username folder"
        select un in $HOSTNAME_VAR/home/*;
            do
                echo "Picked username folder: $USERNAME_VAR"
                FULL_PATH=$USERNAME_VAR
                break
            done
        break
    done
    ;;

    *) echo "Exiting";
    exit 0
    ;;
esac

# Print dest/source and ask user if accepted.
case $fc in
    1) echo "Doing home folder backup"
    echo "Backup to path: $FULL_PATH"
    ;;

    2) echo "Doing home folder restore"
    echo "Restore from path $FULL_PATH"
    ;;
esac
read -r -n1 -p "Continue? Press y/Y to start backup/restore"
echo
if [[ ! $REPLY =~ ^[Yy]$ ]]; then
    echo "Aborting"
    exit 0
else
    echo "Continuing"
fi

# Actual backup/restore.
case $fc in
    1) rsync -aAXv ~/* $FULL_PATH --delete
    echo $(date) >> $FULL_PATH/homefolder_backup.log
    ;;

    2) rsync -aAXv $FULL_PATH ~/*
    ;;
esac
echo "Syncing"
sync
echo "Done"

This is very nice for a beginner!

Instead of matching against files in the filesystem as a glob like this:

if [[ ! $BACKUP_DEV_NODE =~ /dev/* ]]; then

It would be better to use the -e flag to check if the path exists or not:

if [[ ! -e $BACKUP_DEV_NODE ]]; then

It's better to avoid any of the flags of echo,
because they don't work consistently in all systems.

In these examples you don't need any flags:

echo -e "Input 1 to backup, 2 to restore, anything else to quit"
echo -e ""

You could simplify these as:

echo "Input 1 to backup, 2 to restore, anything else to quit"
echo

If you find yourself needing any of echo's flags,
look into printf instead.

In here:

select hn in $MOUNT_POINT/*_backup;
do
    echo "Picked hostname folder: $HOSTNAME_VAR"
    echo "Select appropriate username folder"
    select un in $HOSTNAME_VAR/home/*;
        do
            echo "Picked username folder: $USERNAME_VAR"
            FULL_PATH=$USERNAME_VAR
            break
        done
    break
done

You're not using hn.
Another thing, the do...done of the inner select is over-indented, which is not  consistent with the rest of the code.

The default exit code is that of the last operation.
So unless you want to forcefully exit with 0 after a failed operation,
you shouldn't need exit 0, you can write simply exit.

Instead of this:

echo $(date) >> $FULL_PATH/homefolder_backup.log

You could simply redirect the output of date itself:

date >> $FULL_PATH/homefolder_backup.log

The double-quotes here are unnecessary:

echo "Syncing"
echo "Done"


Computing the cost for creating a perfect square (with N = 3) You are given a square matrix \$A \in \mathbb{ N}^{n,n}\$, this number contains integers from \$1\$ to \$n^2\$.  The task is to compute the minimal cost, to change this square into a perfect square. A perfect square is a Matrix, such that every row, column and (full) diagonal add up to a magic number. The Matrix is limited by containing each number from \$1\$ to \$n^2\$
exactly once.

E.g.:

$$M = \begin{bmatrix}4\,\, 9\,\, 2 \\ 3 \,\,5\,\,7 \\ 8 \,\,1\,\,6\end{bmatrix}$$

\$M\$ is a perfect square.

To change \$A\$ into a perfect square, you are allowed to change every number freely. However this increases the cost by \$c_{n+1} = c_{n} + |m_{i,j} - a|\$, where \$a\$ is the new number.

It turns out, by the way, that the magic number is always:

$$m = \frac{n\cdot (n^2+1)}{2}$$

Example of computing the cost:

$$f(\begin{bmatrix}3\,\, 7\,\, 6 \\
9\,\, 5\,\, 1 \\
4\,\, 3\,\, 8\end{bmatrix}) = 1$$ If we change s[1][1] to 2 and s[1][3] to 6, we get a perfect square. The cost is 2-1 = 1;

Compute the minimal cost for n = 3:

This implementation solves the problem, but I have needed to realize that there are only 8 perfect squares for n = 3.

int formingMagicSquare(size_t s_rows, const int** s) {
    long long cost = -1;
    if(s_rows == 3){
        cost = LLONG_MAX;
        const int perfect_squares[8][3][3] = {
                                    {{2,7,6},{9,5,1},{4,3,8}},
                                    {{4,3,8},{9,5,1},{2,7,6}},
                                    {{6,1,8},{7,5,3},{2,9,4}},
                                    {{2,9,4},{7,5,3},{6,1,8}},
                                    {{8,3,4},{1,5,9},{6,7,2}},
                                    {{6,7,2},{1,5,9},{8,3,4}},
                                    {{4,9,2},{3,5,7},{8,1,6}},
                                    {{8,1,6},{3,5,7},{4,9,2}}
                                    };
        for(int k = 0; k < 8; k++){
            long long cost4_this_operation = 0;
            for(int i = 0; i < 3;i++){
                for(int j = 0; j < 3; j++){
                    long long diff = perfect_squares[k][i][j] - s[i][j];
                    cost4_this_operation += ((diff < 0) ? -diff : diff);
                }
            }
            if(cost4_this_operation < cost)cost = cost4_this_operation;
        }
    }
    return cost;
}

I have more questions about this code and I am not sure if I am allowed to ask them here because they ask for better ways to do this.
However, I have specific questions:

How do you return properly if the program cannot solve a certain case?
Can you calculate the absolute amount better than:

long long diff = perfect_squares[k][i][j] - s[i][j];
cost4_this_operation += ((diff < 0) ? -diff : diff);

The for-Looping seems not to be proper. How would you do that?

Thank you.

Since the function is hardwired to 3x3 matrices, it would make sense to pass a 3x3 matrix as an argument:

int formingMagicSquare(const int s[3][3])

This way you will not worry about what to do if s_rows != 3.
stdlib provides int abs(int).
The line

    if(cost4_this_operation < cost)cost = cost4_this_operation;

better be split into

    if(cost4_this_operation < cost) {
        cost = cost4_this_operation;
    }

Even better, make a static inline int min(int, int) function.
I see nothing wrong with the loops.
Of course, the solution is not scalable for larger dimensions.


Circular-shift with variable bitlength For some memory masking operations I need a bitwise-rotation functionality for unsigned integral types. I came across solutions based on the wiki article, but have not found a variation for a function for bitwise-rotation within an "arbitrary" field of bits. Therefore, I have extended the solution of John Regehr, and now I want some feedback from you. I would also appreciate any advice on using mechanisms provided by the C++ core language up to C++14 (without the use of the std namespace).

#include <iostream>
#include <vector>
#include <bitset>

uint64_t CircShift (uint64_t x, uint8_t n, uint8_t bitwidth)
{
  return ((x<<n)&((1<<bitwidth)-1)) | (x>>(bitwidth-n));
}

int main()
{
    uint64_t var=0b000110100110;
    var=CircShift(var,2,9);
    std::cout<<std::bitset<12>(var);

}

I think the function looks good. It does what it's supposed to do when the input is correct. However, if the input number x is larger or equal to 1<<bitwidth, the behavior is undefined. To rectify this, I suggest:

uint64_t CircShift(uint64_t x, uint8_t n, uint8_t bitwidth)
{
    return ((x<<n)&((1<<bitwidth)-1)) |
           ((x&((1<<bitwidth)-1))>>(bitwidth-n));
}

Just add another mask to the right-shifted part. Also note that for shifts that are bigger than 64 bits, both your original function and my new function behave strangely. To rectify this, you can use the fact that a circular shift by bitlength steps simply give you the original number:

uint64_t CircShift(uint64_t x, uint8_t n, uint8_t bitwidth)
{
    return ((x<<(n%bitwidth))&((1<<bitwidth)-1))
        | ((x&((1<<bitwidth)-1))>>(bitwidth-(n%bitwidth)));
}


Print the number of subarrays of an array having negative sums Problem statement: Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line.

My code: Taking order of 3 time. How can I improve my java code?

    import java.util.Scanner;
     public class NegativeSumOfArray {
        public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); //Taking size of an array
        int[] arr = new int[N];
        for(int i=0;i<N;i++){
            arr[i] = in.nextInt(); // Taking content of the array.
        }
        // Counting number of sub arrays whose summation is negative.
        int sum=0,count=0;
        for(int i=1,k,j;i<=N;i++){
            for(k=1;k<=N-i+1;k++){
                for(j=0;j<i;j++){
                    sum += arr[j+k-1];
                }
                if(sum<0)
                    count++;
                sum = 0;
            }
        }
        System.out.print(count);
        in.close();
    }
}

Consistency

                for(j=0;j<i;j++){
                    sum += arr[j+k-1];
                }
                if(sum<0)
                    count++;

It's more common to write the latter control structure

                if (sum < 0) count++;

That is the clearest way to write the single statement version.

But if you're doing that, why not say

                for (int j = 0; j < i; j++) sum += arr[j+k-1];

How do you choose when to use or not use the single statement form?

I find it easiest to never use it.  So I'd say

                if (sum < 0) {
                    count++;
                }

Then I don't have to consider whether I should use it this time or not.

There are also advantages if someone has to edit it in the future.  In particular, it's harder to make editing mistakes.

Keep it simple

        for(int i=1,k,j;i<=N;i++){
            for(k=1;k<=N-i+1;k++){
                for(j=0;j<i;j++){
                    sum += arr[j+k-1];

Consider

        for (int i = 0; i < arr.length; i++) {
            for (int k = 1; k <= arr.length - i; k++) {
                for (int j = 0; j <= i; j++) {
                    sum += arr[j+k-1];

In the second for, you had N-i+1, which is the same as N-(i-1).  But you can change the bounds of i from 1 to N to 0 to N-1.  Then you don't need the extra 1.  But then you need to change the third for loop to j <= i.

I would rather use arr.length than N, as that's the actual limiting factor.

I added some whitespace for readability.

        for (int i = 0; i < arr.length; i++) {
            for (int k = 0; k < arr.length - i; k++) {
                for (int j = 0; j <= i; j++) {
                    sum += arr[j+k];

In the summation step, you have j+k-1.  But if we change the bounds of k from 1 to N-i to 0 to N-i-1, we can just do j+k.

I find this version easier to follow when I read it.

        for (int i = 0; i < arr.length; i++) {
            for (int k = 0; k < arr.length - i; k++) {
                long sum = 0;
                for (int j = 0; j <= i; j++) {
                    sum += arr[j+k];

You declare sum outside all the for loops.  That's not necessary.  You could define it just before the third.  Then you don't have to reset it at the end of that loop.  It will be automatically set whenever you need it.

Using long instead of int avoids the possibility of overflow.

Alternatives

If you have plenty of space or are willing to modify the input array, you can do this with only two levels of loop nesting.  You can calculate the sums prior to checking them.

        long[][] sums = new long[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            sums[i][i] = arr[i];
        }

        for (int start = 0; start < arr.length; start++) {
            for (int end = start + 1; end < arr.length; end++) {
                sums[start][end] = sums[start][end - 1] + arr[end];
            }
        }

        int count = 0;
        for (int start = 0; start < arr.length; start++) {
            for (int end = start; end < arr.length; end++) {
                if (sums[start][end] < 0) {
                    count++;
                }
            }
        }

But we can actually do better.

        long[] sums = new long[arr.length];
        sums[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
           sums[i] = sums[i - 1] + arr[i];
        }

        int count = 0;

        // count the arrays starting with the first element
        for (int end = 0; end < arr.length; end++) {
            if (sums[end] < 0) {
                count++;
            }
        }

        // count the arrays starting with start+1
        for (int start = 0; start < arr.length; start++) {
            for (int end = start + 1; end < arr.length; end++) {
                if (sums[end] - sums[start] < 0) {
                    count++;
                }
            }
        }

Less space but the same runtime growth.

Both solutions make use of the fact that a sum of N elements is equal to a sum of N-1 elements plus the Nth element.  So we don't have to keep recalculating that, which is the slow part of the original code.


A simple stop watch which I want to extend I am making a very simple stopwatch functionality as below.

New will start the timer.
Pause will suspend the watch.
Start will restart again.
Session will return the duration.

#include<chrono>
#include<vector>

class Timer {
  using cppTimer  =  std::chrono::high_resolution_clock;
  using seconds   =  std::chrono::seconds;
  std::vector< int64_t > mvSession;
  cppTimer::time_point mtpNow;
  cppTimer::time_point mtPause;
  seconds mtRestart;
  bool mbIsPause;
public:

  enum Units {
    sec,
    min,
    hrs,
    end
  };

  Timer() noexcept: mbIsPause(false), mtRestart{} ,mvSession(3) {
  }

  inline void Now() noexcept {
    mtpNow    = cppTimer::now();
    mbIsPause = false;
    mtRestart = seconds(0);
  }

  inline void Pause() noexcept {
    if(!mbIsPause) {
      mtPause = cppTimer::now();
      mbIsPause = true;
    }

  }

  inline void Start() noexcept {
    if(mbIsPause) {
      mtRestart += std::chrono::duration_cast<std::chrono::seconds>(cppTimer::now() - mtPause);
      mbIsPause = false;
    }

  }

  std::vector< int64_t > SessionTime() {

    auto now   =  cppTimer::now();
    auto delay =  std::chrono::duration_cast<std::chrono::seconds>(now - mtpNow);

    if(mbIsPause) {
      mtRestart += std::chrono::duration_cast<std::chrono::seconds>(cppTimer::now() - mtPause);
    }

    auto tp =  std::chrono::duration_cast<std::chrono::seconds>(delay - mtRestart);   //+ mtRestart ;// SecondsTp(cppTimer::now()) - SecondsTp(mtpNow) + SecondsTp(mtRestart);

    mvSession[sec] = tp.count()%60;
    mvSession[min] = std::chrono::duration_cast<std::chrono::minutes>(tp).count()%60;
    mvSession[hrs] = std::chrono::duration_cast<std::chrono::hours>(tp).count();

    return mvSession;
  }

};

Don't use member variables for temporary storage

Your class Timer has a member variable mvSession, which is unnecessary. It is only used in SessionTime(), where it is filled in and returned. No other functions use it. Instead, just declare std::vector<int64_t> mvSession(3) inside SessionTime().

By making it a member variable, you introduced two problems: first, your class now uses more memory than necessary. Second, the function SessionTime() is now no longer reentrant; if two threads would call SessionTime() simultaneously, they would both write to the same mvSession variable, potentially corrupting it.

Use std::chrono::steady_clock for timers

The problem with std::chrono::high_resolution_clock() is that it is not guaranteed what kind of clock it is. It can represent wall clock time, which can jump ahead or forwards because of summer and winter time, leap seconds, the computer suspending and resuming. This is not something you want for a timer where you are interested in a simple duration. For this, you want to use std::chrono::steady_clock, which is guaranteed to be a monotonically increasing clock. Also, your function SessionTime() returns the time in a resolution of seconds, so you don't need a high resolution clock anyway.

Don't use Hungarian notation

There might be some merits to Hungarian notation, but it really isn't necessary to use it for C++, since the compiler will do type checking for you. Moreover, it's easy to use the wrong prefix, and it's hard to come up with a reasonable prefix when you can have complex types.

You are already making mistakes in your code. For example, mtpNow and mtPause are both of type cppTimer::time_point. So the prefix should have been the same. And mtRestart has a different type than mtPause, so their prefixes should have been different. I recommend that you just avoid using Hungarian notation altoghether.

Be consistent with using

You are declaring using seconds = std::chrono::seconds, and use seconds in a few places, but you also use std::chrono::seconds in a lot of places. Furthermore, you also use std::chrono::minutes and std::chrono::hours, but have not declared an alias for them. In this case, I suggest you don't declare using seconds at all.

I would keep using cppTimer though, since it basically selects which clock to use. That makes it easier to change the clock later by just changing one line of code. I would write using clock = ... though, to be consistent with the C++ library itself.

Don't cast to seconds too early

Instead of seconds mtRestart, use cppTimer::duration mtRestart. This will keep the accuracy of the duration to the same as the clock itself. Only cast durations to seconds or other time intervals until the last moment possible. The same goes for the calculation of delay in SessionTime(), just write:

auto delay = now - mtpNow;

Use nouns for variable names, verbs for function names

A variable holds (the value of) a thing, so its name should naturally be a noun. Functions do stuff, so there names should generally be verbs. The function Now() should actually be named Start(). Your function Start() should probably be named Continue(). The function SessionTime() calculates how long the timer has been running for, so probably should be named GetDuration().

Conversely, the variables mtPause and mtRestart should be renamed to nouns as well. They are a bit confusing. Sure, you set mtPause in the Pause() function, but it doesn't describe what the value actually means. The same goes for mtRestart. I would instead write:

clock::time_point StartTime;
clock::time_point PauseTime;
clock::duration PausedDuration;
bool IsPaused;

Now you can rewrite the function Now() to:

void Start() {
    StartTime = clock::now();
    IsPaused = false;
    PausedDuration = {};
}

Remove mtRestart

You are using two variables to handle the timer being paused, mtPause and mtRestart. However, you only need one. In the Pause() function, you indeed just record when this function is called. However, when restarting the timer, instead of adding the duration of being paused to mtRestart, just add that duration to mtpNow instead:

void Start() {
    if(mbIsPause) {
         mtpNow += cppTimer::now() - mtPause;
         mbIsPause = false;
    }
}

This also simplifies SessionTime():

std::vector<int64_t> SessionTime() {
    auto end = mbIsPause ? mtPause : cppTimer::now();
    auto tp = std::chrono::duration_cast<std::chrono::seconds>(end - mtpNow);
    ...
}

Also, since mtPause is only ever 0 when you didn't pause, you can use that to signal whether the timer is paused instead of having bool mbIsPause.

Another option is @user673679's suggestion of storing only the start time and the accumulated elapsed time so far. You would then use the start time being equal to {} as a signal that the timer has not been started.

Just return a std::chrono::duration

When you want the elapsed time, I would avoid having the Timer class be responsible for converting the duration to a vector of integers representing hours, minutes and seconds. It reduces the accuracy of your timer. Instead, I would just return a std::chrono::duration, and have the caller decide whether it wants to convert that to something. It also is much more efficient than having to construct a std::vector<int64_t>.

Try to make it behave reasonable in all situations

One issue with your code is that it only gives reasonable results for SessionTime() if you have called Now() at least once. You didn't initialize mtpNow, and even if it was value-initialized to zero, then SessionTime() will return the time that has passed since the epoch.

If you want the Timer to behave like it was started at construction time, then initialize mtpNow to cppTimer::now(). If you want it to behave like it was paused, then ensure both mtpNow and mtPause are initialized to the same value (I suggest just using {}), and that mbIsPause is true.

Make it work like a real stopwatch

As already suggested by others, it helps to think of a timer as a stopwatch. A real stopwatch starts in a stopped state, showing an elapsed time of zero. Then, you can start and stop the timer mechanism with buttons. Usually, there is a separate button to reset the stopwatch to its initial state. By making the class act like something a lot of people are already familiar with, the code is easier to understand for others.

Reworked code

Here is an example of what the code would look like with my suggestions applied, as well as @user673679's way of storing the elapsed time between previous start and stops of the clock:

#include <chrono>

class Timer {
  using clock = std::chrono::steady_clock;
  clock::time_point StartTime = {};
  clock::duration ElapsedTime = {};

public:
  bool IsRunning() const {
     return StartTime != clock::time_point{};
  }

  void Start() {
    if(!IsRunning()) {
      StartTime = clock::now();
    }
  }

  void Stop() {
    if(IsRunning()) {
      ElapsedTime += clock::now() - StartTime;
      StartTime = {};
    }
  }

  void Reset() {
    StartTime = {};
    ElapsedTime = {};
  }

  clock::duration GetElapsed() {
    auto result = ElapsedTime;
    if(IsRunning()) {
      result += clock::now() - StartTime;
    }
    return result;
  }
};
```


Small haskell text-processing script I'm a bioinformatician and mainly use python, but I'm trying to learn Haskell. So far I like this language because it's beautiful and fun, but my Haskell scripts usually end up being much slower than my Python equivalent.

Here is my latest attempt:

-- Define type synonyms for fields in a fastq record.
type Name = String
type Nucleotides = String
type Qualities = String

data FastqRecord = FastqRecord Name Nucleotides Qualities
{-
Show is implemented so that the string representation of a FastqRecord
is actually its fastq formatted representation.
-}
instance Show FastqRecord where
    show (FastqRecord name s q) = unlines [name, s, "+", q]

-- Parse lines four by four, ignore the third of each batch.
getFastqRecords :: [String] -> [FastqRecord]
getFastqRecords [] = []
getFastqRecords (l1 : l2 : _ : l4 : ls) = FastqRecord l1 l2 l4 : getFastqRecords ls

{-
We assume that the records come in sorted by sequence.
Successive records having the same sequence are fused,
arbitrarilly keeping the first name, and taking the
highest quality at each position.
-}
fuseFastqRecords :: [FastqRecord] -> [FastqRecord]
fuseFastqRecords [] = []
fuseFastqRecords [r] = [r]
fuseFastqRecords (r1@(FastqRecord n s1 q1) : r2@(FastqRecord _ s2 q2) : rs)
    | s1 == s2 = fuseFastqRecords (FastqRecord n s1 (bestquals q1 q2) : rs)
    | otherwise = r1 : fuseFastqRecords (r2 : rs)

{-
For each position, we want to keep the highest quality
among the records that had the same sequence.
In fastq format, qualities are integers represented as ascii characters
Using max on Char does what we want.
-}
bestquals :: Qualities -> Qualities -> Qualities
bestquals = zipWith max

main :: IO ()
main = interact (concatMap show . fuseFastqRecords . getFastqRecords . lines)

On very small test input, this scripts runs 10 times faster than my python implementation.

On "real" input, the python code (using pypy) uses much more ram than the Haskell version, but runs in half the time.

If I understood my readings so far, Strings in Haskell are not implemented efficiently, so I guess I would have to use another type to process my text.
But the representation as a list of Char is actually very convenient for one of the operations I want to do (see the comments about the bestquals function).

What would you recommend to do?

I found out that using Data.ByteString.Lazy.Char8 could significantly improve the running time (about one third of the one I posted initially).

Here is the code, taking into account some suggestions by Gurkenglas:

import qualified Data.ByteString.Lazy.Char8 as C

-- Define type synonyms for fields in a fastq record.
type Name = C.ByteString
type Nucleotides = C.ByteString
type Qualities = C.ByteString

data Fastq = Fastq Name Nucleotides Qualities

formatFastq :: Fastq -> C.ByteString
formatFastq (Fastq n s q) = C.unlines [n, s, C.pack "+", q]

-- Parse lines four by four, ignore the third of each batch.
getFastqs :: [C.ByteString] -> [Fastq]
getFastqs [] = []
getFastqs (l1 : l2 : _ : l4 : ls) = Fastq l1 l2 l4 : getFastqs ls

{-
We assume that the records come in sorted by sequence.
Successive records having the same sequence are fused,
arbitrarilly keeping the first name, and taking the
highest quality at each position.
-}
fuseFastqs :: [Fastq] -> [Fastq]
fuseFastqs [] = []
fuseFastqs [r] = [r]
fuseFastqs (r1@(Fastq n s1 q1) : r2@(Fastq _ s2 q2) : rs)
    | s1 == s2 = fuseFastqs (Fastq n s1 (bestquals q1 q2) : rs)
    | otherwise = r1 : fuseFastqs (r2 : rs)

{-
For each position, we want to keep the highest quality
among the records that had the same sequence.
In fastq format, qualities are integers represented as ascii characters
Using max on Char does what we want, and seems to work on Bytestring elements.
-}
bestquals :: Qualities -> Qualities -> Qualities
bestquals q1 q2 = C.pack (C.zipWith max q1 q2)

processLines :: [C.ByteString] -> [C.ByteString]
processLines ls = map formatFastq (fuseFastqs (getFastqs ls))

main :: IO ()
main = C.interact (C.concat . processLines . C.lines)

It would be nice to be able to avoid the ugly C.pack in bestquals.


Project Euler #9 in C: Special Pythagorean triplet I have finished Project Euler #9 on HackerRank:

  Given \$N\$, Check if there exists any Pythagorean triplet for which \$a+b+c=N\$, \$a^2+b^2=c^2\$.
  Find maximum possible value of \$abc\$ among all such Pythagorean triplets, and if there is no such Pythagorean triplet print −1.

However, I feel uncomfortable about my code. I think it is sort of spaghetti code that is neither well organized nor fast (just a feeling).

Optimization and simplification is needed. (For example, there are many nested ifs).

#include <stdio.h>
#include <time.h>
int main()
{
  clock_t start = clock();
  unsigned int i,j,t,n;
  long p;
  scanf("%u",&t);
  while(t>0)
  {
    p =-1;
    i=2;
    j=1;
    scanf("%u",&n);
    while(1)
    {
      int s = 2*i*i+2*i*j;
      if(s ==n )
      {
        long o = 2*i*j*(i*i+j*j)*(i*i-j*j);
        if (p<o) p =o;
        if(i>j+1) j++;
        else
        {
          j=1;
          i++;
        }
      }
      else if(s>n)
      {
        if(j==1) goto end;
        j=1;
        i++;
      }
      else
      {
        int counter;
        for(counter =2; s*counter<=n;counter++)
        {
          if(s*counter == n)
          {
            long o = 2*i*j*(i*i+j*j)*(i*i-j*j)*counter*counter*counter;
            if (p<o) p =o;
          }
        }
        if(i>j+1) j++;
        else
        {
          j=1;
          i++;
        }
      }
    }
    end: printf("%li\n",p);
    t--;
  }
  clock_t end = clock();
  printf("time in milliseconds %lf\n",(double)(end-start)*1000/CLOCKS_PER_SEC);
  return 0;
}

Just few remarks:

Variables with meaningful names are more useful and make the code easier to read and understand.
Comments add to code clarity and could possibly point to fragments that can be optimized.
Use a more compact brace style.

int foo()
{
    for
      {
          //...
      }
}

could become

int foo(){
    for{
         //...
       }
}

Add white space between operands and operations: (a + b; a == b; a = 1).
Consistency and style: eliminate random white spaces/ indentations in expressions (p =1, p=1 or p= 1)
Brake the code into functions, each with single task.


Increase performance of Bayesian likelihood equation I need to calculate a Bayesian likelihood in its negative logarithmic form:

$$-\ln L = N\ln M -\sum\limits_{i=1}^{N} \ln\left\{P_i \sum\limits_{j=1}^M \frac{\exp\left[ -\frac{1}{2}\left(\sum_{k=1}^D \frac{(f_{ik}-g_{jk})^2}{\sigma_{ik}^2 + \rho_{jk}^2}\right) \right]}{\prod_{k=1}^D \sqrt{\sigma_{ik}^2 + \rho_{jk}^2}} \right\}$$

where these $$P_i\;\;;\;\; f_{ik} \;\;;\;\; \sigma_{ik}^2\;\;;\;\; g_{jk}
\;\;;\;\; \rho_{jk}^2$$ are all known floats. This is my code:

import numpy as np

# Define random data with correct shapes.
N, M = np.random.randint(10, 1000), np.random.randint(10, 1000)
D = np.random.randint(2, 5)
f_N, g_M = np.random.rand(N, D, 2), np.random.rand(M, D, 2)
P_i = np.random.uniform(0., 1., N)

# N summatory.
# Store here each 'i' element from the M summatory.
sum_Mi = []
for f_i in f_N:

    # M summatory.
    sum_M_j = 0.
    for g_j in g_M:

        # Obtain ijk element inside the M summatory
        D_sum, sigma_ijk = 0., 1.
        for k, f_ik in enumerate(f_i):
            # Where: f_ik[0] = \f_{ik}       ; g_j[k][0] = \g_{jk}
            # and:   f_ik[1] = \sigma_{ik}^2 ; g_j[k][1] = \rho_{jk}^2
            D_sum += np.square(f_ik[0] - g_j[k][0]) / (f_ik[1] + g_j[k][1])
            sigma_ijk = sigma_ijk * (f_ik[1] + g_j[k][1])

        sum_M_j += np.exp(-0.5 * D_sum) / np.sqrt(sigma_ijk)

    sum_Mi.append(sum_M_j)

sum_Mi_Pi = P_i * sum_Mi
# Remove 0. elements before applying the logarithm below.
sum_N = sum_Mi_Pi[sum_Mi_Pi != 0.]

# Final negative logarithmic likelihood
lik = len(f_N) * np.log(len(g_M)) - sum(np.log(sum_N))
print(lik)

I'm after an optimization done at the code level, ie: not using multi-threading.

I've tried numpy broadcasting on the inner loop

# Obtain ijk element inside the M summatory
D_sum = sum(np.square((f_i[:, 0] - g_j[:, 0])) / (f_i[:, 1] + g_j[:, 1]))
sigma_ijk = np.prod(f_i[:, 1] + g_j[:, 1])

but that actually takes a longer time to complete than using the for loop!

I also tried using the logsumexp function from scipy combined with the broadcasted arrays:

# Store here each 'i' element from the M summatory.
sum_N = 0.
# N summatory.
for f_i in f_N:

    # M summatory.
    A, B = [], []
    for g_j in g_M:
        # Obtain ijk element inside the M summatory
        A.append(sum(
            np.square((f_i[:, 0] - g_j[:, 0])) / (f_i[:, 1] + g_j[:, 1])))
        B.append(np.prod(f_i[:, 1] + g_j[:, 1]))

    sum_N += logsumexp(-.5 * np.array(A), b=1. / np.sqrt(B))

# Final negative logarithmic likelihood
lik = len(f_N) * np.log(len(g_M)) - sum(np.log(P_i[P_i != 0.])) - sum_N
print(lik)

This resulted in a marginal improvement over just using broadcasting, but still slower than the original code.

This is much faster.  I added the seed to better compare results across runs.

import numpy as np

# Define random data with correct shapes.
np.random.seed(0)
N, M = np.random.randint(10, 1000), np.random.randint(10, 1000)
D = np.random.randint(2, 5)
f_N, g_M = np.random.rand(N, D, 2), np.random.rand(M, D, 2)
P_i = np.random.uniform(0., 1., N)

# replace loops with broadcasted array operation, followed by sums
fgsum = f_N[:,None,:,1] + g_M[None,:,:,1]
fgdif = f_N[:,None,:,0] - g_M[None,:,:,0]
print(fgsum.shape)   # e.g. (694, 569, 3)

Dsum = (fgdif**2 / fgsum).sum(axis=-1)
sigma_ijk = np.prod(fgsum, axis=-1)
sum_M_j = np.exp(-0.5 * Dsum) / np.sqrt(sigma_ijk)
sum_Mi = np.sum(sum_M_j, axis=-1)

# as before
sum_Mi_Pi = P_i * sum_Mi
# Remove 0. elements before applying the logarithm below.
sum_N = sum_Mi_Pi[sum_Mi_Pi != 0.]

# Final negative logarithmic likelihood
lik = len(f_N) * np.log(len(g_M)) - sum(np.log(sum_N))
print(lik)


Adding a list of brokers to a local SQLite database I have this piece of Java (Android) code that adds a list of brokers to a local SQLite database as one single SQL instruction.

public void Add(List<Broker> brokers)
{
    if(brokers == null || brokers.size() == 0)
      return;

    String sql = "INSERT INTO " + TABLE_NAME + " SELECT " + brokers.get(0).getId() + " AS '" + COLUMN_BROKERID + "', "+ brokers.get(0).getOfficeId() + " AS '" + COLUMN_OFFICEID +  "', '"+ brokers.get(0).getName() + "' AS '" + COLUMN_NAME +  "', "+ brokers.get(0).getSuccessRate() + " AS '" + COLUMN_SUCCESSRATE +  "'";

    for(int i=1; i<brokers.size(); i++)
    {
        sql = sql + " UNION SELECT " + brokers.get(i).getId() + ", " + brokers.get(i).getOfficeId() + ", '" + brokers.get(i).getName() + "', " + brokers.get(i).getSuccessRate();
    }

    databaseManager.ExecuteNonQuery(sql);
 }

But what slows this down a lot is the change in the string 'sql'. The last line, which is a call to ExecuteNonQuery(), takes a millisecond, but the above takes a lot. How can I speed this up?

databaseManager is an interface that is implemented by a class of SQLiteOpenHelper and simply executes an SQL statement (but don't take this into account; it doesn't take any time as much as the rest of the code).

A classicel one. String concatenation with the + operator is very inefficient, because it creates a new copy of the string every time.
See for example item 51 in Effective Java from Joshua Bloch or here: http://www.javapractices.com/topic/TopicAction.do?Id=4

Try to change it to StringBuilder:

public void Add(List<Broker> brokers)
{
    if(brokers == null || brokers.size() == 0)
      return;

    StringBuilder query = new StringBuilder(brokers.size() * 50); // size is a guess, could be furhter investigated
    query.append("INSERT INTO ").append(TABLE_NAME).append(" SELECT ").append(brokers.get(0).getId()).append(" AS '").append(COLUMN_BROKERID).append("', ").append(brokers.get(0).getOfficeId()).append(" AS '").append(COLUMN_OFFICEID).append("', '").append(brokers.get(0).getName()).append("' AS '").append(COLUMN_NAME).append("', ").append(brokers.get(0).getSuccessRate()).append(" AS '").append(COLUMN_SUCCESSRATE).append("'"); // it is not that important to change this line. this will probably be done by the java compiler anyway

    for(int i=1; i<brokers.size(); i++)
        query.append(" UNION SELECT ").append(brokers.get(i).getId()).append(", ").append(brokers.get(i).getOfficeId()).append(", '").append(brokers.get(i).getName()).append("', ").append(brokers.get(i).getSuccessRate());

    databaseManager.ExecuteNonQuery(query.toString(););
 }


Simon, Mat's Mug, what's the (rating) difference? This is a part of the code for the almighty bot @Duga (That's me!).

Every evening, 15 minutes before "RELOAD" (00:00 UTC), I post the reputation differences for some Code Review users.

Example output is:

  Mat's Mug vs. Simon Forsberg: 2728 diff. Year: +3618. Quarter: +885. Month: +648. Week: -40. Day: +185.

The code below makes use of the following classes/interfaces:

StackExchangeAPI: Contains methods for doing a request to Stack Exchange API. The result is then parsed and "slurped" as JSON and stored into a Groovy object.
DugaBot: Contains methods for sending a message to chat
WebhookParameters: Information about where to send the chat message (which chat room)

This class is created on startup (or when tasks are reloaded) and then run() is called on this class through a cron trigger in Grails.

Any comments about the code appreciated.

This code is also available on Github: Zomis/Duga.

class UserRepDiffTask implements Runnable {

    private final StackExchangeAPI stackApi;
    private final DugaBot chatBot;
    private final String usersString;
    private final String site;
    private final WebhookParameters room;

    public UserRepDiffTask(StackExchangeAPI stackApi, String room, DugaBot chatBot, String users, String site) {
        this.stackApi = stackApi;
        this.chatBot = chatBot;
        this.usersString = users.replace(',', ';');
        this.room = WebhookParameters.toRoom(room);
        this.site = site;
    }

    @Override
    public void run() {
        try {
            def result = stackApi.apiCall("users/" + usersString, site, "!23IYXA.sS8.otifg5Aq.2");
            List users = result.items
            if (users.size() != 2) {
                throw new UnsupportedOperationException("Cannot check diff for anything other than two users");
            }

            def max = users.stream().max(Comparator.comparingInt({it.reputation})).get();
            def min = users.stream().min(Comparator.comparingInt({it.reputation})).get();
            StringBuilder str = new StringBuilder();
            str.append(clearName(max.display_name) + " vs. " + clearName(min.display_name) + ": ");
            str.append((int)max.reputation - (int)min.reputation);
            str.append(" diff. ");
            diffStr(str, max, min, "Year", {it.reputation_change_year});
            diffStr(str, max, min, "Quarter", {it.reputation_change_quarter});
            diffStr(str, max, min, "Month", {it.reputation_change_month});
            diffStr(str, max, min, "Week", {it.reputation_change_week});
            diffStr(str, max, min, "Day", {it.reputation_change_day});
            chatBot.postSingle(room, str.toString());

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static String chatName(String displayName) {
        return clearName(displayName).replace(" ", "");
    }

    public static String clearName(String displayName) {
        while (displayName.contains("&#")) {
            String replacement = displayName.substring(displayName.indexOf("&#") + 2);
            try {
                replacement = replacement.substring(0, replacement.indexOf(';'));
                int ch = Integer.parseInt(replacement);
                displayName = displayName.replaceFirst("&#\\d+;", String.valueOf((char) ch));
            } catch (RuntimeException ex) {
                displayName = displayName.replaceFirst("&#", "");
            }
        }
        return displayName;
    }

    private void diffStr(StringBuilder str, max, min, String string, ToIntFunction<?> function) {
        str.append(string);
        str.append(": ");
        int maxValue = function.applyAsInt(max);
        int minValue = function.applyAsInt(min);
        int diff = maxValue - minValue;
        str.append(diff > 0 ? "+" : "");
        str.append(diff);
        str.append(". ");
    }

}

The static chatName() method isn't used at all. Just get rid of it because it is only adding noise.
Why is the static clearName() method public ? Make it either private and non static or place it in some other class which has the responsibility to do such cleaning to get the clear name.

Or to ask different, what is wrong with using org.apache.commons.lang.StringEscapeUtils.unescapeHtml like you do in AnswerInvalidationCheck ?
StringBuilder

IMO if you "know" or if you can narrow the resulting capacity of the StringBuilder you should use the overloaded constructor which takes the initial capacity as a parameter.
I like the fluent methods of the StringBuillder. IMO taking advantage of the fluent way makes it easier to read the code.
doing string concatenation to build a parameter for the append() method is somehow strange. Why don't you just use the append() method ?

Some vertical spacing would be good for your code. It groups related code and makes it more readable.

def max = users.stream().max(Comparator.comparingInt({it.reputation})).get();
def min = users.stream().min(Comparator.comparingInt({it.reputation})).get();

StringBuilder str = new StringBuilder();
str.append(clearName(max.display_name) + " vs. " + clearName(min.display_name) + ": ");
str.append((int)max.reputation - (int)min.reputation);
str.append(" diff. ");

diffStr(str, max, min, "Year", {it.reputation_change_year});
diffStr(str, max, min, "Quarter", {it.reputation_change_quarter});
diffStr(str, max, min, "Month", {it.reputation_change_month});


Read two numbers and return a sum, in PIC24 Assembly .data
D0:  .byte 0x04; first number
D1:  .byte 0x03; second number
.bss
R0: .space 2;result
.txt
_main:   ..
         ..
         CALL mySUB
         ..
mySUB:   ...
         ....
         return
 .end

Given above, write a program that would read the numbers (in D0 and D1) and call a subroutine, mySUB, that adds the two number and returns the result. Then your main program saves the result in R0.

My attempt at this was

.data
D0:  .byte 0x04; first number
D1:  .byte 0x03; second number
.bss
R0: .space 2;result
.txt
_main:   mov.b #D0,W1
         mov.b #D1,W2
         CALL mySUB
         mov W3,[W0]; once the subroutine returns, it comes to this line, which stores the result to R0's address
mySUB:   mov #R0,W0
         add W1,W2,W3; W3 = D0+D1
         return; return back to where it was called
 .end

I feel confident that this is the right set of instructions but need confirmation.

As @Snowbody already pointed asked, what is your code supposed to after this line:

mov W3,[W0]

It seems as though the execution of your program will fall through and re-enter the mySUB subroutine again.

To fix this...

Create a second label after the mySUB. Then, after _main is done working with the return values of mySUB, you can jmp (or whatever it is called in PIC24) to the second label that you created.

Then, execution will jump over mySUB and hit the .end pragma at the end.

Your mySUB subroutine seems to be doing more than it's job.

The very first line of this subroutine is

mov #R0, W0

This line is moving a pointer to a memory location into W0. However, this subroutine is supposed to add numbers together. If it was meant to add numbers together and then put the result in memory, then why isn't it doing that at the end of the subroutine?

In my opinion, you should move the first line out of the subroutine and to the first line after the subroutine call (and before mov W3,[W0]).

That way, the subroutine is doing it's job of adding two numbers together, and the _main routine is doing it's job of getting two numbers added together, and then putting that sum in memroy

In the future, I recommend that you add some sort of documentation for each subroutine you have. It doesn't have to be a lot; it can be something as simple as this:

; Adds two numbers
; Input: W1, W2
; Output: W3 = W1 + W2
mySUB: ...


Perl DBI insert of hash How can this method that inserts a hashref into a database table be improved?  It assumes that the columns of the database table are named identically to the fields in the hashref.  The return value is the id field created by the insert.

sub insert(){
    my ($table, $data) = @_;
    my ($fields, $placeholders, $values) = ("", "", []);
    while (my ($field, $value) = each %$data){
        $fields.=", " if ($fields);
        $fields.=$field;
        $placeholders.=", " if ($placeholders);
        $placeholders.="?";
        push(@$values, $value);
    }
    $dbh->prepare("INSERT INTO $table ($fields) VALUES ($placeholders)")->execute(@$values);
    return $dbh->last_insert_id(undef, undef, undef, undef);
}

It assumes that $dbh is a correctly initialized global database handle.

It is used like:

&insert("animals", {
    "type"=>"cat",
    "name"=>"Patches",
    "date-of-birth"=>"November 1, 2015",
    "date-of-death"=>undef
});

Which will insert a record into the animals table:

id | type | name    | date-of-birth    | date-of-death
=====================================================
 1 | cat  | Patches | November 1, 2015 | null

This might be a good candidate to use SQL::Abstract in, as per DBIx::Class.

sub insert {
    # insert takes ( $table, \%fieldmap )
    my $sql = SQL::Abstract->new();
    my ( $query, @binds ) = $sql->insert( @_ );
    $dbh->prepare($query)->execute(@binds);
    return $dbh->last_insert_id(undef, undef, undef, undef);
}

This gives you a few easy features that may come in handy in the future
if you change your database, like:

easily change quoting character for tables/fields
guard against injection abuse in user-specified key names, because your code currently assumes all keys will be safe. But this will not necessarily be true, and is a vulnerability target even under taint


ArrayList implementation Can someone help me optimize speed for my code? I tested it via stopwatch in milliseconds. I've implemented my own ArrayList and I would like to improve its speed without using C# built-in structures.

Mylist.cs

using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ManualArrayList {
class MyList : IList {
private object[] _items;

public MyList() {
    _items = new object[0];
}

public void PrintElement() {
    for(int i = 0; i < _items.Length; i++) {
        Console.WriteLine(_items[i]);
    }
}

public int Add(object value) {
    object[] tmp = new object[_items.Length + 1];
    for(int i = 0; i < _items.Length; i++) {
        tmp[i] = _items[i];
    }
    tmp[tmp.Length - 1] = value;
    _items = tmp;
    return tmp.Length - 1;
}

public bool Contains(object value) {
    return IndexOf(value) != -1;
}

public int IndexOf(object value) {
    return IndexOf(value, 0);
}

public int IndexOf(object value, int startIndex) {
    for(int i = startIndex; i < _items.Length; i++) {
        if(_items[i].Equals(value)) {
            return i;
        }
    }
    return -1;
}

public void Remove(object value) {
    if(!Contains(value)) {
        return;
    }
    object[] tmp = new object[_items.Length - 1];
    bool deleted = false;
    for(int i = 0, j = 0; i < tmp.Length; i++, j++) {
        if(_items[i].Equals(value) && !deleted) {
            j++;
            deleted = true;
        }
        tmp[i] = _items[j];
    }
    _items = tmp;
}

public void Insert(int index, object value) {
    object[] tmp = new object[_items.Length + 1];
    if(index - 1 >= _items.Length + 1 || index < 0) {
        Console.WriteLine("This type of index was not found in array");
        return;
    }
    for(int i = 0, j = 0; i < tmp.Length && j < _items.Length; i++, j++) {
        if(j == index - 1) {
            tmp[j] = value;
            i++;
        }

        tmp[tmp.Length - 1] = value;
        tmp[i] = _items[j];
    }

    _items = tmp;

}
public void RemoveAt(int index) {
    if(index >= _items.Length || index < 0) {
        Console.WriteLine("This type of index was not found in array");
        return;
    }
    object[] tmp = new object[_items.Length - 1];
    for(int i = 0, j = 0; i < tmp.Length; i++, j++) {
        if(i == index) {
            j++;
        }
        tmp[i] = _items[j];
    }
    _items = tmp;
}

public void Clear() {
    _items = new object[0];
}

public int Count {
    get {
        return _items.Length;
    }
}

// es avxsnat ertad mere...
public object this[int index] {
    get {
        throw new NotImplementedException();
    }
    set {
        throw new NotImplementedException();
    }
}

//es ertad gavaketot
public void CopyTo(Array array, int index) {
    throw new NotImplementedException();
}

//es ertad gavaketot
public IEnumerator GetEnumerator() {
    throw new NotImplementedException();
}

#region We Dont Touch This
public bool IsFixedSize {
    get {
        return false;
    }
}

public bool IsReadOnly {
    get {
        return false;
    }
}

public bool IsSynchronized {
    get {
        return true;
    }
}

public object SyncRoot {
    get {
        return this;
    }
}
#endregion

}
}

Probably the best improvement would be to allocate extra storage space and also store how many elements your list contains. Right now you allocate a new array and copy all existing values on each add operation, and this results in O(n) time complexity for adding items. Instead you could increase inner array twice each time, this would result in amortized O(1). Also, with this approach you wouldn't need to allocate new arrays on removal operations, as you could just leave empty space at the end.


Find prime numbers under N I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> because of the performance of removing items to the list while looping through it. Also, I'd want to know if I respect the Java conventions with my code.

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

public class PrimeFinders
{
    public static void main (String[] args) throws java.lang.Exception
    {
        LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();
        final int maxNumber = 1000; //This is N

        //Add only uneven numbers, as even numbers won't be prime
        for(int i = 3; i <= maxNumber;i+=2){
            naturalNumbers.add(i);
        }

        int primeIndex = 1; //Starting at 1 since we need to count the number 2, not added in the list
        int primeNumber = 2; //First prime number is 2

        while(naturalNumbers.size() > 0){
            primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop.
            System.out.println("Prime " + primeIndex + " : " + primeNumber);
            applyEratosthenesSieve(primeNumber, naturalNumbers);
            primeIndex++;
        }
    }

    private static void applyEratosthenesSieve(int prime, LinkedList<Integer> numbers){
        Iterator<Integer> numbersIterator = numbers.iterator();

        while(numbersIterator.hasNext()){
            int number = numbersIterator.next();
            if(number % prime == 0){ //Remove all multiples of the number.
                numbersIterator.remove();
            }
        }
    }
}

This doesn't look like a Sieve of Eratosthenes.  This sure looks like trial division:

  while(numbersIterator.hasNext()){
      int number = numbersIterator.next();
      if(number % prime == 0){ //Remove all multiples of the number.
          numbersIterator.remove();
      }
  }

Unless I'm misunderstanding what your iterators are doing.  A simple SoE will have something that looks like:

for i from 2 to sqrt(n):          /* Loop from 2 to square root of max */
  if A[i]:                        /* If this location indicates prime, */
    for j from i*i to n step i:   /* then for each multiple of i,      */
      A[j] = false;               /* mark composite                    */

See the examples at RosettaCode or Wikipedia for example.  For comparison, RosettaCode's Trial Division task has a loop like your function.

So the immediate performance issue is that a sieve will be much faster than trial division.


IIF shortern to one datarow .Net Is it possible to shorten the Isnull checking?

It would be great to shorten this code and only have to put the datarow once.

This code imports data details (usually there would be more .x = IIF.... statements)

 Public Class apPropertyFunctions

        Public Function GetProperty(ByVal sUPRN As String) As apProperty
            'Public Function GetProperty(ByVal sUPRN As String, ByVal sUCARN As String) As apProperty
            Try

                Dim vIP As String = HttpContext.Current.Request.ServerVariables("REMOTE_ADDR")
                Dim oDetails As New apProperty

                Dim sConnString As String = System.Web.Configuration.WebConfigurationManager.ConnectionStrings("SQL_DEMO").ConnectionString
                Dim dsNames As SqlDataSource

                dsNames = New SqlDataSource

                dsNames.ConnectionString = sConnString
                Dim sSQL As String
                sSQL = "spGetProperty"
                dsNames.SelectCommand = sSQL
                dsNames.SelectCommandType = SqlDataSourceCommandType.StoredProcedure
                dsNames.SelectParameters.Clear()
                dsNames.SelectParameters.Add("ID", ID)

                For Each datarow As Data.DataRowView In dsNames.Select(DataSourceSelectArguments.Empty)

                    With oDetails
                        .ID= datarow("ID").ToString
     .BuildingNo = IIf(datarow("BuildingNo").Equals(DBNull.Value), "", datarow("BuildingNo").ToString)
                    End With

                    '  End If
                Next

                dsNames = Nothing

                Return oDetails

            Catch ex As Exception
                Return Nothing
            End Try

        End Function

Don't leave garbage laying around please, pick up after yourself.

'  End If

This doesn't have a purpose here, just get rid of it.

This isn't a good idea either

        Catch ex As Exception
            Return Nothing
        End Try

This was probably meant to close the connection, but there is a much better way to do that than to catch all exceptions and not report them.  Using Statements.

This is kind of smelly to me as well.

            Dim sSQL As String
            sSQL = "spGetProperty"
            dsNames.SelectCommand = sSQL

This simple Function doesn't need to be any more difficult than it has to be, you should do one of two things here.

Pass in the Stored Procedure Name as a string to the function
just set the SelectCommand to the name of the stored procedure like:

dsNames.SelectCommand = "spGetProperty"

It doesn't look like there is any reason whatsoever to call dsNames.SelectParameters.Clear() this object was created here and there is nothing in it yet, there should be no reason that you need to clear nothing.

Some other things that you don't need include

            Dim vIP As String = HttpContext.Current.Request.ServerVariables("REMOTE_ADDR")

And

        'Public Function GetProperty(ByVal sUPRN As String, ByVal sUCARN As String) As apProperty

With all that I left in the Try/Catch statement because I didn't know exactly what you were needing it for, but this is what it would look like with all these changes.

Public Function GetProperty(ByVal sUPRN As String) As apProperty
    Try
        Dim oDetails As New apProperty
        Dim sConnString As String = System.Web.Configuration.WebConfigurationManager.ConnectionStrings("SQL_DEMO").ConnectionString

        Using dsNames As New SqlDataSource
            dsNames.ConnectionString = sConnString
            dsNames.SelectCommand = "spGetProperty"
            dsNames.SelectCommandType = SqlDataSourceCommandType.StoredProcedure
            dsNames.SelectParameters.Clear()
            dsNames.SelectParameters.Add("ID", ID)

            For Each datarow As Data.DataRowView In dsNames.Select(DataSourceSelectArguments.Empty)
                With oDetails
                    .ID = datarow("ID").ToString
                    .BuildingNo = IIf(datarow("BuildingNo").Equals(DBNull.Value), "", datarow("BuildingNo").ToString)
                End With
            Next
        End Using
        Return oDetails
    Catch ex As Exception
        Return Nothing
    End Try
End Function


converting object of arrays to an array of objects in a desired format const getSelectedItemsIds = selectedItemsList => {

  let keys = Object.keys(selectedItemsList);
  let selectedItems = [];

  keys.map(k => {
    selectedItemsList[k].map(id => {
      if (k.includes("projectIds")) {
        return selectedItems.push({ type: "PROJECT", id });
      } else if (k.includes("subjectGroupIds")) {
        return selectedItems.push({
          type: "SUBJECT_GROUP",
          id
        });
      } else if (k.includes("subjectIds")) {
        return selectedItems.push({ type: "SUBJECT", id });
      }
    });
  });

  return selectedItems;
}

I have written my custom logic to get the desired result, if anyone can validate and tell me if there's a better way to do it. I'm adding input and expected out below:

I/P:
{
    projectIds: [2]
    subjectGroupIds: [] // incase multiple subjects are grouped togehter
    subjectIds: [4]
}

Expected format:
[{"type":"PROJECT","id":2},{"type":"SUBJECT","id":4}]

Thanks in advance!

Your code is not bad. You use functional style to loop through the data, which is good. But inside the loop you do not have to check with if-elseif-elseif, as this is not solid when it comes to many many cases.
Maybe it would be better to use a map object to guide the process of matching data.

getSelectedItemsIds = selectedItemsList => {
    const keyNamesMap = {
        projectIds: "PROJECT",
        subjectGroupIds: "SUBJECT_GROUP",
        subjectIds: "SUBJECT"
    };
    let selectedItems = [];

    Object.keys(keyNamesMap).map( k => {
        selectedItemsList[k].map ( id => {
            selectedItems.push (
                {
                    type: keyNamesMap[k],
                    id: id
                }
            );
        });
    });
    return selectedItems;
}

This way it is more clear and more easy to add another type.


Estimation of min_samples for DBSCAN I'm attempting to speed up some python code that is supposed to automatically pick the minimum samples argument in DBSCAN. Currently the execution time grows exponentially as the number of training samples increases:

0.128999948502 seconds for 100 training examples
0.281999826431 seconds for 1000 training examples
11.5310001373 seconds for 10000 training examples

  min_samples is the number of samples (or total weight) in a
  neighborhood for a point to be considered as a core point. This
  includes the point itself.

Can anyone make some suggestions for how to speed up the code?

As a bonus, adding the n_jobs argument to DBSCAN doesn't seem to affect the execution time of DBSCAN.

import numpy as np
from sklearn.metrics.pairwise import euclidean_distances
from time import time

def autoselect_minsamps_orig(D_sym,eps,K,kmedian_thresh):
   min_samps = 10
   kmedian_dist_prev = 0
   for k in range(2,K):
      k_avg = []
      # For each row, compute median distance to k nearest neighbors
      for row in D_sym:
         flat_row = np.squeeze(np.asarray(row))
         row_nonzero = flat_row[np.flatnonzero(flat_row)]
         # Some nodes aren't connected to anything
         if len(row_nonzero) == 0: continue
         sorted_row = np.sort(row_nonzero)
         sorted_row_t = sorted_row[0:k]
         k_avg.append(np.median(sorted_row_t))
      kmedian_dist = np.median(k_avg)
      kmedian_delta = abs(kmedian_dist - kmedian_dist_prev)

      if kmedian_delta <= kmedian_thresh:
         min_samps=k
         break
      kmedian_dist_prev = kmedian_dist
   return min_samps

num_training_examples = 100
num_features = 10
X = np.random.randint(5, size=(num_training_examples, num_features))

# generate a symmetric distance matrix
D = euclidean_distances(X,X)
eps = 0.25
kmedian_thresh = 0.005
K = num_training_examples

start = time()
result = autoselect_minsamps_orig(D,eps,K,kmedian_thresh)
end = time()
total_time = end - start
print('autoselect_minsamps took {} seconds for {} training examples'.format(total_time,num_training_examples))

num_training_examples = 1000
num_features = 10
X = np.random.randint(5, size=(num_training_examples, num_features))

# generate a symmetric distance matrix
D = euclidean_distances(X,X)
eps = 0.25
kmedian_thresh = 0.005
K = num_training_examples

start = time()
result = autoselect_minsamps_orig(D,eps,K,kmedian_thresh)
end = time()
total_time = end - start
print('autoselect_minsamps took {} seconds for {} training examples'.format(total_time,num_training_examples))

num_training_examples = 10000
num_features = 10
X = np.random.randint(5, size=(num_training_examples, num_features))

# generate a symmetric distance matrix
D = euclidean_distances(X,X)
eps = 0.25
kmedian_thresh = 0.005
K = num_training_examples

start = time()
min_samples = autoselect_minsamps_orig(D,eps,K,kmedian_thresh)
end = time()
total_time = end - start
print('autoselect_minsamps took {} seconds for {} training examples'.format(total_time,num_training_examples))

# min_samples is used here
db = DBSCAN(eps=eps,
            min_samples = min_samples,
            metric='precomputed',
            n_jobs=-1).fit(D)

Since the elements in each row grows, sorting the row only to take the k smallest is a bit wasteful. Using numpy.partition should always be faster:

sorted_row_t = np.partition(row_nonzero, k)[:k]

This is not needed with the examples you give, the row is already an array and flattened:

flat_row = np.squeeze(np.asarray(row))

Similarly, you can just use numpy.nonzero, no need to flatten the flattened row again:

row_nonzero = flat_row[np.nonzero(frow)]

However, this whole for loop can be done entirely in numpy:

First, mask all zeros by setting them to numpy.nan:

D = np.where(D == 0, np.nan, D)

Get the k smallest elements of each row. Since numpy.nan is not smaller than any number it will only appear at the beginning if (almost) the whole row was zeros:

k_smallest = np.partition(D, k, axis=1)[:, :k]

Compute the median of each row, and then the median of the median, ignoring numpy.nan values using numpy.nanmedian:

kmedian_dist = np.nanmedian(np.nanmedian(k_smallest, axis=1))

The first two steps can even be pulled outside of the for k in ... loop, which will save some more time. In that case we have to sort the whole array, though, because numpy.partition does not guarantee that the values are sorted, only that the k smallest values are in the slice up to k. Since K seems to be max(D_sym.shape) in all cases anyway, this should not make such a big difference. It will if the k at which the for loops stops is small enough, though, so you will have to test this.

There's no need to break and then immediately return afterwards, just return directly.

Python has an official style-guide, PEP8. It recommends using 4 spaces as indentation (not 3) and spaces after commas.

In summary, this should do the same as your code:

def autoselect_minsamps_graipher(D_sym, eps, K, kmedian_thresh):
    D = np.sort(np.where(D_sym == 0, np.nan, D_sym), axis=1)
    kmedian_dist_prev = 0
    for k in range(2, K):
        kmedian_dist = np.nanmedian(np.nanmedian(D[:,:k], axis=1))
        if abs(kmedian_dist - kmedian_dist_prev) <= kmedian_thresh:
            return k
        kmedian_dist_prev = kmedian_dist
    return 10 # fall back value

This is faster than your implementation, but suffers from similar scaling behaviour:

n       autoselect_minsamps_orig    autoselect_minsamps_graipher
100     0.028 s                     0.0088 s
1000    0.32 s                      0.064 s
10000   9.5 s                       3.6 s

You could also make timing your code easier by using a decorator:

from time import perf_counter

class Timer:
    def __init__(self, name=""):
        self.name = ""
        self.start = None

    def __enter__(self):
        self.start = perf_counter()

    def __exit__(self, *args, **kwargs):
        delta = perf_counter() - self.start
        print(f"{self.name} finished in {delta:.2f} seconds")

Or, if you are stuck on Python 2:

from time import time

class Timer:
    def __init__(self, name=""):
        self.name = ""
        self.start = None

    def __enter__(self):
        self.start = time()

    def __exit__(self, *args, **kwargs):
        delta = time() - self.start
        print "{} finished in {:.2f} seconds".format(self.name, delta)

Which you can use like this:

D = euclidean_distances(X,X)
eps = 0.25
kmedian_thresh = 0.005
K = num_training_examples

with Timer(f"autoselect_minsamps_orig, K = {K}"):
    min_samples = autoselect_minsamps_orig(D, eps, K, kmedian_thresh)

Note that I used time.perf_counter, which is better suited for timing, but which is Python 3 only.