Sqrt (square root) function As an exercise in learning Scala, I implemented a square root function like this:

  def sqrt(x: Double): Double = {
    if (x < 0) throw new IllegalArgumentException("negative numbers not allowed")
    val threshold = if (x < 1) x / 1e15 else 1e-12
    def sqrt(x: Double, p: Double): Double = {
      if (p == x / p) p  // without this condition, non-termination with 1e50
      else if (Math.abs(p * p - x) < threshold) {
        def diff1 = Math.abs(x - p * p)
        def diff2 = Math.abs(x - x / p * x / p)
        if (diff1 < diff2) p else x / p
      }
      else sqrt(x, (p + x / p) / 2)
    }
    sqrt(x, x / 2)
  }

The implementation passes these unit tests:

  test("sqrt 2") {
    assert(sqrt(2) === Math.sqrt(2))
  }

  test("sqrt 1e-3") {
    assert(Math.abs(1e-3 - sqrt(1e-3) * sqrt(1e-3)) ===
      Math.abs(1e-3 - Math.sqrt(1e-3) * Math.sqrt(1e-3)))
  }

  test("sqrt 1e-20") {
    assert(sqrt(1e-20) === Math.sqrt(1e-20))
  }

  test("sqrt 1e-21") {
    assert(sqrt(1e-21) === Math.sqrt(1e-21))
  }

  test("sqrt 1e20") {
    assert(sqrt(1e20) === Math.sqrt(1e20))
  }

  test("sqrt 1e50") {
    assert(sqrt(1e50) === Math.sqrt(1e50))
  }

My questions:

How can I improve this?
Notice the unit test for the case of 1e-3. It's more complex than the others to compensate for the difference between sqrt and Math.sqrt. Although the both sqrt and Math.sqrt are equally incorrect (the square of both have the same discrepancy with x), I wonder if I can change the implementation to match the result of Math.sqrt.
I found the error thresholds for < 1 and >= 1 through trial and error: all unit tests pass with these values and some would fell if I stretched the limits further. I'm wondering if there is a better, proper way of setting suitable thresholds based on x and the numeric limits of the language.

I'm going to concentrate on the Scala rather than the maths side, because that's my area.

The internal helper function doesn't need two parameters, since the value of x never changes; pushing x repeatedly onto the stack is a waste of time.  Also, better to use a case statement than a chain of if...else if...else - much less error prone.

def sqrt(x: Double): Double = {
  if (x < 0) throw new IllegalArgumentException("negative numbers not allowed")
  val threshold = if (x < 1) x / 1e15 else 1e-12
  def sqrtx(p: Double): Double = p match {
    case q if q == x / q => q // without this condition, non-termination with 1e50
    case q if Math.abs(q * q - x) < threshold => {
      def diff1 = Math.abs(x - p * p)
      def diff2 = Math.abs(x - x / p * x / p)
      if (diff1 < diff2) p else x / p
    }
    case _ => sqrtx((p + x / p) / 2)
  }
  sqrtx(x / 2)
}

I renamed the inner function sqrtx to avoid confusion about what it is doing.


To find if a character is a delimiter I have a function to check if a character is a delimiter and I wonder if it is consistent or can be improved:

int chDelimit(int ch)
{
    return
        (ch == '\n' || ch == '\t') ||
        (ch >= ' ' && ch <= '/') ||
        (ch >= ':' && ch <= '@') ||
        (ch >= '[' && ch <= '`') ||
        (ch >= '{' && ch <= '~') ||
        (ch == '\0');
}

There's no particular ordering of characters' code-points in C (other than the digits 0..9).  This code assumes (for example) that '[' is less than '`', but that's not the case in EBCDIC at least.

I think you might be better off creating a table of boolean values, and indexing into that with the (unsigned value of) ch, in the way that standard <ctype.h> functions are normally implemented.  This will probably improve performance (one lookup, rather than up to 11 comparisons, per call).

Alternatively, and depending on what characters are considered "delimiters", you may be able to use standard library functions (e.g. isalnum()) in combination.


DP example for "Power of Two" in Python I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming.

The snippet should show the bottom-up approach of DP.

The function isPowerOfTwo returns True if the given number n is a power of two otherwise False. The implementation uses a button-up table results.

def isPowerOfTwo(n):
    results = {}
    for i in range(1, n + 1):
        if i == 2:
            results[i] = True
        elif i % 2 != 0:
            results[i] = False
        else:
            results[i] = results[i/2]
    return results[n]

Do you have any recommendations?

There are some major issues with your approach, the major one being that it is going to terribly break down for really large numbers. But if you want to go with it, here are a couple of improvements:

Don't use a dictionary. If your indices are consecutive integers, then a list is the right data structure.
You already know that most of your entries are going to be False, so why not initialize those in bulk and worry only about setting the Trues?

def is_power_of_two(n):
    sieve = [False] * (n + 1)
    pot = 2
    while pot < len(sieve):
        sieve[pot] = True
        pot *= 2
    return sieve[n]

The name sieve is taken from the approach being somewhat similar to the sieve of Erathostenes algorithm.

In your case you can take things one step further, and rather than storing the full array, store only the indices of the True entries:

def is_power_of_two(n):
    pots = [2]
    while pots[-1] < n:
        pots.append(pots[-1]*2]
    return pots[-1] == n

If you look at that code, you don't really need to store the whole array, since you are only using the last value. So you can get the same time complexity, \$O(\log n)\$, but with constant space, by doing:

def is_power_of_two(n):
    pot = 2
    while pot < n:
        pot *= 2
    return pot == n

Of course the proper, fast way of checking if a number is a power of two is with a little bit twiddling hack that give \$O(1)\$ performance:

def is_power_of_two(n):
    return not n & (n - 1)


Setting icons when a tab is selected I have this 2 arrays :

final int[] tabSelected = {
        R.drawable.iconWhite0,
        R.drawable.iconWhite1,
        R.drawable.iconWhite2,
        R.drawable.iconWhite3,
        R.drawable.iconWhite4};
final int[] tabsUnselected = {
        R.drawable.iconBlack0,
        R.drawable.iconBlack1,
        R.drawable.iconBlack2,
        R.drawable.iconBlack3,
        R.drawable.iconBlack4};

I just don't understand how I can simplify this, by making a for loop ..although I am sure it is very easy, I just don't see it.

  @Override
        public void onPageSelected(int position) {
            switch (position) {
                case 0:
                    tabLayout.getTabAt(0).setIcon(tabSelected[0]);
                    tabLayout.getTabAt(1).setIcon(tabsUnselected[1]);
                    tabLayout.getTabAt(2).setIcon(tabsUnselected[2]);
                    tabLayout.getTabAt(3).setIcon(tabsUnselected[3]);
                    tabLayout.getTabAt(4).setIcon(tabsUnselected[4]);
                    break;

                case 1:
                    tabLayout.getTabAt(0).setIcon(tabsUnselected[0]);
                    tabLayout.getTabAt(1).setIcon(tabSelected[1]);
                    tabLayout.getTabAt(2).setIcon(tabsUnselected[2]);
                    tabLayout.getTabAt(3).setIcon(tabsUnselected[3]);
                    tabLayout.getTabAt(4).setIcon(tabsUnselected[4]);
                    break;

                case 2:
                    tabLayout.getTabAt(0).setIcon(tabsUnselected[0]);
                    tabLayout.getTabAt(1).setIcon(tabsUnselected[1]);
                    tabLayout.getTabAt(2).setIcon(tabSelected[2]);
                    tabLayout.getTabAt(3).setIcon(tabsUnselected[3]);
                    tabLayout.getTabAt(4).setIcon(tabsUnselected[4]);
                    break;

                case 3:
                    tabLayout.getTabAt(0).setIcon(tabsUnselected[0]);
                    tabLayout.getTabAt(1).setIcon(tabsUnselected[1]);
                    tabLayout.getTabAt(2).setIcon(tabsUnselected[2]);
                    tabLayout.getTabAt(3).setIcon(tabSelected[3]);
                    tabLayout.getTabAt(4).setIcon(tabsUnselected[4]);
                    break;

                default:
                    tabLayout.getTabAt(0).setIcon(tabsUnselected[0]);
                    tabLayout.getTabAt(1).setIcon(tabsUnselected[1]);
                    tabLayout.getTabAt(2).setIcon(tabsUnselected[2]);
                    tabLayout.getTabAt(3).setIcon(tabsUnselected[3]);
                    tabLayout.getTabAt(4).setIcon(tabSelected[4]);
                    break;
            }
        }

You check whether the index of the tab equals the position. If this is the case, use the selected icon, otherwise use the unselected one:

for(int i = 0; i < 5; i++) {  // maybe replace 5 with a constant declaration...
    if(i == position)
        tabLayout.getTabAt(i).setIcon(tabSelected[i]);
    else
        tabLayout.getTabAt(i).setIcon(tabsUnselected[i]);
}


Merge sort in declarative style with JavaScript ES6 syntax helps to write code in a declarative style, which is exactly what I am trying to achieve here. Any advice to make my code "more declarative" (and easier to read) is welcomed.

const middleIndex = xs => Math.floor(xs.length / 2);

const split = xs => {
    return {
        fst: xs.slice(0, middleIndex(xs)),
        snd: xs.slice(middleIndex(xs))
    };
};

const isSingleton = xs => xs.length === 1;

const any = xs => xs.length > 0;

const dropHead = xs => xs.shift();

const head = xs => xs[0];

// Arrow functions cannot be generators. Damn it!
const merge = function* (xs, ys) {
    while (any(xs) && any(ys)) {
        yield dropHead(head(xs) < head(ys) ? xs : ys);
    }

    while (any(xs)) {
        yield dropHead(xs);
    }

    while (any(ys)) {
        yield dropHead(ys);
    }
}

const sort = xs => {
    if (isSingleton(xs) || !any(xs)) {
        return xs;
    }

    const { fst, snd } = split(xs);

    return [...merge(sort(fst), sort(snd))];
}

I'd move the helper functions into sort's scope. Names like any and merge are very generic, and don't need to be cluttering up the global scope.

I also question the need for some of the functions, especially dropHead. It's just a synonym for Array.shift, so why not just call shift? All you get is a function with side-effects; since shift modifies the receiver, dropHead modifies the passed-in array, but at an extra level of, well, obfuscation almost.

The naming of isSingleton isn't great either. "Singleton" in OO languages usually has precise meaning. In mathematics it refers to a single-element set, but in a programming context I'd expect it to check whether the array object itself is a singleton.

In the end, I'd just say array.length === 1 where needed. And any can be replaced with array.length > 0 or even array.length as zero is falsey. Is it as declarative? Maybe not, but in my opinion it's more readable JS than inventing new expressions.

Conversely, I see no reason to skimp on the naming of variables and properties. Why fst and snd instead of simply first and second? Why xs instead of just array or items or list? If the goal is to be declarative, I see little point to use overly terse naming.

Your main sort function has a subtle gotcha: If you return early because the array is a "singleton" or empty, you return the same array reference that was passed in. If there's actual sorting going on, you return a new array object. So the function essentially has two distinct behaviors depending on input - dangerous. I'd recommend that the early return uses xs.slice(0) (or just xs.slice()) to ensure that it's always a copy that's returned.

