Hover on list items to change map marker styling I'm struggling to make a React/JS map I have more efficient. Essentially, I have a list of cards, and then a map of markers. When I hover on one of the cards, it changes the styling of the marker.

Here’s what it looks like:

But the way I'm doing this...I'm pretty sure is really inefficient, so here's how I have it setup in a couple of components:

//LocationsGrid.js
class LocationsGrid extends React.Component {
  state = {
    hoveredCardId: ""
  };

  setCardMarkerHover = location => {
    this.setState({
      hoveredCardId: location.pageid
    });
  };

  resetCardMarkerHover = () => {
    this.setState({
      hoveredCardId: ""
    });
  };

render() {
    const { locations } = this.props;

{locations.map((location, index) => (
    <LocationCard
      setCardMarkerHover={this.setCardMarkerHover}
      resetCardMarkerHover={this.resetCardMarkerHover}
      location={location}
    />
 ))}
   // map stuff

          <MapAndMarkers
            locations={locations}
            hoveredCardId={this.state.hoveredCardId}
          />

//LocationCard.js
class LocationCard extends React.Component {
  render() {
    const { classes, location } = this.props;

    return (
      <Card
        className={classes.card}
        onMouseEnter={e => this.props.setCardMarkerHover(location)}
        onMouseLeave={e => this.props.resetCardMarkerHover()}
       >
        <CardContent className={classes.cardContentArea}>

        </CardContent>
      </Card>
    );
  }
}

// MapAndMarkers.js

class MapAndMarkers extends React.Component {
  render() {
    const { locations, hoveredCardId, pageid } = this.props;

    let MapMarkers = locations.map((location, index) => {
      return (
        <MapMarker
          key={location.id}
          lat={location.lat}
          lng={location.lng}
          pageid={location.pageid}
          hoveredCardId={hoveredCardId}
        />
      );
    });

    return (

        <GoogleMapReact>
          {MapMarkers}
        </GoogleMapReact>

    );
  }
}

// MapMarker.js
import classNames from 'classnames';
class MapMarker extends React.Component {
  render() {
    const { classes, pageid, hoveredCardId } = this.props;

    return (

      {this.props.name}

    );
  }
}

The problem with doing it this way is I'm pretty sure there's a whole bunch of wasted rendering. When I pulled out the mouse events from my LocationCard, everything else runs faster.

What would be a more efficient way of tracking hovered list items so that I can change the map marker style?

GitHub

Demo

While I wouldn't say your code is inefficiently styled, you can definitely improve the performance of your components.

React performs in a tree format, when a component updates, all their children will attempt to update and potentially re-render. This is part of what React calls the Reconciliation process.

There is a function you can add to your component classes called componentShouldUpdate, which comes with parameters (nextProps, nextState). The idea of this function is to decide whether the component needs to re-render.  You can find some more information on this property here.

For example, if you were to hover and change the colour of one of the markers, the entire list of markers rerenders, but, you can make a check to see whether the specific marker is the one you want to color and so needs to be updated.

These kinds of stops on rerendering means as high as possible in your render trees means you can get the most performance gains.

shouldComponentUpdate(nextProps) { // inside MapMarker.js
    const { props } = this;
    return props.hoveredCardId !== nextProps.hoveredCardId
      || nextProps.hoveredCardId !== props.pageid;
}


Python factory class with dynamic imports I'm trying to write a factory class that essentially provides a user-friendly frontend to creating objects of different kinds depending on keywords. So the user will just have to import this module, and then use module.factory.make_new with the relevant keywords.
The directory structure will be pretty flat: this file will sit in a directory along with SubclassA.py which defines the class SubclassA likewise for SubclassB etc. That is, each subclass is in its own module of the same name.
If the user wants to dig a bit deeper, they can provide their extension to the code by writing SubclassC.py which provides class SubclassC and then add the line factory.register_format("subclassc", "SubclassC") to the bottom of this file (or, eventually, this will be handled by a config file). Here's what I have so far:
import importlib

class TrackerFactory:
    def __init__(self):
        self.subclass_dict = {}

    def register_format(self, subclass_name, subclass_package):
        fmt = importlib.import_module(subclass_package)
        self.subclass_dict[subclass_name] = getattr(fmt, subclass_package)

    def make_new(self, subclass, **kwargs):
        return self.subclass_dict[subclass](subclass, **kwargs)

factory = TrackerFactory()
factory.register_format("subclassA", "SubclassA")
factory.register_format("subclassB", "SubclassB")

I'm just wondering what the possible downsides of this sort of approach are, and what kind of gotchas I might have to look out for. Is there a better way to do this? I get the feeling I can achieve what I want with class methods and a class variable dictionary, and thus avoid hardcoding an instance of the factory, but I couldn't get it to work...
Some things I'm not bothered by:

sneaky hidden imports not at the top of the file (the advantages of dynamically loading the dependencies of only the registered formats outweigh the poor style, for me). And in any case, this is only used to load a very specific type to module. The modules themselves being loaded in this way (SubclassA etc) could have lots of unusual dependencies.

Some things I've already thought of:

extend the register_format method to allow the module name and class name to differ
use some try/except logic
since, in my use case, there will actually be only one or a few objects actually instantiated, I could juggle things around so that the import is actually in make_new (and subclass_dict just holds a string rather than the function), and then registering a format you won't use that you don't have the dependencies for wouldn't choke.

If a factory pattern is indeed called for - much of the time it is not - there is an easier way that needs neither importlib nor explicit registration calls.
If you follow something like this layout:
mypackage/
mypackage/__init__.py
mypackage/tracker_factory.py
mypackage/trackers/__init__.py
mypackage/trackers/type_a.py
mypackage/trackers/type_b.py
...

then in mypackage/trackers/__init__.py:
from .type_a import TypeA
from .type_b import TypeB
...

then your factory can import mypackage.trackers as all_trackers, do a dir(all_trackers), and every subtype that you care about will be listed. Instead of a dynamic import plus runtime registration calls, this uses traditional imports and will look up the individual type using getattr() on the module object. The class and module names are automatically able to differ though it would not be a good idea to do so. The subtype modules would still be able to import, as you put it, "unusual dependencies".
If you are concerned about the performance impact of initializing modules that you may not end up using, I think this concern is unwarranted - though of course you haven't shown any code as evidence one way or the other. A properly-written Python module should be fast and safe to load, and should only incur execution expenses when something is called.


Picking a time based on when the app was last used I am trying to set up a time variable as a local storage property to be retrieved when I open my app in my browser.

If I open it for the first time, today, I'll set it up to today at midnight.

Otherwise, if the time property has already been set up today in a previous session, I'll provide the retrieved value to the session, and assign Date.now to the local storage property for next time I'll visit my app.

I am trying to use ternary operators in place of if statements, but I see duplicated code I am not able to avoid. I am sure I am missing a trivial logic error, but I am not seeing it right now.

const NotificationsStorage: { lastCheck: number } = JSON.parse(localStorage.getItem('NotificationsStorage'));
const today: number = moment().startOf('day').valueOf();
const now: number = moment().valueOf();

localStorage
    ? NotificationsStorage
        ? (NotificationsStorage.lastCheck && NotificationsStorage.lastCheck > today)
            ? (
                this.lastCheck = NotificationsStorage.lastCheck,
                localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: now }))
            )
            : (
                localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: today })),
                this.lastCheck = today
            )
        : (
            localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: today })),
            this.lastCheck = today
        )
    : console.warn('Current browser doesn\'t support Local Storage API');

Whether you use ternaries or classic if/else you can often make your nesting easier to read by inverting your conditions. i.e.

! window.localStorage
    ? console.warn('Current browser doesn\'t support Local Storage API');
    : NotificationsStorage
    && NotificationsStorage.lastCheck
    && NotificationsStorage.lastCheck > today
        ? (
            this.lastCheck = NotificationsStorage.lastCheck,
            localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: now }))
        )
        : (
            localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: today })),
            this.lastCheck = today
        )

Although you can't do it with a ternary operator, I also usually prefer to use early returns to limit nesting. This also avoids the issue that you access localStorage in your first line even though it might not exist.

if (! window.localStorage) {
  console.warn('Current browser doesn\'t support Local Storage API');
  return;
}

const NotificationsStorage: { lastCheck: number } = JSON.parse(localStorage.getItem('NotificationsStorage'));
const today: number = moment().startOf('day').valueOf();
const now: number = moment().valueOf();

if (NotificationsStorage
    && NotificationsStorage.lastCheck
    && NotificationsStorage.lastCheck > today) {
      this.lastCheck = NotificationsStorage.lastCheck,
      localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: now }))
 } else {
      localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: today })),
      this.lastCheck = today
}

You could simply that last if by separating the variables and the logic to update them:

const {newStoredValue, newLocalValue} =
    NotificationsStorage
    && NotificationsStorage.lastCheck
    && NotificationsStorage.lastCheck > today
    ? [now, NotificationsStorage.lastCheck]
    : [today, today];

 localStorage.setItem('NotificationsStorage', JSON.stringify({ lastCheck: newStoredValue }));
 this.lastCheck = newLocalValue;


SQL delivery query performance I need a "little" help with an SQL query (MySQL).

I have the following tables:

COURIERS table:

+------------+
| COURIER_ID |
+------------+

DELIVERIES table:

+-------------+------------+------------+
| DELIVERY_ID | COURIER_ID | START_DATE |
+-------------+------------+------------+

ORDERS table:

+----------+-------------+-------------+
| ORDER_ID | DELIVERY_ID | FINISH_DATE |
+----------+-------------+-------------+

COORDINATES table:

+-------------+-----+-----+------+
| DELIVERY_ID | LAT | LNG | DATE |
+-------------+-----+-----+------+

In the real database I have more columns in each table, but for this example the above columns are enough.

What do I need?

An SQL query that returns all couriers [COURIER_ID], their last
delivery [DELIVERY_ID] (based on last START_DATE), the
delivery's last coordinate [LAT and LNG] (based on last DATE) and the remaining orders count (total of orders of the last delivery that have no FINISH_DATE).
A courier can have no deliveries, in this case I want DELIVERY_ID =
NULL, LAT = NULL and LNG = NULL in the result.
A delivery can have no coordinates, in this case I want LAT = NULL
and LNG = NULL in the result.

What was I able to do?

SELECT c.`COURIER_ID`,
       d.`DELIVERY_ID`,
       r.`LAT`,
       r.`LNG`,
  (SELECT COUNT(DISTINCT `ORDER_ID`)
   FROM `ORDERS`
   WHERE `DELIVERY_ID` = d.`DELIVERY_ID`
     AND `FINISH_DATE` IS NULL) AS REMAINING_ORDERS

