std::string implementation Following is my attempt for a simple implementation for the std string class. Please review my changes and share your feedback.

string.h

class string
{
    char *pcString;
    int iCapacity;
    const static int npos = -1;
public:
    string(void);
    string(int);
    string(const char*);
    string(const string&);
    string& string::operator=(const string &strInstance);
    string& string::operator+(const string &strInstance);
    int find(const char*);
    bool empty() const;
    int size() const;
    char* data() const;
    ~string(void);
};

string.cpp

#include "string.h"
#define INITIAL_SIZE 15

/* Default Constructor */
string::string(void)
{
    pcString = new char[INITIAL_SIZE];
    memset(pcString, 0, INITIAL_SIZE);
    iCapacity = INITIAL_SIZE;
}

string::string(int iSize)
{
    pcString = new char[iSize];
    memset(pcString, 0, iSize);
    iCapacity = iSize;
}

string::string(const char *pcValue)
{
    if(pcValue)
    {
        int iSize = strlen(pcValue) + 1;
        pcString = new char[iSize];
        memset(pcString, 0, iSize);
        iCapacity = iSize;
        memcpy(pcString, pcValue, strlen(pcValue));
    }
}

/* Copy Constructor */
string::string(const string &strInstance)
{
    if(strInstance.empty() == false)
    {
        this->pcString = new char[strInstance.size() + 1];
        this->iCapacity = strInstance.size() + 1;
        memset(this->pcString, 0, this->iCapacity);
        memcpy(this->pcString, strInstance.data(), this->iCapacity);
    }
}

