Fibonacci implementation in Go At the end of the Day 1 Go Course slides (pdf) there is an exercise stated as follows (NOTE: the course in the linked presentation is considered obsolete. If you are looking to learn Go the suggested route is first via http://tour.golang.org):

  You all know what the Fibonacci series is. Write a package to implement it. There should be a function to get the next value. (You don't have structs yet; can you find a way to save state without globals?) But instead of addition, make the operation settable by a function provided by the user. Integers? Floats? Strings? Up to you.

How does the following solution rate with respect to its 'Go'-iness?

package fib

type BinOp func (uint64, uint64) uint64

func fib_intern(a, b uint64, op BinOp) uint64 {
    Fib = func(opnew BinOp) uint64 {
        return fib_intern(b, op(a,b), opnew)
    }
    return a
}

var Fib = func(op BinOp) uint64 {
    return fib_intern(0,1,op)
}

Which can then be called like:

package main

import (
    "./fib"
    "fmt"
)

func add(a, b uint64) uint64 {
    return a+b
}

func main() {
    for i := 0; i < 20; i++ {
        fmt.Println(fib.Fib(add))
    }
}

The link is dead and the code doesn't compile, but there is still an obvious issue to critique:  Part of the challenge was to not save state with "global variables."  In Go, package variables of the package main are typically considered "global variables".  However, only a single instance of any package ever exists at run time, so package variables of all packages are essentially global variables as well.  The code here uses a package variable fib.Fib, thus the code is failing the exercise from the start, working or not.

Edit:  Thank you Anthony for tracking down the archived course and updating the question.  It helps to have the full context.  It also helps to have code working with a current version of Go, which is pretty easy:

package fib

type BinOp func(uint64, uint64) uint64

var Fib func(op BinOp) uint64

func init() {
    Fib = func(op BinOp) uint64 {
        return fib_intern(0, 1, op)
    }
}

func fib_intern(a, b uint64, op BinOp) uint64 {
    Fib = func(opnew BinOp) uint64 {
        return fib_intern(b, op(a, b), opnew)
    }
    return a
}

Go now has stricter checking of static dependencies and reports "initialization loop" with the old code.  My update of your code works by moving the initial assignment of Fib to an init function, which runs at program startup.

I'll abandon this answer now and add another answer where I try to stick to your request for a review of the 'Go'-iness.


An Either Monad in Java Interested in a review of this code, in particular the (hopefully monadic) bind. I actually put this to good use. It was a nice complement to Guava's Optional, and shorter than:

  Optional.fromNullable(x).or(y);

And I threw in a bind method, which I think lifts it up into monad space.

One question I wasn't sure of the the semantics of multiple calls. Should I carry along the original default value, or does each new value become the default? So in psuedo code, should

  Either.with("A").or("B").or(null)

result in "A" (the original default) or "B"? I thought "B" made more sense.

I'm interested in if I got the monad signature & semantics right.

public class Either<A> {

    private final A value;

    /**
     * constructor sets the default & value the same
     * @param defaultValue
     */
    Either(A value) {
        if (value == null) {
            throw new IllegalArgumentException("Either cannot be null");
        }
        this.value = value;
    }

    /**
     * constructor sets the default & value the same
     * @param defaultValue
     */
    Either(A defaultValue, A value) {
        this.value = (value == null) ? defaultValue : value;
    }

    /**
     * the unit method lifts the value into the monadic space
     *
     * @param value
     * @return an either with the value as default
     */
    public static <A> Either<A> with(A value) {
        return new Either<A>(value);
    }

    /**
     * create a new either using the previous default
     *
     * @param value
     * @return
     */
    public Either<A> or(A value) {
        return new Either<A>(this.value, value);
    }

    /**
     * @return the value, or the default
     */
    public A get() {
        return value;
    }

    /**
     * completes this class as a monad
     *
     * @param f
     * @return an either of the new type
     */
    public <B> Either<B> bind(Function<A, Either<B>> f) {
        return f.apply(value);
    }
}

And here are the unit tests for bind (and sample usage):

static class ToInt implements Function<String, Either<Integer>> {

    private final int defaultInt;

    /**
     * lol closures in java
     *
     * @param defaultInt
     */
    public ToInt(int defaultInt) {
        this.defaultInt = defaultInt;
    }

    @Override
    public Either<Integer> apply(String s) {
        try {
            return Either.with(Integer.parseInt(s));
        }
        catch (NumberFormatException nfe) {
            return Either.with(defaultInt);
        }
    }
};

private static final Function<Integer, Either<Double>> SQRT = new Function<Integer, Either<Double>>() {
    @Override
    public Either<Double> apply(Integer i) {
        return Either.with(Math.sqrt(i));
    }
};

private static final int TEN_THOUSAND = 10000;
private final ToInt TO_INT = new ToInt(TEN_THOUSAND);

// ~=~=~=~=~=~=~=~=~=~=
// Tests

public void bindToIntEmptyEXPECTDefault() {
    // Arrange
    Either<String> a = Either.with("");

    // Act
    Either<Double> b = a.bind(TO_INT).bind(SQRT);

    // Assert
    assertEquals(b.get(), 100.0);
}

public void bindToIntFormatEXPECTDefault() {
    // Arrange
    Either<String> a = Either.with("zoom");

    // Act
    Either<Double> b = a.bind(TO_INT).bind(SQRT);

    // Assert
    assertEquals(b.get(), 100.0);
}

public void bindToIntEXPECTInt() {
    // Arrange
    Either<String> a = Either.with("144");

    // Act
    Either<Double> b = a.bind(TO_INT).bind(SQRT);

    // Assert
    assertEquals(b.get(), 12.0);
}

I have a nit-pick with the logic in your Either.or(A) method. You have:

public Either<A> or(A value) {
    return new Either<A>(this.value, value);
}

but, since Either is immutable (oh, should Either be a final class? ... I think so...), it makes sense that the or method can return the exact instance if it is valid.... why does it have to create a new instance each time? In a stream that can create a lot of GC churn....

I would write that method:

public Either<A> or(A value) {
    return value == null ? this : new Either<A>(value);
}

I know that essentially duplicates the constructor, but, doing it this way avoids the constructor in (hopefully) many places entirely.

This leads on to your question:

  One question I wasn't sure of the the semantics of multiple calls.
  Should I carry along the original default value, or does each new
  value become the default? So in psuedo code, should

Either.with("A").or("B").or(null)

  result in "A" (the original default) or "B"? I thought "B" made more
  sense.

If the or(A) method does not need to construct a new instance, then it makes sense to me that the semantics should return "A", since that allows skipping new instances for "B" and null.


Extracting a list of hyperlinks I need to produce a list objCollector with some results:

objCollector = []

      allRows.each () ->
        obj =
          source: self.source
          url: ''
          host: ''

        currentTag = $(this)
        links = currentTag.find('a')
        getTextFromSpan = currentTag.find('span.lnk').text()
        extractedLink = links[0].attribs.href
        obj.url = self.baseUrl + extractedLink
        obj.host = getTextFromSpan

        objCollector.push obj

Instead of building the result by appending to an empty list, could this be done more elegantly by using something like map?

I just moved things around to make it a bit more readable. You can use the map function instead of each. The signature of map is as follows:

element in array
index of element
the array itself

I've added those parameters in the coffee script, but you could have easily done without them for a cleaner look. I assumed that self is some kind of global variable or variable available to the inner scope of the map.

See the Mozilla article on map. It's fantastic!

objCollector = allRows.map (element, index, context) ->
  tag = $(element)

  text = tag.find('span.lnk').text()
  link = tag.find('a').first().attribs.href

  {
    source: self.source
    url: self.baseUrl + link
    host: text
  }


Pub/Sub in JavaScript This seems to work, but for some reason I'm not entirely sure about it.

Can anyone point out any issues with this simple pub/sub library?
Thank you!

(function (undefined) {
    window.mylib = $.extend(window.mylib, (function () {

        var subscriptionsBag = function() {
            var self = this;
            self.count = -1;
            self.handlers = {};

            var cancel = function(index) {
                var self = this;
                delete self.handlers[index];
            };

            self.add = function (fn) {
                if (typeof(fn) !== "function") {
                    throw new Error("function expected.");
                }

                var index = ++self.count;
                self.handlers[self.count] = fn;

                return {
                    cancel: cancel.bind(self, index)
                };
            };

            self.fire = function(obj) {
                for (var handlerKey in self.handlers) {
                    if (!self.handlers.hasOwnProperty(handlerKey)) {
                        continue;
                    }
                    var handler = self.handlers[handlerKey];
                    if (!handler) continue;
                    handler(obj);
                }
            };
        };

        var subscriptions = {
            "": {}
        };

        var publish = function(e, obj) {
            var evt = "@" + e;
            var subs = subscriptions[evt];
            if (!subs) return;

            subs.fire(obj);
        };

        var subscribeTo = function (e, fn) {
            var evt = "@" + e;
            var subs = subscriptions[evt] = (subscriptions[evt] || new subscriptionsBag());
            return subs.add(fn);
        };

        var events = {
            publish: publish,
            subscribeTo: subscribeTo
        };

        return {
            events: events
        };
    })());
})();

Member names

The code is confusing because it involves neither event dispatch nor event handling - therefore is nothing to do with events - yet there are member names evt and events, where :

the evt vars are actually uids used as object keys
the events object contains references to methods.

The loose-coupled nature of Pub/Sub does indeed tempt you into believing that it involves events. But no, it does not (at least typically not, and certainly not here). Whereas a Pub and its corresponding Subs can be in completely diffferent parts of the code base, when a Pub fires it informs the subscribers synchronously, in the same event thread.

Similarly, the subscriptions object is not well named. It receives objects which can themselves be subscribed to, not subscriptions directly. If anything was to be named "subscriptions" it would be SubscriptionsBag's self.handlers - each handler is effectively a subscription.

Leveraging jQuery.Callbacks

You are already using jQuery - great!

The jQuery documentation includes a really neat example under jQuery.Callbacks(), showing how Callbacks() instances can be exploited for Pub/Sub.

If you were to adopt this approach, it would :

take all the pain out of having to write/test your own .add(), .cancel() and fire() methods
replace your SubscriptionsBag() with a Topic() constructor
replace your subscriptions repository with a topics repository
give you nice monads that will method-chain.

You need do little more than adopt jQuery's code and assign the Topic constructor to your chosen namespace in lieu of jQuery, and trap the topics repository in a closure (or otherwise avoid the global namespace).

(function (lib, topics) {
    lib.Topic = function Topic (id) {
        var callbacks,
            topic = id && topics[id];
        if (!topic) {
            callbacks = jQuery.Callbacks();
            topic = {
                publish: callbacks.fire,
                subscribe: callbacks.add,
                unsubscribe: callbacks.remove
            };
            if (id) {
                topics[id] = topic;
            }
        }
        return topic;
    };
})(window.mylib, {});

Thus, your versions of the usage examples in the jQuery documentation would be :

// Subscribers
window.mylib.Topic( "mailArrived" ).subscribe( fn1 );
window.mylib.Topic( "mailArrived" ).subscribe( fn2 );
window.mylib.Topic( "mailSent" ).subscribe( fn1 );

// Publishers
window.mylib.Topic( "mailArrived" ).publish( "hello world!" );
window.mylib.Topic( "mailSent" ).publish( "woo! mail!" );

And an example involving asynchronously derived data :

// Subscriber
var mailArrivedTopic = window.mylib.Topic("mailArrived").subscribe(fn1); // Note how the subscribe() method returns the Topic instance (monadic behaviour).

// Publisher
$.ajax({...}).then(mailArrivedTopic.publish);


Prime numbers that are also a prime number when reversed This is a challenge on Codewars I took years ago. Task is to find all prime numbers that are also a prime number when reversed, i.e. 13 -> 31 is such a number.
This is still the answer with the most upvotes in the categories 'Best practice' as well as in 'Clever'.
Any improvements or thoughts about this piece of code? Please keep in mind in code challenges like this I always try to code as concise as possible.
Examples in => output :
    backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97]
    backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967]
    backwardsPrime(501, 599) => []

