Catalogue manipulation I have a catalogue of 56000 objects and I want to replace some columns with new values for instance replace NaN with -99 and 0 for specific columns (as you can see in the following code). Then I need to compute a value for some columns with a function which is called  get_ebv_from_map
and subtract it from some other columns and so on.

Using get_ebv_from_map function to estimate the values in the catalogue is taking too much time and I think what I did like using this loop is not very efficient.

The function is given by:

from astropy import units as u
from astropy.coordinates import SkyCoord
from scipy.ndimage.interpolation import map_coordinates
import os.path
from collections import Iterable
import pyfits as fits
def get_ebv_from_map(coordinates, interpolate=True, order=1):

    mapdir='/vol/Dust_Map/maps/'
    fname = os.path.join(mapdir, 'SFD_dust_4096_{0}.fits')

    # Parse input
    ra, dec = coordinates
    coordinates = SkyCoord(ra=ra, dec=dec, unit=(u.degree, u.degree))

    # Convert to galactic coordinates.
    coordinates = coordinates.galactic
    l = coordinates.l.radian
    b = coordinates.b.radian

    # Check if l, b are scalar
    return_scalar = False
    if not isinstance(l, Iterable):
        return_scalar = True
        l, b = np.array([l]), np.array([b])

    # Initialize return array
    ebv = np.empty_like(l)

    # Treat north (b>0) separately from south (b<0).
    for n, idx, ext in [(1, b >= 0, 'ngp'), (-1, b < 0, 'sgp')]:

        if not np.any(idx): continue
        hdulist = fits.open(fname.format(ext))
        mapd = hdulist[0].data

        # Project from galactic longitude/latitude to lambert pixels.
        # (See SFD98).
        npix = mapd.shape[0]
        x = (npix / 2 * np.cos(l[idx]) * np.sqrt(1. - n*np.sin(b[idx])) +
             npix / 2 - 0.5)
        y = (-npix / 2 * n * np.sin(l[idx]) * np.sqrt(1. - n*np.sin(b[idx])) +
             npix / 2 - 0.5)

        # Get map values at these pixel coordinates.
        if interpolate:
            ebv[idx] = map_coordinates(mapd, [y, x], order=order)
        else:
            x=np.round(x).astype(np.int)
            y=np.round(y).astype(np.int)
            ebv[idx] = mapd[y, x]

        hdulist.close()

    if return_scalar:
        return ebv[0]
    return ebv

The loop is given in below:

ABtoVEGA=[+0.77,-0.13,-0.02,+0.19,+0.49,-0.19,-0.18,-0.06,-0.06,+0.04,+0.10,+0.22,+0.27,+0.36,+0.45,+0.56,+0.50]

ZP=np.loadtxt("zero-points.offsets.asc")
Gal=np.loadtxt("photometry_galaxies_photometry.cat", dtype=None)
ra=Gal[:,1]
dec=Gal[:,2]

Av=[3.836 ,3.070,2.542,2.058,1.313, 3.466 , 3.082 , 2.882 , 2.652 , 2.367 , 2.226 , 2.066 , 1.872 , 1.652 , 1.423 , 1.298 , 1.156]
count=0
for i in range(Gal.shape[0]):
    j=0
    m=39
    while (j<len(ABtoVEGA)):
         if ((isnan(float(Gal[i,j+5]))) or (isnan(float(Gal[i,j+22])))):
            Gal[i,j+5]='-99.0'
            Gal[i,j+22]='0.0'
            count+=1
         else:
            value=get_ebv_from_map((ra[i], dec[i]), interpolate=True, order=1)
            Gal[i,j+5]=str(float(Gal[i,j+5])-ABtoVEGA[j]-ZP[j]-value*Av[j])
         j+=1
    while (m<45):
          if (math.isnan(float( Gal[i,m]))):
              Gal[i,m] = '0.0'
          m+=1

Do you have any advice on how I could make it optimal and fast?

I'll echo the comments and say that a profile would really help you as far as diagnosing performance problems. Profile before trying any kind of performance optimizations, because whatever you think is going on, that's probably not it. (This applies to me as well, so take everything I say below about performance with a grain of salt.)

Your code is kind of hard to read. I would review PEP 8 for style advice. In particular, spaces around your operators would help a lot. You do this pretty consistently in get_ebv_from_map, but in the driving loop, everything's all scrunched up.

Your get_ebv_from_map function is really long and has all this different stuff going on. That could be masking performance problems, and it'll make profiling harder. If you split some of it into separate functions, the profiler will give you individual performance statistics for those functions, which could be a big help.

I'm not too familiar with this library, so mock me as I deserve if my understanding of the code is egregiously wrong, but offhand, it looks to me like you're doing lots of disk IO; these lines:

for n, idx, ext in [(1, b >= 0, 'ngp'), (-1, b < 0, 'sgp')]:

    if not np.any(idx): continue
    hdulist = fits.open(fname.format(ext))  # this one
    mapd = hdulist[0].data

look like they're opening and reading a file on every iteration of the loop and extracting one value, which is the only thing used in the rest of the loop body. You then call this function in another loop, so you have a loop in which you have a loop in which you open and read a file on every iteration. I'm guessing at least one of those loops does a substantial number of iterations, so that could be a huge performance drag, since disk access is slow. And if I'm reading your code correctly, you only have two unique file extensions, 'ngp' and 'sgp', and your fname doesn't seem to be changing, so you're opening and reading the same two files over and over again, sticking the first value (hdulist[0].data) into a variable, and throwing away that value when the iteration is done.

To test this, I would try isolating that loop into its own function and profiling to see how its speed compares with the rest of the code. Something like:

def main_loop(a):
    for n, idx, ext in [(1, b >= 0, 'ngp'), (-1, b < 0, 'sgp')]:
        # Rest of the code

and call that inside get_ebv_from_map where you now have the main loop. Profile, and compare the runtime of the main_loop function with the rest of the get_ebv_from_map function.

If that does turn out to be a problem, I would try to pre-read these files somehow, or save the values you need somewhere and reuse them across invocations. If the items you're reading fit reasonably in main memory, I would try to cache them. Something like this:

for n, idx, ext in [(1, b >= 0, 'ngp'), (-1, b < 0, 'sgp')]:

    # Other necessary code
    if ext not in mapdcache:
        with fits.open(fname.format(ext)) as hdulist:
            mapdcache[ext] = hdulist[0].data
    else:
        mapd = mapdcache[ext]

mapdcache is a dictionary or list declared at some outer scope (I wrote that code like it was a dictionary). If your files are fixed across calls of get_ebv_from_map (which seems to be the case since you have mapdir and fname as constants), you can put mapdcache outside of get_ebv_from_map and you'll just have to read each file once across the entire run of the program. Otherwise it can go inside, just above this loop, and you'll at least avoid repeated file IO within one call.

I'm not familiar enough with what happens when things get bigger than main memory to offer any suggestions if your data surpasses the size of main memory.


JMS configuration -- client exclusive messages I am SURE this is somehow easy but reading the docs isn't bringing it to light.

The problem: I am trying to setup a JMS message listener and what I need is for the first client to have exclusive message processing rights.

That is: Until a single client acknowledges the message the server will not notify any other consumers of the message.

I believe this is correct but I am looking for some verification. The whole 'transacted' part is throwing me off

As an aside: I posted it to regular SOF and got told to repost here.

  public class QueueMessengerMessageListener implements MessageListener {

    protected Logger log = LoggerFactory.getLogger(getClass());

    private Connection connection;

    @Autowired
    private Queue q;

    @Autowired
    private ConnectionFactory connectionFactory;

    @Autowired
    private DWHService dwhService;

    @PostConstruct
    private void listen() throws JMSException {
        connection = connectionFactory.createConnection();
        Session jmsSession = connection.createSession(false, Session.CLIENT_ACKNOWLEDGE);
        MessageConsumer consumer = jmsSession.createConsumer(q);
        consumer.setMessageListener(this);
        connection.start();
    }

    @PreDestroy
    public void destroy() throws JMSException {
        connection.close();
    }

    @Override
    @Transactional
    public void onMessage(Message m) {
        BytesMessage jmsMessage = (BytesMessage) m;
        MyObject userMessage = null;
        try {
            byte[] in = new byte[(int) jmsMessage.getBodyLength()];
            jmsMessage.readBytes(in);
            ObjectInputStream inStream = new ObjectInputStream(new ByteArrayInputStream(in));
            userMessage = (MyObject) inStream.readObject();
            dwhService.addDwhEntry(userMessage);
            m.acknowledge();

        }
         catch (Exception e) {
            /* I normally wouldn't catch *all* exceptions, but the JMS tutorial says Thou Shalt Not throw
             * a RuntimeException from this method. */
             log.error("Error sending message {}",  e.getMessage());
        }
    }
}

The code looks fine although I'm not familiar with JMS, so I can't say anything about it's correctness. Just three minor notes:

userMessage could be declared inside the try block:

