Parsing double from string I'm trying to parse Double from String in Java. The string input is not necessarily a number, any non number input should be treated as 0.

Given below is a solution using try-catch, where a Array of string is converted into a Array of Double:

public static void main(String[] args) {
    // Array of strings to be parsed as double.
    // In case of NaN I have to assign it a value 0.
    ArrayList<String> dirtyList = new ArrayList();
    dirtyList.add("Null");
    dirtyList.add("1.24");
    dirtyList.add("0");
    dirtyList.add("0asd");
    ArrayList<Double> doubleList = new ArrayList();
    for ( String item : dirtyList) {
        doubleList.add(parseDouble(item));
    }
    System.out.println(doublelist);
}

// Function to clean data
static Double parseDouble(String x) {
    Double a;
    try {
        a = Double.parseDouble(x);
    } catch (Exception ParseException) {
        a = (double) 0;
    }
    return a;
}

Output:

[0.0, 1.24, 0.0, 0.0]

Is it okay to exploit try-catch in situations like this? Is there a better approach?

In Python, the best practice is to use exceptions for many more situations than is best practice in Java. In Python, you shoot first, ask questions later .... you seek forgiveness, not permission.... you ... {add cheesy analogy here....}

In Java, Exceptions are expensive. When an exception happens, the virtual machine needs to backtrack the call stack, often synchronizing on critical aspects of the runtime, perhaps bringing the entire application in to a locked state, while the exception is built. The Java compiled code is often inlined, and optimized, and the call stack for the actual optimized code has to be translated back to the source code, etc.

If you expect your input data to have invalid double input, then it is not an exceptional case to have invalid data, is it. In Java, you seek permission before having to seek forgiveness... so, you validate the data before doing the hard work.

The documentation for Double.valueOf(String) even goes so far as to show you exactly how to validate an input String before parsing it... using a regular expression, and shows how to use it too.

So, let's compare two ways of parsing the values.... the forgiveness way:

private static final double parseForgiveness(String value) {
    try {
        return Double.parseDouble(value);
    } catch (NumberFormatException nfe) {
        return 0.0;
    }
}

