Making the controller clean and readable in (Ruby on Rails) I have this rails controller which works fine but a lot of business logic is confined in the controller which I believe is not a good practice.
class MoviesController < ApplicationController
  before_action :set_movie, only: [ :edit, :update, :destroy ]
  rescue_from ActiveRecord::RecordNotFound, with: :render_404

  def index
    year = params[:year].split('-') unless params[:year].nil?
    starting_year = year[0] unless year.nil? || year.empty?
    ending_year = year[year.length - 1] unless year.nil? || year.empty?
    genre = params[:genre][0] unless params[:genre].nil?
    language = params[:language][0] unless params[:language].nil?
    quality = params[:quality][0] unless params[:quality].nil?
    rating = params[:rating_bound][0] unless params[:rating_bound].nil?
    order_by = params[:orders_filter][0] unless params[:orders_filter].nil?
    @movies = Movie.search_title(params[:title]).search_language(language).search_on_starting_year(starting_year).search_on_ending_year(ending_year).search_video_quality(quality).search_genre(
      genre
    ).search_rating(rating).order_on_filter(order_by).includes(:profile_photo)
  end

  def show
    @movie = Movie.includes(
      :profile_photo, :created_by, movie_roles: [:actor], feedback: [:user]
    ).left_outer_joins(:likes, :ratings).select(
      'movies.*, CAST(AVG(ratings.value) AS DECIMAL(10,1)) AS rating, count(likes.likeable_id) * 6 as total_likes'
    ).find params[:id]
    @reviews = @movie.feedback.select { |item| item.type == 'Review' }
    @comments = @movie.feedback.select { |item| item.type == 'Comment' }
    @directors = @movie.movie_roles.select { |role| role.role_played == 'director' }
    @actors = @movie.movie_roles.select { |role| role.role_played == 'actor' }
  end

  def new
    @movie = Movie.new
    @movie.build_profile_photo
  end

  def edit
  end

  def render_404
    render file: "#{Rails.root}/public/404", status: :not_found
  end

  # POST /movies
  # POST /movies.json
  def create
    parameters = movie_params
    @movie = Movie.new(parameters)
    @movie.created_by = current_user

    if @movie.save
      redirect_to @movie, notice: 'Movie was successfully created.'
    else
      render :new, notice: 'Not Saved!'
    end
 end

  def update
    respond_to do |format|
      if @movie.update(movie_params)
        format.html { redirect_to @movie, notice: 'Movie was successfully updated.' }
        format.json { render :show, status: :ok, location: @movie }
      else
        format.html { render :edit }
        format.json { render json: @movie.errors, status: :unprocessable_entity }
      end
    end
  end

  def destroy
    @movie.destroy
    respond_to do |format|
      format.html { redirect_to movies_url, notice: 'Movie was successfully destroyed.' }
      format.json { head :no_content }
    end
  end

  private
  # Use callbacks to share common setup or constraints between actions.
  def set_movie
    @movie = Movie.find(params[:id])
  end

  # Only allow a list of trusted parameters through.
  def movie_params
    params.fetch(:movie, {}).permit(:name, :release_date, :video_quality, :synopsis, :genres, :language)
    params.fetch(:movie, {}).permit(:name, :release_date, :video_quality, :synopsis, :genres, :language, profile_photo_attributes: [:path])
  end
end

I need to shrink the controller size and make the code look much clear and readable!

One thing you can do to simplify your controllers is use something like the scaffolding gem https://github.com/tubbo/controller_resources - that would reduce some of the boilerplate code.
For the #index method I would rewrite it chainging relations something like
  def index
    @movies = Movie.all.includes(:profile_photo)
    if params[:year].present?
      years = params[:year].split('-')
      @movies = @movies.search_on_ending_year(years.first)
      @movies = @movies.search_on_ending_year(years.last)
    end
    @movies = @movies.search_genre( params[:genre].first ) if params[:genre].present?
    # etc
    @movies = @movies.order_on_filter(params[:orders_filter].filter) if params[:orders_filter].present?
  end

If you define your scopes something like
scope search_on_ending_year, ->(year) { year ? some_condition : all }
then you can also remove the conditionals above
Note that you can combine that a simple way to check both nil? and empty? in one step is to use blank?. Likewise present? is very universal and checks that values are not nil, strings are not blank, arrays are not empty, etc
In the movie_params method
  def movie_params
    params.fetch(:movie, {}).permit(:name, :release_date, :video_quality, :synopsis, :genres, :language)
    params.fetch(:movie, {}).permit(:name, :release_date, :video_quality, :synopsis, :genres, :language, profile_photo_attributes: [:path])
  end

the first line is both redundant and ignored
I think your code would also be simpler if you structured your html to avoid array parameters like this params[:orders_filter][0]


Access View from current/corresponding ViewModel Sometimes when developing a WPF application, I need to access a certain Window (View) from the corresponding ViewModel, to perform or fire a method like this for example:

//In the MainWindowViewModel
MainWindowView.Hide();

But that's not really easy, and even it violates MVVM because the ViewModel shouldn't know anything about the View, so I started doing this instead:

//In the MainWindowViewModel
Application.Current.MainWindow.Hide();

This becomes impractical when dealing with other Windows (Views):

//In the AnotherWindowView
Application.Current.Windows.OfType<AnotherWindowView>().First().Hide();

So I decided to make a solution, a helper class, in which, using a method, I give the ViewModel and I get back the corresponding View, using the DataContext of the View, the solution looks like this:

The Class:

public static class ViewsAccessibility
{
    public static Window GetCorresponingWindow(ViewModelBase viewModel)
    {
        var windowAccessibility = new WindowAccessibility(viewModel);
        return windowAccessibility.CorrespondanteWindow;
    }

    private class WindowAccessibility
    {
        public Window CorrespondanteWindow { get; private set; }

        public WindowAccessibility(ViewModelBase viewModel)
        {
            var windows = Application.Current.Windows.OfType<Window>();
            CorrespondanteWindow = (from window in windows
                                      where window.DataContext.Equals(viewModel)
                                      select window).First();
        }
    }
}

The use:

//In the MainWindowViewModel
ViewsAccessibility.GetCorresponingWindow(this).Hide();

Is this a good practice and does it violate MVVM or not?

You have multiple options

a. Use an event Aggregator where publish the message from the viewmodel and subscribe from view. see prism documentation for event aggregators:here is sample code

 //view will subscribe from this message
