Finding minimal spanning tree of a graph using Kruskal's algorithm I am doing some practice interview questions for class, one of the questions is:

  Given an undirected graph G, find the minimum spanning tree. Function should take in and output an adjacency list.

Here is the code that I have which works using Kruskal's algorithm:

### Question 3 main function and helper functions.
# Within code v = vertice, r = root, e = edge, u = union, m = make, f = find.

# Global Variables for simplifying code.
parent = dict()
rank = dict()

# Find vertices.
def f(v):
    if parent[v] != v:
        parent[v] = f(parent[v])
    return parent[v]

# Make vertices.
def m(v):
    parent[v] = v
    rank[v] = 0

# Creates union between vertices.
def u(v1, v2):
    r1 = f(v1)
    r2 = f(v2)
    if r1 != r2:
        if rank[r1] > rank[r2]:
            parent[r2] = r1
        else:
            parent[r1] = r2
            if rank[r1] == rank[r2]: rank[r2] += 1

# Main Function.
def Question3(G):
    for v in G['vertices']:
        m(v)

    edges = list(G['edges'])
    MST = set()

    for e in edges:
        v1, v2, weight = e
        if f(v1) != f(v2):
            u(v1, v2)
            MST.add(e)
    return MST

G = {
    'vertices': [0, 1, 2, 3, 4, 5, 6, 7],
    'edges': set([
        (1, 6, 5),
        (3, 5, 2),
        (5, 4, 9),
        (4, 2, 3),
        (1, 1, 8),
        (0, 2, 1),
        (2, 3, 6),
        (2, 5, 4),
        (2, 4, 9),
        (2, 1, 7),
        ])
    }

print "Minimum Spanning Tree of G:"
print Question3(G)

# Expected Output.
# Minimum Spanning Tree of G:
# set([(1, 6, 5), (2, 4, 9), (2, 5, 4), (2, 1, 7), (2, 3, 6), (0, 2, 1)])
print """---End Question 3---
"""

Are there any unnecessary bits of code in my solution and/or is there a more efficient way I could be going about this problem?

The first two comments already imparted a negative impression of the code — something you definitely don't want to do in an interview.

# Within code v = vertice, r = root, e = edge, u = union, m = make, f = find.

# Global Variables for simplifying code.

The first comment indicates that your function names are horrible.  The second comment indicates that you don't know how to use variables with the correct scope.

G = {
    'vertices': [0, 1, 2, 3, 4, 5, 6, 7],
    'edges': set([
        (1, 6, 5),
        (3, 5, 2),
        …,
        (2, 1, 7),
        ])
    }

Specifying the vertices is redundant, right?  All of the relevant vertices should already be mentioned as one of the endpoints of an edge.  (And if that is not the case, then you have a lone disconnected vertex, and it would be impossible to make a spanning tree.  Such is the case, in fact, with vertex 7 in your example.)

Furthermore, your Question3() function returns a graph as a set of edges.  It would also make sense that it accepts a graph as a set of edges.

The Question3 function should look more like this:

def kruskal_mst(graph_edges):
    vertex_parents = {
        v: v for v in itertools.chain(*[(v1, v2) for v1, v2, w in edges])
    }
    vertex_ranks = {v: 0 for v in vertex_parents}

    mst = set()
    for e in edges:
        v1, v2, weight = e
        if find(v1, vertex_parents) != find(v2, vertex_parents):
            union(v1, v2, vertex_parents, vertex_ranks)
            mst.add(e)
    return mst

print kruskal_mst([
    (1, 6, 5),
    (3, 5, 2),
    (5, 4, 9),
    …,
    (2, 1, 7)
])

Your code ignores edge weights completely.  (Note that your solution uses the (2, 4, 9) edge rather than the lower-cost (4, 2, 3) edge.  Also, to connect vertex 3 into the MST, it uses the (2, 3, 6) edge rather than (3, 5, 2).)


Since it's easy to convert integer digits to their character values ('0' = 0x30..'9' = 0x39), why not:

public static String stringValueOf(int value) {
  if (value == 0) return "0";
  if (value == Integer.MIN_VALUE) return "-2147483648";

  final boolean negative = value < 0;
  if (negative) value = -value;

  final StringBuilder buf = new StringBuilder();
  while (value != 0) {
    int digit = value % 10;
    buf.append( (char)(0x30 + digit) );
    value = value / 10;
  }
  if (negative) buf.append('-');

  return buf.reverse().toString();
}

It's easy to test this for correctness over the int range; but to do so, I'd extract the StringBuilder construction from the method into a static class variable and just call buf.setLength(0) each time.


Simple socket manager I just wondered if someone could review this socket class for me.

using Apple.Application.Base.Sockets;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Net.Sockets;
using System.Text;
using System.Threading.Tasks;

namespace Apple.Application.Base.Connection
{
    class SocketManager
    {
        private Socket _serverSocket;
        private SocketSettings _settings;

        public SocketManager(SocketSettings settings)
        {
            _settings = settings;
            _serverSocket = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);

            BeginListen();
            BeginAccept();
        }

        public void BeginListen()
        {
            _serverSocket.Bind(_settings.EndPoint);
            _serverSocket.Listen(_settings.SocketBacklog);
        }

        public void BeginAccept()
        {
            _serverSocket.BeginAccept(new AsyncCallback(OnAccept), null);
        }

        public void OnAccept(IAsyncResult AsyncResult)
        {
            try
            {
                _settings._log.Info("New connection was received");
                Apple.GetPlayerManager().RegisterNewPlayer();
            }
            catch (Exception exception)
            {
                _settings._log.Error(exception);
            }
            finally
            {
                BeginAccept();
            }
        }
    }
}

Here is the SocketSettings class:

using log4net;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;

namespace Apple.Application.Base.Sockets
{
    sealed class SocketSettings
    {
        public IPEndPoint EndPoint { get; set; }
        public ushort SocketBacklog { get; set; }
        public ILog _log { get; set; }
    }
}

I'd say, your call to Apple.GetPlayerManager() bothers me. Your socket implementation does not need to know this is a game and it's creating a new player etc. I whould break the relation somehow, passing the payload or event received in your socket to some other service, preferably injected using dependency injection or sth.

This would make your socket class testable on its own (by mockup objects) and other classes much easily.

PS: your SocketSettings class is actually ServerInformation, copy/paste problem I suppose..


Here's my interface, so call me ...maybe I'm inspecting VBA code to find obsolete code constructs - namely explicit Call statements, like this:

Call DoSomething(42)

The "correct" code construct would be to omit the Call token and drop the parentheses - my code locates the obsolete Call statements and rewrites them like this:

DoSomething 42

I have an IdentifierReference class, which I'm using to store the context of various identifier references throughout the VBA code I'm parsing. In order for my code inspection to easily locate method calls that use the obsolete Call syntax, I have added this method to the IdentifierReference class:

public bool HasExplicitCallStatement()
{
    try
    {
        var call = ((dynamic)Context.Parent).CALL();
        return call != null && call.Symbol.Text == Tokens.Call;
    }
    catch (Exception)
    {
        return false;
    }
}

But I didn't like having to handle exceptions here, so I rewrote it in a more strongly-typed way, like this:

public bool HasExplicitCallStatement()
{
    var memberProcedureCall = Context.Parent as VBAParser.ECS_MemberProcedureCallContext;
    var procedureCall = Context.Parent as VBAParser.ECS_ProcedureCallContext;

    return HasExplicitCallStatement(memberProcedureCall)
        || HasExplicitCallStatement(procedureCall);
}

private bool HasExplicitCallStatement(VBAParser.ECS_MemberProcedureCallContext context)
{
    if (context == null)
    {
        return false;
    }
    var statement = context.CALL();
    return statement != null && statement.Symbol.Text == Tokens.Call;
}

private bool HasExplicitCallStatement(VBAParser.ECS_ProcedureCallContext context)
{
    if (context == null)
    {
        return false;
    }
    var statement = context.CALL();
    return statement != null && statement.Symbol.Text == Tokens.Call;
}

And now I wonder... is this really an improvement?

Is there any more elegant way of dealing with different types that should be sharing an interface but aren't? ECS_ProcedureCallContext and ECS_MemberProcedureCallContext are ANTLR-generated types, nested in the VBAParser class, generated from the grammar file I'm using.

Going back to your original code.
I think a little bit of reflection will get you out of the try catch block situation.

public bool HasExplicitCallStatement()
{
    var theObject = ((dynamic) Context.Parent);
    if(theObject.GetType().GetMethod("CALL") != null)
    {
        var call = theObject.CALL();
        return call != null && call.Symbol.Text == Tokens.Call;
    }

    return false;
}


Finding the end of file (EOF) I wrote this code about finding the end of file (EOF).  Please review this.

#include<stdio.h>
#include<conio.h>
void main (void)
{
int x,y,m;
for(x=0;x>=0;x++){
    m=scanf("%d %d",&x,&y);
    if (m!=2 || m==EOF){
    break;
    }
    else printf("/%d/%d/\n",x,y);
}
if (feof ( stdin )){
  printf("End of input\n");
}
else if(m!=2){
  printf("There was an error\n");
}
getch();
}

Let me look at this...first you include the headers, good.

void main (void)
{
    /* snip */
}

Well, for C it's standard to call int main(int argc, char** argv) to facilitate arguments, or if there are no arguments just int main().

This is minor style compaint, not a major problem.

Examining your main function's contents:

    int x,y,m;
    for(x=0;x>=0;x++){
        m=scanf("%d %d",&x,&y); /* NOTE THIS LINE!!! */
        if (m!=2 || m==EOF){
            break;
        }
        else printf("/%d/%d/\n",x,y);
    }

1. This scanf uses STDIN for input, i.e., the user will enter stuff from the command line. Is this what you desire?

I don't think EOF would be entered by the user...

Perhaps you meant fscanf to scan a file for input?

2. So if I enter -9 3 I should expect this for-loop to terminate. Is this the desired behaviour?

On the /* NOTE THIS LINE!!! bit of code, I am suspicious about using sanf(...,&x,...). Again, perhaps this is desired, I don't know.

3. You should also be consistent with the use of brackets for single lines, writing if (...) break; instead. Or change the else to include brackets. But don't include brackets for one, then forget them for the other.

    if (feof ( stdin )){
        printf("End of input\n");
    }
    else if(m!=2){
        printf("There was an error\n");
    }
    getch();
}

4. These lines could be tucked into the for-loop.

5. Avoid using getch() since it's deprecated. If you're just waiting for the user to hit some key to continue, use getchar().

You could have condensed the main function to be:

int main() {
    int m,x,y;
    for(x=0; x>=0; x++) {
        m=scanf("%d %d",&x,&y);
        if (m!=2) { /* note multiple lines always trapped between brackets */
            printf("There was an error!\nHit any key to continue...\n");
            getchar();
            return EXIT_FAILURE;
        } else if (m==EOF) {
            printf("End of input\n");
            break();
        }
        else printf("/%d/%d/\n",x,y); /* single lines don't have brackets */
    }
    printf("Hit any key to continue...\n");
    getchar();
    return EXIT_SUCCESS;
}