try {
    byte[] in = new byte[(int) jmsMessage.getBodyLength()];
    jmsMessage.readBytes(in);
    ObjectInputStream inStream = new ObjectInputStream(new ByteArrayInputStream(in));
    MyObject userMessage = (MyObject) inStream.readObject();
...

(Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

protected Logger log = LoggerFactory.getLogger(getClass());

The logger could be private.

(Item 13 of Effective Java 2nd Edition: Minimize the accessibility of classes and members.)
The logger also could be static. There is a good template for Eclipse for generating getLogger calls with MyType.class classes instead of getClass():

private static final Logger log = LoggerFactory.getLogger(QueueMessengerMessageListener.class);


Filtering out employees that do not meet some criteria, using list comprehensions Right now I have a list of dictionaries. In order to filter out all the entries I do not want included in the list, I am running it through multiple list comprehensions.

Is there a more Pythonic or better way to write these comprehensions that seem repetitive?

#FILTER OUT ALL EMPLOYEES WHO WILL NOT BE FACTORED INTO METRICS
inScope = [s for s in set2 if s['LEAD_TIME'] >= 0]#lead times 0 or more
set2 = inScope

inScope = [s for s in set2 if s['WRK_RLTN_DSC'] != "INDEPENDENT CONTRACTOR"]#not independent contractor
set2 = inScope

inScope = [s for s in set2 if s['WRK_RLTN_DSC'] != "OUTSIDE CONSULTANT"]#not outside consultant
set2 = inScope

inScope = [s for s in set2 if s['WRK_RLTN_DSC'] != "OUTSIDE CONTRACTOR"]#not outside contractor
set2 = inScope

inScope = [s for s in set2 if s['WRK_RLTN_DSC'] != "EMP OF STRATEGIC INVESTMENT CO"]#not emp of strategic investment co
set2 = inScope

inScope = [s for s in set2 if s['BUS_GRP_CD'] != "FIL"]#In scope after removal of FIL Int'l Associates
set2 = inScope

The simplest refactoring is as follows:

CONDITIONS = [
    ('WRK_RLTN_DSC', 'INDEPENDENT CONTRACTOR'),
    ...
]
set2 = [s for s in set2 if s['LEAD_TIME'] >= 0]
for key, excl in CONDITIONS:
    set2 = [s for s in set2 if s[key] != excl]

Note:

You can assign straight back to set2, getting rid of the temporary inScope variable;
I have factored out the multiple checks into a simple loop over a list of keys and values; and
I have consistently used single quotes for string literals, rather than a mix of single and double.

However, although neater than your current code, this is still relatively inefficient, as it builds multiple lists; you could instead try something like:

set2 = [s for s in set2 if s['LEAD_TIME'] >= 0 and
        all(s[key] != excl for key, excl in conditions)]

which reduces it to a single list comprehension. An alternative would be to incorporate e.g.:

INVALID_WRK = {
    'INDEPENDENT CONTRACTOR',
    ...
}

... s['WRK_RLTN_DSC'] not in INVALID_WRK ...

as you check that key multiple times.


Searching a string for any permutation of words Given a string and an array of words, return all indexes in string for which a concatenation of all words in the array,
  in any order (so ["eensie", "weensy", "spider"] has six orderings) can be matched. All words will be the same length.

I am new to programming so please tell me where my big slow down points are. I still am failing the time test.

 var findSubstring = function(s, words) {
         var concatLength =
         for (var i = 0; i < words.length; i++){
         concatLength += words[i].length;
       } //concatLength is now length of all possible concatentations
       var stringLength = s.length;
       var answers = [];

       if (concatLength > stringLength || concatLength === 0){
           return answers;
       }  //outlier cases where answer is inevitably an empty array
         var wordLength = words[0].length  //each word is the same length
         var currentPerm;  //this will be used in permutation function we call
       for (var i = 0; i < stringLength + 1 - concatLength; i++){
           try { //if a match is found in recursive permutations function, an object of type TrueValue is thrown up the stack
             wordsInString(words.slice(), -1, s.substr(i, concatLength));
           }
           catch(e){
               if (e.constructor === TrueValue)
                   answers.push(i);
               else
                  throw e;
           }

       }
       function TrueValue() { //constructor of instances to be thrown up stack in case of match
       }
       function wordsInString(words, index, string){ //permutations function
         if (index === -1)  //In each loop outside it is called with -1 as index, so we reset currentPerm to be empty
                    currentPerm = [];
         if (words.length === 0){  //if currentPerm is full, check if it matches string.  If so throw instance of TrueValue up the stack
                   if (currentPerm.join("") === string)
                       throw new TrueValue();
               }
          for (var i = 0; i < words.length; i++){
            if (string.substr(0,(currentPerm.length + 1) * wordLength) === currentPerm.join("") + words[i]){ //if what is already in currentPerm were to have this word concatenated onto it, would it be potential match of index of string we are currently on?  If so, move this word off of words array and onto currentPerm.  Continue to try all possible concatenations of words we have left via recursion
                     currentPerm.push(String(words.splice(i, 1)));
                     wordsInString(words, i, string);
                   }
               }
               if (index !== -1) //unless this is the first call to wordsInCurrentString, take last word of currentPerm off and move it back onto the place it was on in words before this particular call was made
                   words.splice(index, 0, currentPerm.pop());
               else
                   return false;
           }
       return answers;
    };

OK, first of all, exceptions are slow. Any code that uses exceptions in the normal flow of the application will be slow. Only use exceptions for something that has gone terribly wrong in your application, never for the normal execution of your code.

Having said that, I approached the problem from a different angle. You have two tasks in essence: the first task is to generate all the permutations of the input array of words. The second task is, for every permutation of the words you calculate, concatenate them into a pattern string, and try to find that pattern in your input string wherever it may occur. Since these are two entirely separate tasks, isolate them in separate functions. The great thing about doing this is that you can test them separately and only use them in the overall solution when you know they work properly.

The second task is actually way simpler than the code you have, where you are continually chopping up the input string through substr(). You are missing the indexOf() function which just returns the index of the pattern in the string, or -1 if it was not found. Even better, the second parameter to indexOf() is the starting index for the search (with a default of 0).

Here's one way of doing that second task.

var findPermutation = function (permutation, s, result) {
  "use strict";
  var i, index,
      pattern = permutation.join("");

  for (i = 0; i < s.length - pattern.length; i += 1) {
    index = s.indexOf(pattern, i);
    if (index >= 0) {
      result.push(index);
      i = index;
    }
  }
};

var result = [];
findPermutation(['a', 'b', 'c'], "abcabc", result);
console.log(result); // should be [0, 3]
findPermutation(['c', 'a', 'b'], "abcabc", result);
console.log(result); // should now be [0, 3, 2]

A few things to note here: permutation is some permutation of an array of words and so is itself an array. s is the string to search through, and result is an array of indexes that have been found. The for loop is cut short when the remaining bit of the string to search through is smaller than the pattern length. The code at the end is testing this simple routine (and if I'd written it properly, the test code would itself check that result has the right values. So, BOOM, we have the second part done; now all we have to do is generate the complete set of permutations from an array.

Here, I did it in a functional style: rather than have the routine generate, say, a huge array of all the permutations, I wrote the routine to accept a callback function and this will be called for every permutation that was generated (after which the permutation can be thrown away). In other words, the permutation generator would generate the next permutation, execute the callback function with this value, and then go back and calculate the next permutation. It would stop this merry-go-round once all the permutations had been generated.

For the permutation generator I went with Heap's Algorithm. It's the fastest, you can read up about it on wikipedia, and I'd already written about the algorithm and written a JavaScript version on my blog. Here's that code:

var generatePermutations = function (items, process) {
  "use strict";
  var generate = function (last, items, process) {
    var
      i,
      swap = function (x, y) {
        //console.log(x + " <=> " + y);
        var temp = items[x];
        items[x] = items[y];
        items[y] = temp;
      };

    //console.log(last);
    if (last === 0) {
      process(items);
    }
    else {
      // if last is even
      if ((last & 1) !== 1) {
        for (i = 0; i < last; i += 1) {
          generate(last - 1, items, process);
          swap(0, last);
        }
      }
      // else last is odd
      else {
        for (i = 0; i < last; i += 1) {
          generate(last - 1, items, process);
          swap(i, last);
        }
      }
      generate(last - 1, items, process);
    }
  };

  generate(items.length - 1, items, process);
};

generatePermutations(['a', 'b', 'c', 'd'], function (items) {
  console.log(items.join(""));
});

The last bit of the code shows how it is called: an array of items to be permuted and then a callback function that will be called for every permutation generated (all this one does is to merely output the items joined into a string).

If you are not familiar with this style of writing callback functions you can separate them out like this:

var callbackFunction = function (items) {
  console.log(items.join(""));
};
generatePermutations(['a', 'b', 'c', 'd'], callbackFunction);

So now we have it all: a permutation-of-words generator and a pattern matcher for each permutation of words. Since the callback function is so simple -- it only requires one parameter, yet the matcher requires three, I wrapped things up in another function:

var findPermutations = function (s, words) {
  "use strict";
  var result = [];

  generatePermutations(words, function (permutation) {
    var i, index,
        pattern = permutation.join("");

    for (i = 0; i < s.length - pattern.length; i += 1) {
      index = s.indexOf(pattern, i);
      if (index >= 0) {
        result.push(index);
        i = index;
      }
    }
  });

  return result;
};

console.log(findPermutations("abcdabcd", ['a', 'b', 'c', 'd']));

Again I threw in a small test case at the end to check that everything worked. If you run it, it'll output [0, 4, 3, 2, 1] (with the matching patterns being abcd, abcd, dabc, cdab, bcda).

Aside: things that still aren't great.

The permutation generator is a bit long-winded and can be rewritten to use some helper functions.
The permutation generator modifies the input array of words. It should make a copy, so that the original array is not changed.
I ignored the case where the length of the concatenated words is longer than the search string and hence nothing needs to be done. Easy exercise for the reader.


Tcl loop idea: for_index_item I often need to loop through a list of items and need both the index position, and the item itself:

set names {John Paul George Ringo}
set i 0
foreach name $names {
    puts "$i - $name"
    incr i
}

Output:

0 - John
1 - Paul
2 - George
3 - Ringo

Since I frequently do this, I decided to implement my own loop and call it for_item_index for lack of creativity. Here is my loop and a short code segment to test it:

proc for_index_item {index item iterable body } {
    uplevel 1 set $index 0
    foreach x $iterable {
        uplevel 1 set $item $x
        uplevel 1 $body
        uplevel 1 incr $index
    }
}

# Test it
set names {John Paul George Ringo}
for_index_item i name $names {
    puts "$i - $name"
}

I have tested it with break, and continue and found my new loop performs as expected. My concern is the excessive use of uplevel command in the code. I am seeking reviewers to give me tips for improving it.

Here are my own review of my code:

Excessive use of uplevel
The index always starts at zero. There are times when I want it to start at 1 or some other values. To add that feature, I will probably introduce another parameter, startValue
Likewise, the index always get incremented by 1. The user might want to increment it by a different values such as 2, or -1 to count backward. Again, introducing another parameter, step might help, but at this point, the loop is getting complicated.

I would base something like this on for rather than foreach

proc foreach_with_index {idxvar elemvar list body args} {
    array set opts {-start 0 -inc 1}
    if {[llength $args] > 0 && [llength $args]%2 == 0} {array set opts $args}
    upvar 1 $idxvar idx
    upvar 1 $elemvar elem
    for {set idx $opts(-start)} {$idx < [llength $list]} {incr idx $opts(-inc)} {
        set elem [lindex $list $idx]
        uplevel 1 $body
    }
}

So you get

% foreach_with_index i e {a b c d e} {puts "$i - $e"}
0 - a
1 - b
2 - c
3 - d
4 - e
% foreach_with_index i e {a b c d e} {puts "$i - $e"} -start 1 -inc 2
1 - b
3 - d

Some thoughts:

don't forget about upvar to link a variable up the call stack.
I chose to use Tk style -options for some reason. It looks a bit awkward, but it's not exactly pretty to have to jam arguments at the end. You might choose to arguments with default values for start and inc. Or you might decide to put optional arguments in the middle of the list somewhere (like the way puts has an optional filehandle as the 1st arg), but that's more work to parse the arguments.
in hindsight, using for vs foreach is a pretty arbitrary decision. Here, with for, you need to extract the element from the array. With foreach you need to increment the index.


Sherlock and Anagrams Given a string S, find the number of "unordered anagrammatic pairs"
  of substrings.

  Input Format

  First line contains T, the number of testcases. Each testcase
  consists of string S in one line.

  Output Format

  For each testcase, print the required answer in one line.

  Sample Input#00

2
abba
abcd

  Sample Output#00

4
0

In the below code I am finding all the possible sub strings and then checking all the pairs of equal length to check if they are anagrams or not.

public class Solution {
    private static int N = 26;

    private static boolean isAnagram(String a, String b) {
        int []countA = new int[N];
        int []countB = new int[N];

        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }

        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }

        for (int i = 0; i < N; i++) {
            if (countA[i] != countB[i]) {
                return false;
            }
        }

        return true;
    }

    private static int getPairsCount(String text) {
        int count = 0;
        int length = text.length();

        List<String> subsets = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            for (int j = 1; j <= length - i; j++) {
                subsets.add(text.substring(i, i + j));
            }
        }

        for (int i = 0; i < subsets.size(); i++) {
            for (int j = i + 1; j < subsets.size(); j++) {
                String s1 = subsets.get(i);
                String s2 = subsets.get(j);
                if (i != j &&
                    s1.length() == s2.length() &&
                    isAnagram(s1, s2)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();

        for (int i = 0; i < N; i++) {
            System.out.println(getPairsCount(s.next()));
        }
    }
}

Questions:

I have to agree it took me a lot of time to find the above solution because I spend a lot of time into finding the linear algorithm. For this solution I think that it's \$\mathcal{O}(n^3)\$ solution which feels slow to me.

I need to know how to approach problems like these? when to know that there can't be any linear algorithm possible?

You can speed up your code by changing changing strategy. The overall goal is to determine the occurrence counts (frequencies) of all possible 'normalised' substrings of the given input, and then to use these counts for computing the number of pairings.

'Normalised' means processed in a way that gives all anagrams the same physical representation, either by sorting the substrings on character code (which is \$\mathcal{O}(N log N)\$ where \$N\$ is the length of the string to be normalised) or by frequency counting (which is \$\mathcal{O}(N)\$).

Byte-sized variables are sufficient for frequency counting since inputs are no longer than 100 characters, which means the normalised form of any string will by an array of 26 bytes. Which version is better depends on the (unknown) input distribution, but normalisation by sorting is simpler to arrange in Java than frequency counting and hence preferrable.

The number of possible substrings of a string of length \$K\$ is \$K * \frac{(K + 1)}{2}\$, normalisation was discussed above, and dictionary lookups are amortised \$O(M)\$ where \$M\$ is the length of what's being looked up. Hence overall complexity of this simple approach is quadratic, modulo a logarithmic component if normalisation is done by sorting instead of frequency counting (but that doesn't change the overall picture much), and modulo an additional linear factor if you look up variable-length substrings instead of fixed-length frequency count arrays.

Given the shortness of the inputs, this simple solution should be fast enough to be accepted. If the envelope needs to be pushed then there is no ready-made recipe. The only thing safe to say is that enumerating substrings one by one will invariably add a quadratic component to the complexity.

Also, the constant factor dropped by the asymptotic can be several orders of magnitude depending on how smart you go about enumerating the normalised forms of all substrings. For example, you could enumerate all substrings starting at a given position by starting with the character at that position, adding it to the map, inserting the next character in sorted order, adding that to the map, and so on. That would make the cost of a single normalisation \$\mathcal{O}(log N)\$ instead of the \$\mathcal{O}(N log N)\$ for taking a substring and sorting it, or \$\mathcal{O}(1)\$ if frequency counting is used. A similar strategy can be used with frequency counts. This incremental approach is what makes the overall complexity quadratic instead of cubic (but beware of var-length strings as discussed above).

Also, the are data structures like tries that can handle operations on substrings in linear time instead of quadratic, but the algorithms get really involved. You really need to know your basic data structures and algorithms inside out in order to see whether they can help you with a given problem. I'm not certain whether Sherlock and Anagrams can be solved with less than quadratic complexity without resorting to tries.

However, as a general strategy you should take the problem and look for ways of not doing work, to strip the problem down to its irreducible core of work that cannot possibly be avoided. And remember that counting things can be easier computationally speaking than enumerating them and incrementing a count. E.g. if you know that there are \$K\$ somethings then you can compute the number of their possible pairings in \$\mathcal{O}(1)\$ with a bit of combinatorics, instead of enumerating and counting at a cost of \$\mathcal{O}(K^2)\$. Another classic example is the length of the longest common subsequence of two strings which can be computed in \$\mathcal{O}(N^2)\$ even though the number of possible common subsequences is exponential.


Switching from functional jQuery code to object-oriented I've been happily using jQuery, creating vars and binding events in my modules (which have only a little bit of JS). But recently I needed to add an anonymous functions to my code and after investigating some more, I learned about modular patterns and encapsulation.

So what I'm trying to teach myself is to write clean, fast and maintainable JavaScript code in object-oriented fashion (as opposed to "functional" jQuery code before).

My module inserts a search box (input) that uses Ajax and displays drop-down results.

What I want to have is a template file with the search box other necessary elements;
Then the most flexible way would be to pass the elements to the code in JavaScript file - I could easily adjust settings in the same file if I decide to change IDs or the elements.

Then there should be a separate file with the actual code; It should make no presumptions about the elements of the page.

I follow this article:

http://esbueno.noahstokes.com/post/77292606977/self-executing-anonymous-functions-or-how-to-write

These are my thoughts and what I would like to know:

Is this structure written correctly to accomplishing this task?
Is the anonymous function (self-executing one) being used correctly here?
Is there anything to be optimized (maybe I'm "overkilling" something)?
Is $.proxy used correctly?
I to use an object to defined methods, however, I cant think of a way to only expose a public method. Is writing non-objective (simple enclosed vars and functions) the way to go?

search_box.tpl

<script type="text/javascript" src="autosearch.js"></script>

<form>
    <input id="search-1" type="search">
</form>

<script type="text/javascript">
    AutoSearch.init({
        input  : $('#search-1'),
        option2: ''
    });
</script>

autosearch.js

var AutoSearch = (function($) {

    var search = {

        cache: {},
        bindEvents: function(){
           this.input.on('keyup', $.proxy(this.processInput, this));
        },
        processInput: function(){ alert(this.input.val()); },

        init: function(options) {
            this.input = options.input;

            this.bindEvents();
        }
    }

    return search;

    })(jQuery);

Your mistake is in your processInput() function, it is not created as part of the search object and is invalid syntax the way you have it written.

I try to avoid private functions in javascript as it makes them difficult to test, but if you really wanted to have private functions, you could write your module like this:

var AutoSearch = (function () {
    "use strict";

    // private
    var my = {},
        input;

    // private
    function processInput() {
        alert(input.val());
    }

    // private
    function bindEvents() {
        input.on('keyup', processInput());
    }

    // public
    my.init = function (options) {
        input = options.input;
        bindEvents();
    };

    return my;
}());

It's not obvious to me that you need jQuery or .proxy() at this point, since all the data and functions for the event handler are inside the closure.


A matrix with square diagonals and transpose being increments of other Construct a matrix with the following property:

North-west to South East diagonals are squares.

Matrix[i][j] + 1 = Matrix[j][i] for each i less than j.

Example of such m a matrix is here. Also, since it appears this matrix does not have a name, I have named my class "Sqaure Diagonal, Transpose Increment".
Looking for code review, best practices, clever optimzations etc.
public final class SquareDiagonalTransposeIncrement {

    private SquareDiagonalTransposeIncrement() {}

    public static int[][] getSqaureDiagonalTransposeIncrementMatrix (int dimension) {
        if (dimension < 1) {
            throw new IllegalArgumentException("dimension: " + dimension + " should be greater than 0");
        }

        final int[][] m = new int[dimension][dimension];

        // set the diagonal
        for (int i = 0; i < dimension; i++) {
            m[i][i] = (i + 1) * (i + 1);
        }

        /*
         * Definition of the quadrant.
         *
         * - 0th quadrant means a quadrant square matrix from (0,0) to (0,0)
         * - 1st quadrant means a quadrant square matrix from (0,0) to (1,1)
         * - 2nd quadrant means a quadrant square matrix from (0,0) to (2,2)
         *
         */
        for (int quadrant = 0; quadrant < dimension - 1; quadrant++) {
            besiegeQuadrant(m, quadrant);
        }

        return m;
    }

    private static void besiegeQuadrant(int[][] m, int quadrant) {
        int value = m[quadrant][quadrant];

       // besiege the quadrant from the eastern and southern boundaries.
        for (int i = 0; i <= quadrant; i++) {
            m[i][quadrant + 1] = ++value; // eastern
            m[quadrant + 1][i] = ++value; // southern
        }
    }

    public static void main(String[] args) {
        int[][] m =  SquareDiagonalTransposeIncrement.getSqaureDiagonalTransposeIncrementMatrix (4);
        assertArrayEquals(new int[]{ 1, 2, 5, 10}, m[0]);
        assertArrayEquals(new int[]{ 3, 4, 7, 12}, m[1]);
        assertArrayEquals(new int[]{ 6, 8, 9, 14}, m[2]);
        assertArrayEquals(new int[]{11,13,15, 16}, m[3]);
    }
}

Throwing a different spin on the process, I think you are missing an alternate algorithm that produces the same result....

Here is a 'simple' loop that 'works'. It works because it uses a different 'rule' that is based on the pattern that your matrix creates.

The Pattern is obvious when you study the matrix from the bottom-right corner, and work backwards. The initial value is the square of the matrix size. Then you subtract 1 to the left, then another 1 above, and another 1 to the next left, and another 1 to the next above, etc.

private static final int[][] buildMagicMatrix(int size) {
    int value = size * size + 1;
    int[][] matrix = new int[size][size];
    for (int i = size - 1; i >= 0; i--) {
        matrix[i][i] = --value;
        for (int d = i - 1; d >= 0; d--) {
            matrix[i][d] = --value;
            matrix[d][i] = --value;
        }
    }
    return matrix;
}

Using this algorithm you produce results like:

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


Counting number of nodes between two nodes This code counts the number of nodes between any given two nodes in a circular linked list. Any feedback is appreciated:

public class CountNodesBetweenTwoNodes {
  Node first;
  Node fifth;

  private class Node<Item> {
    Item item;
    Node next;
  }

  public static void main(String[] args) {
    CountNodesBetweenTwoNodes countNodes = new CountNodesBetweenTwoNodes();
    countNodes.buildCircularList();
    int noOfNodes = countNodes.countNodesBetweenTwoNodes(countNodes.getFirst(), countNodes.getFifth());
    System.out.println("Number of Nodes is: "+noOfNodes);
  }

  private Node buildCircularList() {
    first = new Node();
    first.item = "First";

    Node second = new Node();
    second.item = "Second";

    Node third = new Node();
    third.item = "Third";

    Node forth = new Node();
    forth.item = "Forth";

    fifth = new Node();
    fifth.item = "Fifth";

    first.next = second;
    second.next = third;
    third.next = forth;
    forth.next = fifth;

    fifth.next = first;

    return first;
  }

  private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
    int count = 0;

    while(firstNode.next != secondNode) {
        count++;
        firstNode = firstNode.next;
    }

    return count;
  }

  public Node getFirst() {
    return first;
  }

  public Node getFifth() {
    return fifth;
  }
}

Your program is really based only of case where you have 5 nodes. This make your code really hard to change if you want to have a "list" of node of a different size.

The name of the class should represent a concept not an action, CountNodesBetweenTwoNodes could be something like CircularList or something like that. A name that would represent what the class is, not what it does.
Personally, I find that re-using the first argument in the loop to iterate over the list is not what I would want. I would use a third Node variable to let to show that I'm iterating and that my firstNode will not change during this method.

private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
    int count = 0;

    while(firstNode.next != secondNode) {
        count++;
        firstNode = firstNode.next;
    }

    return count;
}

I would rename the class variable Node fifth for Node last, what if you have more than five nodes ? Would you change your code ? I hope not, so by changing the name to represent that it's the last one, we are good to not limit our-self to five nodes.
Since we changed the name of the variable, we should change public Node getFifth() too for public Node getLast().
You should always specify a visibility for you class variable. Currently, first and fifth are package visibility, they should be private.
There is a bug in your class: you made your countNodesBetweenTwoNodes private. If I want to use your class myself, I could not use this method since I would not be in your class. You don't have this problem since you use the method in your main which is in the class. If you move your main method to another class, your program is not working anymore.


Tile and grid abstraction This question is a small subset of the problem I am trying to solve.
I am trying to learn to break problems into better abstractions.

The original problem I am trying to solve is:

  Write a JS library which allows an user to select an Image and then divide the image into square tiles. Calculate the average color of each tile and render the equivalent number of svg elements from top to bottom and left to right direction. The request for each svg element should be an XHR request.

I decided to create two abstractions for now:

Grid
Tile

here is the code:

class Tile {
  constructor(shape='', width = Tile.Width, height = Tile.Height) {
    this.shape = shape;
    this.width = width;
    this.height = height;
  }

  render() {
    return this.shape;
  }
}
Tile.Width = 50;
Tile.Height = 50;

class Grid {
  constructor(rows, cols) {
    this.cells = [];
    this.R = rows;
    this.C = cols;
    for (let row = 0; row < rows; row++) {
      const cells = [];
      for (let col = 0; col < cols; col++) {
        cells.push({
          x: col * Tile.Width,
          y: row * Tile.Height,
          tile: new Tile()
        });
      }
      this.cells.push(cells);
    }
  }

  setTile(shape, {row, col}) {
    if (row < 0 || row >= this.R || col < 0 || col >= this.C) {
      throw new Error("Invalid tile position");
    }
    this.cells[row][col] = {
      x: col * Tile.Width,
      y: row * Tile.Height,
      tile: new Tile(shape)
    };
  }

  render() {
    let output = [];
    this.cells.forEach(row => {
      output.push(this.renderRow(row));
    });
    console.log(output.join('\n'));
  }

  renderRow(cells) {
    let output = [];
    cells.forEach(cell => {
      output.push(cell.tile.render());
    });
    return output.join(' ');
  }
}

const grid = new Grid(2, 2);
grid.setTile('', {row: 0, col: 1});
grid.setTile('', {row: 1, col: 0});
grid.setTile('', {row: 0, col: 1});
grid.setTile('', {row: 1, col: 1});
console.log(grid.render());

Here is the live example.

Question

Does the design of the grid system is compatible with the requirement so far? I want it to be used in the canvas or some other rendering platform so is this a good design?

Your question

  Does the design of the grid system is compatible with the requirement so far?

Well, maybe I don't understand how setting characters (be them Unicode if necessary, as your example shows) on each tile relates to dividing an image into squares but it seems like you would want to allow the user to upload or choose an image (perhaps from a list), which might likely be a binary file. Then you would need to do some graphical analysis of the image and divide up the area of the image (perhaps using the dimensions).

Feedback on code

Design

It appears that when a Grid object is created, it creates cells as plain objects that have an x, y and tile property. Then when the setTile() method is called, it re-assigns those cells, but the only thing that really changes is the tile, so the calculations of x and y seem unnecessary. Additionally, the tile object doesn't need to be recreated - the shape property could be simply re-assigned - perhaps via a setter method, but that property is public so it could be modified outside the class unless it is made private (though that is only experimental1.

forEach with push

The render() method of the Grid uses foreach with push:

let output = [];
this.cells.forEach(row => {
  output.push(this.renderRow(row));
});

That is essentially the map method re-implemented... Why not use that method?

const output = this.cells.map(row => this.renderRow(row));

Notice that const is used because that value is never re-assigned. This can even be used with the forEach, since calling push() doesn't re-assign the value.

The same principle applies for the renderRow() method.

render method

This method does not return any values, it merely logs output to the console. However, the method is called inside a call to console.log(), which results in undefined being output to the console. Maybe that is not a concern for you if you are the only one using the console (perhaps for debugging purposes) but be aware of this if you intend on primarily using the console for output.

undefined
=> undefined

1https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes#Field_declarations


strncpy To strcpy Equivalence I have this ugly function, and I feel that the entire strncpy should just be an strcpy:

void PackData(char*& cursor, const std::string& data) {
    *(reinterpret_cast<int*>(cursor)) = static_cast<short>(data.length() + 1);
    cursor += sizeof(int);
    // copy the text to the buffer
    ::strncpy(cursor, data.c_str(), data.size());
    cursor += (data.length() * sizeof(char));
    *(reinterpret_cast<char*>(cursor)) = 0;
    cursor += sizeof(char);
}

cursor is guaranteed to have enough room to contain all the data copied. And data only contains a '\0' character at termination.

I want to update this function to use strcpy, and to remove some of the ugly. Here's what I have:

void PackData(char*& cursor, const std::string& data) {
    const int size = data.size() + 1;

    std::copy_n(cursor, sizeof(int), reinterpret_cast<char*>(&size));
    cursor += sizeof(int);
    strcpy(cursor, data.c_str());
    cursor += size;
}

My code works fine, but I wanted to ask if anyone sees any misbehavior that I may have missed?

The new version of your function does not have any actual mistakes I could spot. It is good that you have replaced the assignment to *(reinterpret_cast<int*>(cursor)) with a call to std::copy_n because the old version (presumably) violated strict aliasing rules and therefore invoked undefined behavior. (Also think about alignment.) It also seemed wrong in your old function that you casted data.length() + 1 to short instead of int.

I have a few “soft” remarks, though.

Avoid output parameters

Taking a pointer by reference and then modifying does not appear pretty to me. Instead, I'd take the pointer by-value and return the number of bytes by which it was advanced.

std::size_t PackData(char * cursor, const std::string& data);

It looks better and allows for more flexible use.

Chose the appropriate library function

The string manipulation functions from the C standard library all operate on NUL terminated strings. That is, std::strcpy has to look at every byte of the string to determine whether it is the end of the string. You've mentioned that your string does not contain NUL bytes today. But what if it will do so in the future? Will you remember to update the function? And even if you are sure that NUL bytes will never be an issue, it is still less efficient than it could be. Since the std::string already knows its own length, you have a couple of options available.

std::memcpy – if you like doing things the C way
std::copy – if you like doing things the STL way
std::string::copy – if you like doing things the OO way

Note that none of these functions will NUL terminate the copied string, so you'll have to add the NUL byte yourself. Not hard to do.

cursor[size] = '\0';

Using std::memcpy could also help you with storing the length. Since its arguments are void pointers, there is no need to cast anything.

std::memcpy(cursor, &size, sizeof(size));

looks cleaner to me than

std::copy_n(cursor, sizeof(int), reinterpret_cast<char*>(&size));

Don't repeat yourself

Your code mentions the type of size three times. Once in the declaration – which is fine – and then two times in sizeof expressions. By using sizeof(size) instead of sizeof(int), you can eliminate this redundancy. If you ever change the data type, you only need to do so in one place and you can't get it inconsistent.

Verify your assumptions

The cast

const int size = data.size() + 1;

looks rather safe. But are you sure? Integer overflow is a nasty source of bugs and a potential entry door for crackers. I would recommend two things.

First, make the fact that you're narrowing explicit by spelling it out.

const auto size = static_cast<int>(data.size() + 1);

Note that I can use auto now in order to follow the advice from the previous section.

Second, add defensive code (before the cast) to verify your assumptions.

assert(INT_MAX > data.size());

This is safe if your function is only called with trusted input. If attackers are of concern, assert is the wrong tool because it may be compiled out and you don't want your debug builds to be safe only to open security holes in your release builds. Therefore, an explicit check like

if (INT_MAX <= data.size())
  throw std::invalid_argument {"data too large"};

would be preferred in this case.

This code is safe as long as sizeof(int) <= sizeof(std::string::size_type) which I believe is true on almost any implementation. However, it might still trigger a compiler warning about comparing a signed and an unsigned integer. Actually, size could be unsigned anyway.

Alternatively, you could use a helper function checked_cast<int>(data.size() + 1). I believe that the argument cannot overflow because a std::string always has to account for the possibility to NUL terminate its buffer.

Watch out for data leaks

I don't know about the environment in which your function is called but is the buffer that cursor points to aligned? If so, watch out for unused padding bytes after the end of the string and the next thing that is written into the buffer. They might leak information you'd rather not have anybody see.


Knockout computed observables in ES6 I am trying out for the first time knockoutjs and babeljs and have a question on how to do computed observables properly. Both fullName and fullNameComp properties are updated whenever firstName and lastName changes so not sure about pros/cons:

employee

<input type="text" data-bind="value: firstName, valueUpdate: 'keyup'" />
<input type="text" data-bind="value: lastName, valueUpdate: 'keyup'" />

Full name getter: <spane data-bind='text: fullName'>

Full name pure computed:

import ko from 'knockout';
import templateMarkup from 'text!./employee.html';

class Employee {
constructor(params) {
    this.firstName = ko.observable('John');
    this.lastName = ko.observable('Smith');
    this.fullNameComp = ko.pureComputed(function() {
        return this.firstName() + " " + this.lastName();
      }, this);
}

get fullName() {
    return this.firstName() + ' ' + this.lastName();
}

dispose() {
    // This runs when the component is torn down. Put here any logic necessary to clean up,
    // for example cancelling setTimeouts or disposing Knockout subscriptions/computeds.
}
}

export default { viewModel: Employee, template: templateMarkup };

Your fullName() function will return the same result but only when called.  The computed will always have the updated value and can be used as a trigger for other code if needed.  For example, you can subscribe to fullNameComp but you cannot subscribe to fullName as it doesn't extend from KO's observable.

If the function fullName meets your needs then use it.


Extracting a div from parsed HTML It seems that lxml/etree are generally imported as from lxml import etree -- why is that?  It keeps the code tidier, and while the potential namespace ambiguity might not be a concern, I don't have any incentive of doing this as it's generally frowned upon.

I know for a script of this size it doesn't matter much, but I'm going to be using these modules for a lot more. I'm also curious about what others have to say.

#!/usr/bin/python
# Stuart Powers http://sente.cc/

import sys
import urllib
import lxml.html
from cStringIO import StringIO

""" This script parses HTML and extracts the div with an id of 'search-results':
  ex:
...

$ python script.py "http://www.youtube.com/result?search_query=python+stackoverflow&page=1"
The output, if piped to a file would look like: http://c.sente.cc/E4xR/lxml_results.html

"""

parser = lxml.html.HTMLParser()

filecontents = urllib.urlopen(sys.argv[1]).read()

tree = lxml.etree.parse(StringIO(filecontents), parser)

node = tree.xpath("//div[@id='search-results']")[0]

print lxml.etree.tostring(tree, pretty_print=True)

You might be confusing from lxml import etree that is a legitimate (even preferred) form of an absolute import with relative imports for intra-package imports that are discouraged: http://www.python.org/dev/peps/pep-0008/ (see "Imports" section)


Mechanism to retry failed requests, with throttling I have a simple event that the client sends to the server, the server can then respond saying if it was successful, or if it failed for some reason.

The client has to send a auth code, which is inside their config class. Below I attempt to throttle it, allowing 2 attempts, then reloading the config after the 2nd failed attempt.

If it still fails 2 more attempts after reloading the config, I throttle it for 60 seconds. If it fails after reloading the config 3 or more times (12 requests), then I just refuse to resend it.

Please note that I understand just leaving it and not warning the user why it failed to connect to the server is wrong, but I haven't finished with that code yet, and will adapt later on.

I'm just looking to see if its okay, and if I can improve it in any way.

public class HandshakeFailedEvent : IIncomingPacketEvent
{
    private static int ATTEMPTS_BEFORE_CONFIG_RELOAD = 2;
    private static int ATTEMPTS_BEFORE_THROTTLE = 4;
    private static int SECONDS_TO_THROTTLE = 60;

    private int _timesFailed;
    private int _timesSinceReset;

    public void Process(ICoreContext coreContext, IIncomingPacket packet)
    {
        if (packet.GetInteger("error_code") == 1) // WRONG_PASSWORD
        {
            CheckForThrottle(coreContext);
        }

        // Other error codes may need fixing, not throttling, handle here.

        coreContext.SocketHandler.SendPacket(new HandshakeRequestComposer(coreContext.ConfigHandler));
    }

    private void CheckForThrottle(ICoreContext coreContext)
    {
        _timesFailed++;
        _timesSinceReset++;

        if (_timesFailed >= ATTEMPTS_BEFORE_THROTTLE * 3)
        {
            // Application.Restart();
            return;
        }

        if (_timesSinceReset >= ATTEMPTS_BEFORE_CONFIG_RELOAD && _timesSinceReset < ATTEMPTS_BEFORE_THROTTLE)
        {
            coreContext.ConfigHandler.Download();
        }
        else if (_timesSinceReset >= ATTEMPTS_BEFORE_THROTTLE)
        {
            Task.Delay(SECONDS_TO_THROTTLE * 1000).ContinueWith((t) => { _timesSinceReset = 0; });
        }
    }
}

Prefixing field members with _ is more of an "old school" C# approach. It's a preference, I guess, but I think it's not really used anymore.

If the only thing you do with SECONDS_TO_THROTTLE is Task.Wait(SECONDS_TO_THROTTLE * 1000), then SECONDS_TO_THROTTLE should be equal to 60000, not 60, it's kind of confusing. At first I thought maybe there was something related to milliseconds, but no.

Reading your explanation, I understand why you do : if (_timesFailed >= ATTEMPTS_BEFORE_THROTTLE * 3), but if I only had your code, I wouldn't. Consider either adding another constant or maybe a comment.

CheckForThrottle's name is confusing. Reading this, I'd expect the method to tell me if I need to throttle, not to do the throttling itself. I'd either rename it to something else. But then again, I'd notice that a name like MaybeThrottle is a poor name. I'd keep the "should I throttle?" approach in this method, but I'd move Task.Delay(SECONDS_TO_THROTTLE * 1000).ContinueWith((t) => { _timesSinceReset = 0; }); some place else.


Rendering explosion of bouncing balls on a canvas I'm making a particle engine that can spawn new explosions while keeping particles from previous ones active (until they despawn).

The code works well on its own but within the game, two or more active explosions at once causes stutters, especially on laptops that are a few years old. I'm wondering if there's something inherently inefficient with my code, or if any of the coding practices used are bad.

In in the code snippet below, you can click anywhere within the canvas element to see the particle effect. Let me know if there's something that's unclear.

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
var explosions = [];
var mouseX;
var mouseY;

canvas.addEventListener('mousemove', setMouse, false);

canvas.addEventListener('click', function() {
    explosions.push(new explosion(mouseX, mouseY));
}, false);

function loop() {
    ctx.clearRect(0, 0, 500, 500);
    drawExplosion();
    requestAnimationFrame(loop);
}

loop();

function drawExplosion() {
    if (explosions.length === 0) {
        return;
    }

    for (let i = 0; i < explosions.length; i++) {
        const explosion = explosions[i];
        const projectiles = explosion.projectiles;

        if (projectiles.length === 0) {
            explosions.splice(i, 1);
            return;
        }

        const projectilesRemove = projectiles.slice();

        for (let ii = 0; ii < projectiles.length; ii++) {
            const projectile = projectiles[ii];

            // remove projectile if radius is below 0
            if (projectile.radius < 0) {
                projectilesRemove.splice(ii, 1);
                continue;
            }

            // draw
            ctx.beginPath();
            ctx.arc(projectile.x, projectile.y, projectile.radius, Math.PI * 2, 0, false);
            ctx.closePath();
            ctx.fillStyle = 'hsl(' + projectile.h + ',' + projectile.s + '%,' + projectile.l + '%)';
            ctx.fill();

            // update
            projectile.x -= projectile.vx * 1;
            projectile.y -= projectile.vy * 1;
            projectile.radius -= 0.02;

            // collisions
            if (projectile.x > 500) {
                projectile.x = 500;
                projectile.vx *= -1;
            }

            if (projectile.x < 0) {
                projectile.x = 0;
                projectile.vx *= -1;
            }

            if (projectile.y > 500) {
                projectile.y = 500;
                projectile.vy *= -1;
            }

            if (projectile.y < 0) {
                projectile.y = 0;
                projectile.vy *= -1;
            }
        }

        explosion.projectiles = projectilesRemove;
    }
}

function explosion(x, y) {
    this.projectiles = [];

    for (let i = 0; i < 100; i++) {
        this.projectiles.push(
            new projectile(x, y)
        );
    }
}

function projectile(x, y) {
    this.x = x;
    this.y = y;
    this.radius = 2 + Math.random() * 4;
    this.vx = -10 + Math.random() * 20;
    this.vy = -10 + Math.random() * 20;
    this.h = 200;
    this.s = Math.floor((Math.random() * 100) + 70);
    this.l = Math.floor((Math.random() * 70) + 30);
}

function setMouse(e) {
    mouseX = e.offsetX;
    mouseY = e.offsetY;
}
<!DOCTYPE html>
<html>
<body>
<canvas id="canvas" width="500" height="500" style="border:1px solid #000;"></canvas>
</body>
</html>

Games and Animation.

Writing games means managing the compromise between the creative and artistic need, performance practicalities, and coding style.

When developing you usually have a top end gaming machine, sadly this is the wrong machine to develop on.

You need to have the minimum spec device you want your game to work well on as the development machine (or at least run on each test cycle) or you will always be frustrated with poor performance. It sucks, but it is easier to add features at run time that take advantage of a high end machine than to remove them to have it run on a low end machine.

Slow downs.

There are three main reasons that your code is slowing down.

Switching colors causes a state change that can be more expensive than the single draw function. It also forces you to draw using a new path for each item.
Rendering arcs is slow.
Rendering invisible or near invisible shapes still requires CPU cycles. You cull particles when their size is less than zero. But your update reduces the size by 0.02 per step so between radius 0.5 and 0 there are 25 near invisible particles rendered.

Also avoid ctx.closePath as for some reason it is mega slow. For arcs that will connect a path if you draw several it is far quicker to draw using

ctx.moveTo(x + r, y);
ctx.arc(x, y, r, 0, Math.PI * 2);

// An order of magnitude faster than

ctx.arc(x, y, r, 0, Math.PI * 2);
ctx.closePath();

Drawing arcs is slow, for small arcs you can not tell the difference between an arc and a rectangle. Test the size and draw rectangles when you are below the size of a few pixels.

Reduce color state changes

To reduce the state change overhead caused by color changes you need to reduce the number of colors used. This can be achieved using a color table with a limited number of colors. You then create the particles in the explosion so that they are grouped by color. This lets you combine renders and reduce state changes.

Seperat concerns

Separating the explosion logic Explosion.update (movement, decay, bouncing) from the rendering allows you to optimise the code for the particular need. The rendering of particles can be independent of the explosion allowing all particles of the same color to be rendered in the same path.

Each time you call ctx.beginPath() you instigate a whole pile of internal functions. This overhead can be avoided by grouping as many path items together. All particles of the same color should be between a ctx.beginPath() and ctx.fill() or ctx.stroke()

Memory management

Creating and de-referencing (deleting) objects adds additional work for the CPU. The deleting workload will manifest as GC hits (garbage collection) that are uncontrollable.

GC hit can be a major problem when writing animations and require attention to how you use memory.

Memory is plentiful, CPU cycles are not so the rule is don't delete during the animation. You can do this using object pools.

Object pools

Object pools are a store of unused object that can be used when needed. When you need to create a new particle you check the pool, if there are available items in the pool you use them, if not you create a new object. When an object's life is up, you copy the reference to the pool for later use.

If well balanced the pools will grow to a size that represents the max number of particles that are visible at one time. This means the pools do not add additional memory load past the max needed to run without pools.

Bubble sort

When handling array of objects that change size rather than splice them out you can use a bubble sort to sort the objects as you process them. The explosion object does this to manage its array of particles. That means the explosion's particle array ids always full and will not incur GC hits, or need allocation when pulled from the pool.

There are many more ways to optimise but the answer would grow out of control.

Significant performance gain

Using the above concepts can give Significant performance benefits. The example below can render 10 times as many particles than your code. Though there are subtle differences, you will be hard pushed to see them and to the casual observer they will appear identical.

Example

To describe all that is contained in the code below would take to long so will let the code speak.

To get the performance there is added complexity, but performance is more important for a game than simple code.

There are two additional objects. explosions and particles that are the pools and management roles for particles and explosions.

The particle behaviour is almost identical apart from,

(12 * 8 = 96) particles per explosion rather than 100
Different decay rates per particle (this is to spread out pooling operations)
8 particle colors rather than many.
Particles are removed when radius is less than half a pixel.
Particles that have a radius less than 2 pixels are rendered as rectangles
Order of color rendering is fixed, the same color will always be on top.

Non performance change

The explosion picks a random direction and speed per particle to give a more spherical appearance to the explosion.

I have added a performance indicator that give time to render, per particle time (PPT) which is the mean render time of a particle, and particles per frame (PPF). This is so you can compare performance between the example code and your code (added under this example).

const width = canvas.width;
const height = canvas.height;
const ctx = canvas.getContext("2d");
Math.PI2 = Math.PI * 2;

requestAnimationFrame(mainLoop);  // start with a frame dont call the function directly

var pCount = 0;
function mainLoop() {
    ctx.clearRect(0, 0, width, height);
    pCount = 0;
    const now = performance.now();
    explosions.update();
    particles.draw();
    const time = performance.now() - now;

    info.textContent = "Render Time: " + time.toFixed(3) + "ms PPT: " + (time / pCount).toFixed(4) + "ms PPF:" + pCount;
    requestAnimationFrame(mainLoop);
}

canvas.addEventListener('click', (e) => {
    const explosion = explosions.create();
    explosion.init(e.offsetX, e.offsetY);
});

// Number of particles per explosion is renderStyleCount * particlesPerStyle
const explosion = {
    renderStyleCount : 8,   // Number of color styles to use.
                            // Can't be more than explosion.colors.length
    particlesPerStyle : 16, // Number of particles to add to explosion
                            // per color style
    colors : ["#0070a8", "#0077b3", "#0081c2", "#1282ba", "#57c7ff", "#66ccff", "#99ddff", "#a5f6ff"],
};

const explosions = Object.assign([], {
    pool : [],
    create() {
        var exp;
        if (explosions.pool.length) {
            exp = explosions.pool.pop();
        } else {
            exp = new Explosion();
        }
        explosions.push(exp);
        return exp;
    },
    update() {
        var i;
        for (i = 0; i < explosions.length; i ++) {
            if (explosions[i].update() === false) { // if false all particles are dead
                explosions.pool.push(explosions.splice(i--, 1)[0]); // send to pool
            }
        }
    },

});
const particles = Object.assign([], {
    pool : [],
    init() {
        var i;
        for (i = 0; i < explosion.renderStyleCount; i++) {
            particles.push(Object.assign([], {color : explosion.colors[i]})); // create style buckets
        }
    },
    create(style) {
        var p;
        if (particles.pool.length) {
            p = particles.pool.pop();
        } else {
            p = new Projectile();
        }

        p.style = style;
        particles[style].push(p);
        return p;
    },
    draw() {
        var i;
        for (const style of particles) {  // If you have many style you should create a pool for the styles as well
            if (style.length > 0) {
                ctx.beginPath();
                ctx.fillStyle = style.color;
                for (i = 0; i < style.length; i ++) {
                    const p = style[i];
                    if (p.dead) {
                        particles.pool.push(style.splice(i--,1)[0]);
                    } else {
                        pCount += 1;
                        const r = p.radius
                        if (r < 2) {
                            ctx.rect(p.x - r,p.y - r,r * 2, r * 2);
                        } else {
                            ctx.moveTo(p.x + r, p.y);
                            ctx.arc(p.x,p.y,r,0,Math.PI2);
                        }
                    }
                }
                ctx.fill();
            }
        }
    },
});
particles.init();

function Explosion(x, y) {
    this.particles = [];
    this.size = 0;
}
Explosion.prototype = {
    init(x, y) {
        var i, j, p, idx = 0;
        for (i = 0; i < explosion.renderStyleCount; i ++) {
            for (j = 0; j < explosion.particlesPerStyle; j ++) {
                this.particles[idx++] = p = particles.create(i);
                p.init(x, y);
            }
        }
        this.size = idx;
    },
    update() {  // implements a bubble sort to keep live particles grouped at the start of the array

        var head = 0, tail = 0;
        const particles = this.particles;
        const size = this.size;
        while (head < this.size) {
            const p = particles[head];
            p.x -= p.vx * 1;
            p.y -= p.vy * 1;
            p.radius -= p.decayRate;
            if (p.radius < 0.5) {  // particle is too small to see
                p.dead = true; // semaphore for particles object  to know when to pool particle
                head += 1;
            } else {
                p.collide();
                if (tail  0;
    },

}

// Capitalize Object name
function Projectile() {
    // hints the optimiser to type
    this.decayRate = this.style = this.radius = this.vy = this.vx = this.y = this.x = 0;
    this.dead = true;
}
Projectile.prototype = {
    init(x, y) {  // creates using direction and speed to make explosion more
                  // spherical in appearance.
        this.x = x;
        this.y = y;
        const dir = Math.random() * Math.PI2;
        const speed = Math.random() ** 0.5 * 10
        this.radius = 2 + Math.random() * 4;
        this.decayRate = Math.random() * 0.01 + 0.01;
        this.vx = Math.cos(dir) * speed;
        this.vy = Math.sin(dir) * speed;
        this.dead = false;
    },
    collide() {
        const p = this;
        if (p.x > width) {
            p.x = width;
            p.vx *= -1;
        }
        if (p.x < 0) {
            p.x = 0;
            p.vx *= -1;
        }
        if (p.y > height) {
            p.y = height;
            p.vy *= -1;
        }
        if (p.y < 0) {
            p.y = 0;
            p.vy *= -1;
        }
    },
}
#info {
position: absolute;
top: 0px;
left: 0px;
}
<canvas id="canvas" width="500"  height="500"></canvas>

Orignal code.

The next snippet is the original question code with some timing information added to compare the performance.

I made some minor changes to your code to add the timing information.

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
var explosions = [];
var mouseX;
var mouseY;

canvas.addEventListener('mousemove', setMouse, false);

canvas.addEventListener('click', function() {
    explosions.push(new explosion(mouseX, mouseY));
}, false);

var pCount = 0;
function loop() {
    ctx.clearRect(0, 0, 500, 500);
    pCount = 0;
    const now = performance.now();
    drawExplosion();
    const time = performance.now() - now;

    info.textContent = "Render Time: " + time.toFixed(3) + "ms PPT: " + (time / pCount).toFixed(4) + "ms PPF:" + pCount;
    requestAnimationFrame(loop);
}
loop();

function drawExplosion() {
    if (explosions.length === 0) {
        return;
    }

    for (let i = 0; i < explosions.length; i++) {
        const explosion = explosions[i];
        const projectiles = explosion.projectiles;

        if (projectiles.length === 0) {
            explosions.splice(i, 1);
            return;
        }

        const projectilesRemove = projectiles.slice();

        for (let ii = 0; ii < projectiles.length; ii++) {
            const projectile = projectiles[ii];

            // remove projectile if radius is below 0
            if (projectile.radius < 0) {
                projectilesRemove.splice(ii, 1);
                continue;
            }

            // draw
            ctx.beginPath();
            ctx.arc(projectile.x, projectile.y, projectile.radius, Math.PI * 2, 0, false);
            ctx.closePath();
            ctx.fillStyle = 'hsl(' + projectile.h + ',' + projectile.s + '%,' + projectile.l + '%)';
            ctx.fill();

            pCount++;
            // update
            projectile.x -= projectile.vx * 1;
            projectile.y -= projectile.vy * 1;
            projectile.radius -= 0.02;

            // collisions
            if (projectile.x > 500) {
                projectile.x = 500;
                projectile.vx *= -1;
            }

            if (projectile.x < 0) {
                projectile.x = 0;
                projectile.vx *= -1;
            }

            if (projectile.y > 500) {
                projectile.y = 500;
                projectile.vy *= -1;
            }

            if (projectile.y < 0) {
                projectile.y = 0;
                projectile.vy *= -1;
            }
        }

        explosion.projectiles = projectilesRemove;
    }
}

function explosion(x, y) {
    this.projectiles = [];

    for (let i = 0; i < 100; i++) {
        this.projectiles.push(
            new projectile(x, y)
        );
    }
}

function projectile(x, y) {
    this.x = x;
    this.y = y;
    this.radius = 2 + Math.random() * 4;
    this.vx = -10 + Math.random() * 20;
    this.vy = -10 + Math.random() * 20;
    this.h = 200;
    this.s = Math.floor((Math.random() * 100) + 70);
    this.l = Math.floor((Math.random() * 70) + 30);
}

function setMouse(e) {
    mouseX = e.offsetX;
    mouseY = e.offsetY;
}
#info {
    position: absolute;
    top: 0px;
    left: 0px;
    }
<canvas id="canvas" width="500"  height="500"></canvas>


Java client that consumes a RESTful web service created using Jersey 2 I'm learning web services using Java. I just don't know which method has what advantage over another, like which one is more secure? Which one will be more faster?

POST resource is as follows:

@POST
@Path("postactivity")
@Consumes(MediaType.APPLICATION_JSON)
@Produces(MediaType.APPLICATION_JSON)
public String createActivity(
        @QueryParam("id") int id,
        @QueryParam("description") String description,
        @QueryParam("duration") int duration,
        @QueryParam("name")String name)
{
    //My code that creates Activity object from QueryParams is here.
}

Now I've created a client which is a Java application. I'm consuming the REST service in the following two ways:

Method 1 - using HTTPURLConnection

private static void doPost(){
    QueryString qs = new QueryString("id", "123"); //QueryString is a class created to build query, not important to the question.
    qs.add("duration", "12");
    qs.add("description", "This is description");
    qs.add("name", "This is Name");
    String url = "http://localhost:8080/webservices/webapi/activities/activity?" + qs;

    URL obj;
    try {
        obj = new URL(url);
        HttpURLConnection con = (HttpURLConnection) obj.openConnection();
        con.setRequestProperty("Content-Type","application/json");
        con.setRequestMethod("POST");
        con.setRequestProperty("User-Agent", "Mozilla 5.0");
        con.setDoOutput(true);

        BufferedReader in = new BufferedReader(
                new InputStreamReader(con.getInputStream()));
        String inputLine;
        StringBuffer response = new StringBuffer();

        while ((inputLine = in.readLine()) != null) {
            response.append(inputLine);
        }
        in.close();

        Activity activity = GSON.fromJson(response.toString(), Activity.class); //This is for checking if i'm getting correct data back which I'm sending.

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

Method 2 - using WebTarget available via Jersey

private static void doPost(){
Response entity = webTarget
        .path("activities/postactivity")
        .queryParam("id",2204)
        .queryParam("description","Foo")
        .queryParam("duration",100)
        .queryParam("name", "Bar")
        .request()
        .post(null);
String entityRead = entity.readEntity(String.class);

System.out.println(entityRead);
Activity activityRead = GSON.fromJson(entityRead, Activity.class);
}

Realistically these are about the same.  WebTarget is a standard part of JAX-RS so if you were to move to another provider like RestEasy you wouldn't have to port it.  If you like standards then this would be the way to go.

HttpClient is common though not a standard in the JSR way.  It is very powerful and sometimes easier to use when you've got specialized requirements like custom SSL processing.  It is, however, a pain to keep up with.  Every release seems to deprecate something I'm using.

The security of either will depend on you - the libraries will not be significantly different in this area and it will be up to you to implement the code well.

Performance is also likely to be similar.  It's highly likely that the performance of your system will be dependent on something that takes significantly more time than any differences in these libraries.

I would always vote for code that is more readable and I'd argue the WebTarget way is easier to read.


Three-table queryset (full outer join?) in Django I've got three tables I need query to display to a user for a web application I've written. Each table (Url, Note, Quote) has a foreign key relation to the User table. For every User, I need to sort all Bookmarks, Notes and Quotes based on a _date_created_ field, then deliver that to the template as one iterable. This is for a toy/self-learning project so I don't really need to worry about scale.

The approach I've taken is this:

from operator import attrgetter

from app.models import Url, Note, Quote

date_dict = {}

for url in Url.objects.filter(user=request.user):
    date_dict[url.date_created] = Url.objects.get(date_created=url.date_created)

for note in Note.objects.filter(user=request.user):
    date_dict[note.date_created] = Note.objects.get(date_created=note.date_created)

for quote in Quote.objects.filter(user=request.user):
    date_dict[quote.date_created] = Quote.objects.get(date_created=quote.date_created)

my_query = sorted((date_dict[i] for i in date_dict.iterkeys()),
                  key=attrgetter("date_created"),
                  reverse=True)

I have also tried this:

from operator import attrgetter
from itertools import chain

from app.models import Url, Note, Quote

items = sorted(chain(Url.objects.filter(user=request.user),
                     Note.objects.filter(user=request.user),
                     Quote.objects.filter(user=request.user)),
               key=attrgetter("date_created"),
               reverse=True)

I'm concerned how expensive this would get if I had huge data sets (I don't), but from what I've read the second is faster.

This code works and does what I expect it to, but is there a better/faster approach?

EDIT Removed previous version which was pretty much telling you to use the second method shown above. Your first method loads everything from the database twice. (Django may do some caching, but still) I'm not sure why you are putting everything in the dictionary.

The problem with the current implementation is that sorting is done by python rather then in the database. It would be better to have the sorting done in the database. There are two ways I see of doing that.

You could have the three different sources sorted by the database. Then you could perform a merge pass to combine them. However, you are probably going to have need a lot of data before that becomes a worthwhile strategy. Sorting will be implemently in C for python which will make it have a speed advantage over a merge which you would have to implement in python.
You could redesign your database so Urls, Quotes, and Notes are stored in the same table. That way you could request the database to sort them.

Both of these strategies are really only helpful if you end up with a lot of data. If you have that much data you aren't going to want to present it all to the user anyways. The result is that its probably not useful.


Simple TCP client - memory issues Does this snippet take too much memory? How can I let the connection opened with the function connectTo outside the forever loop?

import Control.Concurrent
import Network
import System.IO
import Control.Monad
import System.Environment

main = do
    [host,port]<-getArgs
    let pn1 = fromIntegral ( read port::Int)
    forever $ do
        h <- connectTo host $ PortNumber pn1
        hSetBuffering h NoBuffering
        getLine >>= hPutStrLn h
        forkIO $ hGetContents h >>= putStrL

If I put the line forever ... after the line hSetBuffering, the connection is lost after one input.

It seems to me that this code open too much connection.

hGetContents gets all remaining input, using lazy IO.  The second call to hGetContents throws an error because the first call has already claimed the data, in a sense.

What I would do is have a separate thread tunnel data from the handle to standard output, and have the main thread tunnel data from standard input to the handle:

_ <- forkIO $ hGetContents h >>= putStr
getContents >>= hPutStr h

I would also use LineBuffering rather than NoBuffering, so it doesn't have to transmit a TCP packet for every character (*).

Thus, we have:

import Control.Concurrent
import Network
import System.Environment
import System.IO

main :: IO ()
main = do
    [host, port] <- getArgs
    h <- connectTo host $ PortNumber $ toEnum $ read port
    hSetBuffering stdout LineBuffering
    hSetBuffering h      LineBuffering
    _ <- forkIO $ hGetContents h >>= putStr
    getContents >>= hPutStr h

A couple notes:

I was able to avoid the type signature by using toEnum rather than fromIntegral.
_ <- forkIO $ ... suppresses a warning when the program is compiled with -Wall.

We can do better, though.  Currently, if the server disconnects, the user does not see that the server disconnected until hitting enter a couple times, which produces an ugly error message:

tcp-client: <socket: 3>: commitBuffer: resource vanished (Broken pipe)

Let's see if we can get the program to terminate when either the server or the client closes the connection.  Bear in mind that:

getContents and hGetContents terminate the list when EOF is reached.  Thus:

hGetContents h >>= putStr terminates when the server closes the connection
getContents >>= hPutStr h terminates when the user presses Ctrl+D

The program terminates when the main thread terminates, regardless if child threads still have work to do.

A good way to do this, I think, is to perform the receiving and sending in two separate threads, and have the main thread wait on an MVar:

done <- newEmptyMVar

_ <- forkIO $ (hGetContents h >>= putStr)
              `finally` tryPutMVar done ()

_ <- forkIO $ (getContents >>= hPutStr h)
              `finally` tryPutMVar done ()

-- Wait for at least one of the above threads to complete
takeMVar done

* Actually, sending individual characters at a time will probably trigger Nagle's algorithm.  Still, sending characters one at a time creates a lot of unnecessary CPU overhead.


Calculating the area of a circle This is one of tasks, which I had to do for the recruitment process at some company. Unfortunately they didn't like it so I've decided to share it here for discussion.

CircleArea.h

#ifndef CIRCLEAREA_H_
#define CIRCLEAREA_H_

//PI Number, with max precision for double (8 bytes)
const double PI = 3.141592653589793115997963468544185161590576171875;

double circleArea(double radius);

#endif

CircleArea.cpp

#include "CircleArea.h"
#include <stdexcept>

double circleArea(double radius)
{
    if(radius < 0)
    {
        throw std::invalid_argument("Radius cannot be less than zero");
    }

    return PI * radius * radius;
}

Why could the solution have been disliked by the recruiters?

I assume one of the complaints was with the constant.  There are various ways to calculate pi, using an exact calculation rather than using some number of digits.

Here's one example (in C++14):

constexpr auto pi()
{
    return std::acos(-1);
}

(For C++11, use a non-auto type, such as double or float.)

The constexpr keyword will allow this to be calculated at compile time.  You could still assign the return value to a constant or call the function inline where needed.  If you don't have C++11, then you can use const in place of constexpr, and just assign it to a constant.


Conversion of a simple Python Neural Network to a Haskell implementation I started with this code and modified and expanded it in Python. As an exercise/challenge to myself I decided to covert the original to Haskell. I either write imperatively or functionally. This is the first time I have tried converting from one logic to another.  I ran into a lot of little issue along the way. I aimed to just get it to work and I want to make it work better now.

import Data.List
import System.Random
import Data.Matrix hiding (transpose, trace)
import Debug.Trace

flipSign::Num a => a -> a
flipSign x = (-1) * x

nonlin:: Bool -> Double ->   Double
nonlin True x = x*(1.0-x)
nonlin False x =  1.0 / (1.0 + (exp $ flipSign x))

randomList :: (Random a) => Int -> [a]
randomList seed = randoms (mkStdGen seed)

sample:: [[Double]]
sample = map (map fromIntegral)[ [0,0,1], [0,1,1], [1,0,1], [1,1,1] ]
answers:: [[Double]]
answers = transpose $ map (map fromIntegral) [[0,0,1,1]]

syn0:: [[Double]]
syn0 = [[x] | x<- take 3 (randomList 42 :: [Double])]

dotp:: [[Double]] -> [[Double]] -> [[Double]]
dotp x y = toLists newMatrix
    where
        mx = fromLists x
        my = fromLists y
        newMatrix = multStd mx my

nextGeneration::[[Double]] -> [[Double]] -> ([[Double]], [[Double]]) -> ([[Double]],[[Double]])
nextGeneration x labels syn0_l1 = (new_syn0, l1)
    where
        l0 = x
        syn0 = fst syn0_l1
        l1 = map (map $ nonlin False) $ dotp l0 syn0
        l1_error = zipWith (zipWith (-)) labels l1
        l1_delta = zipWith (zipWith (*)) l1_error $ map (map (nonlin True)) l1
        new_syn0 = zipWith (zipWith (+)) syn0 $ dotp (transpose l0) l1_delta

generations::([[Double]] -> [[Double]]) -> [[Double]] -> Int -> [[Double]]
generations _ end 0 = end
generations fun weights count = generations fun (fun weights) (count - 1)

main = print $ snd $ iterate (nextGeneration sample answers ) (syn0, [[]] ) !!10000

You often switch between matrices and lists in the dotp function. Since that is an essential part of your code called every iteration and your data is a matrix, you should be using matrices everywhere.

In the documentation is noted, that there is a functor instance. That means you can use the function fmap on the matrix, which (in this case) maps a function over every cell. This means you can swap map (map fromIntegral) with fmap fromIntegral. The equivalent to zipWith (zipWith ..) is called elementwise.

The generations function doesn't seem to be called: you can avoid having dead code by compiling with warnings enabled, -Wall. The flipSign function is predefined and called negate.

I have changed nonlin to make the variable explicit, otherwise it wouldn't be clear what this Bool actually does. Furthermore, I have added some comments.

Finally, I have changed nextGeneration as there is no need to carry the l1 variable if it isn't needed by the next step. I've extracted that into a function (and so have to take the 9999th iteration in main).

Here is my version of the code:

import System.Random (randoms, mkStdGen)
import Data.Matrix

-- | input dataset
sample :: Matrix Double
sample = fmap fromIntegral $ fromLists
    [ [0,0,1]
    , [0,1,1]
    , [1,0,1]
    , [1,1,1]
    ]

-- | output dataset
answers :: Matrix Double
answers = transpose (fmap fromIntegral output)
    where
        output = fromLists [[0,0,1,1]]

-- | sigmoid function
nonlin :: Bool -> Double -> Double
nonlin derivative x = if derivative then x * (1.0 - x)
                                    else 1.0 / (1.0 + (exp (negate x)))

layer1 :: Matrix Double -> Matrix Double -> Matrix Double
layer1 l0 syn0 = fmap (nonlin False) (multStd l0 syn0)

nextGeneration :: Matrix Double -> Matrix Double
nextGeneration syn0 = new_syn0
    where
        -- forward propagation
        l1 = layer1 sample syn0

        -- how much did we miss?
        l1_error = elementwise (-) answers l1

        -- multiply how much we missed by the
        -- slope of the sigmoid at the values in l1
        l1_delta = elementwise (*) l1_error (fmap (nonlin True) l1)

        -- update weights
        new_syn0 = elementwise (+) syn0 (multStd (transpose sample) l1_delta)

main = do
    putStrLn "Output After Training:"
    print (layer1 sample result)
        where
            start = fromList 3 1 (randoms (mkStdGen 42))
            generations = iterate nextGeneration start
            result = generations !! 9999


Condensing multiple conditionals into function I feel like I'm repeating a ton of code here and there's got to be a better way to do this but am just completely spacing right now. I basically have an else if clause that, if their conditions are met, repeat the same code, but I'm also repeating the same code in the else statement along with a few other conditions.

What would be the best way to condense this? Could I create one master browser check function?

var searchEngine = document.referrer;

if ($('#userName').length){
      if (/Chrome/.test(searchEngine)){
         browser = "Chrome";
      } else if (/Firefox/.test(searchEngine)){
        browser = "FF";
      } else if (/Safari/.test(searchEngine)){
        browser = "Safari";
      }
} else if (/ip(hone|od|ad)/i.test(searchEngine)){
     if (/Chrome/.test(searchEngine)){
        browser = "Chrome";
     } else if (/Firefox/.test(searchEngine)){
        browser = "FF";
     } else if (/Safari/.test(searchEngine)){
        browser = "Safari";
     }
} else {
     if (/Chrome/.test(searchEngine)){
        browser = "Chrome";
     } else if (/Firefox/.test(searchEngine)){
        browser = "FF";
     } else if (/Safari/.test(searchEngine)){
        browser = "Safari";
     } else if (/ip(hone|od|ad)/i.test(searchEngine)){
        browser = "iOS";
     } else if (/(?:(compatible;.*)?Trident\/7.0)/ig.test(searchEngine)){
        version = 11;
        browser = "IE";
     } else if (/MSIE (\d+\.\d+);/.test(searchEngine)){
        browser = "IE";
     }
   }

The Chrome, Firefox, and Safari duplicated code exists as the first part of every conditional and those three can be moved outside. Then have all of the other logic in an else. You'll end up with the $('#userName').length and /ip(hone|od|ad)/i.test(searchEngine) being empty. The reason I haven't provided a code example is because only you can decide if that's a problem or not.


Class with multiple parameters as the object of a WeakReference I just read this post on how to avoid memory leaks with AsyncTask. The post proposed using a WeakReference and supplying a TextView as the object of the WeakReference.

In my code, I need to supply multiple parameters to the AsyncTask (not just one as shown in the post). So what I did was create an inner class with the parameters needed in the AsyncTask and use the said class as the object of the WeakReference.

private static class AddBooksToDatabase extends AsyncTask<String, String, String> {
        private final WeakReference<AddBooksDbParams> mReference;
        private String TAG = "TownFragment";
        Context mContext;
        WaveLoadingView waveView;
        TextView infoText;
        String townName;
        File mFile;

        public AddBooksToDatabase(AddBooksDbParams params) {
            this.mReference = new WeakReference<    >(params);
            mContext = mReference.get().mContext;
            infoText = mReference.get().infoText;
            townName = mReference.get().townName;
            mFile = mReference.get().mFile;
            waveView = mReference.get().waveView;
        }

        @Override
        protected String doInBackground(String... strings) {
            TownHelper helper = TownHelper.getInstance(mContext, dbName);
            SQLiteDatabase database = helper.getWritableDatabase();
            int booksSize = getFilesInFolder(mFile).size();
            //Stuffs
            return null;
        }

        @Override
        protected void onPreExecute() {
            if (waveView != null) {
                waveView.setVisibility(View.VISIBLE);
            }
        }

        @Override
        protected void onPostExecute(String s) {
            if (waveView != null) {
                waveView.setVisibility(View.GONE);
            }
        }

        @Override
        protected void onProgressUpdate(String... values) {
            super.onProgressUpdate(values);
            Log.d(TAG, "Progress report = " + values[0]);
            infoText.setText(values[0]);
        }

        @Override
        protected void onCancelled() {
            cancel(true);
        }
    }

    //Parameters for AddBooksToDatabase. This is to enable holding of a
    //single object of this class in WeakReference
    private class AddBooksDbParams {
        Context mContext;
        WaveLoadingView waveView;
        TextView infoText;
        String townName;
        File mFile;

        AddBooksDbParams(TextView infoText, Context context, File file,
                         String townName, WaveLoadingView waveView) {
            this.infoText = infoText;
            mContext = context;
            mFile = file;
            this.townName = townName;
            this.waveView = waveView;
        }
    }

When I want to execute the AsyncTask:

AddTownsDbParams params = new AddTownsDbParams(infoText, getActivity(), folder, mShelfLabel, mWave);
addBooksTask = new AddBooksToDatabase(params).execute();

The code is working quite aright but I want to know if I am doing wrong.

What about this

private static class AddBooksToDatabase extends AsyncTask<String, String, String> {

  private String TAG = "TownFragment";

  private WeakReference<Context> mContextRef;
  private WeakReference<TextView> mInfoTextRef;
  private WeakReference<String> mTownNameRef;
  private WeakReference<File> mFileRef;
  private WeakReference<WaveLoadingView> mWaveViewRef;

  public AddBooksToDatabase(Context context, TextView infoText, String townName, File file, WaveLoadingView waveView) {
    mContextRef = new WeakReference<>(context);
    mInfoTextRef = new WeakReference<>(infoText);
    mTownNameRef = new WeakReference<>(townName);
    mFileRef = new WeakReference<>(file);
    mWaveViewRef = new WeakReference<>(waveView);
  }

  @Override
  protected String doInBackground(String... strings) {
    TownHelper helper = TownHelper.getInstance(mContextRef, dbName);
    SQLiteDatabase database = helper.getWritableDatabase();
    int booksSize = getFilesInFolder(mFileRef).size();
    //Stuffs
    return null;
  }

  @Override
  protected void onPreExecute() {
    WaveLoadingView waveView = mWaveViewRef.get();
    if(waveView != null) {
      waveView.setVisibility(View.VISIBLE);
    }
  }

  @Override
  protected void onPostExecute(String s) {
    WaveLoadingView waveView = mWaveViewRef.get();
    if(waveView != null) {
      waveView.setVisibility(View.GONE);
    }
  }

  @Override
  protected void onProgressUpdate(String... values) {
    super.onProgressUpdate(values);
    Log.d(TAG, "Progress report = " + values[0]);
    TextView infoText = mInfoTextRef.get();
    infoText.setText(values[0]);
  }

  @Override
  protected void onCancelled() {
    cancel(true);
  }
}

Without seeing the surrounding code or understanding too much about it's purpose/function, here is how I would change the code

private static class AddBooksToDatabase extends AsyncTask<String, String, String> {

  private String TAG = "TownFragment";

  private WeakReference<Context> mContextRef;

  private String mTownName;
  private File mFile;

  private Dialog mProgressDialog;

  private TextView mInfoText;
  private WaveLoadingView mWaveView;

  /*
  * A constructor/method should rarely exceed 3 parameters.
  * */
  public AddBooksToDatabase(Context context, String townName, File booksFolder) throws IOException {
    /*
    * Since the file parameter must be a directory add in this
    * check as early as possible and throw a checked exception
    * which the caller must handle if it fails.
    * */
    if(!booksFolder.isDirectory()) {
      throw new IOException("the file " + booksFolder.getName() + " is not a directory");
    }
    /*
    * Holding a WeakReference to the Context because
    * the AsyncTask should not outlive the Context.
    * */
    mContextRef = new WeakReference<>(context);

    mTownName = townName;
    mFile = booksFolder;

    /*
    * The progress views are initialised inside the
    * AsyncTask, no need to pass them in as arguments.
    * */
    mInfoText = new TextView(context);
    mWaveView = new WaveLoadingView(context);

    /*
    * Create a dialog to display the progress views.
    * */
    LinearLayout progressDialogView = new LinearLayout(context);
    progressDialogView.setOrientation(LinearLayout.VERTICAL);
    progressDialogView.addView(mInfoText);
    progressDialogView.addView(mWaveView);
    mProgressDialog = new AlertDialog.Builder(context)
        .setTitle("Adding books")
        .setView(progressDialogView)
        .create();
  }

  @Override
  protected void onPreExecute() {
    /*
    * Display the progress dialog
    * when the task starts executing.
    * */
    mProgressDialog.show();
  }

  @Override
  protected String doInBackground(String... strings) {
    final Context context = mContextRef.get();
    TownHelper helper = TownHelper.getInstance(context, dbName);
    SQLiteDatabase database = helper.getWritableDatabase();
    int booksSize = getFilesInFolder(mFile).size();
    //Stuffs
    return null;
  }

  @Override
  protected void onProgressUpdate(String... values) {
    super.onProgressUpdate(values);
    Log.d(TAG, "Progress report = " + values[0]);
    mInfoText.setText(values[0]);
  }

  @Override
  protected void onPostExecute(String s) {
    /*
    * Dismiss the progress dialog
    * when the task finishes executing.
    * */
    mProgressDialog.dismiss();
  }

  @Override
  protected void onCancelled() {
    cancel(true);
  }

}


Unique character lookup I'm solving 387. First Unique Character in a String LeetCode problem defined as:

  Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

  Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

  Note: You may assume the string contain only lowercase letters.

Taking advantage of the input being fully lowercase ASCII I created two bit vectors to track when we encounter a character for the first and second time.

Can this code be improved further? LeetCode says that below code is better than 94.33% solutions. What else could have been done by the last 5.67% solutions that they were better?

class Solution {

  public int firstUniqChar(String s) {
    int firstSpot = 0;
    int secondSpot = 0;
    char[] chars = s.toCharArray();

    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((firstSpot & mask) == 0) {
        firstSpot |= mask;
      } else if ((secondSpot & mask) == 0) {
        secondSpot |= mask;
      }
    }

    int i = 0;
    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((secondSpot & mask) == 0) {
         return i;
      }
      i++;
    }
    return -1;
  }

}

Are there tricks that can be done to improve the LeetCode score? It seems that enhanced for-each loop performs better than standard for loop but I can't prove it. It's an observation based on few of my previous submissions.

When in doubt, profile. We may theorize about possible optimizations, but only the profiler can definitely say where the program does spend time.
That said,

the first/second spot logic looks suboptimal. Consider

if ((firstSpot & mask) != 0) {
    secondSpot |= mask;
} else {
    firstSpot |= mask;
}

(using else may also be redundant).

It is unclear (to me) how for (char c : chars) over the char array fares against other techniques. This could be an entertaining reading.

Yet again, profile.
Strictly speaking, the challenge only says the string contain only lowercase letters, but does not specify the locale.