_aggregator.GetEvent<CloseEvent>().Subscribe(CloseAction);

 private void CloseAction(string s) { //do your logic }
 //view model will pubilsh this request
 _aggregator.GetEvent<CloseEvent>().Publish(output);

b. create an interface named as IView and implement it in your view , pass the instance of IView to data context of the view

public partial class Shell : Window ,IView
{
    public Shell()
    {
        InitializeComponent();
        this.DataContext.View = this;
    }

    public void CloseShell()
    {

    }
}

public interface IView
{
    void CloseShell();
}

by using this you have only a reference of interface will be there in viewmodel . but not the whole view itself


Parsing HTML knock-off for answering queries for values I wrote a code to parse an HTML knock-off from HackerRank, and I would like a review. Mostly I hope to get better at STL and code style. But any tips would be very welcome.

Sample input that I would read from cin to parse and answer queries:

  4 3
  <tag1 value = "HelloWorld">
  <tag2 name = "Name1">
  </tag2>
  </tag1>
  tag1.tag2~name
  tag1~name
  tag1~value

My code:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>

int main() {
    std::string scope, cin_buffer, name;
    std::string::iterator strg_it;
    int lines, querrys;
    std::map<std::string,std::string> variables;

    std::cin >> cin_buffer;
    lines = atoi(cin_buffer.c_str());
    std::cin >> cin_buffer;
    querrys = atoi(cin_buffer.c_str());

    for (int lines_processed=0; lines_processed<lines; ++lines_processed){
        std::cin >> std::ws;
        while (std::cin.peek()!= '\n'){
            std::cin >> cin_buffer;
            if (cin_buffer.at(0)=='<' && cin_buffer.at(1)!='/'){
                strg_it = remove_if( begin(cin_buffer), end(cin_buffer),
                                    [](unsigned char c){return c=='<' || c=='>';});
                cin_buffer.erase(strg_it, end(cin_buffer));
                if (scope.length()>0){
                    scope += "." + cin_buffer;
                }else{
                    scope = cin_buffer;
                }
            }else if (cin_buffer.at(0)=='<' && cin_buffer.at(1)=='/'){
                int length_to_erase = (scope.length())-(cin_buffer.length()-3);
                scope.erase(length_to_erase);
                if (scope.back()=='.'){
                    scope.erase(scope.length()-1);
                }
            }else{
                name = scope + "~" + cin_buffer;
                std::cin >> cin_buffer;
                std::cin >> cin_buffer;
                strg_it = remove_if( begin(cin_buffer), end(cin_buffer),
                                    [](unsigned char c){return c=='"' || c=='>';} );
                cin_buffer.erase(strg_it, end(cin_buffer));
                variables[name]=cin_buffer;
            }
        }
    }

    for (int querry_number=0; querry_number<querrys; ++querry_number){
        std::cin >> cin_buffer;
        if (variables.find(cin_buffer)!=end(variables)){
            std::cout << variables[cin_buffer] << std::endl;
        }else{
            std::cout << "Not Found!" << std::endl;
        }
    }
    return 0;
}

It is good to see that you've avoided the use of using namespace std;.

Coding

Declare variables as close to their initial use as possible, and prefer construction of that initial value to default constructing an object then assigning the initial value.  lines and querrys can be declared when they are assigned:

auto lines = atoi(cin_buffer.c_str());
// ...
auto querrys = atoi(cin_buffer.c_str());

name can be declared where it is used.  strg_it can also be declared (in both places) as auto.  This can help the compiler improve the code by letting it know the value isn't needed after the erase call.

auto strg_it = remove_if( begin(cin_buffer), end(cin_buffer),
                    [](unsigned char c){return c=='<' || c=='>';});
cin_buffer.erase(strg_it, end(cin_buffer));

Alternatively, when using the erase-remove idiom, you can put the erase and remove in one statement

    cin_buffer.erase(remove_if( begin(cin_buffer), end(cin_buffer), [](unsigned char c){return c=='<' || c=='>';}), end(cin_buffer));

and not need the variable at all.

You have no error checking on your inputs.  You should check for failed input, non-integer conversions from atoi, etc.  One alternative (since you have a std::string) is to use std::stoi, which will throw an exception if there is an error during conversion.

cin_buffer.at(0) will throw with an empty string, and cin_buffer.at(1) will throw an exception if the string only has one character in it.

variables[name]=cin_buffer; will replace any existing value for name if one already exists.  This may be the expected behavior.

In your final search loop, store the result of find in a variable to avoid having to look it up again.

auto it = variables.find(cin_buffer);
if (it != end(variables)) {
    std::cout << it->second << `\n`;
} else

You should avoid using std::endl unless absolutely necessary.  Since it flushes the output, there can be a considerable performance hit when using it.

Readability

You should put more spaces in your code, rather than jamming all those characters together.  Put spaces around binary operators

for (int lines_processed = 0; lines_processed < lines; ++lines_processed) {

which also makes it clearer that lines_processed < lines is an expression and not part of a possible template lines_processed<lines>.

The parentheses around (scope.length()) are unnecessary.

Spelling is important.  Variable names should be spelled correctly to make it easier to read and easier to search for.  querrys should be spelled queries.


Function to check empty cells found or not in Datagrid I want to check if any empty cells found or not in a Datagridview when save data to database, so I've written this function:

Public Function IsDataGridViewEmpty(ByRef dataGridView As DataGridView) As Boolean
Dim isEmpty As Boolean
isEmpty = False
For Each row As DataGridViewRow In dataGridView.Rows
    For Each cell As DataGridViewCell In row.Cells
        If Not String.IsNullOrEmpty(cell.Value) Then

            If Not String.IsNullOrEmpty(Trim(cell.Value.ToString())) = True Then
                Dim d = Trim(cell.Value.ToString())
                isEmpty = False

            End If
        Else
            isEmpty = True
            Exit For
        End If
    Next
Next
Return isEmpty
End Function

The code is working now, but are any improvements needed? Is there any way to do this without a foreach loop?

Function calling:

 Private Sub btnSave_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSave.Click
        If IsDataGridViewEmpty(Me.DataGridView1) = True Then
            MsgBox("Empty Cells Found PLease Check!")
        End If
    End Sub

Source

I changed the code from the source website, so see the difference with my code and the source link.

Can anyone explain why we use By ref in a function parameter?

 Public Function IsDataGridViewEmpty(ByRef dataGridView As DataGridView) As Boolean

The ByRef simply means that what you feed in here is going to be affected by what you do to it in the function.  You are passing a Variable or object into the function, whereas ByVal you are only passing the value of the Variable into the function/method.

Also, I am not sure what exactly you were meaning to do with this:

Dim d = Trim(cell.Value.ToString())

but it is an orphan, it is not being used for anything.

Another thing that you should keep in mind is that VB is sensitive and you should indent consistently with the VB Standard.

so the entire function should be indented like this:

Public Function IsDataGridViewEmpty(ByRef dataGridView As DataGridView) As Boolean
    Dim isEmpty As Boolean
    isEmpty = False
    For Each row As DataGridViewRow In dataGridView.Rows
        For Each cell As DataGridViewCell In row.Cells
            If Not String.IsNullOrEmpty(cell.Value) Then

                If Not String.IsNullOrEmpty(Trim(cell.Value.ToString())) = True Then
                    Dim d = Trim(cell.Value.ToString())
                    isEmpty = False

                End If
            Else
                isEmpty = True
                Exit For
            End If
        Next
    Next
    Return isEmpty
End Function


Is my code overdesigned? Does it rely too heavily on interfaces? Context:

I am using XNA to create a simple game / learning project.

Problem:

I have three interfaces, each with a different purpose in mind. However, the way I use them, as well as their implementations, makes me feel as if my code is overdesigned and poorly thought out, so I am looking for better approaches, if possible.

IGrid<T> is intended to wrap a 2-dimensional array, exposing only the Size and indexer.
IChunk<T> is intended to be a grid object with a predetermined size.
IMesh<T> is intended to be a grid, but with several methods to manipulate and transform the data.

Interfaces:

public interface IGrid<T>
{
    Point Size { get; }
    T this[int x, int y] { get; set; }
}

public interface IChunk<T> : IGrid<T>
{
}

public interface IMesh<T> : IGrid<T>
{
    IMesh<T> Clone();
    IMesh<T> Flip(bool horizontal, bool vertical);
    IMesh<T> Rotate(bool clockwise);
    IMesh<T> Slice(Rectangle value);
    IMesh<T> Slice(int x, int y, int width, int height);
    IMesh<T> Transpose();
}

The idea is that I would use IGrid to create a "custom array" which could be inherited from. IChunk would hold a finite part of the world, breaking it apart for easier/segmented access, while IMesh would let me define a heightmap (with T:float), for example, and let me merge and manipulate them very easily (for generating terrain and the like).

Classes:

A secondary concern is defining custom operators for my Mesh class, in such a way that they could easily be added, subtracted, multiplied, etc. Now, because operator overloading involves static methods, it can't really be inherited in an elegant way.

I had tried a pattern in which I made an abstract MeshBase class that defined the operators, which called protected and abstract methods as handlers for the operations, but because of the typing involved, simply adding three meshes together involved heavy usage of casting. Needless to say, it was messy and almost unusuable.

My current solution is to do something like the following to have more control over the manipulation:

public class Mesh<T> : Grid<T>, IMesh<T>
{
    public Mesh(int x, int y)
        : base(x, y)
    {
    }

    // Clone(), Flip(), Rotation(), Slice(), Transpose() methods here
}

public class FloatMesh : Mesh<float> // Used as a heightmap!
{
    // Add the values of the two meshes together, creating a new mesh
    public static FloatMesh operator +(FloatMesh a, FloatMesh b) { }

    // Add the value of "b" to every element of "a", creating a new mesh
    public static FloatMesh operator +(FloatMesh a, float b) { }
}

public class Vector2Mesh : Mesh<Vector2> // Possibly used for sampling perlin noise
{
    // Add the values of two meshes together, creating a new mesh
    public static Vector2Mesh operator +(Vector2Mesh a, Vector2Mesh b) { }

    // Apply the XY values of "b" to every element of "a", creating a new mesh
    public static Vector2Mesh operator +(Vector2Mesh a, Vector2 b) { }

    // Apply the value of "b" to each XY value of every element of "a", creating a new mesh
    public static Vector2Mesh operator +(Vector2Mesh a, float b) { }
}

Obviously, I would need to define these operators for every specific type I wanted to use. Nothing is stopping the user from making a Mesh themselves, if they're only interested in Transpose(), etc., but using a more derived class offers the ability to use convenient operators in addition to the transformation methods.

Conclusion:

Anyways, I am interested in whatever feedback you guys can offer. Like I said, I don't know if I made this in a very roundabout way, or if there is an easier/simpler way of accomplishing what I want.

Is my code overdesigned?

I think so ;)

  IChunk<T> is intended to be a grid object with a predetermined size.

public interface IChunk<T> : IGrid<T>
{
}

But a grid is already a grid object with a predetermined size:

public interface IGrid<T>
{
    Point Size { get; }
    T this[int x, int y] { get; set; }
}

I don't think you need IChunk<T>. Why not just use a IGrid<T>?

IGrid<T> is redundant here:

public class Mesh<T> : Grid<T>, IMesh<T>

Because IGrid<T> is already specified by IMesh<T>, you can't implement IMesh<T> without implementing all of IGrid<T>, because IMesh<T> : IGrid<T>.

I might be wrong, but it seems to me that "adding up" two terrains is a non-trivial operation that would be best rendered as a full-fledged method than in an operator for the terrain itself. Can you make an operator async?


ASP.NET WebAPI `In` Validation Attribute I've created custom validation attribute that will be used to validate model. It allows me to specify values that are valid for specific field.
Here is my code:

public sealed class InAttribute : ValidationAttribute
{
    private const string DefaultErrorMessage = "{1} is invalid value for {0}.";

    private readonly int[] testArray;
    private int _toTest;

    public InAttribute(int[] @in) : base(DefaultErrorMessage)
    {
        if (!@in.Any())
        {
            throw new ArgumentNullException("in");
        }

        testArray = @in;
    }

    public override string FormatErrorMessage(string name)
    {
        return string.Format(ErrorMessageString, name, _toTest);
    }

    protected override ValidationResult IsValid(object value, ValidationContext validationContext)
    {
        if (value == null)
        {
            return new ValidationResult("" + validationContext.DisplayName + " cant be null");
        }
        _toTest = Convert.ToInt32(value);
        if (!testArray.Contains(_toTest))
        {
            return new ValidationResult(FormatErrorMessage(validationContext.DisplayName));
        }

        return ValidationResult.Success;
    }
}

Then I can use it like so:

public class RequestHelpBindingModel
{
    [Required]
    [In(new []{1,3,4,7},ErrorMessage = "{1} is invalid value.")]
    [Display(Name = "Typ")]
    public int Type { get; set; }

    [Required]
    [DataType(DataType.MultilineText)]
    public string Message { get; set; }
}

I'd like to get review on this.

My questions are:

Is it build right?
If there are places to optimize please let me know.

if (!@in.Any())
{
    throw new ArgumentNullException("in");
}

This won't work the way you expect it.

It should be either C# 6

 if (@in?.Any())

or for previous versions

 if (@in == null || !@in.Any())

return new ValidationResult("" + validationContext.DisplayName + " cant be null");

Why the empty string at the beginning?

One time you do

return new ValidationResult("" + validationContext.DisplayName + " cant be null");

and the other time

return new ValidationResult(FormatErrorMessage(validationContext.DisplayName));

I thought you forgot to use the FormatErrorMessage in the first case but it produces a completely different error message.

Create another method and name it accordignly like FormatNullValueErrorMessage and the other one FormatNotInErrorMessage.

ErrorMessage = "{1} is invalid value.")

I don't think this parameter has any value and is actually very error prone because the user of this attribute has to know that he can use the {1} and what it means. I'd stick to an automatic message about the value not beeing allowed.

private readonly int[] testArray;

I would rename this field to soemthing like _allowedValues. As I first time saw it I thought it's a test code. Reserve the test for tests or really rare cases when there is no better word.

_toTest = Convert.ToInt32(value);

It's not necessary to store the value locally. Pass it as a paramter to the FormatXErrorMessage.


Would my implementation of this enum pass? I have a feature with feature flagging enabled, basis the condition I want to load different pages in my screen, to achieve this I have the following enum:

enum class ImageHolderEnum(
    val titleId: Int,
    val qFragment: BaseFragment,
    val fragment: BaseFragment
) : IPageHolder {
    PAGE1(R.string.tab_shop_baby, BabyTwoFragment(), BabyThreeFragment()) {
        override fun getTitle(): Int = titleId
        override fun getFragmentToAdd(): BaseFragment =
            if (isFeatureAllowed()) qFragment else fragment
    },
    PAGE2(R.string.tab_shop_mom, MomThreeFragment(), MomTwoFragment()) {
        override fun getTitle(): Int = titleId
        override fun getFragmentToAdd(): BaseFragment =
            if (isFeatureAllowed()) qFragment else fragment
    },
    PAGE3(R.string.tab_shop_dad, DadTwoFragment(), DadThreeFragment()) {
        override fun getTitle(): Int = titleId
        override fun getFragmentToAdd(): BaseFragment =
            if (isFeatureAllowed()) qFragment else fragment
    };

    fun isFeatureAllowed(): Boolean  {
        val qSlideConfig: QSlideConfig by remoteFeatureFlag() // Kind of dependency injection here
        return qSlideConfig.isQSlideEnabled()
    }
}