The beauty of returning an int is you can have multiple different exit failures, e.g., -1 for bad input, -2 for some other problem, etc.

Addendum

After sleeping on it, I realized some additional style points for C.

A1. You should always initialize your variables! So instead of just writing int m,x,y; we should instead write:

    int m,x,y;
    x=0;
    y=0;
    m=0;

It's something people overlook in C programming.

A2. You could have written a while-loop instead of a for-loop, which may have been more elegant. For example:

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

int main() {
    int m,x,y;
    m = 0;
    x = 0;
    y = 0;
    while (x++ >= 0) {
        m=scanf("%d %d",&x,&y);
        if (m!=2) { /* note multiple lines always trapped between brackets */
            printf("There was an error!\nHit any key to continue...\n");
            getchar();
            exit(EXIT_FAILURE);
        } else if (m==EOF) break();
        else printf("/%d/%d/\n",x,y); /* single lines don't have brackets */
    }
    if (feof(stdin)) printf("End of input\n");
    printf("Hit any key to continue...\n");
    getchar();
    return EXIT_SUCCESS;
}

Note that we immediately terminate when there's an error, as is noted in the C Book in Chapter 1 and Chapter 10.

A3. Observe the only way to leave the while-loop is through (a) scanning an EOF, (b) scanning a "negative enough" number, or (c) through bad data. So we can notify the user of an error immediately, and exit (which is good form).

And the only remaining way to leave the loop is through (a) or (b). But it appears in the OP either case is acceptable, but only for (a) should we notify the user there's the end of input.

A4. Note upon exiting when encountering an error, it's good form to use exit(<error code>). You need stdlib.h to use exit(...) though.


Count the number of ways to make a given sum using one number from each array I have three arrays, each of which contains only numbers. Given a target number, I need to return the number of ways I can make that sum, using exactly one number from each of the arrays.

For example: If I have 2 arrays [[1,2,3], [1,2,3]] and the target sum is 4, I must return the number of combinations that will sum to 4. In this case, they are:

1+3 = 4
2+2 = 4
3+1 = 4

So the function will return 3.

I wrote the function below, and it works well, but I am looking for a way to make more efficient, as well as make it scale to more input arrays - I have less than 6 arrays, but I want it to work if I have a hundred arrays. Is there any array function that can help me here?

This is the code:

<?php
function get_sum ($dice, $sum) {
    $sumcount = array();
    $num_of_dice = count($dice);
    foreach($dice[0] as $die1){
        foreach($dice[1] as $die2){
            if($num_of_dice == 5){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        foreach($dice[4] as $die5){
                            if($die1 + $die2 + $die3+ $die4 + $die5 == $sum){
                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);
                                array_push($sumcount, $good_res);
                            }
                        }
                    }
                }
            }
            if($num_of_dice == 4){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        if($die1 + $die2 + $die3+ $die4 == $sum){
                            $good_res = array();
                            array_push( $good_res, $die1, $die2, $die3, $die4);
                            array_push($sumcount, $good_res);
                        }
                    }
                }
            }elseif ($num_of_dice == 3){
                foreach($dice[2] as $die3){
                    if($die1 + $die2 + $die3 == $sum){
                        $good_res = array();
                        array_push( $good_res, $die1, $die2, $die3);
                        array_push($sumcount, $good_res);
                    }
                }
            }else{
                if($die1 + $die2 == $sum){
                    $good_res = array();
                    array_push( $good_res, $die1, $die2);
                    array_push($sumcount, $good_res);
                }
            }

        }
    };

    echo count($sumcount);
}

get_sum([[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]], 9)
?>

function get_sum ($dice, $sum) {
    ...
    echo count($sumcount);
}

Both the stated specification and the function name say that it will return the count, not print it.

Well, the function name get_XXX says it will return something. If you gave me the signature get_sum ($dice, $sum) and asked me to implement the body I would ask what $dice was for, since the signature clearly says that the body will be return $sum;. Surely there's a better name?

    $sumcount = array();
    ...
    echo count($sumcount);

That's a rather memory-inefficient way of counting something. Why not increment an integer counter instead of adding an array to an array?

                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);

Why not $good_res = array($die1, $die2, $die3, $die4, $die5)?

            if($num_of_dice == 5){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        foreach($dice[4] as $die5){
                            if($die1 + $die2 + $die3+ $die4 + $die5 == $sum){
                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);
                                array_push($sumcount, $good_res);
                            }
                        }
                    }
                }
            }

Again, the aim is to count. If $die1 + $die2 + $die3 + $die4 + $die5 == $sum, why does the loop over $die5 care what $die3 is? You could as well say

foreach ($dice[0] as $die1) {
    $counter += get_sum(array_slice($dice, 1), $sum - $die1);
}

You need to handle a couple of base cases, but that gives you code which should have fairly similar performance to the current code but is much much simpler. Then ask yourself how to memoise. Then ask yourself how to replace the recursion with iteration. The final result will be an iterative method which is about 10 lines long, handles any number of dice, and runs much faster than your current code.


VBA- Retrieving data from an access database by referencing a column in excel I am not able to run the  for loop when number of rows exceed 8-9k.
Can you suggest an alternate method for this? can you suggest the syntax to referencing the data using a tablename(or column name) instead of looping over the cells one by one?

Sub ddd()
Const dbloc As String = "C:\Users\system1\Downloads\Database11.accdb"
Dim db As DAO.Database
Dim rs As DAO.Recordset
Dim xlbook As Workbook
Dim xlsheet As Worksheet
Dim a As Long
Dim SQL As String

Set xlbook = ActiveWorkbook
Set xlsheet = xlbook.Worksheets(1)
xlsheet.Range("B2:Z100000").ClearContents

Set db = OpenDatabase(dbloc)

SQL = "SELECT Material, MPN  "
SQL = SQL & "FROM Sheet2 "

  SQL = SQL & "WHERE Material IN ("
  Dim r As Range
  For Each r In Range("A2:A6768")
   SQL = SQL & r.Text & ","
  Next r
  SQL = Left(SQL, Len(SQL) - 1) 'Drop last comma
  SQL = SQL & ")"

Set rs = db.OpenRecordset(SQL, dbOpenSnapshot)
If rs.RecordCount = 0 Then
MsgBox "No data retrieved from database", vbInformation + vbOKOnly, "No
 Data"
    GoTo SubExit
Else
    rs.MoveLast
    recCount = rs.RecordCount
    rs.MoveFirst
End If
 xlsheet.Range("C2").CopyFromRecordset rs

End Sub

I would suggest that instead of building such a large WHERE clause dynamically, and running into the 64K character limitation of a query's text, that you create a table and insert into it the data from Excel. Your SQL then becomes:

SELECT Sheet2.Material, Sheet2.MPN
FROM Sheet2
INNER JOIN TempSelection
  ON Sheet2.Material = TempSelection.Material

which will work with large amount of selection.

To achieve this, you should create the table TempSelection in Access - it only needs one column, Material of the same data type as the Sheet2 table (is that a linked table to Excel or an actual Access table that was imported from Excel? If imported, good; otherwise, I encourage you to import data instead).

Then your For...Next loop would now look similar to this...

db.Execute "DELETE FROM TempSelection;", dbFailOnError
Set rsTemp = db.OpenRecordset("TempSelection", dbOpenDynaset)
For Each r In Range("A2:A6768")
  rsTemp.AddNew
  rsTemp.Fields("Material").Value = r.Value2 'Or, r.Value if needed
  rsTemp.Update
Next r


ActiveRecord extension to find next / previous record(s) in one query I just wrote this gem order_query to find next or previous records relative to the record assuming a (possibly complex) ORDER BY over the records. For example, this is needed to show a link to the next result from the current search result page.

  The gem is used like so:

class Issue < ActiveRecord::Base
  include OrderQuery
  order_query :order_display, [
    [:priority, %w(high medium low)],
    [:valid_votes_count, :desc, sql: '(votes - suspicious_votes)'],
    [:updated_at, :desc],
    [:id, :desc]
  ]
  def valid_votes_count
    votes - suspicious_votes
  end
end

Issue.order_display         #=> ActiveRecord::Relation<...>
Issue.reverse_order_display #=> ActiveRecord::Relation<...>

p = Issue.find(31).order_display(scope) # scope default: Issue.all
p.items_before  #=> ActiveRecord::Relation<...>
p.prev_item     #=> Issue<...>
p.position      #=> 5
p.next_item     #=> Issue<...>
p.items_after   #=> ActiveRecord::Relation<...>

  Read more

The code gets a complex method warning from CodeClimate, and I agree: it does not look easy to comprehend.

Can this be done better?

This is the code that constructs the query:

# @param [:before or :after] mode
def build_query(mode)
  # The next element will be the first one among elements with lesser order
  build_query_factor(
      order.map { |o| where_relative(o, mode) },
      order.map { |o| where_eq(o) }
  )
end

# @param [Array] x query conditions
# @param [Array] y query conditions
# @return [query, query_args] The resulting query is as follows:
#   x0 | y0 &
#      (x1 | y1 &
#        (x2 | y2 &
#          (x3 | y3 & ... )))
#
# Explanation:
#
#   To narrow the result to only the records that come before / after the current one, build_query passes
#   the values of x and y so that:
#
#   x matches order criteria with values that come after the current record.
#   y matches order criteria with values equal to the current record's value, for resolving ties.
#
def build_query_factor(x, y, i = 0, n = x.length)
  q = []

  x_cond = [x[i][0].presence, x[i][1]]
  q << x_cond if x_cond[0]

  if i >= 1
    q << ['AND'] << y[i - 1]
  end

  if i < n - 1
    q << ['OR'] if x_cond[0]
    nested = build_query_factor(x, y, i + 1)
    q << ["(#{nested[0]})", nested[1]]
  end

  [q.map { |e| e[0] }.join(' '),
   q.map { |e| e[1] }.compact.reduce(:+) || []]
end

EMPTY_FILTER = ['', []]

def where_eq(spec)
  ["#{spec.col_name_sql} = ?", [values[spec.name]]]
end