FROM `COURIERS` AS c
LEFT JOIN `DELIVERIES` AS d USING (`COURIER_ID`)
LEFT JOIN `COORDINATES` AS r ON r.`DELIVERY_ID` = d.`DELIVERY_ID`

WHERE (CASE WHEN
         (SELECT MAX(`START_DATE`)
          FROM `DELIVERIES`
          WHERE `COURIER_ID` = c.`COURIER_ID`) IS NULL THEN d.`START_DATE` IS NULL ELSE d.`START_DATE` =
         (SELECT MAX(`START_DATE`)
          FROM `DELIVERIES`
          WHERE `COURIER_ID` = c.`COURIER_ID`) END)
  AND (CASE WHEN
         (SELECT MAX(`DATE`)
          FROM `COORDINATES`
          WHERE `DELIVERY_ID` = d.`DELIVERY_ID`) IS NULL THEN r.`DATE` IS NULL ELSE r.`DATE` =
         (SELECT MAX(`DATE`)
          FROM `COORDINATES`
          WHERE `DELIVERY_ID` = d.`DELIVERY_ID`) END)
GROUP BY c.`COURIER_ID`
ORDER BY d.`START_DATE` DESC

The problem is that this query is very slow (from 5 to 20 seconds) when I have over 5k COORDINATES and it does not returns all couriers sometimes.

Distinct

