A linked list with push pop append and destructor I tried to implement a linked list that can do pop(), push(), append(), printall(), and so on, and also I tried to handle the wraparound features, and de-wrap it when check if the list is cyclic to avoid endless loop, but I am sure this wrap and de-wrap features can be implemented better...

#include <iostream>

struct Node{
    int value;
    Node* next;
};

class LinkedList{

    std::size_t count;
    Node* head;

    public:
    void pop();           //pop from head
    void push(int);       //push from head
    void append(int);     //append at end
    void wraparound();    //wrap around the list
    bool isCyclicDwrap(); //check if cyclic, if yes, de-wrap-around it

    void printll() const;
    std::size_t size() const { return count; }

    LinkedList(): head(nullptr),count(0) {}
    ~LinkedList();
};

void LinkedList::pop(){

  if(head==nullptr){
    std::cout<<"empty stack !"<<std::endl;
    exit(0);
  }

  Node* cur = head;
  Node* tmp = cur->next;
  head = tmp;
  delete cur; count--;

}

void LinkedList::append(int data){
    Node* cur = head;
    Node* tmp = new Node;
    tmp->value = data;
    tmp->next = nullptr;

    if(!cur){
        head = tmp; count++;
    }
    else{
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = tmp; count++;
    }

}

void LinkedList::wraparound(){
    Node* cur =head;
    while(cur->next != nullptr)
        cur=cur->next;

    cur->next = head;
}

bool LinkedList::isCyclicDwrap()
{
    Node *n1, *n2;
    n1 = head;
    n2 = head->next;

    do{
        n1 = n1->next;
        n2 = n2->next->next;

        if(n1 == n2){

            Node* cur =head;
            size_t cnt=count;
            while(--cnt != 0)
                cur=cur->next; //move to the last node
            cur->next=nullptr; // -> de-warp-around !

            return true;
        }

    }while(n1 != head);

    return false;
}

void LinkedList::push(int data)
{
    Node* cur = (Node*)malloc(sizeof(Node));
    cur->value=data;
    cur->next=head;
    count++;
    head=cur;
}

void LinkedList::printll() const{
    if(head==nullptr)
        std::cout<<"empty Linkedlist!"<<std::endl;
    Node* cur = head;
    while(cur != nullptr){
        std::cout << cur->value << '\n';
        cur = cur->next;
    }
}

LinkedList::~LinkedList()
{
    Node* cur = head;

    while (cur != NULL)
    {
        Node* next = cur->next;
        delete cur;
        cur = next;
    }

    head = NULL;
}

int main(){
    LinkedList LL;
    LL.append(5);
    LL.append(6);
    LL.append(7);
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.wraparound();
    std::cout<<"Cyclic: "<<LL.isCyclicDwrap()<<"; if 1, then remove the Cyclic feauture!"<<std::endl;

    LL.push(4); //push
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
}

I see a few things that could improve your code quite a bit:

Linked List Structure Design

You declare your Node structure outside of your LinkedList class in the header file; this means that anyone including the header file can access your Node structure and use it in their code. This is bad OO design since the Node structure is really an implementation detail of the LinkedList. Therefore, the user should be able to use the linked list without ever having to use (or the ability to use) the Node data structure. To fix this issue, I would declare the Node data structure inside of the private space of your LinkedList class. Moreover, I would provide a constructor for the Node data structure that will populate the values of the structure for me:

class LinkedList {
    struct Node {
        int data;
        Node *next;
        Node(int d, Node *n = nullptr) :
            data(d), next(n) {}
    }* head;
};

In this way, I can use the more C++ way of initializing objects on the heap over the more C way of doing things.

C++ way (recommended):

Node *node = new Node(data);

More C-style way (deprecated / not recommended):

Node *node = new Node();
node->data = data;
node->next = nullptr;

Use C++ Style

Speaking of C and C++ ways, do NOT mix new and malloc in C++ code - especially when you're using delete to free objects allocated by both. new and delete call constructors/destructors whereas malloc and free don't. Use delete to free new'd objects and free to free malloc'd objects. This code is invalid and can cause issues:

void LinkedList::push(int data)
{
    Node* cur = (Node*)malloc(sizeof(Node));
    cur->value=data;
    cur->next=head;
    count++;
    head=cur;
}

Why not use the more C++ way of doing things:

void LinkedList::push(int data)
{
    Node* cur = new Node(data, head); // use constructor I defined for you above.
    ++count;
    head = cur;
}

In addition, keep your style consistent between NULL and nullptr. In C++11 and beyond, always prefer to use nullptr.

Linked List API

I would rename some of your functions to be a bit more descriptive. For example, I would make wraparound() be called make_cyclic(). I would also provide a counter function called make_acyclic() to break the cycle. To check for a cycle, I would rename your function to is_cyclic(). I would also add another function is_empty() to signal when the list is empty and a size() function to return the size of your list so far; otherwise, what's the point of the count member variable? There is also the added benefit that the empty() member function could clear up a bunch of bugs in your code:

Bugs

In your wraparound() and isCyclicDwrap() functions, you don't check for the case when the list is empty (when the head is pointing to nullptr). If the list is empty, derefrencing nullptr like this:

Node* cur = head;
while(cur->next)

is a segmentation fault error waiting to happen. The fix is to check if the list is empty before doing such operations.

Finally, I find your implementation of making the list acyclic (if it is cyclic) a little too heavy and breaks the principle that functions should only have one purpose. We could do something like this to split the two ideas of checking for a cycle and breaking one:

bool LinkedList::is_cyclic() const
{
    if (is_empty()) {
        return false;
    }

    Node *n1 = head, *n2 = head->next;
    while (n1 != n2) {
        if (!n2 || !n2->next) {
            return false;
        }
        n1 = n1->next;
        n2 = n2->next->next;
    }
    return true;
}

void LinkedList::make_acyclic()
{
    if (is_empty() || !is_cyclic()) {
        return;
    }

    Node *curr = head;
    while (curr->next != head) { // move to the end
        curr = curr->next;
    }
    curr->next = nullptr; // break the cycle
}

Simplify Some Functions

With the newly defined Node constructor, append() can become:

void LinkedList::append(int data){

    if(!head){
        head = new Node(data);
    }
    else{
        Node *cur = head;
        while (cur->next){
            cur = cur->next;
        }
        cur->next = new Node(data);
    }
    ++count;
}


Changing background with JavaScript I am in the process of learning JS and I constantly have feeling that my code is bloat and not optimal.

I built this simple DEMO of background changing on click.  Can somebody tell me if this is good approach to build this, what can be improved?  Can I write this with less code?

jsFiddle

HTML

CSS

div {
width: 200px;
height: 200px;
border: 1px solid dimgrey;
display: flex;
margin: auto;
transition: background-color .4s ease-out;
}

div > div {
width: 100px;
height: 100px;
border: 1px solid darkgray;
}

JS

var divOne = document.getElementById("one"),
    divTwo = document.getElementById("two"),
    divOneStyle = divOne.style,
    divTwoStyle = divTwo.style,
    RGB = ["red","green","blue"],
    YPB = ["yellow","purple","black"];

var colorMeRGB = function (event) {
    divOneStyle.backgroundColor = RGB[Math.floor(Math.random() * RGB.length)];
    event.stopPropagation();
};
divOne.addEventListener("click",colorMeRGB,false);

var colorMeYPB = function (event) {
    divTwoStyle.backgroundColor = YPB[Math.floor(Math.random() * YPB.length)];
    event.stopPropagation();
};
divTwo.addEventListener("click",colorMeYPB,false);

You could create a curried function that takes an array of colors, an element, and an event. Then you build your other functions by partial application:

var divOne = document.getElementById("one"),
  divTwo = document.getElementById("two"),
  RGB = ["red","green","blue"],
  YPB = ["yellow","purple","black"];

var colorMe = function(colors) {
  return function(elem) {
    return function(event) {
      elem.style.backgroundColor = colors[Math.random() * colors.length |0];
      event.stopPropagation();
    };
  };
}

var colorMeRGB = colorMe(RGB);
var colorMeYPB = colorMe(YPB);

divOne.addEventListener("click", colorMeRGB(divOne), false);
divTwo.addEventListener("click", colorMeYPB(divTwo), false);

In you have something like LoDash at hand, you can use curry:

var colorMe = _.curry(function(colors, elem, event) {
  ...
})

You could also use this inside the event, which refers to the element, but  find it can be confusing, and you may lose flexibility.

If you think of data flow and transformations, rather than steps, you can come up with a slightly more DRY solution:

var colorMe = _.curry(function(colors, elem, event) {
  elem.style.backgroundColor = colors[Math.random() * colors.length | 0];
  event.stopPropagation();
});

var data = [
  {id: 'one', colors: ['red','green','blue']},
  {id: 'two', colors: ['yellow','purple','black']}
];

data.forEach(function(x) {
  var elem = document.getElementById(x.id);
  elem.addEventListener('click', colorMe(x.colors, elem), false);
});

But if you're reusing the elements it is recommended to cache them in variables.

Note I used |0 to floor the number. This is quite common, and it cleans up that line a bit.

DEMO: http://jsfiddle.net/uqkutqht/1/


GZip archiver for log files It compiles, works well, solves my problem of zipping old or big log files and removes them from a hard drive. However, following this answer, I would like to know what was wrong with the code.

Dir.foreach(FileUtils.pwd()) do |f|
    if f.end_with?('log')
        File.open(f) do |file|
            if File.size(f) > MAX_FILE_SIZE
                puts f
                puts file.ctime
                puts file.mtime

                # zipping the file
                orig = f
                Zlib::GzipWriter.open('arch_log.gz') do |gz|
                  gz.mtime = File.mtime(orig)
                  gz.orig_name = orig
                  gz.write IO.binread(orig)
                  puts "File has been archived"
                end

                #deleting the file
                begin
                  File.delete(f)
                  puts "File has been deleted"
                rescue Exception => e
                  puts "File #{f} can not be deleted"
                  puts "       Error #{e.message}"
                  puts "======= Please remove file manually =========="
                end
            end
        end
    end
end

My proposal, please see also the comments in the code.

require 'zlib'
MAX_FILE_SIZE = 1024 #One KB

#Use a glob to get all log-files
Dir["#{Dir.pwd}/*.log"].each do |f|
  #skip file, if file is small
  next unless File.size(f) > MAX_FILE_SIZE
  #Make a one line info
  puts "#{f}: #{File.size(f)/1024}KB, created #{File.ctime(f)} modified #{File.mtime(f)} "

  # zipping the file - each log in a file
  Zlib::GzipWriter.open("arch_#{File.basename(f)}.gz") do |gz|
    gz.mtime = File.mtime(f)
    gz.orig_name = File.basename(f) #filename without path
    #File.read should be fine for log files. Or is there a reason for IO.binread
    gz.write File.read(f)
    puts "File #{f} has been archived"
  end

  #deleting the file
  begin
    #~ File.delete(f)
    puts "File #{f} has been deleted"
  rescue Exception => e
    puts "File #{f} can not be deleted"
    puts "       Error #{e.message}"
    puts "======= Please remove file manually =========="
  end