# @param [:before or :after] mode
def where_relative(spec, mode)
  ord   = spec.order
  value = values[spec.name]
  if ord.is_a?(Array)
    # ord is an array of values, ordered first to last, e.g.
    # all up to current
    pos    = ord.index(value)
    values = mode == :after ? ord.from(pos + 1) : ord.first(pos) if pos
    # if current not in result set, do not apply filter
    return EMPTY_FILTER unless values.present?
    ["#{spec.col_name_sql} IN (?)", [values]]
  else
    # ord is :asc or :desc
    op = {before: {asc: '<', desc: '>'}, after: {asc: '>', desc: '<'}}[mode][ord || :asc]
    ["#{spec.col_name_sql} #{op} ?", [value]]
  end
end

I will stick to reviewing the code you've posted, although it seems tied to other code.

First of all: Use descriptive variable names. x, y, q, and so forth aren't great for legibility. Use query, position and similar full words. Especially since you're dealing with complex nested arrays.

There also seems to be some logical issues/dangerous assumptions. I don't know if you check/sanitize your input elsewhere, but if you don't things will get weird. E.g.:

# This will fail if x[i] is nil
x_cond = [x[i][0].presence, x[i][1]]

q << x_cond if x_cond[0]

if i >= 1
  # 1. This *may* append ["AND"] etc. directly to an empty array,
  #    if x_cond[0] was nil above, resulting in a nonsense query.
  # 2. This will fail if y.count < i - 1
  q << ['AND'] << y[i - 1]
end

In other words, if x_cond[0] isn't present, you don't append anything to the array. Yet the following if block assumes that something definitely was appended. And there's no check for the length of y so y[i - 1] may fail. And x[i][0].presence will fail if x[i] is nil to begin with.

I also see some (dangerous) redundancy, like the n = x.length method parameter. There's no reason for this to be a method parameter. In fact, it's detrimental, because the n value is never checked, so you can pass any value like n = -42 which wouldn't make sense.

Moreover, the code doesn't actually match its description: Your comment for build_query_factory states that the result should be something like:

x0 OR y0 AND (x1 OR y1 AND (x3 OR y3))

but the method returns:

x1 OR (x2 AND y1 OR (x3 AND y2))

Notice that a) the structure is very different, and b) y3 doesn't even appear.

Now, assuming that you want the result you give as an example in the comment (and not the result the method actually returns), I would do something like this:

def build_nested_query(x, y)
  # zip the two arrays (x, y, x, y, x, y, ...)
  ordered = x.zip(y)

  # split into conditions and parameters
  ordered = ordered.map do |x, y|
    [ [x.first, y.first], [x.second, y.second] ] # still confusing, to be honest
  end

  conditions = ordered.map(&:first)
  parameters = ordered.map(&:second).flatten # thanks to ActiveSupport for Array#second, by the way

  [ nest_conditions(conditions) , parameters ]
end

def nest_conditions(conditions)
  # create "x OR y" string
  branch = conditions.first
  branch = branch.join(" OR ")

  # nest the remaining recursively, appending them with " AND "
  remaining = conditions[1..-1]
  if remaining.any?
    nested = nest_conditions(remaining)
    branch += " AND (#{nested})"
  end

  branch
end

That'll do something like this:

x = [["x1", [:x1]], ["x2", [:x2]], ["x3", [:x3]]]
y = [["y1", [:y1]], ["y2", [:y2]], ["y3", [:y3]]]

query = build_nested_query(x, y)
query[0] #=> "x1 OR y1 AND (x2 OR y2 AND (x3 OR y3))"
query[1] #=> [:x1, :y1, :x2, :y2, :x3, :y3]

Which I believe is what you want. You'll want to do some sanity-checking/sanitizing of x and y beforehand, to make sure they make sense.

Of course, if you find a better way to supply the method parameters in the first place, the code can be cleaned up even more.

I would also consider encapsulating conditions and parameters somehow to avoid the non-descriptive [0] and [1] (or first/second) stuff in favor of something more descriptive (Rails no doubt already has an internal class for this structure. Otherwise, a simple Struct-based class should do.)

I haven't looked closely at where_relative, but again I see some strange logic:

def where_relative(spec, mode)
  ord = spec.order

  # I assume `values` is an instance variable?
  # Anyway, why assign `value` here? It's only used in
  # the else-block, and so should be assigned there
  value = values[spec.name]

  if ord.is_a?(Array)

    # ...

    # Wait, now you're assigning something to `values`?
    values = mode == :after ? ord.from(pos + 1) : ord.first(pos) if pos

    # and apparently, that something can be nil, since you're
    # checking for that here - but you didn't check for that
    # before you called `values[spec.name]` above
    return EMPTY_FILTER unless values.present?

    # ...

  else

    # ...

    # And here you use `value` (i.e. values[spec.name])
    ["#{spec.col_name_sql} #{op} ?", [value]]

  end
end

Now, I admit I don't know the exact sequence of events, but the above looks/smells like dangerous assumptions and nasty side effects. If the method is called several times per object instantiation, results get unpredictable. First time it's called, I assume values is set to something. But it might get set to nil by the method. This will cause the next call to the method to crash on values[spec.name]. If the method is so completely dependent on values, it should be a parameter.

Lastly, this line should really be reworked:

values = mode == :after ? ord.from(pos + 1) : ord.first(pos) if pos

Don't use a ternary and postfixed if on the same line - it's very confusing.


Showing all programs' man pages I'm trying to discover useful command line tools in Arch Linux, and it seems one good way of going about that is to look through all of the man pages related to programs (that is, section 1, as in man 1 bash) in local alphabetic order (that is, not overriding the sorting locale with LC_COLLATE=C or similar). This is the simplest (in terms of number of tokens) I've been able to do so far:

man $(man -s 1 -k . | cut -d' ' -f 1 | sort | tr '\n' ' ')

Questions:

Are there any POSIX incompatibilities here? Or any simple way to make this much more cross-platform?
Is there a simpler way to do this? For example, is there a magic man switch to actually show the pages found with -k, rather than printing their summary, or to sort the output?

This question came about because of a suggestion to use

cd /usr/bin
man

to show all the man pages. First, this just responds

  What manual page do you want?

with exit code 1. Second, amending to man * works for some executables, but several of them do not have man pages. Third, this doesn't necessarily give a complete list of section 1, especially in other distros where some tools are only installed in /usr/sbin or /bin.

POSIX.1-2008 only mandates support for the -k option of man, so you can't rely on man having any -s option on a POSIX compatible system, and in fact it is absent in both FreeBSD and Dragonfly BSD. That aside, your command should be reasonably portable barring the following issues:

Some older shells do not support $() for command substitution

Most notably C shell and the original Bourne shell do not support dollar-parentheses expansion. Use `` instead.

Output of man -k may differ between operating systems

On OpenBSD at least, there are no spaces separating the command names and the section numbers in parentheses, so it's probably better to delimit by left parenthesis. But beware of command synonyms that look like byacc, yacc (1) (MINIX), which will produce undesirable results if not further delimited by comma.

man may only display the first manual page found

Again on OpenBSD at least, the default behavior of man is to display only the first manual page found. From the man manual:

  -a Display all of the manual pages for a specified section and name combination. Normally, only the first manual page found is displayed.

Note: this is not POSIX compliant behavior.

man -k . may actually search for the literal . character

Both man -k . and man -k '' should, according to the POSIX specification, match anything in the man database, but this is not the case in OpenBSD, MINIX and SmartOS.

Piping to tr is unnecessary

Unless the IFS variable has been tampered with, the last command of the pipeline is superfluous.

Proposed solutions

Tested OS: Fairly recent versions of CentOS, Kali Linux, Manjaro Linux, openSUSE, Ubuntu, nixOS; OpenBSD, FreeBSD, Dragonfly; SmartOS; MINIX

Tested shells: sh, csh, tcsh, ksh, bash, dash, zsh

There are three ways to search for man pages in a section: man -ssection, man -Ssection or just mansection, presented roughly in the order of decreasing support by the OSes. Linux distros seem to prefer the first way, and BSDs the second. The CentOS man manual also mentions the -s option is for compatibility with System V, so it is the safest bet.

A general solution that works in all tested OSes except FreeBSD and Dragonfly:

man -a -s 1 `man -s 1 -k '(' | awk -F '[,(]' '{print $1}' | sort`

A targeted solution that works in all tested BSDs:

man -a -S 1 `man -k sec~^1$ | awk -F '[,(]' '{print $1}' | sort`

Simplest solution for a specific OS (OpenBSD):

man -a -k sec~^1$ ; # May contain duplicates


Gradient Boosting Class/Module using sklearn. (My first Python Module) This is a follow-up question to My last question. From then on, I think that I have improved quite a lot thanks to a large amount of feedback I received from my last post. This will be the last time I ask for feedback based on this code. I am looking for any feedback on best practices or coding style but to be honest any kind of tip, information or feedback is greatly accepted. This is my first real python module so I can imagine there is quite a bit of strange or simply wrong stuff.

import os.path
import math
from typing import (Tuple, List)

import pandas as pd
import numpy as np

from sklearn import ensemble
from sklearn.externals import joblib
from sklearn.metrics import mean_absolute_error
from sklearn.model_selection import train_test_split

def prepare_dataset(path: str) -> List[pd.DataFrame]:
    df = pd.read_csv(path)
    features = df.drop('days_remaning', axis=1)
    output = df['days_remaning']
    return train_test_split(features, output, test_size=0.3)

class Model():
    def __init__(self, product: str) -> None:
        self.product = product
        self.save_path = f'models/trained_{product}_classifier_model.pkl'
        (self.x_train, self.x_test, self.y_train, self.y_test) = prepare_dataset(
            f'datasets/{product}_dataset.csv')
        if os.path.isfile(self.save_path):
            print(f'Loading Local Model, product: {product}.')
            self.model = joblib.load(self.save_path)
        else:
            print(f'Creating New Model, product: {product}.')
            self.model = self.create_model()

    def create_model(self) -> ensemble.GradientBoostingRegressor:
        '''Create & fit a GB model using GridSearch optimised parameters.'''
        params = dict(
            learning_rate=0.01,
            loss='ls',
            max_depth=4,
            max_features=0.3,
            min_samples_leaf=9,
            n_estimators=500
        )
        model = ensemble.GradientBoostingRegressor(**params)
        model.fit(self.x_train, self.y_train)
        return model

    def use_model(self, data: List[List[int]]) -> np.ndarray:
        return self.model.predict(data)

    def print_model_output(self, data: List[List[int]]) -> None:
        for output in self.use_model(data):
            print('In about {} to {} days you will need to buy new {}.'.format(
                math.floor(output), math.ceil(output), self.product))

    def save_model(self) -> None:
        joblib.dump(self.model, self.save_path)

    def calculate_error_rates(self) -> Tuple[float]:
        train_error = mean_absolute_error(
            self.y_train, self.model.predict(self.x_train))
        test_error = mean_absolute_error(
            self.y_test, self.model.predict(self.x_test))
        return train_error, test_error

    def print_error_rates(self) -> None:
        (train_error, test_error) = self.calculate_error_rates()
        print(f'Training Set Mean Absolute Error: {train_error:.4f}')
        print(f'Test Set Mean Absolute Error: {test_error:.4f}')

    def print_features_importance(self):
        features_labels = np.array(['days_after_restock', 'left_content'])
        importance = self.model.feature_importances_
        features_indexes_by_importance = importance.argsort()
        for feature in features_indexes_by_importance:
            print(
                f'{features_labels[feature]} - {importance[feature] * 100.0:.2f}%')