There are a few ES6 features you can use, although support is spotty. One is to use array destructuring instead of object destructuring to assign the return value(s) from split. It obviates the need for fst/snd, and by returning an array you ensure ordering, rather than having to explicitly assign fst and snd in order, or even having to know those property names. E.g.

const [head, tail] = split(array); // where split() returns a 2-element array

Returning an array also means you can simply run it through map instead: split(array).map(sort).

Also, you don't need the two extra while loops to yield the elements of xs and ys in your merge function; you can simply delegate the yielding to the arrays themselves:

yield* xs;
yield* ys;

In all, I'd write something like:

const sort = array => {
  const split = array => {
    const middle = array.length >> 1; // should be a safe use of bitwise trickery
    return [array.slice(0, middle), array.slice(middle)]
  };

  const merge = function* (a, b) {
    while(a.length && b.length) {
      yield a[0] <= b[0] ? a.shift() : b.shift();
    }

    yield* a;
    yield* b;
  }

  if(array.length < 2) {
    return array.slice(0); // always return a copy
  }

  return [...merge(...split(array).map(sort))];
}

I've skipped the head function as it'd only be used twice - in the same line even. The remaining helper functions are nicely "symmetrical": Split and merge.

Edit: Just realized something: Your sorting isn't stable. In fact, it's precisely not stable. A quick test:

 var test = [1, "1", 2, "2", "3", 3]; // already sorted

 test = sort(test) // =>  ["1", 1, "2", 2, 3, "3"]
 test = sort(test) // =>  [1, "1", 2, "2", "3", 3]
 test = sort(test) // =>  ["1", 1, "2", 2, 3, "3"]
 // ...

Long story short: The merge branching should use <= rather than < when deciding which array to shift from. I've corrected the code in this answer.

Addendum: It might be more declarative and pattern-matching'y to use a switch statement to determine whether to return early:

const sort = array => {
  const split = array => {
    const middle = array.length >> 1;
    return [array.slice(0, middle), array.slice(middle)]
  };

  const merge = function* (a, b) {
    while(a.length && b.length) {
      yield a[0] <= b[0] ? a.shift() : b.shift();
    }

    yield* a;
    yield* b;
  }

  switch (array.length) {
    case 0:
    case 1:
      return array.slice();
    default:
      return [...merge(...split(array).map(sort))];
  }
}


Worksheetfunction.Vlookup value on error I have this function (wb is a public workbook variable):

Function GetTiersAccount(TiersName As String, Clients As Boolean) As Long

If Clients = True Then
    On Error GoTo ERRRRR
    GetTiersAccount = WorksheetFunction.VLookup(TiersName, wb.Sheets(1).Range("A1:B13"), 2, False)
    Exit Function
Else
    On Error GoTo ERRRRR
    GetTiersAccount = WorksheetFunction.VLookup(TiersName, wb.Sheets(1).Range("D1:E94"), 2, False)
    Exit Function
End If

ERRRRR:
GetTiersAccount = 471

End Function

I feel like the way I have managed to deal with worksheetfunction.vlookup error unelegant. However I want Gettieraccount to return 471 on vlookup error.

There must be a better way to do that.
Thanks in advance.

Your handling is not necessarily unelegant, but there are a couple of things to point out.

The main thing is that you're repeating code that really only needs to be there once. For example, you only need to write the VLookup statement once. Just set up a variable to define your range.

Your error handling can work, but you need to more clearly define what is a "normal exit" from your routine and what is an error exit. It's typical in this case to structure your error handling with the form shown below because there may be processing required during a normal exit only that you still might have to perform during an error exit.

Option Explicit

Function GetTiersAccount(TiersName As String, Clients As Boolean) As Long
    Dim lookupRange As Range
    If Clients = True Then
        Set lookupRange = wb.Sheets(1).Range("A1:B13")
    Else
        Set lookupRange = wb.Sheets(1).Range("D1:E94")
    End If

    On Error GoTo ERRRRR
    GetTiersAccount = WorksheetFunction.VLookup(TiersName, lookupRange, 2, False)

NormalExit:
    Exit Function

ERRRRR:
    GetTiersAccount = 471
    Resume NormalExit
End Function


Find the longest subarray with sum less than K The problem consist of finding the longest contiguous subarray with a sum less than a given integer K.

The input data are:

K - the max sum
array - an array of integers

The algorithm I developed:

head = tail = 0

- while the tail is less than the length of the array
   - increment the tail and update the sum
   - if the sum go over the K, increment the head until the sum is less than K
   - while incrementing the tail check if we have a new max_length

The Python code:

def length_max_subarray(array, K):
    head, tail = 0, 0
    length = 0
    current_sum = 0
    while(tail<len(array)):
        if current_sum + array[tail]<=K:
            current_sum += array[tail]
            tail+=1
            if tail-head > length:
                length = tail-head
        else:
            current_sum -= array[head]
            head+=1

    return length

My assumption is "this code is \$O(N)\$" because:

The worst case is when all elements are larger than K. In that case the while loop will increment the head and the tail successively so the number of iterations is \$2*N\$.

Is it true? If not, what's the complexity of this code?

Time complexity check

The best way to see if a function is indeed running in average linear time is to actually run it and look at the graph of size (N) vs time needed.

(Ask me if you are interested in the code used to generate this graph.)

There are a few outliers when the algorithm has to iterate more rather than less, but in general the trend is clearly linear.

Actual code review

As far as the code itself, you could yield the lengths and call max afterwards, to separate the code into finding all subarrays lengths and picking the max one: (this way finding all sub-arrays is just list(length_subarrays_more_than_k(array, K)))

def length_subarrays_more_than_k(array, K):
    head, tail = 0, 0
    current_sum = 0
    while(tail<len(array)):
        if current_sum + array[tail]<=K:
            current_sum += array[tail]
            tail += 1
            yield tail - head
        else:
            current_sum -= array[head]
            head += 1

def max_subarray_more_than_k(array, k):
    return max(length_subarrays_more_than_k(array, K))


Slow Filtering Method on DataGrid Sometime ago I asked a question regarding a slow Filtering method for my DataGrid. Months later and I have a relatively quick method, though I am still looking to improve performance, especially when the user is deleting text from the SearchBox as this seems to slow down more than if the user is typing characters in.

OnTypingIntoSearchBox

private void OnSearchBoxTextChanged(object sender, TextChangedEventArgs e)
{
    ApplyFilter();
}

ApplyFilter

private void ApplyFilter()
{
    if (CurrentJobsCollectionView != null)
    {
        CurrentJobsCollectionView.Filter = FilterJobs;
    }
    UpdateJobCounter();
}

FilterJobs

    private bool FilterJobs(object o)
    {
        return FilterByCheckBox(o) && FilterByJobsSearchBox(o);
    }

FilterByJobsSearchBox

private bool FilterByJobsSearchBox(object o)
{
    try
    {
        var searchText = CharactersOnly(jobsSearchBox.Text);
        var job = o as JobModel;
        if (searchText == string.Empty)
        {
            return true;
        }
        else
        {
            if (CompanyContains(job.JobReference, searchText.ToLower()) ||
                CompanyContains(job.CaseClient, searchText.ToLower()) ||
                CompanyContains(job.JobDescription, searchText.ToLower()) ||
                CompanyContains(job.JobNotes, searchText.ToLower()) ||
                CompanyContains(job.JobID.ToString(), searchText.ToLower()))
            {
                return true;
            }
        }
        return false;
    }
    catch (System.Exception ex)
    {
        var hEs = new HandleExceptionService();
        hEs.HandleException(ex.ToString());
        return false;
    }
}

FilterByCheckBox

private bool FilterByCheckBox(object o)
{
    var today = DateTime.Today;
    criteria.Clear();

    if (yourJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == yourJobsCheckBox.Tag.ToString()));
    }

    if (adamJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == adamJobsCheckBox.Tag.ToString()));
    }

    if (chrisJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == chrisJobsCheckBox.Tag.ToString()));
    }

    if (danJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == danJobsCheckBox.Tag.ToString()));
    }

    if (emilyJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == emilyJobsCheckBox.Tag.ToString()));
    }

    if (kitJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == kitJobsCheckBox.Tag.ToString()));
    }

    if (mattJobsCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == mattJobsCheckBox.Tag.ToString()));
    }

    if (unallocatedCheckBox.IsChecked == true)
    {
        criteria.Add(new Predicate<JobModel>(x => x.ITName == unallocatedCheckBox.Tag.ToString()));
    }

    if (_employees.Children.OfType<CheckBox>().All(c => Convert.ToBoolean(!c.IsChecked))) // If none are checked
    {
        currentJobsDataGrid.ItemsSource = null;
        completedJobsDataGrid.ItemsSource = null;
        archivedJobsDataGrid.ItemsSource = null;
    }

    JobModel job = o as JobModel;
    bool isIn = true;
    if (criteria.Count() == 0)
        return isIn;
    isIn = criteria.Any(x => x(job));
    return isIn;
}

I hope that isn't too much code - apologies if it is. I'm essentially looking for anyway to improve the efficiency of this filtering method, either by the user searching through typing in text or by checking specific checkboxes.

The end of your code...

bool isIn = true;
if (criteria.Count() == 0)
    return isIn;
isIn = criteria.Any(x => x(job));
return isIn;

Looks really weird to me

Get rid of the boolean variable, you don't need it to return a true or false value from expressions that return a boolean.

Also, make this an if/else statement.

if (criteria.Count() == 0)
{
    return true;
}
else
{
    return criteria.Any(x => x(job));
}

You could also condense this to a single return statement using a ternary statement

return criteria.Count() == 0 ? true : criteria.Any(x => x(job));

or even a simple or conditional

return criteria.Count() == 0 || criteria.Any(x => x(job));

some would say that having the ==0 isn't very clean when you could instead write it like this

return !criteria.Any() || critera.Any(x =>  x(job));

On the other hand, in your FilterByJobsSearchBox method I would un-nest the if statement, it is indented in a way that isn't necessary and looks messy.

Something else that you should do to make this more dry, is to apply the ToLower method to the variable assignment instead of when you compare to see if the jobs contain the search text, I will show you what I mean

    var searchText = CharactersOnly(jobsSearchBox.Text);
    var job = o as JobModel;
    if (searchText == string.Empty)
    {
        return true;
    }
    else
    {
        if (CompanyContains(job.JobReference, searchText.ToLower()) ||
            CompanyContains(job.CaseClient, searchText.ToLower()) ||
            CompanyContains(job.JobDescription, searchText.ToLower()) ||
            CompanyContains(job.JobNotes, searchText.ToLower()) ||
            CompanyContains(job.JobID.ToString(), searchText.ToLower()))
        {
            return true;
        }
    }
    return false;

Here is what it looks like when you do everything I mentioned above

var searchText = CharactersOnly(jobsSearchBox.Text).ToLower();
var job = o as JobModel;
if (searchText == string.Empty)
{
    return true;
}