(Note, there's something important in there, I use double and not Double. Using primitives in Java when you can is almost always a better idea for performance than using the full Object version, like Double).

So, the above system begs forgiveness when the data is broken.... what about prevalidating the number...? The code is basically copied from the Javadoc:

private static final double parsePermission(String value) {
    if (DOUBLE_RE.matcher(value).matches()) {
        return Double.parseDouble(value);
    }
    return 0.0;
}

where the DOUBLE_RE is defined as:

private static final String Digits     = "(\\p{Digit}+)";
private static final String HexDigits  = "(\\p{XDigit}+)";
// an exponent is 'e' or 'E' followed by an optionally
// signed decimal integer.
private static final String Exp        = "[eE][+-]?"+Digits;
private static final String fpRegex    =
    ("[\\x00-\\x20]*"+  // Optional leading "whitespace"
     "[+-]?(" + // Optional sign character
     "NaN|" +           // "NaN" string
     "Infinity|" +      // "Infinity" string

     // A decimal floating-point string representing a finite positive
     // number without a leading sign has at most five basic pieces:
     // Digits . Digits ExponentPart FloatTypeSuffix
     //
     // Since this method allows integer-only strings as input
     // in addition to strings of floating-point literals, the
     // two sub-patterns below are simplifications of the grammar
     // productions from section 3.10.2 of
     // The Java Language Specification.

     // Digits ._opt Digits_opt ExponentPart_opt FloatTypeSuffix_opt
     "((("+Digits+"(\\.)?("+Digits+"?)("+Exp+")?)|"+

     // . Digits ExponentPart_opt FloatTypeSuffix_opt
     "(\\.("+Digits+")("+Exp+")?)|"+

     // Hexadecimal strings
     "((" +
      // 0[xX] HexDigits ._opt BinaryExponent FloatTypeSuffix_opt
      "(0[xX]" + HexDigits + "(\\.)?)|" +

      // 0[xX] HexDigits_opt . HexDigits BinaryExponent FloatTypeSuffix_opt
      "(0[xX]" + HexDigits + "?(\\.)" + HexDigits + ")" +

      ")[pP][+-]?" + Digits + "))" +
     "[fFdD]?))" +
     "[\\x00-\\x20]*");// Optional trailing "whitespace"

private static final Pattern DOUBLE_RE = Pattern.compile(fpRegex);

Note that a Pattern is compiled as a single static, and then used to match the String before actually parsing it. That seems like a lot of work, but consider a situation when about half the values are invalid in a String sequence.... how does it affect the performance?

I wrote a UBench tool a little while ago to test performance of these sorts of exercises. The first thing I do is write a function to generate an input array of 50% valid values, and 50% invalid. Here's that code:

private static final char[] alpha = " `1234567890-=~!@#$%^&*()_+qwertyuiop[]\\QWERTYUIOP{}|asdfghjkl;'ASDFGHJKL:\"zxcvbnm,./ZXCVBNM<>?".toCharArray();

private static final String wordRand(Random rand) {
    int len = rand.nextInt(10) + 3;
    char[] chars = new char[len];
    IntStream.range(0, len).forEach(i -> chars[i] = alpha[rand.nextInt(alpha.length)]);
    return new String(chars);
}

private static String[] buildInput(int size) {
    List<String> values = new ArrayList<>();
    Random rand = new Random(size);
    for (int i = 0; i < size; i++) {
        values.add(Double.toString(rand.nextDouble() * i));
        values.add(wordRand(rand));
    }
    return values.toArray(new String[values.size()]);
}

That buildInput method will return an array of Strings where half the values are guaranteed valid float Strings, and the other half are almost certainly not valid (thought it's possible they may be). Then, I run it through a comparative benchmark using the following code:

private static final double[] parseAll(String[] values, ToDoubleFunction<String> parser) {
    return Stream.of(values).mapToDouble(parser).toArray();
}

public static void main(String[] args) {
    UUtils.setStandaloneLogging(Level.INFO);
    String[] values = buildInput(1000);
    UBench bench = new UBench("Parsing");
    bench.addTask("Permission", () -> parseAll(values, DoubleParser::parsePermission));
    bench.addTask("Forgiveness", () -> parseAll(values, DoubleParser::parseForgiveness));
    bench.press(1000).report();
}

That's complicated, I guess, but really it sets up two tests, one which parses 2000 input values using the forgiveness method, the other test uses the permission method. It runs each test 1000 times, and then takes some measurements of each run, and reports on it. The report, on my computer, looks like:

INFO   2015-08-07 12:13:03.058 net.tuis.ubench.UBench(<init>): Creating UBench for suite Parsing
INFO   2015-08-07 12:13:06.860 net.tuis.ubench.UBench(press): UBench suite Parsing: completed benchmarking all tasks using mode INTERLEAVED in 3785.000ms
Task Parsing -> Permission: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   1.1980
  Fastest  :   1.0339      Slowest  :  26.8094
  95Pctile :   1.3693      99Pctile :   2.9096
  TimeBlock : 1.702 1.265 1.143 1.176 1.073 1.086 1.168 1.194 1.076 1.096
  Histogram :   977    17     5     0     1

Task Parsing -> Forgiveness: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   2.5568
  Fastest  :   2.3117      Slowest  :  12.5496
  95Pctile :   2.8740      99Pctile :   5.5604
  TimeBlock : 3.054 2.539 2.522 2.645 2.411 2.471 2.470 2.591 2.419 2.446
  Histogram :   978    20     2

What that means, is that the average time to parse 2000 values using the regex is 1.20 milliseconds, and using the exception system is 2.56 milliseconds - more than twice as slow.

Additionally the fastest parse is 1.03 milliseconds, vs. 2.31 - again more than twice as slow.

Bottom line is that in Java (unlike Python), you should not use exceptions to handle data validation when you expect data to regularly be invalid....


Simple Linux upgrade script in Bash As I will be deploying this script on multiple machines with the very same system Linux Mint 18 with rather same configuration, I would like to be semi-sure I won't screw things up much. This little script will run every day from crontab and will be logged into syslog.

Conditions were:

Code Readability
Output Readability
Colored Headings
Attempt to correct things
Clean-up after update

My current idea is simple:

#!/bin/bash

RED="\033[1;31m"
GREEN="\033[1;32m"
NOCOLOR="\033[0m"

echo

echo -e "step 1: ${GREEN}pre-configuring packages${NOCOLOR}"
sudo dpkg --configure -a

echo

echo -e "step 2: ${GREEN}fix and attempt to correct a system with broken dependencies${NOCOLOR}"
sudo apt-get install -f

echo

echo -e "step 3: ${GREEN}update apt cache${NOCOLOR}"
sudo apt-get update

echo

echo -e "step 4: ${GREEN}upgrade packages${NOCOLOR}"
sudo apt-get upgrade

echo

echo -e "step 5: ${GREEN}distribution upgrade${NOCOLOR}"
sudo apt-get dist-upgrade

echo

echo -e "step 6: ${GREEN}remove unused packages${NOCOLOR}"
sudo apt-get --purge autoremove

echo

echo -e "step 7: ${GREEN}clean up${NOCOLOR}"
sudo apt-get autoclean

echo

Current visual output:

The output of your script is lovely, but it strikes me as a work in progress.  There's nothing wrong with what is there, but it seems a few major pieces are missing.

error checking

What happens if one of the steps fails?  As it stands the script will diligently proceed to the next step.  If you actually checked the return codes from your apt commands you would also get a chance to use the RED color that seemed wasted in the comments above.

logging

You mention logging, but there is no such thing in the script.  Adding this would not be hard.  If you want your messages to go to the screen and a log you could add functions that log and write to the screen.  logger is handy way to add to the system logs, but you could write to your own $LOGFILE too with something like

echo "step $STEP: $MSG" >> $LOGFILE

docs

Shouldn't there be docs somewhere?  A link to a wiki page or something in the script would help folks figure out what is up.  Providing help from within the script if a -h is provided is a good habit to get into.

rewrite based on above

#!/bin/bash

RED="\033[1;31m"
GREEN="\033[1;32m"
NOCOLOR="\033[0m"

mylog() {
        STEP=$1
        MSG=$2

        echo -e "step $STEP: ${GREEN}${MSG}${NOCOLOR}"
        logger "step $STEP: $MSG"
}

myfail() {
        STEP=$1
        MSG=$2

        echo -e "step $STEP ERROR: ${RED}${MSG}${NOCOLOR}"
        logger "step $STEP ERROR: $MSG"
}

# handle command line options
if [[ $1 == "-h" ]]; then
        echo "usage: $0"
        echo " -h prints help"

        exit 1
fi

# step 1
mylog 1 "the start"
echo foo

# step 2
mylog 2 "a middle"
echo bar

# step 3
mylog 3 "the end"
echo baz
if [[ $? == 0 ]]; then
        myfail 3 "nothing really"
fi

finally

It is a good habit to run your scripts through shellcheck.net.  Even my short rewritten example has one thing that could be improved.


Emulator for representing hardware and operating systems This is an emulator I am currently re-writing for my Operating Systems course. It is a simple emulator that is supposed to represent hardware, OS, etc. It is strictly for learning purposes and I want to propose my solution to the teacher as a method of modern C++ (since his solution is more "C with classes").

However, before I do that, I would like to make sure I don't embarrass myself with bad code.

Right now I'm debating on my association between hardware and OS. They are currently written like so:

// Hardware.h
class OS;
class Hardware : boost::noncopyable
{
    friend class OS;

private:
    Hardware(OS *os);

    void load_job(boost::shared_ptr<Job> job);
    void run_job();

private:
    void execute_instruction(Instruction const& instruction);
    void handle_interrupt(Instruction const& trap);

private:
    enum { NumberOfRegisters     = 32 };
    enum { InstructionMemorySize = 1024 };
    enum { DataMemorySize        = 1024 };

    OS                            *m_pOS;

    std::vector<int>               m_Registers;
    boost::ptr_vector<Instruction> m_InstructionMemory;
    std::vector<int>               m_DataMemory;

    boost::optional<int>           m_Counter;
};

// OS.h
class Hardware;
class OS : boost::noncopyable
{
    friend class Hardware;

public:
    OS();

    // Load jobs
    void boot();
    // Execute jobs
    void run();

private:
    // "Interrupts"
    void trap_halt(int status);
    void trap_getw(int& receiver);
    void trap_putw(int value);
    void trap_dump();

    void time_elapsed();

private:
    void get_next_job();

private:
    boost::scoped_ptr<Hardware> m_pHardware;
    boost::scoped_ptr<Parser>   m_pParser;

    boost::ptr_deque<Job>       m_Jobs;
    boost::ptr_deque<Job>       m_JobsInProgress;
};

The question is:  I don't want the Hardware to be accessible by any other class other than OS. Declaring Hardware private and friending OS is a step in the right direction, but it bothers me that OS now has access to all functions. Is there a way I can restrict OS?

Also, I did some researching on callbacks, but the C++ FAQ suggests that you shouldn't make callbacks to member functions of a class. Are there other solutions such that my Hardware class does not need a pointer to OS in order to call its functions?

Secondly, I'm wondering, at what point does the pImpl idiom become a viable solution? I mean, how large does a class have to be, or how many includes must it have, to seriously consider moving the class into a struct?

That's not what friends are for. Friends are for tightly integrated classes which need to be able to play with each other's private data. OS and Hardware are not tightly related; they interact through a specifically designed interface.

If you don't want other classes besides OS to call the hardware functions, don't write code in those other classes which call the hardware functions. Better yet, simply only give the Hardware pointer to the OS class so only it can call the hardware functions.

For callbacks have a look at the boost::function library. It will allow you to create callbacks to the OS methods. You can create pointers to methods but you need both the method pointer and the object point for it to work. Boost::function hides all of this behind the scenes.

pImpl is workaround because C++ is such a silly language. Its purpose is to make it so that you do not have to recompile the header file whenever the private members of the class change. More modern languages essentially do this automatically for all classes. pImpl makes sense only when your compile times get too large. A class project probably doesn't get large enough for that to be a big concern.


Extracts marks of all students in class from website This code extracts marks of all students in class and stores the result in a file results.txt, using BeautifulSoup. I'm looking for code review and suggestions.

from bs4 import BeautifulSoup
import requests

file = open("results.txt","w")

for roll in range(1,60):
    if roll in range(1,10):
            rollstr = '0'+str(roll)
    else:
            rollstr = str(roll)
    url = 'http://www.*.org/'
    r = requests.get(url)

    data = r.text
    soup = BeautifulSoup(data)

    file.write('roll: ' +rollstr + ' ')

    for i in soup.find_all('strong'):
            sgpa = i.get_text()
            if sgpa.find('SGPA') == 0:
                    file.write(sgpa)
                    break
    file.write('\n')

Style

Your code looks good but you might like to know that there is a Style Guide for Python Code called PEP 8. If you are interested, you'll find tools to check your code automatically (pep8) and to fix it (autopep8).

In your case, I can see straight-away that you are sometimes missing spaces around your '+' operator.

String format

You'll find various more pythonic ways to format your number with leadings 0s.

Also, in case you want to keep your current logic, comparison can be written pretty succintly in Python so that you can simply write : if 1 <= roll < 10. (Please note that in Python 2.x, range returns a list so checking if x in range(whatever) is not efficient in time (it has to check all elements if the elements you are looking for is not in the list) nor in memory (a list is built for no reason)).

Using context managers

Opening files and remembering to close them is a bit tedious. Good thing is that Python has a clean solution to this : the with keyword. In a nutshell, you use with when you open your file, you add a level of indentation and the magic to close your file will happen automaticaly.


A scala implementation of the Java trim method I'm a Scala beginner and looking at the trim() method of the Java API.  I noticed side effects, so I attempted to implement a functional version in Scala.

Here is the Java version:

public String trim() {
int len = count;
int st = 0;
int off = offset;      /* avoid getfield opcode */
char[] val = value;    /* avoid getfield opcode */

while ((st < len) && (val[off + st] <= ' ')) {
    st++;
}
while ((st < len) && (val[off + len - 1] <= ' ')) {
    len--;
}
return ((st > 0) || (len < count)) ? substring(st, len) : this;
}

My Scala version iterates over a string, and when it encounters a space char, the tail of the string is returned. The entire string is then reversed, so it can access the trailing whitespace. This new string is iterated over until a space char is encountered and the tail of this string is returned. This new string is then reversed again to maintain the original string order:

def trim(stringToTrim : String) : String = {
    def removePreString[String](list : List[String]) : java.lang.String = list match {

        case head :: tail => {
            if(head.toString.equals(" ")){
                removePreString(tail)
            }
            else {
                head.toString + tail.mkString
            }
        }
    }//end removePreString

    val preString =    removePreString(stringToTrim.toList)
    val reveresedString = preString.toList.reverse
    val reveresedPostString = removePreString(reveresedString)
  reveresedPostString.reverse

}//end trim

How can this code be improved?  Does it seem wasteful reversing the string twice?

No good idea about the concern of reversing the list twice. But you may

Let you inner function return a List instead of a string thus having less conversions from list to string and string to list.
Change your match to the following pattern (not tested):

case " " :: tail => removePreString(tail)
case _ => _

I just realize you could also use on a list def dropWhile(p: (A) ⇒ Boolean): List[A] which drops longest prefix of elements that satisfy a predicate. You could then chain dropWhile not a space | reverse | dropwhile not a space | reverse...


ASP.NET Core async iactionresult I am new to async methods and am kinda confused how async is working so what i want for you to do is review this code and tell me does implementing async like this is meaningless
[Route("/Dev/ForceBufferUpdate")]
public async Task<IActionResult> BufferUpdate()
{
    bool isAdministrator = await Task.Run(() => {
        return Security.IsAdministrator(Request);
    });

    if(!isAdministrator)
            return View("Error", "You don't have permission!");

    await Task.Run(() => {
        LimitlessSoft.Buffer.Refresh();
    });

    return Redirect("/Dev");
}

This code is pointless since it creates async state machine while the code you execute is actually synchronous code.
So eventually you get a performance penalty for the creation of a state machine but no reward of asynchronous execution.
Consider using async and await when you're dealing with IO operations. Usually, such methods already provide asynchronous API. You can spot this as such methods return Task or Task<T>


Longest palindrome in a string Please be brutal, and judge my code as if it was written at a top 3 tech company, straight out of college. (The method signature, and input parameter is given by the problem, so don't worry about that)

Worst case complexity: \$ O \left( n^2 \right) \$

Space complexity: \$ O \left( n \right) \$

Time it took me to solve this:
6 minutes (I got it right the first shot, and passed all the test cases)

Problem:

  Given a string S, find the longest palindromic substring in S. You may
  assume that the maximum length of S is 1000, and there exists one
  unique longest palindromic substring.

  public String longestPalindrome(String s) {
        String longestPalindrome = "";
        for(int i = 0; i < s.length(); i++){
            for(int j = s.length()-1; j >= 0 && j != i; j--){
                if(isPalindrome(s.substring(i,j+1))){
                    if(s.substring(i, j+1).length()>longestPalindrome.length()){
                        longestPalindrome = s.substring(i, j+1);
                        return longestPalindrome;
                    }
                }
            }
        }
        return longestPalindrome;
    }
    public boolean isPalindrome(String s){
        int end = s.length()-1;
        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i)!=s.charAt(end)){
                return false;
            }
            end--;
        }
        return true;
    }

Complexity

Your answer is \$O(n^3)\$ and not \$O(n^2)\$. You have three levels of nested loops... two inside the longestPalindrome() method and another inside the isPalindrome().

Can this problem be solved with less complexity? I believe it is possible to do an \$O(n^2)\$ solution ... I'll have to think it through though.

Test-Cases

Your code may have passed the test cases, but I don't believe your code works every time... consider this:

                if(s.substring(i, j+1).length()>longestPalindrome.length()){
                    longestPalindrome = s.substring(i, j+1);
                    return longestPalindrome;
                }

You return the first palindrome you find.... longestPalindrome starts off as the empty String (length 0), and you return the first value that is longer. Your code could simply be equally broken as:

   if(s.substring(i, j+1).length() > 0){
       return s.substring(i, j+1);
   }

I don't know what the test cases are, but they need work.

Nit-picks