if __name__ == '__main__':
    EGGS = Model('eggs')
    EGGS.print_error_rates()
    EGGS.print_features_importance()
    EGGS.print_model_output([[2, 7], [7, 2]])

General: docstrings should explain the parameters.

features = df.drop('days_remaning', axis=1)
output = df['days_remaning']

You really ought to put 'days_remaning' into its own variable, declared either via a constant or read in from a configuration file, so that if the field name in your csv changes, you don't have to make the change in multiple places. Similar feeling for the file paths.

       print(f'Loading Local Model, product: {product}.')

This is not output of the program, but just logging its progress. So you should not be using print() but instead the logging module. That way you can configure where the logging goes (and if it's shown at all).

    if os.path.isfile(self.save_path):
        print(f'Loading Local Model, product: {product}.')
        self.model = joblib.load(self.save_path)
    else:
        print(f'Creating New Model, product: {product}.')
        self.model = self.create_model()

This seems odd to me. If the file already exists you load it, but if it doesn't exist you save it? This is actually a race condition since whoever is running this code doesn't know what behavior will happen, based on whether the file exists or is deleted. However I'm not sure what should be done here instead.

    params = dict(
        learning_rate=0.01,
        loss='ls',
        max_depth=4,
        max_features=0.3,
        min_samples_leaf=9,
        n_estimators=500
    )

The dict initializer syntax is more pythonic, and may save a function call.

    params = {
        learning_rate : 0.01,
        loss : 'ls',
        max_depth : 4,
        max_features : 0.3,
        min_samples_leaf : 9,
        n_estimators : 500
    }

but why are you even creating the params variable at all? Just call the function with named parameters!

def print_model_output(self, data: List[List[int]]) -> None:
    for output in self.use_model(data):
        print('In about {} to {} days you will need to buy new {}.'.format(
            math.floor(output), math.ceil(output), self.product))

This doesn't make sense. self.product won't change through this loop. I suspect there shouldn't be a loop at all, as there's never more than one product / output.

def calculate_error_rates(self) -> Tuple[float]:
    train_error = mean_absolute_error(
        self.y_train, self.model.predict(self.x_train))
    test_error = mean_absolute_error(
        self.y_test, self.model.predict(self.x_test))
    return train_error, test_error

This code strongly suggests that instead of two variables y_whatever and x_whatever you should instead have a 2-element tuple called whatever. Then you could get rid of some of this duplicated code.

    features_labels = np.array(['days_after_restock', 'left_content'])

Why an np.array here? What's wrong with a regular list?


Async safe threadpool I'm trying the write a threadpool that can safely be added inside a signal handler or in code forked by multithreaded code. Are there any corner cases that would cause this code to fail? What could be done to improve this code?

#include <pthread.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <semaphore.h>
#include <stdatomic.h>
#include <unistd.h>
#define MAX_WORKERS 16

struct threadpool
{
    _Atomic(int) idle;
    void *(*func)(void*);
    sem_t sem;
    void * arg;
    int id;
    pthread_t thread;
};

struct threadpool threads[MAX_WORKERS] = {0};

void *Worker(void *arg)
{
    int * t = (int*)arg;
x:
    sem_wait(&threads[*t].sem);
    __sync_synchronize();
    threads[*t].func(threads[*t].arg);
    threads[*t].idle = false;
    goto x;
}

bool ThreadPoolNew()
{
    for (int i = 0; i < MAX_WORKERS; i++) {
        threads[i].id = i;
        sem_init(&threads[i].sem, 0, 0);
        pthread_create(&threads[i].thread, NULL, Worker, &threads[i].id);
    }
    return true;
}

bool ThreadPoolAddTask(void *(*entry)(void*), void * arg, bool retry)
{
    _Atomic(bool) found = false;
x:
    for (size_t i = 0; i < MAX_WORKERS; i++) {
        if (__sync_val_compare_and_swap(&threads[i].idle, 0, 1) == 0) {
            threads[i].func = entry;
            threads[i].arg = arg;
            __sync_synchronize();
            sem_post(&threads[threads[i].id].sem);
            found = true;
            break;
        }
    }

    if (found == false && retry == true) {
        goto x;
    }

    return found;
}

void * t1(void *a)
{
    int i = 0;
    while (true) {
        i += 2;
        printf("%i\n", i);
        sleep(5);
    }
}

void * t2(void *a)
{
    int i = 0;
    while (true) {
        i += 3;
        printf("%i\n", i);
        sleep(5);
    }
}

//TESTER CODE
//gcc -pthread list.c

int main(void)
{
    ThreadPoolNew();
    ThreadPoolAddTask(t2, NULL, 1);
    ThreadPoolAddTask(t1, NULL, 1);
    sleep(60);
}

idle

As coded, idle is false when thread is in fact idle. Either rename it to working/running/whatever active or swap the true/false values.
Control flow

Unless I am missing something crucial, there is no need to goto neither in Worker nor in ThreadPoolAddTask.

Similarly, found seems redundant:

do {
    for (i = 0, i < MAX_WORKERS; i++) {
        if (...) {
            ....;
            return true;
        }
    }
} while (retry);
return false;

As a side note, retry shouldn't be handled here. It is a caller business logic when and how to retry. I don't see any value added.
Worker argument

I recommend passing a pointer to a worker instead of pointer to its index. It simplifies both ThreadPoolNew and Worker to:

void *Worker(void *arg)
{
    struct threadpool * t = (int*)arg;
x:
    sem_wait(t->sem);
    __sync_synchronize();
    t->func(t->arg);
    t->idle = false;
    goto x;
}

bool ThreadPoolNew()
{
    for (int i = 0; i < MAX_WORKERS; i++) {
        sem_init(&threads[i].sem, 0, 0);
        pthread_create(&threads[i].thread, NULL, Worker, &threads[i]);
    }
    return true;
}

and removes the need for thread.id. BTW, notice that assert(threads[i].id == i) always holds, so you may post your semaphore as

    sem_post(&threads[i].sem);

You may want to __sync_synchronize() after announcing the thread idle (there is no barrier between setting idle and subsequent sem_wait).


Encoding a list of frequencies as WAV audio This code gets a list of signals with predefined frequency from struc.num

I need to encode it to wave format, so i use this code. This works, but i dont sure it is a correct decision to encode like this in python. Is there any ways to do it better?

def compiler():
    import out
    print("Loaded out.py")
    print("Compiling...")
    lst = list(my_code(out.code))
    print("Compiled!")
    print("Linking...")

    print("Bytes len: ", len(lst), " = ", blen * len(lst))

    music = wave.open('out.wav', 'w')
    music.setparams((2, 1, freq, 0, 'NONE', 'not compressed'))

    for i in lst:
        if (i == "0"):
            packed_value = wave.struct.pack('h', 0)
            for _ in range(100):
                music.writeframes(packed_value)
            continue

        key = i[0:i.find("(")]
        frame = Syntax.struc.num[int(key)]

        duration = 0.05
        samplerate = freq  # Hz
        samples = duration * samplerate
        frequency = frame #Hz
        period = samplerate / float(frequency)  # in sample points
        omega = N.pi * 2 / period

        xaxis = N.arange(int(period), dtype=N.float) * omega
        ydata = 16384 * N.sin(xaxis)

        signal = N.resize(ydata, 400) # 2-й параметр - скорость

        ssignal = b''
        for i in range(len(signal)):
            ssignal += wave.struct.pack('h', int(signal[i]))  # transform to binary

        music.writeframes(signal)

        #packed_value = wave.struct.pack('h', frame)
        #for _ in range(blen):
        #    music.writeframes(packed_value)
    music.close()

print("Linked to out.wav!")

It is hard to tell without knowing how lst is structured, but here is what I can say from what you have shown:

It is safer and cleaner to open files with the with syntax, since it will safely close the file no matter what happens.
It is better to do imports at the top of a module, rather than in a function.
It is a convention to use ALL CAPS for module-level constants, which you appear to have several of here.  This makes it easier to keep track of what is module-level and what isn't.
You re-define certain constants every time through the loop.  It is clearer and faster to define them once outside the loop.
It is a convention to import numpy as np, rather than N.
This would be much easier using scipy.io.wavfile if you can.  I will assume for now that you can't, though.
Although wave has a link to the struct module, it is, as far as I can tell, undocumented.  Even if it was documented, it would be clearer to use the struct module directly.
You potentially re-use the same struct value many times.  It would probably be easier and quicker to define it once and re-use it.
Along similar lines, you write the same value multiple times.  Since it is just a bytes object, it would probably be easier and cleaner to just duplicate the value.  They are small enough that this shouldn't be a problem.
You use i for two different things in the same loop.  Don't do that.  You should use a more informative name for the first i.
You only use a small bit of the i variable.  You should probably strip that off at the beginning.
Rather than finding a particular value in i and then slicing to that, you can just use i.partition('(') to split it at the first '(', then take the first value returned using i.partition('(')[0].
You don't even want the key, you want the frame, or rather the frequency.
You create variables only to immediately re-name them, then never use the original name.  This doesn't have much effect on performance, but it is confusing.
I don't know what my_code produces, but I will assume for my improvement it is an iterable.  If it isn't, then just put the list() wrapper you have now back in.
Is Syntax.struc.num a numpy array?  If it is, then change freqs = np.array([Syntax.struc.num[key] if key else 0 for key in keys]) to freqs = Syntax.struc.num[keys].
If Syntax.struc.num is already numeric, then you can drop the freqs = freqs.astype(np.float).
If you define your frequencies in a numpy array at the beginning, you can also pre-calculate period and omega much faster in a single step rather than at every point in the loop.
Try to avoid "magic numbers", which are seemingly-arbitrary numbers in your code.  They should be named variables for clarity.
You never use duration or samples.
Numpy has a tobytes method that converts an array directly into binary.
You create ssignal, but then write signal instead.  If you can just write numbers, you don't need ssignal at all, right?
I think it would be easier to read in the future if you use the music.set* functions rather than setting everything in one big function.
Are you sure you want the max value to be 16384? 16 bit wave files can handle 32760.

So this is how I would structure your code, assuming you are not able or not willing to use scipy.

import struct
import wave

import numpy as np

import out

def compiler():
    print("Loaded out.py")
    print("Compiling...")
    lst = my_code(out.code)
    keys = (int(ilst.partition('(')[0]) for ilst in lst)
    freqs = np.array([Syntax.struc.num[key] if key else -1 for key in keys])
    freqs = freqs.astype(np.float)
    periods = FREQ/freqs
    omegas = np.pi * 2 / period
    periods = np.floor(periods)
    print("Compiled!")
    print("Linking...")

    print("Bytes len: {0} = {0} ".format(len(periods), BLEN*len(periods)))

    packed_value = np.zeros(100, dtype=np.int16).tobytes()

    maxamp = 2**14
    maxlen = 400
    nchan = 2
    sampwidth = 1
    nframes = 0

    with wave.open('out.wav', 'w') as music:
        music.setnchannels(nchan)
        music.setsampwidth(sampwidth)
        music.setframerate(FREQ)

        for period, omega in zip(periods, omegas):
            if period < 0:
                music.writeframes(packed_value)
                continue

            signal = maxamp * np.sin(np.arange(period)*omega).
            signal = np.resize(signal, maxlen)  # duplicate up to the correct length
            signal = signal.astype(np.int16).tobytes()  # transform to binary

            music.writeframes(signal)

print("Linked to out.wav!")


Linked list in Python which gets values from keyboard What do you think about my implementation of linked list, which gets values from keyboard? I implemented three basic functions: print, insert and size.

class Node:

       def __init__(self):
               self.data = None
               self.next = None

class LinkedList:

       def __init__(self):
               self.head = None

       def insert(self,data):
               data = input("Add an element:")
               node = Node()
               node.data = data
               node.next = self.head
               self.head = node

       def print(self):
               print_list = self.head
               while print_list:
                       print(print_list.data)
                       print_list = print_list.next

       def size(self):
               i=0
               head = self.head
               while head:
                      i+=1
                      head = head.next
               print (i)

  MyList = LinkedList()

  while True:
       print("1. Add an element")
       print("2. Print the list")
       print("3. Size of the list")
       menu = int(input("Choose an action:"))

       if menu == 1:
               MyList.insert(1)
       elif menu == 2:
               MyList.print()
       elif menu == 3:
               MyList.size()

I don't see anything glaring, except for the size method. It has 2 major flaws:

Every time you want to check the size, you must traverse the entire list, giving it a time complexity of O(n) (linear). This would likely be an unacceptable complexity for real world use. I'd expect that a size method would be O(1), meaning the length of time the operation takes  has nothing to do with the number of elements in the list. What if your list contained a million elements and you needed to repeatedly get the size of it?
It prints the size instead of returning it. Rarely should a method print its result; unless that's the sole purpose of the method. Return the result instead of printing it directly so the returned size can actually be used instead of just seen. If you want to print the data, print the return of the function instead. Let the caller of the function decide how the data is used instead of forcing it to be printed.

How can these points be fixed? Instead of calculating the size, give your list an n_nodes (or similar) field, and increment it inside of insert:

def insert(self,data):
    data = input("Add an element:")
    node = Node()
    node.data = data
    node.next = self.head
    self.head = node
    self.n_nodes += 1 # Here

Then just change your size method to return n_nodes. Notice that the number of elements in the list has no effect on the time this method will take to finish:

def size(self):
    return self.n_nodes

Then just print the size at the call site:

...
elif menu == 3:
    print(MyList.size())

Now that I've looked over your insert method though, it suffers from a similar problem: needless use of side-effects. Why ask for the data inside the method via input instead of passing the data in? What if you want to insert data that came from the internet, or from the disk?

Use the data parameter of the insert method to pass the data in, and get rid of the call to input. The data can still come from input, just ask for it outside of the method.


Sum of subset of 5 numbers equals 0 I have a task to print all zero subsets of 5 numbers, input from the console.
I have succeeded in implementing a working code, but it seems it is quite complex (it is like inception) and if the count of the numbers is to be greater, it would be rather pointless to use such a method.

using System;
using System.Collections.Generic;
using System.Linq;

class ZeroSubset
{
    static void Main()
    {
        int number;
        int[] Numbers = new int[5];
        bool result = false;
        for (int i = 0;i <=4; i++)
        {
            here: ;
            Console.WriteLine("Input number {0}", i + 1);
            if (int.TryParse(Console.ReadLine(), out number))
            {
                Numbers[i] = number;
            }
            else
            {
                goto here;
            }
        }

        if (Numbers[0] == 0 && Numbers[1] == 0 && Numbers[2] == 0 && Numbers[3] == 0 && Numbers[4] == 0)
        {
            result = true;
            Console.WriteLine(String.Join("+", Numbers) + " = 0");
            return;
        }

        for (int firstNum = 0; firstNum <= 3; firstNum++)
        {
            for (int secondNum = firstNum + 1; secondNum <= 4; secondNum++)
            {
                if (Numbers[firstNum] + Numbers[secondNum] == 0)
                {
                    result = true;
                    Console.WriteLine("{0} + {1} = 0", Numbers[firstNum], Numbers[secondNum]);
                }
            }
        }

         for (int firstNum = 0; firstNum <= 2; firstNum++)
         {
            for (int secondNum = firstNum + 1; secondNum <= 3; secondNum++)
            {
                for (int thirdNum = secondNum + 1; thirdNum <= 4; thirdNum++)
                {
                    if (Numbers[firstNum] + Numbers[secondNum] + Numbers[thirdNum]== 0)
                    {
                        result = true;
                        Console.WriteLine("{0} + {1} + {2} = 0", Numbers[firstNum], Numbers[secondNum], Numbers[thirdNum]);
                    }
                }
            }
        }

        for (int firstNum = 0; firstNum <= 1; firstNum++)
        {
            for (int secondNum = firstNum + 1; secondNum <= 2; secondNum++)
            {
                for (int thirdNum = secondNum + 1; thirdNum <= 3; thirdNum++)
                {
                    for (int fourthNum = thirdNum + 1; fourthNum <= 4; fourthNum++)
                    {
                        if (Numbers[firstNum] + Numbers[secondNum] + Numbers[thirdNum] + Numbers[fourthNum]== 0)
                        {
                            result = true;
                            Console.WriteLine("{0} + {1} + {2} + {3} = 0", Numbers[firstNum], Numbers[secondNum]
                                    , Numbers[thirdNum], Numbers[fourthNum]);
                        }
                    }
                }
            }
        }

        if (Numbers.Sum() == 0)
        {
            result = true;
            Console.WriteLine(String.Join("+", Numbers) + " = 0");
        }

        if (result == false)
        {
            Console.WriteLine("no zero subsets");
        }
    }
}

I am asking for a more simple approach to this matter.

Using a List<int> instead of int[] allows your code to not only be more dynamic but also to leverage the GetRange method of the List.  This simplifies your code to only 2 loops.

Creating the list would look something like this:

int number;
List<int> Numbers = new List<int>();
for(int i = 0; i <= 4; i++)
{
    number = 0;
    bool good = false;
    while(!good)
    {
        Console.WriteLine("Input number {0}", i + 1);
        if(int.TryParse(Console.ReadLine(), out number))
        {
            Numbers.Add(number);
            good = true;
        }
        else
            Console.WriteLine("Invalid input, try again");
    }

}

The sub routine to get the subsets could look something like this:

public static List<List<int>> AllSubsets2(List<int> mainset, int targetsum)
{
    List<List<int>> outval = new List<List<int>>();
    for(int num2 = 0; num2 < mainset.Count; num2++)
    {
        if(mainset[num2] == 0)
            outval.Add(new List<int>{mainset[num2]});
        int sum = mainset[num2];
        for(int num = num2+1; num < mainset.Count; num++)
        {
            sum += mainset[num];
            if(sum == 0)
                outval.Add(mainset.GetRange(num2, num - num2));
        }
    }

    return outval;
}

This will return a list of all the subsets that add up to the target sum.


Pinging a URL with libcurl I've asked a question about pinging a URL before, but I wanted something that was a bit shorter and still just as efficient.  libcurl seemed to be the perfect answer.  Here is my method:

/**
 * @fn int testConnection(void)
 * @brief Pings "https://www.google.com/" to test if there is an internet connection.  Timeout is set to three seconds.
 * @return Success value if connected to the internet.
 */
int testConnection(void)
{
    CURL *curl;
    CURLcode res = 0;
    curl_global_init(CURL_GLOBAL_ALL);
    curl = curl_easy_init();
    if(curl)
    {
        curl_easy_setopt(curl, CURLOPT_URL, "https://www.google.com/");
        curl_easy_setopt(curl, CURLOPT_CONNECTTIMEOUT, 3);
        curl_easy_setopt(curl, CURLOPT_NOBODY, 1);
        res = curl_easy_perform(curl);
        curl_easy_cleanup(curl);
    }
    curl_global_cleanup();
    return res;
}

Is there anything "wrong" with this pinging method?  Are there any ways that I could make this method more efficient?

Unless you're using C89, I would define variables where they are used (I'm looking at curl).