end

Remark:

This solution creates one gz-file per log file. Your old solution created one arch_log.gz. If there were two log-files, the 2nd would overwrite the 1st.


Recursive categories fetch and view I have categories and subcategories in my view. The code looks like this

  <% Category.roots.each do |category| %>

    <%= category.name %>
    <% if !category.children.empty? %>

      <%= category.decorate.draw_tree %>

    <% end %>

  <% end %>

I'm basically using a decorator to make it recursive

class CategoryDecorator < Draper::Decorator

  delegate_all
  decorates :category

  def draw_tree

    children.inject("") do |memo, child|

      memo << "
#{child.name}"
      memo << "
#{child.decorate.draw_tree}
" if not child.children.empty?
      memo << "
"

    end.html_safe

  end

end

It works fine. But I'm writing HTML inside a Ruby class and I don't like the idea, I'de like to keep it in the view. I tried to play with &block to turn it like following

  <% Category.roots.each do |category| %>

    <%= category.name %>
    <% if !category.children.empty? %>

      <% category.decorate.draw_tree do |child| %>

<%= child.name %>
      <% if child.children.any %>

<%= child.decorate.draw_tree %>
"
      <% end %>

"

      <% end %>

    <% end %>

  <% end %>

Sadly, I couldn't make it work so far. I think I lack methodology here. How can I rewrite this code ?

Here's how I'd do it:

In your view, simply call a recursive method on each category:

  <% Category.roots.map do |category| %>
     <%= draw_tree(category) %>
  <% end %>

And now in a helper file (app/helpers/category_helper.rb?), this is the "right" place to put HTML helpers. First, in pseudo-code:

def draw_tree(category)

    <%= category.name %>
    <% category.children.each do |child| %>

      <%= draw_tree(child) %>

    <% end %>

end

Now, to actually make this work, rather than writing a string and calling #html_safe, a much cleaner (and generally safer) approach is to use content_tag. The end result is:

def draw_tree(category)
  content_tag(:li, class: "col-md-2") do
    link_to('#', category.name)
    category.children.map do |child|
      content_tag(:ul, draw_tree(child))
    end
  end
end

I haven't actually run the above code, so apologies if there's some small mistake. But hopefully you get the idea :)


For each of the visitors, find if they were present within a time period: code is running slow I'm working with a pandas dataframe which describes the start and end time of visits. A toy example of the data could be as follows:
import pandas as pd
data = pd.DataFrame({"start": [pd.Timestamp("2020-01-01 01:23:45"), pd.Timestamp("2020-01-01 01:45:12")], "end": [pd.Timestamp("2020-01-01 02:23:00"), pd.Timestamp("2020-01-01 03:12:00")]})

I want to break down these visits into periods: from 01:00 to 02:00, there were two visitors, from 02:00 to 03:00, also two, and from 03:00 to 04:00, only one of the visitors was present. To achieve this, I'm generating bounds for my periods and generate a dataframe with overlaps:
periods = pd.DataFrame({"period_start": pd.date_range(start = "2020-01-01 01:00:00", end = "2020-01-01 03:00:00", freq = "1H"), "period_end": pd.date_range(start = "2020-01-01 02:00:00", end = "2020-01-01 04:00:00", freq = "1H")})

def has_overlap(A_start, A_end, B_start, B_end):
  latest_start = max(A_start, B_start)
  earliest_end = min(A_end, B_end)
  return latest_start <= earliest_end

periods_breakdown = pd.DataFrame()
for i in range(3):
  ps = periods.period_start[i]
  pe = periods.period_end[i]
  periods_breakdown["period" + str(i)] = data.apply(lambda row: has_overlap(row.start, row.end, ps, pe), axis = 1)

On the toy data, this code returns
  period0 period1 period2
0    True    True   False
1    True    True    True

The problem is that the actual data has 1M visits that I want to break down over 6000 periods, and the code runs for roughly 140 hours.

Is there a better way to count visitors from this sort of data?
Are there performance improvements to this code?

I think it is slow because your periods_breakdown is gigantic, and to fill each cell you have to compute its value.
But what you compute is whether each individual visit overlapped with each other visit, which is overkill.
If what you want is to know when there is two visits (or more) overlapping, but don't need to know which specific ones, you can simply count how many visits there are during each hour slot and you will know when there was an overlap because the count will be more than one.
Based on the data you provided :
import pandas as pd
data = pd.DataFrame({"start": [pd.Timestamp("2020-01-01 01:23:45"),
                               pd.Timestamp("2020-01-01 01:45:12")],
                     "end": [pd.Timestamp("2020-01-01 02:23:00"),
                             pd.Timestamp("2020-01-01 03:12:00")]})

NUMBER_OF_PERIODS = 6  # FIXME: use an upper bound
visitors_count_per_hour = [0] * NUMBER_OF_PERIODS

year_start = pd.Timestamp(year=2020, month=1, day=1, hour=0, minute=0, second=0, microsecond=0)
for visit_start, visit_end in zip(data["start"], data["end"]):
    print(f"there was a visit between {visit_start} and {visit_end}")
    start_hour = visit_start.floor("H")
    end_hour = visit_end.floor("H")
    print(f"  in hours, it spanned from {start_hour} to {end_hour} included")
    visit_hours = pd.date_range(start=start_hour, end=end_hour, freq="1H")
    offset = len(pd.date_range(start=year_start, end=start_hour))
    print(f"  it started at period n°{offset}")
    for i, visit_hour in enumerate(visit_hours):
        print(f"  - so we count one person at hour {visit_hour}")
        visitors_count_per_hour[i + offset] += 1

print(visitors_count_per_hour)

periods_breakdown = pd.DataFrame()
for hour_index, visitor_count in enumerate(visitors_count_per_hour):
    slot_hour = year_start + pd.Timedelta(hours=hour_index)
    periods_breakdown["period" + str(hour_index)] = [slot_hour] + \
                                                    ([True] if visitor_count > 1 else [False]) + \
                                                    [visitor_count]

print(periods_breakdown)

which outputs
there was a visit between 2020-01-01 01:23:45 and 2020-01-01 02:23:00
  in hours, it spanned from 2020-01-01 01:00:00 to 2020-01-01 02:00:00 included
  it started at period n°1
  - so we count one person at hour 2020-01-01 01:00:00
  - so we count one person at hour 2020-01-01 02:00:00
there was a visit between 2020-01-01 01:45:12 and 2020-01-01 03:12:00
  in hours, it spanned from 2020-01-01 01:00:00 to 2020-01-01 03:00:00 included
  it started at period n°1
  - so we count one person at hour 2020-01-01 01:00:00
  - so we count one person at hour 2020-01-01 02:00:00
  - so we count one person at hour 2020-01-01 03:00:00
[0, 2, 2, 1, 0, 0]
               period0              period1              period2              period3              period4              period5
0  2020-01-01 00:00:00  2020-01-01 01:00:00  2020-01-01 02:00:00  2020-01-01 03:00:00  2020-01-01 04:00:00  2020-01-01 05:00:00
1                False                 True                 True                False                False                False
2                    0                    2                    2                    1                    0                    0

My result is slightly different than yours because my period0 is 2020-01-01 00:00:00 while you started at 01:00:00.
Speaking of performance, your algorithm will fill N*M cells, N being the number of visits, M being the number of slots in your data. With the values you provided (N=1000000 and M=6000), it is not surpising it slow.
My solution, by not comparing each visit with each other, only does roughly N+M computes, which is a whole algorithmic complexity class down.
I'm no expert of pandas, so there may a better way to write the code to do essentially the same thing. But if you want to have an even quicker program, maybe you can simplify your problem (find another algorithm) or make better use of pandas than me.


Angular filter based on properties I wrote a Angular filter to use filters based on properties that handles some specific properties differently.

Is there a way to improve or use some built-in Angular filter to avoid extra code?

Usage:

<div ng-repeat="item in items | myObjectFilter: { someProp: user.uid, pending: true }">

Code:

angular.module('app', []).filter('myObjectFilter', function () {
    function _filter(source, search) {
        if (!source) { return source; }

        var result = [], defaultFilters;

        //default filter setting
        defaultFilters = {
            pending: false,
            refusedAt: null
        };

        search = angular.extend({}, defaultFilters, search);

        angular.forEach(source, function (value, key) {
            var isFiltered = true;

            for (var x in search) {
                if (value.hasOwnProperty(x)) {
                    var isEqual = false;

                    // handle specific properties or simply compare
                    switch (x) {
                        case 'someProp':
                        case 'someProp2':
                            isEqual = value[x].uid == search[x];
                            break;
                        default:
                            isEqual = value[x] == search[x];
                            break;
                    };

                    isFiltered = isFiltered && isEqual;

                    if (!isEqual) {
                        break; //exit loop if filter not passed
                    }
                }
            }

            if (isFiltered) {
                result.push(value); // add item to filterd result
            }
        });

        return result;
    };

    return _filter;
});

Named functions

I like the idea of named functions. It helps when you debug your app - you are getting error with name of function instead of "anonymous".

Defalt options

The default options location is good place to keep it. Filter has to be independant from controller and should manage its own data. Although, the default options object is created at every reference to filter. This is waste of resources.