code:
public class BackWardsPrime {

    public static String backwardsPrime(long start, long end) {
        StringBuilder sb = new StringBuilder();
        while(start <= end){
            long rev = Long.parseLong(new StringBuilder(
            String.valueOf(start)).reverse().toString());
            if(start > 12 && isPrime(rev) && isPrime(start) && start != rev)
                sb.append(start + " ");
            start++;
        }
        return sb.toString().trim();
    }

    static boolean isPrime(long n) {
        if(n % 2 == 0) return false;
        for(int i = 3; i * i  <= n  ; i += 2) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}

Name Classes properly.
What is a "Back Wards Prime"?  I have no idea.  I can guess what a Backward Prime is; perhaps you need to change the capitalization of the class!
I'm told that name is dictated by the coding challenge, so you can't change it for your challenge submission; but I'm leaving this comment stand -- the required class name is horrible.
Name variables properly.
This condition is confusing:
    if ( ... && start != rev)

Is this really testing if the reversed value is different from the starting value?  No!  You're using the starting value as the loop variable, and continuously incrementing it with start++;.  Make a new loop variable, and use a proper loop.
    for(long candidate = start; candidate <= end; candidate++) {
        ...
    }

Reducing the work
You appear to have determined that any single digit prime, when read backwards, will not be different than the original, as well as 10 & 12 not being prime, and 11 not being different when reversed.  Therefore, you need only consider values greater than 12.  This optimization should be done before the loop starts,
to avoid the overhead of testing the condition at each iteration.
You should also notice that 2 is the only even prime number, therefore you need not look at any even value.  Instead of moving the start value up by 1, you could skip even values by incrementing by 2.
    if (start < 13)
        start = 13;
    else if (start % 2 == 0)
        start += 1

    for(long candidate = start; candidate <= end; candidate += 2) {
        ...
    }

Avoid creating unnecessary intermediate results
Consider:
new StringBuilder(String.valueOf(start))

You are passing an integer to function which converts it into a string, and then returns that string.  How does that function work?  You then take that resulting string, and pass it to the constructor of the StringBuilder, to copy into the working area.  Do you need that intermediate string?
new StringBuilder().append(candidate)

The StringBuilder.append(long) function takes a long value, and converts it into string characters directly inside the StringBuilder.  This could potentially be faster.  It is even 3 characters shorter, while using a longer variable name, so it is certainly more concise!
Also, consider sb.append(start + " ");. This converts start to a string (again), adds " " to it (internally using another StringBuilder!), and then appends this brand new string to sb.  Instead, you could write:
sb.append(candidate).append(' ');

No intermediate strings needs to be constructed and discarded.
Avoid useless work
        long rev = ...;
        if(start > 12 && isPrime(rev) && isPrime(start) && start != rev)
            ...

If start is not prime, is there any point computing rev?
    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = ...;
            if (isPrime(rev) && candidate != rev)
                sb.append(candidate).append(' ');
        }
    }

Better.  But what about that candidate != rev?  That looks like a very fast test, and isPrime(rev) is probably much, much slower.
    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = ...;
            if (candidate != rev && isPrime(rev))
                sb.append(candidate).append(' ');
        }
    }

But wait!  How many times will candidate != rev be false?  Very rarely?  It may not gain anything, and the change may even slow the program down.  Always profile!
Performance at the cost of conciseness
Constructing a new StringBuilder inside the loop can be a costly operation.  You could construct one outside the loop, and use the .setLength(0) method to clear it, for the next iteration:
    StringBuilder temp = new StringBuilder();

    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = Long.parseLong(temp.append(candidate).reverse().toString());
            if (isPrime(rev) && candidate != rev)
                sb.append(candidate).append(' ');
            temp.setLength(0);
        }
    }

Major optimizations
Reduced search space
How many primes in the ranges 200-299, 400-699, and 800-899 will be reversible primes?  How about in the ranges 2000-2999, 4000-6999, 8000-8999?  How many in the ranges 20000-29999, 40000-69999, 80000-89999?  And so on?
Zero.  A reversible prime cannot start with a 2, 4, 5, 6, or 8, because when reversed, the number will be divisible by two or five, and thus won't be prime.
Implementing this observation in an efficient manner would certainly not make the code concise, but would dramatically speed it up.  Left to student.
Sieve of Eratosthenes
You are potentially doing many, many primality checks using trial division.  It may make more sense to use the Sieve of Eratosthenes to generate a BitSet of prime flags.  Then isPrime(candidate) becomes a simple \$O(1)\$ lookup: prime.get(candidate).
Alternately, if maintaining a BitSet of \$10^{\lceil \log_{10}{end} \rceil}\$ bits is too memory intensive, use the sieve to generate the prime numbers up to \$\sqrt{10^{\lceil \log_{10}{end} \rceil}}\$, and use trial division with just those prime numbers, to avoid pointless trial division by odd composite numbers (9, 15, 21, 25, 27, 33, ...).


Compile time integer square root for large numbers This computes the integer square root at compile time for any \$0 \le N \le L\$ where \$L\$ is the largest integral representation of template parameter T.

This was motivated by the fact that many of the algorithms I found were not able to handle large values of \$N\$. I also just wanted to practice template meta-programming.

Important: I cannot simply declare the runtime algorithm as a constexpr function because my compiler does not allow it.

The implementation is based on this runtime algorithm:

template <typename T>
T rt_square_root( T num )
{
    T bit{ static_cast<T>( 1 ) << ( sizeof( T ) * 8 - 2 ) };

    while ( bit > num )
        bit >>= 2;

    T res{ 0 };
    while ( bit )
    {
        T delta{ res + bit };
        if ( num >= delta )
        {
            num -= delta;
            res = ( res >> 1 ) + bit;
        }
        else
        {
            res >>= 1;
        }
        bit >>= 2;
    }
    return res;
}

Source

square_root.h

Template meta-programming based implementation of the algorithm:

#ifndef CR_SQUARE_ROOT_H
#define CR_SQUARE_ROOT_H

namespace ct
{
    template <typename T, typename U>
    bool constexpr greater( T a, U b )
    {
        return b < a;
    }

    template <typename T, T num, T bit, bool condition = true>
    class calc_shifted_bit
    {
    private:
        static T constexpr shifted_bit = bit >> 2;

    public:
        static T constexpr result = calc_shifted_bit<T, num,
            shifted_bit, ct::greater( shifted_bit, num )>::result;
    };

    template <typename T, T num, T bit>
    class calc_shifted_bit<T, num, bit, false>
    {
    public:
        static T constexpr result = bit << sizeof( T ) / 2;
    };

    template <typename T, T num, T res, T bit, typename = void>
    class calc_sqrt
    {
    private:
        static T constexpr delta = res + bit;
        static bool constexpr num_gt_delta = num >= delta;

    public:
        static T constexpr result = calc_sqrt
            <T,
            num_gt_delta ? num - delta : num,
            num_gt_delta ? ( res >> 1 ) + bit : ( res >> 1 ),
            ( bit >> 2 )
            >::result;
    };

    template <typename T, T num, T res, T bit>
    class calc_sqrt<T, num, res, bit, std::enable_if_t<( bit == 0 )>>
    {
    public:
        static T constexpr result = res;
    };

    template <typename T, T n>
    struct sqrt
    {
        static T constexpr result =
            calc_sqrt
            <T, n, 0,
                calc_shifted_bit
                <T, n,
                static_cast<T>( 1 ) << ( sizeof( T ) * 8 - sizeof( T ) / 2 )
                >::result
            >::result;
    };
}

main.cpp

Some tests, compilation time seems fast, but I'm not very experienced with template meta-programming costs:

#include <limits>

int main()
{
    using ULL = unsigned long long;
    using UL  = unsigned long;

    auto constexpr n_max64bit = std::numeric_limits<ULL>::max();
    auto constexpr n_max32bit = std::numeric_limits<UL>::max();

    static_assert(
        ct::sqrt<ULL, n_max64bit>::result == n_max32bit,
        "bad square root" );

    static_assert(
        ct::sqrt<ULL, n_max32bit * n_max32bit>::result - 2 == n_max64bit,
        "bad square root" );
}

Since you're on a C++14 compiler, the simplest solution is just to stick constexpr in front of your runtime algorithm:

template <typename T>
constexpr T rt_square_root(T num)
{
    /* exact same code as before */
}

static_assert( rt_square_root(N_1 * N_1) == N_1, "bad square root" );

I'm not sure there's a compelling reason to do it any other way.


Re-arrange a string into a { consonant, vowel, consonant, vowel ... } sequence I was prompted to give someone advice about the following problem:

Given a string with equal amount of vowels and consonants, re-arrange it so that it follows the sequence { consonant, vowel, consonant, vowel, ... }
For Example given "abed" modify it to be "bade".  The order of the vowels and consonants must be the same, "dabe" nor "beda" are acceptable answers.

It was a "first year" type question, no std::string, no strlen, no copying the characters somewhere else, ...

Anyway, I came up with this.  Basically, while iterating through the string, if the character isn't what we're looking for, move another pointer forward until it finds one.  Once found, store it and then shift each character one to the right to make space for the character that we want:

#include <iostream>

