Numeric expression parser - calculator In particular, if someone could describe a better way to go from the tokenized list to the Expression tree, it would be super helpful.  I would like to get rid of the casting in the parser but am not sure how.

Full code here

package org.bws.calc;

import java.util.ArrayList;

import org.bws.calc.exception.ParseException;
import org.bws.calc.expression.Expression;
import org.bws.calc.expression.ValueExpression;
import org.bws.calc.tokens.OpToken;
import org.bws.calc.tokens.Token;

public class SimpleParser implements Parsable{

    public Expression parse(ArrayList<Token> tokens){
        if(tokens.size() == 1){
            Token t = tokens.get(0);
            try{
                int intVal = Integer.parseInt(t.getValue());
                return new ValueExpression(intVal);
            }catch(NumberFormatException nfe){
                throw new ParseException("expected int but found: "+t.getValue());
            }
        }

        Expression left;
        Expression right;

        int index=0;
        Token firstToken = tokens.get(index++);

        if("(".equals(firstToken.getValue())){
            int openParens =1;
            while(openParens > 0 ){
                if(index>tokens.size()-1){throw new ParseException("Missing right Parenthesis");}
                Token token = tokens.get(index);
                if("(".equals(token.getValue())){ ++openParens;}
                if(")".equals(token.getValue())){ --openParens;}
                ++index;
            }
            if(index == tokens.size()){
                return parse(new ArrayList<Token>(tokens.subList(1, index-1) ) );
            }
            left = parse(new ArrayList<Token>(tokens.subList(1,index-1)));

        }else{
            int tokenVal = Integer.parseInt(firstToken.getValue());
             left = new ValueExpression(tokenVal);
        }

        Token op = tokens.get(index);
        if(! (op instanceof OpToken) ){
            throw new ParseException("Invalid Syntax. expected Operator but found:"+op);
        }
        OpToken opToken = (OpToken) op;
        ++index;

        Token firstRightToken = tokens.get(index++);
        if("(".equals(firstRightToken.getValue() ) ){
            right = parse(new ArrayList<Token>(tokens.subList(index,tokens.size()-1)));
        }else{
            int tokenVal = Integer.parseInt(firstRightToken.getValue());
            right = new ValueExpression(tokenVal);
        }

        return opToken.toExpression(left, right);
    }
}

Before I begin, let me say, it looks like a well engineered project.  You've separated the work into a tokenizer, parser, and calculator, which is excellent.  The unit tests were helpful as well.  Congratulations.

Before you begin to write a parser, you should define the grammar, which you should state as a long comment in your parser's JavaDoc.  From my interpretation of your code, I see the following productions:

EXPRESSION = BINARY_EXPRESSION |
             TERM

BINARY_EXPRESSION = EXPRESSION BINARY_OPERATOR TERM

BINARY_OPERATOR = "+" | "-"

TERM = VALUE_EXPRESSION |
       PARENTHESIZED_EXPRESSION

VALUE_EXPRESSION = number

PARENTHESIZED_EXPRESSION = "(" EXPRESSION ")"

You don't support unary minus (negative numbers).  That's OK; we'll keep it simple for now.

It would be a good idea to add the following unit test:

@Test
public void evaluateThreeOperatorWithNoParens(){
        int result = c.evaluate("5-2+1");
        Assert.assertEquals(4,result);
}

If you had defined the grammar carelessly, such as the following…

EXPRESSION = VALUE_EXPRESSION |
             BINARY_EXPRESSION |
             PARENTHESIZED_EXPRESSION

VALUE_EXPRESSION = number

BINARY_EXPRESSION = EXPRESSION BINARY_OPERATOR EXPRESSION

BINARY_OPERATOR = "+" | "-"

PARENTHESIZED_EXPRESSION = "(" EXPRESSION ")"

… then it would be ambiguous whether "5-2+1" should be interpreted as (5-2)+1 or 5-(2+1).  The evaluateThreeOperatorWithNoParens() test enforces the former interpretation.

The main problem is your handling of parentheses.  Scanning the entire token list in advance to check for matching parentheses is inelegant; you should be able to detect such syntax errors as part of your parsing routine.  Also, having four if-statements checking for opening/closing parentheses is a sign of confusion.

To enforce some structure to your parser, you should have a helper function for each production listed above.

Instead of taking .subList()s, I think it would be more elegant to use a ListIterator<Token> to keep track of your position.  Also, there's no reason why your parser has to take an ArrayList, when any List<Token> would be acceptable.

Parsable is an odd name for the interface.  I'd consider a string to be parsable.  Therefore, I suggest breaking with the "-able" suffix convention and just call it a Parser.  (Plenty of interfaces in the standard Java API aren't named with an "-able" suffix either.)

/**
 * (JavaDoc describing the grammar goes here.)
 */
public class SimpleParser implements Parser {

    public Expression parse(List<Token> tokens) {
        ListIterator<Token> tokenIter = tokens.listIterator();
        Expression expr = parseExpression(tokenIter);
        if (tokenIter.hasNext()) {
            throw new ParseException("Extra text after expression: " + tokenIter.next().getValue());
        }
        return expr;
    }

    private static Expression parseExpression(ListIterator<Token> tokenIter) {
        if (!tokenIter.hasNext()) {
            throw new ParseException("Premature end of expression");
        }

        Expression expr = parseTerm(tokenIter);
        while (tokenIter.hasNext()) {
            Token op = tokenIter.next();
            if (op instanceof OpToken) {
                expr = parseBinaryExpression(expr, (OpToken)op, tokenIter);
            } else {
                tokenIter.previous();
                break;
            }
        }
        return expr;
    }

    private static Expression parseBinaryExpression(Expression leftExpr, OpToken op, ListIterator<Token> tokenIter) {
        return op.toExpression(leftExpr, parseTerm(tokenIter));
    }

    private static Expression parseTerm(ListIterator<Token> tokenIter) {
        Token t = tokenIter.next();
        if ("(".equals(t.getValue())) {
            return parseParenthesizedExpression(tokenIter);
        } else {
            return parseValueExpression(t);
        }
    }

    private static Expression parseValueExpression(Token t) {
        try {
            int intVal = Integer.parseInt(t.getValue());
            return new ValueExpression(intVal);
        } catch (NumberFormatException nfe) {
            throw new ParseException("expected int but found: " + t.getValue());
        }
    }

    private static Expression parseParenthesizedExpression(ListIterator<Token> tokenIter) {
        Expression innerExpr = parseExpression(tokenIter);
        if (!tokenIter.hasNext() || !")".equals(tokenIter.next().getValue())) {
            throw new ParseException("Missing right parenthesis");
        }
        return innerExpr;
    }
}


A super string cleaner I need a method that clean up a string considering these few rules:

Remove or not Spaces
Remove or not Special Chars
Remove or not Numbers
Descaptalize or not the string (this is don't really needed but I included it anyway).

I did some google if exists something that already do this, but found nothing, so I came up with this:

public static class StringHelper
{
    private static readonly Dictionary<char, char> _specialChars
        = new Dictionary<char, char>
    {
        { 'á', 'a' },{ 'à', 'a' },{ 'â', 'a' },{ 'ã', 'a' },{ 'ä', 'a' },
        { 'é', 'e' },{ 'è', 'e' },{ 'ê', 'e' },{ 'ë', 'e' },
        { 'í', 'i' },{ 'ì', 'i' },{ 'î', 'i' },{ 'ï', 'i' },
        { 'ó', 'o' },{ 'ò', 'o' },{ 'õ', 'o' },{ 'ö', 'o' },
        { 'ú', 'u' },{ 'ù', 'u' },{ 'û', 'u' },{ 'ü', 'u' },
        { 'ç', 'c' },{ 'ñ', 'n' }
    };

    static StringHelper()
    {
        foreach (var item in _specialChars.ToList())
        {
            _specialChars.Add(
                item.Key.ToString().ToUpper()[0],
                item.Value.ToString().ToUpper()[0]);
        }
    }

    private static readonly Regex _spaceRegex = new Regex(@"\s", RegexOptions.Compiled);
    private static readonly Regex _numericRegex = new Regex(@"\s", RegexOptions.Compiled);

    public static string Normalize(this string str, CharType normaliar = CharType.All)
    {
        if (normaliar.HasFlag(CharType.Spaces))
        {
            str = _spaceRegex.Replace(str, string.Empty);
        }

        if (normaliar.HasFlag(CharType.Special))
        {
            str = _specialChars.ToList()
                .Aggregate(str, (ac, item) => ac.Replace(item.Key, item.Value));
        }

        if (normaliar.HasFlag(CharType.Numerics))
        {
            str = _numericRegex.Replace(str, string.Empty);
        }

        if (normaliar.HasFlag(CharType.UpperCase))
        {
            str = str.ToLower();
        }

        return str;
    }
}

public enum CharType
{
    Spaces = 1,
    Special = 2,
    Numerics = 4,
    UpperCase = 8,
    All = 15,
}

I'm not considering really all special char just Portuguese, Spanish and a few more.

As far as I could, I wrote with the better performance and organization, but this was my limit.

private static readonly Regex _numericRegex = new Regex(@"\s", RegexOptions.Compiled);

That should be \d, not \s.

Instead of

_specialChars.Add(
    item.Key.ToString().ToUpper()[0],
    item.Value.ToString().ToUpper()[0]);

You can write

_specialChars.Add(
    Char.ToUpperInvariant(item.Key),
    Char.ToUpperInvariant(item.Value));

I find it a bit cleaner, and there is less work involved.

If the text is potentially very long, you may be better off doing just one pass of the string. You would need to profile against the sort of data you have, but it could look something like this

var spaces = normaliar.HasFlag(CharType.Spaces);
var numerics = normaliar.HasFlag(CharType.Numerics);
var uppercase = normaliar.HasFlag(CharType.UpperCase);
var special = normaliar.HasFlag(CharType.Special);

var sb = new StringBuilder(str.Length);

for (var i = 0; i < str.Length; i++)
{
    var c = str[i];
    if (spaces && Char.IsWhiteSpace(c))
    {
        continue;
    }

    if (numerics && Char.IsNumber(c))
    {
        continue;
    }

    if (uppercase)
    {
        c = Char.ToLowerInvariant(c);
    }

    if (special)
    {
        char replacement;
        if (_specialChars.TryGetValue(c, out replacement))
        {
            c = replacement;
        }
    }

    sb.Append(c);
}

return sb.ToString();


Deck Shuffling Method Just wondering if you guys think this is a good way to shuffle a deck or a bad way. Updated to show the GetRandom function as requested.

Private Sub DeckShuffle()
        ' shuffles the deck 4 times.
        For shufflingCards As Integer = 0 To 3
            ' goes through each card and changes position once each time it goes through shufflingCards
            For shuffleEachCard As Integer = 0 To 51
                ' gets a random number 0 - 51
                Dim placeHolder As Integer = GetRandom(0, 51)
                ' creates a temporary card for swapping cards
                Dim tempCard As Card = deck(placeHolder)
                ' makes the random number card now the card we were shuffling
                deck(placeHolder) = deck(shuffleEachCard)
                ' replaces the card we were shuffling with the one we were saving as a temporary
                deck(shuffleEachCard) = tempCard
            Next
        Next
    End Sub

' Gets a random number for shuffling.
Private Function GetRandom(ByVal Min As Integer, ByVal Max As Integer) As Integer
    Static Generator As System.Random = New System.Random()
    Return Generator.Next(Min, Max)
End Function

Another way to shuffle a deck is to start of with your full deck (oldDeck) and an empty deck (newDeck). This uses the same random generator function in the OP.  I haven't tried to properly code this because the algorithm is the important message.

While size of oldDeck > 0
  chosenCard = getrandom(0,size of oldDeck-1)
  remove chosenCard from oldDeck ' reduces the size of oldDeck by 1
  append chosenCard to newDeck
'Wend
return newDeck ' or reassign newDeck to oldDeck, depending on the broader context

This algorithm would be particularly useful if a class of Deck existed, and it could be a member function as noted in the previous reply. You could then consider having a class of Card which includes a suit and value. A Deck would then be a collection of Cards, and the built-in collection functions become your friends. Of course, this amount of effort depends on what you are going to do with your Deck.


Static wrapper class for log4net Logging - thread safety I'm using log4net in my application and have a static Log class which creates an instance of ILog with a default log type, e.g CMS. The ILog instance is then used by the class to call the log4net logging methods passing in a LogItem type as the log message to enforce a strict logging format.

The user of the class can also change the logger targeted by the logger at runtime by setting a public static property LogType for example: Log.LogType = Enums.LogType.Database.

Here is the class:

/// <summary>
/// Log wrapper around ILog - enforces consistent log format.
/// </summary>
public static class Log
{
    private static ILog Logger = LogManager.GetLogger(LogType.CMS.ToString());

    /// <summary>
    /// Sets the Logger to be used.
    /// </summary>
    public static LogType LogType
    {
        set
        {
            Logger = LogManager.GetLogger(value.ToString());
        }
    }

    /// <summary>
    /// Logs information to the system.
    /// </summary>
    /// <param name="source">Source of the info.</param>
    /// <param name="description">Info description.</param>
    /// <param name="exc">Associated Exception object.</param>
    public static void Info(string source, string description, Exception exc = null)
    {
        Logger.Info(new LogItem() { Source = source, Description = description }, exc);
    }

    /// <summary>
    /// Logs a warning to the system.
    /// </summary>
    /// <param name="source">Source of the info.</param>
    /// <param name="description">Info description.</param>
    /// <param name="exc">Associated Exception object.</param>
    public static void Warn(string source, string description, Exception exc = null)
    {
        Logger.Warn(new LogItem() { Source = source, Description = description }, exc);
    }

    /// <summary>
    /// Logs an error to the system.
    /// </summary>
    /// <param name="source">Source of the info.</param>
    /// <param name="description">Info description.</param>
    /// <param name="exc">Associated Exception object.</param>
    public static void Error(string source, string description, Exception exc)
    {
        Logger.Error(new LogItem() { Source = source, Description = description }, exc);
    }
}

I'm concerned on whether the LogType prop would be thread safe, what would happen if this is changed by another class before the logger does its job?

I've read that log4net itself is thread safe and will block when calling the appenders - would having a single static class that everything logs through eventually cause a bottleneck?

This is not thread safe, just because the LogType static property. The basic problem of such design is that any log operation while setting the log type requires two calls and changes in global state. Imagine how an hypothetical client code would look like:

Log.LogType = LogType.Database;
//What happens between these two lines?
Log.Info("CodeReview", "Testing error logging", new Exception("Kaboom"));

The first line sets the global log type, and the second uses it, quite simple. But what happens if another thread runs similar code in between? LogType can be changed in the meanwhile (look at my comment in the code), changing the effective destination to the unsuspecting code. Thus, it's not thread safe. As you mention, since Log4Net in itself is thread safe, logs methods have no problems with this, but the destination can be somewhat surprising.

You mention a lock to overcome this in comments. Again an hypothetical usage could be like this:

lock (typeof(Log))
{
    Log.LogType = LogType.Database;
    Log.Info("CodeReview", "Testing error logging", new Exception("Kaboom"));
}

This solves the issue but at a high cost, the "fix" must be implemented in each and every call, instead of doing it centrally from within the Log class. Since the operation spans 2 methods, you can't lock within a method. Additionally this increases contention and reduces performance, as all logging is now syncronized and each thread must wait for the others to finish logging. While Log4Net could potentially do the same internally, it may also implement other optimizations, that such approach will nulify.

The root problem comes from the global state, the logger is a just stored in a static variable and can be overwriten by anyone, including between calls. A possible solution would be to pass the log type as a parameter and create a local logger for each call and get rid of the LogType property altogether:

public static void Info(string source, string description, Exception exc = null, LogType logType = LogType.CMS)
{
    ILog logger = LogManager.GetLogger(logType.ToString());
    logger.Info(new LogItem() { Source = source, Description = description }, exc);
}

This results in NO global state, which eliminates chances of races conditions, and also simplify client code, as now every log request is a single call to the appropriate method.


How do I simplify the code in C#? Here is a code I want to simplify:

public void Method1(Context context, EventLog log = null)
{
    Class myClass = ConvertToMyClass();
    ApiCall1 apiCall = new ApiCall1(context);
    if (log != null)
    {
        eventLog.WriteEntry("Starting");
    }

    try
    {
        apiCall.Call1(myClass, null, false);
        IsCallSuccess = true;
    }
    catch (Exception e)
    {
        if (log != null)
        {
            eventLog.WriteEntry("error");
        }

        IsCallSuccess= false;
        CallErrorMessage = e.Message;
    }
}

public void Method2(Context context, EventLog log = null)
{
    Class myClass = ConvertToMyClass();
    ApiCall2 apiCall = new ApiCall2(context);
    if (log != null)
    {
        eventLog.WriteEntry("Starting");
    }

    try
    {
        apiCall.Call1(myClass);
        NewItemID = myClass.ItemID;
        IsCallSuccess = true;
    }
    catch (Exception e)
    {
        if (log != null)
        {
            eventLog.WriteEntry("error");
        }

        IsCallSuccess= false;
        CallErrorMessage = e.Message;
    }
}

public void Method3Context context, EventLog log = null)
{
    Class myClass = ConvertToMyClass();
    ApiCall3 apiCall = new ApiCall3(context);
    if (log != null)
    {
        eventLog.WriteEntry("Starting");
    }

    try
    {
        apiCall.Call3(myClass, "param1");
        UpdatedItemID = myClass.UpdatedItemID;
        IsCallSuccess = true;
    }
    catch (Exception e)
    {
        if (log != null)
        {
            eventLog.WriteEntry("error");
        }

        IsCallSuccess= false;
        CallErrorMessage = e.Message;
    }
}

There are 3 methods. I've been thinking about how I could simplify them using delegates or lambdas and didn't find anything.

Note that ApiCall1/2/3 are all defined in a third-party library.
Your thoughts?

Alright, let's see if we can simplifyabstract this for you. I'm not going to say simplify because often times abstracting something is far from simplifying it.

I think you can turn the method into something like this:

public void Method<T>(Context context, Action<T, Class> body, EventLog log = null)
{
    Class myClass = ConvertToMyClass();
    T apiCall = Activator.CreateInstance(typeof(T), new [] { context });
    if (log != null)
    {
        eventLog.WriteEntry("Starting");
    }

    try
    {
        body(apiCall, class);
        IsCallSuccess = true;
    }
    catch (Exception e)
    {
        if (log != null)
        {
            eventLog.WriteEntry("error");
        }

        IsCallSuccess = false;
        CallErrorMessage = e.Message;
    }
}

... then you should be able to call it like this:

// Method1
Method<ApiCall1>(
    yourContextInstance,
    (apiCall, myClass) =>
    {
        apiCall.Call1(myClass, null, false);
    },
    yourLogInstance);

// Method2
Method<ApiCall2>(
    yourContextInstance,
    (apiCall, myClass) =>
    {
        apiCall.Call1(myClass);
        NewItemID = myClass.ItemID;
    },
    yourLogInstance);

// Method3
Method<ApiCall3>(
    yourContextInstance,
    (apiCall, myClass) =>
    {
        apiCall.Call3(myClass, "param1");
        UpdatedItemID = myClass.UpdatedItemID;
    },
    yourLogInstance);

... one caveat is NewItemID and UpdatedItemID. If you're not making these calls from inside the class Method is defined in, you may need to modify this a tad to get the Method to return and integer instead.


Database logger for ASP.NET Core I have created a database logger for ASP:NET Core's logging API and I'd like to publish it on NuGet when ready. The GitHub repository is here.

The library is partly modeled after Microsoft.Extensions.Logging.Console and I tried to follow good practices of object-oriented design.

I am slightly concerned about some decisions I made while implementing ILogWriter interface in SqlServerLogWriter class AND while designing the interface for the WriteBulk method (the method is called from the LogRecordCache class).

Have I managed threading well enough? It works fine, but it might not look OK.
Should I hide exceptions or let them propagate? Logging should be redundant in production environment, so I think hiding them would be fine.
Is there a better way for column mapping (in SqlServerLogWriter)?
Any advice or contribution would be appreciated.

LogRecordCache.cs

internal static class LogRecordCache
{
    private static readonly List<LogRecord> _logs;
    private static bool _flushingInProgress = false;
    private static object _lockObject = new object();

    public static bool IsEmpty { get { return _flushingInProgress || _logs.Count == 0; } }

    static LogRecordCache()
    {
        _logs = new List<LogRecord>();
    }

    public static void Add(LogRecord log)
    {
        if (_flushingInProgress)
        {
            lock (_lockObject)
            {
                _logs.Add(log);
            }
        }
        else
        {
            _logs.Add(log);
        }
    }

    public static bool IsFull(int maxCount)
    {
        return !_flushingInProgress && _logs.Count >= maxCount;
    }

    public static void Flush(ILogWriter writer)
    {
        if (!_flushingInProgress)
        {
            _flushingInProgress = true;
            Task.Run(() => writer.WriteBulk(_logs, _lockObject, ref _flushingInProgress));
        }
    }
}

WriteBulk() method