0 is currently interpreted as CURLE_OK. This means that if cURL fails to initialize, you're returning a success code. That's probably not what you meant to do.

This is a great example of why you should never use plain constants to set the value of an enum. You throw away the entire purpose of the enum when you do that, and lost meaning gives you cases like this.

I would try to hide the cURL dependency. What if you later decide to change to using sockets again? The simplest way to do this would be a simple enum with 3 possibilities: CONNECTION_SUCCESS, CONNECTION_FAILURE, CONNECTION_EXCEPTION. The first two are obvious. The third would be if something other than simple pass/fail happened (cURL can't initialized for example).

This does unfortunately mean you need to do a bit more boiler plate for your error handling, but it means that you can change out the underlying implementation as you please.

Your comment is very vague with regards to return value ("Success value if connected to the internet."). What in the world is a 'success value'? Also, it might be nice to clarify what connecting to the internet means (in this context, it means DNS resolution, connecting and making an HTTP request -- that's a lot more than simple connection).

(Had to pick on you about documentation, of course :p).

I have a lot of reservations about this in general. What if google is down (yeah, yeah, but it can happen!). What if 5 years from now google doesn't exist? What if the user's DNS server enforces Bing (crazy, but you never know). It just seems a really fragile dependency. Unfortunately though, I have no better solution off the top of my head other than check more than 1 site and allow the user to override defaults.


Divisor game cheating aid This code outputs the smallest number with more divisors than the input:

from operator import mul
from math import sqrt, ceil

def next_prime_factor(n):
    if n % 2 == 0:
        return 2
    for x in range(3, int(ceil(sqrt(n)) + 1), 2):
        if n % x == 0:
            return x
    return int(n)

def factor(n):
    factors=[]
    number=int(n)
    while number > 1:
                f=next_prime_factor(number)
                factors.append(f)
                number /= float(f)
                number=int(number)
                if number==1:break

    return list(factors)

def sundaram(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)/2
    initial = 4
    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)

        if initial > half:
            x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]
            return sorted(x)