giving a variable the same name as a method is 'wrong'... : longestPalindrome
you calculate s.substring(i, j+1) three times in the following block:

       if(isPalindrome(s.substring(i,j+1))){
           if(s.substring(i, j+1).length() > longestPalindrome.length()){
               longestPalindrome = s.substring(i, j+1);
               return longestPalindrome;
           }
       }

Performance

Your loops could be trimmed down (a lot). These optimizations do not affect the complexity, but they do reduce the computational overhead:

for(int j = s.length()-1; j >= 0 && j != i; j--){

has redundant j-conditions. The j >= 0 can be dropped since the j != 1 will be encountered first.

Also, j is only ever used in a +1 context. You may as well change the loop conditions to be:

       for(int j = s.length(); j > i; j--){

and then replace all the j + 1 references inside the loop with plain j.

Conclusion

I am not satisfied that this solution reliably finds the longest palindrome....


Class with a sometimes unused property From times to times I stumble over the following situation:

I have got a class with a property that's only used if another property has a particular value, for instance:

public enum enum_ConnectionType
{
    Local,
    Server
}

public class Session
{
    private enum_ConnectionType _connectionType;
    private string _serverName; // It only makes sense if _connectionType == enum_ConnectionType.Server

    public Session(enum_ConnectionType connectionType, string serverName)
    {
        _connectionType = connectionType;
        _serverName = serverName;
    }
}

There's something that does not feel right to me.
What is your common approach on this kind of situations?

EDIT

I think both Jeff and Leonid answers are valid depending on the situation.

I would do this using an interface and polymorphism to represent this:

public interface ISession
{
    void DoSomething();

    // Add your properties / method definitions
}

public class ServerSession : ISession
{
     private readonly string _serverName;

     public ServerSession(string serverName)
     {
         _serverName = serverName;
     }

     public void DoSomething()
     {
         // Some Code
     }

     // Implement interface contracts
}

public class OtherSession : ISession
{

     public void DoSomething()
     {
         // Some Code
     }

     // Implement interface contracts
}

Then you would use it something like this:

public DoSomethingWithSession(ISession session)
{
     session.DoSomething();
}

foo.DoSomethingWithSession(new ServerSession());

If there is commonality between ISession implementations, you could base class that out, then inherit from that.


DRY up ivar assignment in Rails new and create controller actions When creating a new model in Rails, I need to pass a bunch of other models into the view so I can define the correct associations. All I’m really doing here is querying the persistence layer for models and assigning them to instance variables, but I’m having to do it twice. What’s the best way of extracting the assignment? Just creating a controller method and calling it? I’m not sure.

class ProjectsController < ApplicationController
  def new
    @project = Project.new
    @companies = Company.as_select_options
    @project_varieties = ProjectVariety.as_select_options
    @prices = Price.as_select_options
    @users = User.as_select_options
  end

  def create
    @project = Project.new(project_params)
    @companies = Company.as_select_options
    @project_varieties = ProjectVariety.as_select_options
    @prices = Price.as_select_options
    @users = User.as_select_options
    if @project.save
      flash[:success] = "#{@project.name} has been created."
      redirect_to @project
    else
      render :new
    end
  end
end

Simplest thing would be to add a protected method to the controller and a matching before_filter/before_action callback:

Your actions become:

class ProjectsController < ApplicationController
  before_filter :load_select_options, only: [:new, :create]

  def new
    @project = Project.new
  end

  def create
    @project = Project.new(project_params)
    if @project.save
      flash[:success] = "#{@project.name} has been created."
      redirect_to @project
    else
      render :new
    end
  end

  protected

  def load_select_options
    @companies = Company.as_select_options
    @project_varieties = ProjectVariety.as_select_options
    @prices = Price.as_select_options
    @users = User.as_select_options
  end
end

If you have an edit action, add that to the before-filter's list too.

However, since you (presumably) only need to load all that stuff in create if you have to render the new template, you can skip the before filter, and instead do something more targeted:

class ProjectsController < ApplicationController
  def new
    @project = Project.new
    load_select_options
  end

  def create
    @project = Project.new(project_params)
    if @project.save
      flash[:success] = "#{@project.name} has been created."
      redirect_to @project
    else
      load_select_options
      render :new
    end
  end

  protected

  def load_select_options
    @companies = Company.as_select_options
    @project_varieties = ProjectVariety.as_select_options
    @prices = Price.as_select_options
    @users = User.as_select_options
  end
end


Basic Implementation of Hash Table in Python Basic impl of hash_table in python.  Supports set, get, and delete.  Uses open addressing with linear probing function.  Any ideas would be greatly appreciated! Thanks!

class Entry:
    """
        holds key, value pairs
    """
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.is_deleted = False

class Map(object):
    """
        a basic, minimal implementation of a hash map
    """
    def __init__(self):
        """
            constructs a new Map
        """
        self.table = [None] * 10
        self.load_factor = .75
        self.current_size = 0

    def __setitem__(self, key, item):
        """
            stores the key value combo in the table
            implements open addressing collision resolution
        """
        entry = Entry(key, item)
        for i in range(len(self.table)):
            index = self.__get_hash_code(key, i)

            if self.table[index] is None or self.table[index].is_deleted:
                self.table[index] = entry
                self.current_size += 1
                if float(self.current_size) / len(self.table) >= self.load_factor:
                    self.__resize_table()
                break

    def __getitem__(self, key):
        """
            gets the value associated with the key
        """
        for i in range(len(self.table)):
            index = self.__get_hash_code(key, i)

            if self.table[index] is not None:
                if self.table[index].key == key:
                    if self.table[index].is_deleted:
                        raise KeyError('Key is not in the map')
                    else:
                        return self.table[index].value

            elif self.table[index] is None:
                raise KeyError('Key is not in the map')

        raise KeyError('Hmm something has gone wrong here')

    def __get_hash_code(self, key, value):
        return (hash(key) + value) % len(self.table)

    def __resize_table(self):
        new_table = [None] * (len(self.table) * 2)
        for i in range(len(self.table)):
            new_table[i] = self.table[i]

        self.table = new_table

    def delete(self, key):
        """
            deletes a value from the hash table
        """
        for i in range(len(self.table)):
            index = self.__get_hash_code(key, i)

            if self.table[index] is not None:
                if self.table[index].key == key:
                    if self.table[index].is_deleted:
                        raise KeyError('Key is not in the map')
                    else:
                        self.table[index].is_deleted = True
                        self.current_size -= 1
                        break

Your code looks generally quite good. I just have a few suggestions:

Don't forget to define __str__() and __repr__() for each class
I dislike the use of the "magic number" constants in the __init__() of the Hash_Map. They really ought to be either passed as parameters, read from a config somewhere, or clearly marked in a parameter section as pseudo-constants.
The line for i in range(len(self.table)): appears multiple times. This style of loop is considered non-Pythonic. Python has the enumerate() built-in that returns a succession of tuples consisting of both the item and its index. I'd prefer for (i,item) in enumerate(self.table):
If there's a clash, hash(key) will unnecessarily be called multiple times. Note that index = self.__get_hash_code(key, i) is called each time through the i loop, but the first thing it does is call hash(key) even though it may have already been computed. Better to compute hash(key) once outside the loop since it won't change.
Multiple references to self.table[index]. The interpreter might be able to optimize them away, but the code will be shorter (and less error-prone) if it performs the lookup once and stores in a temp. (Or just use enumerate() like my previous suggestion)
In def __get_hash_code(self, key, value): the third parameter is poorly named. It's not the value of the element, it's the linear probing parameter.
There's a bug related to the interaction of __get_hash_code() and __resize_table() which can lead to \$O(n)\$ performance, defeating the purpose of using a hashtable.


searching word or phrase among files I've written a program:

import java.io.File;
import java.io.FilenameFilter;
import java.io.IOException;
import java.util.ArrayList;
import org.apache.commons.io.FileUtils;

/**
 *
 * @author Mohammad Faisal
 */
public class FileContentMatcher {

public static void main(String[] args) throws IOException {

    String textToMatch = "Quick Styles gallery on";
    ArrayList<String> paths = new ArrayList<String>();
    String content;
    int found = 0;
    int notFound = 0;
    FilenameFilter filter = new FilenameFilter() {
        public boolean accept(File dir, String name) {
            return name.endsWith(".txt");
        }
    };

    File path = new File("E:\\anchit\\temp");
    File[] listOfFiles = path.listFiles(filter);
    for (File file : listOfFiles) {
        content = FileUtils.readFileToString(file);
        if (content.contains(textToMatch)) {
            //System.out.println("Found in: " + file.getAbsolutePath());
            paths.add(file.getAbsolutePath());
            found++;
        } else {
            //System.out.println("No found\n" + content);
            notFound++;
        }
    }
    for (String pth : paths) {
        System.out.println(pth);
    }
    System.out.println("Found in " + found + " files.\nNot found in " + notFound + " files.");
}
}

In which I've used Apache Commons IO api.
My actual requirement is to list all the files in the given directory which contains the search phrase textToMatch in minimum amount of time about 4-5 seconds, where number of files could be upto 100000. But this program takes much more time than that.
So I need to optimize this code but not getting how?
Is there any API which can help me? I've heard of Lucene but not getting how to work with it.

As poined out in the comments, your current approach might be too slow for your goal of "about 4-5 seconds". Depending on what's your actual use case, using an index might indeed be a good idea. This is similar to how internet search engines do it.

To create the index:

create a map Map<String, List<File>> for holding the association of search terms to files
go through all your files, and for each word in each file, add that file to the list corresponding to that word in your index map
you might want to skip common words, such as "a", "and", "the", etc., or you could even apply a stemmer to drastically reduce the variability in words

Once you've created the index (which could take quite some time), you just have to look up the search word in that index to get the list of files that contain the word (or a linguistic variant of it, if you used a stemmer).

As said before, the applicability of this approach depends heavily on your actual use case. If the files contain genetic sequences and you are searching a certain pattern, this probably won't help much. Even if you are searching for some complex phrase this might not work, as you'd have to add each possible (sub) phrase to the index. But if you are looking for individual words in ordinary text files (or HTML or the like) this might work.

Update: Since you seem to indeed search for complex phrases, you could try the following:

create the index, as desribed above, optionally using a stemmer
search for each word in your phrase (or the stemmed version thereof) in your index
for each file that, according to your index, contains all the words, do a full-text search for the original phrase

Finally, if this still does not cut it, you could also create indexes for word bigrams or even trigrams.


Is SList class an ADT? As per the definition given in lecture, ADT is,

With reference to this definition, I would like to call SList class an ADT following 6 invariants:

Multiple users of SList class should be consistent in usage with same SList instance. For example multiple users may insert items in same shopping list.
No runtime exceptions while using SList class when list is empty.
SList size member variable is always correct.
SList is never circularly linked list.
SList never returns SListNode, instead it return only an item.
Methods of the SlistNode class can be modified in future without any affect to SList class users. I guess this is nothing but encapsulation.

The below two classes will be part of a package and be used by classes from other packages:

class SListNode{
    Object item;
    SListNode next;
    public SListNode(){
        this.item = null;
        this.next = null;
    }
    public SListNode(Object item, SListNode next){
        this.item = item;
        this.next = next;
    }
    public SListNode(Object item){
        this(item,null);
    }
    public void insertAfter(Object item){
        this.next = new SListNode(item,this.next);
    }
    public SListNode nth(int position){
        if(position ==1){
            return this;
        }else if((position < 1) || (this.next == null)){ /* error checking */
            return null;
        }else{
            SListNode tempNode = this.next.nth(position-1);
            return tempNode;
        }
    }

}

public class SList {
    private SListNode head; // First node in list.
    private int size; // Number of items in list.
    public SList() { // Here’s how to represent an empty list.
        head = null;
        size = 0;
    }
    public void insertFront(Object item) {
        head = new SListNode(item, head);
        size++;
    }
    public void insertEnd(Object item){
        SListNode lastNode = this.head;
        while(lastNode.next != null){
            lastNode = lastNode.next;
        }
        lastNode.next = new SListNode(item,lastNode.next);
        size++;
    }
    public void insertAt(Object item, int position){
        if (position == 1){
            insertFront(item);
            size++;
        }else if(position < 1){
            System.exit(1);
        }else{
            SListNode currentNode = this.head.nth(position);
            if(currentNode != null){
                currentNode.insertAfter(item);
                size++;
            }else{
                System.exit(1); //position value exceeds
            }
        }
    }
    public Object nth(int position){
        if(position < 1){
            return null;
        }else{
            SListNode tempNode = this.head.nth(position);
            if(tempNode != null){
                return tempNode.item;
            }
            else{
                return null;
            }
        }
    }

    public boolean isEmpty(){
        return (size==0);
    }
}

My question:
With reference to SList class as shown above, Can you please confirm if my interpretation of definition of ADT is correct?
If the interpretation is wrong, What code changes would you like to see, to call SList as an ADT?

Note: I am yet to learn exception-handling, interfaces, inheritance, polymorphism and composition in class.

Bug:

public void insertEnd(Object item){
    SListNode lastNode = this.head;
    while(lastNode.next != null){
        lastNode = lastNode.next;
    }
    lastNode.next = new SListNode(item,lastNode.next);
    size++;
}

Make a new list, add to end. this.head is null, so lastNode.next is a NullPointerException.

Bug:

public void insertAt(Object item, int position){
    if (position == 1){
        insertFront(item);
        size++;
    }else if(position < 1){
        System.exit(1);
    }else{
        SListNode currentNode = this.head.nth(position);
        if(currentNode != null){
            currentNode.insertAfter(item);
            size++;
        }else{
            System.exit(1); //position value exceeds
        }
    }
}

Make new list, insertAt("hello", 1), insertAt("world", 2). The application shuts down.

Please test your code before putting it up for review. You'll get higher grades too, especially if you show your tests to your professor or whoever is teaching you.


Changing IP of msloop This changes the IP of msloop using WMI(Win32_NetworkAdapterConfiguration), which takes about 1~2sec.

But, if I work on another computer, it works much much slower, for about 50~60sec.

My Computer:

OS: Window 7 Professional
RAM: 8GB

Another Computer:

OS: Window XP SP3
RAM: 2GB

public void setIP () {
    ManagementClass objMC = new ManagementClass("Win32_NetworkAdapterConfiguration");
    ManagementObjectCollection objMOC = objMC.GetInstances();

    foreach (ManagementObject objMO in objMOC) {
        if (!(bool) objMO["IPEnabled"]) {
            continue;
        } else if ((String) objMO["ServiceName"] != "msloop") {
            continue;
        }

        try {
            ManagementBaseObject objNewIP = objMO.GetMethodParameters("EnableStatic");
            ManagementBaseObject objNewGate = objMO.GetMethodParameters("SetGateways");

            objNewIP["IPAddress"] = new string[] { "110.110.110.1" };
            objNewIP["SubnetMask"] = new string[] { "255.255.255.252" };

            objNewGate["GatewayCostMetric"] = new string[] { "1" };

            objMO.InvokeMethod("EnableStatic", objNewIP, null);
            Console.WriteLine("EnableStatic End");
            objMO.InvokeMethod("SetGateways", objNewGate, null);
            Console.WriteLine("SetGateways End");

            Console.WriteLine("Change OK");
            Console.WriteLine("==================================================================");
        } catch (Exception ex) {
            MessageBox.Show("Unable to Set IP : " + ex.Message);
        }
    }
}

The result is always "Change OK". It works on XP, but very slowly.  Is the problem with the OP or the RAM?

Can't help with the speed question but some generic remarks:

Both ManagementClass and ManagementObjectCollection are IDisposable and should therefore be wrapped in a using block to make sure any unmanaged resources are properly released.
Prefixing all your local variables with obj smells like hungarian notation and is generally discouraged. It adds not value and just clutter. Your variable names should indicate what they represent and not what type they are.
In C# land the common naming convention for methods is PascalCase and not camelCase. It pays to stick to general naming conventions for the ecosystem you are working in as it will make your code look more familiar to other developers.


Project Euler #58: Primes along the diagonals of a square spiral I am working on Project Euler Problem 58:

  Starting with 1 and spiralling anticlockwise in the following way, a
  square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

  It is interesting to note that the odd squares lie along the bottom
  right diagonal, but what is more interesting is that 8 out of the 13
  numbers lying along both diagonals are prime; that is, a ratio of 8/13
  ≈ 62%.

  If one complete new layer is wrapped around the spiral above, a square
  spiral with side length 9 will be formed. If this process is
  continued, what is the side length of the square spiral for which the
  ratio of primes along both diagonals first falls below 10%?

My code gives the correct answer, but it takes a very long time to do it, even while using Pypy, a JIT compiler.

I would like to know some good ways to increase my efficiency in this problem.

import random
def m_r(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for repeat in range(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def eraSieve(n):
    sieve=[True]*(n+1)
    sieve[:2] = [False, False]
    sqrt = int(n**.5)+1
    for x in xrange(2, sqrt):
        if sieve[x]:
            sieve[2*x::x]=[False]*(n/x-1)
    return sieve

def diagonalNum(n): # n is the number of row
    increment = 2
    getDiaNum = 1
    limit = (n-1)/2
    sideLen = 1.0
    c = 0.0
    for i in xrange(1, limit + 1):
        count = 1
        while count <= 4:
            getDiaNum += increment
            if m_r(getDiaNum):
                c += 1
            count += 1
        increment += 2
        sideLen += 4
    return c / sideLen

for x in xrange(1, 100000):
    ratio = diagonalNum(x)
    print x
    if ratio < 0.10:
        break
print x

A bit of math

It is interesting to see that the corners of a square of size \$s\$ have values: \$s^2-3s+3\$, \$s^2-2s+2\$, \$s^2-s+1\$, \$s^2\$. (Also \$s^2\$ is not a prime ;-))

To be continued later.


Scala inspired classes in Python I have to define a lot of values for a Python library, each of which will represent a statistical distribution (like the Normal distribution or Uniform distribution). They will contain describing features of the distribution (like the mean, variance, etc). After a distribution is created it doesn't really make sense to change it.

I also expect other users to make their own distributions, simplicity is an extra virtue here.

Scala has really nice syntax for classes in cases like this. Python seems less elegant, and I'd like to do better.

Scala:

class Uniform(min : Double, max : Double) {
    def logp(x : Double) : Double =
        1/(max - min) * between(x, min, max)

    def mean = (max + min)/2
}

Python:

class Uniform(object):
    def __init__(self, min, max):
        self.min = min
        self.max = max
        self.expectation = (max + min)/2

    def logp(self, x):
        return 1/(self.max - self.min) * between(x, self.min, self.max)

It's not terrible, but it's not great. There are a lot of extra selfs in there and the constructor part seems pretty boilerplate.

One possibility is the following nonstandard idiom, a function which returns a dictionary of locals:

def Uniform(min, max):
    def logp(x):
        return 1/(max - min) * between(x, min, max)

    mean = (max + min)/2
    return locals()

I like this quite a bit, but does it have serious drawbacks that aren't obvious?

It returns a dict instead of an object, but that's good enough for my purposes and would be easy to fix with a that made it return an object.

Is there anything better than this? Are there serious problems with this?

You might prefer to use namedtuple for the attributes, and the property decorator for mean. Note that mean is now computed every time it's accessed - maybe you don't want this, or maybe it makes sense since max and min are mutable.

from collections import namedtuple

class Uniform(namedtuple('Uniform', ('min', 'max'))):

    def logp(self, x):
        return 1/(self.max - self.min) * between(x, self.min, self.max)

    @property
    def mean(self):
        return 0.5*(self.min + self.max)


Detecting when the contents of a web page changes This is the code I'm using at the moment

/*
 * Adjust content height so that it always fills browser height
 *
 * written by Tom Jenkinson
 */

jQuery(document).ready(function() {

    refreshContentSize(); //run initially

    $(window).resize(function() { //run whenever window size changes
        refreshContentSize();
    });

    setInterval('refreshContentSize()', 500); // in case content size changes. THIS IS WHAT I WANT TO CHANGE
});

function refreshContentSize()
{
    var startPos = $("#content").position();
    var topHeight = startPos.top;
    var contentHeight = $("#content").outerHeight(true);
    var footerHeight = $("#footer").outerHeight(true);
    var viewportHeight = $(window).height();
    var spaceForContent = viewportHeight - footerHeight - topHeight;

    if (spaceForContent <= contentHeight)
    {
        var newHeight = 0;
    }
    else
    {
        var newHeight = spaceForContent - contentHeight;
    }
    $("#filler").css('height', newHeight);
    return;
}

The site is http://wncba.co.uk/results and the script is at http://wncba.co.uk/results/javascript/fill-pagev2.js.

At the moment you can see that I'm using a timer to keep calling the refreshContentSize(). I am doing this because some of the content on the page can change dynamically meaning the page height will change.

Is there a handle for this like jquery's 'resize' so I don't need the timer?

I can't really verify what the code does since when I checked, the filler is always 0px. But I assume your code checks for the surrounding elements in an interval and updates the filler height accordingly.

I have some tips for your code:

//shorthand .ready using the jQuery namespace
//and using the $ as the inner namespace
jQuery(function ($) {

    //cache repeatedly used references
    var content = $("#content"),
        footer = $("#footer"),
        $window = $(window),
        filler = $("#filler");

    // - place functions inside the ready handler to avoid globals
    // - always hand over a function reference to a timer and never an eval-able string
    // - since 500ms is fast enough, resize and an init wouldn't be needed
    //   a human sees 200ms as "instant" and at least 700ms a significant lag
    //   somewhere in between is the "sweet spot"
    setInterval(function () {
        var startPos = content.position(),
            topHeight = startPos.top,
            contentHeight = content.outerHeight(true),
            footerHeight = footer.outerHeight(true),
            viewportHeight = $window.height(),
            spaceForContent = viewportHeight - footerHeight - topHeight,
            //JS has a function scope. Any variable declared anywhere is visible
            //everywhere in the containing function. Therefore, it's better to
            //declare them outside operations
            newHeight = 0; //default to 0

        //overwrite 0 if conditions state otherwise
        if (spaceForContent > contentHeight) {
            newHeight = spaceForContent - contentHeight
        }

        //so it's 0 or some other value
        filler.css('height', newHeight);

    }, 500);
});

Packed version:

jQuery(function ($) {
    var content = $("#content"),
        footer = $("#footer"),
        $window = $(window),
        filler = $("#filler");
    setInterval(function () {
        var startPos = content.position(),
            topHeight = startPos.top,
            contentHeight = content.outerHeight(true),
            footerHeight = footer.outerHeight(true),
            viewportHeight = $window.height(),
            spaceForContent = viewportHeight - footerHeight - topHeight,
            newHeight = 0;
        if (spaceForContent > contentHeight) {
            newHeight = spaceForContent - contentHeight
        }
        filler.css('height', newHeight)
    }, 500)
});

You might want to check out Mutation Observers API which gives you the ability to listen to changes in the DOM. It's not yet supported across browsers but just included it if ever you are interested.

Also, I think it's better that you rethink your layout - one which only relies on plain HTML and CSS.


Getting all number from a String like this "1,2,5-9" I need to get the numbers in a string like "1,2,5-9", the function should return a list with these values [1,2,5,6,7,8,9]

Here's what I did. Is this the best way or there's something simpler/better?

function isNumber(n) {
  return !isNaN(parseFloat(n)) && isFinite(n);
}

function getNumbers(stringNumbers) {
  var nums = [];
  var list1 = stringNumbers.split(",");
  var length = list1.length;
  for(var i = 0; i < length; i++) {
    var number = list1[i];
    if(number.indexOf("-") != -1) {
      range = number.split("-");
      if(isNumber(range[0]) && isNumber(range[1])) {
        var min = parseInt(range[0]);
        var max = parseInt(range[1]);

        //edit to accept range like 9-5

        if(min > max){
          var min_ref = min;
          min = max;
          max = min_ref;
        }

        while(min <= max) {
          nums.push(min);
          min++
        };
      }
    } else {
      if(isNumber(number)) {
        nums.push(parseInt(number));
      }
    }
  }

  //edit to sort list at the end
  return nums.sort(function(a,b){return a - b});
};

Well, here's my version that's benchmarked across different browsers. Might need some improvement (currently finding shortcuts for the isNumber), but works as marketed:

function getNumbers(stringNumbers) {

    //personal preference, but I got this handy tip from the internet that

    //if you had assignments, better if they are individually var'ed
    var nums = [];
    var entries = stringNumbers.split(',');
    var length = entries.length;

    //for variabes that don't, comma separated
    var i, entry, low, high, range;

    for (i = 0; i < length; i++) {
        entry = entries[i];

        //shortcut for testing a -1
        if (!~entry.indexOf('-')) {
            //absence of dash, must be a number
            //force to a number using +
            nums.push(+entry);
        } else {
            //presence of dash, must be range
            range = entry.split('-');

            //force to numbers
            low = +range[0];
            high = +range[1];

            //XOR swap, no need for an additional variable. still 3 steps though
            //http://en.wikipedia.org/wiki/XOR_swap_algorithm
            if(high < low){
              low = low ^ high;
              high = low ^ high;
              low = low ^ high;
            }

            //push for every number starting from low
            while (low <= high) {
                nums.push(low++);
            }
        }
    }

    //edit to sort list at the end
    return nums.sort(function (a, b) {
        return a - b;
    });
}

Here's another version, which is slightly slower (the V2) since I added the additional number checks which the one above didn't but more conformant to the specification of the question.

var getNumbers = (function () {

    //we create a closure so as not to expose some of our utility functions

    function isNumber(n) {
        //we check isFinite first since it will weed out most of the non-numbers
        //like mixed numbers and strings, which parseFloat happily accepts
        return isFinite(n) && !isNaN(parseFloat(n));
    }

    //let's get this one out as well
    //the simple sort() wouldn't work so instead we provide a sorter
    function sorterFunction(a, b) {
        return a - b;
    }

    //getNumbers should be this function
    return function (stringNumbers) {

        //variable declaration format is personal preference
        //but I prefer having declarations with assignments have individual vars
        //while those that have no assignments as comma separated
        var i, range, low, high, entry;

        //an added bonus, " and ' are the same in JS, but order still applies
        //I prefer to use ' since it's cleaner
        var entries = stringNumbers.split(',');
        var length = entries.length;
        var nums = [];

        for (i = 0; i < length; ++i) {
            entry = entries[i];

            if (isNumber(entry)) {
                //we check if the entry itself is a number. If it is, then we push it directly.
                //an additinal advantage is that negative numbers are valid
                nums.push(+entry);
            } else {

                //if not a number, probably it had the - and not being a negative number
                //only here do we split after we determined that the entry isn't a number
                range = entry.split('-');

                //check if what we split are both numbers, else skip
                if (!isNumber(range[0]) || !isNumber(range[1])) continue;

                //force both to be numbers
                low = +range[0];
                high = +range[1];

                //since we are dealing with numbers, we could do an XOR swap
                //which is a swap that doesn't need a third variable
                //http://en.wikipedia.org/wiki/XOR_swap_algorithm
                if (high < low) {
                    low = low ^ high;
                    high = low ^ high;
                    low = low ^ high;
                }

                //from low, we push up to high
                while (low <= high) {
                    nums.push(low++);
                }
            }
        }
        return nums.sort(sorterFunction);
    }
}());


Validate IP address in Java Following is the code that I'm currently using to validate the user given IP address (IPV4 and IPV6). It makes use of apache commons-validator's InetAddressValidator. However, their function validates only IPV4 address and not IPV6.

public static boolean isValidInetAddress(final String address){
        boolean isValid = false;
        if(address == null || address.trim().isEmpty())
            return isValid;
        if(InetAddressValidator.getInstance().isValid(address)){
            isValid = true;
        } else { //not an IPV4 address, could be IPV6?
            try {
                isValid = InetAddress.getByName(address) instanceof Inet6Address;
            } catch (UnknownHostException ex) {
                isValid = false;
            }
        }
        return isValid;
    }

Is there a better way?

(P.S commons-validator does regex pattern matching for IPV4 address validation)

It seems fine if there is not any simpler Java or Apache Commons API.

I'd modify a few small things:

The isValid boolean would be unnecesary if you return immediately when you know the return value. (Flattening Arrow Code)
(address == null || address.trim().isEmpty()) could be changed to StringUtils.isBlank.
According to the Code Conventions for the Java Programming Language if statements always should use braces.

public static boolean isValidInetAddress(final String address) {
    if (StringUtils.isBlank(address)) {
        return false;
    }
    if (InetAddressValidator.getInstance().isValid(address)) {
        return true;
    }

    //not an IPV4 address, could be IPV6?
    try {
        return InetAddress.getByName(address) instanceof Inet6Address;
    } catch (final UnknownHostException ex) {
        return false;
    }
}


Lopsided Trees and Recursion The original problem is:

  Define the height of a binary tree to be the number of nodes in the
  longest path from the root to a leaf. The empty tree is considered to
  have height 0. A node is k-balanced if its left and right subtrees
  differ in height by at most k. A tree is k-balanced if all of its
  nodes are k-balanced. The empty tree is considered to be k-balanced.

  For example, the tree below has height 4.

    o
   / \
  o   o
 / \
o   o
   /
  o

  This tree is 2-balanced but not 1-balanced, because the left subtree
  of the root has height 3 and the right subtree of the root has height
  1. Your task is to write a method that takes a balance factor k and a number of nodes n and returns the maximum height of a k-balanced tree
  with n nodes.

One of the answer(right and fast) is:

int fewest_node(int k,int h)
{
    if(h <= 0)
        return 0;
    return 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

and my solution(terribly slow) is:

int maxHeight(int k, int n)
{
    int i,left,right;
    if(k >= n)
        return n;
    if(n > 2)
    {
        left = maxHeight(k,n-1);
        if(left <= k)
            return left+1;
        else
        {
            i = n - 2;
            left = maxHeight(k,i);
            right = maxHeight(k,n-1-i);
            while((left - right) > k)
            {
                i--;
                left = maxHeight(k,i);
                right = maxHeight(k,n-1-i);
            }
            return left+1;
        }
    }
    else
        return n;
}

My question:

Is my solution really correct? I mean, does it work regardless of its efficiency? Or in other words, is it right logically? (BTW, I think it's right, and I have tested the output when n is less than 30)
Why is my solution so slow? As you can see, I'm a newbie to DSA.

I would consider your first question as offtopic. So I will only answer the second question.

For each call to maxHeight you make a lot of recursive calls. Consider what happens if n is large. Say n=100, then can you tell me how many times you call maxHeight? I can't work it out other than "lots". Also consider that you will be calling maxHeight with the same arguments very often, calculating the same results over and over.

Lets look at an example recursive function that bears some resemblance to your code:

int f(int n)
{
    if (n == 0)
        return 1;

    int sum = 0;
    while(n--){ // In your code: while((left - right) > k)
        sum += f(n);
    }
}

While this looks innocent, even for small n you will iterate a really long time. For f(1) you will need one call to f(0). For f(2) you will need one call to f(1) (which calls f(0)) and one to f(0) which totals 3 calls. For f(3) you will need one call to f(2) (which then does 3 more calls), f(1) (which does 1 extra call for you) and f(0) i.e. (3+1) + (1+1) + 1 = 7. Continuing on f(4) will need (7 + 1) + (3 + 1) + (1+1) + 1 = 15. I think you can see where this is heading. For f(n) you will need 2^n-1 calls. So for n=300 you have 2^300 ~= 10^100 calls to  f(0). To put that into perspective considering that it's been estimated that there are about 10^80 atoms in the observable universe. I wouldn't want to stick around and wait until that completes. Not even if every atom in the observable universe was a 1 THz computer working optimally in parallel to calculate this.

Your code exhibits the same type of pattern, you make many recursive calls per call to maxHeight so you are probably even worse off.

Comparing to:

int fewest_node(int k,int h)
{
    if(h <= 0)
        return 0;
    return 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

Calling fewest_node(int j, int h) will result in at most 2^h recursive calls, which is still a lot, but less than your code. But here is the catch, fewest_node() is very simple in structure and the compiler can expand the function in a way similar to loop-unrolling which removes a lot of iteration and overhead. This is a case of K.I.S.Silly.

One way that both of the solutions can be speed up dramatically is by using Dynamic Programming, like this:

#define MAX_N 1000 // Adjust to taste
#define MAX_K 100

int dp_table[MAX_N *MAX_K]={0}; // Not sure if this is legal, otherwise use memset

int fewest_node(int k,int h)
{
    int index = k*MAX_N+h;
    if(!dp_table[index]){
        if(h <= 0)
            return 0;
        dp_table[index] = 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);
    }
    return dp_table[index];
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

Simply store each calculated result for fewest_node and start from the bottom up with small h. You can also dynamically allocated a table of the required size when you have received your n and k for the problem. This will drop the worst case time from 2^n to n*k which is eons faster. You can do the same for your code. Just introduce a table of cached results.


Simple timer start and stop from console Just a simple timer application for review.  Stop and start the timer from the command line.

The plan is to use this in a poker application to fold out a player if they don't act after a time period (call the clock on them).  I was trying to use async await but it did not seem like the right tool for this.

MyTimer myTimer = new MyTimer();
while (true)
{
    string readLine = Console.ReadLine();
    if (readLine == "stop")
    {
        myTimer.TimerStop();
    }
    else if (readLine == "start")
    {
        myTimer.TimerStart();
    }
    else if (readLine == "q")
    {
        Environment.Exit(0);
    }
}

.

public class MyTimer
{
    private System.Timers.Timer aTimer = new System.Timers.Timer();
    private static void OnTimedEvent(Object source, System.Timers.ElapsedEventArgs e)
    {
        Debug.WriteLine("The Elapsed event was raised at {0}", e.SignalTime);
        Console.WriteLine("The Elapsed event was raised at {0}", e.SignalTime);
    }

    public void TimerStop()
    {
        aTimer.Enabled = false;
        Console.WriteLine("aTimer.Enabled = false");
    }
    public void TimerStart()
    {
        aTimer.Enabled = true;
        Console.WriteLine("aTimer.Enabled = true");
    }

    public MyTimer()
    {
        aTimer.Interval = 2000;
        // Hook up the Elapsed event for the timer.
        aTimer.Elapsed += OnTimedEvent;
        // Have the timer fire repeated events (true is the default)
        aTimer.AutoReset = true;
        // Start the timer
        aTimer.Enabled = true;
        Debug.WriteLine("aTimer.Enabled");
        Console.WriteLine("aTimer.Enabled");
    }
}

Why aren't you inheriting from Timer it's not a sealed class and is disposable (and I believe must be disposed).

public class PokerTimer : Timer
{
    public PokerTimer() : this(2000)
    {

    }

    public PokerTimer(double interval) : base(interval)
    {
        AutoReset = true;
        Elapsed += OnTimedEvent;
    }

    protected override void Dispose(bool disposing)
    {
        //clean up anything you need to here or remove this override.
        base.Dispose(disposing);
    }
}

All that being said, you said this is for a game where you want to time out players so you might want to look a bit into game loops and managing state in such a loop.


Sort function to sort item numbers separated by colon Below is my code. This is a function that will be applied as a sorting method to a grid based data set. The data in the column to be sorted can be stuff like: 123456, 123456:123444, and 12345:12359:139943. So far, I have tested it and it works, but I want to know in which situations might it not work, or if there is a way to optimize/improve the method in any way.

function SkuSorter(a, b, c) {
    // check if either input is a set
    var aMatch = a.match(/\:/g);
    var bMatch = b.match(/\:/g);

    // all items by default should be a regular sku, we'll change this later
    var aType = 0;
    var bType = 0;

    /* types;
     * 0 = regular sku
     * 1 = duo (12345:12345)
     * 2 = trio (1234:1234:1234)
     */

    // has the user sorted asc or desc?
    var direction = c;

    // if 'a' is a set, determine if it is a duo or trio
    if (aMatch) {
        if (aMatch.length == 1) aType = 1;

        if (aMatch.length > 1) aType = 2;
    }

    // save as above
    if (bMatch) {
        if (bMatch.length == 1) bType = 1;

        if (bMatch.length > 1) bType = 2;
    }

    // if 'a' is a set and 'b' isn't, a should come before b (puts sets at the bottom)
    if (aType == 0 && bType != 0) {
        return -1 * direction;
    }

    // save as above, but viceversa.
    if (aType != 0 && bType == 0) {
        return 1 * direction;
    }

    // if both inputs are regular skus, do normal sort operation
    if (aType == 0 && bType == 0) {
        if (direction == -1) {
            return b - a;
        } else {
            return a - b;
        }
    }

    // if 'a' is a set and it is of higher order (i.e. trio > duo)
    if (aType > 0 && aType > bType) {
        return 1 * direction;
    }

    // same as above, but for 'b'
    if (bType > 0 && bType > aType) {
        return -1 * direction;
    }

    // if both inputs are sets
    if (aType > 0 && bType > 0) {

        //break up the individual pieces
        var aP = a.split(':');
        var bP = b.split(':');

        /*
         * The following conditions will compare:
         * The first chunk and sort them based on value
         * Then the second chunk, and if it is a trio, the third.
         */
        if (aP[0] > bP[0]) {
            return 1 * direction;
        }

        if (aP[0] < bP[0]) {
            return -1 * direction;
        }

        // second chunk
        if (aP[1] > bP[1]) {
            return 1 * direction;
        }

        if (aP[1] < bP[1]) {
            return -1 * direction;
        }

        // third chunk
        if (aType > 1 && bType > 1) {
            if (aP[2] > bP[2]) {
                return 1 * direction;
            }

            if (aP[2] < bP[2]) {
                return -1 * direction;
            }
        }
    }
}

Expected behavior:

Before:

1654110
1574698
1189364
1229764
1700004
310425
1626613
36509
1676618
1676832
1536622
1749548
36509:310444
3199:44999:34000
3199:45000:34000
3199:45000:34111
1874361
1551225
1581271
1626076
36509:310425
1676816
1676824

After:

36509
310425
1189364
1229764
1536622
1551225
1574698
1581271
1626076
1626613
1654110
1676618
1676816
1676824
1676832
1700004
1749548
1874361
36509:310425
36509:310444
3199:44999:34000
3199:45000:34000
3199:45000:34111

@Flambino was a bit faster :

function sortSKU( a, b  )
{
    var aParts = a.split( ':' ),
        bParts = b.split( ':' ),
        partCount = aParts.length,
        i;

    if( aParts.length != bParts.length )
        return aParts.length - bParts.length;

    for( i = 0 ; i < partCount ; i++ )
    {
      if( aParts[i] != bParts[i] )
        return +aParts[i] - +bParts[i];
    }
    //Exactly the same
    return 0;
}

console.log( data.sort( sortSKU )  );

As Flambino said, use .reverse() to sort one way or another. Also this function will sort 123 prior to 2:2 if such a case can occur.

If you need the 'c'

function sortingCallback( array, direction ){

  if( direction == 'whatever ascending is' ){
    return array.sort( sortSKU );
  }

  return array.sort( sortSKU ).reverse();
}


Rearranging array elements depending on their indexes I am (still!) going through these CodingBat exercises for Java. Here is the one I have just done:

  Return an array that contains the exact same numbers as the given array, but rearranged so that all the zeros are grouped at the start of the array. The order of the non-zero numbers does not matter. So {1, 0, 0, 1} becomes {0 ,0, 1, 1}. You may modify and return the given array or make a new array.

And here is my code:

    public int[] zeroFront(int[] nums){

    int zeroCount = 0;
    int[] resultantArray = new int[nums.length];
    int[] noZerosArray = new int[nums.length];

    //Count zeros
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            zeroCount++;
        }
    }

    //Make an array without any zeros
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] != 0){
            noZerosArray[j] = nums[i];
            j++;
        }
    }

    //To resultant array, add zeros first, then add remaining numbers of original
    for (int i = 0; i < resultantArray.length; i++) {
        if (i < zeroCount) {
            resultantArray[i] = 0;
        } else {
            resultantArray[i] = noZerosArray[i-zeroCount];
        }
    }

    return resultantArray;
}

Please bear in mind I am doing it without importing anything extra like java.util.Arrays etc., as , primarily, this is not accepted by the assessor and, secondarily, I want to get to grips with arrays without importing anything extra yet.

Regarding my code, I would like to know how this can be improved. Is this a good solution? It feels like it could be more efficient, bearing in mind I have three for loops and creating three extra arrays.

Even though this one seems trivial, I found it really difficult!

The trick you are missing here is a simple swap.

All you need to do is keep a "fast" and a "slow" index in the array. The "fast" index scans forwards looking for 0 values. The "slow" index is an insert-point for where the next 0 would belong.

Consider this loop:

public int[] zeroFront(int[] nums){

    int slow = 0; // next zero inserted here
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] == 0) {
            nums[fast] = nums[slow];
            nums[slow] = 0;
            slow++;
        }
    }
    return nums;
}