angular.module('app', []).filter('myObjectFilter', function myObjectFilter() {
    //default filter setting
    var defaultFilters = {
        pending: false,
        refusedAt: null
    };

    function _filter(source, search) {
        if (!source) { return source; }
        var result = [];
        search = angular.extend({}, defaultFilters, search);
        ...

Last if

This code:

isFiltered = isFiltered && isEqual;
if(!isEqual) {
    break; //exit loop if filter not passed
}

checks for isEqual two times.

//isFiltered = isFiltered && isEqual; //you can delete this line
if(!isEqual) {
    isFiltered = false;
    break; //exit loop if filter not passed
}

My version checks it only once. I know that you don't get much performance here, but imagine situation when you would like to change the statement for making isFiltered false. You need to change condition in two places. This can lead to serious headache and long debugging in case one of them is forgotten ;)


Wrapper for caching methods in ASP.NET I have written a caching wrapper method for some of my services. The actual wrapper method is written as follows:

public T GetFromCache<T>(string key, Func<T> defaultValuePredicate, object cacheLock, TimeSpan duration)
{
    lock (cacheLock)
    {
        var result = _cache[key] is T ? (T)_cache[key] : default(T);
        if (Equals(default(T), result))
        {
            result = defaultValuePredicate();
            if (!Equals(default(T), result))
            {
                _cache.Add(key, result, null,
                            DateTime.Now.Add(duration),
                            System.Web.Caching.Cache.NoSlidingExpiration,
                            System.Web.Caching.CacheItemPriority.Default,
                            (cacheKey, value, reason) =>
                            Debug.WriteLine(string.Format("{0} Dropped from cache becasue {1}", cacheKey, reason)));
            }
        }

        return result;
    }
}

A typical use case is this:

public class SomeService
{
    private static readonly object _lock = new object();

    public string GetSomeValue()
    {
         return GetFromCache("SomeService_GetSomeValue", () =>
                            {
                                //Expensive operation here
                            },
                            _lock,
                            TimeSpan.FromSeconds(600));
    }

}

In all the example code that I've seen floating around the web people never seem to lock around expensive, but cached operations. The reason I lock is to prevent the same operation kicking off twice, duplicating the effort.

Is this approach reasonable and robust, or does it need serious modification to make it more reliable?

I see a minor issues with the code: you are locking every time, no matter if it's needed on not. I would implemented GetFromCache like this

public T GetFromCache<T>(string key, object cacheLock, Func<T> defaultValuePredicate, TimeSpan duration)
{
    object result = _cache[key]; // using object as T may be value type and _cache may return null

    if (result == null || !(result is T))
    {
        lock (cacheLock)
        {
            result = _cache[key];  // rechecking value from cache as another thread may already initialize it
            if (result == null || !(result is T))
            {
                result = defaultValuePredicate();
                if (!Equals(default(T), result))
                {
                    _cache.Add(key, result, null,
                            DateTime.Now.Add(duration),
                            System.Web.Caching.Cache.NoSlidingExpiration,
                            System.Web.Caching.CacheItemPriority.Default,
                            (cacheKey, value, reason) =>
                            Debug.WriteLine(string.Format("{0} Dropped from cache becasue {1}", cacheKey, reason)));
                }
            }
        }
    }

    return (T)result;
}

It's a little more code (+1 if statement) but it doesn't lock thread every time you access it.


Get the best rational approximations for any real number in builtin Python Best rational approximations is a technical term and not subjective. The best rational approximations are the convergents of a value plus it's semi convergents that are closer to the original value than the previous convergents.

Hi everyone,

I've written some quick code in Python that is my tool for exploring various aspects of music theory, number theory, and my obsession with OEIS. It's currently written to spit out a list of the ratio's themselves. It would be quite easy to tweak to your needs. This may also help anyone exploring the logic of infinite continued fractions and convergents. I use the decimal module here for precision. It's written so you can paste any value you want into the input field - that can easily be tweaked to accept any real number from code. Phasers to stun. I call it my approximilator.

(Python 3)

import decimal
import math

D = decimal.Decimal

def contFrac(x, k):
    """Cont Frac from Real value"""
    cf = []
    q = math.floor(x)
    cf.append(q)
    x = x - q
    i = 0

    while x != 0 and i < k:
        q = math.floor(1 / x)
        if q > k:
            break
        cf.append(q)
        x = 1/x - q
        i += 1

    return cf

def bestra(clist, app):
    """Best Rational Approximation from Cont. Frac"""
    hn0, kn0 = 0, 1
    hn1, kn1 = 1, 0
    """Best Rational Approx Init"""
    ran, rad = 0, 0
    conlist, ralist, finallist = [], [], []

    for n in clist:
        for i in range(1, n+1):
            ran = (hn0 + (i*hn1))
            rad = (kn0 + (i*kn1))
            try:
                if D.copy_abs(app-D(ran/rad)) < D.copy_abs(app-D(hn1/kn1)):
                    ralist.append({'ratio': f'{ran}/{rad}', 'denom' : rad})
            except:
                pass
        hn2 = (n*hn1)+hn0
        kn2 = (n*kn1)+kn0
        conlist.append({'ratio': f'{hn2}/{kn2}', 'denom': kn2})
        hn0, kn0 = hn1, kn1
        hn1, kn1 = hn2, kn2

    for x in sorted(conlist+ralist, key = lambda i: i['denom']):
        finallist.append(x['ratio'])

    return list(dict.fromkeys(finallist))

if __name__ == "__main__":
    value = D(input('Input value to approximate: '))
    prec = len(str(value))*2
    decimal.getcontext().prec = prec
    vc = contFrac(value, prec)
    print(bestra(vc, value))

Some output for Pi to entice:

'3/1', '13/4', '16/5', '19/6', '22/7', '179/57', '201/64', '223/71', '245/78', '267/85', '289/92', '311/99', '333/106', '355/113', '52163/16604', '52518/16717', '52873/16830', '53228/16943', '53583/17056', '53938/17169', '54293/17282', '54648/17395', '55003/17508', '55358/17621', '55713/17734', '56068/17847', '56423/17960'

PEP-8 Guidelines

Follow the PEP-8 Style Guidelines, such as:

1 space around operators (1 / x instead of 1/x)
snake_case for identifiers & functions (cont_frac instead of contFrac)

Import As

The preferred method of creating an alias for an import is:

from decimal import Decimal as D

Since you are only using the floor function from math, you could also:

from math import floor

Docstrings

"""Docstrings""" exist to help a user with the usage of a function.  There are usually in triple quotes, because they should be multi-line strings, with enough information to be useful to the caller, without needing the caller to read the source code.

def continue_fraction(x, k):
    """
    Construct a continued fraction from a real value

    Parameters:
        x (float): Real value to determine continued fraction of
        k (int): A loop limit representing accuracy somehow

    Returns:
        List[Int]: List of continued fraction values
    """

A """docstring""" is the first statement of a module, class, function or method, if it is a string.  In particular,

    """Best Rational Approx Init"""

is not a """docstring""", because it is not the first statement.  It should be a comment.

    # Best Rational Approx Init

Comments are used to document the source code, for someone reading the source code.  In contrast, """Docstrings""" are used to provide help to the user of the item, so they do not have to read the source code.  It is displayed using the help() command:

>>> help(continue_fraction)

Don't use docstrings as comments, or vise-versa.

Superfluous Parenthesis

        ran = (hn0 + (i*hn1))
        rad = (kn0 + (i*kn1))

should be written as

        ran = hn0 + i * hn1
        rad = kn0 + i * kn1

Named Tuple

Consider using a named tuple, instead of using dictionaries for fixed content items.

from collections import namedtuple

fraction = namedtuple("fraction", "ratio, denom")

...

        ...
        ralist.append(fraction(f'{ran}/{rad}', rad))
        ...

    for x in sorted(conlist + ralist, key=lambda i: i.denom):
        finallist.append(x.ratio)

Collection

Why are you maintaining ralist separate from conlist, when you later add the two lists together and sort them??  Why not just maintain a single list?

List Comprehension

List appending is inefficient:

    finallist = []
    for x in sorted(conlist + ralist, key=lambda i: i.denom):
        finallist.append(x.ratio)

due to repeated reallocations of the list as the list size grows.  It is better to construct and initialize the list in one operation:

    finallist = [ x.ration for x in sorted(conlist + ralist, key=lambda i: i.denom) ]

Useless

This operation:

return list(dict.fromkeys(finallist))

takes a list, turns it into a dictionary with each list item as a key (all the dictionary values are None), and then constructs a list from just the dictionary's keys.  Uhm.   As long as the dictionary is kept in insertion order, which it is because you are using f'' strings so must be using Python 3.6 or later, this is indistinguishable from:

return finallist

Apparently the goal here was to remove duplicates.  A comment would have helped; it is not obvious.

Meaningful Function and Variable Names

What is contFrac and bestra?  It would be way clearer to use continued_fraction and best_rational_approximation, especially if you are writing this for "anyone exploring the logic of infinite continued fractions".

conlist, ralist, clist, app, ran and rad are equally obscure.


Saving class including a container with pickle I am writing a program that has a 'base' class called Group. The class will have only one instance. Aside from some properties and methods, it needs to keep track of a variable amount of group_companies.
After working with the program (that may involve adding or deleting group_companies), I want to save the current state of my work to a file, which can be imported in the next session. I read that pickle can be used for that and even for 'pickling' classes. I have seen similar questions but none answering my question, or yet too complicated for me to be understood.
I came up with the following solution hereunder that seems to work.
Is there a better approach than my solution? I tried to define the group_companies as a class variable, but then it won't 'unpickle' (the group_companies dictionary remains empty).
The next step will involve changing the group_companies from dictionaries to classes themselves. Will that still work?
That you for your help and insights.
import pickle

class Group():
    """ Creates a group, its metadata and its methods. """

    def __init__(self, name, rates):
        self.name = name
        self.rates = rates

    def add_group_company(self, name, descriptor):
        try:
            self.group_companies[name] = descriptor
        except Exception:
            self.group_companies = {}
        self.group_companies[name] = descriptor

    def __repr__(self):
        return "This is group {}".format(self.name)

# Initialize some variables
group_name = 'XYZ'
rates = {'EUR': 1.0000,
         'USD': 1.2364,
         'NOK': 8.3254,
         }

# Create a group and add some group_companies
group = Group(group_name, rates)
group.add_group_company('ABC', 'some data')
group.add_group_company('DEF', 'moar data')

# pickle the class
with open('data', 'wb') as f:
    pickle.dump(group, f)

# Delete class instance and test if succesfully deleted
del(group)
try:
    print(group)
except Exception:  # catchall
    print("Variable appears no longer to exist.")

# Unpickle my class
with open('data', 'rb') as f:
    group = pickle.load(f)

# Test the results (satisfactory)
print(group)
print(group.group_companies)

The pickle module is fine for such a use case, you just have to be
aware of its limitations.
In particular you'd run into problems in case the current class
definition doesn't match the one of the stored object any more, even
something like a renaming of the class is problematic.

Is there a better approach than my solution? I tried to define the
group_companies as a class variable, but then it won't 'unpickle'
(the group_companies dictionary remains empty).

Well, unless you meant to do a class variable it's fine as it is.  At a
glance I wouldn't expect that pickle on an object of a class would
write out class properties anyway, so this all seems like it should
be.  (It wouldn't make sense to write out class properties every single
time an object that's simply an instance of the class is being pickled,
not to mention reading that data back in every single time.)

The next step will involve changing the group_companies from
dictionaries to classes themselves. Will that still work?

Presumably you'd create a Company class and add that to the
dictionary?  That'd work.  Or if you mean you'd change group_companies from a
dictionary to an object, yes, sure, that will work fine as long as the
pickle module understands the objects (which it will in this case).
That said, the code looks fine.  Two small things I'd perhaps change:

Consider using __str__ instead of __repr__ and the difference in
output between group and print(group) in the REPL
(This is group XYZ and <__main.Group object at 0x...> for the
__str__ variant).  repr should return the "canonical string
representation of the object.  [...] eval(repr(obj)) == obj."  That's
a good guideline for how it should behave, while str is simply for
the printed representation of the object (my words, couldn't find a
quote quickly).

self.group_companies should be initialised from the start in
__init__.  This simplifies add_group_company greatly and will
ensure the object is already in a "valid" state from the start.

Btw. del is a statement, so del group is a bit more explicit in what
it does, removing the group name from the local variable bindings.


Fitting multiple images in a given width I was looking for a function which would take the overall width, max height, min height parameters as the input and fit multiple images in the given overall width adjusting their width.

For an example in this page, all the images (in the same row) should get auto-adjusted to the same height, keeping their original aspect ratio with JavaScript changing their widths.

Is there a simple and better way to do this?

The solved example page is here.

$(function(){

//var pics;

var pic1 = {height:"10", width:"20", ap:1.374, rh:0};
var pics = [pic1];

//pics.push(pic3);

//$('#test').html(pics[2].height);

$('#some').imagesLoaded(function() {

$('#test').html('test ');
$('#some img').each(function(index) {
  //setting const height
  $(this).height(150);
  var apic = {height:$(this).height() , width: $(this).width() ,ap: $(this).width() / $(this).height() , rh:0};
  pics.push(apic);

});

$('#test').append(pics.length+ '
');

for (var j=1; j <pics.length;j++) {

  $('#test').append(pics[j].width  + ' ' + pics[j].ap + '
');
}
$('#test').append('Calculating width ' + '
');
var set = [0];

for (var j=1; j <pics.length;j++) {

  var t = 0;
  var c = j
  do {
    t = t+ pics[c].width;
    $('#test').append(c + ' ' + t+ '
');
    c=c+1;
  }while (t < 645 && c<pics.length);
  c=c-1;
  if(t>645) {
    c = c -1;
  }

  set.push(c);
  j = c;

}
$('#test').append('Sets are:
');
var v = 1;
var st = 0;
for (p = 1; p<set.length; p++) {

  $('#test').append(set[p] + ' ');
  st = v;
  v = set[p];
  $('#test').append(p + ': ');

  var tot = 0;
  var inc = 0;
  while(tot < 645 ) {
    var tot1=0;
    for(var g = st; g<v+1; g ++) {
      tot1 =tot1+ (pics[g].ap * (pics[g].height+inc));

    }
    tot=tot1;
    inc = inc+1;
  }
  for(var g = st; g<v+1; g ++) {
      $('#some img').eq(g-1).height ( 150 + inc);
  }

  $('#test').append( '
');
  v = v+1;

}

$('#test').append('
');

/*
var tot = 0
var wid;
var wid1;
var inc=0;
var r = 1;
for (r =1; r<pics.length-1; r++) {
  inc = 0;
  tot = 0;
while ( tot < 645) {

  wid = pics[r].ap * (pics[r].height+inc);
  wid1 = pics[r+1].ap * (pics[r+1].height+inc);

  tot = wid + wid1;
  inc = inc+ 1;
}

$('#test').append('Total ' + inc +' '+ wid  + ' ' + wid1 + '
');
$('#some img').eq(r-1).height ( 150 + inc);
$('#some img').eq(r).height ( 150 + inc);
  r=r+1;
  */
}
  );

});

Fit images to width.

To make n images fit a width while keeping each image's aspect do the following.

Get the height that the images need to be to fit.

// images is an array of loaded images
// width is the width to fit
// returns the height images must be to fit.
function getFitSize(images,width){
    var totalWidth = 0;  // Holds the total aspect width
    // sum aspect for each image for total aspect width
    images.forEach(img=>{
        totalWidth +=  img.width / img.height;
    })
    // then get height to fit the required width
    return width / totalWidth;  // the height for all to fit
}

var height = getFitSize(images,500); // fit images to 500 pixels across

With the height you just need to use that to scale the width by the aspect and set the height.

Size each image.

image.width = height * (image.width / image.height); // the image width that
                                                     // will fit
image.height = height;

Example

A Javascript example showing usage of above method. Images are loaded one at a time and made to fit the available page width.

const imageURLList = [ "https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Renaissance_Center%2C_Detroit%2C_Michigan_from_S_2014-12-07.jpg/380px-Renaissance_Center%2C_Detroit%2C_Michigan_from_S_2014-12-07.jpg",
"https://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Paulus_Moreelse_-_Zelfportret.jpg/300px-Paulus_Moreelse_-_Zelfportret.jpg",
"https://upload.wikimedia.org/wikipedia/en/thumb/b/bb/Maull_%26_Fox_-_Fanny_Bullock_Workman.jpg/300px-Maull_%26_Fox_-_Fanny_Bullock_Workman.jpg",
"https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Toompea_loss_2014.jpg/380px-Toompea_loss_2014.jpg",
"https://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Winslow_Homer_-_The_Gulf_Stream_-_Metropolitan_Museum_of_Art.jpg/350px-Winslow_Homer_-_The_Gulf_Stream_-_Metropolitan_Museum_of_Art.jpg"
];
const images = [];
function getFitSize(images,width){
    var totalWidth = 0;
    images.forEach(img=>{ totalWidth +=  img.naturalWidth / img.naturalHeight })
    return width / totalWidth;
}
// load images one at a time for effect only
function loadImage(){
    const image = new Image;
    image.src = imageURLList.shift();
    image.onload = function(){
        images.push(image);
        const width = imageContainer.getBoundingClientRect().width;
        const height = Math.floor(getFitSize(images,width));
        images.forEach(image => {
            image.style.width = Math.floor(height * (image.width / image.height)) + "px";
            image.style.height = height + "px";
        });
        imageContainer.appendChild(image);
        if(imageURLList.length > 0){
            loadingInfo.textContent = "Loading image " + (images.length +1);
            setTimeout(loadImage,2000);
        }else{
            loadingInfo.textContent = "Loading complete";
        }
    }
}
loadingInfo.textContent = "Loading image " + (images.length +1);
setTimeout(loadImage,2000);
#imageContainer {width : 100%;}
body { font-family : arial; margin: 0px; overflow: hidden;}
.noEdge {margin: 0px;  padding : 0px; }
.atr { font-size : small; }
Fit images to width.

Images from Wikipedia:Picture of the day/January 2017


Efficient Prime Sieve - Haskell I'm new to Haskell, and am trying to learn the basics with a simple function that will calculate the list of primes up to a given value (using the Sieve of Eratosthenes). Here is my code so far, which has the problem of becoming very slow for large inputs nmax:

primes :: Integer -> [Integer]
primes nmax
  | nmax <= 2 = [2]
  | otherwise = sieve (2:[3,5..nmax])
  where
    sieve :: [Integer] -> [Integer]
    sieve [] = []
    sieve [a] = [a]
    sieve (p:xs) = p : sieve [multiple*p+offset | multiple <- [1..(last xs) `quot` p], offset <-[1..(p-1)], multiple*p+offset `elem` xs]

I am aware of this resource which gives implementations of Eratosthenes' Sieve, however, their methods are beyond me as I'm only just beginning. I'm also aware of this this question, but they have used entirely different methods again. I would like to know what it is about my code that is so inefficient.

Example timings:

primes 100 takes 0.01s and uses 0 bytes of RAM.
primes 1000 takes 0.41s and uses ~38.5MB of RAM.
primes 2000 takes 3.15s and uses ~153MB of RAM.

I suspect the problem lies in checking if multiple*p+offset is an element of the list xs, but I'm not sure how to circumvent this check.

The underlying complexity

  I suspect the problem lies …

Ah, but we don't like to suspect. Just as our compiler tells us that we're missing a semicolon, our profiler will tell us where we lose time. Let's add a main first:

main :: IO ()
main = readLn >>= print . length . primes

Now, it's easier to measure:

$ ghc -prof -auto-all -O2 Primes.hs
$ echo 1000 | ./Primes +RTS -s -p
168
      23,717,912 bytes allocated in the heap
       1,235,856 bytes copied during GC
         111,776 bytes maximum residency (2 sample(s))
          26,880 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0        44 colls,     0 par    0.000s   0.002s     0.0000s    0.0002s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0005s    0.0008s

  INIT    time    0.000s  (  0.002s elapsed)
  MUT     time    0.375s  (  0.372s elapsed)
  GC      time    0.000s  (  0.003s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.375s  (  0.377s elapsed)

  %GC     time       0.0%  (0.8% elapsed)

  Alloc rate    63,247,765 bytes per MUT second

  Productivity 100.0% of total user, 99.5% of total elapsed

$ echo 2000 | ./Primes +RTS -s -p
303
      84,381,928 bytes allocated in the heap
       9,612,184 bytes copied during GC
         137,048 bytes maximum residency (2 sample(s))
          28,592 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0       161 colls,     0 par    0.062s   0.015s     0.0001s    0.0005s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0003s    0.0004s

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    2.297s  (  2.399s elapsed)
  GC      time    0.062s  (  0.015s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    2.359s  (  2.416s elapsed)

  %GC     time       2.6%  (0.6% elapsed)

  Alloc rate    36,737,710 bytes per MUT second

  Productivity  97.4% of total user, 95.1% of total elapsed

Before we have a look at the profile, we already see that something is amiss. For twice the maximum, your code takes almost 7 times the time: 0.375s for numbers up to 1000, and 2.297 seconds for 2000. That indicates that your algorithm doesn't have the right complexity to begin with. Let's check 4000:

$ echo 4000 | ./Primes +RTS -s -p
550
     302,844,912 bytes allocated in the heap
      70,455,392 bytes copied during GC
         431,144 bytes maximum residency (37 sample(s))
          36,976 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0       546 colls,     0 par    0.016s   0.093s     0.0002s    0.0006s
  Gen  1        37 colls,     0 par    0.031s   0.012s     0.0003s    0.0013s

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time   16.766s  ( 17.134s elapsed)
  GC      time    0.047s  (  0.105s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time   16.812s  ( 17.240s elapsed)

  %GC     time       0.3%  (0.6% elapsed)

  Alloc rate    18,063,443 bytes per MUT second

  Productivity  99.7% of total user, 97.2% of total elapsed

For twice the elements, we have 8 times the time. This indicates that you have \$\mathcal O(n^3)\$ complexity.

An unhelpful profile

Let's have a look at the generated profile. In case you don't know GHC's profiling feature yet: -prof enables profiling during compilation, but you still need to tell GHC what to profile (in your code). -auto-all enables profiling of your functions without changing your code. And +RTS -p enables profiling at runtime.

This will create a .prof file. However, it's not very helpful, since most of your logic is in a list comprehension, and that's not profiled:

Sun Sep 11 08:24 2016 Time and Allocation Profiling Report  (Final)

       Primes +RTS -s -p -RTS

    total time  =       15.19 secs   (15193 ticks @ 1000 us, 1 processor)
    total alloc = 185,477,264 bytes  (excludes profiling overheads)

COST CENTRE  MODULE  %time %alloc

primes.sieve Main    100.0   99.9

                                                             individual     inherited
COST CENTRE     MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN            MAIN                        44           0    0.0    0.0   100.0  100.0
 main           Main                        89           0    0.0    0.0   100.0  100.0
  primes        Main                        91           1    0.0    0.1   100.0  100.0
   primes.sieve Main                        92         550  100.0   99.9   100.0   99.9
 CAF            GHC.Read                    76           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding.CodePage    73           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding             68           0    0.0    0.0     0.0    0.0
 CAF            Text.Read.Lex               61           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.Text          57           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.FD            56           0    0.0    0.0     0.0    0.0
 CAF:main1      Main                        52           0    0.0    0.0     0.0    0.0
  main          Main                        88           1    0.0    0.0     0.0    0.0
 CAF:lvl5_r3TO  Main                        51           0    0.0    0.0     0.0    0.0
  main          Main                        90           0    0.0    0.0     0.0    0.0

We see that most of the work is done in primes.sieve. That's nothing new, though. We would like to see where the additional work happens. Remember that I said that we usually have to add profiling annotations (also called cost centers)? Now it's time to add them:

    sieve (p:xs) = p : sieve [multiple*p+offset
                             | multiple <- {-# SCC multiple #-} [1..(last xs) `quot` p]
                             , offset <- {-# SCC offset #-} [1..(p-1)]
                             , {-# SCC elem #-} multiple*p+offset `elem` xs]

Now let's see what takes all that time (and space):

    Sun Sep 11 08:35 2016 Time and Allocation Profiling Report  (Final)

       Primes +RTS -s -p -RTS

    total time  =       14.27 secs   (14270 ticks @ 1000 us, 1 processor)
    total alloc = 186,588,744 bytes  (excludes profiling overheads)

COST CENTRE  MODULE  %time %alloc

elem         Main     98.9   46.7
primes.sieve Main      0.7    9.4
offset       Main      0.4   43.3

                                                             individual     inherited
COST CENTRE     MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN            MAIN                        44           0    0.0    0.0   100.0  100.0
 main           Main                        89           0    0.0    0.0   100.0  100.0
  primes        Main                        91           1    0.0    0.1   100.0  100.0
   primes.sieve Main                        92         550    0.7    9.4   100.0   99.9
    elem        Main                        95     1813869   98.9   46.7    98.9   46.7
    offset      Main                        94        9263    0.4   43.3     0.4   43.3
    multiple    Main                        93         549    0.0    0.4     0.0    0.4
 CAF            GHC.Read                    76           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding.CodePage    73           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding             68           0    0.0    0.0     0.0    0.0
 CAF            Text.Read.Lex               61           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.Text          57           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.FD            56           0    0.0    0.0     0.0    0.0
 CAF:main1      Main                        52           0    0.0    0.0     0.0    0.0
  main          Main                        88           1    0.0    0.0     0.0    0.0
 CAF:lvl5_r3UH  Main                        51           0    0.0    0.0     0.0    0.0
  main          Main                        90           0    0.0    0.0     0.0    0.0

Let's focus on the new centers:

    elem        Main                        95     1813869   98.9   46.7    98.9   46.7
    offset      Main                        94        9263    0.4   43.3     0.4   43.3
    multiple    Main                        93         549    0.0

Wow. For 4000 elements, we have 1813869 elem checks. That's almost \$4000^{1.8}\$. Each of those elem checks is linear. While the size of the list decreases, at worst case it has size \$\mathcal O(n) \$. We end up with \$\mathcal O(n^{2.8})\$ complexity from our empirical point of view, which is really close to our real behaviour.

Prime time for efficiency

Now that we now that the elem checks destroy our runtime, and the creation of offset eats the other half of your RAM, let's get back to the drawing board and remember what Eratosthenes' Sieve is supposed to do:

You write down the numbers from 2 to \$n\$.
You start with the next number that you haven't looked at yet
If it's crossed out, take the next one
If it's not crossed out, cross all it's multiple out
Go to step 2, until you've run out of numbers

However, here's what you do:

You write down the numbers from 2 to \$n\$ (only the odds).
You start with the next number that you haven't looked at and that isn't crossed out yet
Put "maybe prime?" markers on all numbers that aren't multiples of it
Cross out all multiples of your number (all that don't have a marker; that step is implicit)
Go to step 2, until you've run out of numbers

The difference in step 3 is huge. For any number \$p\$, there are at most \$\lfloor \frac{n}{p} \rfloor\$ multiples in the range \$[1,n]\$. How many aren't? Well, \$n - \lfloor \frac{n}{p} \rfloor\$. And since \$p > 2\$, we will always check too many elements.

Now, let's change your sieve so that it actually implements the first algorithm:

    sieve :: [Integer] -> [Integer]
    sieve [] = []
    sieve [a] = [a]
    sieve (p:xs) = p : sieve [prime | prime <- xs
                                    , prime `rem` p /= 0]

Before I post the result, let us verify that this really does the same as yours: for a single \$p\$, you created a list of all non-divisible numbers that were also in xs. Therefore, you ended up with:

$$ \{x \in xs \} \cap \{n \in \mathbb N : n \neq 0 \mod p \}$$

Which is almost literally in the code above. Now for the result:

$ echo 4000 | ./Primes +RTS -s -p
2000
     339,984,336 bytes allocated in the heap
      24,834,416 bytes copied during GC
          89,728 bytes maximum residency (2 sample(s))
          27,736 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0       459 colls,     0 par    0.047s   0.040s     0.0001s    0.0003s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0004s    0.0007s

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    0.250s  (  0.290s elapsed)
  GC      time    0.047s  (  0.041s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.297s  (  0.332s elapsed)

  %GC     time      15.8%  (12.2% elapsed)

  Alloc rate    1,359,937,344 bytes per MUT second

  Productivity  84.2% of total user, 75.2% of total elapsed

Still too much garbage collection, but that's fine for a start.

Additional discussion

Try to avoid last. Instead, you could have used

multiples <- [i * p | i <- [1..nmax`quot`p]]

or similar. last has to traverse all the list.

Next, it's great that you've added type signatures, but make sure that you can actually need Integer. On your platform, Int will probably go up to \$2^{63}-1\$, which is more than enough. It will also make your program a lot faster, since Integer has an overhead.

And last but not least, make the code slightly more readable by adding whitespace. If you get a vertical scrollbar on CR, it's usually a sign that your lines are too long.

Oh, and by the way: this variant will still be too slow compared to Java, but you're probably using another data structure with random access abilities in Java, whereas we're creating a "new" list in Haskell all the time.

TL;DR

Verify that you actually implemented the algorithm that you want to implement.


Parsing HTTP Headers in C++ I am building a web server from scratch and trying to make certain tasks faster by embedding C code into the mix for performance. Specifically I'm worried about how the std::string class with the .find() and other functions compare to straight pointer arithmetic.

#include <iostream>
#include <map>
#include <string>

std::map<std::string, std::string> http_request;

void parse_header( void * );

int main()
{

    char * msg= "GET / HTTP/1.1\r\n"
                "Host: 192.241.213.46:6880\r\n"
                "Upgrade-Insecure-Requests: 1\r\n"
                "Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8\r\n"
                "User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/602.4.8 (KHTML, like Gecko) Version/10.0.3 Safari/602.4.8\r\n"
                "Accept-Language: en-us\r\n"
                "Accept-Encoding: gzip, deflate\r\n"
                "Connection: keep-alive\r\n\r\n";

    parse_header( msg );

}

void parse_header( void *msg )
{
    char *head = (char *) msg;
    char *mid;
    char *tail = head;

    if( sizeof( msg ) == 0 )
    {
        return;
    }

    // Find request type
    while( *head++ != ' ');
    http_request[ "Type" ] = std::string( ( char * ) msg ).substr( 0 , ( head - 1) - tail );

    // Find path
    tail = head;
    while( *head++ != ' ');
    http_request[ "Path" ] = std::string( ( char * ) msg ).substr( tail - ( char *)msg , ( head - 1) - tail );

    // Find HTTP version
    tail = head;
    while( *head++ != '\r');
    http_request[ "Version" ] = std::string( ( char * ) msg ).substr( tail - ( char *)msg , ( head - 1) - tail );

    // Map all headers from a key to a value
    while( true )
    {
        tail = head + 1;
        while( *head++ != '\r' );
        mid = strstr( tail, ":" );

        // Look for the failed strstr
        if( tail > mid )
            break;

        http_request[ std::string( ( char * ) msg ).substr( tail - ( char *)msg , ( mid ) - tail  ) ] = std::string( ( char * ) msg ).substr( mid + 2 - ( char *) msg , ( head - 3 ) - mid );
    }

    // Determine if successful
    std::cout << http_request[ "Host" ] << std::endl;
    std::cout << http_request[ "Upgrade-Insecure-Requests" ] << std::endl;
    std::cout << http_request[ "Accept" ] << std::endl;
    std::cout << http_request[ "User-Agent" ] << std::endl;
    std::cout << http_request[ "Accept-Language" ] << std::endl;
    std::cout << http_request[ "Accept-Encoding" ] << std::endl;
    std::cout << http_request[ "Connection" ] << std::endl;
}

Data comes in via the linux socket.send() function, so it is a void * type. I directly send that data to a parse_header function to create a std::map for easy access. Is it necessary to be this low-level, or can this speed be obtained by the STL?

Note: I killed OO design for a minimal example. The end-goal has an HTTP class.

Note++: I'd prefer to have this code review pertain to performance rather than c++ semantics, I'd like it to be as conforming as possible while also being fast and lightweight. This seems to be the purest form of the cluge of C/C++.

First of all, The Http server send all the headers Line by Line. In your sample i see you created a dummy sample with the next buffer:

char * msg= "GET / HTTP/1.1\r\n"
            "Host: 192.241.213.46:6880\r\n"
            "Upgrade-Insecure-Requests: 1\r\n"
            "Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8\r\n"
            "User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_3) AppleWebKit/602.4.8 (KHTML, like Gecko) Version/10.0.3 Safari/602.4.8\r\n"
            "Accept-Language: en-us\r\n"
            "Accept-Encoding: gzip, deflate\r\n"
            "Connection: keep-alive\r\n\r\n";

I suppose that you first recive all the header before analyzing it with your method void parse_header( void *msg )... and that is the reason that the task to get each Key-Value is so hard because you are using parsers like this:

http_request[ std::string( ( char * ) msg ).substr( tail - ( char *)msg , ( mid ) - tail  ) ] = std::string( ( char * ) msg ).substr( mid + 2 - ( char *) msg , ( head - 3 ) - mid );

What will I do to improve your code:

I will keep the map<string,string> to store all headers.
Read the header one line by time and, before to continue with the other line, analyze it.
I don't see any issue with the code to parse the first but I will modify it to analyze is a single line and simplify the parsers.

If you read and analyze one line by line, the code to map all the keys with values could be like this:

void parseFirstLine(string line)
{

    string key = "";
    string value = "";
    int  position, lpost;

    // Find request type
    position = line.find(' ');
    http_request[ "Type" ] = line.substr(0, position);
    position++; //Skip character ' '

    // Find path
    position = line.find(' ', lpost);
    http_request[ "Path" ] = line.substr(lpost, (position-lpost));
    position++; //Skip character ' '

    // Find HTTP version
    http_request[ "Version" ] = line.substr(position);
}

void parseHeader(string line)
{

    string key = "";
    string value = "";

    if(data.size() == 0) return;

    int posFirst = line.find(":",0); //Look for separator ':'

    key = line.substr(0, posFirst);
    value = line.substr(posFirst + 1);

    http_request[key] = value;
}

(*) This code could have some bugs because I'm writing this code without any developer environment to review this.

Is your decision where you get each line to analyze, at the moment you get it from socket reading or after finishing of read all the header.


Counting numbers that are divisible by 3 and can be produced from the digits of a given number I'm trying to solve this problem from codewars.

  Problem

  Given a certain number, how many multiples of three could you obtain with its digits? Suppose that you have the number 362. The numbers that can be generated from it are: 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632 and among those 3, 6, 36, 63 are  divisible by 3.

  We need a function that can receive a number ann may output in the following order:

  the amount of multiples(without 0)
  the maximum multiple

My solution

I have found all possible permutations of the digits of the given number and checked if the number is divisible by 3. Here is my code -

from itertools import permutations as perm
from functools import reduce

def to_int(digs):    # takes a list of digits of an integer and returns the number
    n = reduce(lambda total, d: 10 * total + d, digs, 0)
    return n

def find_mult_3(num):
    digs = list(map(int, str(num)))
    perms = []        # stores all possible permutations with the digits of num
    for i in range(1, len(digs)+1):
        perms.extend(list(p) for p in set(perm(digs, i)))

    count, mx = 0, 0
    seen = set()      # to keep track of divisors already seen
    if 0 in perms:
        perms.remove(0)
    for p in perms:
        n = to_int(p)
        if n % 3 == 0 and n not in seen:
            if mx < n:
                mx = n
            count += 1
            seen.add(n)

    return [count, mx]

But getting TLE, is there any way to make this program faster or any other clever way to solve this problem? Please ask if there is any need for clarification in any part of the code.

The algorithm can be improved, so that we do less work:

Use the fact that multiples of 3 have a sum of digits that's also a multiple of 3.  That means we can select all the distinct combinations of digits, and discard any that don't sum to a multiple of 3.  Only for those sets not discarded, we can compute the number of permutation of the selected digits.  (Note that we don't have to actually produce all the numbers, merely count them - so if we have n different digits, we count n! permutations; if p of them are identical, then n!/p!, and so on).

For example, with input 5532:

5+5+3+2 is 15, this gives us 4!/2! permutations that are multiples of 3 (and remember 5532 as the largest such multiple).
5+5+3 is 13, so ignore it.
5+5+2 is 12, giving us 3!/2! more permutations to add to our count.
5+3+2 is 10; ignore it.
5+5 is 10; ignore it.
5+3 is 8; ignore it.
5+2 is 7; ignore it.
2+3 is 5; ignore it.
5 alone - ignore
3 alone - add one to the count.
2 alone - ignore.

And we're done; the total count is 4!/2! + 3!/2! + 1 = 16.


Two related hierarchies of classes In order to do its work, a DataProcessor needs Data and otherData.

One instance of Data will be shared over a set of DataProcessor,
but each DataProcessor has its own otherData.

For sharing Data instances, fields of Data could not be defined inside DataProcessor,
thus, there are two hierarchies: Data and DataProcessor.

Each subClass of DataProcessor relates a subClass of Data.

And I have tried three design to fit the requirement, which way is the best? why?

Is my design bad? Why?

Is there any other solution?

Is there any existing design pattern to solve this kind of problem?

It is said that this is a "parallel inheritance hierarchy". Should I avoid this? How? Or is it a good design for my requirement, and do I not need to avoid?

Data hierarchies

abstract class Data {
    int field1;
}

abstract class AData extends Data {
    int field2;
}

class AAData extends AData {
    int field3;
}

class BData extends Data {
    int field4;
}

DataProcessor hierarchies way 1, each super class instance keeps a private reference to Data

abstract class DataProcessor {
    private Data data;
    protected Object otherData;
    DataProcessor(Data data){
        this.data = data;
    }
    void doSomethingUsingDataAndOtherData(){}
}

abstract class ADataProcessor extends DataProcessor {
    private AData data;
    ADataProcessor(AData data) {
        super(data);
        this.data = data;
    }
    void doSomethingUsingADataAndOtherData(){}
}

class AADataProcessor extends ADataProcessor {
    private AAData data;
    AADataProcessor(AAData data) {
        super(data);
        this.data = data;
    }
    void doSomethingUsingAADataAndOtherData(){}
}

class BDataProcessor extends DataProcessor {
    private BData data;
    BDataProcessor(BData data) {
        super(data);
        this.data = data;
    }
    void doSomethingUsingBDataAndOtherData(){}
}

DataProcessor hierarchies way 2, only top superclass instance keeps a protected reference to Data, when subclass needs to use the data, it has to cast the data to its expected Data subclass. And I don't want to define DataProcessor as DataProcessor, because once introducing generic types, I have to use generic types everywhere, and sometimes using generic types is not so simple (i.e. we can not create a generic array in java).

abstract class DataProcessor {
    protected Data data;
    protected Object otherData;
    DataProcessor(Data data) {
        this.data = data;
    }
    void doSomethingUsingDataAndOtherData(){}
}

abstract class ADataProcessor extends DataProcessor {
    ADataProcessor(AData data) {
        super(data);
    }
    void doSomethingUsingADataAndOtherData(){}
}

class AADataProcessor extends ADataProcessor {
    AADataProcessor(AAData data) {
        super(data);
    }
    void doSomethingUsingAADataAndOtherData(){}
}

class BDataProcessor extends DataProcessor {
    BDataProcessor(BData data) {
        super(data);
    }
    void doSomethingUsingBDataAndOtherData(){}
}

DataProcessor hierarchies way3, only bottom sub class instance keep a priavte reference to Data, super class use a abstract method getData() to retrieve the Data

abstract class DataProcessor {
    protected Object otherData;
    protected abstract Data getData();
    void doSomethingUsingDataAndOtherData(){}
}

abstract class ADataProcessor extends DataProcessor {
    protected abstract AData getData();
    void doSomethingUsingADataAndOtherData(){}
}

class AADataProcessor extends ADataProcessor {
    private AAData data;
    protected AAData getData() {
        return data;
    }
    AADataProcessor(AAData data) {
        this.data = data;
    }
    void doSomethingUsingAADataAndOtherData(){}
}

class BDataProcessor extends DataProcessor {
    private BData data;
    protected BData getData() {
        return data;
    }
    BDataProcessor(BData data) {
        this.data = data;
    }
    void doSomethingUsingBDataAndOtherData(){}
}

Well, given the examples, i'd avoid inheritance and implement an interface for the DataProcessor.

package net.icodeapps.examples.ooad;

public interface DataProcessor<T, OtherData> {

    T processData();
}

This could be implement by any class like

package net.icodeapps.examples.ooad;

public class ADataProcessor implements DataProcessor<AData, OtherData> {

    private AData aData;

    private OtherData otherData;

    public ADataProcessor(AData aData, OtherData otherData) {
        this.aData = aData;
        this.otherData = otherData;
    }

    @Override
    public AData processData() {
        return aData;
    }
}

Having a second class implementing the interface

package net.icodeapps.examples.ooad;

public class BDataProcessor implements DataProcessor<BData> {

    private BData aData;

    private OtherData otherData;

    public BDataProcessor(BData aData, OtherData otherData) {
        this.aData = aData;
        this.otherData = otherData;
    }

    @Override
    public BData processData() {
        return aData;
    }
}

With more information, still would skip the abstract class. The reason you use it is providing a contract and avoid code replication. But since the code you try to avoid replicating is the problem itself, i'd skip that and just provide private fields to store references. That way you have the right type in processData.

Keeping the processors stateless and just store the data in a queue could be a better approach though. Depending on the data, you would create a processor on demand. The could be implemented via the command processor pattern. Using that pattern, more complexity would be introduced though.


Workaround for directory-browsing I'm in the process of cross-training myself from CFML to PHP as part of a learning exercise. I'm learning from the docs and online tutorials and googling.

As an initial exercise, I've knocked together the following PHP facsimile of some CFML code I have. I have a blog article explaining the requirement for the code. This is basically a work-around for the fact that the inbuilt PHP web server does not do directory browsing.

I'm just posting the PHP here in case anyone can make observations about how I might improve it. I'm more after PHP-specific info than coding structure "advice", but any observations one might make will be taken on board.

<?php
    // directory to create listing for, defaulting to the current one
    if (array_key_exists("dir", $_GET)){
        $dirCurrent = $_GET["dir"];
    }else{
        $dirCurrent = getcwd();
    }

    // sort out some baseline dirs / URLs
    $dirCurrent = realpath($dirCurrent);
    $dirBase    = realpath($_SERVER["DOCUMENT_ROOT"]);
    $urlBase    = "http://" . $_SERVER["HTTP_HOST"];

    if (strpos($dirCurrent, $dirBase) !== false && file_exists($dirCurrent)){
        // Used for building links to files
        $relativePath = str_replace($dirBase, "", $dirCurrent);
        $urlPath = str_replace("\\", "/", $relativePath);

        // provide a link to go up a level
        $parentDir = preg_replace("#[\\\/][^\\\/]+$#", "", $dirCurrent);
        $parentLinkUrl = $_SERVER["SCRIPT_NAME"] . "?dir=" . $parentDir;
        echo "[Parent Directory]
";

        echo "
";
        opendir($dirCurrent);
        while ($entry = readdir()) {
            if (in_array($entry, [".", ".."])){    // skip these two
                continue;
            }
            $linkText = $entry;
            $wholePathToFile = $dirCurrent . DIRECTORY_SEPARATOR . $entry;
            if (is_dir($wholePathToFile)){
                // we just want to link back to this file, passing the dir
                $linkUrl = $_SERVER["SCRIPT_NAME"] . "?dir=" . $wholePathToFile;
                $linkText .= "/"; // just to make it more clear it's a dir
            }else{
                // we want a link to the actual file
                $linkUrl = $urlPath . "/" . $entry;
            }
            echo "
$linkText
";
        }
        closedir();
        echo "
";
    }else{
        header("HTTP/1.0 404 Not Found");
    }
?>

Took this from your blog post:

  What I need to do is this:

  take a directory on the URL, which by default will be the current directory;
  list the files / directories;
  for each entry, convert the filesystem path to a URL, using the current HTTP host and port;
  also provide a "parent directory" link too, for browsing upstream.

Knowing these requirements, your code is way too complicated. That's quite normal for a beginner with PHP, so it's no problem. PHP offers built-in solutions that from time to time make experienced PHP programmers think: "Why didn't I find that before?" -- So what you missed, is glob(), and maybe some other neat functions.

// Directory to create listing for, defaulting to the current one
$dirCurrent = '';
if (!empty($_GET['dir'])) {
    // Remove leading and trailing slashes
    $dirCurrent = trim($_GET['dir'], '/.');
}
if (!empty($dirCurrent)) {
    $dirCurrent .= '/';
}
$dirBase = realpath($_SERVER["DOCUMENT_ROOT"]);

// Since we make $dirCurrent relative, a basedir check is not needed
if (is_dir($dirBase . '/' . $dirCurrent)) {
    // Provide a link to go up a level
    if (!empty($dirCurrent)) {
        $parentDir = dirname($dirCurrent);
        $parentLinkUrl = $_SERVER["SCRIPT_NAME"] . "?dir=" . $parentDir;
        echo "[Parent Directory]
";
    }
    echo "
";
    foreach (glob("$dirBase/$dirCurrent*") as $entry) {
        // Hidden files (those starting with a dot) are not returned by glob
        $linkText = basename($entry);
        if (is_dir($entry)) {
            // We just want to link back to this file, passing the dir
            $linkUrl = $_SERVER["SCRIPT_NAME"] . "?dir=" . urlencode($dirCurrent . basename($entry));
            $linkText .= "/"; // Just to make it more clear it's a dir
        } else {
            // we want a link to the actual file
            $linkUrl = $dirCurrent . basename($entry);
        }
        echo "
$linkText
";
    }
    echo "
";
} else {
    header("HTTP/1.0 404 Not Found");
}


Adding, deleting elements as per autocomplete results I am working on a bookmarker project for replacing storage of bookmarks in a web browser. It will be storing bookmarks as per categories in a database. I have written some jQuery for the WIP search page.

A bit about functionality

There is a search box for categories with autocomplete which is done by my app
On clicking Enter category is added to the web page via this jQuery. There are checks whether the category is in the autocomplete and whether it is already present on page or not.

The JS file can be viewed on GitHub if anyone prefers that. Please review as I don't know about best practices of javascript and am using JQuery for the first time. This JS is associated with this HTML page. I am not placing the HTML page here as I am interested in Javascript review only. I am using Python 3.4.0 with Django 1.6.4.

Please tell if any other information required for review.

/**
 * Created by Aseem on 5/22/14.
 */

var cur_location = location.protocol + '//' + location.hostname + (location.port ? ':' + location.port : '');
var static_url = '/static/BookMarker';
var static_img_url = cur_location + static_url + '/img';

var category_input = $("#category_inp");

$(function () {
    category_input.autocomplete({
        source: "auto/"
    });
});

//Add Bindings for keys
category_input.keyup(function (e) {
    if (e.keyCode == 13) {
        $(this).trigger("enterKey");
    }
});

category_input.bind("enterKey", function (e) {

    var is_category = false;

    $(".ui-menu-item").each(function (index) {
            if (category_input.val() == $.trim($(this).text())) {
                is_category = true;
                return false;
            }
        }
    )

    if (is_category == false) {
        alert("Not a category");
        return false;
    }

    var already_present = false;

    $(".category").each(function (index) {
            if (category_input.val() == $.trim($(this).text())) {
                alert("Category already added");
                already_present = true;
                return false;
            }
        }
    )

    if (already_present == false) {
        $("#category_list").append(
            '
' +
                ' ' +
                category_input.val() +
                '
'
        );
    }
    category_input.val("");
});

$(document).on('click', ".delete-cat", function (e) {
    var classList = $(this).attr('class').split(/\s+/);
    $.each(classList, function (index, item) {
        if (item != 'delete-cat') {
            $('.category.' + item).remove();
        }
    });
})

I know that this comes a few years late and the code doesn't appear to exist on the github repository anymore. Perhaps you have learned much more about jQuery and the autocompletes since posting this but none-the-less here is a review of it.

It is great that the DOM reference for the category input (i.e. $("#category_inp")) is stored in a variable but others could be also - like the container for the list of selected categories (i.e. $("#category_list")).

Instead of binding the enterKey event to a callback, why not use the select event callback option? That way if the user selects an option with the mouse the callback will also be called.

And for the delete image click handler, it could be simplified using .parent():

$(document).on('click', ".delete-cat", function (e) {
    $(this).parent().remove();
});


I need to know that if everything okay in my BTS put and get method I implement  BinaryTree  (K extends Comparable, V) concept to binarySearchTree and I have written get and put method. As far as I check, there is no problem in my code. So now I wonder that are there any problem or weak point in my code? and m,

   public void put(K key, V value) {
        Node newNode = new Node(key, value, null, null);
        Node current = root;
        if (root == null) {
            root = newNode;
            return;
        }
        while (true) {
            int cmd = key.compareTo(current.key);
            if (cmd > 0) {
                if (current.right == null) {
                    current.right = newNode;
                    break;
                } else {
                    current = current.right;
                }
            } else if (cmd < 0) {
                if (current.left == null) {
                    current.left = newNode;
                    break;
                } else {
                    current = current.left;
                }

            } else  {
                current.value = newNode.value;
                break;
            }
        }

  public V get(K key)  {
        Node curr = root;
        if (curr == null) {
            throw new NoSuchElementException("There is no such a element");
        }
        while (true) {
            int cmd = key.compareTo(curr.key);
            if (cmd > 0) {
                curr = curr.right;
            } else if (cmd < 0) {
                curr = curr.left;
            } else {
                return curr.value;
            }
        }
    }

And i check these and it worked

   BinaryTree<Integer,String> binaryTree = new BinaryTree<Integer, String>();

        binaryTree.put(8,"8");
        binaryTree.put(4,"4");
        binaryTree.put(5,"5");
        binaryTree.put(1,"1");
        binaryTree.put(2,"2");
        binaryTree.put(3,"3");
        binaryTree.put(65,"65");
        binaryTree.put(4,"4 (2)");

        System.out.println(binaryTree.get(8));
        System.out.println(binaryTree.get(4));
        System.out.println(binaryTree.get(65));
        System.out.println(binaryTree.get(5));

Since the code is not compiling, it will be hard to do a proper code review.

In my opinion, you should rename the variable cmd in both of the methods, since it can be confusing.

BinaryTree#put method

In my opinion, it's a bad choice to use the range operators (<, >, <=, >=) with the compareTo method; since you always get one of those values (-1, 0 & 1).
I suggest that you check if the values are equals before checking if they are inferior / superior; this will alow you to merge some of the logic of the inferior / superior since they are pretty similar.

if (cmd == 0) {
   current.value = newNode.value;
   break;
}

if (cmd == 1) {
   //[...]
}
```


Saving model's data in the model vs an external data manager class I have a bunch of models (using activejdbc) Person, Company, Health, .... etc (I have 8 models). I'm showing an example of just one model Person

In the first approach I have a data manager that handles all my insertions to my various models, for example for Person I have

public class Person extends Model {
    static {
        validatePresenceOf(“name”, “birthdate”);
    }
}

and in the Data Manager I do the insertion

public class DataManager {
    private DBManager dbManager;
    public void insertData(Data data) throws Exception {
        try {
            dbManager.openActiveJDBCBaseConnection();
            insertPerson(data)
        } catch (Exception e) {
            // stuff
        } finally {
            dbManager.closeActiveJDBCBaseConnection();
        }
    }
   public void insertPerson(Data data) {
       Person person = new Person();
       person.set(“name”, data.name);
       person.set(“birthdata”, data.birthdata);
       person.set(“country”, data.country();
       person.saveit();
}

Versus doing the actual insertion from the person model itself using a static method and then calling it from the data manager

public class Person extends Model {
    static {
        validatePresenceOf(“name”, “birthdate”);
    }
    public static void insertPerson(PersonData data) {
        Person person = new Person();
        person.set(“name”, data.name);
        person.set(“birthdata”, data.birthdata);
        person.set(“country”, data.country();
        person.saveit();
    }

}

public class DataManager {
    private DBManager dbManager;
    public void insertPerson(PersonData data) throws Exception {
        try {
        dbManager.openActiveJDBCBaseConnection();
            Person.insertPerson(data);
        } catch (Exception e) {
            // stuff
        } finally {
            dbManager.closeActiveJDBCBaseConnection();
        }
    }
}

Which is better?

In my opinion the first example you've given is the best. It seems to adhere more to the single responsibility principle. What this basically means is that your classes should only one responsibility.

Note: You're actually still breaking the principle, because I think activeJDBC requires objects to save themselves? (I'm not experienced with activeJDBC, but after looking around a little it seems that this is the way it's done). For example Person.saveit() isn't really a great solution in my opinion, but we'll ignore that.

The reason why I would prefer the first example is because it makes a lot more sense to use something called a DataManager for insertions, than a Person class.

If you look the the second example Person.insertPerson() just really doesn't make much sense. Does a Person really insert a person? In my opinion you should stick as close to reality as possible (of course there are exceptions), and letting a person insert a person doesn't really reflect reality. Person.sit() or Person.eat() is something I would expect to find in a Person class.

A DataManager (what's in a name) indicates that it manages data. And at first thought I could assume/think that this would be used for inserting/receiving/updating objects (if I hadn't inspected the code). Saying DataManager.insertPerson() seems like the more logical solution for me (even though it still has to actually use Person.saveit() for it to actually insert/save the object).

TL;DR I guess you're question could be put as "Should I save a model's data in the model or in an external data manager class?". My answer to this would be use the external data manager class (DataManager). Just because it makes more sense to have a data manager have an insertPerson() method, than an actual model have that method.


Returning all possible English dictionary words that can be formed out of a string I am using an external library named enchant here. My problem is that I guess my program is not returning all possible English words and is slow as well for large string input.

I am using both en_US and en_UK here:

import enchant
import itertools
uk = enchant.Dict("en_UK")
us=enchant.Dict("en_US")
a=[] # stores all possible string combinations
ent=input('enter the word: ')
ent=ent.rstrip('\r\n')
i=3 # minimum length of words
while i<=len(ent):
  it=itertools.permutations(ent,i)
  for y in it:
    a.append("".join(y))
  i+=1
a.sort(key=len,reverse=True)
possible_words=[]
for x in a:
  if uk.check(x) and x not in possible_words :
    possible_words.append(x)

for x in a :
  if us.check(x) and x not in possible_words:
    possible_words.append(x)

possible_words.sort(key=len,reverse=True)
for x in possible_words:
  print(x)

Example :

enter the word: wsadfgh
wash
wads
wags
swag
shag
dash
fads
fags
gash
gads
haws
hags
shaw
shad
was
wad
wag
saw
sad
sag
ash
ads
fwd
fas
fad
fag
gas
gad
haw
has
had
hag

As a general advice, you may want to organize your code into functions - say

One function to receive user input and process it
One function to generate all possible permutations for a string passed in less than a value (here 3).
Another function to filter this based on whether the string passed in is in us or uk dictionaries
At the end, you can combine these as a list comprehension.

Regarding your problem of performance, time the program with the itertools permutation output alone (without dict checking). My guess would be that the permutations is taking the time, but it would be nice to verify.

You may also want to check where the valid words are getting filtered. (Since you say that not all the words are being output). My guess is that permutation produces them but is not present in the enchant dictionary. But please verify.
Here is a possible rewriting of your code. It removes the redundant sorts

import enchant
import itertools

MIN_LEN = 3
uk = enchant.Dict("en_UK")
us = enchant.Dict("en_US")

def get_input():
  return sorted(set(input('enter the word: ').rstrip('\r\n')))

def gen_permutations(ent):
  tuples = map(lambda i: itertools.permutations(ent,i), range(MIN_LEN,len(ent)+1))
  arrr= [["".join(j) for j in i] for i in tuples]
  return list(itertools.chain(*arrr))

def filter_dict(words):
  return [x for x in words if uk.check(x) or us.check(x)]

for i in filter_dict(gen_permutations(get_input())):
  print i


Nearest Neighbour classification algorithm The following code is from a university assignment of mine to write a classification algorithm (using nearest neighbour) to classify whether or not a given feature set (each feature is the frequency of words in an email) is spam or not.

We are given a CSV file (the training data) with the frequencies, and an integer (1 or 0) at the end of the row indicating whether or not it is spam.
So in this form:

X1,X2,...,Xn,SPAM

The test data is also in this form (including the SPAM column, so we can verify the accuracy).

My question is, how can I make this code more idiomatic, and what speedups can I make to this code? For example, is there a way to write getMostCommon, without having to groupBy and then run a maximumBy again?

import Text.CSV
import Data.List

data SpamType = Spam | NotSpam
    deriving (Show, Eq)

type FeatureSet = [Float]

toSpam :: Int -> SpamType
toSpam 0 = NotSpam
toSpam 1 = Spam
toSpam a = NotSpam

parseClassifiedRecord :: Record -> (FeatureSet, SpamType)
parseClassifiedRecord x = (init converted, toSpam (truncate (last converted)))
    where
        converted = map (\val -> read val :: Float) x

-- returns the euclidean distance between two feature sets
difference :: FeatureSet -> FeatureSet -> Float
difference first second = sqrt (sum (zipWith (\x y -> (x - y)^2) first second))

-- finds the SpamType of the k nearest 'nodes' in the training set
findKNearest :: [(FeatureSet, SpamType)] -> FeatureSet -> Int -> [SpamType]
findKNearest trainingSet toMatch k = take k (map snd (sortBy (\x y -> (compare (fst x)  (fst y))) [(difference (fst x) toMatch, snd x) | x <- trainingSet]))

-- returns item which occurs most often in the list
getMostCommon :: (Eq a) => [a] -> a
getMostCommon list = head (maximumBy (\x y -> (compare (length x) (length y))) (groupBy (\x y -> (x == y)) list))

-- given a feature set, returns an ordered (i.e. same order as input)
-- list of whether or not feature is spam or not spam
-- looks at the closest k neighbours
classify :: [(FeatureSet, SpamType)] -> FeatureSet -> Int -> SpamType
classify trainingSet toClassify k = getMostCommon (findKNearest trainingSet toClassify k)

-- gives a value for the accuracy of expected vs actual for spam classification
-- i.e. num classified correctly / num total
accuracy :: [(SpamType, SpamType)] -> Float
accuracy classifications = (fromIntegral $ length (filter (\x -> (fst x) == (snd x)) classifications)) / (fromIntegral $ length classifications)

main = do
    packed <- parseCSVFromFile "spam-train.csv"
    packedtest <- parseCSVFromFile "spam-test.csv"
    let (Right trainingSet) = packed
    let (Right testSet) = packedtest
    let classifiedTrainingSet = map parseClassifiedRecord (tail (init trainingSet))
    let unclassified = map parseClassifiedRecord (tail (init testSet))
    let classified = map (\x -> (classify classifiedTrainingSet (fst x) 1, snd x)) unclassified
    putStrLn (show (accuracy classified))

One helpful function is Data.Ord.comparing:

comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing p x y = compare (p x) (p y)

With this and using function composition you can write:

getMostCommon :: (Eq a) => [a] -> a
getMostCommon = head . maximumBy (comparing length) . groupBy (==)

Similar changes apply to several places.  Another small simplification could be changing (\x -> (fst x) == (snd x)) to uncurry (==).


Application please send me an E-mail This is an E-mailer class that I created to send me E-mail when/if the Windows service (that will be installed on computers all over) throws an error, so that I know what is going on.

I use a similar set up all over the place, so I would like to know if this is clean and efficient.

class Emailer
{
    public void sendEmail(string bodyText, string sender, List<string> recipientAddresses)
    {
        int portNumber = 25;
        SmtpClient smtpClient = new SmtpClient("mailexchanger_String", portNumber);
        using (MailMessage mailMsg = new MailMessage())
        {
            mailMsg.Body = bodyText;
            mailMsg.IsBodyHtml = true;
            mailMsg.Priority = MailPriority.High; //I want to know now!
            foreach (string address in recipientAddresses)
            {
                mailMsg.To.Add(address);
            }
            mailMsg.From = new MailAddress(sender);

            smtpClient.Send(mailMsg);
        }
    }
}

I would also like to know if I have the right ideas about how classes should work and function; this is just a simple method wrapped inside of a class. Is this how it should be?

Some thoughts about the code itself.

In general method names recommended as Pascal Case so sendEmail should ideally be named SendEmail
I might consider trying to make the class a bit more configurable so that it could be extended in more ways without being modified.  For example if you wanted to send a text email, or you wanted to send an email using a different server.

The modified code might look like:

public class Emailer
{
    // Required for emailer to work
    private readonly string _host;
    private readonly int _portNumber;

    // Optional configurable options
    public bool IsHtml { get; set; }
    public MailPriority Priorty { get; set; }

    public Emailer()
        : this("mailexchanger_String", 25)
    {

    }

    public Emailer(string host, int portNumber)
    {
        _host = host;
        _portNumber = portNumber;

        IsHtml = true;
        Priorty = MailPriority.High;
    }

    public void SendEmail(
        string bodyText,
        string sender,
        List<string> recipientAddresses)
    {
        SendEmail(
            bodyText,
            new MailAddress(sender),
            recipientAddresses.Select(p => new MailAddress(p)).ToList());
    }

    public void SendEmail(
        string bodyText,
        MailAddress sender,
        List<MailAddress> recipientAddresses)
    {
        // .NET 4.0 only for SmtpClient disposing
        using (var smtpClient = new SmtpClient(_host, _portNumber))
        {
            using (var mailMsg = new MailMessage())
            {
                mailMsg.From = sender;
                mailMsg.Body = bodyText;
                mailMsg.IsBodyHtml = IsHtml;
                mailMsg.Priority = Priorty;
                recipientAddresses.ForEach(p => mailMsg.To.Add(p));

                smtpClient.Send(mailMsg);
            }
        }
    }
}

You can also configure an SMTP client via the .config.  In that case
you do not need to provide the connection details in the code but instead can configure it via the .config file.

For an MVC.net application that may be in the web.config or for a desktop application that might be in an app.config.

<system.net>
<mailSettings>
  <smtp from="<fromaddress>">
    <network host="mailexchanger_String" password="??" userName="??" port="25" enableSsl="true" defaultCredentials="false" />
  </smtp>
</mailSettings>
</system.net>

This means that you could create the SMTP client on Emailer creation and then dispose it as necessary.  In this case the code might look like

internal class Emailer : IDisposable
{
    // Our smtp client that will be disposed
    private readonly SmtpClient _smtpClient;

    // Optional arguments
    private bool _isHtml = true;
    public bool IsHtml { get { return _isHtml;  } set { _isHtml = value; } }

    private MailPriority _mailPriority = MailPriority.High;
    public MailPriority Priorty { get { return _mailPriority;  } set { _mailPriority = value; } }

    public Emailer()
    {
        _smtpClient = new SmtpClient();
    }

    public Emailer(string host, int portNumber)
    {
        _smtpClient = new SmtpClient(host, portNumber);
    }

    public void SendEmail(
        string bodyText,
        string sender,
        List<string> recipientAddresses)
    {
        SendEmail(
            bodyText,
            new MailAddress(sender),
            recipientAddresses.Select(p => new MailAddress(p)).ToList());
    }

    public void SendEmail(
        string bodyText,
        MailAddress sender,
        List<MailAddress> recipientAddresses)
    {
        using (var mailMsg = new MailMessage())
        {
            mailMsg.From = sender;
            mailMsg.Body = bodyText;
            mailMsg.IsBodyHtml = IsHtml;
            mailMsg.Priority = Priorty;
            recipientAddresses.ForEach(p => mailMsg.To.Add(p));

            _smtpClient.Send(mailMsg);
        }
    }

    public void Dispose()
    {
        _smtpClient.Dispose(); // Or not if using < .NET 4.0
    }
}

And used like:

using(var emailer = new Emailer())
{
    emailer.SendEmail(
        bodyText,
        sender,
        "sendtome"
    );
}