def factor_count(n):
    factors=factor(n)
    primecounts=[]
    primes_list=sundaram(int(sqrt(n)))
    primes_list = primes_list if primes_list != None else [2]
    for i in primes_list:
        primecounts.append(factors.count(i))
    return primecounts

def div_exps(pcount):
    return [i+1 for i in pcount if i!=0]

def div_count(n):
    pcount=factor_count(n)
    div_count=reduce(mul,div_exps(pcount),1)
    return div_count

def next_num(last_num):
    if last_num == 1:
        return 2
    if last_num in sundaram(last_num+1):
        return 4

    plist=sundaram(int(sqrt(last_num))+1)

    div_count_factors=factor(div_count(last_num))
    num=1
    for i in enumerate(div_count_factors):
        num*=plist[i[0]]**(i[1]-1)

    end_num=num
    while 1:
        if div_count(end_num)<=div_count(last_num):
            end_num*=min(div_count_factors)
        else:
            break
    return end_num

ans=next_num(input('Input the last number chosen: '))
print 'The smallest number with more divisors than the inputted number is',ans,'.'

It was written to help win aid a number game.  The game is simple: somebody says a number, you say a number with more divisors than that number.

You get a point if your number is smaller.  So if Bob says "5", you can say "4" and get a point. The winner is first to 3 points.

This code outputs the next best number given the previous number as input.

Style guide

You should code your Python to follow PEP (Python Enhancement Proposal) documents, and in particular, PEP8.

PEP8

Comparing your code to PEP8's standards shows quite a few violations.

You should have whitespace between your binary operators.

factors=[]
number=int(n)

Two blank lines after a declaration

from operator import mul
from math import sqrt, ceil

def next_prime_factor(n):

Comparison to None: instead of != None it should be is not None

x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]

Line too long: PEP8 has a maximum character count of 79 characters per line, this line has 82:

print 'The smallest number with more divisors than the inputted number is',ans,'.'

while 1 should be denoted as while True instead:

while 1:

Whitespace and naming

You have double indentation here:

while number > 1:
            f=next_prime_factor(number)
            factors.append(f)
            number /= float(f)
            number=int(number)
            if number==1:break

You should avoid names like this:

numbers = range(3, max_n+1, 2)
half = (max_n)/2

Their purpose is a little confusing. Try to use more descriptive names that better describe what they are.

You should name your variables like snake_case:

primecounts

Unnecessary logic

div_count=reduce(mul,div_exps(pcount),1)
return div_count

You're defining a variable right before returning it, just return it directly.

for i in primes_list:
    primecounts.append(factors.count(i))
return v

You can use the list comprehension notation instead:

primecounts = [factors.count(i) for i in primes_list]

if div_count(end_num)<=div_count(last_num):
    end_num*=min(div_count_factors)
else:
    break

When you have a block that looks like this:

if condition == true/false:
    doSomething()
else:
    endBlock #return, break, continue

When the block terminates in the else loop, you can reverse the conditions and reduce a layer of logic:

if condition != true/false:
    endBlock

doSomething()

So, you can simplify that above block down:

if div_count(end_num) > div_count(last_num):
    break

end_num *= min(div_count_factors)

The code after the if is not needed: filter always returns a list, which is empty, if no elements remain. This results in identical behavior to the current code.

x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]


Binary search for random access iterators in C++ I wrote a generic binary search routine in C++ for ranges that are specified by random access iterators. In case the user inputs a range with non-random access iterators, an exception will be thrown. My code is below:

binary_search.h

#ifndef CODERODDE_BINARY_SEARCH_H
#define CODERODDE_BINARY_SEARCH_H

#include <iterator>

namespace coderodde {

    template<typename RandomIt, typename T>
    RandomIt search(RandomIt begin,
                    RandomIt end,
                    T value,
                    std::random_access_iterator_tag)
    {
        RandomIt save_end = end;

        while (begin != end)
        {
            RandomIt middle = begin + ((end - begin) >> 1);

            if (value < *middle)
            {
                end = middle;
            }
            else if (value > *middle)
            {
                begin = middle + 1;
            }
            else
            {
                return middle;
            }
        }

        return save_end;
    }

    template<typename NonRandomIt, typename T>
    NonRandomIt search(NonRandomIt begin,
                       NonRandomIt end,
                       T value,
                       std::input_iterator_tag)
    {
        throw std::runtime_error(
                   "coderodde::search requires random access iterators.");
    }

    template<typename It, typename T>
    It search(It begin, It end, T value)
    {
        return search(begin, end, value, typename std::iterator_traits<It>::iterator_category());
    }
}

#endif /* CODERODDE_BINARY_SEARCH_H */

And the demonstration code is:

#include <iostream>
#include <iterator>
#include <list>
#include <stdexcept>
#include <vector>
#include "binary_search.h"

using coderodde::search;
using std::boolalpha;
using std::cerr;
using std::cout;
using std::end;
using std::endl;
using std::list;
using std::runtime_error;
using std::vector;

int main() {
    cout << "int array:" << endl;
    int arr[] = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
    size_t length = sizeof(arr) / sizeof(arr[0]);
    int* p = search(arr, arr + length, 1);
    cout << "The 1st iterator points to: " << *p << endl;
    p = search(arr, arr + length, 7);
    cout << "The 2nd iterator points to: " << *p << endl;
    p = search(arr, arr + length, 23);
    cout << "The 3rd iterator points to: " << *p << endl;

    p = search(arr, arr + length, 8);

    cout << "8 not found: " << boolalpha << (p == end(arr)) << endl;

    cout << "int vector:" << endl;
    vector<int> vec = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
    vector<int>::iterator it = search(vec.begin(), vec.end(), 1);
    cout << "The 1st iterator points to: " << *it << endl;
    it = search(vec.begin(), vec.end(), 7);
    cout << "The 2nd iterator points to: " << *it << endl;
    it = search(vec.begin(), vec.end(), 23);
    cout << "The 3rd iterator points to: " << *it << endl;

    p = search(arr, arr + length, 8);

    cout << "8 not found: " << boolalpha << (p == end(arr)) << endl;

    try {
        list<int> lst = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
        search(lst.begin(), lst.end(), 4);
    } catch (runtime_error& err) {
        cerr << err.what() << endl;
    }
}

The output is:

int array:
The 1st iterator points to: 1
The 2nd iterator points to: 7
The 3rd iterator points to: 23
8 not found: true
int vector:
The 1st iterator points to: 1
The 2nd iterator points to: 7
The 3rd iterator points to: 23
8 not found: true
coderodde::search requires random access iterators.

As always, any critique is much appreciated.

I wrote a generic binary search routine in C++ for ranges that are specified by random access iterators.

Very good idea.

In case the user inputs a range with non-random access iterators, an exception will be thrown. My code is below:

Bad idea. You are doing a runtime check for something that can be detected by the compiler. This should force a compile time error.
Code Review
template<typename RandomIt, typename T>
RandomIt search(RandomIt begin,
                RandomIt end,
                T value,
                std::random_access_iterator_tag)

No need for the type T here. In fact putting it here is probably a bad idea. As it allows you to search a vector of double with an integer. Now there is not much you can do with compiler standard conversions but at least you can make sure that the value passed to the function has already been converted to the correct type for comparison.
template<typename RandomIt, typename Cat = typename std::iterator_traits<RandomIt>::iterator_category>
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& value,
                std::random_access_iterator_tag)

Also I would not bother passing the fourth parameter that should be a type to the template. Then you can have a template specialization that implements it for random iterators only.
// Generic Declaration with no implementation.
template<typename RandomIt, typename Cat = typename std::iterator_traits<RandomIt>::iterator_category>
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& value);

// Partial specialization for Random Iterator
template<typename RandomIt>
RandomIt search<RandomIt, std::random_access_iterator_tag>(
                RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& value)
{
    // Your implementation here.
}

Now the code will generate a compile time error when you use anything but a random access iterator. With a tiny bit of effort you can do this in a single declaration using the new std::enable_if<> but I leave that as an exercise.
Make Intenet clear
        RandomIt middle = begin + ((end - begin) >> 1);

Not everybody will see >> 1 as a divide by 2. Don't do that it just makes the code unclear. Use the divide operator it express intent much better (and does not have any worse performance).
        RandomIt middle = begin + ((end - begin) / 2);


delete a key in a trie To delete a key from a trie, there are four cases:

For the explanation of trie data structure, please check
the following link:
http://www.geeksforgeeks.org/trie-insert-and-search/

(1) Key is not in the trie.

(2) Key present in the trie as a unique key.

(3) Key is the prefix of another longer key.

(4) Key presents in the trie, having at least one other key as prefix key.

The following code is my implementation of deleting a key from a trie.

struct trie_node
{
    int mark;
    struct trie_node* children[ALPHABET_SIZE];
};

struct trie
{
    struct trie_node* root;
    int count;
};

// check if a trie node has no children
bool isFreeNode(struct trie_node* p)
{
    int i;
    for(i = 0; i < ALPHABET_SIZE; ++i)
    {
        if(p->children[i])
            return false;
    }
    return true;
}

bool isLeafNode(struct trie_node* p)
{
    return p->mark == 1;
}

bool deleteHelper(struct trie_node* root, char* key, int level, int len)
{
    int ind;
    //check if the key is in the trie.
    if(root!=NULL)
    {
        if(level==len)
        {
            //check if the key is in the trie.
            if(root->mark==1)
            {
                root->mark = 0;

                //Is it an unique key?
                            if(isFreeNode(root))
                {
                    return true;
                }
                return false;
            }
        }
        else
        {
            ind = *(key+level) - 'a';
            if(deleteHelper(root->children[ind], key, level+1, len))
            {
                free(root->children[ind]);
                root->children[ind] = NULL;

                //check if the node is an unique key node. Case (2) and
                            //and case (4) can both generates unique key node.
                            if(!isLeafNode(root) && isFreeNode(root))
                {
                    return true;
                }
                return false;
            }
        }
    }
    return false;
}

void deleteKey(struct trie* trie, char* key)
{
    int len = strlen(key);
    if(len>0)
    {
        //check if the key is the only one in the trie
            if(deleteHelper(trie->root, key, 0, len))
        {
            free(trie->root);
        }
    }
}