That loop finds all zero values and then swaps non-zero values with them from the beginning of the loop, ending with a situation where the zeros are all at the front.

Sometimes, tricks like these are really hard to spot, but, when pointed out, make you think: Neat!


Checking that a 6-digit number is not repeated and not in sequence Following is the objective C code snippet to check that the 6-digit number is not repeated and not in sequence/reverse-sequence. I have just printed the proper messages in NSLog that user should be allowed or not:

 NSError *error = nil;
 NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:@"(?!(\\d)\\1+$|(?:0(?=1)|1(?=2)|2(?=3)|3(?=4)|4(?=5)|5(?=6)|6(?=7)|7(?=8)|8(?=9)|9(?=0)){5}\\d$|(?:0(?=9)|1(?=0)|2(?=1)|3(?=2)|4(?=3)|5(?=4)|6(?=5)|7(?=6)|8(?=7)|9(?=8)){5}\\d$)\\d{6}$" options:NSRegularExpressionCaseInsensitive error:&error];

        NSRange matchRange = [regex rangeOfFirstMatchInString:text options:NSMatchingReportCompletion range:NSMakeRange(0, text.length)];

        BOOL didValidate = NO;
        if(matchRange.location != NSNotFound){
            didValidate = YES;
        }
        if(didValidate){
            NSLog(@"Allowed");
        }else{
            NSLog(@"Not Allowed");
        }