/// <summary>
/// Writes a collection of log records to database at once
/// </summary>
/// <param name="logs">List of <see cref="LogRecord"/> objects</param>
/// <param name="lockObject">Locking object</param>
/// <param name="flushingInProgress">Indicates if writing process is still in progress; set to false at the end of this method</param>
/// <exception cref="SqlException">If opening a connection through the provided connection string was not possible</exception>
public void WriteBulk(List<LogRecord> logs, object lockObject, ref bool flushingInProgress)
{
    var lockTaken = false;
    var connection = new SqlConnection(_connectionString);
    connection.Open();
    var transaction = connection.BeginTransaction();

    try
    {
        using (var bulkCopy = new SqlBulkCopy(connection, SqlBulkCopyOptions.TableLock, transaction))
        {
            bulkCopy.DestinationTableName = "Logging";
            foreach (var mapping in _columnMappings)
                bulkCopy.ColumnMappings.Add(mapping.Key, mapping.Value);

            Monitor.TryEnter(lockObject, ref lockTaken);
            if (lockTaken)
            {
                using (var reader = ObjectReader.Create(logs, _columnMappings.Keys.ToArray()))
                {
                    bulkCopy.BatchSize = logs.Count;
                    bulkCopy.WriteToServer(reader);
                }

                transaction.Commit();
            }
        }
    }
    catch
    {
        if (connection.State == ConnectionState.Open)
            transaction.Rollback();
        throw;
    }
    finally
    {
        if (lockTaken)
        {
            logs.Clear();
            Monitor.Exit(lockObject);
        }

        transaction.Dispose();
        connection.Close();
        flushingInProgress = false;
    }
}

Should I hide exceptions or let them propagate? Logging should be redundant in production environment, so I think hiding them would be fine.

Both. I think this should be configurable. During setup / testing exceptions should be thrown for easier debugging (database permission issues etc.) but in production exceptions should not be thrown.

I have been using NLog and at least in my use this way has been working fine.


Make huge view in C# readable and maintanable I have an application that is using MVC5 with C# and Razor Engine.  This view displays a huge table:

            Actions
            Order Status
            Order Details
            Order Date
            Expected Delivery Date
            Ordered By
            Employee ID
            Employee Status
            Employee Name
            Employee Type
            Scope
            Delivery Address
            Comment

Now, the problem is that everything is in one huge file. As you can guess, this file is a nightmare to update and maintain.

I am familiar with the C# region directive, but I can't find anything similar for Views. I also know about partial views, but I have the strong impression from discussions in Stack Overflow that these should only be used when I have a piece of code in a View that is re-usable, which is not the case.

What is the best way to deal with Views this large?

I would use a Partial View for this code.
Anytime I have a menu for a page I put it in a partial view even though it may not be used on another page.

@Html.Partial("_Actions")

@Html.Partial("_OrderStatus")

@Html.Partial("_OrderDetails")

@Html.Partial("_OrderDate")

inside the Partial view placed in Views/Shared

@model ActionsViewModel
Column 1
Column 2
Column 3
Column 4
Column 5

etc...
Good Luck!


Soup of the day: best served during election season Community moderator elections on the Stack Exchange network are really exciting.
Alas, on the page of the primaries, I find it mildly annoying that candidates are randomly reordered on every page load, even if it's surely for a good reason.

So, I cooked up (pun totally intended) this script using Beautiful Soup 4 in Python to list the candidates in an election by their score. To use it, install beautifulsoup4 (for example with pip install --user beautifulsoup4), and then to list the candidates running for Code Review:

$ python primaries.py so -n 6  # the 6th election on Stack Overflow
10905   Martijn Pieters
7310    meagar
5923    Jon Clements
5461    Matt
5211    Madara Uchiha
4133    deceze
3301    Raghav Sood
3180    Paresh Mayani
3126    Jeremy Banks
2651    Ed Cottrell

Since all the Stack Exchange sites seem to use the same format, it can work with all Stack Exchange sites. For the sake of a POC I included support for a few other sites (use "so" for Stack Overflow, "sf" for Server Fault), obviously it should be extended for others. Another feature I plan to add soon is to find the latest election by default, rather than using the first.

I mainly suspect some improvement opportunities concerning my use of Beautiful Soup, but I'm open to any kind of improvement ideas in general.

#!/usr/bin/env python

from argparse import ArgumentParser
from urllib import request

from bs4 import BeautifulSoup

STANDARD_URL_FORMAT = 'http://{}.stackexchange.com/election/{}?tab=primary'
COM_URL_FORMAT = 'http://{}.com/election/{}?tab=primary'

SITES_INFO_HELPER = [
    (('cr', 'codereview'), STANDARD_URL_FORMAT, 'codereview'),
    (('sf', 'serverfault'), COM_URL_FORMAT, 'serverfault'),
    (('so', 'stackoverflow'), COM_URL_FORMAT, 'stackoverflow'),
]

def build_sites_info():
    sites_info = {}
    for info in SITES_INFO_HELPER:
        names, url_format, url_component = info
        for name in names:
            sites_info[name] = url_format, url_component
    return sites_info

def load_html_doc(url):
    return request.urlopen(url).read()

def get_soup(url):
    html_doc = load_html_doc(url)
    soup = BeautifulSoup(html_doc, 'html.parser')
    # print(soup.prettify())  # for debugging
    return soup

def main():
    sites_info = build_sites_info()

    parser = ArgumentParser(description='Show candidates of an SE election in sorted order')
    parser.add_argument('site', choices=sites_info.keys(),
                        help='Site short name or abbreviation')
    parser.add_argument('-n', type=int, default=1,
                        help='Election number')
    args = parser.parse_args()

    site_info = sites_info[args.site]
    url_format, url_component = site_info
    url = url_format.format(url_component, args.n)

    soup = get_soup(url)
    scores = []
    for tr in soup.find_all('tr'):
        if tr.find('td', attrs={'class': 'votecell'}):
            username = tr.find(attrs={'class': 'user-details'}).find('a').text
            votes = int(tr.find(attrs={'class': 'vote-count-post'}).text)
            scores.append((username, votes))

    for name, score in sorted(scores, key=lambda x: x[1], reverse=True):
        print('{}\t{}'.format(score, name))

if __name__ == '__main__':
    main()

Since your list SITES_INFO_HELPER remains constant throughout the entire program, that list should be a tuple instead

Tuples are faster than lists and are write-protected, which doesn't make a difference to you because you are writing to them.

Read more about when you should use a tuple and when you should use a list here.

Good job using ArgumentParser in your code; that is often something that you don't see used in python code and is actually an extremely useful tool.

You could make your code more object oriented by turning the information inside SITES_INFO_HELPER into instances of a class, probably called Site.

It doesn't have to be anything too complicated; it's just supposed to be a way to store some values:

class Site:
    def __init__(self, name, initials, format=STANDARD_URL_FORMAT):
        self.name = name
        self.initials = initials
        self.format = format

Note: I set the format property to be STANDARD_URL_FORMAT by default because most stack exchange sites follow this format.

Then, when storing the sites, you'd store them like this:

SITES_INFO_HELPER = ( Site("codereview", "cr"), Site("stackoverflow", "so", COM_URL_FORMAT) ...)

I'm not entirely sure, but storing site information like this may rid of the need of build_sites_info.

I think you made a good choice using urllib and BeautifulSoup together to read the election webpage. And, from what I know about BeautifulSoup, what you are doing looks just fine.

Also, looking over the election page layout, how you are scanning the webpage seems to be the only/best way.


Round-tripping from LinkedHashMaps to Clojure collections I'm trying to implement round-tripping from LinkedHashMaps to Clojure collections. The implementation below works for smaller collections, but larger collections raise OutOfMemoryError: GC overhead limit exceeded. Below is a generative test that passes, when the number of tests is small (~10), but exhausts memory for larger numbers of tests (~100).

I would appreciate any tips how to reduce the memory requirements of the implementation as well as general tips on how to improve the code's quality.