Check your indentation, mostly for comments. While there are a lots of indent styles for C, none of them recommends removing the spaces after if and for.
Using recursive functions is not the idiomatic way of doing things in C, but that's OK.
It's generally better to check for error conditions before, and handle the general case afterwards. This is a good idea because the "error condition" is generally smaller. For example, if you check for root == NULL case first, the reader doesn't have to remember that there is possibly an else branch. This will also force you to make return false cases more explicit in your if/else branches. I think it's a good thing.
You can write if (root->mark) instead of if(root->mark==1).
This code is too long:

// Is it an unique key?
if (isFreeNode(root))
{
    return true;
}
return false;

Simple write return isFreeNode(root);. Same thing for (!isLeafNode(root) && isFreeNode(root))
*(key+level) should be written key[level].
You don't set trie->root to NULL after freeing it: this is not consistent with the earlier free().


Suitable way for Validating JPA Entities in Spring Boot I have been around in Spring Boot eco-system since 2012, I have worked on many little projects. The most important thing in development I experienced id Validation especially JPA Entities. We simply do validation like:
@Entity
public class Input {

  @Id
  @GeneratedValue
  private Long id;

  @Min(1)
  @Max(10)
  private int numberBetweenOneAndTen;

  @Pattern(regexp = "^[0-9]{1,3}\\.[0-9]{1,3}\\.[0-9]{1,3}\\.[0-9]{1,3}$")
  private String ipAddress;

  // ...

}

as mentioned here, but there is a note highlighted which says :

We usually don't want to do validation as late as in the persistence layer because it means that the business code above has worked with potentially invalid objects which may lead to unforeseen errors...

What is the safe and suitable way of Validating JPA Entities?
I have tried in one of my projects as:
1) Entity class
@Data
@Entity(name = "users")
@NoArgsConstructor
@AllArgsConstructor
@EqualsAndHashCode(callSuper = false)
public class AppUser extends AuditModel{

    private String userFirstName;

    private String userLastName;

    private String userDateOfBirth;

}

2) Dto class
@Data
@AllArgsConstructor
@NoArgsConstructor
@EqualsAndHashCode
public class AppUserDto {

    private Long id;

    @NotNull(message = "First name must not be null")
    @NotBlank(message = "First name must not be blank")
    private String userFirstName;

    @NotNull(message = "Last name must not be null")
    @NotBlank(message = "Last name must not be blank")
    private String userLastName;

    @NotNull(message = "Date of Birth must not be null")
    @NotBlank(message = "Date of Birth must not be blank")
    @Past()
    private String userDateOfBirth;
}

3) Finally Validating Bean to a Spring Service Method
@Service
@Validated
public class AppUserService {

    private final AppUserRepository appUserRepository;

    @Autowired
    public AppUserService(AppUserRepository appUserRepository) {
        this.appUserRepository = appUserRepository;
    }

    public void update(@Valid AppUserDto appUserDto){
        appUserRepository.update(
                appUserDto.getId(),
                appUserDto.getUserFirstName(),
                appUserDto.getUserLastName(),
                appUserDto.getUserDateOfBirth()
        );
    }

}

Is this approach suitable or there is an other better way than that?
Please give your feed back your reviews are precious to me!

The approach is ok, although it depends on the context. If the application receives AppUserDto in the controller layer, doing the validation in the service layer might be too late. Moreover, the service layer will be dependent on the DTO.
If AppUserDto is received in the controller layer (e.g. from a REST API) a good approach is validating the request in the controller layer, mapping the DTO to the entity, and passing it down to the service layer:
@RestController
public class UserController {
    //...

    @PutMapping(value = "/user")
    public void updateUser(@RequestBody @Valid AppUserDto appUserDto) {
        AppUser appUser = toEntity(appUserDto);
        appUserService.update(appUser);
    }

    //...
}

After the validation with @Valid, if there are no errors, toEntity will map the DTO to the entity. The mapping can be done manually or using ModelMapper. More info on this approach here.
In general, DTO validation should be done as soon as possible to prevent internal components to work with invalid objects (as mentioned in the article you linked). Additionally, mapping the DTO to the entity keeps the service layer independent of the particular request so that it can be better reused and tested.


code review for count then sort problems (go lang) the question is simple, for a input [apple, banana, orange, apple, banana, apple], the program will count it as a map: {apple : 3, orange: 1, banana: 2}, then sort this map by it's values, get [(apple, 3), (banana, 2), (orange, 1)]
below is my go version, I'm a go newbie, could you please review it and lecture me how to polish the code? I add a python version for reference

package main

//input, a url.log file, like "apple\nbanana\norange\napple\nbanana\napple\n"
//output, a output.txt file, should be "apple: 3\nbanana: 2\norange: 1\n"
import (
    "fmt"
    "bufio"
    "os"
    "sort"
    "strings"
    "io"
)

func main() {
    m := make(map[string]int)

    // read file line by line
    filename := "url.log"
    f, err := os.Open(filename)
    if err != nil {
        fmt.Println(err)
        return
    }
    defer f.Close()
    r := bufio.NewReader(f)
    for line, err := r.ReadString('\n'); err == nil; {
        url := strings.TrimRight(line, "\n")
        m[url] += 1  // build the map
        line, err = r.ReadString('\n')
    }

    if err != nil {
        fmt.Println(err)
        return
    }

    //sort the map by it's value
    vs := NewValSorter(m)
    vs.Sort()

    // output
    f_out, _ := os.Create("output.go.txt")
    defer f_out.Close()
    var line string
    for i, k := range vs.Keys {
        line = fmt.Sprintf("%s: %d\n", k, vs.Vals[i])
        io.WriteString(f_out, line)
    }

}

type ValSorter struct {
    Keys []string
    Vals []int
}

func NewValSorter(m map[string]int) *ValSorter {
    vs := &ValSorter {
        Keys: make([]string, 0, len(m)),
        Vals: make([]int, 0, len(m)),
    }
    for k, v := range m {
        vs.Keys = append(vs.Keys, k)
        vs.Vals = append(vs.Vals, v)
    }
    return vs
}

func (vs *ValSorter) Sort() {
    sort.Sort(vs)
}

func (vs *ValSorter) Len() int {
    return len(vs.Vals)
}

func (vs *ValSorter) Less(i, j int) bool {
    return vs.Vals[i] > vs.Vals[j]
}

func (vs *ValSorter) Swap(i, j int) {
    vs.Vals[i], vs.Vals[j] = vs.Vals[j], vs.Vals[i]
    vs.Keys[i], vs.Keys[j] = vs.Keys[j], vs.Keys[i]
}

python version:

from collections import Counter

def main():
    count = Counter()
    with open("url.log", "rb") as f:
        for line in f:
            url = line.rstrip()
            count[url] += 1
    with open("output.py.txt", "wb") as f:
        for key, value in count.most_common():
            f.write("%s: %d\n" %(key, value))

if __name__ == "__main__":
    main()

In Go, I would write:

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "sort"
)

type Key string
type Count int

type Elem struct {
    Key
    Count
}

type Elems []*Elem

func (s Elems) Len() int {
    return len(s)
}

func (s Elems) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

type ByReverseCount struct{ Elems }

func (s ByReverseCount) Less(i, j int) bool {
    return s.Elems[j].Count < s.Elems[i].Count
}

func main() {
    m := make(map[Key]Count)
    fi, err := os.Open("keys.txt")
    if err != nil {
        fmt.Println(err)
        return
    }
    defer fi.Close()
    r := bufio.NewReader(fi)
    for {
        line, err := r.ReadString('\n')
        if err != nil {
            if err == io.EOF && len(line) == 0 {
                break
            }
            fmt.Println(err)
            return
        }
        key := line[:len(line)-1]
        m[Key(key)] += 1
    }
    fi.Close()

    e := make(Elems, 0, len(m))
    for k, c := range m {
        e = append(e, &Elem{k, c})
    }
    sort.Sort(ByReverseCount{e})

    fo, err := os.Create("counts.txt")
    if err != nil {
        fmt.Println(err)
        return
    }
    defer fo.Close()
    for _, e := range e {
        line := fmt.Sprintf("%s: %d\n", e.Key, e.Count)
        fo.WriteString(line)
    }
}

Input (keys.txt):

apple
banana
orange
apple
banana
apple

Output (counts.txt):

apple: 3
banana: 2
orange: 1


Profiling script for gathering a lot of data from an API I wrote a script which is supposed to be making requests to an API to gather a lot of data. There is a limit on requests that I can make: about 30 000 in 8 hours otherwise, I will get banned for a significant time. Each object I get from the API can be identified uniquely with a hash. Each API call returns me some data I need and also the hash of the next object I need to get. So I start with some hash I have, make a request, parse the result and obtain the hash of the next object. Repeat. I also log the time of each 20th request I make, recording the time to keep track of the number of the requests I made in last 8 hours.

Here is my code:

import ujson
import requests
import time
import os
import cProfile

# 'logs' has all the requests in the last 8 hours

# the snippet of code which does all of the hard work
for i in range(len(logs) * requests_per_log, maximum_requests):  # to stay in max requests range

    r = requests.get(url + current_hash)
    block = ujson.loads(r.text)  # use ujson because it is faster
    block_timestamp_str = format_timestamp(block['time'])
    block_index_str = str(block['block_index'])

    # only log each 20th request
    if i % 20 == 0:
        f_logs.write(str(time.time()) + '\n')  # log the time when the request was made
    f = open('data/' + block_index_str + "__" + block_timestamp_str, "w+")
    block_string = parse_transactions_in_block(block)
    current_hash = block['prev_block']
    f.write(block_string)
    f.close()
    # record the hash the script stopped at
    f_current_hash.write(current_hash)

# some of the functions it uses:

def parse_transactions_in_block(block):
    block_string = ''
    for transaction in block['tx']:
        block_string += str(transaction['time']) + ',' + str(transaction['tx_index']) \
                        + ',' + str(calc_total_input(transaction)) + '\n'
    return block_string

def calc_total_input(transaction):
    total_input = 0
    for input in transaction['out']:
        total_input += input['value']

# this is the time format I was asked to keep my data in

def format_timestamp(unix_time):
    return time.strftime('%Y-%m-%d-%H-%M-%S', time.gmtime(unix_time))

There is a lot of data to go through, so I want it to be as fast as possible and my previous iterations took a while to run. I am running it on Google Compute Engine using a Linux distribution. Any ideas how I can make this work faster? I don't have enough experience on concurrent computing in Python, so I am just looking for a way of optimizing what I have, without concurrency.

Here are some of the improvements to the current "synchronous" approach:

maintain an instance of the requests.Session() - this would improve performance:

  ..if you're making several requests to the same host, the underlying TCP
  connection will be reused, which can result in a significant
  performance increase

with requests.Session() as session:
    r = session.get(url + current_hash)

use the .json() method to get the JSON object directly out of a response (you would first need to adjust the "json model" to use ujson, source):

requests.models.json = ujson
# ...
block = r.json()

don't open/close files in the main loop - collect the data into memory and dump after. If the data does not fit the memory, use pagination - write to the output file(s) in chunks.
the parse_transactions_in_block() may be rewritten using str.join() and str.format():

def parse_transactions_in_block(block):
    return ''.join("{time},{index},{total}\n".format(time=transaction['time'],
                                                     index=transaction['tx_index'],
                                                     total=calc_total_input(transaction))
                   for transaction in block['tx'])

the calc_total_input() can be rewritten using sum():

def calc_total_input(transaction):
    return sum(input['value'] for input in transaction['out'])

try the PyPy interpreter - can give you a performance boost with no changes to the code (well, I doubt ujson will still work, but simplejson might be a good alternative in this case)

That said, given the information provided in the question, the bottleneck feels to still be the blocking nature of the script. See if you can switch to, for example, Scrapy web-scraping framework, or use the grequests library.


Array Implementation of Stack I've implemented the basic logic of a stack data structure. How can I make this code more generic? Is there any better way to display the stack contents?

StackMethods.java

import java.util.Arrays;

public class StackMethods {
    private int top;
    int size;
    int[] stack ;

    public StackMethods(int arraySize){
        size=arraySize;
        stack= new int[size];
        top=-1;
    }

    public void push(int value){
        if(top==size-1){
            System.out.println("Stack is full, can't push a value");
        }
        else{

            top=top+1;
            stack[top]=value;
        }
    }

    public void pop(){
        if(!isEmpty())
            top=top-1;
        else{
            System.out.println("Can't pop...stack is empty");
        }
    }

    public boolean isEmpty(){
        return top==-1;
    }

    public void display(){

        for(int i=0;i<=top;i++){
            System.out.print(stack[i]+ " ");
        }
        System.out.println();
    }
}

StackReviseDemo.java

public class StackReviseDemo {

    public static void main(String[] args) {
        StackMethods newStack = new StackMethods(5);
        newStack.push(10);
        newStack.push(1);
        newStack.push(50);
        newStack.push(20);
        newStack.push(90);

        newStack.display();
        newStack.pop();
        newStack.pop();
        newStack.pop();
        newStack.pop();
        newStack.display();
    }
}

Good

Naming of parameters and methods follow the naming convention

Bad

not checking input parameter for constructor
not listening to previous answers ( pop() returning nothing )
not using braces {} for every if..else statement

Additional

int size should be final as it won't be changed.
Instead of display() you can override toString() as this is more common.
Instead of writing to System.out you should throw an exception.
give your variables some space to breathe. E.g top=top+1; would be more readable if written like so top = top + 1;


Generating URL and status for an S3 bucket The following program generates the S3 URL and response (status code?) for the key, provided the bucket name and if the S3 URL is a mess (wrong url), then it generates empty string as URL and error as the response.

The code works fine, but the way it handles the messy S3 url seems buggy to me. Please provide some insights to design a better error handling mechanism and a good way to generate the response a.k.a status code?

from boto.s3.connection import S3Connection

class URLGenerator:
    def __init__(self, access_id, access_key, bucket_name, expiry=0):
        """
        Initialization parameters to get url from S3.
        :param access_id: S3 access id
        :param access_key: S3 access key
        :param bucket_name: the name of the bucket to open
        :param expiry: the expiration of the access
        :return: instantiates various attributes
        """
        self.conn = S3Connection(access_id, access_key)
        self.bucket_name = bucket_name
        self.expiry = expiry

    def generate_url(self, k):
        """
        Generates the url by finding the key :param k in the bucket and generates url for it.
        This key is the part of the GET request.
        :param k: the key
        :return: url for the file in S3 and the response for the same,
        """
        resp_dict = {}

        bucket = self.conn.get_bucket(self.bucket_name)

        try:
            key = bucket.get_key(k)
            resp_dict['ok'] = 'success'
            generated_url = key.generate_url(expires_in=self.expiry)
        except AttributeError:
            resp_dict['error'] = "File doesn't exist or check back your S3 URL."
            generated_url = ''
        return generated_url, resp_dict

    def clean_url_and_response(self, id):
        """
        Cleans up the unwanted query methods and authentication tokens in the url generated by
        the self.generate_url() method.
        :param id: the key
        :return: the stripped url and the formatted error or success message based upon the GET request.
        """
        url, resp = self.generate_url(id)
        try:
            url = url.split('?')[0]
        except AttributeError:
            url = ''
        return url, list(resp.values())[0]

    def close(self):
        self.conn.close()

Your code is well-written overall, but the users are going to forget to close the url_connection; I would provide automatic closing by implementing the magic methods __enter__ and __exit__ that allow use with with as a context manager.


Making a decorator with arguments in a flat manner I know you must've been already tired of Python decorators, but this one seems new! There is a common practice of making decorators with arguments.
But Flat is better than nested, so let's flatten it up:

def decorator_with_args(arg):

    def wrapper(*args, **kwargs):
        print('decorated with arg: {}'.format(arg))
        return wrapper.func(*args, **kwargs)

    def wrapper_creator(decorable):
        wrapper.func = decorable
        return functools.wraps(decorable)(wrapper)

    return wrapper_creator

Wrapped func is passed as an attribute, arg - via closure. They don't get overwritten with multiple consequent calls to decorator_with_args.

But not chained ones - functools.wraps will update wrapper's __dict__, overwriting its func attribute like this:

@decorator_with_args('This decorator will be applied')
@decorator_with_args('Others will not')
def gotcha():
    pass

So, attributes are not a good place to store our func. But closure seems to be. Let's use it:

def decorator_with_args(arg):
    func = None

    def wrapper(*args, **kwargs):
        print('decorated with arg: {}'.format(arg))
        return func(*args, **kwargs)

    def wrapper_creator(decorable):
        nonlocal func
        func = decorable
        return functools.wraps(decorable)(wrapper)

    return wrapper_creator

Now it looks good to me! Does it to you? Is it pythonic, idiomatic, correct and nicely performing?

And a real example of making something useful (this is a part to be reviewed):

import functools
import logging
import logging.config

def temp_loglevel(level):
    """
    A decorator for setting temporary loglevel for the scope of
    the wrapped function, then reverting it back on wrapper exit

    Arguments:
        level: new logging level to set
    """
    logger = logging.getLogger()
    func = None

    def wrapper(*args, **kwargs):
        old_level = logger.level
        logger.setLevel(level)
        rv = func(*args, **kwargs)
        logger.setLevel(old_level)
        return rv

    def wrapper_maker(decorable):
        nonlocal func
        func = decorable
        logger.warn(
            "temp_loglevel used, don't forget to "
            "remove it when debugging is done"
        )

        return functools.wraps(decorable)(wrapper)

    return wrapper_maker

logging.config.dictConfig(dict(
    version = 1,
    disable_existing_loggers = False,
    formatters = {
        'default': {
            'format': '%(asctime)-15s [%(levelname)s] %(message)s'
        }
    },
    handlers = {
        'std': {
            'level': 'DEBUG',
            'class': 'logging.StreamHandler',
            'formatter': 'default'
        }
    },
    root = {
        'handlers': ['std'],
        'propagate': False,
        'level': 'INFO'
    }
))

@temp_loglevel(logging.DEBUG)
def print_debug():
    logging.getLogger().debug('This should be visible')

if __name__ == '__main__':
    print_debug()

I would be glad if you put some critique of my code styling as well!

I've found a couple bugs - lack of exception support and it doesn't work with generators. Well, it does in a way, but not the way someone would expect it to.

To fix aforementioned issues, decorator have been changed into this (nevermind Python 2.7 compatibility modifications):

def temp_loglevel(level):
    """
    Decorator to set temporary loglevel for the scope of this function
    (then revert it back on wrapper exit)

    Arguments:
        level: new logging level to set
    """
    logger = logging.getLogger()
    p_closure = dict(func=None)

    def wrapper(*args, **kwargs):
        old_level = logger.level
        logger.setLevel(level)
        try:
            rv = p_closure['func'](*args, **kwargs)
            if isinstance(rv, types.GeneratorType):
                def wrapper_gen():
                    # wrapper's finally block overrides initial setLevel after
                    # returning a generator object
                    logger.setLevel(level)
                    try:
                        for x in rv:
                            yield x
                    finally:
                        logger.setLevel(old_level)

                return wrapper_gen()
            else:
                return rv
        finally:
            logger.setLevel(old_level)

    def wrapper_maker(decorable):
        p_closure['func'] = decorable
        logger.warn(
            "temp_loglevel used, don't forget to "
            "remove it when debugging is done"
        )

        return functools.wraps(decorable)(wrapper)

    return wrapper_maker

P.S. After thinking about how ugly would a flat version of wrapper_gen be, I've made a mental note to myself: "flat is better than nested", but if you absolutely need to make something nested, do it FFS!


Strictly typed JSON representation I would like to be specific in parameter types or write something like this:

Test test = (Json<Test>)"{\"age\": 46}";

Where:

public class Test
{
    public int Age { get; set; }
}

My helper is:

public struct Json<T>
{
    public static implicit operator string(Json<T> json) => json.JObject.ToString();
    public static explicit operator Json<T>(string json) => new Json<T>(json);

    public static implicit operator T(Json<T> json) => json.JObject.ToObject<T>();
    public static implicit operator Json<T>(T obj) => new Json<T>(JObject.FromObject(obj));

    static readonly JObject Default = JObject.FromObject(new { });

    Json(string json) : this(JObject.Parse(json)) { }
    Json(JObject jObject) : this() => _jObject = jObject ??
        throw new ArgumentNullException(nameof(jObject));

    JObject JObject => _jObject ?? Default;
    readonly JObject _jObject;
}

The missing part is a JsonConverter:

[JsonConverter(typeof(JsonTConverter))]
public struct Json<T>
{

And:

public class JsonTConverter : JsonConverter
{
    public override bool CanConvert(Type objectType) =>
        objectType.IsConstructedGenericType &&
        objectType.GetGenericTypeDefinition() == typeof(Json<>);

    public override object ReadJson(JsonReader reader, Type objectType, object existingValue, JsonSerializer serializer) =>
        Activator.CreateInstance(objectType, reader.Value);

    public override void WriteJson(JsonWriter writer, object value, JsonSerializer serializer) =>
        writer.WriteValue(value.ToString());
}