I just want to know if this regex has an effect on performance, and if yes, then what should be optimal solution for it. It would be great if anyone can provide their inputs for the same.

I would write a separate function for validating a string (so that it has a name and you can talk about it).

Then, I would not use regular expressions for it but just simple code:

The length must be 6.
Only digits are allowed.
For each pair of adjacent digits, their difference must be at least 2.

That should be much easier to understand than your regular expression.


Simpler method to find users in child categories I am using the ancestry gem to organize my post categories tree.
I have 8 parent categories, and they all have many child categories.
To retrieve an array of child categories, I use:

parent_category.children

I defined these relations in my category model:

  has_ancestry
  has_many :posts
  has_many :users, through: :posts

The last relation allows me to find the users who post in each category.

What I am trying to do: on first login, users have to choose their categories of interest. On the next screen, they are suggested users who post in the categories they chose.

To find the suggested users, I wrote a method:

def recommendations
    @users = []
    (current_user.get_voted Category).each do |category|
      category.children.each do |cat|
        @users << cat.users
      end
    end
    @users = @users.flatten.uniq
 end

This works, but it seems overly complicated. Is there any way to do this in a "best practice" way ?

Some notes:

ys = [] + xs.each + ys.push + ys.flatten That's an imperative and pretty verbose pattern. A functional approach would use flat_map.
@users = @users.flatten.uniq. Don't re-use variables. Different values, different variables.
(current_user.get_voted Category). You saved two parens on the function call at the cost of being forced to write them to wrap the expression. It's not worth it. I'd just use parens on calls except in DSL-style statements. Check https://github.com/bbatsov/ruby-style-guide