if (CompanyContains(job.JobReference, searchText) ||
    CompanyContains(job.CaseClient, searchText) ||
    CompanyContains(job.JobDescription, searchText) ||
    CompanyContains(job.JobNotes, searchText) ||
    CompanyContains(job.JobID.ToString(), searchText))
{
    return true;
}

return false;

we could go a little further and make this one return statement as well, it will be a very long return statement....

var searchText = CharactersOnly(jobsSearchBox.Text).ToLower();
var job = o as JobModel;
return searchText == string.Empty
    || CompanyContains(job.JobReference, searchText)
    || CompanyContains(job.CaseClient, searchText)
    || CompanyContains(job.JobDescription, searchText)
    || CompanyContains(job.JobNotes, searchText)
    || CompanyContains(job.JobID.ToString(), searchText);


Vector of vectors in contiguous memory I have a class Vector3d with 3 double components and want to store several of them in a Field. For reasons of efficiency when sending a Field over a network via MPI, I would like to allocate contiguous memory in the Field class and let the Vector3ds store their components in that chunk of memory. In addition, Vector3ds should also be able to live without a Field; in this case, they have to care about their own memory allocation.

#include <cstddef>
#include <iostream>
#include <vector>

class Field;

class Vector3d
{
    friend class Field;

    public:
        Vector3d() : components_(new double[3]) {}
        ~Vector3d() { delete[] components_; }
        Vector3d(const Vector3d &v) : components_(new double[3])
        {
            components_[0] = v.components_[0];
            components_[1] = v.components_[1];
            components_[2] = v.components_[2];
        }
        double & operator()(const std::size_t index) { return components_[index]; }

    private:
        Vector3d(double *ptr) : components_(ptr) {};
        double *components_;
};

class Field
{
    public:
        Field(std::size_t size);
        ~Field();
        Vector3d & operator()(const std::size_t index) { return *(vectors_[index]); }

    private:
        std::vector<double> components_;
        std::vector<Vector3d *> vectors_;
};

Field::Field(std::size_t size) : components_(std::vector<double>(3 * size)), vectors_(std::vector<Vector3d *>(size, new Vector3d(0)))
{
    double *ptr = &components_[0];
    for (auto it = vectors_.begin(); it != vectors_.end(); ++it)
    {
        (*it)->components_ = ptr;
        ptr += 3;
    }
}

Field::~Field()
{
    for (auto it = vectors_.begin(); it != vectors_.end(); ++it)
        (*it)->components_ = 0;
}

int main(int argc, char *argv[])
{
    Field field(2);
    Vector3d &v = field(1);
    v(2) = 5;

    Vector3d v2 = v;
    v2(2) = 2;

    std::cout << field(1)(2) << std::endl;

    return 0;
}

I would like to hear what you think about this piece of code. Can this be considered a good solution or what would you change?

When it comes to multidimensional vectors I usually suggest two approaches.
1. vector/array (C++11 and later)
This only works, when the inner dimensions are fixed and only the outer is runtime dynamic. In the end it comes down to something like this:
std::vector<std::array<T, N>> field;

In your case a Vector3d would either derive from std::array<double, 3> or contain one.
2. simple vector
This approach simply creates a one dimensional vector with X * Y size.
The element (x, y) can then be addressed with vec[y * X + x]. This works also with the older C++ standard. Although I think this solution might not work in your setup.
Bonus
I just want to highlight @Yakk's comment. Your Vector3d could look like this:
class Vector3d
{
public:
    // stuff
    // ...
private:
    double components_[3];
};

This way the memory would also be contigous.


Rewriting to single pipeline by using data flow blocks I have a number of messages with a payload as a list of items. My goal is to transform the message payload without losing the relation between the message and payloads.

Isn't it possible to rewrite the code to a single pipeline without creating an instance of a nested pipeline for each message?

using System.Threading.Tasks.Dataflow;

public class Message<T>
{
    public int Id { get; set; }

    public IList<T> Items { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        var rnd = new Random();

        var input = new TransformBlock<Message<int>, Message<string>>(x => Transform(x));

        var action = new ActionBlock<Message<string>>(
            x =>
            {
                Console.WriteLine("MSG #{0}", x.Id);

                foreach (var item in x.Items)
                {
                    Console.WriteLine("\t {0}", item);
                }
            });

        input.LinkTo(action, new DataflowLinkOptions { PropagateCompletion = true });

        for (var idx = 1; idx <= 3; idx++)
        {
            var msg = new Message<int> { Id = idx, Items = Enumerable.Range(0, rnd.Next(0, 10)).ToList() };
            input.Post(msg);
        }

        input.Complete();
        action.Completion.Wait();

        Console.WriteLine("Done");
        Console.ReadKey();
    }

    private static async Task<Message<string>> Transform(Message<int> input)
    {
        var linkOpts = new DataflowLinkOptions { PropagateCompletion = true };

        var itr = new TransformManyBlock<IList<int>, int>(x => x);
        var multiply = new TransformBlock<int, int>(x => x * 10);
        var convert = new TransformBlock<int, string>(x => "STR-" + x);

        itr.LinkTo(multiply, linkOpts);
        multiply.LinkTo(convert, linkOpts);

        var pipeline = DataflowBlock.Encapsulate(itr, convert);

        pipeline.Post(input.Items);
        pipeline.Complete();

        var buffer = new BufferBlock<string>();
        pipeline.LinkTo(buffer);

        await pipeline.Completion;

        IList<string> items;
        if (!buffer.TryReceiveAll(out items))
        {
            items = new List<string>();
        }

        return new Message<string> { Id = input.Id, Items = items };
    }
}

Isn't it possible to rewrite the code to a single pipeline without
  creating an instance of a nested pipeline for each message?

It really seems a hard task because you are putting the pipeline building logic into the transform Method. Create a method to build your pipeline, it is really asking for it!

private static PipelineType _pipeline;
private static PipelineType BuildPipeline(Message<int> input){
    if(_pipeline != null){
        _pipeline.Post(input.Items);
        _pipeline.Complete();
        return _pipeline;
    }
    var linkOpts = new DataflowLinkOptions { PropagateCompletion = true };

    var itr = new TransformManyBlock<IList<int>, int>(x => x);
    var multiply = new TransformBlock<int, int>(x => x * 10);
    var convert = new TransformBlock<int, string>(x => "STR-" + x);

    itr.LinkTo(multiply, linkOpts);
    multiply.LinkTo(convert, linkOpts);

    _pipeline = DataflowBlock.Encapsulate(itr, convert);

    _pipeline.Post(input.Items);
    _pipeline.Complete();

    var buffer = new BufferBlock<string>();
    _pipeline.LinkTo(buffer);

    return _pipeline;
}

To be able to acess the buffer in your transform method you should set it public. But actually the best option would be that await pipeline.Completion would return the result you need.


Asking a user for the capital city of Peru, South America Can this Python code be written in a more Pythonic way?

'''
This scripts ask a user for the capital city of Peru, South America
'''

question = 'What is the capital city of Peru?'
answer = 'Lima'

# Ask question
print question

# Game continues as long as question is not answered
# Game ends after 3 failed attempts
end_game = False

# User has 2 attempts after entering the first wrong answer
attempts = 2

while end_game == False:
    # Get user answer
    user_answer = raw_input('Enter your answer: ').capitalize()

    # Validate users anser
    if user_answer == answer:
        print 'You got it right'
        end_game = True
    else:
        if attempts > 0:
            print 'Wrong! Try again. You have %d attempts left' %(attempts)
            attempts -= 1
        else:
            print 'You have no more attempts remaining'
            print 'The correct answer is %s' %(answer)
            print 'Oops!!! Game ended'
            end_game = True

It's kind of a limited code section, but let us go for a review ride:

Have everything enclosed in main() – The pythonic way of starting any code within a module is to have a main method called from the following if statement: if __name__ == '__main__':
Good naming of variables – You seem to name your variables good, that is in snake_case
Not so good while loop condition – Two slight errors here, first of all if using something like a flag it would have been better to do while not end_game instead of comparing against false. Even better would be to use your end of game indicator namely that there are no more attempts left: while attempts > 0:  (or possibly while attempts_left:
Introducing elif – The combination of else: immediately followed by an if can often be better written as elif (which reads as else if something)
Introducing the improved print() – In Python 3 the print is going to change into a function to make it everything a little more coherent, and whilst changing that, one could also get used to the format string syntax. Which changes print 'answer is %s' %(answer) into print('answer is {}'.format(answer))
Make functions multipurpose – Often it is good to make a function multi-purpose, albeit still letting it have one primary concern. In your case this could be asking for capital cities

With all of these changes we got the code looking like:

'''
Ask user for what is the capital city of a given land
'''

import random

def ask_for_capital_city(land, capital_city, attempts_left = 3):
    """Ask for the capital city of a land with 3 attempts by default"""
    question = 'What is the capital city of {}?'.format(land)
    answer = capital_city

    # Ask question
    print(question)

    while attempts_left:
        # Get user answer
        user_answer = raw_input('Enter your answer: ').capitalize()

        # Validate users answer
        if user_answer == answer:
            print('You got it right')
            return True

        elif attempts_left:
            attempts_left -= 1
            print('Wrong! Try again. You have {} attempts left'.format(attempts_left))

        else:
            print('You have no more attempts remaining.')
            print('The correct answer is {}'.format(answer))
            print('Oops!!! Game ended')

    return False

def main():
    capital_cities = [
       ('Peru', 'Lima'),
       ('the UK', 'London'),
       ('the US', 'Washington DC'),
       ('Norway', 'Oslo'),
       ('Spain', 'Madrid'),
       ('Portugal', 'Lisbon'),
       ('Brazil', 'Brasilia'),
    ]

    # Your original code
    ask_for_capital_city('Peru', 'Lima')

    # Lets test for some more capital cities
    correct_answers = 0

    while ask_for_capital_city(*random.choice(capital_cities)):
        correct_answers += 1
        print('You got {} correct capital cities\n'.format(correct_answers))

    print('Goodbye!')

if __name__ == '__main__':
    main()

Do extend the list at will!

NB! When presenting code here at Code Review, the code is supposed to work, and in your case there was a little indentation fault. A good tip to avoid that is to paste the code into the edit box, mark the entire code text and then to hit Ctrl + K which indents the code properly.


Generate voxel terrain with Perlin Noise For my chunk generator for my game, it currently uses a triple nested loop, which seems very inefficient. It also seems like I could cut down a lot of code in the function somehow. Does anyone have any ideas?

void Chunk::Generate() {
    const int octaves = 6;
    const float heightMod = 4.0f;
    const float densityMod = 8.0f;
    const float horizontalFrequency = 1.0f / 256.0f;
    const float frontalFrequency = 1.0f / 256.0f;
    const float heightMapSize = 1.0f / 512.0f;
    for (int z = m_chunkZ; z < m_chunkZ + m_chunkDepth; z++) {
        for (int x = m_chunkX; x < m_chunkX + m_chunkWidth; x++) {
            // the last type generated
            VoxelType lastType = VoxelType::SAND;
            // the height used for this part of the chunk
            int height = static_cast<int>(noise_fractal_brownian_motion(m_noise, octaves, x * horizontalFrequency, heightMapSize, z * frontalFrequency) * (m_chunkHeight * heightMod));
            int minY = m_chunkY;
            int maxY = m_chunkY + height;
            for (int y = minY; y < maxY; y++) {
                const float colorMinCap = -0.45f;
                const float colorMaxCap = 0.45f;
                const float densityXFrequency = 1.0f / 64.0f;
                const float densityZFrequency = 1.0f / 256.0f;
                const float verticalFrequency = 1.0f / (static_cast<float>(abs(height)) * heightMod);
                float density = noise_fractal_brownian_motion(m_noise, octaves, x * densityXFrequency, abs(y) * verticalFrequency, z * densityZFrequency) * (abs(height) * densityMod);
                // todo: new noise map for color
                float colorR = noise_fractal_brownian_motion(m_noise, octaves, x * densityXFrequency, 0.0f, z * densityZFrequency - 0.15f);
                float colorG = noise_fractal_brownian_motion(m_noise, octaves, x * densityXFrequency - 0.08f, 0.0f, z * densityZFrequency);
                float colorB = noise_fractal_brownian_motion(m_noise, octaves, x * densityXFrequency - 0.32f, 0.0f, z * densityZFrequency - 0.64f);
                if (colorR >= colorMaxCap)
                    colorR = colorMaxCap;
                if (colorG >= colorMaxCap)
                    colorG = colorMaxCap;
                if (colorB >= colorMaxCap)
                    colorB = colorMaxCap;
                if (colorR <= colorMinCap)
                    colorR = colorMinCap;
                if (colorG <= colorMinCap)
                    colorG = colorMinCap;
                if (colorB <= colorMinCap)
                    colorB = colorMinCap;
                if (density >= 0.0f) {
                    VoxelType type = ((y == maxY - 1 && lastType == VoxelType::DIRT) ? VoxelType::GRASS : _GetTypeFromY(y));
                    // check if we should replace a dirt type with grass
                    if (y == maxY - 1 && type == VoxelType::DIRT) type = VoxelType::GRASS;
                    if (type == VoxelType::WATER) {
                        m_transparentRenderer.AddVoxel(Position(x, y, z), Voxel(VoxelType::WATER, 0));
                    }
                    else {
                        if (y <= m_seaLevel)
                            m_underwaterRenderer.AddVoxel(Position(x, y, z), Voxel(type, colorR, colorG, colorB));
                        else
                            m_opaqueRenderer.AddVoxel(Position(x, y, z), Voxel(type, colorR, colorG, colorB));
                    }
                    lastType = _GetTypeFromY(y);
                }
            }
            // no matter what, add one water voxel at sea level
            m_transparentRenderer.AddVoxel(Position(x, m_seaLevel, z), Voxel(VoxelType::WATER, 0));
            // no matter what, add one sand voxel at 0 (bottom of the water)
            m_underwaterRenderer.AddVoxel(Position(x, 0, z), Voxel(VoxelType::SAND, 0));
            lastType = VoxelType::SAND;
        }
    }
}

For your:

            if (colorR >= colorMaxCap)
                colorR = colorMaxCap;
            if (colorG >= colorMaxCap)
                colorG = colorMaxCap;
            if (colorB >= colorMaxCap)
                colorB = colorMaxCap;
            if (colorR <= colorMinCap)
                colorR = colorMinCap;
            if (colorG <= colorMinCap)
                colorG = colorMinCap;
            if (colorB <= colorMinCap)
                colorB = colorMinCap;

This can be reduced using a suggestion from here:

inline float clip(float n, float lower, float upper) {
  return std::max(lower, std::min(n, upper));
}

And then do:

clip(colorR, colorMinCap, colorMaxCap);
clip(colorG, colorMinCap, colorMaxCap);
clip(colorB, colorMinCap, colorMaxCap);

I don't believe you will lose any performance from that.

Also, try adding OpenMP to your project and right before the first for loop add:

#pragma omp parallel for

This should parallelize the first loop (don't nest pragmas), and make your code run faster. Although, I am assuming (after a not too thorough review) that the any particular iteration does not depend on a previous iteration. Although it should, as Perlin Noise is "embarrassingly parallel".


Correcting coordinates of an image with polynomial root in python I want to optimize this for loop for correcting coordinates of an image, it takes too long which is not suited for my system. I have done some profiling, the numpy roots is taking most of the time (near to 90%). Could someone suggest some optimization or vectorization of the code? Or a better alternative?
src = cv2.imread('distorted_JJ.bmp')
dist_center = np.array([512, 224])
k1 = 0.15
k2 = 0.52

h,w,_ = src.shape
xc = dist_center[0]
yc = dist_center[1]

dst = np.zeros([h,w,3],dtype=np.uint8)
dst[::]=((255,0,0))

for i in range(h):
    for j in range(w):
        ru = np.array([j-xc, yc-i])/w
        p = [k2 , 0, k1, 0, 1, ru]
        abs_rd = np.roots(p)
        if i == yc and j == xc:
            rd = np.array([0,0])
        else:
            rd = ru * (p/abs_rd)

        v = np.array([xc/w + rd[0], yc/w - rd[1]])

        v = v*w
        v = v.astype(int)

        dst[i][j] = src[v[1],v[0]]

This is more of a suggestion as I don't have the time to code it, but it is perhaps too long for a comment.
From your code it seems that it is assumed that this fifth degree polynomial has only a single real root. It must have one, because the complex ones must come in conjugate pairs, but I don't see why it has only one.
I will assume it has an unique real root. Here's the idea:

Calculate abs_ru in a fast, vectorized manner.
Order these real values.
Take the smallest, use numpy.roots to find the corresponding unique real root.
Starting from this, consider the next abs_ru value and the corresponding polynomial. If this next abs_ru is far, then consider using numpy.roots again, else a few iteration steps using a root finding iteration should suffice. Consider a gradient descent on the square of the polynomial, or a Newton iteration.

A few things on the code as it is.
Root finding is generally done numerically, therefore it is perhaps better to consider the numeric roots that have a real value of an absolute value below say 1e-5 instead of ~np.iscomplex(abs_rd).
Root finding is expensive, and it is redundant if i == yc and j == xc. Move it to the else branch.


Are the sum of two numbers desired? Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add up to the any numbers in the second array.

\$-1 + 3 = 2 \therefore \text{True}\$

My algorithm simply takes all the pairs from the first input and check if they exist in second array set which the complexity of set lookup is \$O(1)\$. Overall complexity is \$O(n^2)\$ I'm pretty sure there should be a better algorithm leveraging hash tables or sorting and doing a binary search. Is there a way to make time complexity more efficient?

My code:

def arraySum(inputs, tests):
    # iterating through all possible sums and check if it exists in test by using a test set which
    #makes the complexity better with O(1) lookup in set.
    my_set=set(tests)
    for i in range(len(inputs)-1):
        for j in range(i+1,len(inputs)):
            my_sum=inputs[i]+inputs[j]
            if my_sum in my_set:
                return True
    return False #this will take care of an edge case when there is one input from each arr

I believe you could reduce it to \$O(n\log{n}+m\log{n}+n m)\$ if you want.

Sort the inputs, then iterate over the tests and for each one, do a two variable iteration over the inputs, where you start as close to the test value/2, and move one index in the increasing direction and the other in the decreasing direction depending on whether the sum is less than or greater than the test value.

This is somewhat confusing, so a partial implementation is:

def one_test(sorted_array, test_value):

    index1 = index_just_under(sorted_array, test_value/2)
    index2 = index1 + 1

    while (index1>=0) and (index2 < len(sorted_array)):
        sum = sorted_array[index1] + sorted_array[index2];
        if sum == test_value:
            return True
        if sum > test_value:
            index1 = index1 - 1
        else:
            index2 = index2 + 1

    return False

Function index_just_under would be an \$O(\log{n})\$ method to find our initial cut point.  It returns the number of entries in the array below the second parameter, minus 1.  Given a sorted array, a binary search can be used.

The rest of this one_test function is \$O(n)\$.  This function is executed \$m\$ times, and the initial sort is \$O(n\log{n})\$.

While this might be a poor savings of the two input arrays are the same size, if tests array is much smaller, this could be a big saving.

If you start the indexes at the 0 and len(sorted array) - 1, you might be able to eliminate the index_just_under() call, reducing the time by \$O(m\log{n})\$.  On the other hand, it would eliminate any early-outs in the \$O(n m)\$ loops.  Effectiveness could depend on your expected number ranges.


scan activedirectory for all users and their groups in domain with c# I wrote a method for a wpf app in .net core to get all users and their group by name if they are in a group from my active directory domaine.

public static void getGroupsWithUsers() {
    String currentDomain = Domain.GetCurrentDomain().ToString();

    using (PrincipalContext context = new PrincipalContext(ContextType.Domain, currentDomain))
    {
        using (PrincipalSearcher searcher = new PrincipalSearcher(new UserPrincipal(context)))
        {

            foreach (var result in searcher.FindAll())
            {
                DirectoryEntry de = result.GetUnderlyingObject() as DirectoryEntry;
                var SID = WindowsIdentity.GetCurrent().User.ToString();

                // find a user
                UserPrincipal user = UserPrincipal.FindByIdentity(context, de.Properties["samAccountName"].Value.ToString());

                if (user != null)
                {
                    // get the user's groups
                    var groups = user.GetAuthorizationGroups();

                    foreach (GroupPrincipal group in groups)
                    {
                        Console.WriteLine("User: " + user + " is in Group: " + group);
                    }

                }
            }
        }
    }

}

The method takes 1.5 to 1.8 seconds for a small amount of data and Im afraid that the execution time takes forever for real world data amounts.

I suspect you'd better off using a DirectorySearcher, but I don't know Active Directory services are supported by .NET Core.

Here is how I did it in .NET Framework (4.7.2).

Classes to hold the data I needed:

public class Account
{
    private Account(string name)
    {
        Name = name;
    }

    public Account(string name, List<DataCombination> groupData)
        : this(name)
    {
        GroupData = groupData;
    }

    public string Name { get; }

    public List<DataCombination> GroupData { get; }
}

public class DataCombination
{
    public string GroupName { get; set; }

    public string Account { get; set; }
}

The code that queries AD:

        var searchResults = new List<SearchResult>();

        using (var directoryEntry = new DirectoryEntry(directoryEntryPath))
        {
            directoryEntry.RefreshCache();

            using (var directorySearcher = new DirectorySearcher(directoryEntry))
            {
                directorySearcher.SearchRoot = directoryEntry;
                directorySearcher.SearchScope = SearchScope.Subtree;
                directorySearcher.PageSize = 1000;
                directorySearcher.Filter = filter;

                directorySearcher.PropertiesToLoad.Clear();
                directorySearcher.PropertiesToLoad.Add(PropertyName.Name);
                directorySearcher.PropertiesToLoad.Add(PropertyName.MemberOf);

                searchResults.AddRange(directorySearcher.FindAll().Cast<SearchResult>());
            }
        }

        var accounts = searchResults
            .Select(searchResult => _accountFactory.Execute(searchResult.Properties))
            .OrderBy(x => x.Name)
            .ToList();

        return accounts;

directoryEntryPath is an LDAP URI, starts with "LDAP://".
filter is used to filter using a list of user names and is filled by this method:

public static string Execute(IEnumerable<string> userNames)
{
    var filter = new StringBuilder();
    filter.Append("(&(objectClass=user)(|");

    foreach (var userName in userNames)
    {
        filter.Append($"(sAMAccountName={userName})");
    }

    filter.Append("))");

    return filter.ToString();
}

PropertyName is a class containing const strings:

internal static class PropertyName
{
    // https://msdn.microsoft.com/en-us/library/windows/desktop/ms675090.aspx
    public const string Name = "name";
    public const string LockoutTime = "lockoutTime";
    public const string UserAccountControl = "userAccountControl";
    public const string MemberOf = "memberOf";
    public const string DisplayName = "displayName";
}

This is the _accountFactory which converts the data returned by the DirectorySearcher into my classes:

internal class GroupAccountFactory : BaseDirectorySearcher, IAccountFactory
{
    public Account Execute(ResultPropertyCollection properties)
    {
        var accountName = GetValue<string>(properties, PropertyName.Name);

        var groupData = GetGroupData(properties, accountName);

        return new Account(accountName, groupData);
    }

    private List<DataCombination> GetGroupData(ResultPropertyCollection properties, string accountName)
    {
        var groupNames = new List<string>();

        foreach (var propertyValue in properties[PropertyName.MemberOf].Cast<string>())
        {
            groupNames.AddRange(propertyValue
                .Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries)
                .Select(part => part.Split('='))
                .Select(x => new
                {
                    Key = x[0],
                    Value = x[1],
                })
                .Where(x => x.Key == LdapDirectory.CommonName)
                .Select(x => x.Value));
        }

        return DataCombinationCollectionCreator.Execute(new HashSet<string>(groupNames), accountName);
    }
}

Its base class:

internal abstract class BaseDirectorySearcher
{
    protected T GetValue<T>(ResultPropertyCollection properties, string propertyName)
    {
        var value = PropertyValueRetriever.GetObject(properties, propertyName);
        if (value == null)
        {
            return default(T);
        }

        return (T)value;
    }
}

And that one uses:

internal class PropertyValueRetriever
{
    public static string GetString(ResultPropertyCollection properties, string propertyName)
    {
        var value = GetObject(properties, propertyName);

        return (string)value;
    }

    public static object GetObject(ResultPropertyCollection properties, string propertyName)
    {
        if (properties.Contains(propertyName)
            && properties[propertyName].Count > 0)
        {
            return properties[propertyName][0];
        }

        return null;
    }
}

You might have noticed this class:

internal class LdapDirectory
{
    public const string CommonName = "CN";
    public const string OrganizationalUnit = "OU";
    public const string DomainComponent = "DC";
}

And finally:

internal class DataCombinationCollectionCreator
{
    public static List<DataCombination> Execute(ICollection<string> groupNames, string accountName)
    {
        var groupData = new List<DataCombination>();

        foreach (var groupName in groupNames)
        {
            groupData.Add(CreateDataCombination(groupName, accountName));
        }

        return groupData;
    }

    private static DataCombination CreateDataCombination(string groupName, string accountName)
    {
        return new DataCombination
        {
            GroupName = groupName,
            Account = accountName
        };
    }
}

(Note that I have stripped away some of the extra logic that is present in my code which only applies for my purposes; thus the whole use of DataCombinationCollectionCreator might be overkill for you.)

It's all fairly self-explanatory. Whether it performs better than your code, I don't know: AD operations can be notoriously slow.


Integer Factorization using the Trial Division Algorithm I am trying to factor integers using the trial division algorithm (Wikipedia: http://en.wikipedia.org/wiki/Trial_division).

I reviewed the Wikipedia entry for trial division and multiple other sources but I don't completely understand the trial division algorithm.

I wrote the code below based on my findings and it finds all of the prime factors of a number.

For example, input 20 and you get its prime factors 2 2 5. I would like to know if it can be simplified or better written (I want to stick with the trial division algorithm --- I don't plan on inputting numbers any larger than 9,999)?

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Prime Number Checker</title>

A few comments :

Before writing any code, perform the computation manually. How would you do it for 20? You'd do something along the lines like :

let's try the first prime number : 2
is 2 a divisor of 20 ? yes, it is. 20 is 2*10 so let's add 2 to the list of divisors and let's focus on 10 now.
is 2 a divisor of 10 ? yes, it is. 10 is 2*5 so let's add 2 to the list of divisors and let's focus on 5 now.
let's consider the next prime number. It's 3. Oh, 3*3 is actually bigger than 5 so we won't be able to find any other prime factor smaller than 5 : let's add 5 to the list of divisors.
Try it yourself  with numbers such a 8, 100, 19....

Then, about your code : the first is I noticed that your loop condition is not right and you might get out of your array. Just try a value of n greater than 168 and you'll probably notice the issue.

If you want to follow the wiki page and to something like : for p in primes: if p*p > n: break what you really need to do is.

// Find prime factors
var n = 180;
var primeFactors = "";
// Trial division algorithm
for (var i = 0, p=primeNumbers[i]; i < primeNumbers.length && p*p<=n; i++, p=primeNumbers[i]) {
    while (n % p == 0) {
            primeFactors += " " + p + " ";
            n/=p;
    }
}
if (n>1)
{
    primeFactors += " " + n + " ";
}

document.getElementById("divSolution").innerHTML = primeFactors;

(Sorry for rewriting the whole code)


C++ lock free, single producer, single consumer queue Assumptions for use:

push() will only ever be called by a single thread.
pop() will only ever be called by a single thread.

Requirements:

push() needs to be as fast as possible. Requirements are stringent enough that I've determined that I can't use std::mutex (at least not in any way I've attempted to) as it is far too slow. (some initial stress tests took 6-8 ms without and 26-60 ms with std::mutex)

Code:

template<typename T>
class PCQueue {
    const size_t size;
    std::unique_ptr<T[]> contents;
    std::atomic<size_t> head;
    std::atomic<size_t> tail;
public:
    explicit PCQueue(size_t s) : size(s), contents(new T[s]), head(0), tail(0) {}

    //num of elements in ringbuffer (size - room())
    size_t count() {
        return (tail + size - head) % size;
    }

    //num of free spaces in ringbuffer (size - count())
    size_t room() {
        return (head + size - tail) % size;
    }

    void push(T t) {
        size_t newTail = (tail + 1) % size;
        if (newTail == head) {
            throw std::runtime_error("Pushing Full PCQueue");
        }
        contents[tail] = t;
        tail = newTail;//std::atomic implicitly memfences, so this op must occur after the "contents[tail] = t;"
    }

    T pop() {
        if (tail == head) {
            throw std::runtime_error("Popping Empty PCQueue");
        }
        T ret = contents[head];
        size_t newHead = (head + 1) % size;
        head = newHead;
        return ret;
    }
};

My testing has implied that this performs correctly (but I'd like to squeeze more speed out of it if possible), but I'm not entirely certain my assumption about the push method is correct (the comment regarding memory barriers), as I'm still getting a handle on those, and I'm not sure I understand how loads and stores can be reordered regarding atomic and non-atomic variables, with the various memory orders.  sequential consistency (the default) should enforce the desired behavior I think?

I'm worried that it's just working by coincidence (as concurrent code has a tendency to do), so a verification that my code is valid would be appreciated, as well as any general tips to improve it both in readability and performance.

Design

The problem with your implementation of pop() is that it can not be implemented in an exception safe manner (for any type of T). This is why the standard implementation implements this as two different methods top() and pop(). The top() function simply returns the value while pop() does not return the value but simply removes the value from head.

So usage would become:

T val = queue.top();
queue.pop();

Code Review

Your code assumes that T has a default constructor.

    std::unique_ptr<T[]> contents;

When you create the content with contents(new T[s]) you are allocating and initializing all the elements in that array using the default constructor.

In addition to this if T is very expensive you have just used a lot of effort to create the items that may never be used (or you wasted resources creating the objects that are just going to be destroyed when overwritten).

I would consider changing this to std::vector<T>. That way you don't create any un-required objects when first created.

This is fine:

    explicit PCQueue(size_t s) : size(s), contents(new T[s]), head(0), tail(0) {}

But you can make it more readable. Remember the point of code is to make the code maintainable.

    explicit PCQueue(size_t s)
        : size(s)
        , contents(new T[s])
        , head(0)
        , tail(0)
    {}

Is this the real definition of the function?

    //num of elements in ringbuffer (size - room())
    size_t count() {
        return (tail + size - head) % size;
    }

I would rename this function to reflect what the function is actually returning. I would also change the formula so it is easy to read. I would call this availableSpace(). The formula is: size - (head - tail).

This would be better named freeSpace().

    //num of free spaces in ringbuffer (size - count())
    size_t room() {
        return (head + size - tail) % size;
    }

You pass the parameter by value.

    void push(T t) {

This causes a copy to be made to pass it to the parameter. You should pass this by const reference (so there is no copy). If you want to get more advanced you could also pass by r-value reference which would allow you to move the object into your buffer rather than copying it.

    void push(T const& t) {   // Pass by const reference
    void push(T&& t) {        // Pass by r-value reference

The problem with the pop() as written you can not guarantee a clean removal. This is because you need to make several copies and if those copies fail you can leave the container in a bad state.

    T pop() {
        T ret = contents[head];              // Here is a copy.
        size_t newHead = (head + 1) % size;
        head = newHead;
        return ret;                          // Here is another copy.
    }

You did not define T so you don't have control over the copy assignment constructor. That is why it is usually split into two functions.

    // Return by reference
    // That way we can avoid any un-needed copies.
    T const& top() const {
        return contents[head];
    }
    // Simply remove the head item in the pop.
    void pop() {
        size_t newHead = (head + 1) % size;
        head = newHead;
    }


Finding the smallest missing positive number in an array Any suggestions to improve?

public class FindSmallestMissingPositive {
    public static void main(String args[]){
        int a[] = {3,5,4,-1,1,-1,0};
        System.out.println("Smallest Missing positive : "+ findSmPositive(a));
    }

    public static int findSmPositive(int input[]){
        int min = input[0];
        int max= input[0];

        HashSet<Integer> set = new HashSet<Integer>();

        for(int i=0;i<input.length;i++){
            set.add(input[i]);

            if(input[i]<min){
                min = input[i];
            }
            if(input[i]>max){
                max = input[i];
            }
        }

        for(int i=min;i<=max;i++){
            if(i>0 && !set.contains(i)){
                return i;
            }
            else continue;

        }
        return -1;
    }
}

Bugs

The implementation incorrectly gives -1 for all these input:

[0] should return 1
[1] should return 2
[2] should return 1
[0,2,2,1,1] should return 3
[1,2,2,1,3,1,0,4,0] should return 5

Improving the algorithm

The algorithm you used is \$O(n)\$ time and \$O(n)\$ space.
If you don't mind modifying the input array,
then you could reuse it as the storage,
making the algorithm \$O(1)\$ space.

Consider this alternative algorithm:

If the array is empty, return 1
Loop over the array indexes

While input[i] - 1 is a valid array index and not in the correct position, and input[input[i] - 1] is not in the correct position, then swap the elements i and input[i] - 1.

Loop over the array indexes again, and when you find a value not in the correct position, then return i + 1.
Return the last value + 1.

The logic behind this algorithm:

Swap elements into the correct position to get a sequence of positive integers 1, 2, 3, ...
Ignore values that cannot be in this array (<= 0 or too high index)
The beginning of the array will be filled with correct sequence values, gaps will be filled with junk, and the second looping pass will short-circuit on the first incorrect value

Strange coding style

Although these type declarations compile, they are not recommended:

public static void main(String args[]) {

public static int findSmPositive(int input[]) {

The recommended writing style:

public static void main(String[] args) {

public static int findSmPositive(int[] input) {

Also,
the code formatting style is not great, at many places it's too compact.
I suggest to copy paste into an IDE like IntelliJ or Eclipse and use the auto-formatting function to reformat nicely.

Testing your improvements

The problem description seems to match this one on leetcode.
After you implement your improvements,
I suggest posting there to verify the correctness of your implementation.

https://leetcode.com/problems/first-missing-positive/


Number of possible numbers in roman number string I just started learning programming a few months ago, and I'm intrigued by Haskell. To learn a bit I tried to adapt some code I have in Java so I can see what are equivalent solutions in Haskell.

The problem I had was to see how many different numbers can be “represented” by a string of roman numbers (0, .., 9, where X is equivalent to zero).

For example "I" means just one possible number (1), but "II" could be two possibilities: 11 (two "I") or 2 (one "II"). This is from some competitive programming website. Similar "XX" should give 1, since it represents 00 only. A bit bigger example: "IVII" should give 6, because there are 6 possibilities:

"I" + "V" + "I" + "I" = 1511
"I" + "V" + "II" = 152
"I" + "VI" + "I" = 161
"IV" + "I" + "I" = 411
"I" + "VII" = 17
"IV" + "II" = 42

Ok, that said, this is my Haskell code (first thing I write so far).

romanCombinations :: String -> Int
romanCombinations [] = 1
romanCombinations str = if length str == 1 then 1
  else foldr (+) 0 [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
  where
    sep = map (divide str) $ take (length str) [1..4]
    divide str n = (take n str, drop n str)
    possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

What would you change in this Haskell code? I've never written anything before. Anything is welcome since I will probably learn from every comment. (I'm not asking about algorithms, but anything is welcome too)

Use pattern matching to check for single-element lists

Let's start with romamCombination's second pattern:

romanCombinations str = if length str == 1 then 1

Compared to Java, length isn't a constant time operation in Haskell. It will traverse the whole list. If we only want to know if a list consists of a single element, we should pattern match to get a constant time behaviour:

romanCombinations [_] = 1

Use named variants of folds where applicable

Next, we will sum all elements in some list:

  -- we have to change the else due to the new pattern, but more on that later
  else foldr (+) 0 [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]

However, foldr (+) 0 is a common operation and therefore has a name in the Prelude: sum. We should use the named variant to convey our intend:

  else sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]

Similarly, divide is already in the Prelude, it's called splitAt, although the arguments are flipped:

  where
    divide str n = splitAt n str

Use Hoogle to find functions

But how would we find those functions? With Hoogle. If we search for Num a => \[a\] -> a, we will come across sum very soon, and if we search for [a] -> Int -> ([a], [a]), Hoogle will also find splitAt, even though the arguments are flipped.

Note that you sometimes need to use more general type signatures to find something with Hoogle.

All together so far

If we apply all those recommendations, we end up with

romanCombinations :: String -> Int
romanCombinations []  = 1
romanCombinations [_] = 1
romanCombinations str = sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
  where
    sep       = map (`splitAt` str) $ take (length str) [1..4]
    possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

Adjusting the length of a list by another list

We're already at the end. However, there is one last step we should take: get rid of the other length. That can be done with zip and map:

limit :: [a] -> [b] -> [b]
limit xs = map snd . zip  xs

In case you're not familiar with pointfree-code, it's the same as

limit :: [a] -> [b] -> [b]
limit xs ys = map snd (zip xs ys)

As zip will end whenever the shorter list is exhausted, this will limit str to at most 4 elements in [1..4] and of course limit [1..4] to at most length str.

We end up with

romanCombinations :: String -> Int
romanCombinations []  = 1
romanCombinations [_] = 1
romanCombinations str = sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
  where
    sep       = map (`splitAt` str) $ limit str [1..4]
    possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

limit :: [a] -> [b] -> [b]
limit xs = map snd . zip  xs

Bottom line

All in all, your original code was already easy to read, had type signatures and uses   simple splitting algorithm one can easily infer from your code. That being said, I haven't checked your algorithm or thought about improvements but only checked the code.

I recommend you to check the Prelude, as splitAt and sum are already available for your use without any import. Also, try to avoid length. Either work with the list immediately (e.g. map, fold, sum, ...) or pattern match.


Django query ManyToMany for tagged items I've got a item inventory that each inventory item is tagged with multiple tags. What I've got is an API that takes a query parameter with multiple comma separated query items and returns a list of all items that match all of the tags.

The following code is working, however this isn't really using the ManyToMany attributes in the Django models and I'm sure there is a better way to do this.

Schema ---

class InventoryTag(models.Model):
    class Meta:
        unique_together = ('key', 'value')

    key   = models.CharField(max_length=240, db_index=True)
    value = models.CharField(max_length=240, db_index=True)

class InventoryItem(models.Model):
    instance_id = models.CharField(max_length=255)

    created_at = models.DateTimeField(auto_now_add=True)
    updated_at = models.DateTimeField(auto_now=True)

    tags = models.ManyToManyField(InventoryTag, through='InventoryItemTag', through_fields=('item', 'tag'))

    def as_json(self):
        return serializers.serialize('json', [self])[0]

class InventoryItemTag(models.Model):
    class Meta:
        unique_together = ('item', 'tag')

    item = models.ForeignKey(InventoryItem, db_index=True, related_name='invitem')
    tag  = models.ForeignKey(InventoryTag, db_index=True, related_name='invtag')

    created_at = models.DateTimeField(auto_now_add=True)

Get Function --

def get(self, request, *args, **kwargs):
    query = request.GET.get('q', '').strip()
    start = int(request.GET.get('start', 0))
    count = int(request.GET.get('count', 50))

    query_items = [q.strip() for q in query.split(',') if q.strip()]

    items = InventoryItem.objects
    if query_items:
        for q in query_items:
            tags = InventoryTag.objects
            q = q.lstrip(':')
            if ':' in q:
                (k, v) = q.split(':', 1)
                tags = tags.filter(Q(key = k) & Q(value__startswith = v))
            else:
                tags = tags.filter(value__startswith = q)

            tags_pks = InventoryItemTag.objects.filter(Q(tag__in = tags.values_list('id')))
            items = items.filter(pk__in=tags_pks.values_list('item_id'))

    items = items.all()

How this is used:

InventoryItem -- For practical purpose this is an AWS instance with an instance_id
InventoryTag -- Other attributes of that instance (e.g. Name) or IP address. This is unique for any key/value pair of the tag.

You might have a set of instances like:

Item(id=1) -- tags:  name=dev.test zone=us-east-1a
Item(id=2) -- tags:  name=dev.vpc  zone=us-east-1a
Item(id=3) -- tags:  name=dev.cron zone=us-east-1a
Item(id=4) -- tags:  name=dev.test zone=us-east-1c
Item(id=5) -- tags:  name=dev.test zone=us-west-2a

So the goal is that you should be able to do a search where you ask for all name=dev.test and zone=us-east-1a machines and get item #1 and #4.

You are, more or less, manually performing in Python what can be achieved in SQL using Q objects. Basically, you can chain Q objects to create an SQL query on the InventoryItems with one WHERE clause for each part of your HTTP query.

Also note that, on queryset operations that will be converted to a WHERE clause (like get, filter...) as well as Q objects, the keywords arguments are ANDed together. So there is no need in doing tags.filter(Q(key = k) & Q(value__startswith = v)) since tags.filter(key=k, value__startswith=v) performs the same query and is more readable.

Building the tags research query should already include the lookup that span relationship and can be something like:

relevant_tags = Q()  # Fallback, if the query is empty will select everything
for tag_searched in query_items:
    tag_searched = tag_searched.lstrip(':')
    try:
        tag_name, tag_value = tag_searched.split(':', 1)
    except ValueError:
        # tag_searched did not contain any :
        query = Q(tags__value__startswith=tag_searched)
    else:
        query = Q(tags__key=tag_name, tags__value__startswith=tag_value)

    relevant_tags = relevant_tags & query

And from there, we can retrieve objects we want in a single query:

items = InventoryItems.objects.filter(relevant_tags)

A few things to note:

if iterable just before for element in iterable is pointless as the for loop will be a no-op anyway if the iterable is empty;
you can use EAFP rather than LBYL, especially if you expect one path to happen more frequently than the other. I made a wild guess that the user will use the name:value syntax of the query more often than the simple value one. It is also to show an alternate syntax.
you can clean your query better in the list-comprehension to avoid an extra lstrip in the computation. Or you can avoid the list-comp and perform the whole cleanup in the for loop:

for tag_searched in query.split(','):
    tag_searched = tag_searched.strip().lstrip(':')
    if not tag_searched:
        continue
    ...

you never use start or count, you should remove them.


Iterating an array of nodes, each of which can have children I've written some C# (7) code to iterate through a Node[], listing all of its nodes in order (i.e. child elements are listed immediately after the parent).

Each Node is defined as follows,

class Node
{
    public string Name { get; set; }

    public List<Node> Children { get; set; } = new List<Node>();

    public bool HasChildren => Children.Count > 0;

    public Node(int n)
    {
        Name = $"Node #{n}";
    }

    public Node AddChild(Node n)
    {
        Children.Add(n);
        return this;
    }

    public override string ToString() => Name;
}

The collection of nodes to be iterated would be,

var nodes = new Node[]
{
    new Node(1),
    new Node(2),
    new Node(3)
        .AddChild(new Node(4))
        .AddChild(new Node(5))
        .AddChild(new Node(6)
            .AddChild(new Node(7)))
        .AddChild(new Node(8)
            .AddChild(new Node(9))
            .AddChild(new Node(10)))
};

...and output for the above would be 10 lines of "Node #", each followed by the number passed to the constructor of each (i.e. 1 to 10, in ascending order).

The code I've written to perfom the aforementioned task is,

var stack = new Stack<(Node[], int)>();

var i = 0;

while (i < nodes.Length)
{
    WriteLine($"{nodes[i]}");

    if (nodes[i].HasChildren)
    {
        // Stores away the current Node[] and the next index, to return to it once all children are iterated though.
        stack.Push((nodes, i + 1));

        // Makes the child Node[] the iteration target.
        nodes = nodes[i].Children.ToArray();

        // Resets the index to iterate all the children.
        i = 0;

        continue;
    }

    // If the current node is the last in the targeted Node[], and there are parent Node[]s from which this Node[] was switched to in the stack.
    if (i == nodes.Length - 1 && stack.Count > 0)
    {
        // Pop the stack until the popped Node[] isn't the last element, and assign it to the array being iterated.

        var (_target, _i) = stack.Pop();

        while (stack.Count > 0 && _i >= _target.Length)
        {
            (_target, _i) = stack.Pop();
        }

        nodes = _target;
        i = _i;

        continue;
    }

    ++i;
}

Do provide me with constructive criticism of my algorithm.
Does it work for Node[]s of any depth (level of child-ception ;)?
Are there ways in which it can be optimized?

N.B. (T1, T2) is equivalent to a Tuple (see: C# 7's System.ValueTuple)

Collection initializer
You can improve and simplify your code by first tuning the Node.

make it IEnumerable<T> and consequently remove the Children and HasChildren properties because now we can use LINQ's Any
let the Name property take care of the formatting and keep the value clean in a dedicated field
replace AddChild with the Add method to be able to use collection initializer
replace the array with a root node

Example:
public class Node<T> : IEnumerable<Node<T>>
{
    private readonly T _value;

    private readonly List<Node<T>> _children = new List<Node<T>>();

    public Node(T value) => _value = value;

    public T Value => _value;

    public string Name => $"Node #{_value}";

    public void Add(Node<T> node) => _children.Add(node);

    public override string ToString() => Name;

    public IEnumerator<Node<T>> GetEnumerator() => _children.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Enumerator
Now you can improve the algorithm by using the Enumerator. There is no need for any indexes or tuples. What you need to do is to GetEnumerator from each node and MoveNext on it until it is now longer possible to continue or continue from a sub node if it contains Any.
The enumerator will keep the current state allowing you to continue iterating on child nodes and resume from the parent node later that's why you need to re-push the current node back to the stack.
An extension for the Node<T> could look like this:
public static IEnumerable<Node<T>> Flatten<T>(this Node<T> root)
{
    var stack = new Stack<IEnumerator<Node<T>>>();
    stack.Push(root.GetEnumerator()); // start with the root node

    yield return root; // return the root node

    while (stack.Any())
    {
        var node = stack.Pop();
        while (node.MoveNext())
        {
            yield return node.Current;
            if (node.Current.Any())
            {
                stack.Push(node); // re-add the node to continue later
                stack.Push(node.Current.GetEnumerator()); // continue from here now
                break; // we'll continue from "node" later, when node.Current is enumerated
            }
        }
    }
}

Example
You can now create nodes like arrays without confusing parenthesess when adding subnodes:
var nodes = new Node<int>(0)
{
    new Node<int>(1),
    new Node<int>(2),
    new Node<int>(3)
    {
        new Node<int>(4),
        new Node<int>(5)
        {
            new Node<int>(6)
            {
                new Node<int>(7)
            },
            new Node<int>(8)
            {
                new Node<int>(9),
                new Node<int>(10)
            },
            new Node<int>(11)
        }
    },
    new Node<int>(12)
};

after flattening it
nodes.Flatten().Select(n => n.Name).Dump();

you'll get:

Node #0
Node #1
Node #2
Node #3
Node #4
Node #5
Node #6
Node #7
Node #8
Node #9
Node #10
Node #11
Node #12


Javascript Stringify Nested Objects with Loop References I created these functions that will take any object and stringify it, and can then de-stringify it later.

function stringify(objectToCopy, exceptionClasses = []) {

    // Listify.
    var objects = [];

    var que = [objectToCopy];
    while(que.length > 0){
        var o = que.pop();
        objects.push(o);
        var propNames = Object.getOwnPropertyNames(o);
        for (let i = 0; i < propNames.length; i++) {
            const n = propNames[i];
            var property = o[n];
            if (
                typeof property == "object" && property != null &&
                objects.indexOf(property) == -1 &&
                que.indexOf(property) == -1 &&
                exceptionClasses.indexOf(property.constructor.name) == -1
            ) {
                que.push(property);
            }
        }
    }

    // Stringify.
    var stringifiedList = [];

    for (let i = 0; i < objects.length; i++) {
        const o = objects[i];

        var temp = {
            "className": o.constructor.name,
            "properties": [],
        };

        var propNames = Object.getOwnPropertyNames(o);
        for (let i = 0; i < propNames.length; i++) {
            const n = propNames[i];
            var property = o[n];
            if (typeof property == "object" && property != null){
                if (exceptionClasses.indexOf(property.constructor.name) == -1) {
                    temp.properties.push({
                        "isObject": true,
                        "name": n,
                        "content": objects.indexOf(property), // content will here refer to the index of where the object is.
                    });
                }
            }else{
                var content = JSON.stringify(property);
                if (content == null) {
                    content = null; // Converts from undefined to null.
                }
                temp.properties.push({
                    "isObject": false,
                    "name": n,
                    "content": content,
                });
            }
        }

        stringifiedList.push(temp);
    }

    //
    return JSON.stringify(stringifiedList);
}
function deStringify (string) {
    var stringifiedList = JSON.parse(string);

    // Listify.
    var objects = [];
    for (let i = 0; i < stringifiedList.length; i++) {
        const data = stringifiedList[i];

        var cleanName = /[a-zA-Z_$][0-9a-zA-Z_$]*/.exec(data.className).toString();

        if (cleanName != data.className) {
            throw "ERROR: Class name validation failed."
        }

        var newObject = Object.create(eval(cleanName).prototype);
        objects.push(newObject);
    }

    // Destringify
    for (let i = 0; i < stringifiedList.length; i++) {
        const data = stringifiedList[i];
        const obj = objects[i];

        for (let j = 0; j < data.properties.length; j++) {
            const property = data.properties[j];
            if (property.isObject){
                obj[property.name] = objects[property.content];
            }else{
                obj[property.name] = JSON.parse(property.content);
            }
        }
    }

    return objects[0];
}

// Testing.
var a = [6,5,4,3];
var b = [a, a, "alpha", "beta"];
b.push(b);
a.push(b);

var s = stringify(a);
console.log(deStringify(s));

/* Output:
(5) [6, 5, 4, 3, Array(5)]
    0:  6
    1:  5
    2:  4
    3:  3
    4:  Array(5)
        0:  (5) [6, 5, 4, 3, Array(5)]
        1:  (5) [6, 5, 4, 3, Array(5)]
        2:  "alpha"
        3:  "beta"
        4:  (5) [Array(5), Array(5), "alpha", "beta", Array(5)]
        length: 5
        __proto__:  Array(0)
    length: 5
    __proto__:  Array(0)
*/

The reason I don't only use JSON.stringify() is because it does not conserve the prototype, and also does not support loop references. Is this approach hacky? Is there something about the objects I duplicate that I am missing when I only duplicate its properties? I know this code doesn't work for DOM objects or objects related to webgl.

JSON.stringify() and JSON.parse() were meant to serialize and deserialize data. This is why it omits non-data (functions, regex, etc.) on purpose. When you mention serializing prototypes, you are serializing behavior and object relationships, not data. It's the same reason why JSON is preferred over XML for AJAX, because JSON is a data exchange format while XML is a document format.

I suggest you rethink your approach before this becomes a rabbit hole.

FWIW, JSON.serialize() accepts a replacer function as second arg, while JSON.parse() accepts a reviver function as second arg. If what you're building is some kind of object mapper, you can use the replacer to insert metadata about the constructor for that instance, and use the reviver to pick up that metadata and customize how that object instance is created.


Handling keyboard shortcuts in C# software Edit: I have added the revised code in an answer to this question.

Currently, I handle the keyboard shortcuts of my applications in a single huge method that looks like this:

    protected override bool ProcessCmdKey(ref Message msg, Keys keyData)
    {
        // Next issue (validate the fix)
        if (keyData == (Keys.Control | Keys.Enter) ||
            keyData == (Keys.Shift | Keys.Enter))
        {
            mark_as_fixed();
            return true;
        }
        // Skip to next issue without validating or changing anything
        if (keyData == (Keys.Alt | Keys.Down))
        {
            next_issue();
        }
        // Previous issue
        if (keyData == (Keys.Alt | Keys.Up))
        {
            previous_issue();
            return true;
        }
        ... [130 lines of this]

It works perfectly, it isn't particularly hard to read or maintain, but having a method 130 lines long and constantly growing just feels wrong.

Also I may want to implement shortcut customization in the future, and there is no easy way to find out what keys are mapped to which method so it will have to be rewritten.

Since all non trivial applications have a gazillion shortcuts, I assume it's a solved problem, but I couldn't find a good explanation on how applications handle their shortcuts.

Also I may want to implement shortcut customization in the future, and there is no easy way to find out what keys are mapped to which method so it will have to be rewritten.

Stop right here! Extract a class for each command (e.g. instead of a mark_as_fixed method, you'll have a MarkAsFixedCommand class). If you're using WPF you can implement the ICommand interface and have nevermind, you're using WinForms. Still, extract the command classes - WPF's ICommand is a really simple interface that merely exposes bool CanExcute(object) and void Execute(object) methods (you don't have to implement the object parameter if you don't need it) - by extracting your logic into command classes, you can prepare the ground for the day you redo your UI with WPF (which you should!).

  there is no easy way to find out what keys are mapped to which method

Make one! Have your command classes derive from an abstract CommandBase class that exposes a method for it:

public abstract bool IsShortcutKey(Keys keys);

Now every derived command class has to implement this IsShortcutKey method. The implementation for MarkAsFixedCommand could look like this:

public override bool IsShortcutKey(Keys keys)
{
    return keys == (Keys.Control | Keys.Enter)
        || keys == (Keys.Shift | Keys.Enter);
}

A cleaner way would have been to expose some Keys ShortcutKey { get; } property getter, but that wouldn't play nice with multiple shortcuts for the same command.

Anyway now that each command implementation is responsible for is shortcut key logic, you can easily fetch the configuration and make that method return true when keys matches whatever Keys value you have in your config.

Then, whoever runs this ProcessCmdKey method simply needs to know about all available commands - take them as an IEnumerable<CommandBase> constructor parameter and let whoever is calling this constructor deal with providing it with the command instances (which you will acquire with some reflection code).

Now ProcessCmdKey can be as simple as this:

// assume only 1 command returns true for specified keyData value:
var command = _commands.SingleOrDefault(cmd => cmd.IsShortcutKey(keyData));
if (command != null && command.CanExecute())
{
    command.Execute();
    return true;
}

return base.ProcessCmdKey(ref msg, keyData);

PS - Method names should be PascalCase, not lower_snake_case.


Reading in millions of lines of AOL query logs for query suggestion/expansion I am working on a query suggestion program, and to faciliate this, I am reading in millions of AOL queries logs. The logs have this format:

AnonID  Query   QueryTime
479 family guy  2006-03-01 16:01:20
479 family guy movie references 2006-03-03 22:37:46
479 top grossing movies of all time 2006-03-03 22:42:42
479 car decals  2006-03-03 23:20:12
479 car window decals   2006-03-03 23:24:05
479 car window sponsor decals   2006-03-03 23:27:17
479 car sponsor decals  2006-03-03 23:28:59
...

Where each "column" is separated by a tab character.

This following code reads in the AOL Query logs into a Guava MultiMap (to allow duplicates) and then puts those into an Apache-Collections PatriciaTrie so that prefixes can be grabbed efficiently for future query suggestion/expansion.

private void readInAolQueries(String directory)
{
    try (Stream<Path> paths = Files.walk(Paths.get(directory)))
    {
        Multimap<String, QueryLog> multimap = TreeMultimap.create();
        paths
                .filter(Files::isRegularFile)
                .filter(path -> path.toString().endsWith(".txt"))
                .filter(path -> path.toString().contains("Clean-Data-"))
                .forEach(path ->
                {
                    String fileName = path.toString();
                    List<QueryLog> queryLogs = new AolQueryLogsProcessor(fileName).getQueryLogs();
                    // Read logs into a multimap to preserve duplicates
                    multimap.putAll(Multimaps.index(queryLogs, QueryLog::getQueryString));
                });
        //Put the multimap into the trie. It now also has duplicates.
        queryTrie.addAll(multimap.asMap());
    }
    catch (IOException e)
    {
        e.printStackTrace();
    }
}

The AOL logs files are in my resources directory (which is passed into the readInAolQueries method), and the files all have the form Clean-Data-XX.txt where XX is a number.

Here is the code for the AolQueryLogsProcessor class from the code above:

public class AolQueryLogsProcessor
{
    private List<QueryLog> queryLogs;

    public AolQueryLogsProcessor(String fileName)
    {
        queryLogs = new ArrayList<>();
        try
        {
            List<String[]> lines = readFile(fileName)
                    .stream()
                    .filter(line -> !line.isEmpty())
                    .map(line -> line.split("\t"))
                    .collect(Collectors.toCollection(ArrayList<String[]>::new));

            //Dates looks like this 2006-03-28 20:39:58
            final DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss");

            //The first line is the header. Skip it.
            for (int i = 1; i < lines.size(); ++i)
            {
                String anonId = lines.get(i)[0];
                String[] query = lines.get(i)[1].split("\\s");
                LocalDateTime timeStamp = LocalDateTime.parse(lines.get(i)[2], formatter);
                QueryLog log = new QueryLog(anonId, query, timeStamp);
                queryLogs.add(log);
            }
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
    }

    private List<String> readFile(String fileName) throws IOException
    {
        return Files.readAllLines(Paths.get(fileName), Charset.forName("UTF-8"));
    }

    public List<QueryLog> getQueryLogs()
    {
        return Collections.unmodifiableList(queryLogs);
    }
}

I'm using a lot of Java 8 Streams, lambdas, and the like because I am trying to familiarize myself with them.

I'm looking for a better and more efficient way to read in the millions of query logs. On my reasonably fast computer, it takes 45-50 seconds to read in all of the logs.

Is there something I can do to speed up this whole process?

Maybe some of my answers and thoughts from this thread (Scanning through logs (tail -f fashion) parsing and sending to a remote server) can help you.

What I want to point out: It's very important, to measure. If you just post a piece of code and tell, it takes that amount of time and ask, how to increase 'performance', it's usually ghost hunting. If you can reduce the time of a routine by 99% but it only takes 1% of the overall time - you just wasted your time.

My main concern about the app is the use case: You're reading millions of lines into memory into a tree structure for further processing/querying - at least that's my interpretation. Have you thought about using an indexing library, such as Apache Lucene? Usually, people invest more time in better response times, instead of "indexing times" - which is, of course, also important, if you have a real-time or near-real-time requirement. But then I would analyze the software architecture first.

Other than that, I can't identify any major problem with the code. One problem could be the garbage collector, since millions of lines are using a lot of memory. And more memory means more memory managament. But that has to measured too and also analyzed in detail. Playing around with collectors, heap sizes, collector threads and so on, can improve throughput significantly.

Hope this helps,

slowy


Expression tree in Haskell with support for differentiation A simple binary expression tree in Haskell without operator precedence and without parentheses.

Any comments would be much appreciated.

data Tree a= Const a
       | X
       | Plus (Tree a) (Tree a)
       | Mult (Tree a) (Tree a)
       | Minus (Tree a) (Tree a)
       | Div (Tree a) (Tree a)
       | Power (Tree a) (Tree a)
       | Cos (Tree a)
       | Sin (Tree a)
deriving Show

eval :: ( Eq t, Floating t) => Tree t-> t -> Maybe t
eval (Const a) x =  Just  (a)
eval X x =  Just x
eval (Plus a b) x = (+) <$> eval a x <*> eval b x
eval (Mult a b) x =  (*) <$> eval a x <*> eval b x
eval (Minus a b) x =  (-) <$> eval a x <*> eval b x
eval (Power a b) x =  (**) <$> eval a x <*> eval b x
eval (Div a b) x =  if (eval b x) == (Just 0) then Nothing else (/) <$> eval a x <*> eval b x
eval (Cos a) x =(cos) <$> eval a x
eval (Sin a) x = (cos) <$> eval a x

dif :: ( Eq t, Floating t) => Tree t->Tree t
dif (Const a)  = Const 0
dif X  =  Const 1
dif (Plus a b)  =Plus (dif a) (dif b )
dif (Mult a b)  =  Plus (Mult (dif a) b) (Mult  a (dif b))
dif (Minus a b)  =  Minus (dif a) (dif b)
dif (Div a b) =  Div (Minus (Mult (dif a) b) (Mult  a (dif b))) (Mult b b)
dif (Power (Const a) (Const b)) = Const 0
dif (Power a (Const b)) = Mult (Const b) (Power X (Minus (Const b) (Const 1)))
dif (Cos a) = Minus (Const 0) (Mult (dif a) (Sin a))
dif (Sin a) = (Mult (dif a) (Cos a))

You have a copy-and-paste error here:

eval (Cos a) x =(cos) <$> eval a x
eval (Sin a) x = (cos) <$> eval a x


Ulam numbers (calculates your life expectancy if you want to) I'm new to Java and wanted to present to you my latest project: Ulam Numbers

/**

 * This class consists of some instance variables a constructor and some getter and setter methods
 * It is supposed to implement the Ulam numbers which are named after Stanislav Ulam
 * Furthermore we will make use of the numbers to calculate/foresee how old you or me will become
 * If this made you curious just enter your own birthday or that of a relative but be warned it might
 * shock you to death.. Hehe..
 *
 * @author  Jae
 * @version 1.0
 */
public class UlamNumber {

 private int number;

 /**
  * This is a constructor which is pretty self-explaining
  *
 * @param number
 * describes the number the user can input like for example his/her birthday
 */
public UlamNumber(int number) {
     this.number = number;
 }

 /**
 * This is a method without parameters which implements the ulam algorithm
 * Furthermore it calculates your "age" by counting how many steps are needed till
 * you reach the number 1 and gives it out on the console
 */
public void ulamAlgorithm() {

     int counter = 0;

     while (number != 1) {
     if (number % 2 == 0) {
         number = number / 2;
         counter++;
         } else if (number % 2 != 0) {
             number = (number * 3) + 1;
             counter++;
         }
     }

     if (counter == 1) {
         System.out.println("Unfortunately you will only become: " + counter + "  years old >:-)");
     } else if (counter < 100) {
         System.out.println("Unfortunately you will only become: " + counter + " years old =(");
     } else {
         System.out.println("Congratulation you will become " + counter + " years old =)");
     }
 }

/**
 * This is a getter method which is pretty self-explaining
 *
 * @return number
 * is from the type integer which returns the current value of number
 */
public int getNumber() {
    return number;
}

/**
 * This is a setter method which is pretty self-explaining
 *
 * @param number
 * is from the type integer which an user can input to change the current value of number
 */
public void setNumber(int number) {
    this.number = number;
}
}

I'm sorry but I didn't write an explanation to the above stated things. You can also see this in my bad javadocs. If you have any hints/tips for improvements, please let me know.

This is a senseless use of objects.  What exactly is an UlamNumber object?  Consider how you might use this class:

 UlamNumber ulam = new UlamNumber(0);
 ulam.setNumber(20);
 ulam.ulamAlgorithm();    // ← prints something about your age
 ulam.getNumber();        // ← returns 1, not 20

That code tells you nothing about the task that it performs (if you ignore the comments).  In particular, ulamAlgorithm() does several things (count steps, compose a remark, and print it) — none of which is obvious from the name of the function.

What you want to write is

System.out.println(AgeCommenter.commentAbout(UlamSequence.countSteps(20)));

To make that happen:

public class UlamSequence {
    public static int countSteps(long number) {
        int steps;
        for (steps = 0; number > 1; steps++) {
            number = (number % 2 == 0) ? number / 2
                                       : 3 * number + 1;
        }
        return steps;
    }
}

Note the use of the for-loop for counting.

And the AgeCommenter:

public class AgeCommenter {
    public static String commentAbout(int age) {
        String fmt =
            (age ==  1) ? "Unfortunately you will only become: %d year old >:=)"
          : (age < 100) ? "Unfortunately you will only become: %d years old =("
          :               "Congratulations, you will become %d years old =)";
        return String.format(fmt, age);
    }
}


Scamble a vector, preserving the sum My first crack at clojure... if you have time to provide input, I'd appreciate it. I'm as much interested in style as proper usage. I'm just getting started.

The task to start with an vector of N zeros, and then "scramble" it by: Select 2 items in the vector. If one is less than 4, and the other is greater than -4, increment one and decrement the other -- so that the sum of the vector remains the same.

am I abusing let?
this generates a sequence of vectors, and I take the last one. Is there a better way to iterate and get the last result?
what tricks that I've missed?
this is just a small sample ;) but what community standards and practices have I missed?

code

(defn level [c] (let [n+ (rand-int (count c))
               n- (rand-int (count c))
               v+ (inc (nth c n+))
               v- (dec (nth c n-))
               go (and (not= n+ n-) (< v+ 4) (> v- -4))
               ]
           (if go (assoc (assoc c n+ v+) n- v-) c)
           ))

(defn rseq [n]
      (let [first (vec (repeat n 0))]
        (last (take (* n 2) (iterate level first)))))

(rseq 16)

(deftest rseq-sum-equals-2
  (let [actual (rseq 16)]
  (is (= 0 (apply + actual)))))
(run-tests 'ursound.core)

I am also relatively new to Clojure, but here are my first thoughts:

I like that you work with a vector, because random access of vectors with (nth) and assoc is faster. I also like your naming. thanks for providing a deftest, but please, user a proper inlining.
(assoc)'s do not need to be nested: (assoc (assoc c n+ v+) n- v-) is the same as (assoc c n+ v+ n- v-).
(last (take n x)) can be written as (nth x n).
Warning: you use the name 'first in yout (let), but this name is already defined in clojure.core.
For a style guide, please see https://github.com/bbatsov/clojure-style-guide

That is all for now, and I hope you found some advice useful.