/* empty() */
bool string::empty() const
{
    if(this->pcString)
    {
        if(memcmp(this->pcString, "", strlen(this->pcString)) == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

/* '=' operator */
string& string::operator=(const string &strInstance)
{
    if(strInstance.empty() == false)
    {
        this->iCapacity = strInstance.size() + 1;
        delete this->pcString;
        this->pcString = new char[this->iCapacity];
        memset(this->pcString, 0, this->iCapacity);
        memcpy(this->pcString, strInstance.data(), this->iCapacity - 1);
    }
    return *this;
}

/* '+' operator */
string& string::operator+(const string &strInstance)
{
    int iNewSize = strInstance.size() + this->size() + 1;
    char *pcTemp = new char[iNewSize];
    _snprintf(pcTemp, iNewSize, "%s%s", this->data(), strInstance.data());
    string *pStrResult = new string(pcTemp);
    return *pStrResult;
}

/* size() */
int string::size() const
{
    if(this->pcString)
    {
        return strlen(this->pcString);
    }
    else
    {
        return 0;
    }
}

/* data() */
char * string::data() const
{
    if(this->pcString)
    {
        return this->pcString;
    }
    else
    {
        return NULL;
    }
}

int string::find(const char *pcInputString)
{
    char *pcSubstrResult = strstr(this->pcString, pcInputString);
    if(pcSubstrResult)
    {
        return (this->size() - strlen(pcSubstrResult));
    }
    else
    {
        return string::npos;
    }
}

string::~string(void)
{
    delete this->pcString;
}

Size

The biggest thing that sticks out is that your string does not have a length member. So when testing for empty or size you have to scan the string to find the result (you don't actually need to do it for empty but you do).

Would it not be easier to keep track of the string length in a member and just return it?

Resetting Memory

    memset(this->pcString, 0, this->iCapacity);
    memcpy(this->pcString, strInstance.data(), this->iCapacity - 1);

Setting memory to zero then copying over it with new values seems completely redundant. Just copy the data into the memory you want.

Because you don't have an explicit length setting memory to zero in other places is required (but do you need to set the whole array to zero? Why not jus the first element. In C-Strings the '\0' character is the string terminator. So if the first character is '\0' then the string is empty and has length zero. At this point what the other characters hold is irrelevant.

Also you are using C functions to do your copying. Use the much better C++ functions. These will use the fastest technique to copy the current type.

std::copy(strInstance.pcString, strInstance.pcString +  strInstance->iCapacity,
          pcString);

Default Parameters

Your first two constructors are identical. You should DRY up your code and use a single constructor. The difference is one has zero parameters and the other takes none and defaults the size:

string::string(void)   // By the this is correct. BUT not often used in C++
                       // The empty list has exactly the same meaning.
{
    pcString = new char[INITIAL_SIZE];
    memset(pcString, 0, INITIAL_SIZE);
    iCapacity = INITIAL_SIZE;
}

string::string(int iSize)
{
    pcString = new char[iSize];
    memset(pcString, 0, iSize);
    iCapacity = iSize;
}

By using a default parameter you can write this in one function:

class string
{
     public:
        string(int iSize = INITIAL_SIZE); // Now you only need to write it once
                                          // If used with zero parameters the
                                          // the compiler will call this
                                          // constructor and use the default value.
}

Using this

This is a sign of bad code design.

You only need to use this if you have shadowed variables. If you have shadowed variables you are writing code that is hard to read and understand because you are using the same name to represent different objects.

So stop using this and turn your compiler warnings up so that it warns you about shadowed variables and then use meaningful unique variable names so that it is obvious what you are doing.

Uninitialized Objects

If your input is not what you expect you don't initialize the object.

string::string(const char *pcValue)
{
    if(pcValue)
    {
         // INIT CODE
    }
}
string::string(const string &strInstance)
{
    if(strInstance.empty() == false)
    {
         // INIT CODE
    }
}

Notice in both these cases there is no else. So if you don't fit the condition you do no work. Note in C++ unless you explicitly set the value it has an indeterminate value. Attempting to read an indeterminate value is Undefined Behavior. In your constructors you should explicitly try and set all members (Note: Members that have constructors will be initialized but POD objects don't have constructors int/float/pointers etc...).

Initializer List

You should prefer to use the initializer list in your constructor to set up members. In your code it does not matter because all your members are POD but it is a good habit to get into for all members because when they are not POD (or if somebody changes the type of you member to non POD) this will cause a lot of extra code. This is because the members are initialized by their constructor (if they have one) before the constructor is entered from the initializer list. If you don't explicitly put them in the list the compiler will add them using their default constructor. Subsequent assignment in the constructor code will use the assignment operator for that object.

string::string(int iSize)
    : pcString(new char[iSize])    // Initializer list
    , iCapacity(iSize)
{
    pcString[0] = '\0'; // Only setting the first char
}

Boolean Tests

If a value or expression is boolean. You don't need to test it against true/false. That's its value already.

    if(strInstance.empty() == false)

    // I would just write

    if (!strInstance.empty())   // The whole point in giving it a reasonable
                                // name like empty() is to make the code more
                                // readable in situations like this.

Destructor

string::~string(void)
{
    delete this->pcString;
}

You used the wrong delete. Because you used new [] you must use delete [] to release the memory.

string::~string(void)
{
    delete [] pcString;
}

Assignment operator

string& string::operator=(const string &strInstance)
{
    if(strInstance.empty() == false)
    {

So if the other string is empty() you are not going to do anything. I think that is a bug. If the other string is empty then this string should also become empty.

        delete this->pcString;  // missing [] see notes on destructor
        this->pcString = new char[this->iCapacity];

You correctly delete the pcString before re-use. BUT what happens if the call to new char[] fails? This can potentially throw an exception. If sombody catches that exception further down the road then you now have an object with pcString pointing at deallocated memory. Not a good idea.

When reallocating. You first allocate the new memory (make sure it works). if it does then you can delete your old memory. It should look like this:

string& string::operator=(const string &strInstance)
{
     // Step 1:
     // Do dangerous work into temporaries.
     // If this fails and throws an exception your object is
     // still in a good state.
     char* newPcString = new char[strInstance.iCapacity];
     std::copy(strInstance.pCString, strInstance.pCString + strInstance.iCapacity,
               newPcString);

     // Step 2:
     // Swap the temporaries and your internal state in an exception safe way
     std::swap(newPcString, pcString);
     this->iCapacity  = strInstance.iCapacity;

     // Step 3:
     // Now release the old memory. In this case it is not dangerious.
     // But if the objects in the array had destructors it could be dangerious.
     // This is why we do it after the state of the object has been completely
     // changed.
     delete [] newPcString; // Note the swap in Step 2.

     return *this;
}

OK. So that is the long way around of doing it. But there is a technique called the copy and swap idiom. That automates Step 1 and Step 3. So all you have to do is write Step 2.

string& string::operator=(string strInstance)
{
     std::swap(strInstance.pcString, pcString);
     this->iCapacity  = strInstance.iCapacity;
     return *this;
}

Where did Step 1 and 3 go? If you look at the parameter strInstance. You will notice that we passed it by value. This causes a copy of the original to be created (this is step1) and when the function exits the destructor is called and the parameter is destroyed thus invoking Step 3.

Operator +

Operator + is not doing what I expect it to.

string& string::operator+(const string &strInstance)

I would expect operator + to return a completely new object with the strings concatenated. What you have implemented is what I would expect the function operator+= to implement (because you are returning a string reference). If you want to return a new object then you should return by value (drop the &). Yes it looks inefficient to do so but the compiler will see this and perform RVO optimization to elide the copy).

If you look at this in some code.

string    bred   = "bred";  // calls the correct constructor.
string    butter = "butter"

toast(bred + butter);

std::cout << bred.data() << "\n";  // This prints "bredbutter"
                                   // This is not what I expect because
                                   // I have made no assignment to bred.

toast(bred += butter);             // Here I see an assignment so I am
                                   // OK with bred changing.

So I would change the operator to +=. Note writing operator+ in terms of operator+= is trivial.

Having a look at your code for operator+. It looks like you were actually trying to do it correctly. Couple of gotchas.

{
    int iNewSize = strInstance.size() + this->size() + 1;
    char *pcTemp = new char[iNewSize];
    // This is leaked.
    // Also efficient as you are going to call new inside the constructor.

    _snprintf(pcTemp, iNewSize, "%s%s", this->data(), strInstance.data());
    string *pStrResult = new string(pcTemp);
    // You are dynmaiclly allocating a new object here.
    // But you return by refernece.
    // So there is no where to delete this object.

    return *pStrResult;
}

// This is how I would do it.

string string::operator+(string const& strInstance)
{
    // Create a new string object with enough space.
    string    result(size() + strInstance.size() + 1);

    std::copy(pcString, pcString + size(), result.pcString);
    std::copy(strInstance.pcString, strInstance.pcString + strInstance.size()
              result.pcString + size());
    result.pcString[size() + strInstance.size()] = '\0';

    // Don't worry about returning by value.
    // NRVO will kick in and elide the copy and build this object in place
    // at the destination.
    return result;

}


Cleaning up a multi-model view in Rails3 I'm new to rails and have built a multi-model form. It's working, but some of the code doesn't feel right.

The model code is below. I'm using Devise for my user authentication:

# models/signup.rb
class Signup < ActiveRecord::Base
  has_one :company
  accepts_nested_attributes_for :company
end

# models/company.rb
class Company < ActiveRecord::Base
  belongs_to  :signup
  has_many    :users

  accepts_nested_attributes_for :users
end

# models/user.rb
class User < ActiveRecord::Base
  devise :database_authenticatable, :confirmable, :recoverable,
    :rememberable, :trackable, :validatable, :registerable

  attr_accessible :email, :password, :password_confirmation

  belongs_to :company
end

My view is fairly standard and follows the typical pattern for multiple models. The most important code is the initial Signup creation which is done via the following helper:

# signup is created via signups#new
def setup_signup(signup)
  signup.company ||= Company.new
  if signup.company.users[0] == nil
    1.times { signup.company.users.build }
  end
  signup
end

I had to add a condition to not create additional users, because if the form validation failed it would create another user.

Finally my controller code looks like this:

# controllers/signups_controller.rb
class SignupsController < ApplicationController
  respond_to :html

  def new
    @signup = Signup.new
  end

  def create
    @signup = Signup.new(params[:signup])

    # The first user to signup for a company should be an admin user
    # But this feels really awkward
    @signup.company.users.first.admin = true

    # Skip confirmation for the first user to signup
    @signup.company.users.first.skip_confirmation!

    if @signup.save
      sign_in_and_redirect(@signup.company.users.first)
    else
      render :action => "new"
    end
  end
end

This is what feels wrong to me:

When signing up to my website, there will only ever be a single User created. However, because a user is associated via a Company, and a Company has_many users I have to access this user in an awkward manner: signup.company.users.first. Obviously I could create an instance variable user = signup.company.users.first, and if that's the best solution, I'll take it, but it feels like there should be a better solution.
The setup_signup helper method requires checking if a user has already been created so a second user isn't created: if signup.company.users[0] == nil. To me if feels like Rails ought to have a cleaner way of handling this.
It feels like my create action is too fat for a controller, and that there ought to be a better way to set the admin boolean.

Am I right? Are there cleaner ways to accomplish these tasks?

Firstly (and yes I did read the comments) the signup model seems unessential.

So firstly we should do away with that, if you need to associate payment details then that could easily be done directly on the company model.

Secondly you controller is getting a bit cuddly. In favour of having "fat model, skinny controller" let's move all that signup logic into the company model in the form of a Company::register method.

So far we have changes like this:

# app/models/company.rb
class Company < ActiveRecord::Base
  has_many :users
  accepts_nested_attributes_for :users

  def self.register(params)
    company = self.new(params)

    company.users.first.admin = true
    company.users.first.skip_confirmation!

    if company.save
      company
    else
      false
    end
  end
end

Now your controller can look like this:

# app/controllers/companies_controller.rb
class CompaniesController < ApplicationController

  def new
    @company = Company.new
  end

  def create
    if @company = Company.register(params[:company])
      sign_in_and_redirect(@company.users.first)
    else
      render :new
    end
  end
end

I'm also pretty sure that it's unessential to use that helper you have above. The form builder should be able to work it out from the model accepting nested attributes.


Trim a string to a given start and end Are there any other more exotic ways ... or is this one just good?

void strdev (char *str, long from, long to)
{
    char *part1 = malloc(strlen(str) - strlen(&str[from]));
    long i;

    part1[from] = '\0';

    //for(i=0; i<from; i++) part1[i] = str[i]; // Old copying
    memmove(part1, str, from); // New copying
    sprintf(str, "%s%s", part1, &str[to+1]);
    free(part1);
}

Interface

To design functions that other programmers will find useful, it helps to draw inspiration from conventions established by existing string libraries.

In C, as in other languages with array indices numbered from 0, it is customary to use inclusive-exclusive ranges.  from would be the index of the first byte to delete; to would be the index of the first byte to keep.  That has the nice property that to - from indicates the number of characters to be deleted.  That convention would echo the String.substring(beginIndex, endIndex) function that Java offers, for example.

Another common convention in C would be to accept parameters (str, from, len) — the last parameter specifying the number of bytes to remove.

Finally, you should study Perl's splice function and JavaScript's array.splice(), which are generalized versions of this function.

Implementation

Starting from the top…

void strdev (char *str, long from, long to)

The name strdev doesn't mean anything to me.  I suggest splice_away.

    char *part1 = malloc(strlen(str) - strlen(&str[from]));

You call strlen() twice, when you don't need to call it at all.  malloc(from) will do.  Since strlen() works by visiting every byte in the string, you should avoid calling it carelessly.

    long i;

i is no longer used.  Prune the dead code.

    memmove(part1, str, from); // New copying

part1 is newly allocated memory, and is guaranteed not to overlap with the source string.  Therefore, memcpy() will do.

    sprintf(str, "%s%s", part1, &str[to+1]);

Whoa! Why are you overwriting the initial part of the string with the same characters?  You didn't need to do any of that previous work.

The whole function can be condensed down to

char *splice_away(char *str, int from, int to)
{
    memmove(str + from, str + to, 1 + strlen(str + to));
    return str;
}

I've used the inclusive-exclusive range convention mentioned above, and added return str for the caller's convenience.


Find Median of Two Sorted Arrays in JS The task
is taken from leetcode

  There are two sorted arrays nums1 and nums2 of size m and n
  respectively.

  Find the median of the two sorted arrays. The overall run time
  complexity should be O(log (m+n)).

  You may assume nums1 and nums2 cannot be both empty.

  Example 1:

  nums1 = [1, 3]

  nums2 = [2]

  The median is 2.0

  Example 2:

  nums1 = [1, 2]

  nums2 = [3, 4]

  The median is (2 + 3)/2 = 2.5

My solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let i1 = i2 = 0;
  let smallest, valBefore;
  const pivot = Math.floor((nums1.length + nums2.length) / 2);

  while (nums1[i1] || nums2[i2]) {
    smallest = (nums2[i2] === void 0 || nums1[i1] < nums2[i2])
      ? nums1[i1++]
      : nums2[i2++];

    if ((nums1.length + nums2.length) % 2) {
      if (pivot === i1 + i2 - 1) {
        return smallest;
      }
    } else {
      if (pivot - 1 === i1 + i2 - 1) {
        valBefore = smallest
      }
      if (pivot === i1 + i2 - 1) {
        return (smallest + valBefore) / 2;
      }
    }
  }
};

This is the first idea that I had and it reached 99th percentile. I guess you can't take this evaluation seriously. And I'm sure there's a better solution.

The 99th percentile is due to the linear nature of your approach. The goal of this exercise is to figure out a logarithmic one.

I don't want to spell out the algorithm entirely. Just a hint to get you started. Take a middle element of nums1. Find its lower bound in nums2; call it i2. In the sorted array the selected element would be at the position nums1.length/2 + i2. I hope the hint is a good enough.

pivot doesn't look like a good name to me. totalLength, perhaps?

The complicated logic inside the loop also hurts the performance. Consider looping until you reach the midpoint:

    while (i1 + i2 < pivot)

and do the final median finding afterwards.


Python, Iterate through a list sending batches of 100 records at a time to an API, then appending results to another list I have a list of 9000 dictionaries and I am sending them to an API in batches of 100 (limit of the API). The API returns the list of 100 dictionaries just expanded with more key/value pairs. So both lists look something like this:

[
{Key1:Val1, Key2:Val2},
{Key1:Val3, Key2:Val4},
...
]

and returns:

[
{Key1:Val1, Key2:Val2,Key3:Val1, Key4:Val4},
{Key1:Val3, Key2:Val4,Key3:Val1, Key4:Val4},
...
]

Now, I have to create a list that has all 9000 returned dictionaries in them, because the original input receives a batch of 9000 so it needs to output them all at once as well. I have accomplished this with the following code:

dict_list = [This is the list with 9000 dicts]
batch_list = []
return_list = []

for i in dictlist:
    batch_list.append(i)
    if len(batch_list)  == 100:
        api_batch = API_CALL_FUNCTION(batch_list)
        for j in api_batch:
            return_list.append(j)
        batch_list.clear()
    else:
        continue
if batch_list:
    api_batch = API_CALL_FUNCTION(batch_list)
    for k in api_batch:
        return_list.append(k)

This code does what I want it to, but I really don't like the nested for loop and I'm sure there's probably a more efficient way to do this. Any suggestions?

You should just be able to append the returned API list directly to return_list:

dict_list = [This is the list with 9000 dicts]
batch_list = []
return_list = []

for i in dictlist:
    batch_list.append(i)
    if len(batch_list)  == 100:
        return_list.append(API_CALL_FUNCTION(batch_list))
        batch_list.clear()

if batch_list:
    return_list.append(API_CALL_FUNCTION(batch_list))

and your else clause is un-needed.

You should also explore slicing the dictlist instead of iterating through each one.
You can call dictlist[0:100] and it will return a list containing the first 100 elements. dictlist[100:200] will return the next chunck, etc.

Hope this helped! Good luck.


Building categories block based on JSON I'm not even sure if this is how you're supposed to do it, but this is what I have so far:

$.getJSON("/api/get_categories", function(data){
    var items = [];
   $.each(data["categories"], function(key, value){

    items.push('
<div class="card waves-effect waves-block waves-light"

'+value+'

');
   });

   $("#categories").html(items.join(""));

});

The issue is that the string within my push looks really awkward and long. What's the better way of doing this?

I have a few issues with your code before I get into your actual question:

Your indentation is inconsistent and wrong, you should be using two or four space indentation, not three-space indentation.
Your usage of quotation marks is inconsistent, use either " or ', but stay consistent.
BUG: you're missing a close html tag character in here: <div class="card waves-effect waves-block waves-light"
.
Instead of pushing it into the block as one big lump, consider pushing it through at each category, that way it'll actually look like it's loading, and you can avoid storing a massive html string. You can use jQuery's .append to do this

As for your specific question, I would style it better by splitting it into parts, and joining each part like so:

$.getJSON('/api/get_categories', function(data){
    $.each(data.categories, function(key, value){
        $('#categories').append(
            '
' +
            '

' +
            '
' +
            '' +
            value + '

'
        );
    });
});


Pick a random big word from a list of words using Python I am trying to randomly pick a large word (7 letters or more in length) from a large text file of words.

I know that there has to be a better and more efficient way to do this.

def goalWord():
    with open("words.txt","r") as allWords:
        wordList = allWords.read()
        wordList = wordList.split()
        bigWords = []
        for word in wordList:
            if len(word) > 6:
                bigWords.append(word.upper())
        return random.choice(bigWords)

Here is the sample input:

A
a
aa
aal
aalii
aam
Aani
aardvark
aardwolf
Aaron
Aaronic
Aaronical
Aaronite
Aaronitic
Aaru
Ab
aba
Ababdeh
Ababua
abac
abaca
abacate
abacay

Output would be a random word from words.txt that is greater than 6 characters in length.

Comments

Python functions are written in snake_case.
You could use function parameters for word length and filename.
You could use iterators and generators to avoid loading the whole file into memory.
If you read the file line by line, you need to take care with the trailing newline character: len("test\n") is 5.

Refactoring

Here's a way to rewrite your function. Thanks to a generator, the script only loops once over every line:

import random

def goal_word(min_length=7, filename="words.txt"):
    with open(filename) as wordbook:
        words = (line.rstrip('\n') for line in wordbook)
        large_words = [word for word in words if len(word) >= min_length]
    return random.choice(large_words)

print(goal_word(7))
# evening
print(goal_word(15))
# circumnavigations

Optimization

@etchesketch commented that rstrip is called on every line even though it's only needed for one word. Here's a variation:

import random

def goal_word(min_length=7, filename="words.txt"):
    min_line_length = min_length + 1
    with open(filename) as wordbook:
        large_words = [line for line in wordbook if len(line) >= min_line_length]
    return random.choice(large_words).rstrip('\n')

print(goal_word(7))
# jauntily
print(goal_word(15))
# fundamentalists

On a dictionary of English words (/usr/share/dict/american-english), this function is 3 times faster than the previous one.

Exception handling

In the above examples, goal_word(30) fails with IndexError: Cannot choose from an empty sequence. There's no indication that the desired length is too long.

Before calling random.choice, the script could simply check that large_words isn't empty:

import random

def goal_word(min_length=7, filename="words.txt"):
    min_line_length = min_length + 1
    with open(filename) as wordbook:
        large_words = [line for line in wordbook if len(line) >= min_line_length]
    if large_words:
        return random.choice(large_words).rstrip('\n')
    else:
        raise ValueError("No word found with at least %s characters." % min_length)

print(goal_word(7))
# jauntily
print(goal_word(15))
# insurrectionist's
print(goal_word(30))
# ValueError: No word found with at least 30 characters.


Refactoring class methods to helper class? I have an abstract class that represents data request. The request is in XML format. There are a few classes that derive from abstract class and they do similar things.

Some basic XML operations such as create XML document, write the elements and attributes of XML document and so on are implemented as methods of abstract class and they can be used from derived classes as well.

I should refactor the abstract class. I think I could write some kind of XML helper class outside of request-based classes, but I'm not sure if it's right way.

The code looks as following:

public abstract class MWRequest
{
    public static string WebServiceURL = "url";
    protected XmlDocument xmlDoc = new XmlDocument();

    protected MWRequest()
    {
        xmlDoc.LoadXml("<?xml version=\"1.0\" encoding=\"utf-8\"?><request/>");
    }

    public XmlDocument XmlDocument
    {
        get { return xmlDoc; }
    }

    protected void PrepareRequest(string requestType)
    {
        LoadElement("protocol-version", "4.00");
        LoadElement("request-type", requestType);
        LoadExtraElement("password", password);
        LoadElement("terminal-id", terminalId);
    }

    protected void LoadElement(string elemName, string val)
    {
        XmlElement elem = xmlDoc.CreateElement(elemName);
        elem.InnerText = val;
        xmlDoc.DocumentElement.AppendChild(elem);
    }

    protected void LoadExtraElement(string name, string val)
    {
        // <extra name="ltime">60</extra>
        XmlElement elem = xmlDoc.CreateElement("extra");

        XmlAttribute attrName = xmlDoc.CreateAttribute("name");
        attrName.Value = name;
        elem.Attributes.Append(attrName);

        elem.InnerText = val;

        xmlDoc.DocumentElement.AppendChild(elem);
    }

    ...
}

public abstract class MWRequest
{
    public static string WebServiceURL = "url";
    protected XmlDocument xmlDoc = new XmlDocument();

    protected MWRequest()
    {
        xmlDoc.LoadXml("<?xml version=\"1.0\" encoding=\"utf-8\"?><request/>");
    }

Class name

I get the Request part of the class name, but MW could be just about anything, and itsn't descriptive. I suggest you rename the class, and drop this abbreviation.

Static field

Anything public static in an abstract class, smells. You're not showing how it's used, but being static, the value stops being an instance-level value and becomes a type-level value, which means all instances of that class will have the same WebServiceURL (which should be named WebServiceUrl - PascalCase FTW!), which just doesn't sound right, especially in a base/abstract class.

Public fields

Don't do that, you're breaking encapsulation. Derived classes can do anything they want with xmlDoc, and bypass everything you've coded as protected methods.

Encapsulation enables abstraction. Your base class could encapsulate an XmlDocument and provide an abstraction layer that hides this implementation detail to its clients and derived types. If you need to expose the XML, then override ToString and return the encapsulated XML instead of exposing the whole xmlDoc, or expose a Xml property that does that.

public XmlDocument XmlDocument
{
    get { return xmlDoc; }
}

If a derived type wants to set the XmlDocument reference, the parameterless constructor will still run and call LoadXml with the hard-coded string there. I think you should have a protected constructor that just takes an XmlDocument from the derived type, and chain the constructor calls:

protected MWRequest()
    : this(new XmlDocument())
{
    _xmlDoc.LoadXml("<?xml version=\"1.0\" encoding=\"utf-8\"?><request/>");
}

protected MWRequest(XmlDocument xmlDoc)
{
    _xmlDoc = xmlDoc;
}

private readonly XmlDocument _xmlDoc;
public XmlDocument xmlDocument { get { return _xmlDoc; } }

This way a derived type has only 1 way of setting the XmlDocument reference, through the constructor.

A word about LoadElement and LoadExtraElement: they're both badly named, protected and useless - a derived type can access the XmlDocument from the XmlDocument property, and do everything it needs to do with it, including destroying/replacing the entire DOM.

Either make them protected virtual and drop the XmlDocument property (and add any members to expose whatever other types need out of it), or keep the XmlDocument property and drop the helper methods - at the end of the day, it's a design decision you need to make.

If you decide to keep them, I'd suggest to change the signatures a bit:

protected virtual XmlElement CreateElement(string name, string innerText)
{
    // ...
}

protected virtual XmlElement CreateExtraElement(string name, string value)
{
    // ...
}

By making CreateElement a function that returns the XmlElement it's creating (instead of adding it itself to xmlDoc), you can delete some of the code from CreateExtraElement and call CreateElement from within CreateExtraElement

var element = CreateElement("extra", value);
var attribute = _xmlDoc.CreateAttribute("name"); // "attrName" is a bad name
attribute.Value = name;
element.Attributes.Append(attribute);
return element;

The client code is a derived class, so it can do this:

var element = CreateExtraElement("foo", "bar");
XmlDocument.DocumentElement.AppendChild(element);

And if the base class implementation for CreateExtraElement doesn't suit that class' needs, it can always override it, because it's virtual.

LINQ to XML

I'd suggest you use the System.Xml.Linq namespace and its XDocument and XNode, XElement, and XAttribute classes, instead of the older XmlDocument & friends classes from System.Xml.


Checking whether two lists contain the same elements I have two lists of numbers:

$$\{i_1, i_2, i_3,i_4\}$$ and $$\{j_1,j_2,j_3,j_4\}$$

The problem I want to solve is: Inside a loop, if the following two conditions are satisfied, then it will do something I want, otherwise it just cycle the loop. The conditions are:

Both lists contain four different numbers;
If ignoring the ordering, in other words, we view these two lists as two set, then they are the same.

I want to find a very fast way to get the answer to the problem. I have very slow Fortran code as follows:

if (i2==i1) cycle
if (i3==i1) cycle
if (i3==i2) cycle
if (i4==i1) cycle
if (i4==i2) cycle
if (i4==i3) cycle

if (j2==j1) cycle
if (j3==j1) cycle
if (j3==j2) cycle
if (j4==j1) cycle
if (j4==j2) cycle
if (j4==j3) cycle
q1=0
q2=0
q3=0
q4=0
if (i1==j1)q1=1
if (i1==j2)q1=2
if (i1==j3)q1=3
if (i1==j4)q1=4
if (i2==j1)q2=1
if (i2==j2)q2=2
if (i2==j3)q2=3
if (i2==j4)q2=4
if (i3==j1)q3=1
if (i3==j2)q3=2
if (i3==j3)q3=3
if (i3==j4)q3=4
if (i4==j1)q4=1
if (i4==j2)q4=2
if (i4==j3)q4=3
if (i4==j4)q4=4

if (q1*q2*q3*q4==24)then
 Something I want to do
endif

I think to find a good program, the following should also be considered as well as cutting down the number of instructions:

The probability to have four different numbers in both lists are about
1/10;
The probability to have for these two lists containing two same set
of numbers are very small, about 10^(-11);
I really have to do many loops.

Could someone help me out? I think a good idea can really boost the code.

The only way to reduce the number of operations is to sort one of the arrays. But 4 elements is hardly worth it.

Perhaps when adding the numbers to the array then add them in a sorted order, otherwise quicksort is good for arrays under 10 elements in size.

Performing a binary search on a sorted array would give you O(log n) time for each search - with O(n log n) time to compare two full arrays of the same size. Quicksort is O(n log n), with binary search that's roughly O(2[n log n]).

Adding items in a sorted order, then searching, would be a similar complexity: O(n log n) for adding 'n' items, and O(n log n) for searching through n items. I prefer this solution because it's one simple algorithm, and it's cleaner.


Better way to write this branch with an exceptional retry in an embedded C environment? A while back I wrote the following code (target is embedded C code on an 8 bit atmel device):

    bool received;
tryAgain:
    received = radioReceive(radiogram, MatchTree, CycleClock, duration);
    if (received && radiogram->timeSlit == SolicitMask)
        goto tryAgain; // not interested in recursion and the (stack) problems that could come with it
    return received;

I rarely rarely use a goto. Sometimes in embedded land, I talk myself into it. I'm aware that goto is bad, let's skip that issue. The real goal of the code flow was to capture 3 cases:

the radioReceive timed out, so we pass the false back up
it returned, but what was heard was basically a false positive, so try some more (this is somewhat exceptional)
otherwise it was good and we return true

Then we refacatored the timeSlit test to include some other conditions that we felt were false positives (new function named radiogramIsValidSync()), but we got the logic backwards. At which point, we concluded this code was screwy and should be rewritten. But we diverged on how to best express those 3 conditions.

We came up with:

do {
    bool received = radioReceive(radiogram, MatchTree, CycleClock, duration);
    if (received == false) return false;
    else if (radiogramIsValidForSync(radiogram)) return true;
} while (1);

This is terse, but I'm not a fan of meaningless while()'s (would rather use empty for conditions). I also don't care for the fact that 2 of the 3 conditions are explicit, but the other is implicit.

A more explicit version is

    bool received
tryAgain:
    received = radioReceive(radiogram, MatchTree, CycleClock, duration);
    if (received)
    {
        if (radiogramIsValidForSync(radiogram))
            return true;
        else
            goto tryAgain;
    }
    else
    {
        return false;
    }

But this still includes the goto. A terse version is:

do
{
    if (!radioReceive(radiogram, MatchTree, CycleClock, duration))
        return false;
} while (!radiogramIsValidForSync(radiogram));
return true;

It gets rid of a named variable (which could be good or bad), my real issue with this is that it has multiple logic negation points, so you have to think "backwards" in both of the important points. Finally, a for variant:

for ( ; ; )
{
    received = radioReceive(radiogram, MatchTree, CycleClock, duration);
    if (received == false)
        return false;
    else if (radiogramIsValidForSync(radiogram))
        return true;
}

But this isn't really any better than the do/while(1) variant. And at the end of that we found ourselves feeling unexcited about any of them. Is this just a case of the Law of Conservation of Ugly? Or is there a good/clear way to write this?

If you can do without the received variable...just make the radioReceive(...) the condition of a while loop.  You get rid of received, and your loop condition now has a purpose.  :)

while (radioReceive(radiogram, MatchTree, CycleClock, duration)) {
    if (radiogramIsValidForSync(radiogram)) return true;
}
return false;

The only real drawback is that it gets a bit awkward if you need to do anything at both exit points, other than return.


Mathematical quiz game I have been studying C#, and I have made a simple math quiz program.

Is my program reasonable or is there anything I need to improve?

class Program
{

    static void Main(string[] args)
    {
        Console.WriteLine("============== Math Game ===================");

        double num1, num2;
        double userInput;
        int randomIndex;
        double sum = 0;
        string operation;

        // [2]
        //int lives = 0;

        // Console.Write("How many lives do you want?\t");
        // lives = Convert.ToInt32(Console.ReadLine());
        // Console.WriteLine("You have  {0} Lives", lives);

        bool isPlaying = true;
        do
        {
            // 1 generate randon#
            Random rnd = new Random();
            randomIndex = rnd.Next(1, 4);
            num1 = rnd.Next(1, 11);
            num2 = rnd.Next(1, 11);

            // 2 cal sum && operation && Display
            sum = Cal(num1, num2, randomIndex);
            operation = Operation(randomIndex);

           // DisplayProblem(num1, num2, operation);

            // 3 request input
            userInput = RequestInput(num1,num2,operation);

            // 4 check answer
            CheckAnswer(userInput, sum);

        } while (isPlaying);

    }
    private static double Cal(double num1, double num2, int randomIndex)
    {
        double sum = 0;
        switch (randomIndex)
        {
            case 1:
                sum = num1 + num2;
                break;
            case 2:
                sum = num1 - num2;
                break;
            case 3:
                sum = num1 * num2;
                break;
            case 4:
                sum = num1 / num2;
                break;
            default:
                Console.WriteLine("Error");
                break;
        }
        return sum;
    }
    private static string Operation(int randomIndex)
    {
        string operation = "";

        switch (randomIndex)
        {
            case 1:
                operation = "+";
                break;
            case 2:
                operation = "-";
                break;
            case 3:
                operation = "*";
                break;
            case 4:
                operation = "/";
                break;
            default:
                Console.WriteLine("error");
                break;
        }
        return operation;
    }
    private static void DisplayProblem(double num1, double num2, string operation)
    {
        Console.Write($"{num1} {operation} {num2}  = ");
    }
    private static double RequestInput(double num1, double num2, string operation)
    {
        DisplayProblem(num1, num2, operation);

        double userInput;
        while (!Double.TryParse(Console.ReadLine(),out userInput))
        {
            Console.WriteLine("Invalid input. Please type a whole num");
            DisplayProblem(num1, num2, operation);
        }
        return userInput;
    }
    private static void CheckAnswer(double userInput, double sum)
    {
        if (userInput == sum)
        {
            Console.WriteLine("Correct Answer.");
        }
        else if(userInput != sum)
        {
            Console.WriteLine("Wrong Answer.");
        }
    }
}

In the Operation method

private static string Operation(int randomIndex)
{
    string operation = "";
    switch (randomIndex)
    {
        case 1:
            operation = "+";
            break;
        case 2:
            operation = "-";
            break;
        case 3:
            operation = "*";
            break;
        case 4:
            operation = "/";
            break;
        default:
            Console.WriteLine("error");
            break;
    }
    return operation;
}

instead of doing operation = ... and then returning operation you can just return

Example :

case 1:
    return "+";

Same thing in the Cal method.

In the CheckAnswer method you should just have else instead of else if(userInput != sum)

Also in the Main your Random rnd = new Random(); should be out of the do while loop.


Determining the region from several sources of information The task is to determine the region by comparing three sources of information taking into account the coefficients of their importance.

//GetRegionIdByKeywordAsync returns region id by string name, if the region could not be determined, 0 will return

//The received identifiers can completely or partially coincide, or be absolutely different
int regionIdByIp = await GetRegionIdByKeywordAsync(regionByIpStr);
int regionIdByPhone = await GetRegionIdByKeywordAsync(regionByPhoneStr);
int regionIdByInput = await GetRegionIdByKeywordAsync(regionByInputStr);

var weights = new List<KeyValuePair<int, int>>
{
  //Each source of information has its own importance coefficient, determined manually
  new KeyValuePair<int, int>(regionIdByIp, 5),
  new KeyValuePair<int, int>(regionIdByPhone, 3),
  new KeyValuePair<int, int>(regionIdByInput, 4)
};

//The final decision is determined by the search for a region that has the highest score in the total
int regionId = weights.Where(x => x.Key != default(int)).GroupBy(kvp => kvp.Key).OrderByDescending(x => x.Sum(y => y.Value)).Select(x => x.Key).FirstOrDefault();

Do you see any improvement / issue?

Since you are not actually using a dictionary I find anonymous tuples would be much more readable here. Consider this where you don't even need a List<T> but just a simple array:

var weights = new (int RegionId, int Importance)[]
{
  (regionIdByIp, 5),
  (regionIdByPhone, 3),
  (regionIdByInput, 4)
};

Where you define such a tuple as (int RegionId, int Importance). With it the next query (also written with line breaks) would be much easier to understand.

int mostImportantRegionId =
    weights
        .Where(x => x.RegionId > 0)
        .GroupBy(kvp => kvp.RegionId)
        .OrderByDescending(x => x.Sum(y => y.Importance))
        .Select(x => x.RegionId)
        .FirstOrDefault();

I also think that x.Key != default(int) is a strage condition. If Key is an id then it probably should be greater than 0 so it's better to write x.RegionId > 0 instead.

What you also can do better is the await part. Currently you wait for each task to finish one-by-one. Let's them work in parallel with WaitAll:

var regionIdByIpTask = GetRegionIdByKeywordAsync(regionByIpStr);
var regionIdByPhoneTask = GetRegionIdByKeywordAsync(regionByPhoneStr);
var regionIdByInputTask = GetRegionIdByKeywordAsync(regionByInputStr);

Task.WaitAll(new []
{
    regionIdByIpTask,
    regionIdByPhoneTask,
    regionIdByInputTask
};

Now you can build your weights:

var weights = new (int RegionId, int Importance)[]
{
  (regionIdByIpTask.Result, 5),
  (regionIdByPhoneTask.Result, 3),
  (regionIdByInputTask.Result, 4)
};


Convert object with 'long.property.name' property to object tree I want to transform such object from:

foo = {
    42: 'foo',
    'a.b.c[0].42': 'bar',
    'a.b.c[0].43': 'zet',
    'a.d.c[0].42': 'baz'
}

To:

bar = {
    42: 'foo',
    'a.b.c[0].42': 'bar',
    'a.b.c[0].43': 'zet',
    'a.d.c[0].42': 'baz',
    a: {
        b: {
            c: [{
                42: 'bar', 43: 'zet'
            }]
        },
        d: {
            c: [{
                42: 'baz'
            }]
        }
    }
}

I have written implementation, but it looks ugly.
Do anybody know how to improve the function below?
We use lodash in my project so that can help with basic operations.

function convertToTree(rowObjectData) {
  function it(object) {
      return _.reduce(object, function (finalObjectData, value, key) {
          var pathParts = key.match(/(.+?)\.(.+)/);

          if (pathParts) {
              delete finalObjectData[key];

              var deepObject = {},
                  containerObject = {},
                  arrayMatch = pathParts[1].match(/(.*)\[(.)]$/);

              deepObject[pathParts[2]] = value;

              if (arrayMatch) {
                  containerObject[arrayMatch[1]] = [];
                  containerObject[arrayMatch[1]][arrayMatch[2]] = it(deepObject);
              } else {
                  containerObject[pathParts[1]] = it(deepObject);
              }

              finalObjectData = _.defaultsDeep(finalObjectData, containerObject);
          }

          return finalObjectData;
      }, object);
  }

  return _.assign(_.cloneDeep(rowObjectData), it(_.cloneDeep(rowObjectData)));
}

var object = {
    42: 'foo',
    'a.b.c[0].42': 'bar',
    'a.b.c[0].43': 'zet',
    'a.d.c[0].42': 'baz'
};

console.log(convertToTree(object));
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.1/lodash.js"></script>

If I had to take a stab at it I would write something like this:

function convertToTree(rowObjectData) {

  function isArrayKey(key) {
    return _.last(key) == ']';
  }

  function setValue(object, value, key) {
    var parts   = key.split(/[.[]/),
        last    = parts.length - 1;

    for (var i=0, current=object;
         i < parts.length;
         i++, current = current[k]) {
      var p = parts[i],
          k = isArrayKey(p) ? parseInt(p) : p;
      if (i == last)
        current[k] = value;
      else if (current[k] == undefined)
        current[k] = isArrayKey( parts[i+1] ) ? [] : {}
    }

    return object;
  }

  return _.reduce(rowObjectData, setValue, _.cloneDeep(rowObjectData) );
}

var object = {
    42: 'foo',
    'a.b.c[0].42':    'bar',
    'a.b.c[0].43':    'zet',
    'a.d.c[0].42':    'baz',
    'a.d.c[1]':       'zaphod',
    'a.d.c[2][0].49': 'beeblebrox',
};

console.log(convertToTree(object));
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.1/lodash.js"></script>

Which also allows multiple sequential arrays (c[0][1].49 = 'foo' and doesn't require the last key to be an object (c[0] = 'foo')


Generate the alphabet and select only specific letters I am learning java and would like to create a very simple application but which uses SOLID principles.

The required functionality is: generate the alphabet with a possibility to select specific letters. For now there must be an option to select only even/odd letters but the project must be open for extra functionalities (which are unknown at the moment but may be defined in the near future).

I created a code but I got a feedback that my code is not using the Single Responsibility Principle. Could you please help me understand which part of my code is not in line with that principle and what can be done better?

abstract class Characters {
    private ArrayList<Character> array;

    public ArrayList<Character> getArray() {
        return array;
    }

    public Characters() {
        array = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            array.add((char) ('A' + i));
        }
    }

    public abstract void getModifiedArray(String arg);
}

class CharactersParity extends Characters {

    @Override
    public void getModifiedArray(String arg) {
        String arg2 = arg.trim().toLowerCase();

        switch (arg2) {
        case "even": {
            for (char c : getArray()) {
                if (c % 2 == 0) {
                    System.out.println(c);
                }
            }
        }
            break;
        case "odd": {
            for (char c : getArray()) {
                if (c % 2 != 0) {
                    System.out.println(c);
                }
            }
        }
            break;
        default:
            System.out.println("wrong parameter");
        }
    }
}

This may get hard, but you requested it... ;o)

Your program fails the SOLID principle (at least) in this ways:

Single responsibility principle

You mix the "business logic" with the user interface (UI).

The getModifiedArray method does the separation of the values and displays the result. Along the way it also fails to do what its name expresses.

Open/closed principle

Your class hierarchy is questionable.

OCP is about future changes, so imagine you want to enhance this program so that the user can select the number of characters to process.

SoC does not allow to put a int maxChars = new Scanner(System.in).nextInt(); into your Characters class.

So you have to either create a setter Metthod in    Characters which extends the interface of CharactersParity too (violates Interface seggaration), or you create a parameterized constructor which forces you to create the same constructor in CharactersParity too.

The better way would be that CharactersParity does not inherit from Characters but gets a Charactersobject as constructor parameter to use:

class CharactersParity  {
   private final Characters characters;

   CharactersParity(Characters characters){
     this.characters = characters;
   }

public void getModifiedArray(String arg) {
    String arg2 = arg.trim().toLowerCase();

    switch (arg2) {
    case "even": {
        for (char c : characters.getArray()) {

    // ....

Liskov substitution principle

IMHO
not applicable .

Interface segregation principle

The declaration of method getModifiedArray() in class Characters is not needed. It makes the interface of   class Characters wider as is should be.

I guess the aim was to force other AnythingCharacters classes to have this method.
In that case this method should be in a separate interface class:

public interface CharacterArrayModifier {
   void getModifiedArray(String arg);
}
class CharactersParity implements  CharacterArrayModifier{
   private final Characters characters;

   CharactersParity(Characters characters){
     this.characters = characters;
   }

@Override
public void getModifiedArray(String arg) {
// ...

Dependency inversion principle

Your class  CharactersParity  has 2 dependencies: Systen.out and  Characters.

You get the first via static access and the second is bound via inheritance.

DI suggests to gather the dependencies outside the class needing it and injecting them into the using class. The using class stores them in internal variables.

This injection can be done in three ways:

direct assignment
The dependency object is directly assigned to the variable in the using object.
setter injection
the using object has a setter method to receive the dependency.
constructor injection
the using object gets  the dependency as constructor parameter (as shown above).

IMHO the priority in usage should be 3, 1, 2.

The main advantage of "constructor injection" is that the dependency cannot be null by accident, (i.e. you simply did not type the assignment). The compiler forces you to pass a value. If this value is null then it is your intention...

As I indicated you program as some improper naming, but I think it is enough for now...


Cached infinite prime generator For a project I am working on, I need to use a lot of primes, frequently. To do this, I added a cache to Will Ness's prime sieve, that stores already generated primes so getting them is quick. How can I improve this code?

def prime_sieve(): # postponed sieve, by Will Ness
    for c in (2,3,5,7):                     # original code David Eppstein,
        yield c
    sieve = {}                              # Alex Martelli, ActiveState Recipe 2002
    ps = prime_sieve()                      # a separate base Primes Supply:
    p = next(ps) and next(ps)               # (3) a Prime to add to dict
    q = p*p                                 # (9) its sQuare
    for c in count(9,2):                    # the Candidate
        if c in sieve:                      # c’s a multiple of some base prime
            s = sieve.pop(c)                # i.e. a composite ; or
        elif c < q:
            yield c                     # a prime
            continue
        else:   # (c==q):            # or the next base prime’s square:
            s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
            p=next(ps)               #    (5)
            q=p*p                    #    (25)
        for m in s:                  # the next multiple
            if m not in sieve:       # no duplicates
                break
        sieve[m] = s                 # original test entry: ideone.com/WFv4f

class cached_primes:
    def __init__(self):
        self.prime_gen = prime_sieve()
        self.vals = [2]
        next(self.prime_gen)

    def get(self, start=2, end=float('inf')):
        vals = self.vals

        lo = self.get_ind(start)
        if vals[-1] >= end:
            hi = self.get_ind(end)
            yield from islice(vals, lo, hi)
            return
        else:
            while vals[-1] < end:
                if len(vals) > lo:
                    bound = len(vals)
                    yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
                    lo = bound
                vals.append(next(self.prime_gen))
        hi = self.get_ind(end)
        yield from islice(vals, lo, hi)

    def get_ind(self, x):
        if x <= 2:
            return 0
        vals = self.vals
        B = x/log(x)
        if x < 17:
            return bisect(vals, x, 0, min(len(vals), int(B)))
        return bisect(vals, x, int(B), min(len(vals), int(1.25506*B)))

prime_sieve() isn't your code, so I won't review it (although I will express my opinion that it's in dire need of more commenting).

However, the choice to use it is firmly within the scope of this review, and frankly I can't understand it. The whole point of that particular implementation is to optimise memory use at the cost of considerable code complexity. But given that your goal is a fully cached list (i.e. optimising speed at the cost of memory usage), it would make far more sense to me to use a simpler implementation which directly accesses the cache.

        if vals[-1] >= end:
            hi = self.get_ind(end)
            yield from islice(vals, lo, hi)
            return
        else:
            while vals[-1] < end:
                if len(vals) > lo:
                    bound = len(vals)
                    yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
                    lo = bound
                vals.append(next(self.prime_gen))
        hi = self.get_ind(end)
        yield from islice(vals, lo, hi)

Taking a step back to look at the structure, we have

        if condition():
            foo()
            return
        else:
            while not condition():
                bar()
        foo()
        return # implicit because it's the end of the function

Firstly,

            return
        else:

can often be clearer without the else, which is unnecessary: the scope it defines is unreachable if the if block executed. That gives

        if condition():
            foo()
            return

        while not condition():
            bar()
        foo()
        return

which is semantically identical to

        while not condition():
            bar()
        foo()
        return

            while vals[-1] < end:
                if len(vals) > lo:
                    bound = len(vals)
                    yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
                    lo = bound
                vals.append(next(self.prime_gen))

The whole if clause in here seems dubious to me. Why can't it be removed entirely? (I figured out the reason, but IMO there should be a comment to save me the effort).

Given that all but the first time round it will yield from a slice containing precisely one value (the one appended the previous time round), it seems rather heavyweight. It would probably make sense to refactor as:

    yield from (something)
    while vals[-1] < end:
        extension = next(self.prime_gen)
        vals.append(extension)
        yield extension

Further modification to the final refactors implemented for the above points may come from the simpler replacement of prime_gen. Do you want a replacement with produces primes one at a time, or something like a paged sieve? The latter should be more efficient, but at the cost of slight complication.

    def get_ind(self, x):

If I had to guess without any contextual clues, I would assume that ind is short for independent. If it's necessary to abbreviate index then I consider idx to be the best option. But here there is a clear correct name for the method: index, for consistency with list.index.

(Of course, that's assuming you want it to be public. Given that it returns incorrect values for primes which haven't yet been reached by get, it would probably be better to call it _index).


Test if given ip is a public one? I'd like to check if the user submitted adress ip is a valid public IPv4 (non loopback, non local, non reserved).

For that purpose, I came up with that method, but I was wondering if this was enough or if I was missing some tests.

private boolean isValidPublicIp(String ip) {
    try
    {
        Inet4Address address = (Inet4Address) InetAddress.getByAddress(ip.getBytes());
        if (!address.isSiteLocalAddress() && !address.isAnyLocalAddress() && !address.isLinkLocalAddress() && !address.isLoopbackAddress() && !address.isMulticastAddress()) {
            return true;
        }
    }
    catch (UnknownHostException exception) {}

    return false;
}

One-shot answer:

private boolean isValidPublicIp(String ip) {
    Inet4Address address;
    try {
        address = (Inet4Address) InetAddress.getByName(ip);
    } catch (UnknownHostException exception) {
        return false; // assuming no logging, exception handling required
    }
    return !(address.isSiteLocalAddress() ||
             address.isAnyLocalAddress()  ||
             address.isLinkLocalAddress() ||
             address.isLoopbackAddress() ||
             address.isMulticastAddress());
}

Reduce your try scope, and you do not need to do something like if (boolean) { return true; }. Just return boolean;. :)

edit: Your usage of ip.getBytes() for getByAddress() is actually wrong. The most straight-forward way is just to do getByName(ip), as shown here and here.


Finding max rating for a movie I am taking Stanford's Introduction to Databases Self-Paced online course. I have gone through the videos in the SQL mini-course, and I am having trouble completing the exercises.

The following is the question from the SQL Movie-Rating Query Exercises, Question 7:

  For each movie that has at least one rating, find the highest number
  of stars that movie received. Return the movie title and number of
  stars. Sort by movie title.

The database can be found here.

My answer to this question is as follows:

SELECT distinct Movie.title, Rate.stars
FROM Movie, Rating,
(SELECT * FROM Rating R1 WHERE not exists (SELECT mID FROM Rating R2 WHERE R1.stars < R2.stars and R1.mID = R2.mID)) as Rate
WHERE Movie.mID = Rate.mID and Rate.stars = Rating.stars
order by Movie.title;

This seems like a very tortured query, and it seems to me like I am missing some important concepts. Can someone help me refactor this query?

SELECT distinct Movie.title, Rate.stars

You should rarely use the DISTINCT keyword.  In this particular case it's unnecessary and may do the wrong thing.  What you want to do is to return the highest star rating for a given movie title:

SELECT Movie.title, MAX(Rating.stars)

There's the title and we use the MAX keyword to make sure that it's the highest stars.  More on when we can use MAX later.

FROM Movie, Rating,
(SELECT * FROM Rating R1 WHERE not exists (SELECT mID FROM Rating R2 WHERE R1.stars < R2.stars and R1.mID = R2.mID)) as Rate
WHERE Movie.mID = Rate.mID and Rate.stars = Rating.stars

We can make this simpler:

FROM Movie, Rating
WHERE Movie.mID = Rating.mID

No subselects required.

GROUP BY Movie.title
ORDER BY Movie.title;

The GROUP BY will allow us to use MAX.  It says to return only one row per Movie.title value.  The other columns need to be aggregated with grouping functions, like MAX.  You already had the ORDER BY clause and presumably it's correct.


Multithreaded lock-free queue implementation My partner and I are beginning to believe there could be a desync possibility in the lock free queue we have written, but we would like some fresh eyes on the subject. What are your thoughts on our design?

// nolockqueue.hpp:
#ifndef NOLOCKQUEUE_HPP
#define NOLOCKQUEUE_HPP

template<typename T>
class noLockQueue {
public:
    noLockQueue();
    ~noLockQueue();
    void push(const T dataVar);
    bool pop(T &dataVar);

private:
    struct node {
        node(T dataPassed) : dataVar(dataPassed), next(NULL) {};
        T dataVar;
        node* next;
    };

    node* topOfList;
    node* bottomOfList;
};

template<typename T>
noLockQueue<T>::noLockQueue() {
    topOfList = NULL;
    bottomOfList = NULL;
}

template<typename T>
noLockQueue<T>::~noLockQueue() {
    node* temp;

    while (topOfList != NULL) {
        temp = topOfList->next;
        delete topOfList;
        topOfList = temp;
    }

    if (bottomOfList != NULL)
        throw("Not All Nodes Deleted - nolockqueue/38/.cpp"); // TODO: Strange error to throw.
}

template<typename T>
void noLockQueue<T>::push(const T dataVar) {
    if (topOfList == NULL) {
        topOfList = bottomOfList = new node(dataVar);
        return;
    } else {
        bottomOfList->next = new node(dataVar);
        bottomOfList = bottomOfList->next;
    }
}

template<typename T>
bool noLockQueue<T>::pop(T &dataVar) {
    if (topOfList == NULL)
        return false;

    dataVar = topOfList->dataVar;
    node* temp = topOfList->next;
    delete topOfList;
    topOfList = temp;
    return true;
}

#endif

// main.cpp (purely a test unit):
#include <iostream>
#include <thread>

#include "nolockqueue.hpp"
#include <windows.h> // For Sleep().

noLockQueue<int> queue;

void threadFunc() {
    int var = 0;
    Sleep(10);
    while (queue.pop(var)) {
        std::cout << "\nPopped: " << var;
        Sleep(1);
    }
}

int main(int argc, char* argv[]) {
    std::thread myThread(threadFunc);

    for (int i = 0; i < 1000; ++i) {
        queue.push(i);
        std::cout << "\nPushed: " << i;
        Sleep(1);
    }

    myThread.join();

    std::cin >> argc;
    return 0;
}

This is not a lock-free queue, but a locking-agnostic queue. That means, it is not safe to use on multiple threads. The reason this works in your implementation is because the push calls alter the end of the queue and the pop calls alter the beginning (so conflicts are more or less, avoided).

If you tried adding elements from multiple threads at the same time (for example), you would leak elements.

Since bottomOfList is never changed in the destructor, if it is initialized, you will always get to throw the exception.

Consider splitting pop into a const T& top() const and a void pop(); This would allow for an exception-safe implementation of the operations.


Doing a roll back with multiple MySQLI prepared statement This is my code for doing a roll back with multiple MySQLI prepared statement.

I want to know if anything is wrong with the code.

 $newRegistrationDataArray = array(
    "date" => $date,
    "name" => $name,
    "address" => $address,
    "country" => $country,
    "occupation" => $occupation,
    "emailAddress" => $emailAddress,
    "memberID" => $memberID,
    "usename" => $usename,
    "password" => $password,
    "salt" => $salt,
    "secretQuestion" => $secretQuestion,
    "secretAnswer" => $secretAnswer,
    "transactionCode" => $transactionCode,
    "perfectMoneyAccount" => $perfectMoneyAccount,
    "egoPayAccount" => $egoPayAccount,
    "payeerAccount" => $payeerAccount,
    "okPayAccount" => $okPayAccount,
    "bitcoinAccount" => $bitcoinAccount,
    "upline" => $upline,
    "userRegistrationIp" => $userRegistrationIp,
    "status" => $status
);

public function CreateNewAccount(&$newRegistrationDataArray){ ///note the &

    /* set autocommit to off */
    $this->dbConnection->autocommit(FALSE);

    $stmt1=$this->dbConnection->prepare("INSERT INTO `members` (date,name,address,country,occupation,emailAddress,memberID,usename,password,salt,secretQuestion,secretAnswer,transactionCode,perfectMoneyAccount,egoPayAccount,payeerAccount,okPayAccount,bitcoinAccount,upline,userRegistrationIp,status) VALUES (?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?)");
    $stmt2=$this->dbConnection->prepare("INSERT INTO `membertotalfinancialstatus` (memberId) VALUES (?)");

    /* variable needed */
    $memberId = $this->generateMemberId(); // a private function that generate member id
    $date = $newRegistrationDataArray['date'];
    $name = $newRegistrationDataArray['name'];
    $address = $newRegistrationDataArray['address'];
    $country = $newRegistrationDataArray['country'];
    $occupation = $newRegistrationDataArray['occupation'];
    $emailAddress = $newRegistrationDataArray['emailAddress'];
    $usename = $newRegistrationDataArray['usename'];
    $password = $newRegistrationDataArray['password'];
    $salt = $newRegistrationDataArray['salt'];
    $secretQuestion = $newRegistrationDataArray['secretQuestion'];
    $secretAnswer = $newRegistrationDataArray['secretAnswer'];
    $transactionCode = $newRegistrationDataArray['transactionCode'];
    $perfectMoneyAccount = $newRegistrationDataArray['perfectMoneyAccount'];
    $egoPayAccount = $newRegistrationDataArray['egoPayAccount'];
    $payeerAccount = $newRegistrationDataArray['payeerAccount'];
    $okPayAccount = $newRegistrationDataArray['okPayAccount'];
    $bitcoinAccount = $newRegistrationDataArray['bitcoinAccount'];
    $upline = $newRegistrationDataArray['upline'];
    $userRegistrationIp = $newRegistrationDataArray['userRegistrationIp'];
    $status = $newRegistrationDataArray['status'];
    /* variable needed */

    $stmt1->bind_param('sssssssssssssssssssss',$date,$name,$address,$country,$occupation,$emailAddress,$memberID,$usename,$password,$salt,$secretQuestion,$secretAnswer,$transactionCode,$perfectMoneyAccount,$egoPayAccount,$payeerAccount,$okPayAccount,$bitcoinAccount,$upline,$userRegistrationIp,$status);
    $stmt2->bind_param('s',$memberId);

    try
    {
        if( ($stmt1->execute() == false) OR ($stmt2->execute() == false)){

            /// close statement, roll back and throw an exception
            $stmt1->close();
            $stmt2->close();

            $this->dbConnection->rollback();
            throw new Exception("AN INTERNAL ERROR HAS OCCURED. TRY AGAIN LATER.");
        }
    }
    catch(Exception $e)
    {
        $error=$e->getMessage();
        throw new Exception($error);
    }

    $this->closeDBConn;
}

function CreateNewAccount(&$newRegistrationDataArray){ ///note the &

    /* variable needed */
    $memberId = $this->generateMemberId(); // a private function that generate member id

    // that is lots of repetitive code, lazy way is use extract,
    // although can be dangerous if you can't trust data in $newRegistrationDataArray
    extract($newRegistrationDataArray);

//    $date = $newRegistrationDataArray['date'];
//    $name = $newRegistrationDataArray['name'];
//    $address = $newRegistrationDataArray['address'];
//    $country = $newRegistrationDataArray['country'];
//    $occupation = $newRegistrationDataArray['occupation'];
//    $emailAddress = $newRegistrationDataArray['emailAddress'];
//    $usename = $newRegistrationDataArray['usename'];
//    $password = $newRegistrationDataArray['password'];
//    $salt = $newRegistrationDataArray['salt'];
//    $secretQuestion = $newRegistrationDataArray['secretQuestion'];
//    $secretAnswer = $newRegistrationDataArray['secretAnswer'];
//    $transactionCode = $newRegistrationDataArray['transactionCode'];
//    $perfectMoneyAccount = $newRegistrationDataArray['perfectMoneyAccount'];
//    $egoPayAccount = $newRegistrationDataArray['egoPayAccount'];
//    $payeerAccount = $newRegistrationDataArray['payeerAccount'];
//    $okPayAccount = $newRegistrationDataArray['okPayAccount'];
//    $bitcoinAccount = $newRegistrationDataArray['bitcoinAccount'];
//    $upline = $newRegistrationDataArray['upline'];
//    $userRegistrationIp = $newRegistrationDataArray['userRegistrationIp'];
//    $status = $newRegistrationDataArray['status'];
    /* variable needed */

    try
    {
        /* set autocommit to off */
        $this->dbConnection->autocommit(FALSE);

        $stmt1=$this->dbConnection->prepare("INSERT INTO `members` (date,name,address,country,occupation,emailAddress,memberID,usename,password,salt,secretQuestion,secretAnswer,transactionCode,perfectMoneyAccount,egoPayAccount,payeerAccount,okPayAccount,bitcoinAccount,upline,userRegistrationIp,status) VALUES (?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?)");
        $stmt1->bind_param('sssssssssssssssssssss',$date,$name,$address,$country,$occupation,$emailAddress,$memberID,$usename,$password,$salt,$secretQuestion,$secretAnswer,$transactionCode,$perfectMoneyAccount,$egoPayAccount,$payeerAccount,$okPayAccount,$bitcoinAccount,$upline,$userRegistrationIp,$status);

        // failure is unexpected, so lets use exceptions to handle it
        if ($stmt1->execute() == false) {
            throw new Exception('Statement 1 Failed');
        }

        $stmt2=$this->dbConnection->prepare("INSERT INTO `membertotalfinancialstatus` (memberId) VALUES (?)");
        $stmt2->bind_param('s',$memberId);

        if ($stmt2->execute() == false) {
            throw new Exception('Statement 2 Failed');
        }

        // tidy up
        $stmt1->close();
        $stmt2->close();

        // is it normal to close connection at this level? or do you leave it open for other requests
        $this->closeDBConn;
    }
    catch(Exception $e)
    {
        // any sort of exception and we should rollback?
        // either that or subclass exception and handle each exception type differently
        $this->dbConnection->rollback();

        // whats the point of this, just re-throw the same exception?
        // $error=$e->getMessage();
        // throw new Exception($error);
        throw $e;
    } finally {
       // if you have php 5.5 you can do your tidy up here, although if
       // an exception has occured, you probably don't care about freeing stmt's as
       // they all end up in the garbage anyway

        // tidy up
        //$stmt1->close();
        //$stmt2->close();
    }

}


Style and Suggestions for K&R2 1-18 I just completed K&R (2nd Ed.) ex 1-18.  I'm fairly new to C, but have had experience in other languages (Perl, C++, Java, Common Lisp, PHP, etc) and really want to learn the C idiom as opposed to translating the idioms I already know.

What do you think about this approach to 1-18?

/*
   Exercise 1-18 in K&R 2nd Edition
   Removes trailing blanks & tabs & blank lines from each line of input
   Written by Z. Bornheimer (provided as is without warranty).
*/

#include <stdio.h>
#define MAXLINE 1000

/* removes trailing blanks and tabs...deletes null lines */
main()
{
    int len; /* current line length */
    int i = -1, j; /* two counters */
    int c; /* current char */
    char line[MAXLINE]; /* current input line */

    while ((c=getchar()) != EOF) {
        line[++i] = c;
        if (c == '\n') {
            j = i + 1;
            while (line[--j] == ' ' || line[j] == '\n' || line[j] == '\t')
                line[j] = '\0';

            printf("%s", line);

            for (j = 0; j <= i; j++)
                line[j] = '\0';

            i = -1;
        }
    }
    return 0;
}

https://github.com/zachbornheimer/programming-exercises/blob/master/c/1-18.c

Thank you for your help!

First the obvious: if a line is too long, your program will seriously fail (unknown memory gets overwritten, or the program crashes). Without dynamic memory allocation, I see no way to fix it. However, you could improve the situation significantly.

Since you're reading the input character by character, and you need to remove only trailing blanks and tabs, you can printout any character that is not one of these, and put only blanks and tabs in the string. Once you encounter another non-(blank or tab), you printout that string, and reset it back to a blank string. If \n is encountered, you write it out without the content of the string, as these are the trailing blanks and tabs.

You'll also need to keep track of printout and, in case nothing was printed in the line (i.e., there were no non-(blanks or tabs)), you also skip printing of \n, to delete the entirely blank lines.

If you had to remove only the trailing blanks (or only the trailing tabs), you wouldn't need a string at all -- just a counter of how many of those you've encountered. Unfortunately, your task is a bit more complex, and so is a solution.

My modification does not solve the "line is too long" problem, but it does reduce it to "a line has more than 1000 blanks+tabs in a row" problem.

Now, I give you some comments on your actual code.

First, I have one simple remark:

    int i = -1, j; /* two counters */
    ...
    while ((c=getchar()) != EOF) {
        line[++i] = c;
        if (c == '\n') {
            j = i + 1;
            ...
            i = -1;

I think this would be more natural if i was the next character to be written to (instead of the last), i.e.,

    int i = 0, j; /* two counters */
    ...
    while ((c=getchar()) != EOF) {
        line[i++] = c;
        if (c == '\n') {
            j = i;
            ...
            i = 0;

I think that this is also more customary approach when working on strings, since after the loop you often get to do something like s[i] = '\0' instead of s[i+1] = '\0'. This also makes it possible to use the unsigned variable, although I don't see much practical use for that.

Second, this is unnecessary:

            while (line[--j] == ' ' || line[j] == '\n' || line[j] == '\t')
                line[j] = '\0';

You simply need to remember the value of i when you encounter blank or tab the first time after you encountered a character that is not one of these. You can do so easily by keeping the old value of c in a  variable, let's call it oc:

    oc = 'x'; /* anything non-(blank or tab), so it works properly for the empty lines */
    while ((c=getchar()) != EOF) {
        line[i++] = c;
        if ((c == ' ' || c == '\t') && (oc != ' ' && oc != '\t'))
            start_of_trailing_blanks_and_tabs = i;
        ...
        c = 'x';
    }

You could event replace oc by a properly set Boolean flag (in C, this is, of course, of type int).

And, as my last remark, this is also unnecessary:

            for (j = 0; j <= i; j++)
                line[j] = '\0';

You set the end of string elsewhere in the code, and it's only the first \0 that counts.

I also have one suggestion on the style: I'd make a function to identify these characters, or just use isspace() from the ctype library. The later is not exactly what you need, as it also identifies the feed and the carriage return, but I think it is in the spirit of what is asked in the exercise.


Average of multiple vectors with different length I have several profiles that are in form of mappings (id,value) and I need to find average between that profiles (values). The issue is that not all profile consist of the same ids, so that the lengths are different, as here:

1 2 3 4 5 6
-----------
1 3 - 5 - 9
0 - 1 1 2 -

The first row denotes element_id and rows 2 and 3 denote the user profiles. '-' is the element with no value. The average for these 2 profiles is: {0.5, 3, 1, 3, 2, 9}.

I have implemented is as following:

private static void calcAverage(Map<Integer, Map<Integer, Integer>> profiles) {
        Map<Integer, Float> res = new HashMap<>();
        Map<Integer, Integer> elemcount = new HashMap<>();
        Map<Integer, Integer> elemsums = new HashMap<>();

        for (Map<Integer, Integer> profile : profiles.values()) {
            for (Map.Entry<Integer, Integer> element : profile.entrySet()) {
                if (!elemcount.containsKey(element.getKey())) {
                    elemcount.put(element.getKey(), 1);
                    elemsums.put(element.getKey(), element.getValue());
                } else {
                    int count = elemcount.get(element.getKey());
                    elemcount.put(element.getKey(), count + 1);

                    int sum = elemsums.get(element.getKey());
                    elemsums.put(element.getKey(), element.getValue() + sum);
                }
            }
        }

        for (Map.Entry<Integer, Integer> entry : elemcount.entrySet()) {
            System.out.println(entry.getKey() + " => " + (double)elemsums.get(entry.getKey())/(double)entry.getValue());
        }
    }

The source is working perfectly. It does what I want.

The only thing, I wanted to ask, if it is possible to optimize it somehow? Because when I have 1k profiles with 1k elements each, it will take really much time to work on.

Your code is O(NM) because it iterates through every value, for every id.

You need to iterate through the values once, adding the values to some structure which tracks the sum of every value for every id, and the number of values seen.

This lets you calculate average = (sum_values)/n_values in O(N+M), where N is number of values, M is number of ids.


Function to replace color in .bmp I wrote a function to replace color in a bitmap image. For beginners in image processing, it could be exclusively useful, since they could use it to replace the entire gamma of a color or to replace a color with gradient/abstract lines, following the function's logic.

The main problem of the function, according to performance, is that it isn't fast enough.
For larger images/replacing more then one color, this could take a minute or even more.
I am sure there is a huge room for improvement of this function, therefore speed-optimized.

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

#define IMAGE_WIDTH         500
#define IMAGE_OFFSET_SIZE   2
#define IMAGE_OFFSET_PIXELS 54

typedef unsigned char byte;
typedef unsigned long dword;

int main (int argc, char *argv[])
{
    dword bitmap_color_replace (char *, byte, byte, byte, byte, byte, byte);

    printf("Pixels successfully replaced: %i\n",
    bitmap_color_replace("sample.bmp", 255, 255, 255, 0, 200, 255));

    return EXIT_SUCCESS;
}

/**************************************************************************/

dword
bitmap_color_replace
(char *file_name, byte old_r, byte old_g, byte old_b, byte new_r, byte new_g, byte new_b)
{
    dword fp_height = 0;
    dword fp_size;
    FILE* fp = fopen(file_name, "r+b");
    dword i, pixels_replaced = 0;

    byte new_color[3];

    new_color[0] = new_b;
    new_color[1] = new_g;
    new_color[2] = new_r;

    fseek(fp, IMAGE_OFFSET_SIZE, SEEK_SET);
    fp_size = fgetc(fp) + fgetc(fp)*256 + fgetc(fp)*(256*256) + fgetc(fp)*(256*256*256);

    for(i = IMAGE_OFFSET_PIXELS; i < fp_size; i += sizeof(new_color))
    {
        byte current_r, current_g, current_b;

        fseek(fp, i, SEEK_SET);

        if(i == IMAGE_OFFSET_PIXELS + (IMAGE_WIDTH * (fp_height+1))) // skip padding
        {
            fp_height++;
            i += IMAGE_WIDTH % 4;
            fseek(fp, IMAGE_WIDTH % 4, SEEK_CUR);
        }

        current_b = fgetc(fp);
        current_g = fgetc(fp);
        current_r = fgetc(fp);

        if(current_b == old_b && current_g == old_g && current_r == old_r)
        {
            fseek(fp, i, SEEK_SET);
            fwrite(new_color, sizeof(new_color), 1, fp);
            pixels_replaced++;
        }
    }

    fclose(fp);
    return pixels_replaced;
}

I see some ways in which this code might be improved.

Make sure printf format specifiers match the data

In the sample main, the format specifier used is "%i" but bitmap_color_replace returns a dword which is an alias for unsigned long, so the correct format specifier would actually be "%lu" for that data.

Omit return statement in main

This line

return EXIT_SUCCESS;

is not needed with modern C compilers. Getting to the end of main implicitly means that the program has succeeded, so the compiler will include code to do that return if you simply omit it.

Rearrange the code to reduce the need for declarations

A function declaration is only needed by the compiler if it hasn't already encountered the function itself.  With that said, if the bitmap_color_replace function is moved to the top of the file, above main, the function declaration within main can be omitted, making main a single printf.

Omit unused variables

Because argc and argv are unused, you could use the alternative form of main:

int main ()

Avoid hardcoding values

The IMAGE_WIDTH, IMAGE_OFFSET_PIXELS are not valid for most images.  Rather than hardcode those, you could simply read them from the file header in the same way that fp_size is read.

Avoid uneccessary fseek calls

There are a lot of fseek calls within the current routine which are not necessary because the program moves linearly through the data anyway.  Eliminating them would likely speed up the program.

Calculate pad size just once

The padding size is the same for every row so you can calulate it based on the image width and the size of each color.

Process only the pixel data

In some version of BMP files, there is data after the pixel data, so the current code, which continues to the end of the physical file, would overwrite that data.  Better would be to calculate just the size of the pixel data which is obtained from the height and width of the image.

Don't overwrite the input file

Create a new file instead of overwriting the input file.  This helps the user as well as preventing file corruption if something goes wrong during the processing of the file. It may also speed the program.

Process larger chunks at a time in memory

Instead of reading the colors byte at a time, it would likely speed things up considerably by processing entire rows at a time, or even the entire file as a memory image.  I/O is often the bottleneck for programs like this, so minimizing it can result in considerable time savings.

Note the correct data order

BMP files contain pixel data as R,G,B in that order.  It's important to get the order right to correctly match colors.

One possibility

Here's a version of the code with some, but not all of these ideas incorporated:

// these are absolute offsets to the two most important
// items in the BMP file
#define IMAGE_PIXEL_START   10
#define IMAGE_WIDTH         18

typedef unsigned char byte;
typedef unsigned long dword;

dword
bitmap_color_replace
(char *file_name, byte old_r, byte old_g, byte old_b, byte new_r, byte new_g, byte new_b)
{
    FILE* fp = fopen(file_name, "r+b");
    dword pixels_replaced = 0;

    byte new_color[3];

    new_color[0] = new_r;
    new_color[1] = new_g;
    new_color[2] = new_b;

    byte old_color[3];

    fseek(fp, IMAGE_PIXEL_START, SEEK_SET);
    dword fp_pixelstart = fgetc(fp) + fgetc(fp)*256 + fgetc(fp)*(256*256) + fgetc(fp)*(256*256*256);
    fseek(fp, IMAGE_WIDTH, SEEK_SET);
    dword fp_width = fgetc(fp) + fgetc(fp)*256 + fgetc(fp)*(256*256) + fgetc(fp)*(256*256*256);
    dword fp_height = fgetc(fp) + fgetc(fp)*256 + fgetc(fp)*(256*256) + fgetc(fp)*(256*256*256);
    // rows are padded to a multiple of 4 bytes
    dword padsize = (4 - ( (sizeof(new_color) * fp_width) & 0x3 )) & 0x3;

    fseek(fp, fp_pixelstart, SEEK_SET);
    for (int row = fp_height; row; --row)
    {
        for (int col = fp_width; col; --col)
        {
            fread(old_color, sizeof(old_color), 1, fp);
            if(    old_color[0] == old_r
                && old_color[1] == old_g
                && old_color[2] == old_b)
            {
                fseek(fp, -sizeof(old_color), SEEK_CUR);
                fwrite(new_color, sizeof(new_color), 1, fp);
                pixels_replaced++;
            }
        }
        if (padsize)
        {
            fseek(fp, padsize, SEEK_CUR);
        }
    }
    fclose(fp);
    return pixels_replaced;
}


Isolate a Database Change Within Django Transaction.Atomic I have been typically adding the @transaction.atomic decorator to my endpoints and appreciate if a request fails at any point the data completely rolls back.  However, some of my endpoints will make an API call to another API service.  If my token for that API service is invalid, I refresh the token.  This is all well and good until an exception occurs after the API token has been refreshed.  The transaction is rolled back including the token information which then will be stale.  This includes the new refresh token information so I'm now unable to refresh the auth token.

I attempted to get around this situation by distributing the token refresh to a celery task and waiting for the result as a way of isolating that database change.   Even if the requests fails later on, the token information remains while the rest is rolled back.

Here is a simplified example

@transaction.atomic()
def post(request):
  response = api_call()
  db_operation(response['result']) #  Could potentially have an exception

def api_call(allow_refresh=True)
  response = requests.post(url, params)

  if response.status_code == 401:
    if allow_refresh:
     refresh_token_task.delay().get(timeout=10)
     response = api_call(allow_refresh=False)
    else:
      raise Exception('Invalid authorization') # In the case refreshing token doesn't resolve authorization issues, this prevents infinite loop.

  return response

Phew! I thought I was in the clear except... sometimes I distribute api calls.  It didn't occur to me but I realized calling celery tasks from celery tasks easily risks locking.   So now I've written out a solution that involves chaining.

def post(request):
  chain(api_call_task.s(), refresh_token_task.s(), api_call_task.s(), db_operation_task.s())()

@task
def api_call_task(initial_response=None)
  if initial_response and initial_response.status_code != 401:
    return response

  response = requests.post(url, params)

  return response

@task
def refresh_token_task(response):
  if response.status_code == 401:
    refresh_token()

  return response

@transaction.atomic()
@task
def db_operation_task(response):
  if response.status_code == 401:
    raise Exception('Invalid authorization')

  db_operation(response['result'])

I think this works to a degree but gosh what a confusing mess.  By chaining the functions, the response is continuously passed through which determines if the token needs to be refreshed and/or if the call needs to be made again and then finally to handle the db operation based upon the response to the api.

Is there a simpler way? Marginal improvement? Bad practice involved?  Would it better to just let go of transaction.atomic?  Let me know if my simplified pseudo code can use clarification.

Let's start off with what's probably the most important note here: if you are running into issues with atomic transactions, pushing the database work off to Celery (or another worker thread) inherently makes your transactions non-atomic. It sounds like this has been working for you currently, but this will not always work and may have unintended consequences.

So I'm going to review this from two different angles:

Handling atomic transactions within APIs when you only need part of it to be atomic
Chaining Celery tasks that need to execute conditionally

If only part of your handling needs to be atomic, don't make everything atomic

In your hypothetical example, you make it clear that db_operation needs to be atomic and that's why you are wrapping the entire handle in transaction.atomic. I'm assuming that db_operation is actually a series of calls, or something more complex than just a single call, which is why you couldn't just decorate that call with transaction.atomic. But you only appear to care about these calls being atomic, which is why the call to refresh_token still needs to be committed to the database even if there are issues within db_operation.

My suggestion would be to use transaction.atomic as a context manager instead of as a decorator. This would result in your hypothetical view looking something like:

def post(request):
    response = api_call()
    with @transaction.atomic():
        db_operation(response['result']) #  Could potentially have an exception

This still allows db_operation to remain atomic while ensuring that api_call is always committed to the database.

Celery has advanced method chaining, use it to your advantage

You correctly identified that calling one Celery task and waiting for a response can easily cause a deadlock or starvation, which is why Celery explicitly recommends that you don't do it.

Getting an error when making an API call because your access token has expired is generally considered to be an exceptional case. Celery provides functionality for handling exceptions, so don't be afraid to use it. You found Celery's chaining functionality, but what is also useful is the linking functionality between tasks that works very similarly.

def post(request):
    api_call_task.apply_async(
        link=[db_operation_task.s()],
        link_error=[refresh_token_task.s(), api_call_task.s(), db_operation_task.s()]
    )

You'll see in this case that if the original call to api_call_task returns an error, we are instructing Celery to call refresh_token_task, then api_call_task again (it should have a valid token) and then eventually db_operation_task like we originally planned. This allows for api_call_task to error out twice, such as if there was an error not relating to the token refresh, without risking calling db_operation_task with potentially invalid data.

Because Celery provides a clear callback format and allows you to define a chain of methods to be called during the callbacks, you can design your tasks to only focus on what they really care about: calling those other methods.

@task
def api_call_task():
    response = requests.post(url, params)

    if response.status_code == 401:
        raise Exception('Access token needs to be refreshed')

    return response

@task
def refresh_token_task():
    refresh_token()

@task
@transaction.atomic()
def db_operation_task(response):
    db_operation(response['result'])

This has the benefit of allowing you to handle errors naturally within the flow, without forcing every step in the chain to perform the error handling for you.

Bonus: Celery tasks can also be run synchronously, use that to your advantage

In your hypothetical example, you defined api_call and api_call_task when talking about the Celery task and the actual API call itself. If you have control over api_call (it's not a third-party call), you can actually just condense this down to a single method. If you call a method wrapped with @task() without calling .delay() or .apply_async(), the method is called synchronously and Celery is never contacted. This allows you to design methods which can be called either asynchronously using Celery, or synchronously in the course of your own application, without having to duplicate a lot of code or add in additional special cases.

Because Celery allows you to execute the code synchronously that would otherwise be executed asynchronously, this also makes testing of these tasks much easier. In tests you can call them synchronously and ensure the functionality works as expected, while knowing that in the real world there may be a time delay that you need to account for.


Calculating the maximum drawdown of a set of returns I wrote a simple function that calculates and returns the maximum drawdown of a set of returns. I am trying to squeeze as much efficiency for speed out of the code as possible. I've got it down to about as fast as I can go. Does anyone have suggestions on how to write this function more efficiently, perhaps through list comprehensions etc.?

import numpy as np

def max_drawdown(returns):

    draw_series = np.array(np.ones(np.size(returns)))
    max_return = 0; max_draw = 1; draw = 1
    returns = returns + 1

    for r in range(returns.count()-1, 0, -1):

        if returns[r] > max_return:
            max_return = returns[r]

        else:
            draw = returns[r] / max_return
            if draw < max_draw:
                max_draw = draw

        draw_series[r-1] = -(1 - max_draw)

    return draw_series

You are correct to point out that your implementation is terribly inefficient compared to most built-in Numpy operations of similar complexity.  100X speedup would be reasonable for large arrays once you eliminate the python loop.  It would be trivial to replace your python loop with some Numpy indexing or broadcasting if it weren't for the pesky draw_series[r-1] = -(1 - max_draw) line which operates on the next-to-be-computed item in the array.  This is analogous to Numpy's accumulate but obviously there's no implementation of it for your particular algorithm.  You have three options as I see it:

Study your problem hard and see if you decompose it into numpy-only
accumulate and regular operations.
See if your algorithm can be expressed as a compiled numexpr
expression.
Compile this function using Cython, f2py or ctypes

One minor improvement is to replace returns = returns + 1 with returns += 1 which will operate in-place and avoid re-allocating the returns array.

Hope this helps.  good luck.


JavaScript: Weighted Random Generator I'm attempting to create a function that will give me a "fish" at random, though a bias random depending on the weight value for the "fish".

var FISH = {
    "level1": [
          //["name",      xp, weight]
            ["Shrimp",    10, 95],
            ["Sardine",   20, 85],
            ["Herring",   30, 75],
            ["Anchovies", 40, 65],
            ["Mackerel",  40, 55]
        ]
};

function randomRange(min, max) {
    return Math.random() * (max - min) + min;
}

function getRandomFish(level) {
    var fishForLevel = FISH[level],
        numberOfFish = fishForLevel.length,
        chance = randomRange(0, 100);

    if (numberOfFish > 1) {

        var fish = fishForLevel[Math.floor(randomRange(0, numberOfFish))];

        if (chance <= fish[2]) {
            return fish;
        } else {
            return getRandomFish(level);
        }

    } else {
        return fishForLevel[0];
    }
}

Example of outcome: http://jsfiddle.net/qAvAs/

If this could be made more efficient, how would one do so?

I'd suggest you select a random number that's from 0 to the total weight of your fish.  Then, each fish can have a piece of that random range according to it's weight which gives it the weighting you want.  This ends up giving each fish a number of buckets that corresponds to it's weighting value and then you pick a random number from 0 to the total number of buckets and find out who's bucket the random number landed in.

It's the same idea as turning each weighting number into a percentage change and then picking a random number from 0 to 99.

This code should do that:

var FISH = {
    "level1": [
          //["name",      xp, weight]
            ["Shrimp",    10, 95],
            ["Sardine",   20, 85],
            ["Herring",   30, 75],
            ["Anchovies", 40, 65],
            ["Mackerel",  40, 55]
        ]
};

function getRandomFish(level) {
    var fishForLevel = FISH[level];
    var fishTotalWeight = 0, fishCumWeight = 0, i;
    // sum up the weights
    for (i = 0; i < fishForLevel.length; i++) {
        fishTotalWeight += fishForLevel[i][2];
    }
    var random = Math.floor(Math.random() * fishTotalWeight);
    // now find which bucket out random value is in

    for (i = 0; i < fishForLevel.length; i++) {
        fishCumWeight += fishForLevel[i][2];
        if (random < fishCumWeight) {
            return(fishForLevel[i]);
        }
    }
}


Work out if a string is "fieldname" or "tablename.fieldname", and assign variables Is there a neater way to write this code?

    var table, field, dbFieldEntries;
    var s = 'one.two';
    // The DB field is always the first parameter
    dbFieldEntries = s.split( '.' );
    if( dbFieldEntries.length === 1 ){
      field = dbEntryEntries[ 0 ];
    } else {
      table = dbEntryEntries[ 0 ];
      field = dbEntryEntries[ 1 ];
    }

Basically, s can be either something or something.other.
If it's something, then table is undefined and field is something; it it's something.other, then table is something and field is other.

Assuming that field always gets the value of the last part of dbFieldEntries you could do:

field = dbEntryEntries[ dbFieldEntries.length - 1 ];
if ( dbFieldEntries.length > 1 ) {
  table = dbEntryEntries[ 0 ];
}

Besides this, s is a bad variable name.