The interface is as follows:

interface IPageHolder {
    fun getTitle(): Int
    fun getFragmentToAdd(): BaseFragment
}

I am concerned if I am using the dependency injection inside the enum and breaking some principles.

Why are you giving seperate implementations for each enum value? All getTitle() and getFragmentToAdd() implementations are the same.

enum class ImageHolderEnum(
    val titleId: Int,
    val qFragment: BaseFragment,
    val fragment: BaseFragment
) : IPageHolder {
    PAGE1(R.string.tab_shop_baby, BabyTwoFragment(), BabyThreeFragment()),
    PAGE2(R.string.tab_shop_mom, MomThreeFragment(), MomTwoFragment()),
    PAGE3(R.string.tab_shop_dad, DadTwoFragment(), DadThreeFragment()),
    ;

    override fun getTitle(): Int = titleId
    override fun getFragmentToAdd(): BaseFragment = if (isFeatureAllowed()) qFragment else fragment

    fun isFeatureAllowed(): Boolean  {
        val qSlideConfig: QSlideConfig by remoteFeatureFlag() // Kind of dependency injection here
        return qSlideConfig.isQSlideEnabled()
    }
}

Interfaces can also have properties, so there's no need to have getTitle() as a function, when it can just be a value.

interface IPageHolder {
    val titleId: Int
    fun getFragmentToAdd(): BaseFragment
}

And you can then use it like this in the enum class:

enum class ImageHolderEnum(
    override val titleId: Int,
    ...


Finding the Minimum and Maximum Value in an Image Given an image which is padded to support aligning (SSE) I need to find its minimum and maximum value as fast as possible.
Mind you the padded values are not defined and can't be assumed to have certain values.

This is the code I created:

void ExtractMinMax(float* vMinMax, float* mI, int numRows, int numCols, int numColsPad)
{

    int ii, jj, numColsSse;

    __m128 pxI;
    __m128 minVal;
    __m128 maxVal;

    numColsSse = numCols - (numCols % SSE_STRIDE);

    minVal = _mm_loadu_ps(&mI[0]);
    maxVal = _mm_loadu_ps(&mI[0]);

    for (ii = 0; ii < numRows; ii++) {
        for (jj = 0; jj < numColsSse; jj += SSE_STRIDE) {

            pxI     = _mm_loadu_ps(&mI[(ii * numColsPad) + jj]);
            minVal  = _mm_min_ps(minVal, pxI);
            maxVal  = _mm_max_ps(maxVal, pxI);

        }
    }

    vMinMax[0] = HorizontalMinSse(minVal);
    vMinMax[1] = HorizontalMaxSse(maxVal);

    for (ii = 0; ii < numRows; ii++) {
        for (jj = numColsSse + 1; jj < numCols; jj++) {

            if (mI[(ii * numColsPad) + jj] < vMinMax[0]) {
                vMinMax[0] = mI[(ii * numColsPad) + jj];
            }

            if (mI[(ii * numColsPad) + jj] > vMinMax[1]) {
                vMinMax[1] = mI[(ii * numColsPad) + jj];
            }

        }
    }

}

The horizontal min / max are given by (following Peter Cordes' advice):

static inline float HorizontalMaxSse(__m128 x) {
    // Calculates the sum of SSE Register - http://stackoverflow.com/a/35270026/195787
    __m128 shufReg, sumsReg;
    shufReg = _mm_movehdup_ps(x);        // Broadcast elements 3,1 to 2,0
    sumsReg = _mm_max_ps(x, shufReg);
    shufReg = _mm_movehl_ps(shufReg, sumsReg); // High Half -> Low Half
    sumsReg = _mm_max_ss(sumsReg, shufReg);
    return  _mm_cvtss_f32(sumsReg); // Result in the lower part of the SSE Register
}

static inline float HorizontalMinSse(__m128 x) {
    // Calculates the sum of SSE Register - http://stackoverflow.com/a/35270026/195787
    __m128 shufReg, sumsReg;
    shufReg = _mm_movehdup_ps(x);        // Broadcast elements 3,1 to 2,0
    sumsReg = _mm_min_ps(x, shufReg);
    shufReg = _mm_movehl_ps(shufReg, sumsReg); // High Half -> Low Half
    sumsReg = _mm_min_ss(sumsReg, shufReg);
    return  _mm_cvtss_f32(sumsReg); // Result in the lower part of the SSE Register
}

It's a really straightforward implementation using SSE, yet it seems it is not so fast.
For instance, MATLAB's min() and max() running sequencely are 10 times faster.

The code was compiled into DLL using Visual Studio 2017 Update 3.
Timing was done using MATLAB's tic() / toc().

What can be done to make it faster?

Using signed integer loop counters is leading to some extra work outside the loop, but it doesn't seem to be hurting the inner-most loop in the compiler's asm output.  Still, you might as well use size_t for memory sizes; that's what it's for and usually compiles efficiently.  OTOH, limiting your args to signed makes it easier to express the condition that the loop should run zero times (because size - unroll width can be negative, instead of having to code it like asm, with an explicit compare and then a do{}while() loop.)

numColsPad should be called rowStride or stride.  numColsPad is ambiguous whether it means number of columns including padding, or whether it's the width of the padding!  Stride is a well-established term for the distance in memory between rows.  stride - cols doesn't even have to be small: separating the storage layout from the width lets you pass a sub-image to a function without copying the data to another buffer.

numColsSse is an awkward variable name.  SSE should be all-caps.  Or better, just call it something else, like colVecs.  I'm not a fan of your other variable names, or camelCase in general.  HorizontalMaxSse is also a silly name.  Max of what?  Call it HorizontalMax_ps to indicate that it's packed-single-precision floats.

You should use const float* for the read-only input array.  You could also return min by value and only use the output-pointer for max.  It would be better C++ style to declare your variables as you use them, instead of C89-style at the top of the function.

The two biggest performance things I see are:

Handling the tail of every row with a 2nd loop over all the rows is horrible (for(jj = numColsSse + 1; ...).  That data will be hot in L1D cache from HW prefetch while doing a row, so you should grab it then instead of waiting until later when it's probably evicted again.  Striding over the rows to load a couple columns is a bad access pattern which will hurt a lot for tall and narrow image.

You also don't need to do it scalar.  You can accumulate tailMin and tailMax vectors, and after the fact take only the elements that are actually part of the image.  (e.g. loop over 1 to 4 elements of the vector, depending on numCols%4.  Not 0-3, because that would mean we'd want to do it conditionally to avoid wasting work.)

If you need to avoid loading past the end of the last row, then peel the last row out of the main loop and do it specially.

It makes the cleanup trivial if we use an unaligned potentially-overlapping load that gets the last 4 elements of a row (then we don't have to ignore any elements of separate tail accumulators).  Overlap is fine because x=min(x,y) is idempotent.  Unlike a sum reduction, looking at the same element multiple times doesn't change the result.  If we're clever, we can use this to simplify the unrolling.

OTOH, branching based on numCols & 7 would probably be better to avoid doing a fully-overlapped vector, since we bottleneck on min/maxps throughput, not on the front-end.  Still, this is pretty good and makes the source simple.  Optimize further however you like.

Unroll the inner vector loop with multiple accumulators.  maxps has 3c or 4c latency, 1c or 0.5c throughput on recent Intel CPUs (http://agner.org/optimize/, and see also this SO Q&A about using multiple accumulators for FMA.)

On Skylake, you need 8 accumulators to keep 8 min/maxps instructions in flight at once to max out execution-unit throughput (it runs FP add/cmp/min/max on the FMA units on p0/p1, same as mul and fma).  You only have 2, one each for min and max.  On Broadwell (3c latency, 1c throughput, runs on port1 only) this will in theory get you 2/3rds of theoretical max throughput.

This is what MSVC CL19 does for the inner loop:

$LL7@ExtractMin:
    movups   xmm0, XMMWORD PTR [rdx]
    lea      rdx, QWORD PTR [rdx+16]   ; ADD would be better, but this probably doesn't create resource conflicts
    minps    xmm1, xmm0
    maxps    xmm2, xmm0
    sub      r8, 1                  ; will macro-fuse with JNE on Intel SnB-family
    jne      SHORT $LL7@ExtractMin

That's 5 fused-domain uops, so it can issue at about 1 iteration per 1.25 clocks.  So actually even on Haswell/Broadwell, min/maxps latency is a bigger bottleneck than CPU front-end throughput (4 uops per clock max, or slightly less in loops that aren't a multiple of 4 uops in some cases.)  Still, unrolling will let out-of-order execution see the loads earlier.

OTOH, unrolling introduces more code to get the iteration count right (especially if you need your code to work for very narrow images where you can't assume the width is at least one full vector).

This can be outside the outer loop if the whole nested loop is duplicated.  (Either in the source or in the compiler output if it decides to factor out a check).  Or we can do something simple and branchless like always doing a first vector and then starting j from 0 or 4 depending on whether numCols is a multiple of SSE_STRIDE*2 or not (ignoring the low 2 bits).  Overlap is fine because min and max are idempotent. (I haven't thought through the possibilities with NaN; _mm_min_ps() and max are not commutative without -ffast-math or equivalent for other compilers.  You are using them with the operand order that allows the compiler to avoid extra movaps instructions.)

Here's an example of most of those ideas.  I'm only unrolling by 2, but you need to unroll by at least 4 to max out performance on Skylake (for cases where you don't bottleneck on memory).

source + asm on Godbolt.  It looks good for MSVC and gcc and clang.  Clang does further unrolling of the inner loop, but without using more accumulators so it's useless for speeding up Skylake.

Returning a 2-member struct by value ends up taking slightly more code than just storing twice, so it's probably not a win.  I'd recommend picking one method (or just returning min by value as a float and max by pointer), instead of storing both and packing both into a struct.  The caller will have to unpack the struct into separate registers in most cases, so it's not that great.

#include <immintrin.h>

struct minmax { float min, max; };

// pre-condition: numCols >= 8
// numRows >= 1
minmax ExtractMinMax(float* vMinMax, const float* mI, int numRows, int numCols, int rowStride)
{
    static const int VEC_WIDTH = 4;
    //if (numCols < 2*VEC_WIDTH) {
    //    return alternate_version(vMinMax, mI, numRows, numCols, rowStride);
    //}

    // if you want to support numCols < 8, a simple way is _mm_load1_ps(mI)
    // but you'd also have to change the non-multiple-of-8 handling in the loop
    __m128 min0 = _mm_loadu_ps(mI);
    __m128 min1 = _mm_loadu_ps(mI + VEC_WIDTH);
    __m128 max0 = min0, max1 = min1;
    // TODO: skip the first 2 vectors of the first row

    int i=0;
    do {  // let the compile know this loop runs at least once
        // manually hoisting the row pointer mostly helps human readability; compilers usually already do this
        const float *row = &mI[i * rowStride];

        for (int j=0 ; j < numCols - VEC_WIDTH*2; j += VEC_WIDTH*2) {
            // for large unroll counts, a function or macro is useful.  (not recommended, don't go nuts)
            // for small unrolls, manual repetition is usually the most readable.
            __m128 pxI0 = _mm_loadu_ps(row+j);
            min0  = _mm_min_ps(min0, pxI0);
            max0  = _mm_max_ps(max0, pxI0);
            __m128 pxI1 = _mm_loadu_ps(row+j + VEC_WIDTH);
            min1  = _mm_min_ps(min1, pxI1);
            max1  = _mm_max_ps(max1, pxI1);
        }
        // loop stops with 1 to 2*VEC_WIDTH elements left to do, depending on numCols & (2*VEC_WIDTH - 1)

        // last 2 vectors ending at the end of the row, could overlap with above
        // but won't for multiple-of-8 numCols
        __m128 tail = _mm_loadu_ps(row + numCols - VEC_WIDTH*2);
        min0  = _mm_min_ps(min0, tail);
        max0  = _mm_max_ps(max0, tail);

        tail = _mm_loadu_ps(row + numCols - VEC_WIDTH);
        min1  = _mm_min_ps(min1, tail);
        max1  = _mm_max_ps(max1, tail);
        // This isn't really optimal; 2 unaligned loads is more chances to CL-split or 4k-split
        // assuming the start of each row is aligned
        // but it does avoid any branching on the low bits of numCols.
    } while(++i < numRows);

    // reduce the multiple accumulators to one
    min0 = _mm_min_ps(min0, min1);
    max0 = _mm_max_ps(max0, max1);

    // horizontal min/max.
    float min = HorizontalMin_ps(min0);
    float max = HorizontalMax_ps(max0);

    vMinMax[0] = min;
    vMinMax[1] = max;
    return { min, max };
}

Using AVX if available could help, too, but probably not if you're totally memory bottlenecked from looping over giant images doing not much work for the amount of memory traffic.  Still, AVX can help saturate memory bandwidth better because the same number of in-flight loads covers twice as much data.  (But requests from L1 to L2, and L2 to L3, are tracked in whole cache lines.)

Try to combine the min/max calculation into whatever wrote the image in the first place, to increase computational intensity.  Doing a separate pass for min/max isn't great.  (Although it's twice as good as doing separate passes over your data for min and for max.)

Using multiple threads can help even if you're memory-bound, especially on Intel CPUs with more than quad cores.  IDK how bad single-threaded memory performance is on your 6-core Broadwell i7-6800k, but on many-core Xeons the extra latency to L3 and DRAM hurts single-threaded bandwidth a lot.  (bandwidth = max concurrency / latency).  See the Latency-bound platforms section of this answer for more details.

My quad-core Skylake (i7-6700k) can use most of the total memory bandwidth with only one thread, but that's with a quite high core / uncore clock speed.

Also, with enough cores for a medium-size image, it might start fitting in L2 cache (since each core only looks at part of it).  But 2k*2k * 4B is 15.25MiB, which is larger than the 15MB L3 cache on your CPU.

If you're going to use this with unaligned input pointers very often (e.g. a sub-image), it might make sense to do the unaligned head of each row separately, and a potentially-overlapping aligned loop over the main part of each row.  cache-line splits won't be a problem on recent Intel (you're only going to do 1 load per clock max), but 4k-splits will still cause bubbles on pre-Skylake.  Like 34 cycle load-use latency on Haswell for a 4k-split instead of only 11 for a cache-line split.

NaN behaviour: this will ignore NaN in the input (unless it's in the initial values that we start with.

max and _mm_min_ps() are not commutative without -ffast-math (or equivalent for other compilers).  You are using them with the operand order that allows the compiler to avoid extra movaps instructions, so that's a good thing.


Algorithm to return unique values from unsorted input I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.

As the function that will call this algorithm can abort the reading at any time, I think that using a well defined Iterable implementation is the right way, so I will not waste extra processing power for the uneeded input.

Today, I am using a Set to keep track of the values I've already read. But I don't know if this is the most efficient algorithm, as my input length can be huge.

The code below is my today's working algorithm:

import java.util.Iterator;
import java.util.HashSet;
import java.util.Set;
import java.util.NoSuchElementException;
import java.io.BufferedReader;
import java.io.StringReader;
import java.io.IOException;

public class UniqueValues implements Iterable<String> {
    private final Iterator<String> iterator;

    public UniqueValues(BufferedReader r) {
        this.iterator = new UniqueValuesIterator(r);
    }

    public Iterator<String> iterator() {
        return iterator;
    }

    static class UniqueValuesIterator implements Iterator<String> {
        private final BufferedReader r;

        private final Set<String> values = new HashSet<>();

        // When 'next' is null, need to get the next value
        private String next;

        public UniqueValuesIterator(BufferedReader r) {
            this.r = r;
        }

        public boolean hasNext() {
            // Good point from OldCurmudgeon
            if(next != null) return true;

            try {
                String line;
                while((line = r.readLine()) != null) {
                    if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.
                        next = line;
                        return true;
                    }
                }
            } catch(IOException e) { }

            return false;
        }

        public String next() {
            if(next == null) {
                if(! hasNext() ) throw new NoSuchElementException();
            }

            final String temp = next;
            next = null;
            return temp;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    // For testing
    public static void main(String... args) {
        final StringReader r = new StringReader("value1\nvalue6\nvalue1\nvalue3\nvalue3\nvalue6\nvalue1\nvalue6");

        for(final String value : new UniqueValues(new BufferedReader(r)) ) {
            System.out.println(value);
        }

        /* Output is (order is not important):
         *
         * line 1
         * line 6
         * line 3
         */
    }
}

Does it have any better algorithm to do this?

There are three significant issues I would address here...

Ratchet Freak is right about being concerned about the Iterator/FilteredReader... but I disagree with his suggestion. I think the problem is that your code is converting a BufferedReader in to an Iterator, and making the results unique at the same time. This is a class that is performing 2 functions... and you shoould have two classes instead. One that converts the BufferedReader to an interator, and the other that enforces uniqueness.
If your input data really is huge, then a Set may not be the right data structure because of it's memory footprint. I have found that custom implementations of memory-efficient structures can save a lot of space. I hesitate to recommend that you change from the Set though, it is the 'logical' choice, but, if, for example, your average String value is about 16 characters, then more than half of your memory will be in the Set overhead. I have, in the past, had reason to do similar things to you, and have written a memory-efficient class that can be seen in JDOM here (you will need to make changes to that code if you want to use it because it will need to have a mechanism for a true/false seen-it test).
I have a pattern I use for Iterators that is really effective, and makes the Iterator logic much simpler/readable. I'll give you an example....

First, part 1, a Reader-to-Iterator implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.util.Iterator;
import java.util.NoSuchElementException;

@SuppressWarnings("javadoc")
public class ReaderLineIterator implements Iterator<String> {

    private final BufferedReader reader;
    private String nextval;

    public ReaderLineIterator(Reader reader) {
        this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :
            new BufferedReader(reader);

        advance();

    }

    private void advance() {
        try {
            nextval = reader.readLine();
        } catch (IOException ioe) {
            throw new IllegalStateException("Unable to read from reader.", ioe);
        }
    }

    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}

Note how, in this class, I use a trick for the nextval, where it is advanced in the finally block of the next() call. This is a pattern I like because it makes the hasNext() method very light-weight, and it is always a step-ahead of the data.

So, that is a single-purpose class, it converts a Reader to a line-at-a-time Iterator.

Now, you need a unique Iterator... which can look something like:

import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

@SuppressWarnings("javadoc")
public class UniqueIterator implements Iterator<String> {

    private final Iterator<String> source;
    private String nextval = null;
    Set<String> seenit = new HashSet<String>();

    public UniqueIterator(Iterator<String> source) {
        this.source = source;
        advance();
    }

    private void advance() {
        while (source.hasNext()) {
            String nxt = source.next();
            if (seenit.add(nxt)) {
                // found a unique value....
                nextval = nxt;
                return;
            }
        }
        // no more unique values.
        nextval = null;

    }

    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}


Creating a proper workflow through version control and a Makefile disclaimer: I've posted this around but the question keeps being put on hold for being inherently opinionated which I understand, just looking for some vague direction as to how a more experienced developer would approach this problem. I think this is the right place based on what I'm asking and I apologize if not.

So I've been working on creating a workflow for my buddy and I to use across the 2 projects and few servers we have. While at first I started with a shared group ownership option of the project files, I found this to be annoying and prone to human error.

I decided to convert the project to an svn controlled directory on a separate server where my production server and ourselves can pull from as needed, we can do local builds/testing and then tell the server to pull changes when we are ready to push to live, the concept is nice and seems pretty simple.

I have the svn system built out how I like it however I am struggling with how to set up my Makefile, my plan is to have a few commands:

clean - go and delete all extra artifacts created as you work
dev - spin up a local flask instance for testing purposes
venv - destroy and rebuild the virtual environment, used mainly for new setups
when you first pull the project
install - tell the production server to pull the most recent changes and then restart apache through an 'svn' user we all have access to

This is the simplest Makefile I can think of to do the jobs I want, as well as easily allowing for more support as time goes on if need be.

My problem is that I'm not exactly sure what the best way to approach 'make venv' and 'make install'. I have it set up manually right now and it works but it's just not graceful and I know it's becuase of my lack of knowledge in building a large python project like this. I've seen people use setuptools but I'm not sure if that's totally overkill for my project or not.

Does anyone have a similar workflow and/or have any suggestions on how I can improve my setup? I have my Makefile and install.sh script below for reference.

install.sh:

svn up

sudo /etc/init.d/apache2 restart

Makefile:

clean:
    find . -name \*~ -delete
    find . -name \*.pyc -delete

test:
    FLASK_APP=octlive/__init__.py \
    FLASK_DEBUG=1 \
    ../venv/bin/flask run --host=0.0.0.0

venv:
    virtualenv ../venv
    ../venv/bin/pip install -r require.txt

relclean: clean
    rm -rf ../venv

dev: relclean venv test

install:
    ssh user@server '/var/www/app/install.sh'

and just in case it's useful, my require.txt:

Flask
Flask-session
Flask-bootstrap
WTForms

I know this is not the best practice how I have my Makefile set up, specifically how I am using make to call install.sh on the production server. Has anyone taken a similar approach to what I've done and if so what suggestions do you have? I feel kind of lost in how to make this better while knowing it isn't that good to begin with.

I don't know anything about Flask, but there are definitely problems with the Makefile:

dev: relclean venv test

In a parallel build, the building of the relclean target can overlap with that of venv and test; you might want to add some ordering there (or put .NOTPARALLEL: as a target).

The rules for clean and dev don't create their targets, so need to be marked with .PHONY.

All makefiles should have .DELETE_ON_ERROR to avoid partially-written files satisfying the dependencies.

The install target doesn't appear to depend on anything.  So make install may well install an out-of-date product.  On further reading, the install target doesn't look like a conventional install step - perhaps it would be better named as update-server or something?

Overall, it looks more like a job for a script than a Makefile, unless you are actually going to make use of Make's dependency engine.  Perhaps something like this:

#!/bin/bash

# Definitions
server=server
user=${USER:-user}

export FLASK_APP=octlive/__init__.py
export FLASK_DEBUG=1

# Actions
action()
{
do case "$1" in
       clean)
           find . -name \*~ -delete
           find . -name \*.pyc -delete
           ;;
       test)
           ../venv/bin/flask run --host=0.0.0.0
           ;;
       venv)
           virtualenv ../venv
           ../venv/bin/pip install -r require.txt
           ;;
       relclean)
           action clean
           rm -rf ../venv
           ;;
       dev)
           action relclean
           action venv
           action test
           ;;
       install)
           ssh "$user@$server" /var/www/app/install.sh
           ;;
   esac
}

for arg in "$@"
do action "$arg"
done


Changing an element in a list when a predicate holds My current project is a Settlers of Catan server in Haskell. I often manage to achieve my goals within Haskell, but the code is getting messier as the project grows.
My question is about the placeBuilding :: Board -> Building -> VertexCoordinate -> Board function that places a building on the board at a specified VertexCoordinate.
Board has a property vertices :: [Vertex], and Vertex is contains a property vertex_coordinate :: ((Int, Int), Int)
My question is about three different attempts for this function:
First of all, would you do anything different in any of the attempts?
For my first attempt I first found the vertex_index of [Vertex] that the building should be placed on, and then with the lens package I change it. This feels natural to me, but it looks rather ugly, especially because of the way I have to deal with the fromMaybe, for which I now make the assumption that the supplied VertexCoordinate must exist.
-- ATTEMPT 1
-- Return a board with the supplied building placed at the supplied coordinate
placeBuilding :: Board -> Building -> VertexCoordinate -> Board
placeBuilding board building coord = board {vertices = vertices'}
                      where v_index = fromMaybe 0 $ findIndex (\v -> vertex_coordinate v == coord) (vertices board)
                            vertices' = vertices board & element v_index .~ Vertex coord (Just building)

Now the second and third are kind of similar. Is one better than the other? Personally, I think the third is the most readable.
-- ATTEMPT 2
-- Return a board with the supplied building placed at the supplied coordinate
placeBuilding2 :: Board -> Building -> VertexCoordinate -> Board
placeBuilding2 board building coord = board {vertices = vertices'}
                      where vertices' = map (\v -> if vertex_coordinate v == coord then Vertex coord (Just building) else v) (vertices board)

-- ATTEMPT 3
-- Return a board with the supplied building placed at the supplied coordinate
placeBuilding3 :: Board -> Building -> VertexCoordinate -> Board
placeBuilding3 board building coord = board {vertices = map placeIfAtCoord $ vertices board}
                      where placeIfAtCoord v | vertex_coordinate v == coord = Vertex coord (Just building)
                                             | otherwise                    = v

I'm not super familiar with Catan, having played it only once in my life and not even to completion, but a grid's a grid, and hex grids can be modeled using three axes instead of the usual two. The data structure you're searching for is an Array. (Or a Vector, if you wanna get fancy with mutability.)
Before I get to the demo, just a few notes on your various versions. #1 lies, if there's no match it just returns the first element in the array. The right thing to do is crash, or if you're feeling nice you can make your return value a Maybe Board. Returning the wrong thing is a good way to end up with subtle bugs that corrupt your data which you still just have to track down later, crashes get fixed. All your versions clobber any building that was already in that coordinate, which I have no idea if that's a thing that you do in Catan or not but I'm going to assume it's an illegal move.
These sorts of problems are easy to lose in the line noise when you haven't modeled your data correctly. One dimensional linked lists are great, but they're not the solution to everything. So, on to Arrays. You find them in the “array” package, which is part of the Haskell 2010 standard so you can expect it to be present in all modern compilers (GHC, GHC, and uh... GHC).
I've no idea what your vertex_coordinate :: ((Int, Int), Int) is supposed to represent (aside, use camelCase for your Haskell names, and did you intentionally choose a 2-tuple containing a 2-tuple over just using a 3-tuple?) but hexagonal grids are easy, especially hexagonally shaped ones like the Catan board is. Instead of just x- and y-coordinates, you use x-, y- and z-coordinates representing ↗, ↖, and ↓. Now the trick is to recognize that the axes aren't independent like in the Cartesian plane, they actually have a relation. Try drawing out a grid and figuring out what that is.
Hint:

 Remember that the origin is at \$(0,0,0)\$.

Solution:

 Using the arrows as given above for the positive direction of each axis, you'll notice that \$x + y + z = 0\$.

Now if I remember correctly Catan boards have a radius of 2, so we'll make an empty board.
type Coordinate = (Int, Int, Int)
type Board = Array Coordinate (Maybe Building)

emptyBoard :: Board
emptyBoard = listArray ((-2, -2, -2), (2, 2, 2)) (repeat Nothing)

And then write a place function that maintains the game logic.
placeBuilding :: Board -> Coordinate -> Building -> Either String Board
placeBuilding board coord@(x, y, z) building
  | x + y + z /= 0 = Left "Invalid coordinate"
  | not (inRange (bounds board) coord) = Left "Coordinate out of range"
  | otherwise = case board ! coord of
    Just _ -> Left "Coordinate occupied"
    Nothing -> Right $ board // [(coord, Just building)]


Image color-moment extractor I was just wondering if there is a way to speed up the performances of this for loops in Python.

I'm trying to process an image to get the color-moments without using libraries.
It takes about 12sec to do the calculate_mean and calculate_standard_deviation functions for each part of the image.

import math

import cv2
import numpy as np

parts = 2
new_height = int(img.shape[0]/parts)
new_width = int(img.shape[1]/parts)

for i in range (0,img.shape[0],new_height):
    for j in range(0,img.shape[1],new_width):
        color_moments = [0,0,0,0,0,0,0,0,0]
        cropped_image = img[i:i+new_height,j:j+new_width]
        yuv_image = cv2.cvtColor(cropped_image,cv2.COLOR_BGR2YUV)
        Y,U,V = cv2.split(yuv_image)

        pixel_image_y = np.array(Y).flatten()
        pixel_image_u = np.array(U).flatten()
        pixel_image_v = np.array(V).flatten()

        calculate_mean(pixel_image_y,pixel_image_u,pixel_image_v,color_moments)
        calculate_standard_deviation(pixel_image_y, pixel_image_u, pixel_image_v, color_moments)

And this are the two functions:

def calculate_mean(pixel_image_y,pixel_image_u,pixel_image_v,color_moments):
    for p in pixel_image_y:
        color_moments[0]+=(1/(new_height*new_width))*int(p)
    for p in pixel_image_u:
        color_moments[1]+=(1/(new_height*new_width))*int(p)
    for p in pixel_image_v:
        color_moments[2]+=(1/(new_height*new_width))*int(p)

def calculate_standard_deviation(pixel_image_y,pixel_image_u,pixel_image_v,color_moments):
    temp = [0,0,0]
    for p in pixel_image_y:
        temp[0]+=(p-color_moments[0])**2
    color_moments[3] = math.sqrt((1/(new_height*new_width))*temp[0])
    for p in pixel_image_u:
        temp[1]+=(p-color_moments[1])**2
    color_moments[4] = math.sqrt((1/(new_height*new_width))*temp[1])
    for p in pixel_image_v:
        temp[2]+=(p-color_moments[2])**2
    color_moments[5] = math.sqrt((1/(new_height*new_width))*temp[2])

Python 2 is end of life, many core libraries and tools are dropping Python 2 support.
Python is dumb. If you tell it to calculate (1/(new_height*new_width) each and every loop, then Python will.
Your style is not Pythonic, you should have more whitespace.
If we change one of the for loops in calculate_mean to math, we can see we can that ¶2 isn't needed inside the loop.

for p in pixel_image_y:
    color_moments[0]+=(1/(new_height*new_width))*int(p)

$$
\Sigma \frac{\lfloor p \rfloor}{hw} = \frac{\Sigma \lfloor p \rfloor}{hw}
$$
We can utilize numpy to perform the loop, in calculate_standard_deviation, in C.

color_moments[3] = (
    np.sum((pixel_image_y - color_moments[0]) ** 2)
    * math.sqrt((1/(new_height*new_width))
)

You should change calculate_mean and calculate_standard_deviation to either work in one dimension or all dimensions.
You should remove color_moments from your code. You should return if you need to return.
You can determine new_height*new_width by the values you enter in your function. No need to pass them.

def mean(values):
    return sum(int(v) for v in values) / len(values)

def std_deviation(values):
    return np.sum((values - mean(values)) ** 2) / math.sqrt(len(values))


Large Power Mod - Extreme Efficiency I've implemented my own 'power-mod' procedure which will compute a^b 'mod' n for some large b and even larger n. I think the way I've done it is a common procedure, and it does seem well optimised, but I really need to squeeze the maximum performance out of it as it is currently the bottleneck in my program (~75% of the CPU time).

First I will explain in words the procedure (ironically, in an imperative style), then display the code (which is quite short).

In Words

Calculating a^b mod n:

Obtain the binary expansion of b in Big Endian form. Call it bE.

For example, b = 10 becomes b = [1,0,1,0] which is the reverse of its conventional binary representation 0101. This part is well optimised (~5% of the CPU time).

Drop the first element of bE (essentially because this  will always be 1-- I don't care about b=0 as this is trivial).
Start with result = 1. (i.e. a^0)
If bE is empty, then return result.
Take the next element from bE to be k.

If k is 0, then do result = result^2     'mod' n
If k is 1, then do result = result^2 * a 'mod' n

Go to step 4.

The Code

-- This part computes the Big Endian binary representation list of an Integer `k`. It's not a bottleneck, so I'm not so concerned about this.
binarizeE k = binarizeETab k []
  where
    binarizeETab 0 xs  = xs
    binarizeETab k xs = binarizeETab (fst kdivmod) ((snd kdivmod):xs)
      where
        kdivmod = k `divMod` 2

-- The part that I want to optimise to oblivion!
-- Doing `rem` and then ending with a final `mod` may make an incredibly minute improvement for extremely large numbers as compared with using `mod` each and every step.
largepowmod num pow modbase = (operate num opList) `mod` modbase
  where
    opList = drop 1 $ binarizeE pow
    operate k    []   = k
    operate k (0:ops) = operate (k^2         `rem` modbase) ops
    operate k (1:ops) = operate ((k^2 * num) `rem` modbase) ops

My Optimistic Goal

The background here is that I've implemented the Baillie–PSW Primality Test and am trying to improve its performance so that it is comparable with professional software like Mathematica. This bottleneck is happening during the Miller-Rabin Test procedure. Since Haskell is compiled, and Mathematica on my machine utilizes the same CPU % as my program, I don't see why I couldn't achieve something close. At the moment, they are indeed close for some tests (1.1s versus 1.4s), but for fun I'd like to see if maybe I can even surpass Mathematica!

Additional Information / Benchmark

The base a is in my case always 2. Maybe this lends itself to some neat trick. The exponent b and modulo base n vary greatly, but a typical example would be something like n an odd number somewhere in the vicinity of 10^1000 and b ~= n/2.

Example test comparison of my current implementation and Mathematica's:

Set b(n) = (n-1)/2. Then evaluating 2^b mod n for every odd n between 10^1000 and 10^1000 + 10000 takes ~110s for my program, and ~92s for Mathematica.

Testing code below for reference.

Haskell:

import PrimeStuff
import PrimeStuff.PQTrials
import System.Environment
import Control.DeepSeq

main :: IO()
main = do
        let trialNs   = [10^1000 + 1, 10^1000 + 3.. 10^1000 + 9999]
        let modTest n = largepowermod 2 ((n-1) `div` 2) n
        let test      = map modTest trialNs

        let sol   = deepseq test "Done."
        putStrLn(sol)

Mathematica:

nList = 10^1000 + (2*Range[5000] - 1);
Timing[results = PowerMod[2, (# - 1)/2, #] & /@ nList;][[1]]

Ideas

I am always using a=2 as the base, so in big endian form, a^b looks like [1,0,0,0.....0] with b zeros. Is there perhaps a way of taking the modulo of this with respect to n by manipulating the 0s and 1s directly? Would such a thing be faster than what the computer/compiler is already doing with my current code?

TL;DR

Use strictness annotations at the right point to get rid of thunks:

largepowmod :: Integer -> Integer -> Integer -> Integer
largepowmod num pow modbase = (operate num opList) `mod` modbase
  where
    opList = drop 1 $ binarizeE pow
    operate !k    []   = k
    operate !k (0:ops) = operate (k^2         `rem` modbase) ops
    operate !k (1:ops) = operate ((k^2 * num) `rem` modbase) ops
--          ^

Note that this is equivalent to using foldl'.

Proper benchmarks

First of all, let's get reliable benchmarks. We can use Criterion for this:

import Criterion.Main
import Text.Printf (printf)

main :: IO()
main = defaultMain [
  bgroup "largepowmod" $
    flip map ([1,3..5] ++ [9999]) $ \i ->
      bench (printf "10^1000 + %d" i) $
        let n = 10^1000 + i :: Integer
        in whnf (largepowmod 2 ((n - 1) `div` 2)) n
  ]

On my machine, I get about 16.4ms per call with -O2:

benchmarking largepowmod/10^1000 + 1
time                 16.14 ms   (16.07 ms .. 16.22 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.18 ms   (16.13 ms .. 16.23 ms)
std dev              124.6 μs   (99.83 μs .. 164.8 μs)

benchmarking largepowmod/10^1000 + 3
time                 16.44 ms   (16.26 ms .. 16.63 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 16.35 ms   (16.29 ms .. 16.42 ms)
std dev              168.3 μs   (135.2 μs .. 223.2 μs)

benchmarking largepowmod/10^1000 + 5
time                 16.24 ms   (16.19 ms .. 16.30 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.35 ms   (16.30 ms .. 16.41 ms)
std dev              138.4 μs   (89.59 μs .. 182.9 μs)

benchmarking largepowmod/10^1000 + 9999
time                 16.45 ms   (16.34 ms .. 16.58 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.37 ms   (16.30 ms .. 16.43 ms)
std dev              165.2 μs   (129.3 μs .. 235.4 μs)

But let's not stop here. Let's have a look at the profile:

$ ghc --make Test.hs -O2 -prof -auto-all && ./Test +RTS -s -p && head -n20 Test.prof

        Tue Sep 27 13:32 2016 Time and Allocation Profiling Report  (Final)

           Test +RTS -s -p -RTS --output benchmark.html

        total time  =       19.65 secs   (19652 ticks @ 1000 us, 1 processor)
        total alloc = 8,760,057,056 bytes  (excludes profiling overheads)

COST CENTRE         MODULE                %time %alloc

largepowmod.operate Main                   91.9   83.5
getGCStats          Criterion.Measurement   5.1   10.6
getOverhead         Criterion.Monad         2.2    1.5
applyGCStats        Criterion.Measurement   0.1    1.5

                                                                                individual     inherited
COST CENTRE                                  MODULE                                   no.     entries  %time %alloc   %time %alloc

MAIN                                         MAIN                                     273           0    0.0    0.0   100.0  100.0
 main                                        Main                                     550           0    0.0    0.0   100.0   99.9
  main.\                                     Main                                     745           0    0.0    0.0    91.9   83.5
   largepowmod                               Main                                     746        1208    0.0    0.0    91.9   83.5
    largepowmod.operate                      Main                                     752     4011768   91.9   83.5    91.9   83.5
    largepowmod.opList                       Main                                     751        1208    0.0    0.0     0.0    0.0

So most of the time is used in operate. It's allocating most of the data. However, that's a little bit of a red herring, since binarizeE is inlined at this point, and poor operate is merely allocating the list that will be generated lazily.

Getting stricter

However, we're not strict enough. In operate we create a large chunk of intermediate data:

operate k    []   = k
operate k (0:ops) = operate (k^2         `rem` modbase) ops
operate k (1:ops) = operate ((k^2 * num) `rem` modbase) ops
--                           ^^^^^^^^^^^^^^^^^^^^^^^^^

Haskell is lazy, therefore (k^2 * num) `rem` modbase isn't evaluated until it's actually needed. Therefore we allocate \$\mathcal O(\log_2 p)\$ additional terms. This isn't necessary. We can provide a small fix to make sure that k has been fully evaluated:

largepowmod' :: Integer -> Integer -> Integer -> Integer
largepowmod' num pow modbase = (operate num opList) `mod` modbase
  where
    opList = drop 1 $ binarizeE pow
    operate !k    []   = k
    operate !k (0:ops) = operate (k^2         `rem` modbase) ops
    operate !k (1:ops) = operate ((k^2 * num) `rem` modbase) ops

This needs -XBangPatterns. How does this fare? We change our main:

main :: IO()
main = defaultMain [
  bgroup "largepowmod" $
    flip map ([1,3..5] ++ [9999]) $ \i ->
      bench (printf "10^1000 + %d" i) $
        let n = 10^1000 + i :: Integer
        in nf (largepowmod 2 ((n - 1) `div` 2)) n
 , bgroup "largepowmod'" $
    flip map ([1,3..5] ++ [9999]) $ \i ->
      bench (printf "10^1000 + %d" i) $
        let n = 10^1000 + i :: Integer
        in nf (largepowmod' 2 ((n - 1) `div` 2)) n
  ]

And run it again (without -prof):

benchmarking largepowmod/10^1000 + 1
time                 16.14 ms   (16.07 ms .. 16.22 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.18 ms   (16.13 ms .. 16.23 ms)
std dev              124.6 μs   (99.83 μs .. 164.8 μs)

benchmarking largepowmod/10^1000 + 3
time                 16.44 ms   (16.26 ms .. 16.63 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 16.35 ms   (16.29 ms .. 16.42 ms)
std dev              168.3 μs   (135.2 μs .. 223.2 μs)

benchmarking largepowmod/10^1000 + 5
time                 16.24 ms   (16.19 ms .. 16.30 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.35 ms   (16.30 ms .. 16.41 ms)
std dev              138.4 μs   (89.59 μs .. 182.9 μs)

benchmarking largepowmod/10^1000 + 9999
time                 16.45 ms   (16.34 ms .. 16.58 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 16.37 ms   (16.30 ms .. 16.43 ms)
std dev              165.2 μs   (129.3 μs .. 235.4 μs)

benchmarking largepowmod'/10^1000 + 1
time                 14.54 ms   (14.49 ms .. 14.60 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 14.51 ms   (14.46 ms .. 14.54 ms)
std dev              101.0 μs   (64.28 μs .. 177.1 μs)

benchmarking largepowmod'/10^1000 + 3
time                 14.53 ms   (14.49 ms .. 14.58 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 14.53 ms   (14.50 ms .. 14.56 ms)
std dev              78.32 μs   (62.67 μs .. 95.66 μs)

benchmarking largepowmod'/10^1000 + 5
time                 14.42 ms   (14.36 ms .. 14.48 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 14.56 ms   (14.51 ms .. 14.65 ms)
std dev              180.4 μs   (92.90 μs .. 298.2 μs)

benchmarking largepowmod'/10^1000 + 9999
time                 14.60 ms   (14.49 ms .. 14.85 ms)
                     0.998 R²   (0.993 R² .. 1.000 R²)
mean                 14.61 ms   (14.53 ms .. 14.87 ms)
std dev              314.4 μs   (69.97 μs .. 618.3 μs)

We went from 16.14ms to 14.77ms (0.89 of original time), or if we extrapolate this to your 110s to 98s, which is closer to Mathematica's time.


Intersection function in Scala The problem is：

  Intersection: Given two (singly) linked lists, determine if the two
  lists intersect. Return the intersecting node. Note that the
  intersection is defined based on reference, not value.

  That is, if the kth node of the first linked list is the exact same
  node (by reference) as the jth node of the second linked list, then
  they are intersecting. Below is an example:

The code I wrote is as following, may I know any improvement can be done?

  def intersecton[A](alist: List[A], blist:List[A]): Option[A]= (alist.last, blist.last)match{
    case (a,b) if (a!=b) => None
    case (_,_) if (alist.size>1 && blist.size>1 && alist(alist.size-2) != blist(blist.size-2)) => Some(alist.last)
    case (a,b) if (alist.size ==1||blist.size ==1)&& a==b => Some(a)
    case (_,_) => intersecton(alist.dropRight(1), blist.dropRight(1))
  }

Below is the test case I already run:

val list1: List[Int]=List(5,6, 1, 1, 4)
val list2: List[Int]=List(6, 1, 1,4)
>>6

val list1: List[Int]=List(3,2,4)
val list2: List[Int]=List(5,6,7)
>>None

val list1: List[Int]=List(4,6,7)
 val list2: List[Int]=List(5,6,7)
>>6

intersecton(List(1, 2, 4), List(4, 5, 6)) incorrectly returns None.

You've asked several questions recently, and I keep seeing similar issues:

Using list.last: You have been advised to avoid traversing to the end of the list, for efficiency.  Lists should be manipulated at the head.
Functional thinking: These solutions involve too many tedious cases, and the code could be simplified by defining helper functions, or even restated entirely in terms of other functions.
Spelling: What's an "intersecton"?  (You previously misspelled "palindrome", twice.)
Inadequate testing: The counterexample cited above just happened to be the first test I tried, and it failed.  This isn't the first time I've seen an obviously wrong result.  Your first question was closed due to broken code, and it still hasn't been fixed.

You are welcome to use Code Review as a learning resource, but it would be a good idea to show some improvement between questions.


Finding the intersection of two sets of integers I need to pass a programming exam in order to graduate but I'm having a hard time passing it because most of my programs are too slow. Can someone give me some tips on how to make my programs faster please? Below is an example of a question we had in the last exam and the code i wrote. My code passed the first test case but for the other 3 it exceeded the time limit. Please let me know if you have any suggestions on how to improve my code.

  Description Given two sets of numbers, output their intersection set.

  Input There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.

  All the numbers are 32 bit signed integers.

  The input is terminated if N = 0.

  For case 1, 1 <= N, M <= 10^3  (Time Limit: 1 sec)
  For case 2, 1 <= N, M <= 10^4  (Time Limit: 1 sec)
  For case 3, 1 <= N, M <= 10^5  (Time Limit: 1 sec)
  For case 4, 1 <= N, M <= 10^6  (Time Limit: 3 sec)

  Output For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two
  sets is an empty set, print 「empty」 (without quotes).

  Sample Input 3 1 2 3 3 4 5 6 8 4 10 13 8
  9 2 1 5 4 4 2 3 1 5 1 2 2 3 2 5 1 2 2 3
  1 0

  Sample Output empty 1 2 4 1 2 2 3

This is my code:

#include<stdio.h>
#include<stdlib.h>

int set1[2][1000000];
int set2[2][1000000];
int intersection[1000000];

int main()
{
    int n;
    scanf("%d",&n);

    while( n!= 0)
    {
        int m, i, x, num, y = 0;
        int w, u, xx;

        for(i = 0; i < n; i++) //initialise set1 to 0
        {
            set1[1][i] = 0;
        }

        for(x = 0; x < n; x++) //put set1 in array
        {
            scanf("%d", &num);
            set1[0][x] = num;
        }

        scanf("%d",&m);
        for(i = 0; i < m; i++) //initialise set2 to 0
        {
            set2[1][i] = 0;
        }

        for(x = 0; x < m; x++) //put set2 in array
        {
            scanf("%d", &num);
            set2[0][x] = num;
        }

        for(x = 0; x < n; x++)
        {
            for(i = 0; i < m; i++)
            {
                if((set1[1][x] == 0) && (set1[0][x] == set2[0][i]) && (set2[1][i] == 0))
                {
                    intersection[y] = set2[0][i];//put in printing array
                    y++;
                    set2[1][i] = 1;
                    set1[1][x] = 1;
                }
            }
        }

        for(x = 0; x < y; ++x) //sort
        {
            for(i = x + 1; i < y; ++i)
            {
                if(intersection[x] > intersection[i])
                {
                    w = intersection[x];
                    intersection[x] = intersection[i];
                    intersection[i] = w;
                }
            }
        }

        for(x = 0; x < y; x++)//print
        {
            if(x == 0)
            {
                printf("%d", intersection[x]);
            }
            else printf(" %d", intersection[x]);
        }

        if (y == 0)
        {
            printf("empty");
        }
        printf("\n");

        scanf("%d",&n);
    }
    return 0;
}

Let's look at these two nested loops. How many times does the loop body need to be executed?

for(x = 0; x < n; x++)
{
    for(i = 0; i < m; i++)
    {
        /* loop body ... */
    }
}

The loop body gets executed \$ nm \$ times. But the problem statement says that we have \$ 1 \le n, m \le 10^6 \$, so in the worst case \$ n = m = 10^6 \$ and so the loop body gets executed \$ 10^{12} \$ times. There's no way to do that in just 3 seconds!

So you need to find a different algorithm, one that doesn't try to examine every pair of elements.

How might you do that? Well, here are two ideas:

Sort the two arrays, and then output the intersection by merging the sorted arrays.
Store the first input set in a data structure that has efficient lookup, for example a hash table or a radix tree, and then look up the numbers in the second input set.


Power-Guessing The Number I decided to help @Matt out a bit and ask a PowerShell question.  This is a simple guess-the-number game learning how to use functions with and without parameters, and use the input and output functions.  All comments are welcome.

Function GetNumber([int]$min, [int]$max) {
    Return Get-Random -minimum $min -maximum ($max + 1)
}

Function PlayGame() {
    Write-Host "This is a guess-the-number game.`r`nYou have 6 guesses to guess a number between 1 and 100."

    $secretNum = GetNumber 1 100

    [int]1..6 | ForEach {
        $guess = Read-Host
        If ($guess -eq $secretNum) {
            Write-Host "Correct!"
            Return
        }
        ElseIf ($guess -gt $secretNum) {
            Write-Host "Too high!"
        }
        Else {
            Write-Host "Too low!"
        }

        $remainingGuesses = 6 - $_
        Write-Host "You have $remainingGuesses guesses left"
    }

    Write-Host "The number was $secretNum"
}

PlayGame

# Borrowed from https://technet.microsoft.com/en-us/library/ff730938.aspx
Write-Host "Press any key to continue ..."
$host.UI.RawUI.ReadKey("NoEcho, IncludeKeyDown")

I have three points to make:

GetNumber:
The naming indicates it may be for integer conversion. While the truth is far from that, renaming might be a good idea.
Instead of having the function outside the main loop, have the max passed into PlayGame and simply do the operation in the game loop:
Function PlayGame([int]$max) {
    #...
    $secretNum = Get-Random -minimum 1 -maximum ($max + 1)
    #...
}
PlayGame 100

Multiline strings:
Instead of including new line characters in the string, use a multiline string, like so:
    Write-Host @"
This is a guess-the-number game.
You have 6 guesses to guess a number between 1 and 100.
"@

Note that any indentation you add ends up in the resulting string.

Type comparison
In PowerShell, as written in this Stack Overflow post:

On comparison a right value is converted to the type of a left value. Thus, '2' -gt 9 becomes '2' -gt '9', that is False, and '2' -gt 10 becomes '2' -gt '10', that is True.

This is a potential bug. I would recommend a helper method that converts the input to an integer, and tests its boundaries. Obviously in a number guessing game, 100000000 isn't a valid guess for a limit of 100. Not to mention the above type coercion.
If you don't really care about people putting in massive amounts because they're idiots, than you can just swap the order of the operators, and the guess will be coerced to an integer.


Converting inches to feet This was a homework assignment that I'm now done with - I submitted it as is. However the fact that I needed to use the same code twice bugged me... The double code is:

printf("Enter a distance in inches (0 to quit): ");
scanf("%f",&input);

Is there a better way to do the same thing in my loop instead of the double scanf/printf? It does need to quit the program immediately if a 0 is entered.

#include <stdio.h>
int main()
{
    float distance, floatFeet, input;
    int feet;

    printf("Enter a distance in inches (0 to quit): ");
    scanf("%f", &input);
    while (input != 0)
    {
        feet = input/12;
        distance = (input-feet*12);
        floatFeet = input/12;
        printf("%d feet and %f inches or %f feet \n\n", feet, distance, floatFeet);
        printf("Enter a distance in inches (0 to quit): ");
        scanf("%f", &input);
    }
}

You could move the duplicated lines into a function, something like this should work:

#include <stdio.h>

float get_input(void)
{
    float input;

    printf("Enter a distance in inches (0 to quit): ");
    scanf("%f", &input);

    return input;
}

int main()
{
    float inches, floatFeet, input;
    int feet;

    while (input = get_input())
    {
        feet = input/12;
        inches = (input-feet*12);
        floatFeet = input/12;
        printf("%d feet and %f inches or %f feet \n\n",feet,inches,floatFeet);
    }

    printf("Goodbye!\n");
}


Shorter way to write list-as-dict-value in Python? I have a data structure that looks like this:

a = {
     'red': ['yellow', 'green', 'purple'],
     'orange': ['fuschia']
    }

This is the code I write to add new elements:

if a.has_key(color):
    a[color].append(path)
else:
    a[color] = [path]

Is there a shorter way to write this?

You can use collections.defaultdict:

from collections import defaultdict

mydict = defaultdict(list)

Now you just need:

mydict[color].append(path)

defaultdict is a subclass of dict that can be initialized to a list, integer...

btw, the use of has_key is discouraged, and in fact has_key has been removed from  python 3.2.
When needed, use this by far more pythonic idiom instead:

if color in a:
    ........


Letter detector code I have created this function where it detects the first letter of the string provided. I was hoping if you guys can take a look, give your opinion about it and help me to improve it.

 //This function takes a string and outputs
 //its first letter
 function letterDetector(str){
      //Checking if string is an empty string
      if(str === "" || str === undefined)
      {return ("Please input an argument");}

      var alphabetsArr = "abcdefghijklmnopqrstuvwxyz".split("");
     //making user input to lower case
     var string = str.toLowerCase().replace(/[^0-9a-z]\d+/gi, '');
     var result = alphabetsArr.map(letter => {
     if( string.charAt(0) === letter ){
        //logging out the letter as upper case
        console.log("Your first name letter is" + " " + letter.toUpperCase());
     }
   });
}
letterDetector("Adam"); //output A
letterDetector("£1%Adam"); //output A
letterDetector(""); or letterDetector(); //output Please input an argument

While this function does what you want, it can be greatly simplified.

function letterDetector(str) {
  if (!str) { //Handles both undefined and the empty string
    return "Please input an argument"
  }
  // Replace everything that isn't the letter, then get the first letter.
  const firstLetter = str.replace(/[^a-z]/gi, '').charAt(0)
  return "Your first name letter is " + firstLetter.toUpperCase()
}

for (const str of ["Adam", "£1%Adam", "", undefined]) {
  console.log("'" + str + "'", "-->", letterDetector(str))
}

A few things to note about your implementation:

return is not a function, there is no need to wrap what you are returning with parenthesis (and generally you shouldn't).
Be consistent. Should this function log to the console or return the result? Personally, I prefer returning to avoid side effects, which will help keep your code simpler when working on more complex projects.
Uncovered edge case: What if I input 123?
Don't use (near) keywords as variable names. string looks very close to String and could easily be mistaken for it.
Though in this case it seems you aren't handling non-ascii characters, it is a good idea to use toLocaleLowerCase() and toLocaleUpperCase() instead of toLowerCase() and toUpperCase() to avoid a multitude of problems with languages other than English.
Don't define variables you don't use, result is never used and thus can be dropped.
Since you use arrow functions, you can use const and let instead of var. This is a good switch to make in order to easily avoid any future pain where variables aren't scoped as you expect (especially if you work with other languages like C or Java where everything is block scoped, var is function scoped)


Fetching and formatting content from a database I've wrote this script to fetch and format content from my DB. It also counts how many result there are and separates them into pages. I'm barely learning PHP and MySQL so I don't know much about performance.

function fetch_content($section, $subsection, &$count, $page = 0){
    $section = substr($section, 0,8);
    $subsection = substr($subsection, 0,8);
    require_once("system/config.php");
    //Initiate connection
        $mysqli = new mysqli($db_host, $db_user, $db_password, $db_database);
        if ($mysqli->connect_error) {
            die('Connect Error (' . $mysqli->connect_errno . ') '. $mysqli->connect_error);
        }
    //Select page
        $limit = 2;
        $start = $page * $limit ;

    //select query
        if($section == 'home' || ($section != 'home' && $subsection == NULL)){
            $selection =  "WHERE section = ?";
            }
        else
            $selection = "WHERE section = ? AND subsection = ?";

    //Fetch data
        $stmt = $mysqli->stmt_init();
        $qry= "SELECT * FROM public
        $selection
        ORDER BY id DESC LIMIT ?,?";
        $stmt->prepare($qry);
        if($section == 'home' || ($section != 'home' && $subsection == NULL))
            $stmt->bind_param("sss", $section, $start , $limit);
        else
            $stmt->bind_param("ssss", $section, $subsection, $start , $limit);
        $stmt->execute();
        $result = $stmt->get_result();
    //Format the data
        while( $row =  $result->fetch_assoc()){
            format_home($row, $mysqli);
        }
        $stmt->close();
    //Count result
        $stmt = $mysqli->stmt_init();
        $qry= "SELECT COUNT(*) AS count FROM public  $selection";
        $stmt->prepare($qry);
        if($section == 'home' || ($section != 'home' && $subsection == NULL))
            $stmt->bind_param("s", $section);
        else
            $stmt->bind_param("ss", $section, $subsection);
        $stmt->execute();
        $result = $stmt->get_result();
        $count = $result->fetch_assoc();
        $count =  $count['count'];
        $stmt->close();
    //close connection
        $mysqli->close();
}

I would make a single file with the MySQL server connection, so you can use the same connection in other functions, etc..

Also you should pass string variables directly.

$stmt->prepare("SELECT COUNT(*) AS count FROM public  $selection");

Did you know, that you can check every single called function if a error occurred?
For example:

if(!($stmt->execute()) {
   die('Unable to execute!'. $mysqli->error);
}

The next point is, why do you execute another query to count the result rows?
In the mysqli_stmt object $num_rows. http://php.net/manual/en/mysqli-stmt.num-rows.php


Producing full list of Fibonacci numbers which fit in an Int I am progressing through the problems listed at projecteuler.com as I learn Scala (my blog where I am covering this experience). I have written a function to produce all the Fibonacci numbers possible in an Int (it's only 47). However, the resulting function feels imperative (not functional).

  val fibsAll = {
    //generate all 47 for an Int
    var fibs = 0 :: List()
    var current = fibs.head
    var next = 1
    var continue = true
    while (continue) {
      current = fibs.head
      fibs = next :: fibs
      continue = ((0.0 + next + current) <= Int.MaxValue)
      if (continue)
        next = next + current
    }
    fibs.reverse
  }

I am looking for feedback on this code:

To what degree does the presence of even a single var (there are four here) indicate an erred approach from a functional standpoint?
Given I want to return a List[Int], what better way is there to do this recursively as opposed to my current (odd) "while loop" approach?

I am finding the transition from imperative to functional thinking quite challenging.

object Euler002 extends App{
  // Infinite List (Stream) of Fibonacci numbers
  def fib(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fib(b, a+b))

  // Take how many numbers you want into a List
  val fibsAll = fib() takeWhile {_>=0} toList
  fibsAll reverse
}

Take a look at this.


Check if a Binary Tree  is aBinary Search Tree I'm understanding the question, but I want to know whether or not my implementation is correct.

The question is:

  Write a method that accepts as its argument a BinaryTree object and
  returns true if the argument tree is a binary search tree. Examine
  each node in the given tree only once.

This is my implementation:

public boolean isBST (BinaryTree<String> tree)
{
    BinaryNode Node = new BinaryNode (tree.getRootData);
    if(tree == null || Node.isLeaf() )
        return true;

    if(Node.getData > Node.getLeftChild && Node.getData < Node.getRightChild)
    {
        boolean leftTree = isBST(new BinaryTree(Node.getLeftChild));
        boolean rightTree = isBST(new BinaryTree(Node.getRightChild));
        return leftTree && rightTree ;
    }
    else return false ;
}

There are some serious problems with this function.

Issues of correctness

Code won't compile: If BinaryNode indeed has fields named getData, getLeftChild, and getRightChild that are of type String, then you can't use operators < and > on them.  For strings, as with any object, you have to use a.compareTo(b).
No consideration for unbalanced or incomplete trees: If a node has only one child, what happens?
Check for tree == null after tree.getRootData: There's no point in checking for tree == null, since it would have crashed on tree.getRootData with a NullPointerException already if that were the case.
Recursive check is insufficient: As @user2668926 points out, you have to verify that all nodes within a subtree fall within a range of values.

Serious violations of style conventions

Using an uppercase variable name: In Java, variable names should be lowerCase, except constants, which should be ALL_CAPS.  By naming a variable Node, you hurt readability tremendously by making it look like the name of a class.
Using getSomething as field names: The convention is that getSomething() is the name of a getter method (i.e., a member function), usually corresponding to an instance variable named something.  Instead, you seem to have instance variables named getRootData, getData, getLeftChild, and getRightChild in your BinaryTree and BinaryNode classes, which is exceedingly weird.

I consider these two issues to be extremely serious, even if the compiler accepts the code and the algorithm runs.  These are not "merely" conventions — they are major traps for anyone else who works with your code, enough for every programmer to go facepalm.

Less serious issues of style

Distinction between BinaryTree and BinaryNode: Wrapping nodes as trees and unwrapping the tree's root node is cumbersome.  Do you really have to make a distinction between trees and nodes?  Could you not just treat any node as a tree rooted there?
Use of generics: The BinaryTree class is genericized, so your code should also aim to be generic.  The method signature should look something like

public class BSTVerifier {
    public static <T extends Comparable> boolean isBST(BinaryTree<T> tree) {
        ...
    }
}

Alternatively,

public class BSTVerifier<T extends Comparable> {
    public boolean isBST(BinaryTree<T> tree) {
        ...
    }
}


Property to compare in Linq is different by criteria. I feel like repeating myself but i don't know how to refactor this.
Linq condition is the same but property to compare is different
(BookingDate ,CheckInDate ,CheckOutDate)

    protected void FilterByDateRange(ref IEnumerable<ViewBooking> pObjListBooking)
    {
        DateTime startDate;
        DateTime endDate;

        startDate = DateTime.ParseExact(txtStartDate.Text, "d", System.Globalization.CultureInfo.CurrentCulture);
        endDate = DateTime.ParseExact(txtEndDate.Text, "d", System.Globalization.CultureInfo.CurrentCulture).AddDays(1);

        switch(ddlOrderBy.Text)
        {
            case "Booking Date":
                pObjListBooking = pObjListBooking.Where(item => item.BookingDate >= startDate && item.BookingDate < endDate);
            break;

            case "Check In Date":
                 pObjListBooking = pObjListBooking.Where(item => item.CheckInDate >= startDate && item.CheckInDate < endDate);
           break;

            case "Check Out Date":
                pObjListBooking = pObjListBooking.Where(item => item.CheckOutDate >= startDate && item.CheckOutDate < endDate);
            break;
        }
    }

You could do something like this, but I don't know, whether it's a good idea:

Func<ViewBooking,DateTime> getDate = null;
switch(...)
{
    case ...:
    getDate = (ViewBooking item) => item.BookingDate;
    break;
}

pObjListBooking = pObjListBooking.Where(item => getDate(item) >= startDate && getDate(item) < endDate);


How to optimize Karatsuba algorithm (using arraylist and java) I was using Karatsuba algorithm to multiply two polynomials and return the coefficients and I am using java, we are asked to use arraylists here, however, my code is too complicated and it takes much longer to run than I expected, can anyone help me with reducing the running time and simplify my code? Thanks a lot!
public static List<Long> smellCosmos(List<Long> a, List<Long> b) {
    int n = a.size();
    int n1 = a.size() / 2;

    List<Long>c = new ArrayList<Long>();

    if (n == 1) {
        c.add(0, a.get(0) * b.get(0));
        return c;
    };

    List<Long>ahigh = new ArrayList<Long>(n1);

    List<Long>alow = new ArrayList<Long>(n1);

    List<Long>amed = new ArrayList<Long>(n1);

    List<Long>bhigh = new ArrayList<Long>(n1);

    List<Long>blow = new ArrayList<Long>(n1);

    List<Long>bmed = new ArrayList<Long>(n1);

    for (int i = 0; i < n1; i++) {
        ahigh.add(a.get(i));
        alow.add(a.get(i + n1));
        amed.add(alow.get(i) + ahigh.get(i));
        bhigh.add(b.get(i));
        blow.add(b.get(i + n1));
        bmed.add(blow.get(i) + bhigh.get(i));
    }

    List<Long>chigh = smellCosmos(ahigh, bhigh);
    List<Long>clow = smellCosmos(alow, blow);
    List<Long>cmed = smellCosmos(amed, bmed);

    for (int j = 0; j < n1; j++)
        c.add(chigh.get(j));

    for (int m = 0; m < cmed.size(); m++)
        c.add(cmed.get(m) - chigh.get(m) - clow.get(m));

    for (int g = cmed.size() - n1; g < clow.size(); g++)
        c.add(clow.get(g));

    for (int i = n1; i < chigh.size(); i++)
        c.set(i, c.get(i) + chigh.get(i));

    for (int i = 0; i < cmed.size() - n1; i++)
        c.set(n1 * 2 + i, c.get(n1 * 2 + i) + clow.get(i));

    return c;

}
```

Reduce running time

Maybe you can use subList to prevent new lists that are basically a copy of a part of the input? This saves a lot of autoboxing (which I assume is the bottle neck, if the algorithm is implemented correctly). You could profile your application to see where most time is spend.

For example:  ahigh = a.subList(0,n1);

You can initialize List c with a size, as you know the length it will be.

Use addAll whenever you can, it will use the faster System.arrayCopy internally if possible.


Returning generic types from Repository Is it bad design if I create repostory with methods that returns generic types. For example in AccountsRepository if I have:

public class Repository<T> : IRepository<T>
where T : class
{
}

public class AccountsRepository<TUser> :
Repository<User>,IAccountsRepository
    where TUser : class,IUser,new()
    {
      public TUser GetUserByUserName(string username)
      {
       return this.context.User.Where(s =>
       s.UserName.Equals(username)).Select(c=>new TUser(){ Password =c.Password }).FirstOrDefault();
      }
    }

Is this the proper way of doing that. So It's something like I return DTO object but it is generic type. So my classes using repository doesn't have to know what types are the objects in database.

Is it bad design if I create repostory with methods that returns generic types.

Not at all. It's very useful.

  Is this the proper way of doing that?

I'm not entirely sure because even though you use a generic return type you use the same User table for all of them:

this.context.User

However if the IRepository provides different User tables where each of the different users implement the TUser then I'd say it' fine. Otherwise it would not be that usefull and you could just return the normal User.