bool isVowel( const char ch )
{
  return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

void rearange( char *str )
{
  bool on_consonant = true;

  while ( *str )
  {
    bool is_vowel = isVowel( *str );

    if ( ( on_consonant && is_vowel ) || ( !on_consonant && !is_vowel ) )
    {
      char *ptr = str + 1; // we don't get here with a valid string
      while ( isVowel( *ptr ) == is_vowel )
        ++ptr;

      // ptr now points to the first type we are looking for
      char swap = *ptr;

      // move each character up the line
      while ( ptr != str )
      {
        *ptr = *( ptr - 1 );
        --ptr;
      }

      *str = swap;

    }
    ++str;
    on_consonant = !on_consonant;
  }

}

int main( int argc, char *argv[] )
{
  if ( argc != 2 )
  {
    std::cout << "please enter a valid string as an argument\n";
    return 0;
  }

  std::cout << argv[1] << '\n';
  rearange( argv[1] );
  std::cout << argv[1] << '\n';

  return 0;
}

I realize that the \$O\$ notation of this isn't very good, we are going to be going back and forth across this string many times.  I really couldn't think of a better way to do it with the constraints that were given.  I was trying to do it in linear time, but the problem is that you never know how far forward the correct character will be and it is possible to overwrite data that hasn't even been looked at.

I offered another solution, which I do believe is linear \$( 2 * n )\$, using no constraints.

void rearange( std::string& str )
{
  std::vector< char > vowels( str.length() / 2 );
  std::vector< char > consonents( str.length() / 2 );

  size_t v_idx = 0;
  size_t c_idx = 0;

  for ( char ch : str )
    isVowel( ch ) ? vowels[ v_idx++ ] = ch : consonents[ c_idx++ ] = ch ;

  str.clear();
  for ( size_t i = 0; i < consonents.size(); ++i )
  {
    str += consonents[i];
    str += vowels[i];
  }
}

Am I correct that this is a linear operation?  Are there any other ideas that could speed this up?  ( Though, I'm not too worried about it, it currently takes twice as long to even make the random string ).

You have tagged this question with algorithm, and I like algorithm problems. In the spirit of the original question, the solution should not be using any additional space, which means your char vector suggestion at the end is not really relevant. I would agree with your analysis, that the problem is reduced to \$O(n)\$ by storing the vowels and consonants in different vectors, and then merging them again... but that relies on an \$O(n)\$ space complexity too.

I think the solution that the original problem (with no additional storage) is looking for, is a three-pointer option.... a 3-point turn, to make a bad pun.

Consider the following algorithm, which contains three pointers. Each pointer advances sequentially from the beginning to the end of the char array. There is a 'rotate' operation that makes a temp copy of the last char in an array slice, it then shifts all previous chars forward one, and then inserts what was the last char, at the front.

The three pointers consitute an \$O(n)\$ sequence through the data, and the rotate is another \$O(n)\$ operation, but worst-case is n/2, and the worst case will reduce significantly as the pointers advance, and the gap tightens up.... Technically, though, the time complexity combined worst case is \$O(n^2)\$ though.

So, in pseudocode:

set three pointers all to the first char

vowel pointer will, when set, point to the next available vowel - initialize to 0
consonant pointer will, when set, point to the next abailable consonant - initialize to 0
insert pointer - initialize to 0

loop while the insert pointer is valid

advance the vowel pointer to the next vowel (inclusive of the current char)
advance the consonant pointer to the next consonant (inclusive of the current char)
rotate the consonant to the insert pointer.
if the consonant was after the next vowel, indicate that the vowel has advanced 1 char
advance the insert pointer
rotate the vowel to the insert point.
if the vowel was after the consonant, indicate the consonant advanced 1 char
advance the insert pointer
advance the vowel pointer
advance the consonant pointer

So, working off this, and using beginner-level C++ (I am a Java person), I put together the following functions:

bool isVowel( const char ch )
{
  return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

void rotate(char *from, char *to)
{
    char c = *to;

    while (--to >= from)
    {
        *(to + 1) = *to;
    }
    *from = c;
}

void rearange( char *str )
{

  char *vowel, *consonant;
  vowel = str;
  consonant = str;

  while ( *str )
  {
    while (*consonant && isVowel(*consonant))
    {
        consonant++;
    }
    while (*vowel && !isVowel(*vowel))
    {
        vowel++;
    }

    rotate (str, consonant);
    if (consonant > vowel)
    {
        vowel++;
    }
    str++;

    rotate (str, vowel);
    if (vowel > consonant)
    {
        consonant++;
    }
    str++;

    consonant++;
    vowel++;
  }

}

This is in an Ideone here;

The advantages here are that the logic for the boolean on_consonant is removed. Additionally, the pointers only ever advance, and never have to be re-located (if you ignore the rotate...)


Auto-complete using Tries in Python with OOP I am working on a problem to develop auto-complete functionality to practice different applications of Tries. The auto-complete function will return all the possible words in the wordlist given a prefix. I came up with the following solution which returns the result as expected. I need some help to review my code, in order to enhance the OOP structure and improve the code quality over all.

Please let me know your thoughts, any feedback is welcome.

class Trie():
    def __init__(self):
        self.children = {}
        self.flag = False # Flag to represent that a word ends at this node

    def insert(self, word):
        for char in word:
            if char not in self.children:
               self.children[char]= Trie()

            self = self.children[char]
        self.flag = True

    def all_suffixes(self, prefix):
        results = set()

        if self.flag:
            results.add(prefix)

        if not self.children:
            return results

        return reduce(lambda a, b: a | b,  [node.all_suffixes(prefix + char) for (char, node) in self.children.items()])

    def autocomplete(self, prefix):
        node = self
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return list(node.all_suffixes(prefix))

if __name__=="__main__":
    word_list = ['aardvark','ark', 'altimeter','altitude', 'apotactic', 'bagonet', 'boatlip',
    'carburant', 'chyliferous', 'consonance', 'cyclospondylic',
    'dictyostele', 'echelon', 'estadal', 'flaunty', 'gesneriaceous',
    'hygienic', 'infracentral', 'jipijapa', 'lipoceratous', 'melanthaceae']

    c = Trie()

    for word in word_list:
        c.insert(word)
    print c.autocomplete('a')

Output - ['aardvark', 'ark', 'altimeter', 'altitude', 'apotactic']

I was thinking on the lines of having two classes one as Trie() and the other as Autocomplete(). The __init__(self,word_list) for Autocomplete()  can then have the for loop code snippet to create the Trie from the word list.

Bug
Put 'a' in word_list: it is not found by autocomplete('a'). This is because all_suffixes doesn't use the result variable when building the result in case the node has children.
Naming

The name self.flag tells nothing about the purpose of the variable. self.word_end would be better.
all_suffixes returns whole words, not suffixes. words_with_prefix would be a better name. Alternatively, the function could return suffixes only and adding the prefix would be the responsibility of autocomplete.

Other
Instead of using a set and reduce in all_suffixes, it would be simpler to use just a list and extend it in a loop. (There should be no duplicate words in the list anyway, because the trie does not store duplicates)
def words_with_prefix(self, prefix):
    results = []
    if self.word_end:
        results.append(prefix)
    for (char, node) in self.children.items():
        results.extend(node.all_suffixes(prefix + char))
    return results


Finding minimum steps required to traverse from source to terminal Hello everyone this is my first post here so please do critique my post if there's anything.
I have made a program intended to pass a programming challenge on open.kattis.com, here.
It should do as title says, but with the conditions that each traversal follows the rules of a "Knight" from chess, that being plus/minus two columns/rows and plus/minus one column/row.

_read method:
I attempted to solve this making a Node class and passing coordinate and char data into each instance of a Node object for each coordinate.

_adjacencify method:
Thereafter, I found adjacencies (neighbours) of all Node objects, with the aforementioned condition of a chess Knight.

_jump method:
Lastly, I used a BFS implementation in order to find the shortest path from the source (root) to the terminal (here represented as 'K').

find_path:
Wraps everything up.

Here's the code I ended up with:
class Nite
  #attr_accessor :char, :col, :row
  class Node
    attr_accessor :char, :col, :row, :disc, :parent
    attr_reader :adjies
    def initialize(char, col, row)
      @char = char
      @col = col
      @row = row
      @adjies = [] # adjacencies
      @disc = false
      @parent = nil
    end
    def add(value)
      @adjies << value
    end
  end

  def _read
    # assign each coord. to a Node-object
    n = gets.to_i
    nodes = Array.new
    n.times do |x|
      temp = gets.strip.to_s
      temp.size.times do |y|
        node = Node.new(temp[y], x, y)
        nodes << node
      end
    end

    nodes
  end

  def _adjacencify(nodes)

    nodes.each do |x|
      nodes.each do |y|
        if y.col == x.col && y.row == x.row || y.char == '#'
          next
        end

        # logic

        if x.row == (y.row - 1) # y.row + 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row+1)
          elsif x.col == (y.col + 2) # y.col - 2
            x.add(y) # (col-2, row+1)
          end

        elsif x.row == (y.row + 1) # y.row - 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row-1)
          elsif x.col == (y.col + 2) # y.col - 2)
            x.add(y) # (col-2, row-1)
          end

        end

        if x.row == (y.row - 2) # y.row + 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row+2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row+2)
          end

        elsif x.row == (y.row + 2) # y.row - 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row-2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row-2)
          end

        end

      end
    end

    nodes
  end

  def _jump(nodes)

    nodes = _adjacencify(nodes)

    q = Queue.new
    root = nodes[0]
    root.disc = true
    q << root

    while !q.empty? do
      v = q.pop
      if v.char == 'K'
        steps = 0
        until v.parent == nil do
          if !v.nil?
          end
          steps += 1
          v.parent = v.parent.parent
        end
        return steps
      end
      v.adjies.each do |w|
        if w.disc == false
          w.parent = v
          w.disc = true
          q << w
        end
      end
    end
    return -1

  end

  def find_path
    _jump(_read)
  end

end

nite = Nite.new
puts nite.find_path

I suspect of course that the _adjacencify method is super time consuming, and that some loops are way too time consuming.
I failed the <1.00s time requirement in order to pass the challenge.
I want all types of criticism on my code, and I want tips and also, if anyone wants, different implementations that perform better.
Especially Ruby convention is something I want critique on, considering I am coming from a Java and Python background and I'm fairly fresh in Ruby.
Please tell me if I should edit anything in this post to make anything clearer.

and welcome!
Things I really like

Using standard Ruby indention (2 spaces)
Using the attr_accessor and attr_reader helpers instead of hand-rolling these methods
Using n.times do to loop.
Using next at the top of a loop body instead of a nested if
Short, focused methods
Great use of functional decomposition (goes along with the focused methods)

There's a lot of nit-picky things to follow, so don't be discouraged.  Many of these things are minor, and I'm mostly pointing out Ruby idioms or practices you have no way to know yet.  Due to time constraints, I am not going to address the algorithm itself, nor look for any major improvements.  I will mostly point out the things that catch my eye as a Ruby programmer.
Naming things
  def _read
    # assign each coord. to a Node-object

Does the comment indicate that "read" could use a better name?
    nodes.each do |x|
      nodes.each do |y|

x and y are frequently used as coordinate names for a Cartesian grid, which a chessboard is.  Here, x and y are nodes, not coordinates.  Better names would be a and b, or perhaps origin and destination.
@adjies = [] # adjacencies

Probably just name the variable @adjacencies so you can lose the comment, and the code will be clearer throughout.  Someone reading the code who hasn't seen this comment yet will be confused.
Formatting
    end
    def add(value)
      @adjies << value
    end
  end

Standard Ruby formatting separates methods with a blank line.  I also prefer a blank line between a method and the end of the class:
    end

    def add(value)
      @adjies << value
    end

  end

but the more common practice is to have no blank line after the last method in a class:
    end

    def add(value)
      @adjies << value
    end
  end

Idiomatic private methods in Ruby
def _jump(nodes)

Standard Ruby does not use the underscore conversion for private methods.  Instead, private methods can follow the private keyword:

private

def jump(nodes)

Note that all methods that follow "private" will be private, so you don't have to use it before every private method.  Standard Ruby practice is to just give the "private" keyword once, and then follow that with all of the private methods.
Omit the "return" keyword in the last expression in a method.
   return -1

The result of a Ruby method is the value of the last expression in the method.  So unless returning early, we usually omit the "return" keyword when it's on the last line:
    -1

You omit the "return" keyword elsewhere, so I assume this is just an oversight.
Don't compare to true or false
if w.disc == false

In Ruby, true and false are a little different than in Java.  Ruby considers anything that is either nil or false to be "falsey", and everything else is "truthy".  Therefore, it is bad practice to compare a value with false, since this comparison will fail if the value is actually nil.
So instead of comparing with false, do this:
if !w.disc

But even better, Ruby has a negating form of "if" called "unless".  Idiomatic Ruby would be:
unless w.disc

Getting the first element of an array or enumeration
root = nodes[0]

This is fine, but this also works:
root = nodes.first

Ruby likes you to have multiple ways to do a thing, a philosophical shift from Python.
Redundant #to_s
     temp = gets.strip.to_s

The result of String#strip is a String, so there's no need for .to_s here.
Use Array instead of Queue (for this application)
q = Queue.new

Queue is intended for multi-threaded applications; it includes locking to prevent race conditions.  For a single-threaded application, you can and should just use Array.  The minor reason is performance (avoid the locking).  The major reason is communication: A Ruby programmer seeing Queue is going to start looking for the threading in your program.
Since the methods you are calling on q (<< and pop) are also implement on Array and have the same meaning, you can do this instead:
q = []

Create empty arrays with []
nodes = Array.new

There's nothing wrong with this, but you will more often see a new, empty array created using the array literal syntax:
nodes = []


Follow-up: How can we optimizing Java BigInteger operations? This is the follow up question of How can we optimizing Java BigInteger operations?
Problem
Reduce the number to 1 in a minimal number of steps, following the rules:
If the number is even, divide it by 2.
Otherwise, increment or decrement it by 1.

Limit: s can be up to 309 digits long.
Solution
The solution I have come up with is below:
import java.math.BigInteger;

public class Solution {

    public static int solution(String s) {
        BigInteger n = new BigInteger(s);

        if ( isPrimitive(n) ) {
            return longOps(0, n.longValue());
        }

        return bigIntOps(n);
    }

    public static int bigIntOps(BigInteger n) {
        BigInteger one = BigInteger.ONE;
        BigInteger two = BigInteger.TWO;
        BigInteger four = new BigInteger("4");
        int count = 0;

        while (n.compareTo(one) == 1) {
            count++;

            if( n.and(one).byteValue() == 0 ){
                n = n.shiftRight(1);

                if ( isPrimitive(n) )
                    return longOps(count, n.longValue());

            } else if ( n.byteValue() == 3 || n.mod(four).byteValue() == 1)
                n = n.subtract(one);
            else
                n = n.add(one);
        }

        return count;
    }

    public static int longOps(int count, long n) {

        while (n > 1) {
            count++;

            // If number is divisible by 2
            if ( (n & 1) == 0 ) {

                // Check if the number is power of two
                if ((n&(n-1)) == 0)
                    return (int)Math.ceil(Math.log(n)/Math.log(2)) + count - 1;
                else
                    n = n >> 1;// Binary Division

            } else if ( n == 3 || n%4 == 1 )
                n--;
            else
                n++;
        }

        return count;
    }

    public static boolean isPrimitive(BigInteger n) {
        return n.compareTo(new BigInteger(String.valueOf(Long.MAX_VALUE))) < 0;
    }

}

Just some note from the source I collect:
"From the research, BigInteger operations are memory intensive and hence slow. Hence, the processing was divided into BigInteger processing and long processing.
A check was made at first to see if the number is long, and the processing was divided based on the number.
Check was also made in the BigInteger processing to check if the remainder was a long, and if true, further processing was done for long processing.
I found a sweet math solution to find the 2 power of number:
Math.ceil(Math.log(x)/Math.log(2))
This solution provided a single statement to find the number of steps.
Unfortunately BigInteger does not provide Math.log() functionality so this could not be implemented which could have been a great solution."

https://github.com/JavaCheatsheet/codechallenge/blob/master/src/google/Level3/Part3/README.md

Log2(n)
Math.ceil(Math.log(x)/Math.log(2)) is not the fastest way of determining \$\lceil\log_2{n}\rceil\$, of an integer n.  That requires converting the integer to a double, calculating the transcendental function, dividing by a constant, and then converting back to an integer, while rounding up.
Much faster is to count the number of bits in the value. \$\lceil\log_2{255}\rceil\$ is 8, and \$255 = 11111111_2\$ which has 8 bits.  Exact powers of two are represented by a 1 followed by \$\log_2\$ zeros; we can fix this with a tiny amount of preprocessing: subtracting 1.
Java doesn't directly provide the number of bits in an int, but it does give us Integer.numberOfLeadingZeros(), which will we can use to get the answer:
int ceil_log_2(int n) {
    if (n < 1)
        return Integer.MIN_VALUE;
    return 32 - Integer.numberOfLeadingZeros(n - 1);
}

Java's BigInteger does give us the BigInteger.bitLength() which does directly give the number of bits required to represent the number, so will give us the answer more directly:
int ceil_log_2(BigInteger n) {
    if (n.compareTo(BigInteger.ONE) < 0)
        return Integer.MIN_VALUE;
    return n.subtract(BigInteger.ONE).bitLength();
}

bigIntOps
Even/Odd
In bigIntOps(), you are now dividing by 2 using a shiftRight(1) operation.  Good; that faster than actual division.
But you are testing if the value is even by and'ing the BigInteger value with BigInteger.ONE, which likely allocates a new BigInteger value, which after being used must be garbage collected.  Then, you discard all of the upper bits of the value keeping only the lower 8 with .byteValue(), and finally test if that is zero.
You could simply discard the upper bits, then and with 1, and test:
if (n.byteValue() & 1 == 0)

Now no additional BigInteger temporary object is being created, which is a win.  But that is still doing unnecessary work.  Java directly provides a way of testing individual bits of a BigInteger, with .testBit():
if (n.testBit(0) == false)

Looping
While the result is even, you are dividing by 2.  You are doing this by shifting by 1 bit, which is faster than division, but still creates a new BigInteger object each step.
You notice this with your power-of-two test in longOps, and handle a power-of-two final value in one operation, instead of doing it in multiple steps.
Why not do that in bigIntOps as well?
BigInteger.getLowestSetBit() will tell you the number of trailing zero bits in the number, which is the number of times it can be divided evenly by 2.  And this works not only for exact power-of-twos
int zeros = n.getLowestSetBit();
n = n.shiftRight(zeros)
count += zeros;

Note that this works for integers as well:
int zeros = Integer.numberOfTrailingZeros(n);
n >>= zeros;
count += zeros;

So instead of doing a bunch of divisions one at a time, you can do them in bulk.  And not just for power of twos.
With the value \$3*2^{1024}\$, you'd do 1024 divisions by 2 in one step, leaving 3, which you'd then subtract 1, and then divide by 2, for 1026 steps, done in 3 calculations.
mod-4
Like the n.and(one) early, n.mod(four).byteValue() == 1 takes a possibly 1000-bit number, and does expensive modulo-4 division, and creates a new BigInteger value to store the result in, which must be allocated, and then garbage collected later.  You then discard all of the upper bits, and compare the result with 1.
Again, since your doing modulo-4 math, you can do modulo-256 math first, without changing the result.  n.byteValue() % 4 == 1.  This means no temporary BigInteger object needs to be created.
But because you know that n is odd (or you would be doing division-by-2), the results must be 1 or 3.  This means you are effectively just testing whether or not bit 1 is set.  n.testBit(1) == false.  Which is a lot clearer and more direct:
isPrimitive
Every time, isPrimitive is called, this statement is executed:
    return n.compareTo(new BigInteger(String.valueOf(Long.MAX_VALUE))) < 0;

You are converting Long.MAX_VALUE to a string, and then converting that back to binary form in BigInteger.
EVERY TIME!
If ever there was time to declare a constant, that was it, so it was done once, and not every call.
It could also be made more efficient by getting rid of the string intermediate step, and simple use BigInteger.valueOf(Long.MAX_VALUE).

Improved Code
import java.math.BigInteger;

public class Solution {

    private final static BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);

    public static int solution(String s) {
        BigInteger n = new BigInteger(s);
        int count = 0;

        while (n.compareTo(MAX_LONG) > 0) {
            int zeros = n.getLowestSetBit();

            if (zeros > 0) {          // Even!
                n = n.shiftRight(zeros);
                count += zeros;
            } else {                  // Odd
                if (n.testBit(1))        // At least 2 least significant one bits
                    n = n.add(BigInteger.ONE);
                else                     // Only 1 least significant one bit
                    n = n.subtract(BigInteger.ONE);
                count++;
            }
        }

        // Value now fits with a primitive long
        long lv = n.longValue();

        while (lv > 3) {
            int zeros = Long.numberOfTrailingZeros(lv);
            if (zeros > 0) {          // Even!
                lv >>= zeros;
                count += zeros;
            } else {                  // Odd
                if (lv % 4 == 1)        // Only 1 least significant one bit
                    lv--;
                else
                    lv++;               // At least 2 least significant one bits
                count++;
            }
        }

        if (lv == 3)
            count += 2;
        if (lv == 2)
            count += 1;

        return count;
    }
}

Notice:

The BigInteger loop condition loops while the value is greater than Long.MAX_VALUE, instead of while greater than 1.  This naturally breaks out of the loop when the value is small enough.  No need for a separate test.
The n.byteValue() == 3 special case is not even present in BigInteger case, since it does not change the number of steps, and adding the test will slow execution down.
The lv == 3 special case can been removed from the primitive loop as well, by only looping while lv > 3!

Improved Algorithm
Consider:
11111000000111111100000000111111100000000111011100000111100000111     +1
11111000000111111100000000111111100000000111011100000111100001000     / 2^3
11111000000111111100000000111111100000000111011100000111100001        -1
11111000000111111100000000111111100000000111011100000111100000        / 2^5
111110000001111111000000001111111000000001110111000001111             +1
111110000001111111000000001111111000000001110111000010000             / 2^4
11111000000111111100000000111111100000000111011100001                 -1
11111000000111111100000000111111100000000111011100000                 / 2^5
111110000001111111000000001111111000000001110111                      +1
111110000001111111000000001111111000000001111000                      / 2^3
111110000001111111000000001111111000000001111                         +1
111110000001111111000000001111111000000010000                         / 2^4
11111000000111111100000000111111100000001                             -1
11111000000111111100000000111111100000000                             / 2^8
111110000001111111000000001111111                                     +1
111110000001111111000000010000000                                     / 2^7
11111000000111111100000001                                            -1
11111000000111111100000000                                            / 2^8
111110000001111111                                                    +1
111110000010000000                                                    / 2^7
11111000001                                                           -1
11111000000                                                           / 2^6
11111                                                                 +1
100000                                                                / 2^5

How many bits were there originally?  How many divide by 2's?
How many groups of 1 bits were there?  How many extra operations did a single 1 bit require?  How many operations did a group of more than a single 1 bit require?
Can you just count groups of 1's, single 1's, and total number of bits?  Are there any special cases you need to consider, like ending with 3, or a single 0 bit?


splitWith function for splitting a list doesn't seem optimal As an exercise from RWH, I needed to write a function that splits a list every time the predicate is false (words == splitWith (== ' ') for strings):

splitWith :: (a -> Bool) -> [a] -> [[a]]
splitWith _ [] = []
splitWith p xs
    | null pre = splitWith p post'
    | otherwise = pre : splitWith p post'
    where
        (pre, post) = break p xs
        post' = if null post then [] else tail post

My concern is the if..then..else chain; it seems "forced". I have to make sure that post isn't null, or it will crash on the call to tail.

Is there a better way to write this?

You can gin up a safe version of tail lickety-split by using drop 1.


Creating procfs entry on linux in Kernel Module My Linux kernel version is

Linux version 5.0.0-29-generic

I'm currently learning how to write kernel modules for Linux and implemented this simple module which creates a new procfs entry and allows some data to be read from it.

The module consists of the following files:

init.c:

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include "pfs_regfile.h"

MODULE_LICENSE("GPL");

static struct proc_dir_entry *pde_regfile;

static struct file_operations fops_regfile = {
    .owner = THIS_MODULE,
    .open = pfs_open,
    .read = pfs_device_read,
    .release = pfs_release
};

static int __init init_md(void){
    pde_regfile = proc_create(PROC_REGFILE_NAME, 0, NULL, &fops_regfile);
    if(!pde_regfile){
        remove_proc_entry(PROC_REGFILE_NAME, NULL);
        printk(KERN_ALERT "Error: could not initialize procfs entry /proc/%s", PROC_REGFILE_NAME);
        return -ENOMEM;
    }
    return 0;
}

static void __exit exit_md(void){
    remove_proc_entry(PROC_REGFILE_NAME, NULL);
}

module_init(init_md);
module_exit(exit_md);

pfs_regfile.h:

#ifndef PFS_REGFILE_H
#define PFS_REGFILE_H

#include <linux/fs.h>

#define PROC_REGFILE_NAME "pfs_regfile"

int pfs_open(struct inode*, struct file *);

int pfs_release(struct inode *, struct file *);

ssize_t pfs_device_read(struct file *, char __user * buffer, size_t, loff_t *);

#endif //PFS_REGFILE_H

pfs_regfile.c:

#include <linux/module.h>
#include <linux/uaccess.h>
#include "pfs_regfile.h"

static char data[5000];
static char *current_ptr;
int pfs_open(struct inode* in, struct file *filp){
    for (int i = 0; i < sizeof(data) - 1; i++){
        data[i] = 'a';
    }
    current_ptr = data;
    try_module_get(THIS_MODULE);
    return 0;
}

int pfs_release(struct inode *in, struct file *filp){
    module_put(THIS_MODULE);
    return 0;
}

ssize_t pfs_device_read(struct file *file, char __user * buffer, size_t len, loff_t *off){
    size_t pos = (size_t)(current_ptr - data);
    size_t to_copy = pos + len < sizeof data ? len : sizeof data - pos;
    unsigned long not_copied = copy_to_user(buffer, current_ptr, to_copy);
    if(not_copied){
        printk(KERN_ALERT "Unknown error occurred when copying data into userspace\n");
    }
    size_t copied = to_copy - (size_t) not_copied;
    current_ptr += copied;
    return (ssize_t) copied;
}

I'm not sure if this module should work in all cases and its implementation is sort of "idiomatic". I'm especially concerned about concurrency. I tried to access it concurrently from different processes (cat /proc/pfs_regfile), and it worked fine.

memset

for (int i = 0; i < sizeof(data) - 1; i++){
    data[i] = 'a';
}

shouldn't be needed. Just use memset from string.h, which is indeed available in the kernel.

sizeof

You have this:

int i = 0; i < sizeof(data) - 1; i++

but also this:

pos + len < sizeof data ? len : sizeof data - pos

Today I learned that the parens are needed on types and optional on expressions:

  The operator has a single operand, which is either an expression or a data type cast. A cast is a data type enclosed in parenthesis.

The only syntax I've ever seen is with parens. You should at least stay internally consistent.

Buffer sizes

5000 is a little unusual, especially inside the kernel. Unless there are hidden motivations, consider just making it 1024*4 == 4096.


Small particle engine I wrote a small particle engine in Java for my Pong clone.

I read that changing a texture is very expensive in OpenGL, so I tried to change the texture as few times as possible.  Therefore I change the texture in the render method of the emitter and not in the render method of every particle.  Although my framerate drops from about 8000 FPS to 4000 FPS while there are about 60 particles on the screen.

So, is it possible to improve my particle engine when it comes to rendering? I am only asking for the rendering, because when I use the engine, but disable its rendering, nothing changes in the FPS.

This is the render Method of the particle emitter:

public void render() {
    //Initialize....
    GL11.glMatrixMode(GL11.GL_MODELVIEW);
    BloodParticle.PARTICLE_TEXTURE.bind();

    for(Integer index : this.getBlockedParticles()){
        this.getParticles()[index].render();
    }

    GL11.glDisable(GL11.GL_TEXTURE_2D);
}

And this is the code for the particle self:

public void render() {
    if(!this.isAlive()){
        return;
    }

    // Store matrix
    GL11.glPushMatrix();

    // Set to particle's position and scale
    GL11.glTranslatef(this.getPosition().getX(), this.getPosition().getY(), 0);
    GL11.glScalef(3.5f, 3.5f, 1.0f);

    // Set the current alpha.
    GL11.glColor4f(1.0f, 1.0f, 1.0f, this.getAlphaFade());

    //Draw the texture on a quad.
    GL11.glBegin(GL11.GL_QUADS);
    {
        GL11.glTexCoord2f(0, 0);
        GL11.glVertex2f(-PARTICLE_TEXTURE.getImageWidth()/2.0f,
                -PARTICLE_TEXTURE.getImageHeight()/2.0f);

        GL11.glTexCoord2f(0, 1);
        GL11.glVertex2f(-PARTICLE_TEXTURE.getImageWidth()/2.0f,
                PARTICLE_TEXTURE.getImageHeight()/2.0f);

        GL11.glTexCoord2f(1, 1);
        GL11.glVertex2f(PARTICLE_TEXTURE.getImageWidth()/2.0f,
                PARTICLE_TEXTURE.getImageHeight()/2.0f);

        GL11.glTexCoord2f(1, 0);
        GL11.glVertex2f(PARTICLE_TEXTURE.getImageWidth()/2.0f,
                -PARTICLE_TEXTURE.getImageHeight()/2.0f);

    }
    GL11.glEnd();

    //Get the matrix again.
    GL11.glPopMatrix();
}

A few notes:

for(Integer index : this.getBlockedParticles()){
    this.getParticles()[index].render();
}

This should be:

for( Particle particle : getBlockedLivingParticles() ) {
  particle.render();
}

By maintaining a list of living particles, you can eliminate a number unwarranted calls to render and eliminate the following check:

if(!this.isAlive()){
    return;
}

Assuming the width and height cannot change while rendering:

    GL11.glTexCoord2f(0, 0);
    GL11.glVertex2f(-PARTICLE_TEXTURE.getImageWidth()/2.0f,
            -PARTICLE_TEXTURE.getImageHeight()/2.0f);

As Marco commented, that duplicate code can be refactored:

    float width = PARTICLE_TEXTURE.getImageWidth() / 2.0f;
    float height = PARTICLE_TEXTURE.getImageHeight() / 2.0f;

    GL11.glTexCoord2f(0, 0);
    GL11.glVertex2f(-width, -height);

This will reduce the number of divisions (an expensive operation) from 8 to 2. You'll also note that there's a relationship between glTexCoord2f and the sign of the width/height passed to glVertex2f, which can be abstracted.

Architecturally, I'd be concerned that the Particle can only be rendered using the GL11 API. Use an Abstract Factory to decouple the rendering device from the application logic. This will also help determine the slower parts of the code (i.e., you could employ a dummy particle that has no rendering device to quickly and easily tune the other parts of the application).

One other trick to speed things up: if all calculations can be made with integer math, then instead of diving by 2, bit-shift by 1.


Memoization with factorial in Python I wrote a Python module to learn about memoization, and I have some questions on what I did.

How pythonic is this?
Does it make a difference if I used a class attribute instead of a function attribute for my lookup_table?
How can I modify multi_run_chrono to use it like Python's decorators (with @)?
Should I keep the try... except KeyError or rather do if key in dictionary...?
Are there some nice tricks I could do to improve this code's elegance and/or performance?

Here is the code:

from __future__ import print_function
from random import randint
from time import clock

def naive_factorial(n):
    """calculates n! with a simple recursive algorithm"""
    if n == 0:
        return 1
    else:
        return n * naive_factorial(n-1)

def memo_factorial(n):
    """calculates n! using memoization in a recursive algorithm"""
    if not hasattr(memo_factorial, 'lookup_table'):
        memo_factorial.lookup_table = {0: 1}
    try:
        return memo_factorial.lookup_table[n]
    except KeyError:
        val = n * memo_factorial(n - 1)
        memo_factorial.lookup_table[n] = val
        return val

def check_correctness():
    print('Checking both functions do the same things')

    for i in [0, 1, 4, 10, 22, 63]:
        n = naive_factorial(i)
        m = memo_factorial(i)
        print('n = %d -- Naive : %d, Memo : %d' % (i, n, m))
        if n != m:
            print('Error in functions implementation')
            exit()

def multi_run_chrono(func, nb_runs, min_val, max_val):
    print('Running %s %d times, with n from %d to %d'
          % (func.__name__, nb_runs, min_val, max_val))
    tests = [randint(min_val, max_val) for _ in xrange(nb_runs)]
    starting_time = clock()
    for n in tests:
        func(n)
    ending_time = clock()
    print('Duration : %fs' % (ending_time - starting_time))

def main():
    # check_correctness()  # comment/uncomment to check or not
    for func in [naive_factorial, memo_factorial]:
        multi_run_chrono(func, 20000, 10, 200)

if __name__ == '__main__':
    main()

Benchmarking on my computer :

Running naive_factorial 20000 times, with n from 10 to 200
Duration : 0.596933s
Running memo_factorial 20000 times, with n from 10 to 200
Duration : 0.006060s

All remarks are welcome, thank you very much!

Regarding the memoization, here are two different ways to do this (for single-valued functions):

import functools

def memoize(func):
    cache = func.cache = {}

    @functools.wraps(func)
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper

def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__

@memodict
# @memoize
def factorial(n):
    """calculates n! with a simple recursive algorithm"""
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

The latter is faster because it saves one additional lookup, but only works for single-valued functions, whereas the first can be extended to also pass along multiple arguments.

The memoize is also nice, because it keeps the documentation of the function because of functools.wraps (try help(factorial) in both cases to see the difference).

Which implementation is faster depends on how often your try block misses and succeeds.

As for timings:
Using @memoize to calculate all factorials from 1 to 100000000 takes 2.66s on my machine, while doing the same with @memodict takes 2.51s, so not a big difference.

If you want to use a decorator to time the execution time of a function, this will not work very nicely here, since if you decorate factorial, every execution of the function will be timed (because of recursion this will be very often).

You can however use something like this:

def timeit(func, *args, **kwargs):
    starting_time = clock()
    result = func(*args, **kwargs)
    ending_time = clock()
    print 'Duration: {}'.format(ending_time - starting_time)
    return result

timeit(factorial, 100)

If you do want to use this as decorator, just insert a wrapper:

def timeit(func):
    def wrapper(*args, **kwargs):
        starting_time = clock()
        result = func(*args, **kwargs)
        ending_time = clock()
        print 'Duration: {}'.format(ending_time - starting_time)
        return result
    return wrapper

@timeit
def f():
    pass


Thread sync using conditional variables Can you review the code?

#include <stdio.h>
#include <pthread.h>
#include <windows.h>

#include "bin/include/pthread.h"
#include "bin/include/sched.h"
#include "bin/include/semaphore.h"

#define TCOUNT 10
#define WATCH_COUNT 12

int count = 0;
pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t count_threshold_cv = PTHREAD_COND_INITIALIZER;
int  thread_ids[2] = {1,2};

/* Function prototypes */
void watch_count(int *idp);
void inc_count(int *idp);
int getDirFileCount(void);
/* End of fuction prototypes */

int main(void)
{
    pthread_t threads[2];
    int retCode = 0;
    int initialFileCount = getDirFileCount();
    count = initialFileCount;
    printf("No of Files initially : %d \n",initialFileCount);
    if ((retCode = pthread_create(&threads[0],NULL,(void *)&inc_count, &thread_ids[0]))) {
        perror("Thread creation error : can't able to create thread");
    }
    if ((retCode = pthread_create(&threads[1],NULL,(void *)&watch_count, &thread_ids[1]))) {
        perror("Thread creation error : can't able to create thread");
    }

    pthread_exit(NULL);
    return 0;
}

void watch_count(int *idp)
{
    pthread_mutex_lock(&count_mutex);
    //int watchCount = getDirFileCount();
    while (1) {
        printf("waiting for changes made to the directory \n");
        pthread_cond_wait(&count_threshold_cv,
                          &count_mutex);
        printf("OK , now someone made chaneges to the directory\n");
    }
    pthread_mutex_unlock(&count_mutex);
}
void inc_count(int *idp)
{
    for (;;) {
        pthread_mutex_lock(&count_mutex);
        int countnow = getDirFileCount();
        printf("Number of files now: %d \n",countnow );
        if (count < countnow) {
            pthread_cond_signal(&count_threshold_cv);
            pthread_mutex_unlock(&count_mutex);
            return;
        }
        //pthread_cond_signal(&count_threshold_cv);
        pthread_mutex_unlock(&count_mutex);
        //pthread_exit(NULL)

    }
}

int getDirFileCount(void)
{
    int count = 0;
    WIN32_FIND_DATA fd;
    char *dirFilePath = "D:\\Test\\*";
    HANDLE h = FindFirstFile(dirFilePath, &fd);
    if (h != INVALID_HANDLE_VALUE) {
        do {
            count++;
        } while (FindNextFile(h, &fd));
        FindClose(h);
    }
    return count;
}

Could be simplified

For what you are doing, using a mutex and a condition variable is more complex than necessary.  You could just use a semaphore or signal instead.  A mutex should guard some shared variable or state, but your code doesn't have any.  Instead, you are using the mutex + condition variable simply to wake up another thread.

As far as your implementation goes, I have the following comments:

A loop containing pthread_cond_wait() should always check a predicate variable to guard against spurious wakeups.  This is in the documentation for pthread_cond_wait().  So for example:

pthread_mutex_lock(&count_mutex);
while (count == initialCount) {
    pthread_cond_wait(&count_threshold_cv, &count_mutex);
}
// Do something here...
pthread_mutex_unlock(&count_mutex);

The loop doing the work should lock the mutex for as short a time as possible.  You only need to hold the mutex when you want to access shared variables.  So for example:

for (;;) {
    // Do this long work outside of the mutex
    int countnow = getDirFileCount();

    if (countnow > initialCount) {
        // Only lock the mutex when you need to actually need to access
        // shared state (in this case the variable "count").
        pthread_mutex_lock(&count_mutex);
        count = countnow;
        pthread_cond_signal(&count_threshold_cv);
        pthread_mutex_unlock(&count_mutex);
        return;
    }
}


Formatting milliseconds as days, hours, minutes, and seconds This is a function which aims to convert an amount of milliseconds to a more human-interpretable Day(s) Hour(s) Minute(s) Second(s) format:

function dhms(t) {
    d = Math.floor(t / (1000 * 60 * 60 * 24)),
    h = Math.floor((t % (1000 * 60 * 60 * 24)) / (1000 * 60 * 60)),
    m = Math.floor((t % (1000 * 60 * 60)) / (1000 * 60)),
    s = Math.floor((t % (1000 * 60)) / 1000);
    return d + 'Day(s) ' + h + 'Hour(s) ' + m + 'Minute(s) ' + s + 'Second(s)'
}

So for getting the variables values I have for now something quite verbose:

d = Math.floor(t / (1000 * 60 * 60 * 24)),
h = Math.floor((t % (1000 * 60 * 60 * 24)) / (1000 * 60 * 60)),
m = Math.floor((t % (1000 * 60 * 60)) / (1000 * 60)),
s = Math.floor((t % (1000 * 60)) / 1000);

Is it the way to go? Or should I go with:

d = Math.floor(t / 86400000),
h = Math.floor(t % 86400000 / 3600000),
m = Math.floor(t % 3600000 / 60000),
s = Math.floor(t % 60000 / 1000);

Or even with:

d = Math.floor(t / 864e5),
h = Math.floor(t % 864e5 / 36e5),
m = Math.floor(t % 36e5 / 6e4),
s = Math.floor(t % 6e4 / 1e3);

Or another way? How is it recommended to assign time values?

The Decimal Point

Exponential notation is by far the better for large numbers.

However when writing numbers in this format the convention is to have the decimal point after the first digit, as the exponent represents the magnitude of the value which is obscured if you have to locate the decimal point.

d = Math.floor(t / 8.64e7),
h = Math.floor(t % 8.64e7 / 3.6e6),
m = Math.floor(t % 3.6e6 / 6e4),
s = Math.floor(t % 6e4 / 1e3);

As constants

But.. These are magic numbers, and you repeat some of them several times, which is prone to error. Also assuming that this function would be part of a set of such functions declaring these constants as named variables would be much better.

DAY_MS = 8.64e7;
HOUR_MS = 3.6e6;
MIN_MS = 6e4;
SEC_MS = 1e3;

Derived values

As they are derived from each other you can then write it as

SEC_MS = 1e3;
MIN_MS = SEC_MS * 60;
HOUR_MS = MIN_MS * 60;
DAY_MS = HOUR_MS * 24;

Encapsulate

If you then encapsulate them you can drop the _MS and your function would look like.

"use strict";
const dhms = (()=>{
    const SEC = 1e3;
    const MIN = SEC * 60;
    const HOUR = MIN * 60;
    const DAY = HOUR * 24;
    return time => {
        const ms = Math.abs(time);
        const d = ms / DAY | 0;
        const h = ms % DAY / HOUR | 0;
        const m = ms % HOUR / MIN | 0;
        const s = ms % MIN / SEC | 0;
        return `${time < 0 ? "-" : ""}${d}Day(s) ${h}Hour(s) ${m}Minute(s) ${s}Second(s)`;
    };
})();

Notes

That t is made positive ms to avoid a negative sign on each number. This also lets you use the shorter and quicker | 0 (bit-wise OR 0) to floor the values, which you should only use for positive integers.
The use of a template string to format the output.
You could also define it as a module and thus avoid the need to encapsulate the constants as a module has its own local scope.


Heapsort implementation in C++14 Please review the following implementation of heapsort and pay attention to the following:

Have I correctly chosen the names InputIt and BidirIt for my iterators?
Is there a way to make the initialise iterator and then advance it pattern occupy one line instead of two?
Is the it != ix - 1 comparison of iterators ok?

Here is the code:

#include <iterator>
#include <functional>

template<
    class InputIt,
    class Key = std::less_equal<
        std::iterator_traits<InputIt>::value_type
    >
>
void plunge(
    const InputIt ix, // first element of heap
    const InputIt iy, // one-past last element of heap
    const InputIt iz, // element to be plunged
    Key key = Key()   // comparison key to use (up or down)
) {
    auto ii = iz;
    auto il = ix;
    std::advance(il, 2 * std::distance(ix, ii) + 1);

    while (il < iy) {
        auto ir = il + 1;

        auto it = ir < iy && key(*ir, *il) ? ir : il;

        if (key(*ii, *it)) {return;}

        std::iter_swap(ii, it);
        std::     swap(ii, it);

        il = ix;
        std::advance(il, 2 * std::distance(ix, ii) + 1);
    }
}

template<
    typename BidirIt,
    typename Key = std::greater_equal<
        std::iterator_traits<BidirIt>::value_type
    >
>
void heapsort(const BidirIt ix, const BidirIt iy, Key key = Key()) {
    auto it = ix;
    std::advance(it, std::distance(ix, iy) / 2);

    for (; it != ix - 1; --it) {
        plunge(ix, iy, it, key);
    }

    for (it = iy - 1; it != ix - 1; --it) {
        std::iter_swap(ix, it);
        plunge(ix, it, ix, key);
    }
}

Answers:

Input iterator is not suitable for your plunge function. The reason
is in std::advance(). It increments the iterators, which
invalidates all previous ones. Bidirectional iterators are ok.
Use std::next() as mentioned in the comment by
user2296177.
No. Only random access iterators are mandated to support the
operation.

Here is the piece of C++ 14 standard that proves answer #1.

Paragraph 24.2.3 of N4296 (Input Iterators). Note from table 107 - Input Iterator requirements (in addition to Iterator).

Expression:

++r;

  pre: r is dereferenceable.
  post: r is dereferenceable or
  r is past-the-end.
  post: any copies of the
  previous value of r are no
  longer required either to be
  dereferenceable or to be in
  the domain of ==.

where r is Input Iterator. Additionally, it is stated that post increment has the same effect. Either pre or post increment should be used to implement std::distance(), so it invalidates all copies of Input Iterators according to the standard.

Comments about the code

template<
    class InputIt,
    class Key = std::less_equal<
        std::iterator_traits<InputIt>::value_type
    >
>

Very arguable gain in readability.

Combo of first and last if preferred when referring to range. value is used to refer to some instance of T. ii and il make things even worse. Don't be lazy to type!

Bad idea to make iterators const. May be you wanted iterator pointing to const?

Nice usage of standard library (though you will need to be sure what it does, which you're trying to do).

The code is not working for input iterators, as mentioned in answers.

Nice one for the first try overall.


Making a staircase using HTML and CSS Here is my answer to the question, which I think is quite inefficient considering its length:

$('document').ready(function() {
 function makeEqual(blocks,dash) {
  var n =blocks;
  var widthSize = dash *10;
  var i=0;
  var equal = "";
  var contentName = "";
for(i=0;i<n;i++) {

  if(i==(n-1)) {
   contentName='contentL'+i;
  equal = "
"+produceDashStructure(dash*3)+"
";
  $("#main").append(equal);
  $("#"+contentName).css({marginLeft:i*widthSize , width:widthSize*3});
   for(j=i;j>0;j--) {
     contentName='contentR'+j;
      equal = "
"+produceDashStructure(dash)+"
";
      $("#main").append(equal);
      $("#"+contentName).css({marginLeft:((n-j)+i+2)*widthSize , width:widthSize , bottom: (((n-j)*2))*55 , position: "relative" });
    }
  }
   else {
    contentName='contentL'+i;
      equal = "
"+produceDashStructure(dash)+"
";
      $("#main").append(equal);
  $("#"+contentName).css({marginLeft:i*widthSize , width:widthSize});
    }
  }

  }
  function produceDashStructure(dash) {
      var dashedStructure = "";
    for(var i=0;i<dash;i++) {
         dashedStructure += "- ";
      }
       return dashedStructure+"

"+dashedStructure;
  }

  makeEqual(5,5);
})
#main {
  top: 10px;
  left: 10px;
  width: 30 px;
  position: relative;
}

I have written a lot of code for a small problem which I think is time-inefficient too, and I'm using the same methodology in my projects. Any improvement in this question will help me make all my projects more efficient.

It's hard to comment when the original question was very vague, the Original-OP (O-OP) failed to answer questions, different interpretations were made by the various respondants, and there's (currently) no accepted answer. Even worse, someone saw fit to remove the jQuery tag, implying that only a CSS solution would suffice - a view that did not come from the O-OP.

None of that was your fault.

The worst feature of this answer (and possibly others) is that the paradigm is reliant on a particular font size - change it and the step-formation falls apart.

You might consider something like the version below, which goes a long was to fixing that particular issue, and tidies up the code considerably :

$('document').ready(function() {
    function makeEqual($container, dashes, n) {
        var $step, scale = {}, i;

        // Create a single step and proactively measure its width and height in the target container.
        // IIFE allows working member `dashString` to be GC'd.
        (function(dashString) {
            $step = $("
").html(dashString + "

" + dashString).css({'position': 'absolute', 'width': 'auto', 'white-space': 'nowrap'}).appendTo($container);
            scale.w = $step.width();
            scale.h = $step.height();
            $step.remove();
        })(Array.apply(null, new Array(dashes)).map(function() {return '- '}).join('')); // pass in the required string of dashes and spaces

        // create staircases - descending and ascending in the same loop
        for(i=0; i<(n-1); i++) {
            $step.clone().css({ 'left': i * scale.w, 'top': i * scale.h }).appendTo($container); // descending steps
            $step.clone().css({ 'left': (2 * n - i) * scale.w, 'top': i * scale.h }).appendTo($container); // ascending steps
        }
        // create bridge-piece
        for(i=0; i<3; i++) {
            $step.clone().css({ 'left': (n - 1 + i) * scale.w, 'top': (n - 1) * scale.h }).appendTo($container); // bridge-piece
        }
    }
    makeEqual($("#main").empty(), 5, 3);
});

DEMO

Notes :

no ids and no rediscovery of freshly appended DOM elements.
no need for the dashStructure() function - instead, positioned clones of the prototype $step are appended.
all steps are absolutely positioned on the same bases using left and top; the vagaries of mixed natural flow and relative positioning are avoided.
the number of assignments is greatly reduced.
consistent indentation!!


Converting images to greyscale using JuicyPixel I would like to use Haskell to do some image processing so I have been writing small programs to test performance. I wrote a program to batch convert PNG images from color to greyscale. I compared the performance of the program below with a Python script using PIL. I found when compiled with -threaded -O2, the Haskell code takes four times longer than the python script (this comparison was done on a folder of 50 images).

Is there a way to speed this process up?

Haskell Code

import Codec.Picture
import System.Environment
import System.Directory
import System.FilePath
import Control.Monad

dynToImg :: DynamicImage -> Image PixelRGB8
dynToImg (ImageRGB8 img) = img

procAvg :: FilePath -> FilePath -> IO ()
procAvg inpath outpath = do
  Right inImage <- readPng inpath
  let image = avgImage . dynToImg $ inImage
  writePng outpath image

main :: IO ()
main = do
  args <- getArgs
  let [infolder,outfolder,tstr] = args
      t = read tstr :: Int
  files <- getDirectoryContents infolder
  let baseNames = filter ((==) ".png" . takeExtension) files
      infiles = map (infolder </>) baseNames
      outfiles  = map (outfolder </>) baseNames

  zipWithM_ procAvg infiles outfiles

avgImage :: Image PixelRGB8 -> Image Pixel8
avgImage = pixelMap pixelAvg

pixelAvg :: PixelRGB8 -> Pixel8
pixelAvg (PixelRGB8 r g b) =
  (r `div` 3 + g `div` 3 + b `div` 3 +
          (r `mod` 3 + g `mod` 3 + b `mod` 3) `div` 3)

Python Code

from PIL import Image
import sys
import os

if __name__ == "__main__":
    infolder = sys.argv[1]
    outfolder = sys.argv[2]

    fnames = os.listdir(infolder)

    for f in fnames:
        infile = os.path.join(infolder,f)
        outfile = os.path.join(outfolder,f)

        inimg = Image.open(infile)
        gray = inimg.convert('L')
        gray.save(outfile)
        inimg.close()

Python

What does your Python code look like? I'm sure that most of
the work is actually being done in C, not Python. JuicyPixels
allows you to write an arbitrary pixel mapping function in Haskell.
If the Python library called a user-supplied Python function to convert
every pixel I can assure you that it wouldn't be as fast as it is.

Other Libraries

That said, JuicyPixels may not be the fastest Haskell library to use.
For instance, Haskell can call routines in C libraries, and there are
Haskell bindings to the ImageMagick library via the imagemagick
package.

Another package you should have a look at is friday.
On assorted algorithms it compares favorable with ImageMagick,
It cannot produce SIMD instructions, so it's not as fast
as libraries such as OpenCV. On the other hand, it gives you the
tools to construct your own image transformations so it's a lot more
versitile than a library which gives you just a handful of canned
algorithms.

Improving pixelAvg

Obviously the function pixelAvg is the hot spot in the program, so
anything we can do to optimize it will have a significant impact on
the execution time. Here are some versions I tried:

pixelAvg (PixelRGB8 r g b) =

-- (1) original version:
   (r `div` 3 + g `div` 3 + b `div` 3) + (r `mod` 3 + g `mod` 3 + b `mod` 3) `div` 3

-- (2) use quot and rem:
   (quot r 3 + quot g 3 + quot b 3) + (quot (rem r 3 + rem g 3 + rem b 3) 3)

-- (3) use quotRem:
   let (rq,rr) = quotRem r 3
       (gq,gr) = quotRem g 3
       (bq,br) = quotRem b 3
   in (rq+gq+bq + (rr+gr+br) `quot` 3)

-- (4) simplify the expression
   (div r 3 + div g 3 + div b 3)

-- (5) just use one division
   fromIntegral $ ((fromIntegral r + fromIntegral g + fromIntegral g) :: Int) `quot` 3

-- (6) use a lookup table
   V.unsafeIndex avgVector (fromIntegral r + fromIntegral g + fromIntegral b)

Here are some timings I obtained on a 4246 x 2856 image:

(1) 0m2.796s
(2) 0m2.768s
(3) 0m2.440s
(4) 0m2.297s
(5) 0m2.198s
(6) 0m2.117s

quot/rem avoids a sign check and therefore should be marginally faster than div/mod
while giving the same answers for positive arguments. However an even bigger speed-up
can be obtained by computing both the quotient and remainder with one function call
(either quotRem or divMod) as demonstrated by (3).

Note that the formula used by (4) only differs from the original formula by at most 2
and has a lot fewer operations. Formula (5) reduces the number of divisions to
just one by converting all three pixel values to Ints, adding and then dividing the
total by 3.

As to be expected, the lookup table method is is the overall fastest. Here's the rest
of the code that initializes the table:

import qualified Data.Vector.Unboxed as V
...
avgVector :: V.Vector Pixel8
avgVector = V.generate (3*256) (\x -> fromIntegral $ div x 3)

So there are significant gains to be made by optimizing pixelAvg, but there are
also limitations to what you can achieve.  To get better results you'll likely
have to use a different library.


Pandas filter dataframe on multiple columns wrt corresponding column values from another dataframe I have a pandas dataframe, df1:
a b c d e f
1 1 1 x 1 5
1 1 1 x 1 6
1 1 1 y 1 5
1 1 1 y 1 7

and another dataframe, df2:
a b c d e f
1 1 1 x 1 5

Now I want to filter df1 on columns a, b, c, d if it is present in respective columns of df2. This is what I tried:
mask = df1['a'].isin(df2['a']) & df1['b'].isin(df2['b']) & df1['c'].isin(df2['c']) & df1['d'].isin(df2['d'])
df_new = df1[mask]

so df_new finally contains:
a b c d e f
1 1 1 x 1 5
1 1 1 x 1 6

I am looking for a better approach as there are a lot of columns to compare and a lot of rows, both in df1 and df2.

You need to merge dataframes like done here in Pandas Merge. You also need to read on dataframe joins which is a common topic in learning databases.Here I have not done any tweaking with indices i.e, whether to keep left ones or right ones but you can check the docs for better information on here Merge Docs Pydata
import pandas as pd

columns = "a b c d e f".split()
data = '''1 1 1 x 1 5
1 1 1 x 1 6
1 1 1 y 1 5
1 1 1 y 1 7'''.split("\n")

data = list(map(lambda x:x.split(), data ))

left = pd.DataFrame(columns = columns, data=data)

    a   b   c   d   e   f
0   1   1   1   x   1   5
1   1   1   1   x   1   6
2   1   1   1   y   1   5
3   1   1   1   y   1   7

right = pd.DataFrame(data = ["1 1 1 x 1 5".split()], columns=columns)

    a   b   c   d   e   f
0   1   1   1   x   1   5

pd.merge(left, right, how="right", on=["a", "b", "c", "d"])

    a   b   c   d   e_x f_x e_y f_y
0   1   1   1   x   1   5   1   5
1   1   1   1   x   1   6   1   5

pd.merge(left, right, how="right", on=["a", "b", "c", "d"], suffixes=["", "_"] ).drop(["e_", "f_"], axis=1)

    a   b   c   d   e   f
0   1   1   1   x   1   5
1   1   1   1   x   1   6


Checking errors from a series of function calls I have to work with C-style functions which return ERROR_SUCCESS when successful or an error code when not. I want my code to be nice and neat and easy to read but I am not sure I like what I have.

Option one:

int Foo()
{
    int result = Init();

    if (result == ERROR_SUCCESS)
    {
        result = SetTemperature( 30 );
    }
    else
    {
        return result;
    }

    if (result == ERROR_SUCCESS )
    {
        result = SetVoltage( 5 );
    }
    {
        return result;
    }

}

Option two:

int Foo()
{
    int result = Init();

    if (result != ERROR_SUCCESS)
        return result;

    result = SetTemperature( 30 );

    if (result != ERROR_SUCCESS)
        return result;

    result = SetVoltage( 5 );

    if (result != ERROR_SUCCESS)
        return result;

}

Please note that I can't use exceptions here. If there is an error then I simply need to return from the function with that error. Is there an even better way to organize this code?

Do your early returns properly, and there will be no more to tweak:

int Foo()
{
    int result;
    if((result = Init()))
        return result;
    if((result = SetTemperature( 30 )))
        return result;
    return SetVoltage( 5 );
}

Using the extra parentheses () around the assignment to suppress a compiler warning.

I don't check for expr != ERROR_SUCCESS because that's equivalent to expr in a boolean context.

If there are really a lot of those calls, consider investing in a preprocessor macro.
Don't forget to undefine it after use if the compilation unit is not at an end.
Also, many really don't like those.

#define OkOrReturn(a) do{int result = a; if(result) return result;}while(0)
#undef OkOrReturn


Retry mechanism for failed downloads I'm writing a mechanism to retry any failed downloads that respond with certain http error codes, I've noticed the server I'm downloading from will unexpectedly throw these codes to me and when I manually visit the URL it appears to be fine.

It also seems that its fine when trying to download for a second or (rarely) third time. The KeyValuePair represents the key as being the download link, and the value being the location where the file is set to be saved on the device.

I simply check if the file exists in the save location to determine if it actually downloaded.

public static class DownloadUtilities
{
    public static void DownloadLinks(Dictionary<string, string> files)
    {
        Parallel.ForEach(
            files,
            new ParallelOptions { MaxDegreeOfParallelism = 20 },
            DownloadLink);
    }

    private static void DownloadLink(KeyValuePair<string, string> link, bool retrying = false)
    {
        try
        {
            using (var webClient = new WebClient())
            {
                webClient.Headers.Add("User-Agent", "Mozilla/4.0 (compatible; MSIE 8.0)");
                webClient.DownloadFile(new Uri(link.Key), link.Value);
            }
        }
        catch (WebException e)
        {
            if (retrying) { return; } // Silently exit, we're retrying.

            if (e.Status != WebExceptionStatus.ProtocolError)
            {
                throw;
            }

            if (e.Message.Contains("(504) Gateway Timeout") || e.Message.Contains("(403) Forbidden"))
            {
                if (!RetryFailedDownload(link))
                {
                    Program.FailedDownloads.Add(link.Key); // Lets settle for the fact it can't download, and add it to the failed list.
                }
            }
            else
            {
                Logger.Error("Failed to download: " + link.Key);
                Logger.Error(e.Message);
            }
        }
    }

    private static bool RetryFailedDownload(KeyValuePair<string, string> link)
    {
        for (var i = 0; i < 4; i++) // Retry mechanism for 4 trys?
        {
            DownloadLink(link, true);

            if (File.Exists(link.Value)) // It finally managed to download?
            {
                return true;
            }
        }

        return false;
    }
}

Provided I understand the intent of this code, I think the following may be cleaner:

public static class DownloadUtilities
{
    private const int RETRY_COUNT = 4;

    public static void DownloadLinks(Dictionary<string, string> files)
    {
        Parallel.ForEach(
            files,
            new ParallelOptions { MaxDegreeOfParallelism = 20 },
            DownloadLink);
    }

    private static void DownloadLink(KeyValuePair<string, string> link, bool retrying = false)
    {
        int retriesRemaining = retrying ? RETRY_COUNT : 1;

        while (retriesRemaining > 0 && !File.Exists(link.Value))
        {
            retriesRemaining -= 1;
            try
            {
                using (var webClient = new WebClient())
                {
                    webClient.Headers.Add("User-Agent", "Mozilla/4.0 (compatible; MSIE 8.0)");
                    webClient.DownloadFile(new Uri(link.Key), link.Value);
                }
            }
            catch (WebException e)
            {

                if (e.Status != WebExceptionStatus.ProtocolError)
                {
                    throw;
                }

                var response = ex.Response as HttpWebResponse;

                if (response.StatusCode != HttpStatusCode.GatewayTimeout ||
                    response.StatusCode != HttpStatusCode.Forbidden)
                {

                    Program.FailedDownloads.Add(link.Key);
                    Logger.Error($"Failed to download {link.Key}, unhandled response code.");
                    return;
                }

                Logger.Error($"Failed to download {link.Key}, {retriesRemaining} attempts remaining");
                Logger.Error(e.Message);
            }
        }

        if (!File.Exists(link.Value))
        {
            // Lets settle for the fact it can't download, and add it to the failed list.
            Program.FailedDownloads.Add(link.Key);
            Logger.Error($"Failed to download {link.Key}, retries expired.");
        }
    }
}

Here is a summary of the changes and their reasoning:

Replaced addition of string literals and variables with string interpolation, which is generally regarded as better practice.
Making use of the HttpStatusCode enum instead of matching on the response message. This shortens the code and does not require string matching.
Moving the retry logic into the DownloadLink method, rather than extracting into an auxiliary method, since this does not add to the code and complicates behaviour.


Transposing a square matrix (n x n) I wish to transpose a square matrix, permanently overwriting it.
This is not the same as creating a 2nd matrix with the transposed contents of the 1st matrix.

I call the procedure with 3 parameters: the address of the original matrix, its rank, and the address of a scratch buffer that is large enough.
First, all the elements are spread out over the scratch buffer. Later the scratch buffer is copied back to the original storage.

How can I optimize this code?

; TransposeSquareMatrix(Address, Rank, Scratch)
Q:  push    ebp
    mov     ebp, esp
    push    ecx edx esi edi
    mov     esi, [ebp+8]    ; Address
    mov     edx, [ebp+12]   ; Rank
    mov     edi, [ebp+16]   ; Scratch buffer
    lea     eax, [edx-1]    ; Additional address increment
.a: push    edi             ; (1)
    mov     ecx, [ebp+12]   ; Rank
.b: movsb                   ; Spreading out the elements of one row
    add     edi, eax
    dec     ecx
    jnz     .b
    pop     edi             ; (1)
    inc     edi
    dec     edx
    jnz     .a              ; Repeating it for every row
    mov     edi, [ebp+8]    ; Address
    mov     ecx, [ebp+12]   ; Rank
    imul    ecx, ecx
    mov     esi, [ebp+16]   ; Scratch buffer
    rep movsb               ; Overwriting the original matrix
    pop     edi esi edx ecx
    pop     ebp
    ret     12
; --------------------------

20+ percent faster using the stack for the extra buffer.

Matrix     Question     Answer(1)    Faster
-------------------------------------------
16 x 16    3.62 µsec    2.62 µsec    27.6 %
13 x 13    2.67 µsec    2.05 µsec    23.2 %
10 x 10    1.77 µsec    1.35 µsec    23.7 %
 7 x  7    1.02 µsec    0.77 µsec    24.5 %
 4 x  4    0.56 µsec    0.44 µsec    21.4 %

Setting up a temporary scratch buffer in the stack proved to be a winner. A decent speed increase, no need for the 3rd parameter, and with a single branch target, applying code alignment could be a bit easier.

This pushes the same 5 registers but delays assigning EBP so it can be used as an EndOfBuffer marker. A minor drawback is that the easy recognizable  EBP-offsets for the parameters (+8, +12, ...) are gone. Requires some more attention to detail like in the ESP-offsets of today.

Nothing is pushed on the stack below the local stack buffer and so keeping ESP dword-aligned is not needed.

This is cleaner code. I think addressing the parameters several times over, looked a bit untidy.

; TransposeSquareMatrix(Address, Rank)
A1: push    ecx edx esi edi ebp
    mov     ebp, esp
    mov     esi, [ebp+24]   ; Address
    mov     edx, [ebp+28]   ; Rank
    mov     ecx, edx
    imul    ecx, ecx        ; -> Size of matrix
    sub     esp, ecx        ; Local buffer
    mov     edi, esp
    lea     eax, [edx-1]    ; (Rank - 1)
.a: movsb                   ; -> EDI += 1
    add     edi, eax        ; -> EDI += (Rank - 1)
    cmp     edi, ebp        ; Until end of local buffer
    jb      .a
    sub     edi, ecx        ; Back to start of current column
    inc     edi             ; Go to start next column
    dec     edx
    jnz     .a              ; Repeat rank times
    sub     esi, ecx        ; Copy to original storage
    mov     edi, esi        ; -> EDI is Address
    mov     esi, esp        ; -> ESI is local buffer
    rep movsb
    mov     esp, ebp
    pop     ebp edi esi edx ecx
    ret     8
; --------------------------

50+ percent faster without even using an extra buffer.

Matrix     Question     Answer(2)    Faster
-------------------------------------------
16 x 16    3.62 µsec    1.80 µsec    50.1 %
13 x 13    2.67 µsec    1.22 µsec    54.3 %
10 x 10    1.77 µsec    0.77 µsec    56.0 %
 7 x  7    1.02 µsec    0.44 µsec    56.9 %
 4 x  4    0.56 µsec    0.23 µsec    58.9 %

The elements on the main diagonal are never touched. All the other elements are flipped across the main diagonal.

; TransposeSquareMatrix(Address, Rank)
A2: push    ebx ecx edx esi edi ebp
    mov     ebx, [esp+28]   ; Address
    mov     ecx, [esp+32]   ; Rank
    mov     ebp, ecx
    dec     ecx
    jz      .c              ; It's a (1 x 1) matrix
.a: push    ecx             ; (1)
    mov     esi, ebx        ; Column address
    mov     edi, ebx        ; Row address
.b: inc     esi             ; To next element in this row
    add     edi, ebp        ; To next element in this column
    mov     al, [esi]       ; Swap 2 elements
    mov     dl, [edi]
    mov     [edi], al
    mov     [esi], dl
    dec     ecx
    jnz     .b
    add     ebx, ebp        ; To next element on main diagonal
    inc     ebx
    pop     ecx             ; (1)
    dec     ecx
    jnz     .a              ; Continu until (1 x 1) matrix
.c: pop     ebp edi esi edx ecx ebx
    ret     8
; --------------------------


Using I18n in capybara feature specs Here I am trying to avoid hardcoding in flash messages by using I18n. Also, I have tried to use a CSS selector for submitting the form to make the tests less brittle (I don't really care that much about what the text on the button is - more what happens when submitting).

Is this a good approach for making tests less brittle due to translation changes?

RSpec.feature "Classic Authentication" do

  let(:submit) {  find(:css, 'input[type="submit"]') }
  let(:user) { FactoryGirl.create(:user) }

  context 'Registation' do
    background do
      visit new_user_registration_path
      page.fill_in 'Email', with: 'test@example.com'
      page.fill_in 'Password', with: 'P4ssword'
      page.fill_in 'Password confirmation', with: 'P4ssword'
    end
    scenario "when I sign up with valid info" do
      submit.click
      expect(page).to have_content I18n.t('devise.registrations.signed_up')
      expect(page).to have_content I18n.t('user.sign_out')
    end
    scenario "when I sign up with invalid info" do
      page.fill_in 'Email', with: 'testasdas'
      submit.click
      expect(page).to have_content 'Email is invalid'
      expect(page).to_not have_content I18n.t('devise.registrations.signed_up')
    end
  end

  context 'Log in' do
    background do
      visit '/'
      click_link I18n.t('user.sign_in')
      page.fill_in 'Email', with: user.email
    end
    scenario 'when I sign in with valid details.' do
      page.fill_in 'Password', with: 'P4ssword'
      submit.click
      expect(page).to have_content I18n.t('devise.sessions.signed_in')
      expect(page).to have_link I18n.t('user.sign_out')
    end
    scenario 'when I sign in with an invalid password' do
      page.fill_in 'Password', with: 'H4XX0R'
      submit.click
      expect(page).to_not have_content I18n.t('devise.sessions.signed_in')
    end
  end
end

Seems OK to me.

However, it might be nice to add a "macro" to let you skip the I18n. and just use t like you do in views.

And you can add some extra checks while you're at it, since you'll i18n want it to make noise when testing.

For instance, you could add a file like spec/support/macros/i18n_macros.rb with the following:

module I18nMacros
  def t(*args)
    I18n.translate!(*args)
  end
end

Using translate! will cause i18n to raise an exception if the translation you're looking for doesn't exist.

Then include it in spec_helper.rb

config.include I18nMacros

or alternatively include it for type: :feature specs only.

And if you haven't already (it's default for newer versions of Rails), set i18n to raise exceptions in your views (the above will only raise on the stuff in your tests). Put something like this in config/environments/test.rb

# Raises error for missing translations
config.action_view.raise_on_missing_translations = true