In a properly designed database, this DISTINCT should not be needed:

  (SELECT COUNT(DISTINCT `ORDER_ID`)
   FROM `ORDERS`

If multiple different orders can have the same ORDER_ID, we're gonna have a bad time.

Aliases

c, d, r... these are bad table aliases. Why? Because Mr. Maintainer has to go through your entire query to know what those mean, as they are not self-evident. Your table names are pretty short, but if you really need to shorten them further... perhaps something like crier, deliv, coord would be better.

Join syntax

This USING command:

FROM `COURIERS` AS c
LEFT JOIN `DELIVERIES` AS d USING (`COURIER_ID`)

USING is not standard SQL syntax, when it comes to joins. Sure, it can be a nice shorthand in MySQL, but generally it is preferred to use standard SQL syntax (usually more verbose) instead of depending on syntactic sugar provided by a particular build or version of a language. Like this:

FROM `COURIERS` AS c
LEFT JOIN `DELIVERIES` AS d
ON c.`COURIER_ID` = d.`COURIER_ID`

Performance

It's a bit difficult to assess performance hiccups if not presented with the execution plan, or a sample dataset to reproduce the issue. If I had to guess, I would say you have too many subqueries in your CASE statements.

CASE statements are great and very fast when you use constants to compare; but when you use variable values, such as what you are doing... well... it's pretty slow. You're asking the SQL engine to run each subquery for each record essentially. It may find a way to optimize that's halfway efficient, but I believe you would be better using a set-based approach. Example:

WHERE (CASE WHEN
         (SELECT MAX(`START_DATE`)
          FROM `DELIVERIES`
          WHERE `COURIER_ID` = c.`COURIER_ID`) IS NULL THEN d.`START_DATE` IS NULL ELSE -- etc.

Instead:

-- this goes before your CASE statement
INSERT INTO TEMP TABLE DeliveryDates
    SELECT IFNULL(
        MAX( d.`START_DATE`, NULL )
    )
WHERE d.`COURIER_ID` = c.`COURIER_ID`

Then:

WHERE (CASE WHEN
         (SELECT `START_DATE`
            FROM DeliveryDates) IS NULL THEN d.`START_DATE` IS NULL
        ELSE d.`START_DATE`


Loading dictionary words into a trie I have here a program created for pset5 of the CS50 course. The program compiles correctly and does as it should. However, is there any way to improve the run time of this program? Are there any pieces of code that are redundant and can be omitted? And is there anything that can be improved on in general?

/*
 * Implements a dictionary's functionality.
 */

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

#include "dictionary.h"

typedef struct trie
{
    bool word;
    struct trie* children[27];
}trie;

trie* root;

unsigned int wordCount;

// Function that frees a node from the heap.
void freenode(trie* node)
{
    for (int i = 0; i < 27; i++)
    {
        if (node->children[i] != NULL)
        {
            freenode(node->children[i]);
        }
    }

    free(node);
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    int n = strlen(word);

    trie* node = root;

    for (int i=0; i < n; i++)
    {
        char c = tolower(word[i]);

        if (c == '\'')
        {
            // ASCII a (97) + 26
            c = 123;
        }

        struct trie* current = node->children[c-97];

        if (current == NULL)
        {
            return false;
        }
        else
        {
            node = current;
        }
    }

    if (node->word == true)
    {
        return true;
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // Open the dictionary file
    FILE* d = fopen(dictionary, "r");
    if (d == NULL)
    {
        return false;
    }

    root = calloc(1, sizeof(trie));

    trie* node = root;

    for (char c = tolower(fgetc(d)); c != EOF; c = fgetc(d))
    {
        if (c == '\n')
        {
            if (node != root)
            {
                wordCount++;

                node->word = true;

                node = root;
            }
        }
        else
        {
            if (c == '\'')
            {
                c = 123;
            }

            struct trie* current = node->children[c-97];
            if (current == NULL)
            {
                node->children[c-97] = calloc(1, sizeof(trie));

                node = node->children[c-97];
            }
            else
            {
                node = current;
            }

        }
    }

    fclose(d);

    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return wordCount;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    freenode(root);
    return true;
}

If you feel you need a comment like this:

    // ASCII a (97) + 26
    c = 123;

it means that the code is not clear. Consider

    c = 'a' + 26;

While we can figure out the significance of 26 (size of an English alphabet, right?) again it is better to be explicit. What you want is the first character beyond the [a-z] range, so:

    c = 'z' + 1;

Similarly, node->children[c-97] should be node->children[c-'a'].
The

    if (node->word == true) {
        return true;
    }

    return false;

is a long way to say

    return node->word;

Avoid globals. Make load return root (or NULL on failure), and pass root to check as a parameter.
Test what calloc returns.
root = calloc(1, sizeof(trie)); requires the knowledge that root is trie *, and therefore results a double maintenance. A preferred idiom is

root = calloc(1, sizeof(*root));

Branching factor of 27 adds a huge overhead. Most nodes will use just a few pointers, so most of the allocated memory is wasted. This in turn results in poor cache utilization, and may directly affect the performance. Consider allocating just as much as you need, and searching instead of indexing. It may or may not improve performance. Profile and compare.


Python Fizz Buzz, Acceptance Unit test OK, maybe crazy overkill and a little silly, but why not? Here's a Python FizzBuzz Acceptance Test:

import unittest
from fizzbuzzmodule import fizzbuzz

class FizzBuzzAcceptanceTestCase(unittest.TestCase):
    '''
    Test that fizzbuzz(int) returns int
    unless multiple of 3 (then returns 'fizz')
           multiple of 5 (then returns 'buzz')
           multiple of both (then returns 'fizzbuzz')
    '''
    def test_business_as_usual(self):
        '''
        test that an integer >= 0 not evenly divisible
        by three or five returns the same
        '''
        self.assertEqual(fizzbuzz(1), 1)
        self.assertEqual(fizzbuzz(2), 2)
        self.assertEqual(fizzbuzz(4), 4)
        self.assertEqual(fizzbuzz(7), 7)
        self.assertEqual(fizzbuzz(998), 998)
    def test_fizz(self):
        '''evenly divisible by 3 returns fizz'''
        self.assertEqual(fizzbuzz(3), 'fizz')
        self.assertEqual(fizzbuzz(6), 'fizz')
        self.assertEqual(fizzbuzz(111), 'fizz')
        self.assertEqual(fizzbuzz(999), 'fizz')
    def test_buzz(self):
        '''evenly divisible by 5 returns buzz'''
        self.assertEqual(fizzbuzz(5), 'buzz')
        self.assertEqual(fizzbuzz(10), 'buzz')
        self.assertEqual(fizzbuzz(20), 'buzz')
        self.assertEqual(fizzbuzz(500), 'buzz')
    def test_fizz_buzz(self):
        '''evenly divisible by 3 and 5 returns fizzbuzz'''
        self.assertEqual(fizzbuzz(15), 'fizzbuzz')
        self.assertEqual(fizzbuzz(30), 'fizzbuzz')
        self.assertEqual(fizzbuzz(45), 'fizzbuzz')
        self.assertEqual(fizzbuzz(600), 'fizzbuzz')

    # def test_zero(self):
        # self.assertEqual(fizzbuzz(0), 'fizzbuzz') #??????

def main():
    unittest.main()

if __name__ == '__main__':
    main()

Typed up a little implementation that passes these tests:

def fizzbuzz(number):
    '''
    if number divisible by 3 return 'fizz';
    5, 'buzz'; both, fizzbuzz
    else return number
    '''
    if not number % 3:
        if not number % 5:
            return 'fizzbuzz'
        else:
            return 'fizz'
    if not number % 5:
        return 'buzz'
    return number

def main():
    for i in range(1, 101):
        print fizzbuzz(i)

And when I run the tests:

>>> unittest.main()
....
----------------------------------------------------------------------
Ran 4 tests in 0.002s

OK

And my question is, how would you augment the above? Would you find it useful to run this test on someone's code? Does it clearly define a clean API? Would it be preferable to return a consistent type instead of strings or ints?

Should I have done this differently? Have I not considered any edge or corner cases?

For something so simple, it might be less overkill to use the doctest module.  Write the expected calls and outputs in the docstring, then run python -m doctest -v fizzbuzzmodule.py.  There's no need to write a separate class.

I've written one of the tests to ensure that the function also works when called with decreasing arguments.

As for the function itself, I believe that the code reads better if you write number % 3 == 0 instead of not number % 3.  I would also use a conditional expression, but that's just a matter of personal preference.

def fizzbuzz(number):
    '''
    if number divisible by 3 return 'fizz';
    5, 'buzz'; both, fizzbuzz
    else return number

    >>> fizzbuzz(1)
    1
    >>> fizzbuzz(2)
    2
    >>> fizzbuzz(3)
    'fizz'
    >>> fizzbuzz(4)
    4
    >>> fizzbuzz(5)
    'buzz'
    >>> fizzbuzz(15)
    'fizzbuzz'
    >>> [fizzbuzz(i) for i in range(31, 20, -1)]
    [31, 'fizzbuzz', 29, 28, 'fizz', 26, 'buzz', 'fizz', 23, 22, 'fizz']
    '''
    if number % 3 == 0:
        return 'fizzbuzz' if (number % 5 == 0) else 'fizz'
    if number % 5 == 0:
        return 'buzz'
    return number


Sequence-based enumeration of permutations with Heap's algorithm Heap's algorithm
is an algorithm to generate all permutations of a given array. It

  ... generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed.

Here is my attempt to implement this algorithm in Swift 4 as a Sequence,
so that all permutations of an array can be enumerated with for .. in
loops and related techniques:

/*
 * A sequence of all permutations of a given array. Based on the
 * non-recursive version of Heap's algorithm as described in
 * https://en.wikipedia.org/wiki/Heap%27s_algorithm
 */

struct HeapPermutationSequence<Element>: Sequence, IteratorProtocol {

    private var current: [Element]
    private var c: [Int]
    private var i = 0
    private var firstIteration = true

    init(elements: [Element]) {
        self.current = elements
        self.c = Array(repeating: 0, count: elements.count)
    }

    mutating func next() -> [Element]? {
        if firstIteration {
            firstIteration = false
        } else {
            while i < c.count {
                if c[i] < i {
                    if i % 2 == 0 {
                        current.swapAt(0, i)
                    } else {
                        current.swapAt(c[i], i)
                    }
                    c[i] += 1
                    i = 0
                    break
                } else {
                    c[i] = 0
                    i += 1
                }
            }
        }
        return i < c.count ? current : nil
    }
}

Example usage:

for p in HeapPermutationSequence(elements: [1, 2, 3]) {
    print(p, terminator: ", ")
}
print()

// Output:
// [1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1],

Several techniques from @Hamish's answer Sequence-based enumeration of permutations in lexicographic order could be
applied here as well to improve the performance:

Avoid the cost of copy-on-write by not mutating the current
array after it is returned as the next element.
Have a single exit point in the next() method.

Benchmark:

let N = 10
var count = 0
let start = Date()
for _ in HeapPermutationSequence(elements: Array(1...N)) { count += 1 }
let end = Date()
print(count, end.timeIntervalSince(start))

which takes about 0.03 seconds (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode).

All feedback is welcome, such as (but of course not restricted to):

Performance improvements.
Better variable names (c and i are simply copied from the Wikipedia
pseudo-code).
Simplifying the code, or making it better readable/understandable.

I've been able to slash the execution time by almost half on my machine by declaring current and c as ContiguousArray:

struct HeapPermutationSequence<Element>: Sequence, IteratorProtocol {

    private var current: ContiguousArray<Element>
    private var c: ContiguousArray<Int>
    private var i = 0
    private var firstIteration = true

    init(elements: [Element]) {
        self.current = ContiguousArray(elements)
        self.c = ContiguousArray<Int>(repeating: 0, count: elements.count)
    }

    mutating func next() -> ContiguousArray<Element>? {
        ...
    }
}

Benchmarks

Using the same benchmarking code, compiled with -O in the terminal, on a  2.7 GHz i7 MacBook Pro :

Before: fluctuates between 0.126s and 0.139s
After:  0.07s with inferior fluctuations, thanks to current being a ContiguousArray, since such a type has predictable performance.

I've got to 0.022s by wrapping the benchmarking code in a do statement or any new scope (Makes the code 3x faster):

do {
    let N = 10
    var count = 0
    let start = mach_absolute_time()
    for _ in HeapPermutationSequence(elements: Array(1...N)) { count += 1 }
    let end = mach_absolute_time()
    print(count, Double(end - start)/Double(1e9))
}

 Putting the original code inside a single iteration for loop for _ in 0..<1 {...} brings its execution time down to 0.020 too. Putting it inside a do statement, repeat while false, closure, while true { ... break}..., takes it back to 0.13s .

N.B: The above result has only been observed on a mac (4 physical cores, 4 logical ones). On an iPhone and an iPad (both 2 physical cores), using a ContiguousArray makes the code a full second faster (2.~s vs 3.~s).

We can gain 1 to 2ms by rearranging the conditions:

private var notFirstIteration: Bool = false
//...
if notFirstIteration {
//...
} else {
    notFirstIteration = true
}

This would eliminate The (N! - 1) unnecessary conditional jumps in the assembly code.

As suggested by Mr. Martin: Not discarding manually the output of HeapPermutationSequence by using this code:

for x in HeapPermutationSequence(elements: Array(1...N)) {
    count += x.count
}

Gives a +/-2ms fluctuation in both solutions.


SQL to find users that the current user hasn't liked/disliked I have this really long query, which in my opinion looks ugly next to all the tidy code in my project. I was wondering if there was a way to optimize it or make it shorter at least:

$query = <<<SQL
    SELECT * FROM users
    WHERE NOT EXISTS (
        SELECT id
        FROM profile_likes
        WHERE profile_id = users.id
        AND viewer_id = $my_user->id
    )
    AND NOT EXISTS (
        SELECT id
        FROM profile_dislikes
        WHERE profile_id = users.id
        AND viewer_id = $my_user->id
    )
    AND id != $my_user->id
SQL

This query is a part of an user filter which has the purpose of filtering the users to only those that the currently logged in user ($my_user) hasn't liked/disliked yet.

Personally, I would just stick with what you have already got.

You could try something like this, although too me it doesn't look any tidier.
You would need to profile it against your database, to see if it performs any better.

SELECT *
FROM users
left outer join profile_likes on profile_likes.profile_id = users.id AND profile_likes.viewer_id = $my_user->id
left outer join profile_dislikes on profile_dislikes.profile_id = users.id AND profile_dislikes.viewer_id = $my_user->id
where users.id <> $my_user->id
having profile_likes.profile_id is null and profile_dislikes.profile_id is null


Implementing ShowDialog() style functionality without disabling any other windows I need a simple prompt window to ask the user to do something with an OK/Cancel return. But I also need all Windows to remain functional, so a xx.ShowDialog isn't appropriate.

This is my attempt. DialogWindow takes a Delegate in the constructor and calls it when OK or Cancel is clicked with a True/False parameter respectively. The Window is coded to take top Z priority.

It seems to work but I'm not very knowledgeable on await usage. Is there an easier way?

        bool result;
        ManualResetEvent manualReset = new ManualResetEvent(false);
        DialogWindow myDialog = new DialogWindow((dialogResult) =>
        {
            result = dialogResult;
            manualReset.Set();
        });
        myDialog.Show();
        await Task.Factory.StartNew(() =>
        {
            manualReset.WaitOne();
        });
        //Do something with result

Using ManualResetEvent this way means that you're blocking a thread unnecessarily while the dialog is shown. Instead, you should use TaskCompletionSource, which allows you to create a Task that completes when you want it to.

Encapsulated into a method, the code could look something like this:

public static Task<bool> ShowAsync()
{
    var tcs = new TaskCompletionSource<bool>();
    var dialog = new DialogWindow(tcs.SetResult);
    dialog.Show();
    return tcs.Task;
}


Simplifying working Caesar cipher I'm learning Python 3 at the moment, so to test the skills I've learned, I am trying the puzzles at Python Challenge.

I've created some code to solve the 2nd puzzle here. it works, but I think that the way I've done it is very convoluted.  Any suggestions on how to solve the puzzle in a simpler way?

(The code basically needs to substitute each letter in a message to the letter 2 spaces to the right of it, such as E->G.)

import string
alphabet = string.ascii_lowercase
letter=0
replaceLetter = 2
times=1
message = input()
newMessage=''
while times < 26:
    newMessage = message.replace(alphabet[letter], str(replaceLetter)+',')
    message = newMessage
    letter = letter + 1
    replaceLetter = replaceLetter + 1
    time = times + 1
    if letter == 26:
        times = 0
        break
newMessage = message.replace('26'+',', 'a')
message = newMessage
newMessage = message.replace('27'+',', 'b')
message = newMessage
number = 25
message = newMessage
while times < 26:
    newMessage = message.replace(str(number)+',', str(alphabet[number]))
    message = newMessage
    letter = letter + 1
    number = number - 1
    time = times + 1
    if number == -1:
        times = 0
        break
print(newMessage)

I would define a shift function that shifted the letters like so:

from string import whitespace, punctuation

def shift(c, shift_by = 2):
    if c in whitespace + punctuation: return c

    upper_ord, lower_ord, c_ord = ord('A'), ord('a'), ord(c)
    c_rel = (c_ord - lower_ord) if c_ord >= lower_ord else (c_ord - upper_ord)
    offset = lower_ord if c_ord >= lower_ord else upper_ord
    return chr(offset + (c_rel + shift_by) % 26)

Then, to translate a message:

msg = 'a quick brown fox jumped over the lazy dog'
encoded_msg = ''.join(shift(l) for l in msg)

Alternatively, combine Mark Tolonen's maketrans suggestion with g.d.d's deque suggestion to get:

import string
from collections import deque

alphabet = string.ascii_lowercase
alphabet_deque = deque(alphabet)
alphabet_deque.rotate(-2)
rotated_alphabet = ''.join(alphabet_deque)
tbl = string.maketrans(alphabet, rotated_alphabet)

Then, later in the code:

msg = 'a quick brown fox jumped over the lazy dog'
encoded_msg = string.translate(msg, tbl)

This second method only works for lowercase letters, but you can always create two separate translation tables -- one for uppercase letters and another for lowercase letters -- to account for case.

Offtopic note: sometimes I wish Python had Smalltalk-like cascaded message sends. Ah well, one can dream.


First OOP TicTacToe game This is my first program using classes. How could this be improved?

#include <iostream>

class TicTacToe
{
    char m_field[3][3];
    char sign;
public:
    char Sign(char x) {sign=x;};
    void MakeField();
    void DrawField();
    bool IsFree(int y, int x);
    bool FindAndReplace(int x,int y);
    bool Row();
    bool Column();
    bool Diagonal();
    bool Win();
    bool IsFull();
    TicTacToe(){MakeField();DrawField();}
};

void TicTacToe::MakeField()
    {
        for (int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                m_field[i][j]=' ';
    }

void TicTacToe::DrawField()
    {
        std::cout << " ";
        for(int i = 0; i < 3; i++)
            std::cout << " " << i;

        std::cout << "\n  - - -\n";
        for(int i = 0; i < 3; i++)
        {
            std::cout << i;
            for(int j = 0; j < 3; j++)
            {
                std::cout << "|" << m_field[i][j];
            }
            std::cout << "|\n  - - -\n";
        }
    }

bool TicTacToe::IsFree(int y, int x)
    {
        if(m_field[y][x]==' ')
            return true;
        return false;
    }

bool TicTacToe::FindAndReplace(int x,int y)
    {
        if(IsFree(y,x))
        {
            m_field[y][x]=sign;
            return true;
        }
        return false;
    }

bool TicTacToe::Row()
    {
        for (int i = 0; i < 3; i++)
            if(!IsFree(i,0)&&!IsFree(i,1)&&!IsFree(i,2))
            if(m_field[i][0]==m_field[i][1]&&m_field[i][0]==m_field[i][2])
                return true;
        return false;
    }

bool TicTacToe::Column()
    {
        for (int i = 0; i < 3; i++)
            if(!IsFree(0,i)&&!IsFree(1,i)&&!IsFree(2,i))
            if(m_field[0][i]==m_field[1][i]&&m_field[0][i]==m_field[2][i])
                return true;
        return false;
    }

bool TicTacToe::Diagonal()
    {
        if(!IsFree(1,1))
        {
            if(m_field[2][0]==m_field[1][1]&&m_field[1][1]==m_field[0][2])
                return true;
                if(m_field[0][0]==m_field[1][1]&&m_field[0][0]==m_field[2][2])
                return true;
        }
        return false;
    }

bool TicTacToe::Win()
    {
        return Row()||Column()||Diagonal();
    }

bool TicTacToe::IsFull()
    {
        for (int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(IsFree(i,j))
                    return false;
        return true;
    }

int main()
{
    int x,y,i=0;
    char sign;
    TicTacToe field;
    while(!field.IsFull())
    {
        i++;
        sign=i%2==0?'o':'x';
        std::cout << "Turn " << sign << ": Get x cordinate:";
        std::cin >> x;
        std::cout << "Get y cordinate:";
        std::cin >> y;
        if(x>2||y>2)
        {
            std::cout << "this coordinates does not exist! Try again\n";
            i--;
            continue;
        }

        field.Sign(sign);
        if(field.FindAndReplace(x,y))
            field.DrawField();
        else
        {
            std::cout << "is full!";
            i--;
        }
        if(field.Win())
        {
            std::cout << "Winned sign " << sign;
            break;
        }
    }
    std::cout << "\nEnd!\n";
    return 0;
}

Some comments on naming and coding style.

First, it is a bit unusual for member function names to be in PascalCase in C++. camelCase or snake_case are more usual, reserving identifiers that start with an uppercase letter for type names.

char sign;
char Sign(char x) {sign=x;};
field.Sign(sign);

This isn't clear to me at all (could be a language issue though). What is this "sign" thing? Positive/negative? Does the Sign method do a cryptographic signature? What does Sign do to a sign?

I'd go with player, and rename TicTacToe::Sign to SetPlayer/SetCurrentPlayer to make it clear it's setting something.

Or get rid of that entirely and pass the current player's symbol to the methods that need it: there's only one. This lets the TicTacToe class to only manage the board, and leaves managing players to your future gameplay controller class ('cos stuffing all that in main isn't the best idea).

void MakeField();

The field is already "made", but not initialized. Something like InitializeField or ClearBoard would be sound more appropriate to me (though that's really minor).

void DrawField();           // good
bool IsFree(int y, int x);  // great

bool FindAndReplace(int x,int y);

This method doesn't find anything. It sets a cell to a value if it's free. And wait a sec, didn't we just see another method that takes coordinates?

bool IsFree        (int y, int x);  // oh?
bool FindAndReplace(int x, int y);  // what?

Why do you pass in the coordinates in different order? Please don't do that, it is very, very error prone. Stick to one order, and make that x, y consistently.

bool Row();
bool Column();
bool Diagonal();

These names don't tell me anything about what the functions do. I'd expect them to somehow return are row, column or diagonal, but bool doesn't work for any of this. Plus they operate on all rows, columns and diagonals (plural).

I'd rename all that to CheckRows() etc., and make them private - users aren't supposed to call these directly. Then fix the indentation, especially since you're not using {} in your ifs - your current layout is misleading.

bool Win();

IsGameWon()?

bool IsFull();

IsGameTied()?

TicTacToe(){MakeField();DrawField();}

The constructor initializes the field - that's good, but then it prints it immediately. This might not be what the caller wants, and the caller doesn't have a choice. I'd remove the DrawField() call, and add some whitespace.

TicTacToe() { MakeField(); }

Now in main, this should be in a separate function that does just that, i.e. get valid input from the player.

    std::cout << "Turn " << sign << ": Get x cordinate:";
    std::cin >> x;
    std::cout << "Get y cordinate:";
    std::cin >> y;
    if(x>2||y>2)
    {
        std::cout << "this coordinates does not exist! Try again\n";
        i--;
        continue;
    }

The i--; continue; is not very intuitive, and you're likely to get something wrong if you ever update the code and add something in between the top of the loop and the continue statement.

I personally don't like this form:

    if(field.FindAndReplace(x,y))
        field.DrawField();
    else
    {
        std::cout << "is full!";
        i--;
    }

I'd {} both sides, and only omit the braces only if both sides are single, simple statements. Most importantly be consistent - your Row, Col and Diagonal methods aren't (for the for).

As for spacing:

    sign=i%2==0?'o':'x';

This is unreadable for me (slightly better if I put my glasses on, but still hard to parse). More spaces, at least:

    sign = i%2==0 ? 'o' : 'x';

And I'd personally add a pair of parens and even more spaces, but I tend to like parens more than most I think.

    sign = (i % 2 == 0) ? 'o' : 'x';

Same applies for most of your assignments and comparisons, they could do with more spaces (and perhaps more parens), e.g.

if (!IsFree(0, i) && !IsFree(1, i) && !IsFree(2, i))
if ((m_field[0][i] == m_field[1][i]) && (m_field[0][i] == m_field[2][i]))
m_field[y][x] = sign;

Finally:

bool TicTacToe::Something()
    {
    }

but:

int main()
{
}

That's unusual. I'd stick to one style only - the class/struct name already informs the reader that it's a member function, so I see no reason for a different style between toplevel and member functions. (I'd pick the style you chose for main, less wasted horizontal space.)

A couple suggestions for the code itself.

This one is (I believe) non controversial:

bool TicTacToe::IsFree(int y, int x)
{
  // no need for an 'if', you have a boolean result already
  return m_field[y][x] == ' ';
}

This is a bit trickier but makes your row and column check a bit easier to read:

bool TicTacToe::CheckRows()
{
  for (int i = 0; i < 3; i++) {
    if (IsFree(i, 0)) // if the first cell is free, no need to look further
      continue;
    if ((m_field[i][0] == m_field[i][1]) && (m_field[i][0] == m_field[i][2]))
      return true; // and if it isn't the other two must match to win
  }
  return false;
}

This is a matter of taste - getting the "easy" cases out of the way as soon as possible generally results in less nesting depths for the main part of the function. (Here, not much gained.)

bool TicTacToe::SetIfFree(int x, int y)
{
  if (!IsFree(y, x))
    return false;

  m_field[y][x] = sign;
  return true;
}


Bash script to check available name in Github I just wrote this script to check if the name (that has 2 characters: 1 alphabet and 1 number) in Github is available or not so I can accompany this name.

Here is my script:

#!/bin/bash

for i in {a..z}
do
  echo 'running ...'
  for j in {0..9}
  do
    out=$(curl -s -o /dev/null -w "%{http_code}" "https://github.com/$i$j") &
    if [[ $out =~ .*4.* ]]
    then
      echo "$i$j is available"
    else
      echo "$i$j is not available"
    fi
  done
  echo 'finish batch ...'
  wait
done

Let me explain:

I use 2 loops to generate all permutation of 2  characters.
I use curl to check status of the the host. For example:

curl -s -o /dev/null -w "%{http_code}" "https://github.com/google"

it will return the status of the host, in case the username exist it will return 200 else it will return 404

Then I compare the status code with any 4xx error:

$out =~ .*4.*

If the status is 4xx then the user name is available so I can get it.
Currently, it is running 10 background jobs at the same time by using curl with &.

As you can see I have found j3 and m6, n5, u6, y4, y6, y9 are available.

Could you please help me to review this script.

The code is nice and short, and it is easy to read.

I'm surprised that it works at all. Sending the out=$(…) command to the background sounds as if the code might continue before curl had the chance to fill the output. Do you get the same results without the &? I'd expect that more names are reported as available then.

As long as the & is in the program, I would verify the results manually.

I also don't see the point of running the requests in parallel. It's only 10 * 26 requests, which are answered anyway within 5 minutes.

Update: The Shell Command Language specification says:

  If a command is terminated by the control operator  ( '&' ), the shell shall execute the command asynchronously in a subshell.

This means that the variable assignment cannot affect the out variable at all. This in turn means that the output you posted does not correspond to the code you posted. Please check again.

If you can reproduce the behavior, please write down all details that might influence it. I tried to reproduce it, and I got exactly the result I expect after reading the specification: all names are not available.


Converting a Website Into a Single Page App I want to convert my website into a single page app. This function does the trick:

$(document).ready(function(){
    $("body").delegate("a", "click", function(){
        var href = $(this).attr("href");
            $.get(href,function(data){
            var newDoc = document.open("text/html", "replace");
            newDoc.write(data);
            newDoc.close();
        });
        return false;
    });
});

Assuming I have no redirects other than <a> tags, it should work fine, right? It feels so wrong and yet so right...

It will work, but consider why you might be doing SPA's:

No more full screen flickering, better user experience
Keep your state on the browser side instead of pingponging it between server & browser
Less network traffic if you only request for data & do the rendering with templates in JS

With your approach,

You are rebuilding the whole DOM from scratch everytime, so there will still be flickering.
With script tags being replaced while JS is still running, I dont even want to think about what mess your state will be in ;)
You are still fetching data + layout from the server, so not gaining anything from a network perspective.

Furthermore, you run the risk of memory leaks, which happen like this:

Add any listener to your DOM
Forget to unbind that listener when the user clicks a link
New content is loaded, old DOM is gone, but that old listener is still out there


Optimizing simple xHTML parser I'm writing a simple xHTML parser which parses a data without nested tags.

Example input code will look like:

Header

 atsatat

asdsaad</2>
s32532235

I've wrote the following code:

#include <node.h>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>

using namespace v8;

enum Tags {
    Closing = 0,
    Paragraph,
    Heading
};

int tagDetect(char *ptr){
    if (*ptr == '/') {
        return Tags::Closing;
    }

    if (*ptr == 'p') {
        return Tags::Paragraph;
    }

    if (*(ptr + 1) == '2' || *(ptr + 1) == '3')
        return Tags::Heading;

    return -1;
}

Handle<Value> Callback(const Arguments& args) {
    HandleScope scope;

    if (!args[0]->IsString() || !args[1]->IsFunction()) {
        return ThrowException(Exception::TypeError(
            String::New("Invalid arguments! First parameter must be [string], second must be a callback [function].")));
    }

    Local<Function> callback = Local<Function>::Cast(args[1]);
    String::Utf8Value param1(args[0]->ToString());
    std::string input = std::string(*param1);

    static Persistent<String> data_symbol = NODE_PSYMBOL("data");
    static Persistent<String> tag_symbol = NODE_PSYMBOL("tag");

    std::string::size_type pos = 0, closePos = 0;

    int openPos;
    int tagID, lastTag, id = 0, lastAppended = 0, clearStartPos;

    Local<Array> nodes = Array::New();
    Local<Object> node_obj;

    while ((pos = input.find('<', pos)) != std::string::npos) {
        pos++;
        switch (tagID = tagDetect(&input[pos])) {
        case Tags::Closing:
            tagID = tagDetect(&input[pos + 1]);
            if (tagID == lastTag && (pos - openPos > 10 || lastTag != Tags::Paragraph)) {
                /* Concat tags */
                if (lastAppended == lastTag) {
                    if (lastTag == Tags::Heading) { /* Dont concat heading tags */
                        continue;
                    }

                    node_obj = nodes->Get(id - 1)->ToObject();
                    node_obj->Set(data_symbol, String::Concat(node_obj->Get(data_symbol)->ToString(), String::New(input.substr(openPos + (lastTag > 1 ? 3 : 2), pos - openPos - (lastTag > 1 ? 3 : 2) - 1).c_str())));
                    continue;
                }

                node_obj = Object::New();
                node_obj->Set(data_symbol, String::New(input.substr(openPos + (lastTag > 1 ? 3 : 2), pos - openPos - (lastTag > 1 ? 3 : 2) - 1).c_str()));
                node_obj->Set(tag_symbol, Integer::New(lastTag));
                nodes->Set(id, node_obj);
                id++;
                lastAppended = lastTag;
                continue;
            }

            /* Clear useless tags */
            input.erase(pos - 1, input.find('>', pos - 1) - pos + 2);
            break;
        case Tags::Paragraph:
        case Tags::Heading:
            openPos = pos;
            lastTag = tagID;
            break;
        default:

            /* Clear useless tags */
            input.erase(pos - 1, input.find('>', pos - 1) - pos + 2);
            break;
        }
    }

    /* Remove last element from array if its heading */

    if (lastTag == Tags::Heading) {
        nodes->Delete(id - 1);
    }

    const unsigned argc = 2;
    Local<Value> argv[argc] = {
        Local<Value>::New(Null()),
        nodes
    };

    callback->Call(Context::GetCurrent()->Global(), argc, argv);

    return Undefined();
}

void RegisterModule(Handle<Object> target) {
    target->Set(String::NewSymbol("parse"),
        FunctionTemplate::New(Callback)->GetFunction());
}

NODE_MODULE(smartparser, RegisterModule);

I'm using this as Native NodeJS module. Since I'm really new in the C++ world, any tips on how to optimize/improve my code will be greatly appreciated.

Although optional, you can keep your #includes organized (alphabetically, for instance) so that it's easier to locate an individual one or to determine if you've already included a particular one.
You've included <sstream>, but I don't see any use of stringstreams.  If you're not utilizing this library, then remove it.
Avoid using namespace X in global scope as it will expose it to the entire program or file, which can break code in cases such as name-clashing (using the same name for something in which something doesn't belong to the namespace).  It could also make it difficult for readers to tell what is part of a particular namespace (I cannot tell what belongs to v8, so I'm having a bit more trouble reviewing this).  If you insist on keeping a using, then keep it local, such as in a function.
For this enum:

enum Tags {
    Closing = 0,
    Paragraph,
    Heading
};

You don't need to explicitly set it to 0.  This is already the default starting value for enums.
You don't need a char* here:

int tagDetect(char *ptr){

Looking at the calling code, you're passing in an std::string.  You should just pass this object by itself.  Also, because it's not being modified, pass it by const& to avoid a needless copy and any accidental modification:

int tagDetect(std::string const& str){

In C++ in general, you should avoid passing raw pointers to functions as you cannot keep track of ownership with them (C++11 smart pointers helps with that for when points are necessary).  But in this case, you shouldn't need to deal with pointers.

With this change, you will need to modify the function code (I'll use different names for clarity):

This is accessing the first character:

if (*ptr == 'p')

so use front():

if (str.front() == 'p')

This is accessing the second one:

*(ptr + 1)

so you can use indices to make it more clear (while they are technically the same thing; yours is doing pointer arithmetic):

str[1]

I'd keep these on separate lines for readability:

int tagID, lastTag, id = 0, lastAppended = 0, clearStartPos;

They aren't entirely related to each other, and there could be some maintenance issues since some are declared and the others initialized.

int tagID;
int lastTag;
int id = 0;
int lastAppended = 0;
int clearStartPos;

You should also have these declared/initialized as close to their scope as possible.  This will help determine if any variable is no longer used (keeping around unused variables will clutter the code).  But if you cannot put them any closer, then do have each one on separate lines.


`Static inheritance` pattern I have an abstract class Entity in my code, which requires a reference to an instance of EntityData to operate. (EntityData provides basic information about the type of the entity).
In the design of my program, every type of entity would have its own class that extends Entity, and thus would have to provide EntityData that would describe and be shared between all of the instances of that that entity class.
EntityData itself is an immutable class that is built like a multiton (similar to Java's enum). It has a private constructor, and its instances are revealed as readonly static fields.

An example of how EntityData would look:

sealed class EntityData
{
    public static readonly EntityData Table = new EntityData(250, 60);
    public static readonly EntityData Chair = new EntityData(120, 25);

    public readonly int Cost;
    public readonly int Weight;

    private EntityData(int cost, int weight)
    {
        Weight = weight;
        Cost = cost;
    }
}

I can think of two simple ways to deal with this, but I am uncertain which one I should go with.

First one is to add a reaodnly field to Entity and request is via the constructor, so Entity would look like this:

abstract class Entity
{
    private readonly EntityData data;

    protected Entity(EntityData data)
    {
        this.data = data;
    }
}

While an extending class, Table for example, would look like this:

sealed class Table: Entity
{
    public Table() : base(EntityData.Table) {}
}

The second option would be to add an abstract, protected property (getter only) to Entity. In this case Entity would look like this:

abstract class Entity
{
    protected abstract EntityData Data { get; }
}

While the extending class Table would look like this:

sealed class Table : Entity
{
    protected override EntityData Data
    {
        get { return EntityData.Table; }
    }
}

Thus internally, Entity would simply use the property instead of a field.

The performance differences are probably in the realm of micro-optimization, but I would still like to take them into consideration.

The first way obviously increases the size of any Entity object.
The first way also forces all the extending types to define their constructors and call the base constructor or will simply increase the number of parameters in the already existent constructor.

The second way doesn't increase the size of objects, and (to me) look shorter and slightly more concise.
Performance-wise however, benchmarking showed that a virtual method call is much slower than accessing a field.
It is also less obvious that such a property is a dependency of Entity, something the first way makes perfectly clear.

As there's no clear-cut answer here, I would simply love to have a few opinions on the matter, and which of the two ways you find 'better'.
Thanks in advance.

(Please no responses about how this is in the realm of micro optimization and thus I shouldn't waste my time with it. I simply find this interesting.)

I think I personally like the set by constructor method in general.  I think it provides a means by which you can better allow for TDD and also implicitly implies the contract all inheriting classes must obey in providing a Entity object if they wish to inherit from the base class.

I think if I were going make Entity a requirement of the second method I would make the protected method abstract which would also enforce this constraint.  However that doesn't allow for the easy of use in using dependency injection which I think would suit this approach nicely.

I'm not sure why there would be a huge increase in the size of the Entity object itself.  I would assume the size increase would only be as large as the size of the memory register holding the location of the Entity object itself.  As for performance, I can't comment explicitly but I would assume you would still need to make visible the EntityData object to it's children so you would probably do that via a property accessor or method anyway so performance impacts to me would be low on the priority list unless profiling the code suggested otherwise.

So assuming the Entity is required in inherited classes I would consider something like:

abstract class Entity
{
    protected EntityData Data { get; private set; }

    protected Entity(EntityData data)
    {
        this.Data = data;
    }
}


unique username generator I have written a class to generate a unique username from the full name. The full name is the name of a company usually containing 4 to 5 words. The username generated will be of format {preffix}{username}{suffix}. The user name should not be derived from stop words. stops words are generated analysing the most common words in the list of companies name.

To generate name I am taking the first letter from each word of name and taking remaining from the last word. For eg. if the length of the username is 5 then ABC Company Limited will be converted to ACLIM.

kindly review the code.

class UniqueNameGenerator:

    def __init__(self, stop_words, suffix, prefix):

        self.stop_words = stop_words
        self.suffix = suffix
        self.prefix = prefix

    def split_full_name_and_filter_stop_word(self, full_name, size):

        name_words = " ".join(full_name.split(" ")).split()

        if len(name_words) > size:
            name_words = name_words[:size]
        words_considered = []
        for word in name_words:
            ignore_word = False
            if word.lower() in self.stop_words:
                ignore_word = True
            if not ignore_word:
                words_considered.append(word)
        return words_considered

    @staticmethod
    def get_name_from_list_of_words(size, list_of_words):

        size_counter = 1
        len_words_considered = len(list_of_words)
        letters_left = size
        username = ""
        while size_counter <= len_words_considered:
            current_word = list_of_words[size_counter - 1]
            if size_counter == len_words_considered:
                if len(current_word) >= letters_left:
                    username += current_word[:letters_left]
                else:
                    username += current_word
            else:
                username += current_word[0]
                letters_left -= 1
            size_counter += 1
        return username

    def check_and_update_username_to_unique(self, username, unique_name_list):

        while True:
            s = len(username)
            if username in unique_name_list:
                char_list = list(username)
                char_list[random.randint(0, s)] = random.choices(
                    string.ascii_uppercase + string.digits
                )[0]
                username = "".join(char_list)
            else:
                return username

    def generate_username(self, full_name, size, unique_name_list=None):

        if not unique_name_list:
            unique_name_list = []

        full_name = re.sub("[^\sa-zA-Z]+", "", full_name)
        words_considered = self.split_full_name_and_filter_stop_word(full_name, size)
        username = self.get_name_from_list_of_words(size, words_considered)
        if self.suffix:
            username = username + self.suffix
        if self.prefix:
            username = self.prefix + username
        username = self.check_and_update_username_to_unique(username, unique_name_list)
        return username

Areas to fix/improve:

Namings

The function names like split_full_name_and_filter_stop_word, check_and_update_username_to_unique and alike are considered as anti-patterns for function naming.
run_and_fly or think_or_talk like names point to ambiguity or excessive responsibilities assigned to a function.A function should have a concrete responsibility. Therefore, you need to analyze those functions and apply whether Rename function or Extract function (in your case - split a function into several functions each with separate responsibility) technique.

Some variable and function names are too verbose:
name_words --> just names
get_name_from_list_of_words --> just compose_username
list_of_words --> just a plural words
unique_name_list --> just unique_names

def generate_username(self, full_name, size, unique_name_list=None) method.

to avoid passing the same unique_name_list across multiple methods - it's good to pass it into UniqueNameGenerator constructor at once.
full_name = re.sub("[^\sa-zA-Z]+", "", full_name). In case if full_name happened to be empty, to avoid redundant calls of subsequent functions - it's good to add a check for that:

...
full_name = re.sub("[^\sa-z]+", "", full_name.strip(), re.I)
if not full_name:
    raise ValueError(f'Incorrect full name `{full_name}`')

either of these complements:

if self.suffix:
    username = username + self.suffix
if self.prefix:
    username = self.prefix + username

can throw TypeError in case if caller would pass non-string argument for prefix or suffix.Instead, use flexible f-string formatting:

username = f'{self.prefix}{username}{self.suffix}'

def split_full_name_and_filter_stop_word(self, full_name, size) method

the function name is better named as filter_valid_words or select_valid_words (or alike)
" ".join(full_name.split(" ")).split() - this looks like a "5-wheel bicycle that circles rounds instead of going straight".Simply words = full_name.split()
the whole construction:

words_considered = []
for word in name_words:
    ignore_word = False
    if word.lower() in self.stop_words:
        ignore_word = True
    if not ignore_word:
        words_considered.append(word)

is a verbose "invention" of a simple list comprehension with if constraint:

valid_words = [w for w in words if w.lower() not in self.stop_words]

The restructured function would look as:

def filter_valid_words(self, full_name, size):
    words = full_name.split()
    if len(words) > size:
        words = words[:size]

    return [w for w in words if w.lower() not in self.stop_words]


Simplifying many-indents-code I have the following code, written in Python:

if id:
    fields = r.table(cls._tablename)
              .get(id)
              .run(cls.connection())
else:
    try:
        fields = list(r.table(cls._tablename)
                       .filter(**kwargs)
                       .limit(1)
                       .run(cls.connection()))[0]
    except IndexError:
        fields = None

The code acts as a wrapper for getting a document from a RethinkDB datastore. I find all those indents unaesthetic, and I cannot seem to find a way to wrap the lines to look nicer.

So, is there a way I can rewrite (or maybe just rewrap) this code to look better and provide the same functionality?

Your indentations strike me as reasonable.  In any case, in functions you can often use return statements to help avoid indentation ...

def get_fields(id):
    if id:
        fields = ...
        return fields

    try:
        fields = ...
    except:
        fields = ...

    return fields


Doubly circular link list implementation I am supposed to be creating a doubly circular linked list, but I am now have problems creating the actual linked list. Is there a problem with the classes? Also, for the assignment, the list is suppose to be a template class, but now I just want to get the code to work.

#include <iostream>
#include <string>
#include <iomanip>
#include <stdio.h>

using namespace std;
//template <class Object>

//template <class Object>
class Node
{
    //friend ostream& operator<<(ostream& os, const Node&c);
public:
    Node( int d=0);
    void print(){
        cout<<this->data<<endl;
    }
//private:
    Node* next;
    Node* prev;
    int data;

    friend class LinkList;
};
Node::Node(int d):data(d)
{

}

//template <class Object>
class LinkList
{
void create();
public:
    //LinkList();
    LinkList():head(NULL),tail(NULL),current(NULL)
    {create();}
    int base;
    //LinkList(const LinkList & rhs, const LinkList & lhs);
    ~LinkList(){delete current;}

    const Node& front() const;//element at current
    const Node& back() const;//element following current
    void move();
    void insert (const Node & a);//add after current
    void remove (const Node &a);
    void print();
private:
    Node* current;//current
    Node* head;
    Node* tail;
};

void LinkList::print()
{
    Node *nodePt =head->next;
    while(nodePt != head)
    {
        cout<<"print function"<<endl;
        cout<<nodePt->data<<endl;
        nodePt=nodePt->next;
    }
}
//element at current

void LinkList::create()
{
    current = head = tail = new Node(0);
    current->next = current->prev = current;
}

const Node& LinkList::back()const
{
    return *current;
}
//element after current
const Node& LinkList::front() const
{
    return *current ->next;
}

void LinkList::move()
{
    current = current ->next;
}
//insert after current
void LinkList :: insert(const Node& a)
{
    Node* newNode= new Node();
    newNode->prev=current;
    newNode->next=current->next;
    newNode->prev->next=newNode;
    newNode->next->prev=newNode;
    current=newNode;
}
void LinkList::remove(const Node& a)
{
    Node* oldNode;
    oldNode=current;
    oldNode->prev->next=oldNode->next;
    oldNode->next->prev=oldNode->prev;
    delete oldNode;
}

//main file
#include <iostream>
#include <string>
#include <iomanip>
#include <stdio.h>
#include "LinkedList.h"

using namespace std;

int main()
{
    int n;
    cout<<"How many Nodes would you like to create"<<endl;
    cin>>n;

    LinkList list1 ;

    list1.print();
    for(int loop = 0;loop < n;++loop)
    {
        list1.insert(loop);
    }
    list1.print();
}

You have done the correct thing by putting a sentinel element into the list.
This makes adding/removing and generally manipulating the list trivial because you don't need to handle NULL links in the list.

But you have done it using a two phase create.

You have to construct your list.
You have to call create to initialize it.

This is a very bad idea. Your object should be fully constructed at the end of the constructor. That way users can not incorrectly initialize your class.

There is also a bug in your create. You create a node but you don;t link it to anything:

void LinkList::create()
{
   Node start(0);  // This node is destroyed at the end of the function.
}

What you should be doing is:

LinkedList::LinkedList()
    : current(new Node(0, NULL, NULL))
    // , head(current)      You don't actually need head/tail
    // , tail(current)      since it is circular these are beside each other.
{
    current->prev = current;
    cureent->next = current;
}

Also your code can delete the sentinel and thus cause all sorts of problems. You should not allow the deletion of the sentinel and your other functions should check for a list with just a sentinel in them (this is the empty list).

Why are you giving back references to the Node? This is an internal implementation detail. Return a reference to the value (or throw an exception if the list is empty). By returning a node you are binding your self to use a specific implementation (take a leaf out of the standard library and just return a reference to the value).

const Node& LinkList::back()const

Same comment again:

const Node& LinkList::front() const

Not sure I have seen this functionality in a list before. It seems to allow you to move the head around inside the list.

void LinkList::move()

So this is why you have to return the node above?

void LinkList :: insert(const Node& a)

I would rather have insert_front/insert_back/insert_at functionality.

Remove has some issues:

void LinkList::remove(const Node& a)

Two problems:

You don't update current (so it points at the deleted node).
You allow the sentinel to be deleted.
If you delete the last node the easy insertion/deletion breaks down.

This is what I would do:

class LL
{
   struct Node {
       int value;
       Node* next;
       Node* prev;
       Node() // Sentinel
         : next(this)
         , prev(this)
       {}
       Node(int val, Node* prev, Node* next)
          : value(val)
          , next(next)
          , prev(prev)
       {
           prev->next = this;
           next->prev = this;
       }
       ~Node()
       {
           prev->next = next;
           next->prev = prev;
       }
    };
    Node* current;
    LL()
        : current(new Node)
    {}
    ~LL()
    {
        while(!empty())
        {
           delete current->next;
        }
        delete current;
    }
    bool empty() const { return current == current->next;}
    void insert_front()
    {
         new Node(current, current->next);
    }
    void insert_back()
    {
         new Node(current->prev, current);
    }
    void delete_front()
    {
         if (!empty())
             delete current->next;
    }
    void delete_back()
    {
         if (!empty())
             delete current->prev;
    }
    int& front()
    {
        if (empty()) {throw empty_exception();}
        return current->next->value;
    }
    int& back()
    {
        if (empty()) {throw empty_exception();}
        return current->prev->value;
    }
};


Largest Palindrome Product - Project Euler #4 This is my code for Project Euler Problem #4
The question:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

My code:

function problem4(){
    let product = 1;
    let largest = 1;
    for(let i = 100; i<1000; i++){
        for(let j = i; j<1000; j++){
            product = i*j;
            if(("" + product) == ("" + product).split("").reverse().join("")){
                largest = Math.max(largest, product);}
}
    }
    return largest;
}
console.log(problem4());

At present, it takes 311.5649999999732 ms for execution, but I think it can be better. So how can I make it more efficient and faster?

How about this small modification that could potentially make it faster if the answer is large enough.

function problem4(){
    let product = 1;
    let largest = 1;
    for(let i = 999; i>=100; i--){
        for(let j = 999; j>=i && i*j>largest; j--){
            product = i*j;
            if(("" + product) == ("" + product).split("").reverse().join("")){
                largest = Math.max(largest, product);}
}
    }
    return largest;
}
console.log(problem4());


Git delete all merged in local branches I have written a shell script utility for deleting all merged local branches.

#!/usr/bin/env bash

# Remove references to remote branches that no longer exist.
git remote prune origin
# Create a file containing list of all merged branches.
git branch --merged > 5db3bb3c-718a-444c-b1ce-d90a5a0d1cb3.clc

nano 5db3bb3c-718a-444c-b1ce-d90a5a0d1cb3.clc
# Trim trailing and leading whitespace etc.
sed 's/^[ \t]*//;s/[ \t]*$//' < 5db3bb3c-718a-444c-b1ce-d90a5a0d1cb3.clc
# Soft delete all branches left in the file and then remove tmp file.
xargs git branch -d < 5db3bb3c-718a-444c-b1ce-d90a5a0d1cb3.clc
rm 5db3bb3c-718a-444c-b1ce-d90a5a0d1cb3.clc

Although I wrote this only for personal use, I will likely create a repository for it on my github account and I am not particularly familiar with shell script best practices.

(Edit: The script eventually ended up on github here)

Improve your file handling:

Don't use a hard coded file name for temporary files.
Don't spew temporary files into the current directory.
Make sure you clean up temporary files even on error.

The first two can be addressed by leveraging mktemp. The last can be addressed with a trap.

branchesfile=$(mktemp)
trap "{ rm -f $branchesfile; }" EXIT

You should also honor the user's choice of default editor, rather than require nano. You can get the user's editor preference with git var GIT_EDITOR:

$(git var GIT_EDITOR) $branchesfile

Git tools typically honor the exit code of the editor. If the editor exited with error, this should stop the script:

if [ $? -ne 0 ]; then
    exit 1
fi

This allows the user to cancel the operation if they spot a problem they don't want to fix at the moment.

Putting this all together:

#!/usr/bin/env bash
branchesfile=$(mktemp)
trap "{ rm -f $branchesfile; }" EXIT

# Remove references to remote branches that no longer exist.
git remote prune origin
# Create a file containing list of all merged branches.
git branch --merged > $branchesfile

$(git var GIT_EDITOR) $branchesfile
if [ $? -ne 0 ]; then
    exit 1
fi

# Trim trailing and leading whitespace etc.
sed 's/^[ \t]*//;s/[ \t]*$//' < $branchesfile
# Soft delete all branches left in the file and then remove tmp file.
xargs git branch -d < $branchesfile

There's one other issue: your script will try to keep going if any other commands error out. set -e is one option to solve this, but there are caveats to using it. If you choose to use set -e, you'll need to revise the exit code checking of the editor, since bash will exit before it gets to the if.


Partition a linked list arround an element This is my code to partition a list into two parts according to a value. I.e. nodes smaller than value x should precede nodes larger than the value x.
It seems correct. Any corner cases I am overseeing or corrections are highly appreciated.

public Node partition(Node head, int x){
   if(head == null) return head;
   Node prev = null;
   Node current = head;
   while(current != null){
       if(current.data > x || current == head){
           prev = current;
           current = current.next;
       }
       else{
           Node next = current.next;
           current.next = head;
           if(prev != null) {
              prev.next = next;
           }
           head = current;
           current = next;
      }
   }
   return head;
}

I just have a point on naming of your function. You named it partition but you're just rearranging the elements and returning the head pointer! If you want to partition, you may want to return pointers to heads of partitions (the head you already return and another pointer to start of bigger than x partition), this way someone using your function doesn't need to iterate over linked-list to find start of next partition, and this pointer can be easily recorded in if statement in your while loop.


Sum of Multiples of 3 or 5 up to 1000 Question:

  Find the sum of multiples of 3 or 5 up to 1000

I have come up with this solution that is bit more generic than the first 1000 per se:

let multiplesSum = n => {

  let sum = 0

  for (let i = 0; i < n; i++) {
    if (i % 3 === 0 || i % 5 === 0) {
      sum += i
    }
  }
  return sum
}

Instead of pushing everything to an array use a variable and sum the numbers as they are looping.

Implementation
Your implementation is clean, robust and easy to understand. I suggest only small changes:

Declare multiplesSum as const to prevent accidental rebinding / overriding later on.
multiplesSum(n) should compute the sum of multiples of 3 or 5 up to and including n. Sum formulas are usually following this convention.
I prefer terminating statements with semicolons instead of relying on JavaScript's automatic semicolon insertion.

Algorithm
Your algorithm is simple and easy to understand, but comes with a linear runtime complexity of O(n).
An algorithm with constant runtime complexity O(1) exists. Here are some pointers in case you are stuck:

Given a positive integer n, how often do 3 or 5 fit into n? Division and Math.floor give the answer.
Arithmetic sequences such as 3 + 6 + 9 + ... have simple, explicit sum formulas.
By adding (3 + 6 + 9 + ...) + (5 + 10 + 15 + ...), you count some numbers twice, so you need to find and subtract those.


Print a space separated list in Python I am trying to solve the common "print a character after every item in a list, except the last one" problem.
I do not want to use list indexes. There are a couple of simple ways to do this in Python, but I am not sure how to apply them to my code.
Is there a more readable/couple liner way to do this?
def echo(*args):
    for data in args:
        if data is args[-1]:
            ender = ''
        else:
            ender = ' '

        if isinstance(data, six.string_types) \
                    or isinstance(data, six.integer_types):

            print_(data, end=ender)
        else:
            op = getattr(data, '__str__', None)
            if op:
                print_(data.__str__(), end=ender)
            else:
                LOG.error("echo called with an unsupported data type")
    print_('')

Note: Code works in both Python 2 and Python 3.

I might be misreading your code, but it looks like all you want is:

def echo(*args):
    six.print_(*args, sep=" ", end="")

For something a bit more manual:

def echo(*args):
    six.print_(" ".join(map(str, args)), end="")

In terms of reviewing your actual code, on top of the issues Morwenn raises, note that:

op = getattr(data, '__str__', None)
if op:

simplifies to:

if hasattr(data, '__str__'):

However, it is rare to call magic methods directly in Python; normally you'd just do str(data) and let Python call __str__. This is safer, as although an old-style class may not implement __str__, you can still get e.g. '<foo.bar object at 0x...>' via str(...).

I would include the filtering as a separate function:

def valid(arg):
    """Include a docstring to explain your filtering rules."""
    if (isinstance(data, (six.string_types, six.integer_types)) or
        hasattr(data, '__str__')):
        return True
    LOG.error("echo called with an unsupported data type")
    return False

Then echo can use filter:

def echo(*args):
    six.print_(*filter(valid, args), sep=" ", end="")


Performance/Optimization of Knapsack(ish) algorithm for move generation for a game I'm writing an AI for an italian Card game scopa http://en.wikipedia.org/wiki/Scopa And as part of it i need to generate all moves available to the user.

A move consists of finding cards in the centerboard that sum to a card in the players hand.

For example if I have a 5 in my hand and the center contains a [5,4,3,2,1,2] the possible moves would be:

pick up the 5 with my five

pick up the 4 and 1 with my five

pick up one of the twos and the three with my five

pick up the other tow and the three with my five

pick up both 2s and the 1 with my five

After profiling my code it shows that this is by far the most expensive part of the program (about 95 percent of execution time being spent here)

Can you see any way to optimize these methods?

this one actually generates all the possible moves.

private void generateMoves(Card myCard,ArrayList<Card> CurrentMove,
              ArrayList<Card> centerCards,ArrayList<Move> moves, int moveSum) {
    if(moveSum>myCard.value)
    {
        return;
    }
    else if(moveSum == myCard.value)
    {
        Move m = new Move(myCard, new ArrayList<>(CurrentMove));
        rateMove(m);
        moves.add(m);
        return;
    }

    for (Card card :centerCards) {
        if(!card.selected)
        {
            CurrentMove.add(card);
            card.selected = true;
            moveSum += card.value;
            generateMoves(myCard, CurrentMove, centerCards, moves, moveSum);
            moveSum -= card.value;
            CurrentMove.remove(card);
            card.selected = false;
        }
    }
}

this one removes any duplicates (the code above would return 4,1 and 1,4 as different moves from the example) I know its hacky but i couldn't think of anything that would be faster. Ideally they would be combined and duplicates would never be returned but i couldn't get it to work.

 protected void removeDuplicates(ArrayList<Move> moves)
{
    ArrayList<Move> temp = new ArrayList<>(moves);

    for(Move move : temp)
    {
        while(moves.remove(move));
        moves.add(move);
    }
}

Any suggestions would be appreciated.

In your recursive generateMoves method, you can reduce a huge amount of the duplicates by limiting where in the centerCards list you operate in.

My suggestion would be to pass that list through the recursion with a pointer to your current position in the array.... for example:

generateMoves(Card myCard,ArrayList<Card> CurrentMove,
          ArrayList<Card> centerCards, int centercardpos,
          ArrayList<Move> moves, int moveSum)

Then, in your method you can change the loop:

for (Card card :centerCards) { ...

to be:

for (int ci = centercardpos; ci < centerCards.size(); ci++) {
    Card card = centerCards.get(i);

        generateMoves(myCard, CurrentMove, centerCards,
               centercardpos + 1, // new increased limit.....
               moves, moveSum);

This will substantially reduce the number of possible moves (and still get the right answers). Reducing the values you gnerate will also substantially reduce duplicates, which in turn will also improve th pwerformance of removeDuplicates ...

The only time removeDuplicates will have effect is when you have something like (using your example: [5,4,3,2,1,2] ) the moves [5,2] and [5,2] (but the 'other' 2).


Creating a fast Android dictionary (word counts) This is a follow-up of my question here:

I am currently working on an application for various statistics. One task is to analyse a good amount of sentences for their word counts.

The specifications are:

sentences are read from SQLiteDatabase (up to 20k with an average of about 15 words)
transformation: split by whitespaces (to get the words of the sentences)
transformation: toLowerCase (to minimize variations of words)
transformation: replace [^a-zA-Z] (for the same reason as above)
get word + count for the first x (not sure yet, maybe 10-15) most common words
preserve a flag if the messages was sent/received

What I'm looking for:

improvements to make the code run faster
alternative approaches for this task
(general hints to improve the task)

Current version with the suggested improvements made

//fields

private static final CharMatcher pat_rep = CharMatcher.inRange('A', 'Z').or(CharMatcher.inRange('a', 'z'))
        .precomputed();
private static final Pattern pat_split = Pattern.compile("\\s");
private HashMultiset<String> sent = HashMultiset.create();
private HashMultiset<String> rcvd = HashMultiset.create();
private Cursor c1;
private Cursor c2;

//start

    c1 = db.rawQuery("select lower(DATA) as SENTENCE, SENT from MESSAGELIST", null);
    while (c1.moveToNext()) {
        String[] words = pat_split.split(c1.getString(c1.getColumnIndex("SENTENCE")));
        int from_me = c1.getInt(c1.getColumnIndex("key_from_me"));
        for (String in : words) {
            in = pat_rep.retainFrom(in);
            if (!in.equals("")) {
                if (from_me == 1) {
                    sent.add(in);
                } else {
                    rcvd.add(in);
                }
            }
        }
    }

    db.execSQL("create temp table if not exists WORDS (WORD varchar, SENT integer, CNT integer)");
    SQLiteStatement ins = db.compileStatement("insert into WORDS values (?, ?, ?)");
    db.beginTransaction();

    Iterator<Entry<String>> i = sent.entrySet().iterator();
    Entry<String> e = null;
    while (i.hasNext()) {
        e = i.next();
        ins.bindString(1, e.getElement());
        ins.bindLong(2, 1);
        ins.bindLong(3, e.getCount());
        ins.executeInsert();
    }
    i = rcvd.entrySet().iterator();
    while (i.hasNext()) {
        e = i.next();
        ins.bindString(1, e.getElement());
        ins.bindLong(2, 0);
        ins.bindLong(3, e.getCount());
        ins.executeInsert();
    }
    db.setTransactionSuccessful();
    db.endTransaction();

    c1 = db.rawQuery("select WORD, CNT from WORDS where SENT=0 group by WORD order by CNT desc limit 10", null);
    c2 = db.rawQuery("select WORD, CNT from WORDS where SENT=1 group by WORD order by CNT desc limit 10", null);

Just some ideas.

Maybe you could use batching?

You may be also able to save some time by iterating over sent.entrySet() instead of looking up the count separately.

Split on [^a-zA-Z] as you later throw non-letter away anyway.

Can't you use JDK5 loops like

for (String in : send) {...}

? I guess, clearBindings is unnecessary as you always overwrite everything.

Make all fields private. Always (unless you have a very good reason not to). AT least I hope that pat_rep etc. are fields.

Split your method. Shorter methods are easier to read and to optimize.


Linking to an image asset from a JavaScript file in Symfony 2 I am calling a JS file from a bundle directory like so:

<script src="{{ asset('bundles/macppages/js/main.js') }}"></script>

which loads the JS file into the base.index.twig

In that JS file I want to add some custom css via jQuery like this:

function loadBkrndImg(){
    var img = new Image();
        img.src = "/bundles/macppages/images/bkrnd.0" + currentBkrndImgNum + ".jpg";
        $('body').css("background-image","url('" + img.src + "')");
}

which works, but to the question:

Is this the correct way to do it using the Symfony 2 framework?  In Symfony 1, there was a function you could call to pull the web dir. With Sym2, the assets are in the bundle directories, so is there a Symfony2 command for this so it is not so explicit?

There might be a better way to retrieve the web directory, I would not know. However, there are other things to ponder upon.

Naming : loadBkrndImg -> loadBackgroundImage looks so much better
Naming : currentBkrndImgNum, enough said..
The background image number ought to be a parameter to loadBackgroundImage, not a global
You are creating an Image() object, assign the src value ( which can trigger the loading of the image ) , and then throw away the image. You could just put the url in a string.
You could preemptively centralize the retrieval of the asset folder

I would counter-suggest the following :

function getAssetFolder( subfolder )
{
  var folder = '/bundles/macppages/';
  return subFolder ? ( folder + subfolder + "/" ) : folder
}

function loadBackgroundImage( number )
{
  var url = getAssetFolder( 'images' ) + 'bkrnd.0' + number + '.jpg';
  $('body').css("background-image","url('" + url + "')");
}


Cache-optimized matrix multiplication algorithm in C I am trying to optimize matrix multiplication on a single processor by optimizing cache use. I am implemented a block multiplication and used some loop unrolling, but I'm at a loss on how to optimize further though it is clearly still not very optimal based on the benchmarks.

Matrices are in column major order.

Any suggestions would be appreciated!

const int blockSize = 12;

void readBlock(double outputMatrix[], double inputMatrix[], int beginX, int endX, int beginY, int endY, int n) {

        int i = 0;
        for (int x = beginX; x < endX; x++) {
                for (int y = beginY; y < endY; y++) {
                        outputMatrix[i] = inputMatrix[x*n + y];
                        i++;
                }
                for (int y = endY-beginY; y < blockSize; y++) {
                        outputMatrix[i] = 0;
                        i++;
                }

        }

        for (int x = endX - beginX; x < blockSize; x++) {
                for (int y = 0; y < blockSize; y++) {
                        outputMatrix[i] = 0;
                        i++;
                }

        }

}

int min(int a, int b) {
        if (a < b) return a;
        else return b;

}

void multiplyMatrices(double inputMatrix1[], double inputMatrix2[], double outputMatrix[], int endx, int endy) {
        for (int i = 0; i < endx; i++) {
                for (int j = 0; j < endy; j++) {
                        double cvalue = outputMatrix[i*blockSize + j];
                        for (int l = 0; l < blockSize; l+=2) {
                                double a1 = inputMatrix1[l*blockSize + j] * inputMatrix2[i*blockSize + l];;
                                double a2 = inputMatrix1[(l+1)*blockSize + j] * inputMatrix2[i*blockSize + l + 1];
                                cvalue += a1 + a2;

                        }
                        outputMatrix[i*blockSize + j] = cvalue;
                }
        }

}

void writeMatrix(double* inputMatrix, double* outputMatrix, int beginX, int endX, int beginY, int endY, int n) {
        int k,l=0;
        for (int i = beginX; i < endX; i++) {
                k = 0;
                for (int j = beginY; j < endY; j++) {
                        outputMatrix[i*n + j] = inputMatrix[l*blockSize+k];
                        k++;
                }
                l++;
        }

}

void square_dgemm(int n, double* A, double* B, double* C) {

        for (int x = 0; x < n; x += blockSize) {
                for (int y = 0; y < n; y += blockSize) {
                        double CC[blockSize*blockSize];

                        readBlock(CC, C, x, min(x + blockSize, n), y, min(y + blockSize, n), n);

                        for (int z = 0; z < n; z += blockSize) {
                                double BC[blockSize*blockSize];
                                double AC[blockSize*blockSize];
                                int zAdj = min(z + blockSize, n);
                                readBlock(AC, A, z, zAdj,y, min(y+blockSize, n), n);

                                readBlock(BC, B, x, min(x + blockSize, n), z,zAdj, n);

                                multiplyMatrices(AC, BC, CC, min(x+blockSize,n)-x,min(y+blockSize,n)-y);

                        }
                        writeMatrix(CC, C, x, min(x + blockSize, n), y, min(y + blockSize, n), n);

                }

        }
}

The block size shouldn't be 12 (more like 1 to 2 orders of magnitude bigger), but I don't know exactly what it should be and it's easier to try some values and see how they work out than trying to predict it.. Likely the blocks shouldn't be square either (and therefore, not all three the same shape), because the eventual kernel will "prefer" a certain direction over the other.

There are inherent inefficiencies in multiplyMatrices due to its "shape" and we can calculate in advance what shape it should have. The Intel(R) Xeon(R) E5-2695 v3 has the Haswell micro-architecture, which has these key properties:

Vector FMA per cycle: 2
Vector FMA latency: 5
Vector loads per cycle: 2
Vector size: 256bit (4 doubles)

This means that, in order to max out the amount of arithmetic that happens, we will need at least 2*5=10 (the throughput-latency product) independent vector accumulators. Unrolling by 2 was a good start, but not close to what is required. Just unrolling more would be easy but there is more to it.

The limited number of loads, only a 1:1 ratio with FMAs at most (otherwise it starts to eat into the arithmetic throughput), means that we must somehow re-use data within a single iteration of the inner loop. Having two loads for each FMA (loading elements from each matrix) is twice the budget, that's definitely out.

So the inner loop itself needs to have a somewhat rectangular footprint to enable data re-use, and that rectangle needs to have an area of at least 10 4-wide vectors. For example it could be 2x5, 5x2, 3x4, 4x3.. that's about it. It can't really be bigger, then we would run out of registers, and spilling accumulators is super out. 3x5 seems like it could be possible, but it does not only require 15 accumulators but also some extra registers to hold the values from the input matrixes and it won't fit. By the way an other way to view the "rectangular footprint" is unrolling the outer two loops. The above sizes are all in numbers of vectors, so in a scalar view one of the directions gets 4 times as big again.

As an example (consider this mainly clarificational as in "how to put all of the above abstract-sounding considerations together into code" and not so much "copy&paste code") I'll pick 5x2 (20x2 scalars). That means the main part of the code would look something like this:

#include <x86intrin.h>

// must be multiple of 20
#define BLOCK_H 120

// must be multiple of 2
#define BLOCK_W 128

// this is the number of columns of mat1 and the number of rows of mat2
// has no relation to the size of the result block
// can be whatever
#define BLOCK_K 128

void matmulBlock(double *result, double *mat1, double *mat2) {
    size_t i, j, k;
    __m256d sum0, sum1, sum2, sum3, sum4;
    __m256d sum5, sum6, sum7, sum8, sum9;
    __m256d tmp0, tmp1, tmp2, tmp3, tmp4;
    __m256d m1, m2;
    size_t N = BLOCK_H;
    for (i = 0; i < BLOCK_W; i += 2) {
        for (j = 0; j < BLOCK_H; j += 20) {
            sum0 = _mm256_load_pd(&result[i * N + j]);
            sum1 = _mm256_load_pd(&result[i * N + j + 4]);
            sum2 = _mm256_load_pd(&result[i * N + j + 8]);
            sum3 = _mm256_load_pd(&result[i * N + j + 12]);
            sum4 = _mm256_load_pd(&result[i * N + j + 16]);

            sum5 = _mm256_load_pd(&result[i * N + j + N]);
            sum6 = _mm256_load_pd(&result[i * N + j + N + 4]);
            sum7 = _mm256_load_pd(&result[i * N + j + N + 8]);
            sum8 = _mm256_load_pd(&result[i * N + j + N + 12]);
            sum9 = _mm256_load_pd(&result[i * N + j + N + 16]);

            for (k = 0; k < BLOCK_K; k++) {
                m1 = _mm256_set1_pd(mat2[i * N + k]);
                m2 = _mm256_set1_pd(mat2[i * N + k + N]);

                tmp0 = _mm256_load_pd(&mat1[k * N + j]);
                tmp1 = _mm256_load_pd(&mat1[k * N + j + 4]);
                tmp2 = _mm256_load_pd(&mat1[k * N + j + 8]);
                tmp3 = _mm256_load_pd(&mat1[k * N + j + 12]);
                tmp4 = _mm256_load_pd(&mat1[k * N + j + 16]);

                sum0 = _mm256_fmadd_pd(m1, tmp0, sum0);
                sum1 = _mm256_fmadd_pd(m1, tmp1, sum1);
                sum2 = _mm256_fmadd_pd(m1, tmp2, sum2);
                sum3 = _mm256_fmadd_pd(m1, tmp3, sum3);
                sum4 = _mm256_fmadd_pd(m1, tmp4, sum4);

                sum5 = _mm256_fmadd_pd(m2, tmp0, sum5);
                sum6 = _mm256_fmadd_pd(m2, tmp1, sum6);
                sum7 = _mm256_fmadd_pd(m2, tmp2, sum7);
                sum8 = _mm256_fmadd_pd(m2, tmp3, sum8);
                sum9 = _mm256_fmadd_pd(m2, tmp4, sum9);
            }

            _mm256_store_pd(&result[i * N + j], sum0);
            _mm256_store_pd(&result[i * N + j + 4], sum1);
            _mm256_store_pd(&result[i * N + j + 8], sum2);
            _mm256_store_pd(&result[i * N + j + 12], sum3);
            _mm256_store_pd(&result[i * N + j + 16], sum4);

            _mm256_store_pd(&result[i * N + j + N], sum5);
            _mm256_store_pd(&result[i * N + j + N + 4], sum6);
            _mm256_store_pd(&result[i * N + j + N + 8], sum7);
            _mm256_store_pd(&result[i * N + j + N + 12], sum8);
            _mm256_store_pd(&result[i * N + j + N + 16], sum9);
        }
    }
}

By the way I didn't test this, I converted it from code that is tested, but it was single precision and row-major and some miscellaneous differences, I may have made some errors in changing it just now. Even if its works, this is ultimately not the most efficient code, this is just step 1: writing code to fit the basic parameters of the machine - it's not optimized beyond that.

Some assumptions are made: result and mat1 both 32-aligned, and zero padding in empty areas (same block size always).

GCC 4.8.5 needs -mfma to compile this but cannot take -march=haswell yet.