I'd write:

def recommendations
  @users = current_user.get_voted(Category).
    flat_map { |category| category.children.flat_map(&:users) }.
    uniq
end


Counting occurrences of substring in string I need to know how many times a substring occurs in a given string.  I figured that I might as well create an extension method:

public static int Occurences(this string str, string val)
{
    string copy = str;

    int instancesOf = 0;
    int indexOfVal;

    while ((indexOfVal = copy.IndexOf(val)) != -1)
    {
        copy = copy.Remove(indexOfVal, val.Count());
        instancesOf++;
    }

    return instancesOf;
}

I'm not sure that the assignment in the while loop is good practice.  Should I change this to compute the value once outside the loop, and once in the loop, like this?

int indexOfVal = copy.IndexOf(val);

while (indexOfVal != -1)
{
    copy = copy.Remove(indexOfVal, val.Count());
    instancesOf++;
    indexOfVal = copy.IndexOf(val);
}

Any and all comments appreciated, the more the better.

Your current implementation could be more efficient.  Copying the passed in string and chopping it up is probably pretty expensive (I'm not a master of .NET internals though).

val.Count()

Why not val.Length?  Count() is very inefficient compared to Length.

copy = copy.Remove(indexOfVal, val.Count());

We don't need to remove part of the string, just search again starting at indexOfVal + val.Length.

Here is an example using an overload of String.IndexOf:

public static int Occurences(this string str, string val)
{
    int occurrences = 0;
    int startingIndex = 0;

    while ((startingIndex = str.IndexOf(val, startingIndex)) >= 0)
    {
        ++occurrences;
        ++startingIndex;
    }

    return occurrences;
}

This implementation will count overlapping occurrences (so "bbb".Occurences("bb") will return 2.

If you don't want to count overlapping occurences, you can replace ++startingIndex; with:

startingIndex += val.Length

On why an exception isn't thrown in the case of "foo".Occurrences("o"), from MSDN:

  If startIndex equals the length of the string instance, the method returns -1.


Block Allocation in Fixed-Size Block Allocator The following routine is the block-allocation procedure in a fixed-size allocator being written for library use. It is designed to be accessed from C++ (the un-mangled symbol name is void * Superblock::alloc_block()). The performance of this routine is the critical to the library; and I, with almost no prior experience in assembly, am looking for suggestions about performance and also any holes in the logic. It seems to be working correctly right now, but I'm worried about edge cases.

Execution context: written for x86_64 System V abi, full allocator may be found here: https://github.com/cmura81/experimental-allocator.

alloc_sb_alloc_block.s:

.globl __ZN10Superblock11alloc_blockEv

// 'this is passed in %rdi
// Variables:
//    this->beginning = 0(%rdi) +8
//    this->last_privately_freed_block = 8(%rdi) +8
//    this->last_publicly_freed_block = 16(%rdi) +8
//    this->block_size = 24(%rdi) +2
//    this->free_blocks = 26(%rdi) +2
//    this->max_blocks = 28(%rdi) +2

__ZN10Superblock11alloc_blockEv:
  xorq %rcx, %rcx
  // this->beginning -> rsi
  movq 0(%rdi), %rsi
  // allocated_block = this->last_privately_freed_block
  movq 8(%rdi), %rax
  // if this->last_privately_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_pubchalloc
  // this->free_blocks--
  decw 26(%rdi)

  // Move 2 bytes from rax into edx
  movzwl (%rax), %edx
  notw %dx
  jz __ZN10Superblock11alloc_blockEv.i_nbi_ffff
  notw %dx
  movslq %edx, %rcx
  // this->last_privately_freed_block = this->beginning + next_block_index
  addq %rcx, %rsi
  movq %rsi, 8(%rdi)

  ret
__ZN10Superblock11alloc_blockEv.i_nbi_ffff:
  movq $0, 8(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_pubchalloc:
  movq 16(%rdi), %rax
  // if this->last_publicly_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_noalloc
  // this->free_blocks--
  decw 26(%rdi)

  // if *(uint16_t)(this->last_publicly_freed_block + next_block_index) == 0xFFFF
  movzwl (%rax), %edx
  notw %dx
  jz __ZN10Superblock11alloc_blockEv.i_pubnbi_ffff
  notw %dx
  movslq %edx, %rcx
  // this->last_privately_freed_block = this->beginning + next_block_index
  addq %rcx, %rsi
  movq %rsi, 16(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_pubnbi_ffff:
  movq $0, 8(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_noalloc:
  movq $0, %rax
  ret

These comments all have to do with optimization, not "logic holes."  Also, they are written without having tested them.  Obviously you'll want to both ensure correct function, and profile to see if they actually improve anything.

1) As an obvious first step:

xorq %rcx, %rcx

can be done as

xorq %ecx, %ecx

It produces the same effect, but it's 1 byte shorter.

2) It looks like you are using notw %dx (in 2 different places) to see if dx is 0xffff?  I might try cmp $0xffff, %dx instead.  It's 2 bytes longer, but you don't have to "put it back" if it's not (the extra notw %dx costs 3 bytes).

3) (Check me on this one) You are using movslq %edx, %rcx to move edx to rcx.  However because of how you populate edx, I believe it already clears the upper bits.  Such being the case, a simple movq %rdx, %rcx might suffice.

4) The __ZN10Superblock11alloc_blockEv.i_pubchalloc loop should probably have a pause inserted.  Perhaps something like this:

__ZN10Superblock11alloc_blockEv.i_pubchalloc2:
  pause
__ZN10Superblock11alloc_blockEv.i_pubchalloc:
  movq 16(%rdi), %rax
  // if this->last_publicly_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_pubchalloc2

See the docs on pause for why this is a good idea.

These are all pretty nitpicky.  Since there's only the 1 loop, there's just not that much to optimize.


Thread-safe session manager Expected behavior of the code below:

There will be one static SessionManager accessed by many threads.
Multiple calls to SessionManager.UseTheSession for a given session ID must be processed on a first come first serve basis (similarly, calling EndSession should allow any currently executing UseTheSession's to finish).
The goal of the individual session locks is that a call to SessionManager.UseTheSession by one thread doesn't hold up another thread that is calling the same method with a different session ID.

Things I'm looking for input on are:

Will this perform as expected.
Does sessions need to be a ConcurrentDictionary or does a regular Dictionary work fine here since I'm locking any access of the one key.
What's a good way to handle the memory leak that happens when I keep creating new locks but don't remove them for a given id after I stop using that it?

The code (runnable in Linqpad with the inclusion of the System.Collections.Concurrent namespace):

void Main()
{
    var sm = new SessionManager();

    Guid id = sm.StartSession();

    sm.UseTheSession(id).Dump();
    sm.UseTheSession(id).Dump();

    sm.EndSession(id);
}

public class SessionManager
{
    private ConcurrentDictionary<Guid, object> sessionLocks =
        new ConcurrentDictionary<Guid, object>();

    private ConcurrentDictionary<Guid, ASession> sessions =
        new ConcurrentDictionary<Guid, ASession>();

    public Guid StartSession()
    {
        Guid id = Guid.NewGuid();

        // Takes a sec to create the session.
        var session = new ASession(string.Format("Session {0}", id));
        Thread.Sleep(1000);

        if(!sessions.TryAdd(id, session))
            throw new Exception("Astronomically unlikely situation encountered.");

        return id;
    }

    public int UseTheSession(Guid id)
    {
        lock(this.GetSessionLocker(id))
        {
            ASession session;
            if(sessions.TryGetValue(id, out session))
            {
                return this.DoSomethingWithSession(session);
            }
            else
            {
                throw new Exception(string.format("Session with id {0} does not exist.",
                    id));
            }
        }
    }

    public void EndSession(Guid id)
    {
        lock(this.GetSessionLocker(id))
        {
            ASession removedSession;
            if(sessions.TryRemove(id, out removedSession))
            {
                this.CleanUpSessionRemnants(removedSession);
            }
        }
    }

    private object GetSessionLocker(Guid id)
    {
        return sessionLocks.GetOrAdd(id, x => new object());
    }

    private int DoSomethingWithSession(ASession session)
    {
        Thread.Sleep(1000);

        return 1;
    }

    private void CleanUpSessionRemnants(ASession session)
    {
        Thread.Sleep(1000);
    }
}

public class ASession
{
    public ASession(string name)
    {
        this.Name = name;
    }

    public string Name { get; private set; }
}

In this answer I explain in details why one should not throw System.Exception. You should be throwing InvalidOperationException in the case of the astronomically unlikely situation, and probably an ArgumentException in the case of the non-existing session.

As far as thread safety is concerned, I don't write multithreaded code very often so I might be completely wrong, but I since ConcurrentDictionary is a thread-safe IDictionary implementation, sessions.TryGetValue(id, out session) is already a thread-safe call, doesn't need to be wrapped in a lock block.


Where to put hidden fields when displaying entities properties in a table? Let's say that I have a view, whose purpose is to show a table with some information about a person entity. The view contains a form with an input element that the user can use to add a new person to the table by entering its name.

My question is: In this scenario, is there a convention about where to put hidden fields that are needed to retrieve the data in the server again?

In my code, I put them in the table definition; but maybe it's best to put all those fields together inside a div or something. Maybe it just doesn't matter where you put those as long as the code works. I'm just curious because I like to generate the best HTML possible.

I understand that this type of operation is very expensive to archive using a full post-back to the server, and an Ajax request will be better in this scenario, but still the question remains valid.

This is the model for the view:

class IndexViewModel
{
    public string Query { get;set; }

    public IList<Person> People { get;set; }
}

And the view:

<form action="home/index">
    <input id="query" name="query"/>
    <input type="submit" value"Add"/>

                Name

            @for (int i = 0; i < Model.People.Count; ++i)
            {

                        @Html.HiddenFor(m=>m.People[i].Id)
                        @Html.ActionLink(Model.People[i].Name, "Details", "Person", new { id = Model.People[i].Id }, null)

                        @Html.ActionLink("Remove", "RemovePerson", "Home", new { id = Model.People[i].Id }, null)

            }

</form>

In the Action I receive the model and get the list of people again from the database and add the new person.

[HttpPost]
public ActionResult Index(IndexViewModel model)
{
    // Here I load again all people in the view and add the new that was queried.
    for (int i = 0; i < model.People.Count; ++i)
        model.People[i] = db.FindById(model.People[i].Id);

    var newPerson = db.FindByName(model.Query);
    if (newPerson != null)
        model.People.Add(newPerson);

    return View(model);
}

When you are iterating over the collection of people, it probably does make sense to keep the hidden fields within the loop. I would try to keep them grouped together in that first td, with a hidden field per line, so that they are easily noticeable when scanning the source.

If I weren't iterating (meaning that I was using some field at the top of my model, not in an array), I generally stuff my hidden inputs immediately following the opening  tag.

When iterating, within the td, a hidden element should have no effect on the rendering. You might consider wrapping them in a  or  with display:none applied. I believe there are some (older) browsers that will render white space if you have line breaks between your hidden inputs.


on() event handler for multiple objects I'm using three instances of ace editor in a form. I initialize them like so:

var before = ace.edit("beforeSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
}),
execute = ace.edit("executeSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
}),
after = ace.edit("afterSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
});