(import '[clojure.lang IPersistentMap IPersistentVector]
        '[java.util ArrayList LinkedHashMap])

(defprotocol LinkedHashMappable
  "Convert Clojure data structure to LinkedHashMap."
  (->linked-hash-map [data]))

(extend-protocol LinkedHashMappable
  IPersistentMap
  (->linked-hash-map [m]
    (let [lhm (LinkedHashMap.)]
      (doseq [[k v] m]
        (.put lhm
              (if (keyword? k) (name k) k)
              (->linked-hash-map v)))
      lhm))

  IPersistentVector
  (->linked-hash-map [v]
    (let [alist (ArrayList.)]
      (doseq [i v] (.add alist (->linked-hash-map i)))
      alist))

  Object
  (->linked-hash-map [o] o))

(defprotocol Clojurizable
  "Convert LinkedHashMap to Clojure data structure."
  (->clj [lhm]))

(extend-protocol Clojurizable
  LinkedHashMap
  (->clj [lhm]
    (reduce (fn [m [k v]]
              (assoc m (keyword k) (->clj v)))
            {}
            (iterator-seq (.. lhm entrySet iterator))))

  ArrayList
  (->clj [alist]
    (mapv ->clj alist))

  Object
  (->clj [o] o))

; ----- Test -----

(require '[clojure.test.check :as tc]
         '[clojure.test.check.generators :as gen]
         '[clojure.test.check.properties :as prop])

(def map-generator
  (gen/recursive-gen (fn [inner]
                       (gen/map gen/keyword (gen/one-of [(gen/map gen/keyword inner)
                                                         (gen/vector inner)])))
                     gen/string))

(def linked-hash-map-round-tripping
  (prop/for-all [m map-generator]
                (= (->clj (->linked-hash-map m)) m)))

; The test passes for smaller numbers of tests (~10), but exhausts memory for larger numbers (~100).
#_(tc/quick-check 100 linked-hash-map-round-tripping)

I think automatically creating keywords from string keys and string keys from keywords is not a good idea, for three reasons.

It would be surprising to a user to have values change classes when theoretically just pouring the contents of one map into another.
In the space of possible key transformations, keyword<-->string is just one point. As a user, I might want to do many other kinds of transformations while converting. For a more general approach, think about how transducers can be supplied to the four-argument form of into.
Keywords are interned. This may be a source of your memory trouble. Every new keyword gets stored permanently in the heap. That's how Clojure does fast keyword comparison by just checking object references. That means a property-based test that generates huge numbers of unique keywords is going to consume a lot of memory.


Project Euler 18/67 : Maximum Path using Memoization Problem statement of PE18 is :

By starting at the top of the triangle below and moving to adjacent numbers
on the row below, the maximum total from top to bottom is 23.

   3
  7 4
 2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

                75
               95 64
              17 47 82
            18 35 87 10
           20 04 82 47 65
          19 01 23 75 03 34
         88 02 77 73 07 63 67
        99 65 04 28 06 16 70 92
       41 41 26 56 83 40 80 70 33
      41 48 72 33 47 32 37 16 94 29
     53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
   91 71 52 38 17 14 91 43 58 50 27 29 48
  63 66 04 68 89 53 67 30 73 16 69 87 40 31
 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

And PE67 is the very same question but,

  NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. It cannot be solved by brute force, and requires a clever method! ;o)

My Implementation :

public class Euler_18{
// A custom data structure used to store
// the array so that I can seperate the
// logic from the storage
static class TriangularArray{
    HashMap<Integer, int[]> map;
    int someInt;
    int size;
    // All the elements will be stored in
    // HashMap according to their order
    public TriangularArray(int size){
        this.size = size;
        map = new HashMap<Integer, int[]>();
        // Initialise the array
        for(int i=1; i<=size; i++){
            int[] currArray = new int[i];
            map.put(i, currArray);
        }
    }

    // Accept the array
    public void acceptArray(Scanner in){
        for(int i=1; i<=size; i++){
            int[] currArray = map.get(i);
            for(int j=0; j<currArray.length; j++){
                currArray[j] = in.nextInt();
            }
            map.put(i, currArray);
        }
    }

    // Display the array
    public void displayArray(){
        for(int i=1; i<=size; i++){
            int[] currArray = map.get(i);
            System.out.println("Array " + i + " : " + Arrays.toString(currArray));
        }
    }

    // Finds the maximum using Memoization.
    public void findMaximum(){
        for (int i=size-1; i>0; i--) {
            int[] currArray = map.get(i);
            int[] belowArray = map.get(i+1);
            for (int j=0; j<currArray.length; j++) {
                // The value of current element will be the maximum of the 2 values
                // of the array directly below it
                currArray[j] = Math.max(belowArray[j], belowArray[j+1]) + currArray[j];
            }
        }
        System.out.println("The maximum route is of length : " + map.get(1)[0]);
    }
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int size = in.nextInt();
    TriangularArray theArray = new TriangularArray(size);
    theArray.acceptArray(in);
    theArray.displayArray();
    theArray.findMaximum();
}
}

Storage

A Map is most useful when the key values are not in a sequence,
but sparse, with smaller and bigger gaps between key values.

In this example, the key corresponds to a row of the triangle,
taking on values from 0 to size, and using all values in the range.
An array would be a more natural choice for storage,
in this example an int[][].

Note that a hash map has some storage overhead.
Also, accessing array elements is simpler to write than .get(...) and .put(...) calls.

Encapsulation

This is a bit unfortunate:

TriangularArray theArray = new TriangularArray(size);
theArray.acceptArray(in);
theArray.displayArray();
theArray.findMaximum();

Since findMaximum will modify the underlying storage,
if you call theArray.findMaximum() one more time,
it will produce different output,
which is unexpected.

It's best when you can call a method multiple times and get the same result consistently.
Unless of course it is by design that the call manipulates state,
for example in an iterator.
The name "findMaximum" doesn't hint at manipulating state,
which is misleading.

In fact, findMaximum is designed for one-time use.
It would be better to rewrite this in a way that the state manipulation becomes obvious.
Or throw an exception if the method is called a second time.
Or encapsulate the logic in a way that calling findMaximum repeatedly would produce the same result consistently.

I would also recommend to make findMaximum return the maximum instead of printing text.

Pointless statements

This variable is unused (and poorly named):

int someInt;

The map.put(i, currArray) statement at the end is unnecessary:

int[] currArray = map.get(i);
for(int j=0; j<currArray.length; j++){
    currArray[j] = in.nextInt();
}
map.put(i, currArray);

Because currArray comes from map.get(i), and it is not reassigned.

Other redundancies

TriangleArray.size is redundant.
The same information is available through the underlying storage,
whether using a map or an array.

Instead of initializing the arrays in the constructor,
you could do it at the same time as parsing from Scanner,
to iterate over the lines only once.

Most of the comments are completely redundant, noise, for example:

// Display the array
public void displayArray() {

This helps nobody, omit such redundant comments.

Naming

acceptArray is a strange name for a method that parses numbers from a Scanner. How about parseFromScanner ?

displayArray is a strange name for method that prints the content of the triangle. How about simply print ? As the method is on the TriangleArray class, it's implied that it will print the triangle itself.

Alternative implementation

Consider this alternative implementation:

static class TriangularArray {
    private final int[][] rows;

    public TriangularArray(int size) {
        rows = new int[size][];
    }

    public void parseFromScanner(Scanner scanner) {
        for (int i = 0; i < rows.length; i++) {
            rows[i] = new int[i + 1];
            for (int j = 0; j < rows[i].length; j++) {
                rows[i][j] = scanner.nextInt();
            }
        }
    }

    // Finds the maximum using Memoization.
    public int findMaximum() {
        int[] below = rows[rows.length - 1];
        for (int i = rows.length - 2; i >= 0; i--) {
            int[] current = rows[i].clone();
            for (int j = 0; j < current.length; j++) {
                current[j] = Math.max(below[j], below[j + 1]) + current[j];
            }
            below = current;
        }
        return below[0];
    }
}


Vote-switching optimization I have 2 s being used for displaying the votes, which is up votes and down votes. There is no problem for the adding or removing votes, but the switching of votes is the issue (not really an issue).

The structure of the votes in the HTML is:

The values are retrieved from the database and I user innerHTML to insert the data between the  tags. Once the user clicks the , either the up_vote or the down_vote, the update request is sent through ajax and updates the vote counts, and once it is successfully executed, the value inside the  will be incremented by one, as well as the removing of vote, it will be decremented. And a voted class will be added once the user votes.

My JavaScript looks like this:

$("#up_vote, #down_vote").click(function(e) {
  var voteCount = document.getElementById(e.target.id).innerHTML;
  var action;
  var value;

  if ($("#up_vote").hasClass("voted") || $("#down_vote").hasClass("voted")) {
    if ($(this).hasClass("voted")) {
      action = "remove_vote";
      setValue();
    } else {
      action = "switch_vote";
      setValue();
    }
  } else {
    action = "add_vote";
    setValue();
  }

  function setValue() {
    if (e.target.id === "up_vote") {
      value = 1;
    } else if (e.target.id === "down_vote") {
      value = -1;
    }
  }

  $.ajax({
    method: "GET",
    url: "votes.php",
    data: , //it includes the user session id, the post id, and the action and values for doing the specific functions (i just didn't put it here, just giving the logic on what does my code looks like
    cache: false,
    success: function(msg) {
      if (msg === "vote_added") {
        document.getElementById.innerHTML = parseInt(voteCount) + 1;
        $("#" + e.target.id).addClass("voted");
      } else if (msg === "vote_removed") {
        // the same function of the vote_added message, but instead, it decrements the value and removes the "voted" class
      } else if (msg === "vote_switched") {
        // these is the part that i want to achieve, but coding it seems a bit long (just my thought)
      } else if (msg === "vote_exist") {
        // these is a, some sort of notifying the user that the he/she already votes the specific post
      }
    }
  })
})

As on what you see on the JavaScript, it sends an action and value (which will specify if it is up vote or down vote, which will be used to do specific functions inside the PHP. It will then echo out the message that will be used once the query is executed successfully.

(On the last condition, vote_exist, is used for security check. While I'm testing something out, removing the class="voted" (which notifies that the user already voted) inside Inspector window, clicking these back will increment the vote count again, which removes the restrictions, so I added a validation function inside the PHP before the user votes for doubled security check. Hope that these can help for others.)

My concern is about the 3rd condition, which is the switching of votes. For example, the user already up votes, and then he/she wants to down vote. There is no problem for the queries, just for the JavaScript part. I have an idea, though: by using the same functions inside the vote_added and vote_removed, where, when clicked, will target id will be incremented at the same time the other one will be decremented, also adds a voted class to the target id and removes the other one.

How can I do this in a shorter way?

We cant review the code if you don't provide it, telling us that it is a bit long will not help. You should provide the full code especially since it is likely that refactoring will be useful between the different cases.

Regardless, here are some observations from what you did provide:

In essence, whatever the user does, you will always call setValue(), once you realize this you can simplify the first if statement

if ($("#up_vote").hasClass("voted") || $("#down_vote").hasClass("voted")) {
  if ($(this).hasClass("voted")) {
    action = "remove_vote";
  } else {
    action = "switch_vote";
  }
} else {
  action = "add_vote";
}
setValue();

And, since you only call setValue() once, you can even take it out of it's function and just put it after the first if statement.
You might even consider replacing the if statement inside setValue with a ternary statement: value = e.target.id === "up_vote" ? 1 : -1;
When posting data, you should use "POST", not "GET"
I feel votes.php should give back the vote counts. Just adding 1 or removing 1 from the last vote count is cheating, and I think users can tell.
Finally, and this is a matter of taste, I would not send +1 or -1 back, I would send the value of e.target.id back, and let the back-end do the conversion.


Pythonic sieve of Erasthotones that saves results to file I'd like to have some feedback on this sieve of erasthotones that I've wrote. It outputs all prime numbers up to n correctly (I've tested with the first 10k prime numbers).

Is this well written? Does it look good for python programmers?

I've made the math up to the sqrt of n + 1, which improved the performance a lot.

import time
import sys
from math import sqrt

def notMarkedValue(n):
    """
    Returns True if parameter is a possible prime number, False otherwise
    """
    return n != -1

def sieve(val):
    """
    Sieve of Eratosthenes implementation. Finds all prime numbers up to n
    """
    primes = [x for x in range(2, val)]
    for n in range(2, int(sqrt(val)+1)):
        if notMarkedValue(n):
            for i in range(2, val):
                index = (i*n) - 2 # shift index down -2 because 0 and 1 are not in the list
                if index < len(primes):
                    primes[index] = -1
    return filter(notMarkedValue, primes)

def saveToFile(primes):
    """
    Saves the input to a file
    """
    with open('output', 'w+') as f:
        for n in primes:
            f.write(str(n) + ' ')

def getMaxNumber():
    """
    Gets, from passed arguments if provided or input otherwise, the number in which all prime numbers up to it will be calculated
    """
    return int(sys.argv[1]) if len(sys.argv) > 1 else int(input('Find all primes up to: '))

def main():
    n = getMaxNumber()
    print("-- counting primes...")
    start = time.clock()
    primes = sieve(n)
    end = time.clock()
    print("-- calculated all prime numbers up to {0} in {1} seconds".format(n, (end - start)))
    print("-- saving to file \"output\"...")
    saveToFile(primes)

if __name__ == '__main__':
    main()

One thing that I've thought was about making def sieve() return a list(filter(notMarkedValue, primes)), so that I'd have a list that could be enumerated later, but I didn't as I thought it'd be a bit overkill.

Edit: Now that I'm thinking of it, I should have added to its docstring that it returns a filter object. :-)

First off, the general naming style in Python is snake_case for functions and variables, and PascalCase for classes. On the note of style, you should also have two blank lines between top-level functions/classes/code blocks.

Secondly, are you sure that you want to be using len( ... ), rather than len ( ... ) - 1, as you did here: if index < len(primes):? The len function "counts" the objects in the list starting at 1, not 0, which means if you're using it to get indexes, it'll be off by one.

Other than that, there's not much else that really needs to be improved here! Good job!


Updating register_globals code for importing $_GET and $_POST data I'm updating a bunch of PHP code that relies on register_globals and uses request data globally. In the process of fixing/updating I spend a lot of time writing code that looks like:

<?php
$x = isset($_REQUEST['x']) ? $_REQUEST['x'] : $xdefault; // other times loaded from $_GET['x'] or $_POST['x']
$abc = isset($_REQUEST['abc']) ? $_REQUEST['abc'] : $abcdefault;
?>

I've been toying with the idea of using something like:

<?php
function _export(&$source, &$defaults) {
  return array_merge($defaults, array_intersect_key($source, $defaults));
}

// old code essentially uses $_REQUEST, but I could point this at $_POST
// $_GET or a db query in the future

$defaults = array (
  'x'   => $xdefault,
  'abc' => $abcdefault,
);

$options = _export($_GET, $defaults);
extract($options); //export if needed until global code can be fixed
?>

The benefits being:

It's easier (I feel) to read array syntax compared to a list of ternary issets() assignments
The defaults array acts as a whitelist
The defaults array can be used to document the expected or required inputs

Are there any disadvantages or possible improvements to this approach? I would name _export() something different.

This seems a bit complex for relatively little benefit. Personally, from these two choices, I would go with the isset approach for simplicity and slightly improved performance.

But I do see your point about the default value, and the readability of the array structure. If you actually do have a lot of parameters which have a default value, your approach might have merit.

But since you are going through the trouble of updating legacy code anyways, you could also think about choosing a different approach and create an Input class. It would also result in readable code, and you could add input filters, increasing your security. The structure is really a matter of preference, but it might look something like this:

class Input {

    function getRaw($value, $default) { ... }
    function getInt($value, $default) { ... }
    function getSafeHTML($value, $default) { ... }
    function getFiltered($value, $default, $regex) { ... }
    ...

    function postRaw($value, $default) { ... }
    function postInt($value, $default) { ... }
    function postSafeHTML($value, $default) { ... }
    function postFiltered($value, $default, $regex) { ... }
    ...

    ...
}

It's then used like this:

$x  = Input::getInt('x', $xdefault);
$ab = Input::postCleanHTML('ab', $abdefault);

It's a bit more work, but it's readable, well structured, and provides additional security; filtering input should never be your main line of defense, but it is highly recommended as defense in depth (depending on the input of course; some input you want unaltered, which is why the getRaw method is there).

Misc

There's no need to pass the arguments by reference to _export. It gives off the impression that the function will change the values, which it does not (and should not, especially for $_GET).
if you are updating legacy code anyways, I would check if REQUEST is really needed. If it is not, change it to GET or POST to increase the security of the code even further.


Python worker pattern for multithreading I'm building a script where I pass in a text file of hostnames, and a text file of commands and each command will then be run against each host.

To prevent this getting out of hand I'm also passing in a maximum thread count and trying to manage a maximum number of workers at any one time.

The code I would like feedback on is as follows:

main.py

#!/usr/bin/python3
import sys
from lib.core.input import InputParser, InputHelper
from lib.core.output import OutputHelper, Level
from lib.core.threader import Pool

def build_queue(arguments, output):
    queue = list()
    for target in InputHelper.process_targets(arguments):
        for command in InputHelper.process_commands(arguments):
            output.terminal(Level.VERBOSE, target, command, "Added to Queue")
            queue.append(command)
    return queue

def main():
    parser = InputParser()
    arguments = parser.parse(sys.argv[1:])

    output = OutputHelper(arguments)

    output.print_banner()

    pool = Pool(arguments.threads, build_queue(arguments, output), arguments.timeout, output)
    pool.run()

if __name__ == "__main__":
    main()

threader.py

import threading
import os

class Worker(object):
    def __init__(self, pool):
        self.pool = pool

    def __call__(self, task, output, timeout):
        self.run_task(task)
        self.pool.workers.append(self)

    @staticmethod
    def run_task(task):
        os.system(task)

class Pool(object):
    def __init__(self, max_workers, queue, timeout, output):
        self.queue = queue
        self.workers = [Worker(self) for w in range(max_workers)]
        self.timeout = timeout
        self.output = output

    def run(self):
        while True:

            # make sure resources are available
            if not self.workers:
                continue

            # check if the queue is empty
            if not self.queue:
                break

            # get a worker
            worker = self.workers.pop(0)

            # get task from queue
            task = self.queue.pop(0)

            # run
            thread = threading.Thread(target=worker, args=(task, self.output, self.timeout))
            thread.start()

Essentially, I don't know what I don't know. There's likely some basic gaps in my knowledge here, and I'd love feedback and examples that help me  to bridge those gaps. Any and all help is very welcome, and very appreciated.

1. Introduction

From a practical point of view, the most important points are that Python has batteries included:

To run tasks in a pool of worker threads, use concurrent.futures.ThreadPoolExecutor.
But if what you really want to do is run external programs via the shell, as suggested by the use of os.system, then you don't need threads at all! Use subprocess.Popen instead.

(Note that on some operating systems, notably macOS, you can only have one call to os.system running at a time. Subsequent calls, even from other threads, have to wait for the first call to finish. On these systems you have to use subprocess.Popen if you want the subprocesses to run in parallel.)

Nonetheless I think it's a good exercise to have a go at writing your own thread pool, and so I'm go to look at how you might improve the code in the post. There's quite a lot of ground to cover, so I'm going to take it in stages, starting by reviewing improving the code in the post, and then identifying and fixing various problems with the design.

2. Initial review

There are no docstrings. How do I use this module? Which classes are public and which are private? Do I create my own Worker objects or do I let the Pool create them for me? What kind of object do I pass for queue? How should I specify the timeout?
The Pool constructor takes timeout and output arguments but these have no effect: they are passed to Worker.__call__ but then they are ignored.
The Pool class has only one method (other than __init__). When you have a class with just one method, then what you need is a function. Not everything needs to be a class! It would simplify the code if it were turned into a function with a specification like this:

def run_shell_commands_in_parallel(commands, max_threads):
    """Run shell commands in parallel. max_threads is the maximum
    number of threads that may run simultaneously.

    """

Running a shell command is not very general. It would make sense to generalize the code to do arbitrary function calls in parallel:

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel. max_threads is the
    maximum number of threads that may run simultaneously.

    """

To try to run a bunch of shell commands in parallel, you'd call it like this:

apply_in_parallel(os.system, ['command1', 'command2', ...])

but now you can use it for other parallel tasks:

apply_in_parallel(print, range(10))

The main thread calls workers.pop(0) and the worker threads call workers.append(self), but the workers data structure is just an ordinary Python list, which is not thread-safe. Whenever you have a data structure that's shared between threads, access to the data structure needs to be synchronized, for example by using a lock to ensure that only one thread can be updating it at a time.
All the Worker objects are identical — their only attribute is self.pool, and that's the same for every worker, so instead of a list of workers all we really need is a count of how many workers are idle.

3. Revised code

Fixing the issues in §1 above yields the following, which does essentially the same thing as the code in the post, but in a simpler way:

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel. max_threads is the
    maximum number of threads to run simultaneously.

    """
    available_workers = max_threads
    available_workers_lock = Lock()

    def worker(arg):
        nonlocal available_workers
        fun(arg)
        with available_workers_lock:
            available_workers += 1

    for arg in args:
        while True:
            with available_workers_lock:
                if available_workers:
                    available_workers -= 1
                    break
        Thread(target=worker, args=(arg,)).start()

4. Problem: busy-waiting

The while True: loop is busy-waiting. If it takes a long time for a worker to become available, the main thread will be wasting effort by repeatedly taking the lock and testing the condition if available_workers: which remains false.

What we'd like instead is to be able to suspend the main thread until a worker becomes available. For this use case what we need is a semaphore, and Python provides us with threading.Semaphore:

from threading import Semaphore, Thread

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel. max_threads is the
    maximum number of threads that may run simultaneously.

    """
    available = Semaphore(max_threads)

    def worker(arg):
        fun(arg)
        available.release()

    for arg in args:
        available.acquire()
        Thread(target=worker, args=(arg,)).start()

5. Problem: can't tell when threads are done

The code in §4 starts the shell commands but does not wait for them all to complete. But in many use cases it is important to wait for workers to finish running before proceding.

To ensure that all threads have finished, we must join them before returning:

from threading import Semaphore, Thread

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel and wait until all
    calls have completed. max_threads is the maximum number of threads
    that may run simultaneously.

    """
    available = Semaphore(max_threads)

    def worker(arg):
        fun(arg)
        available.release()

    threads = []
    for arg in args:
        available.acquire()
        thread = Thread(target=worker, args=(arg,))
        threads.append(thread)
        thread.start()

    for thread in threads:
        thread.join()

6. Problem: too many threads

The code in §5 creates a new thread for every task, and every thread exits after completing its task. This defeats one of the purposes of having a pool of threads, namely that it avoids some of the overhead of creating new threads by reusing the threads in the pool.

The usual approach to implementing a pool of threads is for each thread to execute another task when it is finished (so long as there are more tasks to run). That means that the main thread is going to need a safe way of sending the tasks to the running threads, and Python provides queue.Queue which is exactly what we want:

from queue import Queue
from threading import Thread

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel and wait until all
    calls have completed. max_threads is the maximum number of threads
    that may run simultaneously.

    """
    queue = Queue()

    def worker():
        while True:
            arg = queue.get()
            fun(arg)
            queue.task_done()

    for _ in range(max_threads):
        Thread(target=worker).start()
    for arg in args:
        queue.put(arg)
    queue.join()

7. Problem: threads are left dangling

The problem with the implementation in §6 is that the worker threads never finish! When all the tasks are done, each worker thread is blocked in queue.get waiting for the next task, but it will never arrive. This is a dangerous resource leak because the number of threads that we can create is limited by the operating system, and so to ensure that we can continue to create new threads later in the program, we must clean up all the threads that we started.

So when all tasks are done, we must tell the threads to exit. A convenient way to do that is to pass in a special sentinel argument that is different from any argument that the caller could pass in:

from queue import Queue
from threading import Thread

def apply_in_parallel(fun, args, max_threads=4):
    """Apply fun to each of the arguments in parallel and wait until all
    calls have completed. max_threads is the maximum number of threads
    that may run simultaneously.

    """
    queue = Queue()
    sentinel = object()

    def worker():
        while True:
            arg = queue.get()
            if arg is sentinel:
                break
            fun(arg)

    threads = []
    for _ in range(max_threads):
        thread = Thread(target=worker)
        threads.append(thread)
        thread.start()
    for arg in args:
        queue.put(arg)
    for _ in range(max_threads):
        queue.put(sentinel)
    for thread in threads:
        thread.join()


Bulk HTTP request queue consumer Today I had to write a small tool to help me send HTTP requests in bulk. Rabbit was overloading my server, so I decided to change my consumers to buffer the contents of the request, before sending. After changing my API, I did this:

#include <amqpcpp.h>
#include <amqpcpp/libev.h>
#include <ev.h>
#include <cpr/cpr.h>

typedef std::unordered_map<std::string, std::ostringstream> HttpBuffer;
const char* RabbitQueue = getenv("RABBIT_NAME");
char QueueAddress[128];

int main()
{
    sprintf(QueueAddress, "amqp://%s:%s", getenv("RABBIT_HOST"), getenv("RABBIT_PORT"));

    int MaxThreads = std::thread::hardware_concurrency();
    std::vector<std::thread> threads;

    for (int i = 0; i < MaxThreads; i++) {
        threads.push_back(std::thread(RabbitThread));
    }

    for (std::thread &thread : threads) {
        thread.join();
    }

    threads.clear();
}

void RabbitThread()
{
    struct ev_loop *loop = ev_loop_new(0);
    AMQP::LibEvHandler handler(loop);
    AMQP::TcpConnection connection(&handler, AMQP::Address(QueueAddress));
    AMQP::TcpChannel channel(&connection);

    AMQP::MessageCallback onMessage = [&channel](const AMQP::Message &message, uint64_t deliveryTag, bool redelivered) {
        HttpBuffer[message.replyTo()] << message.message().c_str() << ",";
        if (HttpBuffer[message.replyTo()].tellp() < 300000) {
            channel.ack(deliveryTag);
            return;
        }

        cpr::PostCallback(handle_response, cpr::Url{"http://localhost:8888"}, cpr::Body{HttpBuffer[message.replyTo()].str()});
        HttpBuffer[message.replyTo()].str("");

        channel.ack(deliveryTag);
    };

    channel.declareQueue(RabbitQueue);
    channel.bindQueue("default", RabbitQueue, "default");
    channel.consume(RabbitQueue).onReceived(onMessage);

    ev_run(loop);
    ev_loop_destroy(loop);
}

What do you guys think? How can I improve this one?

I don't know rabbit and have only small nit-picks regarding C++.

emplace

You might consider constructing threads in place instead of moving them to vector.

Instead of:

threads.push_back(std::thread(RabbitThread));

I would try:

threads.emplace_back(RabbitThread);

clear()

Is threads.clear(); in main() necessary?

struct and null pointer

This looks like C-style struct keyword usage. It is very rare to see in C++ (not saying it is wrong).

struct ev_loop *loop = ev_loop_new(0);

This might be also ok and looks more familiar

ev_loop *loop = ev_loop_new(0);

One more thing and this is a wild guess. Is this zero really a NULL pointer?

struct ev_loop *loop = ev_loop_new(0);

This would be more C++11 way:

struct ev_loop *loop = ev_loop_new(nullptr);

hardware_concurrency()

I really have no idea where lies bottleneck in you use case but I suspect it is not CPU bound so maybe you might utilize even much more threads.

int MaxThreads = std::thread::hardware_concurrency();


Fill an array of objects with some default object I have an array of objects. Whatever may be the size of this array, I need to ensure the size of the array as n using a default object.

 function fillRemaining(arr, n) {
        var defaultObject = {'id' : 0, 'name' : ''};
        var temp = 0;
        while(arr.length + temp < n ) {
           var template = $.extend({}, defaultObject);
           template.id = new Date().getTime();
           arr.push(defaultObject);
           temp++;
        }
    }

Is there a better method of doing it?

I see a few ways this can be improved.

First, you are creating the template variable as a copy of the defaultObject, but then you are inserting defaultObject rather than template. I am going to assume this is a bug.

I would also say that there is not a big reason why you should have a defaultObject, then create and modify a copy to add. Just create objects on the fly.

Second, you are using a while loop, but constructing it like a for loop (loop variable, incremented every iteration). You actually don't even use the loop variable, so it can be removed completely. There is also a second potential bug where you are checking against arr.length + temp in your conditional, but arr.length increases every time you add an element to the array, so you are counting by 2's instead of by 1's.

Lastly, the name fillRemaining does not clearly describe what the function is supposed to do. Since it is padding onto the end of the array, perhaps padArrayWithDefault or something similar might be more descriptive.

Here's what I would suggest:

function padArrayWithDefault(arr, n) {
    while(arr.length < n) {
        arr.push({
            "id": new Date().getTime(),
            "name": ""
        });
    }
}


Project Euler Problem 50 in Haskell The prime 41, can be written as the sum of six consecutive primes:

  41 = 2 + 3 + 5 + 7 + 11 + 13
  This is the longest sum of consecutive primes that adds to a prime below one-hundred.

  The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

  Which prime, below one-million, can be written as the sum of the most consecutive primes?

My solution (very fast):

asFarAsPossibleCondition :: (a -> Bool) -> [a] -> Maybe [a]
asFarAsPossibleCondition _ [] = Nothing
asFarAsPossibleCondition f xs = if f $ last xs then Just xs else asFarAsPossibleCondition f $ init xs

maxPrimeSum :: Int -> Int
maxPrimeSum n = snd $ maximumBy (comparing fst) series
    where
        series = map (\x -> (length x, last x)) $ mapMaybe checkSeries [0..10]
        checkSeries x = asFarAsPossibleCondition (isPrime) $ takeWhile (<n) $ scanl1 (+) $ drop x primes

asFarAsPossibleCondition looks for the last element in a list that satisfies a condition then returns that list up to that point (e.g. asFarAsPossibleCondition (<5) [1..10] -> Just [1,2,3,4]. (Note that it differs from takeWhile, since takeWhile will start at the beginning of the list and stops as soon as it encounters an element that does not satisfy the condition. My function starts at the end of the list and looks for the last element that satisfies the condition, regardless of whether there are elements before that that don't satisfy the condition, e.g. asFarAsPossibleCondition (<5) [1,2,3,4,5,6,7,8,9,10,4] -> Just [1,2,3,4,5,6,7,8,9,10,4]. This is useful to check a list of consecutive prime sums (e.g. [2, 5, 10, ...]) and get the longest one that adds to a prime, for instance:

last $ fromJust $ asFarAsPossibleCondition isPrime $ scanl1(+) $ take 20 primes
281

This is the highest consecutive prime sum that results in a prime number that  you can get with x<=20 prime numbers starting from 2 (2+3+5+7+11+13+17+19+23+29+31+37+41+43 = 281).

To start from the next prime, you simply drop the first prime, and so forth, e.g.

last $ fromJust $ asFarAsPossibleCondition isPrime $ scanl1(+) $ take 20 $ drop 1 primes
499

This is the highest consecutive prime sum that results in a prime number that  you can get with x<=20 prime numbers starting from 3.

The rest is fairly obvious; it checks for each starting prime the greatest prime below 1,000,000, gets the length and the prime it adds up to, then gets the prime with the maximum length.

Any advice is welcome, specifically on:

the use of Maybe (I'm just learning about this); is it correct? Justified? ...
how to determine on how many items that I should map the checkSeries function on. ([0..10] was sufficient, but that was simply because I got lucky).
is there a builtin that does what my asFarAsPossibleCondition function does?

Here is my approach:

First some imports:

 {-# LANGUAGE BangPatterns #-}

 module Euler50
 where

 import Math.NumberTheory.Primes
 import qualified Data.IntSet as Set
 import Data.List
 import Debug.Trace

We use the arithmoi library to get the primes:

 myPrimes :: [Int]
 myPrimes = map fromIntegral $ takeWhile (< 1000000) primes

 myPrimeSet :: Set.IntSet
 myPrimeSet = Set.fromList myPrimes

 myIsPrime :: Int -> Bool
 myIsPrime p = Set.member p myPrimeSet

To solve the problem, let's first define a function to produce consecutive sums of a list:

 consecutiveSums0 :: [Int] -> [(Int,Int)]
 consecutiveSums0 ps = scanl step (0,0) ps
   where step (!n,!total) p = (n+1, total+p)

For example, consecutiveSums0 [2,3,5,7] will produce the list:

[ (0,0), (1,2), (2,5), (3,10), (4,17) ]

It will be useful to be able to specify a starting value for the
accumulator, so we'll define:

 consecutiveSums :: (Int,Int) -> [Int] -> [(Int,Int)]
 consecutiveSums start ps = scanl step start ps
   where step (!n,!total) p = (n+1, total+p)

Next, we filter out only the prime sums
which are less than 1000000:

 primeSums :: (Int,Int) -> [Int] -> [ (Int,Int) ]
 primeSums start ps = filter (myIsPrime . snd ) $ takeWhile ( (<1000000) . snd ) $ consecutiveSums start ps

A naive solution to the problem involves repeatedly calling primeSums on the tails of
our list of primes:

 solve0 = maximum $ concat $ map (primeSums (0,0)) (tails myPrimes)

However, there are 78498 primes less than 1000000 and this will examine
approximate 78498^2/2 sums which will take too long.

A better solution involves keeping track of the best solution found so far
and using that to enforce the minimal size of any better solution.
We can stop once the minimal size constraint forces the total of any better
solution to be greater than 1000000.

Our loop will have this structure:

 loop :: [Int]        -- current list of primes
      -> (Int,Int)    -- best solution so far (n, total)
      -> (Int,Int)    -- best solution

The idea is that loop ps b1 will compute a new best solution b2
and then call loop (tail ps) b2 which will compute a new best b3
and call loop (tail (tail ps)) b3 etc. The iteration will stop
when either the primes list is exhausted or the above stopping condition
holds.

An easy case:

 loop [] best = best  -- prime list has been exhausted

We include this just to trace the execution of the function
- it has no effect on the computation:

 loop (p:_) best | trace msg False = undefined
   where msg = "--- p = " ++ show p ++ "  best: " ++ show best

The main definition is:

 loop ps best@(n,total) =
   let (as, bs) = splitAt (n+1) ps -- better solution must have at least n+1 primes
       total0 = sum as
   in
   if total0 >= 1000000
      then best
      else let best' = maximum $ [best] ++ primeSums (n+1, total0) bs
           in
           loop (tail ps) best'

To kick everything off:

 solution = loop myPrimes (0,0)

which results in the followin output:

*Euler50> solution
--- p = 2  best: (0,0)
--- p = 3  best: (536,958577)
--- p = 5  best: (536,958577)
--- p = 7  best: (539,978037)
--- p = 11  best: (543,997651)
(543,997651)

So the longest sum begins at 7 and has length 543 and has sum 997651.
Solving the problem only involves looking at sums which start from the first
five primes.


A ValueService is used to share data among objects I have C# code that makes some calculations for physical models. I have this project class:

public class Project
{
    public IEnumerable<GenericComponent> components;
    private ValueService valueService = new ValueService(Guid.NewGuid().ToString());

    public Project(string norm)
    {
        components = FactoryGenerator.GetFactory(norm).GetComponents();
    }

    public void SetValues(IEnumerable<ValueViewModel> values)
    {
        values.ToList().ForEach(t => valueService.SetValue(t.Key, t.Value));
    }

    public bool Valid(string componentName)
    {
        return components.Where(s => s.Title == componentName).Single().Valid();
    }
}

That creates smaller components that do some calculations. E.g.

public class CrossSectionComponent: GenericComponent
{
    public CrossSectionComponent(ValueService valueService): base(valueService)
    {

    }

    ICrossSectionViewModel crossSection;

    double valuex;

    override
    public bool Valid()
    {
        return valuex > valueService.GetValue<double>("valuey") ? true : false;
    }
}

Each component has a list of values with keys that are unique over the entire model. At the moment I use a ValueService, where each component registers its values with the respective keys. The ValueService can be used to get values from other components in order to do validation calculations.

    private string projectUUID;
    private List<ValueViewModel> values = new List<ValueViewModel>();

    public ValueService(string projectUUID)
    {
        this.projectUUID = projectUUID;
    }

    public void RegisterValue(string key)
    {
        if (!this.hasKey(key))
        {
            values.Add(new ValueViewModel()
            {
                Key = key,
            });
        }
    }

    public void SetValue(string key, object value)
    {
        if (this.hasKey(key))
            this.values.Find(t => t.Key == key).Value = value;
    }

    public T GetValue<T>(string key)
    {
        return (T)values.Find(t => t.Key == key)?.Value;
    }

    private bool hasKey(string key)
    {
        return values.Any(t => t.Key == key);
    }
}

This is part of a stateless API, i.e. for each HTTP request (at the moment) a new Project object is generated and used to make validations.

My API controller looks like this:

    public IActionResult postData([FromRoute] string norm, [FromRoute] string component, [FromBody] ValueViewModel[] data)
    {
        Project project = new Project(norm);
        project.SetValues(data);
        return Ok(project.Valid(component));
    }

The validity of one component does depend in most cases on values of other components. If one wants to check the validity of a components, the use sends a list of values (ValueViewModel[] data), the server creates the project where all available values are stored. Then IF AND ONLY IF all required values are set, the validity can actually be calculated. If not all values are provided inside the "data list", then the validity of said component is false. So there are two cases where component.Valid() => false

The calculations yield false
Not all values have been submitted

My concerns are

When the project continues, the number of components will get quite large, I fear there will be a performance issue if for each request the whole set of components needs to be generated --> should I use LazyLoading?
Is the ValueService approach good to share data between the components? Is there a better solution?

You have built a system of components and shared objects, but don't use its potential. In fact, for your use case the complete setup is an overkill.

There is no component hierarchy
There are no component-sensitive or -specific values
You only need a single component to verify any incoming request

 public IActionResult postData(
        [FromRoute] string norm,
        [FromRoute] string component,
        [FromBody] ValueViewModel[] data)
    {
        Project project = new Project(norm);
        project.SetValues(data);
        return Ok(project.Valid(component));
    }

For the aforementioned reasons, I don't see a need for having a list of components and values. I would rewrite the API to be as simple as possible:

Let the factory retrieved by FactoryGenerator get the requested component
Let that component validate the input values

code:

public IActionResult postData(
        [FromRoute] string norm,
        [FromRoute] string component,
        [FromBody] ValueViewModel[] data)
    {
        var component = FactoryGenerator.GetFactory(norm).GetComponent(component);
        return Ok(component.Valid(data));
    }


Readable implementation of Trie in Python Need reviews on my readable implementation of Trie. Also what other methods can or should be added to this data structure.

from collections import defaultdict

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self, word):
        curr = self.root
        for letter in word:
            node = curr.children.get(letter)
            if not node:
                node = TrieNode()
                curr.children[letter] = node
            curr = node
        curr.end_of_word = True

    def search(self, word):
        curr = self.root
        for w in word:
            node = curr.children.get(w)
            if not node:
                return False
            curr = node
        return curr.end_of_word

    def all_words_beginning_with_prefix(self, prefix):
        curr = self.root
        for letter in prefix:
            node = curr.children.get(letter)
            if curr is None:
                raise KeyError("Prefix not in Trie")
            curr = node
        result = []

        def _find(n, p):
            if n.end_of_word:
                result.append(p)
            for k, v in n.children.items():
                _find(v, p + k)

        _find(curr, prefix)
        return result

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.end_of_word = False

This is the calling client that can be used to test the code.

if __name__ == '__main__':
    trie = Trie()
    trie.add('foobar')
    trie.add('foo')
    trie.add('bar')
    trie.add('foob')
    trie.add('foof')

    print(list(trie.all_words_beginning_with_prefix('foo')))

naming

Your naming is not consistent. sometimes you use letter, sometimes w for the same thing. I generally avoid 1-letter variable names, but if you use them, be consistent

dict.setdefault

using dict.setdefault, you can simplify your Trie.add method significantly

def add(self, word):
    curr = self.root
    for letter in word:
        curr = curr.children.setdefault(letter, TrieNode())
    curr.end_of_word = True

Then you can also change the TrieNode.children to an ordinary dict.

string representation

For debugging, it can be handy to have a string representation of a Node

def __repr__(self):
    return f'TrieNode(end_of_word={self.end_of_word}, children={tuple(self.children)})'

getting a node

Currently, there is no way in your Trie to get a node. Having this method would simplify the rest of the implementation

def __getitem__(self, word):
    curr = self.root
    for letter in word:
        curr = curr.children[letter]
    return curr

def get(self, word):
    return self[word]

If you changed the type of TrieNode.children to a dict instead of a defaultdict, this will raise a KeyError. If you left it at defaultdict, this will return an empty TrieNode: 'TrieNode(end_of_word=False, children=())', check for it, and raise the KeyError yourself

would simplify the rest of the implementation

def __getitem__(self, word):
    curr = self.root
    for letter in word:
        curr = curr.children[letter]
    if not (curr.children or curr.end_of_word):
        raise KeyError(f'{word} not in Trie')
    return curr

trie['foo']

TrieNode(end_of_word=True, children=('b', 'f'))

Search

With the method to get a Node, Search becomes as trivial as

def search(self, word):
    try:
        return self[word].end_of_word
    except KeyError:
        return False

words starting with prefix

This name can be shortened to starts_with.

Here, I would move the iteration to find the 'child-words' to the TrieNode, and recursively descend down the nodes

def child_words(self, prefix=''):
    if self.end_of_word:
        yield prefix
    for letter, node in self.children.items():
        word = prefix + letter
        yield from node.child_words(word)

Trie.starts_with becomes simply:

def starts_with(self, prefix):
    try:
        node = self[prefix]
    except KeyError:
        raise KeyError(f"Prefix `{prefix}` not in Trie")
    return node.child_words(prefix)

which returns the generator yielding words

list(trie.starts_with('foo))

['foo', 'foob', 'foobar', 'foof']

If you want to, you can even add in a inclusive boolean flag

def child_words(self, prefix='', inclusive=True):
    if inclusive and self.end_of_word:
        yield prefix
    for letter, node in self.children.items():
        word = prefix + letter
        yield from node.child_words(word, inclusive=True)

full code

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.end_of_word = False

    def __repr__(self):
        return f'TrieNode(end_of_word={self.end_of_word},' \
               f' children={tuple(self.children)})'

    def child_words(self, prefix='', inclusive=True):
        if inclusive and self.end_of_word:
            yield prefix
        for letter, node in self.children.items():
            word = prefix + letter
            yield from node.child_words(word, inclusive=True)

class Trie_Maarten:

    def __init__(self):
        self.root = TrieNode()

    def add(self, word):
        curr = self.root
        for letter in word:
            curr = curr.children.setdefault(letter, TrieNode())
        curr.end_of_word = True

    def __getitem__(self, word):
        curr = self.root
        for letter in word:
            curr = curr.children[letter]
        return curr

    def get(self, word):
        return self[word]

    def search(self, word):
        try:
            return self[word].end_of_word
        except KeyError:
            return False

    def starts_with(self, prefix, inclusive=True):
        try:
            node = self[prefix]
        except KeyError:
            raise KeyError(f"Prefix `{prefix}` not in Trie")
        return node.child_words(prefix, inclusive)


Python Merge Sort Implementation I doing some algorithm reviews and am soliciting opinions on my implementation of the Merge Sort in Python.

Anything from readability to optimization is fair game.

In particular, I am wondering if accessing the elements of a list using pop(0) somehow slows things down. I am doing this because I am not aware of a good way to peek into the last for the last element.

Note: The code works on both Python 3 and 2.

import math

def merge(left, right):

    merge_result = []

    while (len(left) > 0 and len(right) > 0):
        if left[0] > right[0]:
            merge_result.append(right.pop(0))
        else:
            merge_result.append(left.pop(0))

    while (len(left)):
            merge_result.append(left.pop(0))

    while (len(right)):
            merge_result.append(right.pop(0))

    return merge_result

def merge_sort(array_to_be_sorted):

    if len(array_to_be_sorted) < 2:
        return array_to_be_sorted

    middle = math.floor(len(array_to_be_sorted) / 2)

    left = array_to_be_sorted[0:middle]
    right = array_to_be_sorted[middle:]

    return merge(merge_sort(left),merge_sort(right))

.pop(0) would remove the first element from a list - this is a \$O(n)\$ operation since everything after must "shift" (Time Complexity reference).

I would not pop from left and right subarrays and instead keep track of indexes in both the left and right lists:

def merge(left, right):
    merge_result = []

    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] > right[right_index]:
            merge_result.append(right[right_index])
            right_index += 1
        else:
            merge_result.append(left[left_index])
            left_index += 1

    merge_result += left[left_index:]
    merge_result += right[right_index:]

    return merge_result

And, if you are preparing for an interview, make sure to write this function from memory couple times - it'll persist in your memory pretty soon - focus on the pattern (using left and right indexes for merging), don't try to remember the code line-by-line.


Using SQL to reorder items in a list view - is this efficient? I'm writing an application for work that requires me to process a list of transactions.  The list is small (5 records at the most) and I'm required to display that data in an android ListView. My client has asked that I include the ability to order the list based on the date (I have added ordering it by the amount spent.)

My code uses SQLite queries to get the transactions, from an in-memory database, in the desired order.

public Cursor getAllTransactions(int orderByType)
{
    String orderBy = " order by ";
    switch (orderByType)
    {
        case ORDER_BY_NEWER:
            orderBy += "date(" + KEY_DATE + ") desc";
            break;
        case ORDER_BY_OLDER:
            orderBy += "date(" + KEY_DATE + ")";
            break;
        case ORDER_BY_MOST:
            orderBy += KEY_AMOUNT;
            break;
        case ORDER_BY_LEAST:
            orderBy += KEY_AMOUNT + " desc";
            break;
        default:
            orderBy = null;
    }

    return getAllTransactions(orderBy);
}

The getAllTransactions(orderBy) line executes the SQL command select * from TABLE_TRANSACTIONS appending the order by constraint should it be non-null.

Is this the proper use of SQL? Would it be more efficient (aka faster) to store this data in a standard container (such as List<Transaction>) and then sort them in the desired order?

Enum
First of all, instead of an int orderByType, I would use an enum.
enum SortOrder {
    NEWER("date(" + SomeConstant.KEY_DATE + ") desc"),
    OLDER("date(" + SomeConstant.KEY_DATE + ") asc"),
    ...;
    private SortOrder(String order) {
        this.order = order;
    }

    public String getOrder() {
        return this.order;
    }
}

This will clean up your getAllTransactions method:
public Cursor getAllTransactions(SortOrder orderByType) {
    return getAllTransactions(orderByType == null ? null : orderByType.getOrder());
}

Database vs. Application
I feel that is OK to let the database deal with this. There is a positive aspect of letting it be handled in the application: If the application deals with it, then you can reorder the elements without querying the database.
However,

The list is small (5 records at the most)

I think either way will work just fine. If it is common to reorder the list, then I would let the application deal with it. Although your enum SortOrder needs quite a lot of more code to work directly with a List<T>.
If you want to use an enum and reorder inside the application, then I would let the enum take a Comparator<T> in the constructor and create an anonymous inner class for each enum value.


Autoloader unit test - first attempt I am learning TDD and I want to test my AutoLoader class, what needs to do the next job:

do a check is the namespace is string
do a check, is the path to directory parameter is a string
do a check is the path to directory what I want to load is exists, directory and readable.

There will be more jobs, but I am newbee, so I need your opinion about my test:

<?php

namespace Myframework\Application\Autoloader;

class Autoloader {

    /**
     * @var string
     */
    protected $namespace;

    /**
     * @var string
     */
    protected $path;

    public function __construct($namespace, $pathToClassesDirectory = '') {
        if (!is_string($namespace)) {
            throw new \Exception('Namespace must be string');
        }
        if (!is_string($pathToClassesDirectory)) {
            throw new \Exception('Path to directory parameter should be string');
        }
        if (!file_exists($pathToClassesDirectory) || !is_dir($pathToClassesDirectory) || !is_readable($pathToClassesDirectory)) {
            throw new \Exception('Path to directory is not accessible to read: "' . $pathToClassesDirectory . '"');
        }
        $this->namespace = $namespace;
        $this->path = $pathToClassesDirectory;
    }

}

The class:

    <?php

use PHPUnit\Framework\TestCase;

/**
 * @author vaso
 */
require_once '../system/Application/Autoloader/Autoloader.php';

class AutoloaderTest extends TestCase {

    protected $Autoloader;

    public function setUp() {
        $this->Autoloader = new Myframework\Application\Autoloader\Autoloader(TEST_NAMESPACE, BASE_PATH);
    }

    public function tearDown() {
        unset($this->Autoloader);
    }

    public function testConstructorCall() {
        new Myframework\Application\Autoloader\Autoloader('nameSpaceAsString', BASE_PATH);
    }

    public function testConstructorCallNameSpaceIsNotStringException() {
        $this->expectException('Exception');
        new Myframework\Application\Autoloader\Autoloader(2);
    }

    public function testConstructorCallPathIsNotStringException() {
        $this->expectException('Exception');
        $notStringForPath = new stdClass();
        new Myframework\Application\Autoloader\Autoloader(TEST_NAMESPACE, $notStringForPath);
    }

    public function testIsDirectoryExistsException() {
        $this->expectException('Exception');
        new Myframework\Application\Autoloader\Autoloader('x', 'Failed directory what not exist');
    }

}

Test passed, and my methods are works, I am happy. But I doubt this is not how TDD works even if I follow every requirements.

My questions are:

Is it ok to use constants in test what comes from bootstrap.php to define path?
All of the test ok, but is this the right way to test a constructor? I feel no for some reason, if its ok, please tell me, if not, please tell me why.

I found a lot of resources about TDD, videos, books, but testing the constructor is not in it.

After some research, I've got these answers:

Testing constructor is totally unnecessary if you follow this: Constructor does Real Work. Unit test for units. The constructor only job is to build the object, nothing else, no new objects creation, no initializing, etc...

For constants: I see no reason why do not use constants (for example for a path) to help me to access my classes for tests.


Project Euler #14 - Longest Collatz Sequence in Python I recently solved Project Euler Problem 14 in Python:

  The following iterative sequence is defined for the set of positive
  integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

  Using the rule above and starting with 13, we generate the following
  sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

  It can be seen that this sequence (starting at 13 and finishing at 1)
  contains 10 terms. Although it has not been proved yet (Collatz
  Problem), it is thought that all starting numbers finish at 1.

  Which starting number, under one million, produces the longest chain?

  NOTE: Once the chain starts the terms are allowed to go above one
  million.

But my code takes around 45 seconds to run. I'm looking for some basic ways to make my code more efficient, specifically in the function which calculates each sequence. I have heard in other answers that I should store operations that have already been completed, but how would I do this? I also feel like the method I use for sorting the sequence numbers is clunky and could be optimized.

My code:

import time
start = time.time()

def collatzSeq (n):
    chainNumber = 1
    n1 = n
    while n1 != 1:
        if n1 % 2 == 0:
            n1 = n1/2
            chainNumber += 1
        else:
            n1 = (3*n1) + 1
            chainNumber += 1
    return [chainNumber, n]

fullList = []
for i in range(2, 1000000):
    fullList.append(collatzSeq(i))
sortedList = sorted(fullList, reverse=True)
print(sortedList[:1])

print('Time:', 1000*(time.time() - start))

Memoization

Storing results that have already been computed is known as memoization. Your current function's structure wouldn't work very well since collatzSeq isn't recursive, and you only call it with unique values. After all, the real time savers would be with all the intermediate collatz sequence values.

Restructuring your code to be recursive would make setting up the memoization a lot easier:

def collatz_seq(n):      # no space after function, snake case preferred in python
    if n == 1:           # base case
        return 1
    elif n % 2 == 0:     # recursive definitions
        return collatz_seq(n // 2) + 1     # integer division
    else:
        return collatz_seq(3*n + 1) + 1

Recusion is where you define a function in terms of itself and a base stopping condition.

Now we can easily set up memization using a dictionary:

memo = {}                               # initialize the memo dictionary
def collatz_seq(n):
    if not n in memo:                   # check if already computed
        if n == 1:                      # if not compute it
            memo[n] = 1                 # cache it
        elif n % 2 == 0:
            memo[n] = collatz_seq(n // 2) + 1
        else:
            memo[n] = collatz_seq(3*n + 1) + 1
    return memo[n]                      # and return it

So what's going on here? First we create an empty dictionary called memo. It's crated outside the function so that it persists through each function call. Next check if collatzSeq(n) has already been computed. If not compute the value, and then store it in the memo. Finally return the chached result.

This is great since once a number's collatz sequence length is computed, it never needs to be computed again. This really saves on computation time!

For more memoizaiton info check out this great SO question.

Maximum Stack Depth

Python has a maximum stack depth of 1000 (by default) which sometimes messes with recursive functions if they go too deep. I don't how long the longest collatz sequence under 1000000 is, so I don't know if this is relevent to your problem. But if you run into issues, you can change the maximum depth.


A simple quicksort implementation I have the following class for Quicksorting.

import java.util.Random;

public class QuickSorter {
    public static void main(String[] args) {
        Random random = new Random();
        int[] randoms = new int[10000];
        for(int i = 0; i < randoms.length; i++) randoms[i] = random.nextInt(10000);

        quickSort(randoms, 0, randoms.length);
        System.out.println(Arrays.toString(randoms));
    }

    /** Same as {@link #quickSort(int[], int, int)}, but assumes the whole array should be sorted. */
    public static void quickSort(int[] in) {quickSort(in, 0, in.length);}
    /** Sorts an array of integers using the Quicksort algorithm, in the range [{@code start}, {@code end}).
     * @param in The full array to sort
     * @param start The starting index, inclusive
     * @param end The ending index, exclusive
     * @see #quickSort(int[]) */
    public static void quickSort(int[] in, int start, int end) {
        int pivot = (start + end) / 2;

        /* Temporary array containing the ordered sub-list */
        int[] sub = new int[end - start];
        int left = 0, right = sub.length;

        /* Populate the sub-list */
        for(int i = start; i < end; i++) {
            if(i == pivot) continue;

            if(in[i] < in[pivot]) {
                sub[left++] = in[i];
            } else {
                sub[--right] = in[i];
            }
        }
        /* Add in the original pivot in its new position */
        sub[left] = in[pivot];

        /* Copy back into the original array */
        for(int k = start; k < end; k++) {
            in[k] = sub[k - start];
        }

        /* Translate new pivot position into full list index */
        left += start;
        if(left - start > 0) quickSort(in, start, left);
        /* The start of the right branch should not include the pivot */
        left++;
        if(end - left > 0) quickSort(in, left, end);
    }
}

Is this the most efficient way to Quicksort? I feel as if copying the values from sub back into in can be done better somehow.

And of course, I know this won't cause any huge issues with arrays of size 10000. But, I'd like this to hold up all the way up to 2^31-1 (to the limits of max array size).

Integer overflow

Since you said you cared about array sizes up to the max size, you should know that this line could cause an overflow with two large indices, meaning that pivot could become negative:

    int pivot = (start + end) / 2;

You can fix this by using the following expression instead:

    int pivot = start + (end - start) / 2;

Skip subarrays of length 1

You can do slightly better by ignoring subarrays of length 1, since they are already sorted.  In other words, this line:

    if(left - start > 0) quickSort(in, start, left);

could be:

    if(left - start > 1) quickSort(in, start, left);

The same goes for the right subarray.

In-place version should be faster

Although there is nothing incorrect with your version, it allocates a temporary array and copies elements back and forth.  If you switched to an in-place algorithm, you will reduce your array writes by 50%.  This means that the in-place version should be faster than your current version, assuming you use a proper version that swaps elements from both ends working inwards.