I then put a listener on each one to make sure there's content in each field before the user can click the submit button:

  before.session.on('change', () => {
    toggleSubmit();
  });
  execute.session.on('change', () => {
    toggleSubmit();
  });
  after.session.on('change', () => {
    toggleSubmit();
  });

The toggleSubmit() function enables the submit button when each editor stores a value.

Both sections of code feel redundant, but the second section is what really concerns me. Anyone know a clever way to whittle this down? For example is there a way I could do the following:

[before.session, execute.session, after.session].on('change', () => {
  toggleSubmit();
});

var before = ace.edit("beforeSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
}),
execute = ace.edit("executeSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
}),
after = ace.edit("afterSQL", {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
});

There's a lot of repetition here in terms of the options you're using. You could avoid repeating yourself by creating an object to hold defaults. For example:

const defaults = {
  showPrintMargin: false,
  fontSize: '14px',
  theme: "ace/theme/sqlserver",
  mode: "ace/mode/sql"
}

var before = ace.edit("beforeSQL", {...defaults})
var execute = ace.edit("executeSQL", {...defaults})
var after = ace.edit("afterSQL", {...defaults})

To avoid repeating yourself when adding an event listener you could do something like this:

[before, execute, after].forEach(obj => {
  obj.session.on('change', toggleSubmit);
})


Matching rows between two dataframes I have managed to write this piece of code but as I am using it on big data sets it ends up being quite slow. I am pretty sure it would be possible to optimize it but I am very knew to coding and I don't really know where to start.. I think getting rid of the for loop would be one way but honestly I'm lost. A little bit of help would be greatly appreciated !

Basically, the point is to look if one row of the 'data' dataframe match one row of the 'ref' dataframe. And I use np.isclose in order to allow for small differences in the value as I know my 'data' values can be slightly different than the 'ref' values.

Also, because my rows can have a lot of NaN values in them, I first use np.isnan to get the index of where is my last 'real' value in the row and then only do the row comparison with the 'actual' values. I thought it would speed things up but I'm not very sure it did...

match = []
checklist = set()

for read in data.itertuples():

    for ref in ref.itertuples():

        x = np.isnan(read[3:]).argmax(axis=0)

        if x == 2:
            if np.isclose(read[4:6],ref[7:9],atol=5, equal_nan=True).all() == True and np.isnan(ref[6:]).argmax(axis=0) == x:

                if not read[1] in checklist:
                    match.append([read[1], ref[5]])
                    checklist.add(read[1])

        if x > 2:
            read_pos = 3+x-1
            ref_pos = 6+x-1

            if np.isclose(read[4:read_pos],ref[7:ref_pos],atol=5, equal_nan=True).all() == True and np.isnan(ref[6:]).argmax(axis=0) == x:

                if not read[1] in checklist:
                    match.append([read[1], ref[5]])
                    checklist.add(read[1])

    if read[1] not in checklist:
        match.append([read[1], "not found"])
        checklist.add(read[1])

Thanks in advance !

EDIT:

To download samples of data and ref tables: https://we.tl/RF6lxDZBjt

Short example of the dataframes:

ref = pd.DataFrame({'name':['a-1','a-2','b-1'],
                  'start 1':[100,100,100],
                  'end 1':[200,200,500],
                  'start 2':[300,np.NaN,600],
                  'end 2':[400,np.NaN, 700]},
                   columns=['name', 'start 1', 'end 1', 'start 2', 'end 2'],
                   dtype='float64')

    name  start 1   end 1  start 2  end 2
 0  a-1     100.0   200.0    300.0  400.0
 1  a-2     100.0   200.0      NaN    NaN
 2  b-1     100.0   500.0    600.0  700.0

data = pd.DataFrame({'name':['read 1','read 2','read 3','read 4', 'read 5'],
                  'start 1':[100,102,100,103,600],
                  'end 1':[198,504,500,200, 702],
                  'start 2':[np.NaN,600,650,601, np.NaN],
                  'end 2':[np.NaN,699, 700,702, np.NaN]},
                   columns=['name', 'start 1', 'end 1', 'start 2', 'end 2'],
                   dtype='float64')

    read      start 1   end 1  start 2   end 2
 0  read 1      100.0   200.0    300.0   400.0
 1  read 2      100.0   200.0      NaN     NaN
 2  read 3      100.0   500.0    600.0   700.0
 3  read 4      300.0   400.0    600.0   700.0
 4  read 5      600.0   702.0      NaN     NaN

Invariants

for read in data.itertuples():
    for ref in ref.itertuples():
        x = np.isnan(read[3:]).argmax(axis=0)

x doesn't change in the inner loop, so you can move it out of the inner loop, and not execute it repeatedly.

for read in data.itertuples():
    x = np.isnan(read[3:]).argmax(axis=0)
    for ref in ref.itertuples():

These following two lines are identical, apart for the end-points of the slices:

if np.isclose(read[4:  6     ],ref[7:  9    ],atol=5, equal_nan=True).all() == True and np.isnan(ref[6:]).argmax(axis=0) == x:
if np.isclose(read[4:read_pos],ref[7:ref_pos],atol=5, equal_nan=True).all() == True and np.isnan(ref[6:]).argmax(axis=0) == x:

You already have a variable for the end-points.  Why not use it for the first line as well, and only have one case?

read_pos = 3+x-1 if x > 2 else 6
ref_pos  = 6+x-1 if x > 2 else 9

Once you've found your target, you can't ever add it again ...

if not read[1] in checklist:
   match.append([read[1], ref[5]])
   checklist.add(read[1])

... but you don't break out of your inner search, which is now pointless.

If I haven't made any errors, this should be a litte faster:

match = []
checklist = set()

for read in data.itertuples():

    x = np.isnan(read[3:]).argmax(axis=0)

    if x >= 2  and  read[1] not in checklist:

        read_pos = 3+x-1 if x > 2 else 6
        ref_pos  = 6+x-1 if x > 2 else 9

        for ref in ref.itertuples():

            if np.isclose(read[4:read_pos],ref[7:ref_pos],atol=5, equal_nan=True).all() == True and np.isnan(ref[6:]).argmax(axis=0) == x:
                match.append([read[1], ref[5]])
                checklist.add(read[1])
                break

    if read[1] not in checklist:
        match.append([read[1], "not found"])
        checklist.add(read[1])