Correct way to cover dependencies in unit tests My approach to unit testing feels very wrong. I feel like I am missing something very basic, and I'm looking for some insight please.

Let's assume that I am testing a method (I'm using NUnit) that returns an object. It might look like this:

public void TestConnection()
{
     DBConnector dbConn = new DBConnector(connString);
     Assert.IsInstanceOf(typeof(DBConnector), dbConn);
}

Let's assume too that the test passes.

Later in my test class, I create another test on an object that has a dependency on MyObject. That test method might look like this:

public void IsCallInstanceNull()
{
     DBConnector dbConn = new DBConnector(connString);
     dbConn.EstablishConnection();
     CallInstance ci = new CallInstance(dbConn);
     Assert.IsNotNull(ci);
}

I am first marking TestConnection() "public void", ensuring a basic pass, then changing the method to private so that I can use a typed object in the second method, instead of duplicating code. So my example test class becomes:

private DBConnector CreateDBConnector()
{
     var dbConn = new DBConnector(connString);
     dbConn.EstablishConnection();
     return dbConn;
}

public void IsCallInstanceNull()
{

     CallInstance ci = new CallInstance(CreateDBConnector());
     Assert.IsNotNull(ci);
}

But this feels completely wrong. No one will ever know that the constructor for DBConnector was ever tested (since not only did I change its visibility, I renamed the method!) so  how can this be refactored so that I ensure test coverage for the private method without having to leave 2 almost identical methods in the test class?

When unit testing a class you should focus only on the functionality in that class. For all other dependencies, mocking should be used. That is to say you should create "fake" implementations of the dependencies and use them to simulate the real thing. You can then run tests against the mocks to ensure that they are being used correctly according to the functionality of the class under test.

In order to do this you will have to inject all dependencies(this is pretty much always what you should be doing), likely in your constructor.

Your test example doesn't tell us too much and doesn't test anything. Instantiating a class then validating its type is not a test. Could you provide the class that you would like to test? Then we can give concrete examples.

I wrote a tutorial for using Moq to test dependencies, it can be found here:
http://stevemichael.net/how-do-i-use-moq-with-asp-net-mvc/

Okay so I'll try answer the meta-question about unit testing with dependencies. As others have pointed out, your examples aren't really unit tests, which makes it a little difficult to redo them.

First point. the aim of a unit test is to test some behaviour of the system, in an isolated manner. This is important to keep in mind as not all dependencies are the same, and their nature dictates how you'll handle them.

Some dependencies will be the source of state, some will be the source of domain logic/knowledge and others will be further system behaviour.

So lets take the following code: (Implied is the code to set the fields which hold the dependencies)

public class House {
  private TemperatureSensor thermometer;
  ...
  public bool IsLoungeTooHot() {
    return thermometer.CurrentTemperature > 20;
  }
}

It's a simple class with a single bit of behaviour checking the lounge temperature and a single dependency on a thermometer.

So thermometer is the source of the data and as such it is always faked since the test needs to be able to use multiple temperatures to ensure it works (at the very least return temp below 20 and above 20)

Now if we were to extend the code to

public class House {
  private TemperatureSensor thermometer;
  private Thermostat thermostat;
  ...
  public bool IsLoungeTooHot() {

    return thermometer.CurrentTemperature > thermostat.DesiredTemperature;
  }
}

So we now the desired temperature is no longer a constant but rather retrieved from a domain object. So the thermostat dependency is something that will almost never  be  faked (safe to read never but there can be edge cases). The reason why we don't want to fake this is to protect ourselves against test fragility.

As the writers of the code we could create a perfect fake of the Thermostat. However it would only be perfect at the moment we wrote the test. At some point down the line the behaviour of Thermostat could change, and if we had used a fake there is a very good chance we would not notice.

Third and final extension of the code:

public class House {
  private TemperatureSensor thermometer;
  private Thermostat thermostat;
  private DataRepository repo;
  ...
  public bool IsLoungeTooHot() {
    repo.Audit("IsLoungTooHot");
    return thermometer.CurrentTemperature > thermostat.DesiredTemperature;
  }
}

The repo dependency similar to the thermostat dependency, it is additional system behaviour. However in this specific case we would replace it with a fake because using the real database would break the isolation we need to ensure that this test doesn't affect other tests that may also be running.

A bit of a wall of text, hope it's made things a little clearer.

fake - stub/mock see https://stackoverflow.com/a/346440/5889 for a good explanation of the differences.


Counting number of pairs in an integer array So, I wanted to have the count for number of pairs of same integer there are in an array for which I used a HashMap

Input contains two lines:

  Integer n:

  Signifies the size of input
  Input numbers separated by white space character:
  E.g 4 6 6 7 7 8 7 6 4

For the same input,

  Expected Output:

  3

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class SockMerchant {

    public int[] returnsockArr() {
        Scanner sc = new Scanner(System.in);
        int arraySize = sc.nextInt();
        int[] sockArr = new int[arraySize];
        for(int i = 0;i <= arraySize-1; i++) {
            sockArr[i] = sc.nextInt();
        }
        sc.close();
        return sockArr;
    }

    public int returnCount(Map<String, Object> mapCount) {
        int count = 0;
        for(String keyName : mapCount.keySet()) {
            int value = (int)mapCount.get(keyName);
            count = count+(value/2);
        }
        return count;
    }

    public int setMapAndReturnCount(int[] sockArr) {
        Map<String, Object> mapCount = new HashMap<String, Object>();
        for(int j = 0;j<= sockArr.length-1;j++) {
            if(mapCount.containsKey(Integer.toString(sockArr[j]))) {
                mapCount.put(Integer.toString(sockArr[j]), (int)mapCount.get(Integer.toString(sockArr[j]))+1);
            }
            else {
                mapCount.put(Integer.toString(sockArr[j]), 1);
            }
        }
        return returnCount(mapCount);
    }

    public static void main(String args[]) {
        SockMerchant sm = new SockMerchant();
        int[] sockArr = sm.returnsockArr();
        int finalCount = sm.setMapAndReturnCount(sockArr);
        System.out.println(finalCount);
    }
}

I think that I have complicated the solution a bit too much

Is there a better approach to do the same thing?

There are couple of improvement possible in your code.

In this method setMapAndReturnCount you should change the declaration of map from,

Map<String, Object> mapCount = new HashMap<String, Object>();

to

Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();

As you know, you want to store the input array numbers as key in Map and value is the count of occurence of a particular number in the array.

By using Object class as value in Map, you are defeating one of the main purpose of having generics implementation in Java. If you use Object then you need to uselessly cast, and otherwise don't have to.

Another point in same method, you can write your for loop in a better way like this, instead of your current code which does double work of first checking through containsKey and then uses mapCount.get to again pick the value of key.

public int setMapAndReturnCount(int[] sockArr) {
    Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();
    for (int j = 0; j < sockArr.length; j++) {
        Integer count = mapCount.get(sockArr[j]);
        if (count == null) {
            mapCount.put(sockArr[j], 1);
        } else {
            mapCount.put(sockArr[j], count + 1);
        }
    }
    return returnCount(mapCount);
}

Similarly, you can change returnCount method to this,

public int returnCount(Map<Integer, Integer> mapCount) {
    int count = 0;
    for (Integer value : mapCount.values()) {
        count += (value / 2);
    }
    return count;
}

As you don't need to first iterate on keySet and then retrieve the values with get which will be slower, and instead just iterate it on values as that is what you need for calculating number of pairs, which will be relatively faster.

Also, if you are using Java-8 and above,

You can change your returnCount to one liner like this,

public int returnCount(Map<Integer, Integer> mapCount) {
    return mapCount.values().stream().mapToInt(x -> x / 2).sum();
}

I have tried to simplify your code like this.

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SockMerchant {

    private int[] returnSockArr() {
        Scanner sc = new Scanner(System.in);
        int arraySize = sc.nextInt();
        int[] sockArr = new int[arraySize];
        for(int i = 0;i <= arraySize-1; i++) {
            sockArr[i] = sc.nextInt();
        }
        sc.close();
        return sockArr;
    }

    private int returnCount(int[] sockArr) {
        int count = 0;
        Set<Integer> uniqueElements = new HashSet<>();
        for (int i: sockArr) {
            if(uniqueElements.contains(i)) {
                count ++;
                uniqueElements.remove(i);
            } else {
                uniqueElements.add(i);
            }
        }
        return count;
    }

    public static void main(String args[]) {
        SockMerchant sm = new SockMerchant();
        int[] sockArr = sm.returnsockArr();
        int finalCount = sm.returnCount(sockArr);
        System.out.println(finalCount);
    }
}

I have used your returnSockArr as it is for reading the numbers. Then I have removed setMapAndReturnCount method which uses Map for storing numbers. Instead I am calling returnCount and calculate the number of pairs.

In that method I am putting the number in to a Set if the number is not present in the 'Set'. If number is present the count is incremented and that number is removed from the Set. So count won't be incremented when a number is seen odd times in the list.

And am sure it can be again simplified :)


Finding the mean using RxJava I'm learning RxJava and this is what I attempted to find the mean of 'n' transactions.

List<Transaction> transactions = TransactionsStore.getTransactions();
BigDecimal nTransactions = new BigDecimal(transactions.size());
Observable.from(transactions)
        .map(transaction -> transaction.amount)
        .reduce(BigDecimal::add)
        .map(total -> total.divide(nTransactions, 2, BigDecimal.ROUND_DOWN))
        .map(mean -> String.format("The mean is %s", mean.toPlainString()))
        .subscribe(System.out::println);

I'd like to know if this could be done better.

Using RxJava-Math you can achieve the same result by this way:

List<Transaction> transactions = createRandomTransactions(10);

final Observable<Float> amountStream = Observable.from(transactions)
        .map(transaction -> transaction.amount);

MathObservable.averageFloat(amountStream)
        .map(mean -> String.format(Locale.US, "The mean is %.2f", mean))
        .subscribe(System.out::println);

Hope that helps!


Implementing a HashTable in Objective-C I am trying to implement a hash table in Objective-C.  I did some testing and the implementation seems to work.  I am using an NSMutableArray to store linked lists of entries.  It also resizes when it gets almost full.  I am using an NSString for a key and any object as a value.  I store NSNull objects in an NSMutableArray to be able initialize it to a certain size.

The hash function I copied from the Java HashTable implementation:

#import "YZHashTable.h"
#import "Entry.h"

@interface YZHashTable()

@property (nonatomic,strong) NSMutableArray *tableArray;
@property (nonatomic) NSInteger elementCount;
@end

@implementation YZHashTable

const int HASHTABLECAPACITY=10;
const double HASHTABLELOADFACTOR = 0.75;

-(instancetype)init
{
    self  = [super init];
    if(self){
        [self resizeTableArray];
        _elementCount = 0;
    }

    return self;
}

-(void)resizeTableArray
{
    for(int i = 0; i < HASHTABLECAPACITY; i++){
        [self.tableArray addObject:[NSNull null]];
    }
}

-(NSMutableArray *)tableArray
{
    if(!_tableArray){
        _tableArray = [[NSMutableArray alloc]initWithCapacity:HASHTABLECAPACITY];
    }
    return _tableArray;
}

-(void)setElementCount:(NSInteger)elementCount
{
    if(elementCount < 0) return;
    _elementCount = elementCount;
}

-(void)addObjectForKey:(NSString *)key andValue:(id) value
{
    if(self.elementCount > [self.tableArray count] * HASHTABLELOADFACTOR){
        [self resizeTableArray];
    }
    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    if([[self.tableArray objectAtIndex:keyArrayIndex] isKindOfClass:[NSNull class]]){
        [self.tableArray setObject:[[Entry alloc]initWithKey:key andValue:value] atIndexedSubscript:keyArrayIndex];
    }else{
        Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
        while(root.next && ![root.key isEqualToString:key]){
            root = root.next;
        }
        if([root.key isEqualToString:key]){
            root.value = value;
        }else{
            root.next = [[Entry alloc]initWithKey:key andValue:value];
        }
    }
    self.elementCount++;
}

-(id)getObjectForKey:(NSString  *)key
{
    id value = nil;

    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
    if(![root isKindOfClass:[NSNull class]]){
        while(![root.key isEqualToString:key] || root.next != nil){
            root = root.next;
        }
        if([root.key isEqualToString:key]) value = root.value;
    }

    return value;
}

-(id)removeObjectForKey:(NSString  *)key
{
    id value = nil;

    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
    if(![root isKindOfClass:[NSNull class]]){
        if([root.key isEqualToString:key]){
            if(!root.next){
                [self.tableArray setObject:[NSNull null] atIndexedSubscript:keyArrayIndex];
            }else{
                root = root.next;
            }
            self.elementCount--;
        }else{
            while(root.next && ![root.next.key isEqualToString:key]){
                root = root.next;
            }
            if([root.next.key isEqualToString:key]){
                root.next = root.next.next;
                self.elementCount--;
            }
        }

    }
    return value;
}

-(NSUInteger)count
{
    return self.elementCount;
}

-(NSUInteger)indexForHash:(NSUInteger)hash
{
    hash ^= (hash>>20)^(hash>>12);
    return hash ^ (hash >> 7) ^ (hash >> 4);
}

@end

Use NSHashTable from iOS 6+ SDK.
The hash table is modeled after NSSet with the following differences:

It can hold weak references to its members.
Its members may be copied on input or may use pointer identity for equality and hashing.
It can contain arbitrary pointers (its members are not constrained to being objects).

Example usage:

 NSHashTable *hashTable = [NSHashTable
 hashTableWithOptions:NSPointerFunctionsCopyIn];
 [hashTable addObject:@"foo"];
 [hashTable addObject:@"bar"];
 [hashTable addObject:@100];
 [hashTable removeObject:@"bar"];
 NSLog(@"Members: %@", [hashTable allObjects]);


Python program to remove invalid parentheses This is a Leetcode problem -

  Remove the minimum number of invalid parentheses in order to make the
  input string valid. Return all possible results.

  Note -

  The input string may contain letters other than the parentheses (
  and ).

Here is my solution to this challenge -

def remove_invalid_parentheses(s):

    removed = 0
    results = {s}
    count = {"(": 0, ")": 0}
    for i, c in enumerate(s):
        if c == ")" and count["("] == count[")"]:
            new_results = set()
            while results:
                result = results.pop()
                for j in range(i - removed + 1):
                    if result[j] == ")":
                        new_results.add(result[:j] + result[j + 1:])
            results = new_results
            removed += 1
        else:
            if c in count:
                count[c] += 1
    count = {"(": 0, ")": 0}
    i = len(s)
    ll = len(s) - removed
    for ii in range(ll - 1, -1, -1):
        i-=1
        c = s[i]
        if c == "(" and count["("] == count[")"]:
            new_results = set()
            while results:
                result = results.pop()
                for j in range(ii, ll):
                    if result[j] == "(":
                        new_results.add(result[:j] + result[j + 1:])
            results = new_results
            ll -= 1
        else:
            if c in count:
                count[c] += 1
    return list(results)

Explanation -

Scan from left to right, make sure count["("] >= count[")"].
Then scan from right to left, make sure count["("] <= count[")"].

Here are some inputs/outputs -

print(remove_invalid_parentheses("()())()"))
>>> ["()()()", "(())()"]

print(remove_invalid_parentheses("(a)())()"))
>>> ["(a)()()", "(a())()"]

print(remove_invalid_parentheses(")("))
>>> [""]

Here are the times taken for each output -

%timeit remove_invalid_parentheses("()())()")
6.54 µs ± 176 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit remove_invalid_parentheses("(a)())()")
8.43 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit remove_invalid_parentheses(")(")
3.69 µs ± 67.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Test, consistent behavior & data structure

Trying to add tests for the code based on the example of input/output provided led to the following result: the behavior is not consistent : in particular the order of the elements in the returned list is not always the same.

The root cause for this is that we are using sets in the logic only to convert to list at the end.

A solution would be to return sorted(results) at the end. An alternative would be to just return a set instead of trying to convert to list.

Then, we get the following automated tests:

print(remove_invalid_parentheses("()())()") == {"(())()", "()()()"})
print(remove_invalid_parentheses("(a)())()") == {"(a())()", "(a)()()"})
print(remove_invalid_parentheses(")(") == {""})

It would make sense to try to rewrite it as unit-tests using a proper unit-test framework but I will stop here as this is enough for me to keep working.

More explicit loop

I tend to find loops based on for ii in range(ll - 1, -1, -1) very error-prone/hard to understand because of the number of tweaks on both sides of the range. I'd suggest a much more explicit alternative: for ii in reversed(range(ll)):.

Similar indices

As ii will go over ]ll, 0] which is ]len(s) - removed, 0], i will go over ]len(s), removed].

The difference between the indices is always removed, we have ii + removed == i: we can get rid of the i variable. We can take this chance to rename ii into i.

At this stage, we have:

def remove_invalid_parentheses(s):
    removed = 0
    results = {s}
    count = {"(": 0, ")": 0}
    for i, c in enumerate(s):
        if c == ")" and count["("] == count[")"]:
            new_results = set()
            while results:
                result = results.pop()
                for j in range(i - removed + 1):
                    if result[j] == ")":
                        new_results.add(result[:j] + result[j + 1:])
            results = new_results
            removed += 1
        elif c in count:
                count[c] += 1
    count = {"(": 0, ")": 0}
    ll = len(s) - removed
    for i in reversed(range(ll)):
        c = s[i + removed]
        if c == "(" and count["("] == count[")"]:
            new_results = set()
            while results:
                result = results.pop()
                for j in range(i, ll):
                    if result[j] == "(":
                        new_results.add(result[:j] + result[j + 1:])
            results = new_results
            ll -= 1
        elif c in count:
                count[c] += 1
    return results

print(remove_invalid_parentheses("()())()") == {"(())()", "()()()"})
print(remove_invalid_parentheses("()())))()") == {"(())()", "()()()"})
print(remove_invalid_parentheses("(a)())()") == {"(a())()", "(a)()()"})
print(remove_invalid_parentheses(")(") == {""})

(I took this chance to add a new test case)

More explicit loop again

We want to iterate in reversed order over the beginning of the s string. Here again, we can try to make things more explicit and remove some computation as we go:

    for i, c in enumerate(reversed(s[removed:])):
        if c == "(" and count["("] == count[")"]:
            new_results = set()
            while results:
                result = results.pop()
                for j in range(len(s) - i - removed - 1, ll):
                    if result[j] == "(":
                        new_results.add(result[:j] + result[j + 1:])
            results = new_results
            ll -= 1
        elif c in count:
                count[c] += 1

In order to test this more throughly, I took this chance to add the following test case:

print(remove_invalid_parentheses("((((((((()(") == {"()"})

More beautiful loops

Instead of using a combination of while and pop to iterate over the elements of a set, you can just use for:

        for result in results:

Work in progress: I have to go. I may continue in the future.

> s = '()())()'
>
>
> def set_par(s):
>     d = {}
>     updated_s = ''
>     counter_1 = 0
>     counter_2 = 0
>     for i in list(s):
>         if i == '(':
>             counter_1 += 1
>             if counter_1 - counter_2 == 1:
>                 updated_s = updated_s + i
>             else:
>                 counter_1 = counter_1 - 1
>         elif i == ')':
>             counter_2 += 1
>             if counter_1 == counter_2:
>                 updated_s = updated_s + i
>             elif counter_2 > counter_1:`enter code here`
>                 counter_2 = counter_2 - 1
>
>     print updated_s


Hackerrank : Hash Tables: Ransom Note I just solved the Hash Tables: Ransom Note problem on Hackerrank using both Java-8 and Java-7.  Given m words in a magazine and the n words in the ransom note, print Yes if a kidnapper can replicate his ransom note exactly (case-sensitive) using whole words from the magazine; otherwise, print No.  1 ≤ m, n ≤ 30000.

I am looking for suggestions regarding the efficiency, coding style and if this is the best way to solve this kind of problem.

Java-7

public class RansomeNotesJava7 {

    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(new File("input.txt"));
        int m = in.nextInt();
        int n = in.nextInt();
        String magazine[] = new String[m];
        for(int magazine_i=0; magazine_i < m; magazine_i++){
            magazine[magazine_i] = in.next();
        }
        String ransom[] = new String[n];
        for(int ransom_i=0; ransom_i < n; ransom_i++){
            ransom[ransom_i] = in.next();
        }

        if(getRansom(m,n,magazine,ransom))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    private static boolean getRansom(int m, int n, String[] magazine, String[] ransom) {

        if(m < n)
            return false;

        Map<String, Long> magazineMap = getFrequencyMapFromArray(magazine); //Arrays.stream(magazine).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        Map<String, Long> ransomMap =  getFrequencyMapFromArray(ransom); //Arrays.stream(ransom).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        System.out.println(magazineMap);
        System.out.println(ransomMap);

        for(String key : ransomMap.keySet()){
            if(!magazineMap.containsKey(key))
                return false;

            if(magazineMap.get(key) < ransomMap.get(key))
                return false;
        }

        return true;

    }

    private static Map<String, Long> getFrequencyMapFromArray(String[] arr) {

        Map<String, Long> map = new HashMap<>();

        for(String key : arr){
            if(map.containsKey(key))
                map.put(key, map.get(key)+1);
            else
                map.put(key, new Long("1"));
        }
        return map;
    }
}

Java-8

public class RansomNotes {

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new File("input.txt"));
        int m = in.nextInt();
        int n = in.nextInt();
        String magazine[] = new String[m];
        for (int magazine_i = 0; magazine_i < m; magazine_i++) {
            magazine[magazine_i] = in.next();
        }
        String ransom[] = new String[n];
        for (int ransom_i = 0; ransom_i < n; ransom_i++) {
            ransom[ransom_i] = in.next();
        }

        if (getRansom(m, n, magazine, ransom))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    private static boolean getRansom(int m, int n, String[] magazine, String[] ransom) {

        if (m < n)
            return false;

        Map<String, Long> magazineMap = getFrequencyMapFromArray(magazine);
        Map<String, Long> ransomMap = getFrequencyMapFromArray(ransom);
        System.out.println(magazineMap);
        System.out.println(ransomMap);

        return (ransomMap.entrySet().stream()
                .filter(i -> (!magazineMap.containsKey(i.getKey()) || magazineMap.get(i.getKey()) < i.getValue()))
                .count() == 0);

    }

    private static Map<String, Long> getFrequencyMapFromArray(String[] arr) {

        return Arrays.stream(arr)
                     .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }

}

Coding style

Overall looks good. I only got some small remarks:

Put {} after each if and else as well. This is mostly to prevent stupid bugs if you (or someone after you) adds an innocent looking line like this:

 for(String key : ransomMap.keySet()){
    if(!magazineMap.containsKey(key))
        System.out.println("Not enough of: " + key);
        return false;  //<- this false is actually outside the if block now.

    if(magazineMap.get(key) < ransomMap.get(key))
        return false;
}

Suddenly it always returns false, even tho we just wanted to print which key wasn't found. Most IDE's can be set up to always place the braces for you.

A minor thing is also the name for magazineMap. I would rename this to magazineFrequencyMap to make it clear that it's a frequency map (like your great method name says to populate the map). But since that might feel a little long later on you'll have to decide for yourself what feels better.

The last thing is that you never close your Scanner. Since this is in your main method and your program ends after execusion it doesn't really matter much, but since we're talking best practices here I couldn't ignore this.

Efficiency

Why store the number of words in a Long if there's at most 30k of them? An Integer should do:

Map<String, Integer> magazineMap = getFrequencyMapFromArray(magazine);

A major change to gain efficiency is to never build the frequency map for the ransom notes. Instead use the following strategy to solve the problem:

Put all the magazine words into a map like you did now.
Try to take each ransom word out of that bag while reading them from the file.
If it's not in the bag (or count is 0) you can stop here and return false

If you are "lucky" and the first ransom word is not present in your magazines you can stop early. This can save "a lot" of time counting the other ransom words. (Note that "a lot" means a couple of miliseconds probably, so it doesn't really matter that much for this problem).

the best way

I would argue that there is no best way to solve a computer problem. Only a better way given certain criterea.

For the given problem I would argue that my "take ransom words out of the existing bag as we go" is better since it's more memory efficient and fails faster.

If, however, we want to expand this problem later to:

  Given a stack of magazines, which of these magazines can be used to write the ransom note?

Then it makes a lot more sense to read the ransom note once and put them into their own frequency map. Because we can use this map to compare with each of the magazine frequency maps like you did in your solution.

I solved it this way - I modified main method that hacker rank provided to not read all inputs for ransom note or store it - but break early if mismatch  is found.

Also, there is no need to store magazine words in a String[], you can directly build map while reading input.

import java.util.*;

public class RansomNote {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();

        boolean flag = true;

        Map<String,Long> magazineMap = new HashMap<>();
        for(int magazine_i=0; magazine_i < m; magazine_i++){
            magazineMap.merge(in.next(), 1L, Long::sum);
        }

        //Prepared only one map of magazines & not ransom words to to have memory efficiency
        // Ransom note stoarge is not needed

        for(int ransom_i=0; ransom_i < n; ransom_i++){
            String ransomWord = in.next();

            if(!magazineMap.containsKey(ransomWord) || magazineMap.get(ransomWord) == 0) {
                flag = false;
                break;
            }else {
                Long newfrequency = magazineMap.get(ransomWord).longValue()-1L;
                magazineMap.put(ransomWord, newfrequency);
            }
        }

        if(flag)
            System.out.println("Yes");
        else
            System.out.println("No");

        in.close();

    }
}


Accurate sum of a range object in O(1) I recently created a function calculating the sum of an arbitrary range object in \$O(1)\$:

def sum_of_range(range_obj):
    """Calculates the sum of a range object (Python 3) in O(1).

    This function always returns a python integer representing the sum
    without loss of precision (as would happen if it uses intermediate
    floating point values).
    """
    start, stop, step = range_obj.start, range_obj.stop, range_obj.step
    len_ = len(range_obj)
    if step > 0:
        if start >= stop:
            return 0
        # Find the last "really" included number. Subtract one from stop
        # because the stop is not included in ranges.
        upper = (stop - 1 - start) // step * step + start
    else:
        if stop >= start:
            return 0
        # In case the step is negative we need to add one to the difference
        # instead of subtracting one.
        upper = (stop - start + 1) // step * step + start
    sum_first_and_last = upper + start
    return (sum_first_and_last * len_) // 2

I used "random" tests to verify that it works:

import random

for i in range(100000):  # make a lot of random tests
    up = random.randint(-10000, 10000)
    lo = random.randint(-10000, 10000)
    step = random.randint(-25, 25)
    if step == 0:  # steps of zero are not possible
        continue
    rg = range(lo, up, step)
    assert sum_of_range(rg) == sum(rg)

Is there any room for improvement? Especially (but not only):

Code readability
Code performance
Should I replace the random tests with explicit tests or can I neglect explicit tests? Or should I include both?

Let's get a closer look at the sum you're trying to calculate:

$$start + (start+step) + (start+2 \times{}step) + \ldots + (start + (len-1)\times{} step)$$

Which can be reordered as:

$$start + \ldots + start + step + 2\times{}step + \ldots + (len-1)\times{}step$$

Which gives you a nice formula regardless of the sign of start or step or even the value of stop:

$$start \times{} len + step \times\frac{len(len-1)}{2}$$

All the complexity being hidden in the len(range_obj) call. So you can just write:

def sum_of_range(range_obj):
    """Calculates the sum of a range object (Python 3) in O(1).

    This function always returns a python integer representing the sum
    without loss of precision (as would happen if it uses intermediate
    floating point values).
    """

    length = len(range_obj)
    step_counts = length * (length - 1) // 2
    return range_obj.start * length + range_obj.step * step_counts

range_obj is not a container, and you cannot rely on len(range_obj) being \$O(1)\$. A simple experiment

$ python -mtimeit "len(range(10))"
10000000 loops, best of 3: 0.158 usec per loop

$ python -mtimeit "len(range(10000000))"
10 loops, best of 3: 188 msec per loop

shows that it is in fact linear.

The bright side is that you don't need len at all. You need a number of elements, and even though it is numerically equal to len, it can (and should) be computed as

    len_ = (obj.stop - obj.start) // obj.step


Remove parameters from string containing URL Is this the best way to remove URL parameters from a string containing an URL?

$url = "http://www.test.com/test.html?parameter=hey&parameter2=ho";
if (strstr($url, "?")) {
   $url = strstr($url, "?", true);
}

Is there a better one-line solution? It seems so bad to run the same function twice.

The simplest way, a true one-liner, would be to use strtok, an ancient but for some reason obscure function that does exactly what you need:

$url = "http://www.test.com/test.html?parameter=hey&parameter2=ho";
$url = strtok($url, "?");

it will give you the part before the token if it is found, or the whole string otherwise

$url = 'http://www.test.com/test.html?parameter=hey&parameter2=ho';
if ( $temp = strstr($url, '?', true) ) {
   $url = $temp;
}

If you just want to get rid of the second call, you can save the value in a variable.  If it exists, do the assignment.  If not, don't.

In PHP, if you don't need to do string interpolation (variables embedded in strings), you can just use single quotes.  This is slightly faster and can help avoid bugs where you accidentally interpret something as a variable that was meant to be a literal $.

Note:  there may be better overall solutions, but with so little context, it is hard to see them.  For example, you don't say how you get this URL.  Or what you're going to do with it.  There might be better changes in one of those places.


JavaScript filter() on JSON object? I'm building a web interface for a home monitoring sensor array, and fetching JSON from the backend framework. I want to start putting statistics together for monitoring different areas of the home, inside and outside.

Each thermal sensor provide the reading, in regular intervals, of temperature and time of day, so I end up with a JSON object looking like this:

{
"sensor_1" :    [
    {
    "location" : "garage_east",
    "temp_f" :  [{
                    "value" : "71.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "70.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "72.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }
        ]}],

"sensor_2" : [{
    "location" : "kitchen",
    "temp_f" : [{
                    "value" : "78.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "78.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "78.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }]
}]}

and so on, with multiple sensors each displaying pretty large JSON objects for the reporting periods.

I want to derive the highest and lowest temperatures around the house, and at what time they occurred, using JavaScript (with AngularJS). Currently, I'm looking to optimize this (which does work):

/* The entire array of data, within time frame set by the user
*   and for the sensors defined by the user
*   from the RESTful API (params)
*/

api.sensor_data.get(params, function(data){

  $scope.sensorStats = {
    "kitchen" : {},
    "garage" : {}
  }
  /* find the highest temperature for a single sensor */
  let hightemp_kitchen = Math.max.apply(Math, data.sensor_1.temp_f.map(function(t){
        return t.value;
  }));
  /* grab the associated timestamp and put them both into an object */
  $scope.sensorStats.kitchen.high = data.sensor_1.temp_f.find(function(obj){
      return obj.value == hightemp_kitchen;
  });
  /* Repeat for each sensor of concern (user defined in params) */
  etc...
 });
}, ...

and then I use the in the DOM the expression {{ sensorStats.kitchen.high }} to display the high temp and date/time to the user for the kitchen.

Like I say, this works, but I'm doing this for each of the 15+ sensors in the array around the property. This method not the easiest to read and maintain - I think it can be faster and more efficient to maintain, but I don't have the lexicon to know what to research.

Is this efficient? Is there a "better" or more efficient way to filter out the data and return the temp and time? I'm reading up on ES6, and discovered the filter() method, but it seems to be useful only on arrays and not objects.

It seems like you should not be hard-coding concepts such as "kitchen", "garage", etc. into your code at all. You need to design that out.

Also I question the JSON structure.  sensor_* are meaningless property names, giving you an unnecessary level of nesting, so if you have control over JSON generation, you might consider an array of object like:

[
    {
        "location": ...,
        "temp_f": [
            ...
        ]
    },
    {
        ...
    }
]

But let's assume you can't do that, and think of ways we can get you the information make this whole thing more dynamic. I am not sure what params is even used for, so I am discarding this.

api.sensor_data.get(function(data){
    let sensorData = {};
    // loop through each sensoer object, ignore top level key value
    Object.values(data).forEach( (sensor) => {
        // reduce f_temp array to single entry with highest temp
        // and set to sensorData result object with location as key
        sensorData[sensor.location] = sensor.f_temp.reduce( (acc, metric) => {
            if(parseFloat(metric.value) > parseFloat(acc.value)) acc = metric;
            return acc;
        }, sensor.f_temp[0]);
    });

    $scope.sensorStats = sensorData;
}

Based on your comment regarding params, you might have something more like this:

    let sensorData = {};

    let sensors = Object.values(data);
    // filter by location
    if (location in params) {
        sensors = sensors.filter( (sensor) => sensor.location === params.location );
    }
    // loop through each sensor objects
    sensors.forEach( (sensor) => {
        let result = null;
        let metrics = sensor.f_temp;
        if(minTimestamp in params) {
            metrics = metrics.filter( metric => {
                return (Date.parse(metric.timestamp) >= params.minTimeStamp );
            });
        }
        if(maxTimestamp in params) {
            metrics = metrics.filter( metric => {
                return (Date.parse(metric.timestamp) =< params.maxTimeStamp );
            });
        }
        if(metrics.length > 0) {
        result = metrics.reduce( (acc, metric) => {
            if(parseFloat(metric.value) > parseFloat(acc.value)) acc = metric;
            return acc;
        }, metrics[0]);
       sensorData[sensor.location] = result;
    });

    $scope.sensorStats = sensorData;
}

The solution depends on the desired output format. My example:

const a = {
"sensor_1" :    [
    {
    "location" : "garage_east",
    "temp_f" :  [{
                    "value" : "71.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "70.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "72.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }
        ]}],

"sensor_2" : [{
    "location" : "kitchen",
    "temp_f" : [{
                    "value" : "78.2",
                    "timestamp" : "2017-05-01T08:15:00"
                },
                {
                    "value" : "78.8",
                    "timestamp" : "2017-05-01T08:30:00"
                },
                {
                    "value" : "78.6",
                    "timestamp" : "2017-05-01T08:45:00"
                }]
}]}

const b = Object.keys(a)
  .map(k => {
    const key = a[k][0].location;
    const value = a[k][0].temp_f.sort((a, b) => a.value - b.value).pop();
    return { [key]: value }
  })

console.log(JSON.stringify(b, null, 2))


Hacker rank - Left rotation - PHP code feedback Here is the problem description - https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem

  A left rotation operation on an array of size \$n\$ shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array \$[1,2,3,4,5]\$, then the array would become \$[3,4,5,1,2]\$.

  Given an array of \$n\$ integers and a number, \$d\$, perform \$d\$ left rotations on the array. Then print the updated array as a single line of space-separated integers.

I wanted to get some feedback on my solution for this problem, it's a task in the Hackerrank Cracking the Coding Interview series.
I am pretty sure the code is working fine, as it passes 7 of the 9 test cases, but is getting timed-out for the last two cases, since these cases are unknown, I wanted to get some expert feedback, as how can I optimize this code.

<?php
    //$handle = fopen ("input_leftR.txt","r");
    $handle = fopen ("php://stdin","r");
    fscanf($handle,"%d %d",$n,$k); //n and k values are available from here
    $a_temp = fgets($handle);
    $a = explode(" ",$a_temp);
    array_walk($a,'intval');

    //My Code from below
    $i; $j; $temp;
    if($n<0 || $n>1000000 || $k<0|| $k>1000000 || count($a) <=0)
        exit;
    for($i=0; $i<$k%$n; $i++){
    //for($i=0; $i<$k; $i++){
        for($j=0; $j<$n-1; $j++){
            $temp = $a[$j];
            $a[$j] = $a[$j+1];
            $a[$j+1] = $temp;
        }
    }
    //array_walk($a,'intval');
    //print implode(" ", $a);
    /*foreach($a as $key=>$value){
        printf("%d", $value);
        if($key<$n-1)
            printf(" ");
    }*/

    for($i=0;$i<$n;$i++){
    printf("%d", $a[$i]);

    if($i<$n-1)
        printf(" ");
    }
?>

Performance

Shifting the content of an array is a very expensive operation.
Lot's of assignments.

Realize that you don't really need to shift the content.
You can shift an offset index,
and use that shifted offset to print the desired output:

for ($i = 0; $i < $n; $i++) {
    $shifted = ($i + $k) % $n;
    printf("%d", $a[$shifted]);

    if ($i < $n-1) printf(" ");
}

Unnecessary statements

This is unnecessary, it serves no purpose at all, you can safely delete it:

$i; $j; $temp;

Input validation

Although input validation is a good practice,
in an online challenge you can trust that the input will be in the described format, and all values will be within the described ranges.
I haven't seen an exception to that yet.
So you don't need this kind of code:

if($n<0 || $n>1000000 || $k<0|| $k>1000000 || count($a) <=0)
    exit;

Formatting

The code is very poorly formatted:

Indentation is inconsistent
No spaces between operators make it look extremely compact and hard to read

Try to follow the writing style of the snippet in my first point.

function rotateLeft($d, $arr) {
  if($d > 0){
      $d--;
      $num = count($arr);
      $k = $arr[0];

      foreach($arr as $key => $val){

         if($key == $num-1){
          $arr[$key] = $k;
         }else{
          $arr[$key] = $arr[$key+1];
         }

      }

      echo "<pre>";print_r($arr);echo "</pre>";
      rotateLeft($d, $arr);
  }

}

$arr = [1,2,3,4,5];

$d = 4;
rotateLeft($d, $arr);


Same method to export different txt files C# I have a basic method to export files, however I have several arrays to export and I need the files to have these names, I'm trying to make it by the enum list, however when I do it, the file isn't created and I'm wondering is there a way to combine the directory+name of array+.txt? Here's method that doesn't export nothing at all. Thank you for looking at the code.

enum exportByName { Client, Appointment, Address,Location,Historic }

        static string askPath()
        {
            var dir = "";

            do
            {
                Console.Clear();
                Console.Write("Insert path to export the txt file: ");
                dir = Console.ReadLine();
            } while (String.IsNullOrEmpty(dir));

            var userPath = Path.Combine(dir,Enum.GetName(typeof(exportByName),0),".txt");
            return userPath;
        }

I don't have much reputations to comment so trying to help for what I know and modified your code according to the need -

There are two issues I observed -

The below line in your code -

  var userPath = Path.Combine(dir,Enum.GetName(typeof(exportByName),0),".txt");

will generate the output "directory+name of array\.txt" instead of
  "directory+name of array+.txt"

You mentioned the point saying "the file is not created", actually your code
is just returning the path using Path.Combine you need to create file for each of the ENUM values using the File.WriteAllText method.

I have modified your code and placed below. Please check

class Program
    {
        enum exportByName { Client, Appointment, Address, Location, Historic }

        static string askPath(int count)
        {
            var dir = "";

            do
            {
                Console.Clear();
                Console.Write("Insert path to export the txt file: ");
                dir = Console.ReadLine();
            } while (String.IsNullOrEmpty(dir));

            var userPath = Path.Combine(dir, Path.GetFileName((Enum.GetName(typeof(exportByName), count))) + ".txt");
            return userPath;
        }
        static void Main(string[] args)
        {

            for (int i = 0; i < 4; i++)
            {
                var path = askPath(i);
                if (!File.Exists(path))  // if it doesn't exist, create

                    File.WriteAllText(path, "add text here");
            }
        }

    }

Hope this helps!


Subdividing a 4×4 array into four 2×2 arrays I want to subdivide a 4×4 2d array into 4 2×2 arrays and I have figured out how to do this in a very crude way, but am having a tougher time with a more elegant general solution.

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                int j2 = j;
                int k2 = k;
                if (i == 1) { k2 += 2; }
                if (i == 2) { j2 += 2; }
                if (i == 3) { j2 += 2; k2 += 2; }
                twoByTwo[i][j, k] = fourByFour[j2, k2];
            }
        }
    }

Flatten and copy array values

You can flatten your fourByFour array and then populate the twoByTwo array:

private static object convertArray1()
{
    int[,] fourByFour = new int[,]{
                        {1,2,3,4 },
                        {12,13,14,15 },
                        {21,22,23,24 },
                        {31,32,33,34 } };

    int[] arrayElems = new int[fourByFour.GetLength(0) * fourByFour.GetLength(1)];

    Buffer.BlockCopy(fourByFour, 0, arrayElems, 0, arrayElems.Length * sizeof(int));

    int[][,] twoByTwo = new int[4][,];

    int elemIndex = 0;
    for (int i = 0; i < twoByTwo.GetLength(0); i++)
    {
        twoByTwo[i] = new int[2, 2];

        for (int j = 0; j < twoByTwo[i].GetLength(0); j++)
        {
            for (int k = 0; k < twoByTwo[i].GetLength(1); k++)
            {
                twoByTwo[i][j, k] = arrayElems[elemIndex];
                elemIndex++;
            }
        }
    }

    return twoByTwo;
}

This solution has a performance penalty - Buffer.BlockCopy copies the source array fourByFour an extra time (which will also require additional memory).

Dimension counter class

Use a helper class to keep track of and increment index positions in each dimension.

This solution is more generic.

private static object convertArray2()
{
    int[,] fourByFour = new int[,]{
                        {1,2,3,4 },
                        {12,13,14,15 },
                        {21,22,23,24 },
                        {31,32,33,34 } };

    DimensionCounter dim1 = new DimensionCounter(4, 4);
    DimensionCounter dim2 = new DimensionCounter(4, 2, 2);

    int[][,] twoByTwo = new int[4][,];

    for (int i = 0; i < dim1.Capacity; i++)
    {
        int val = (int)fourByFour.GetValue(dim1.Current);

        if (twoByTwo[dim2.Current[0]] == null)
        {
            twoByTwo[dim2.Current[0]] = new int[dim2.DimensionSizes[1], dim2.DimensionSizes[2]];
        }

        twoByTwo[dim2.Current[0]][dim2.Current[1], dim2.Current[2]] = val;

        if (i + 1 < dim1.Capacity)
        {
            dim1.Next();
            dim2.Next();
        }
    }

    return twoByTwo;
}

private class DimensionCounter
{
    private readonly int[] dimSizes;
    private readonly int capacity;

    private int[] dimIndexes;
    private int position;

    public int[] DimensionSizes { get { return dimSizes; } }
    public int[] Current
    {
        get { return dimIndexes; }
    }
    public int Position { get { return position; } }
    public int Capacity { get { return capacity; } }
    public DimensionCounter(params int[] dimSizes)
    {
        this.dimSizes = dimSizes;
        this.capacity = dimSizes.Aggregate(1, (a, b) => a * b);
        this.dimIndexes = new int[this.dimSizes.Length];
    }

    public int[] Next()
    {
        for (int i = dimIndexes.Length - 1; i >= 0; i--)
        {
            if (dimIndexes[i] < dimSizes[i] - 1)
            {
                dimIndexes[i]++;
                break;
            }
            else
            {
                for (int j = i; j < dimIndexes.Length; j++)
                {
                    dimIndexes[j] = 0;
                }

                if (i == 0)
                {
                    throw new IndexOutOfRangeException("Cannot increment indexes any more!");
                }
            }
        }
        position++;
        return dimIndexes;
    }

    public void Reset()
    {
        dimIndexes = new int[dimIndexes.Length];
        position = 0;
    }
}


A* pathfinding algorithm too slow I'm trying to make a pathfinding algorithm for my project. I need it for a simulation and I need it to be fast!!!

I watched a few videos explaining the algorithm online and came up with the code below.

However, the performance varies a lot considering the start/finish points.
My project should have grids that go upwards of 500x500

A very slow example is the following, with a very small grid:

I have no idea what's making the algorithm so slow

Dir_Map = {
    "1": (1, 0),
    "2": (0, 1),
    "3": (-1, 0),
    "4": (0, -1),
    "5": (1, 1),
    "6": (-1, -1),
    "7": (1, -1),
    "8": (-1, 1)
}

class Node():
    def __init__(self, pos):
        self.x = pos[0]
        self.y = pos[1]
        self.g = 0
        self.h = 0
        self.f = 0
        self.beggining = 1
        self.parent = None

    def update(self, final):
        self.h = manhattan(self, final)
        self.f = self.f +  self.g

class Child(Node):
    def __init__(self, x, y, parent):
        Node.__init__(self, (parent.x + x, parent.y + y))
        self.g = abs(x) + abs(y) + parent.g
        self.beggining = 0
        self.came_from = (parent.x, parent.y)
        self.parent = parent

def sortbyF(node):
    return node.f

def manhattan(current, final):
    return abs(current.x - final.x) + abs(current.y - final.y)

def check_List(list, successor):
    for ind, val in enumerate(list):
            if (val.x, val.y) == (successor.x, successor.y):
                if val.f < successor.f:
                    return 1
    return 0

openlist = []
closedlist = []

def recursion(node):
    if node.beggining is 0:
        closedlist.append(node.came_from)
        recursion(node.parent)

def pfind(grid, start, finish):

    start_node = Node((start[0], start[1]))
    finish_node = Node((finish[0], finish[1]))
    Stop = 0
    openlist.append(start_node)

    while len(openlist) is not 0:
        current = openlist.pop(0)

        for dirs in Dir_Map.values():
            suc = Child(dirs[0], dirs[1], current)

            if grid[suc.x][suc.y] is not 1 and suc.x <= len(grid[:][1]) and suc.y <= len(grid[1][:]):
                suc.update(finish_node)

                if (suc.x, suc.y) == finish:
                    #Added so it adds the last step.
                    #New suc.came_from = finish
                    suc = Child(dirs[0], dirs[1], suc)
                    #retrace the path.
                    recursion(suc)
                    closedlist.reverse()
                    return closedlist

                if check_List(openlist, suc):
                    continue

                openlist.append(suc)

            else:
                 continue

        openlist.sort(key=sortbyF)

    return None

grid = [[0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

print(pfind(grid, (0,0), (4,3)))

There is some reasonable general algorithmic and python-specific advice here.

The lesson that needs to precede everything is, until you know where you're spending your time, you can't work out how to speed things up. It's well worth learning to use python's cProfile or another profiling tool.

Here's a run with the profiler of your example.

C:\Users\Josiah\Desktop>python -m cProfile -s cumtime astar.py
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]
         6911416 function calls (6911411 primitive calls) in 8.103 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    8.103    8.103 {built-in method builtins.exec}
        1    0.000    0.000    8.103    8.103 astar.py:2(<module>)
        1    0.042    0.042    8.102    8.102 astar.py:59(pfind)
    15538    6.918    0.000    6.918    0.000 astar.py:43(check_List)
     2082    0.645    0.000    1.087    0.001 {method 'sort' of 'list' objects}
  6719169    0.442    0.000    0.442    0.000 astar.py:37(sortbyF)
    16658    0.019    0.000    0.031    0.000 astar.py:28(__init__)
    15539    0.008    0.000    0.018    0.000 astar.py:22(update)
    16660    0.010    0.000    0.010    0.000 astar.py:13(__init__)
    15539    0.008    0.000    0.010    0.000 astar.py:40(manhattan)
    64394    0.004    0.000    0.004    0.000 {built-in method builtins.abs}
    33161    0.003    0.000    0.003    0.000 {built-in method builtins.len}
     2083    0.002    0.000    0.002    0.000 {method 'pop' of 'list' objects}
     8494    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
     2083    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.__build_class__}
      6/1    0.000    0.000    0.000    0.000 astar.py:53(recursion)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 astar.py:12(Node)
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
        1    0.000    0.000    0.000    0.000 astar.py:27(Child)

cumtime is the amount of time spent in a function and all functions it calls.
tottime is the amount of time just spent in the function.

What you can see is that the whole run takes 8.1 seconds, and 6.9 of those are spent directly inside check_List. That's 85% of the whole program's runtime, and basically the only place that's worth optimising. After all, even if you got everything else to take no time at all, you'd only reduce your runtime by 15%. Your only options are call check_List less or make it faster.

The purpose of check_List is to determine whether successor is the fastest way seen thus far to get to wherever successor goes to. You've done that by looping over a list. It would be faster to maintain and check a dictionary of all the places you've seen thus far.

That is, change check_list to check_dict

def check_dict(openDict, successor):
    if (successor.x, successor.y) in openDict:
        return openDict[(successor.x, successor.y)].f < successor.f
    return False

and instead of

            if check_List(openlist, suc):
                continue

            openlist.append(suc)

You'd want

            if check_Dict(openDict, suc):
                continue

            openlist.append(suc)
            openDict[(suc.x, suc.y)] = suc

My variation, which changes nothing except replacing check_list with check_dict as above, runs in 0.025 seconds instead of 8.1.

You might notice that that is significantly better than an 85% speed up, which seems odd because 15% of the run time wasn't actually in check_list at all.

As it happens, my variation fixes a subtle bug that I didn't see initially. As above, check_list is meant to prevent you from revisiting nodes that you've already found a way to. It does that by exhaustively checking all the nodes that you are currently considering for a next step. However, that's not the same! Because of current = openlist.pop(0) there are some entries that you have found routes to, but are no longer part of openlist! Because you don't have any indicator to avoid going back to them, you bounce back and forth among your early nodes.

Patching that bug by separately storing each node you pop off into current and searching them as well in check_list gets almost as good performance as using the dictionary. Well, it doesn't. It takes 0.125 seconds on my machine, which is a whole five times slower than the dictionary, and liable to get worse as the graph gets bigger. But it's a good sight better than 8 seconds!

Since you want to go for performance and your environment is tightly constrained in terms of which nodes are neighbors, you should not use a generic graph structure. E.g. you can use a grid to store the costs of each of the nodes you have computed, as well as a similar grid to store a reference or whatever to the parent of each node.

Also, don't use a normal list for the openlist since you will have to sort it repeatedly if you follow the naive approach as you do at the moment. Python has the heapq module or queue.PriorityQueue exactly for that purpose. You would then use the node's cost + its estimated heuristic cost as priority value - Python does: the lower the value, the higher up. Furthermore, it's also possible to implement A* without using a closelist, which would eliminate another lump of data you would have to care for.

There is also no need to look at all the elements of the openlist once you have found a path to the goal. IIRC you can terminate early once the goal is part of the openlist (under the assumption of an admissible heuristic).

I still stand by what I said about the heuristic function in a comment under your code. You will usually always want to use the Euclidean distance for grid worlds as yours. Python will also happily support you in computing this distance with hypot from the math module. Using hypot(dx, dy) will likely be at least little bit faster than sqrt(dx*dx + dy*dy) and also numerically more stable. The comments also describe heuristics that might even be more suitable for this case.

Addendum

I cobbled together some code that still ignores some of the recommendations above and reuses some of the structural ideas (like a modified version of the Node class), but is considerably faster while producing the same result. Also note that this in an implementation that does not use a closelist.

Your original implementation took about 12s here on my machine. The version runs in less than 1ms.

from heapq import heappush, heappop
from math import hypot, sqrt

SQRT2 = sqrt(2.0)

DIRECTIONS = ((1, 0, 1.0), (0, 1, 1.0), (-1, 0, 1.0), (0, -1, 1.0),
              (1, 1, SQRT2), (-1, -1, SQRT2), (1, -1, SQRT2), (-1, 1, SQRT2))

class Node:

    def __init__(self, x, y, cost=float("inf"), h=0, parent=None):
        self.x = x
        self.y = y
        self.cost = cost
        self.h = h
        self.parent = parent

    def update(self, new_parent, new_cost):
        self.parent = new_parent
        self.cost = new_cost

    def __repr__(self):
        return "Node(x={x}, y={y}, cost={cost}, h={h}, parent={parent})".format(**self.__dict__)

    @property
    def priority(self):
        return self.cost + self.h

    @property
    def pos(self):
        return self.x, self.y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __lt__(self, other):
        """This allows Node to be used in the priority queue directly"""
        return self.priority < other.priority

def make_grid(n_rows, n_cols, value):
    """Make a n_rows x n_cols grid filled with an initial value"""
    return [[value for _ in range(n_cols)] for _ in range(n_rows)]

def euclidean_distance(node1, node2):
    """Compute the Euclidean/L2 distance between two nodes"""
    return hypot(node1[0] - node2[0], node1[1] - node2[1])

def is_valid(x, y, grid, x_max, y_max):
    """Check the bounds and free space in the map"""
    if 0 <= x < x_max and 0 <= y < y_max:
        return grid[x][y] == 0
    return False

def pfind_new(grid, start, goal):
    x_max, y_max = len(grid), len(grid[0])

    # None will later be used as sentinel for "no node here (yet)"
    nodes = make_grid(x_max, y_max, None)

    start_node = Node(*start, cost=0, h=euclidean_distance(start, goal))
    nodes[start_node.x][start_node.y] = start_node
    goal_node = Node(*goal)
    nodes[goal_node.x][goal_node.y] = goal_node

    # openlist will be used a priority queue and has to be accessed using
    # heappush and heappop from the heapq module. The Node class was modified
    # to work well with this kind of datastructure.
    openlist = []
    heappush(openlist, start_node)

    found = False
    while not found:
        # get the node with the least overall cost (actual + heuristic)
        current = heappop(openlist)
        for direction in DIRECTIONS:
            # compute new coordinates
            x_n, y_n = current.x + direction[0], current.y + direction[1]
            if not is_valid(x_n, y_n, grid, x_max, y_max):
                continue
            # we have valid coordinates
            if nodes[x_n][y_n] is None:
                nodes[x_n][y_n] = Node(
                    x_n, y_n, h=euclidean_distance((x_n, y_n), goal)
                )
            # the new cost is made up if the current cost + transition
            new_cost = nodes[current.x][current.y].cost + direction[2]
            if new_cost < nodes[x_n][y_n].cost:
                # cool, we have found a faster path to this node, let's update
                # it's predecessor
                nodes[x_n][y_n].update(current.pos, new_cost)
                heappush(openlist, nodes[x_n][y_n])
                if nodes[x_n][y_n] == goal_node:
                    # we're done, get out of here
                    found = True
                    break
        # openlist is empty and we have not bailed out with found. seems like
        # there is nothing we can do here
        if not openlist:
            return []

    # backtracking
    path = []
    current = goal_node
    # this is a little bit weird because I decided to store only the
    # coordinates instead of the parent itself. Why? Because repr(node) is way
    #  more readable that way ;-)
    while True:
        path.append(current.pos)
        if current.parent is not None:
            current = nodes[current.parent[0]][current.parent[1]]
        else:
            break
    # the path is built by backtracking from the goal, so we have to reverse it
    return path[::-1]

if __name__ == "__main__":
    import timeit
    grid = [[0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 1, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0]]

    start = (0, 0)
    goal = (4, 3)
    t_start = timeit.default_timer()
    path = pfind_new(grid, start, goal)
    print(f"took: {timeit.default_timer() - t_start}")
    assert path == [(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]


Set + Queue + a get method backed by a Map The other day I stumbled upon this question on Stack Overflow about the lack of a get method on the Set and loved the suggestion of using a Map<E,E> to back the Set. I decided to try this out. Since this is quite a generic object that could serve a lot of purposes, I would like to know if there is something weird with my implementation.

NB: I am using Java 7.

Here is the interface:

public interface QueuedSetWithGet<E> extends Set<E>, Queue<E> {
    public E get(E e);
}

And here is the implementation I wrote:

public class QueuedSetWithGetImpl<E> implements QueuedSetWithGet<E> {

    LinkedHashMap<E, E> map = new LinkedHashMap<E, E>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean contains(Object paramObject) {
        return map.containsKey(paramObject);
    }

    @Override
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    @Override
    public Object[] toArray() {
        return map.keySet().toArray();
    }

    @Override
    public <T> T[] toArray(T[] paramArrayOfT) {
        return map.keySet().toArray(paramArrayOfT);
    }

    @Override
    public boolean add(E paramE) {
        boolean notAlreadyPresent = !map.containsKey(paramE);
        if (notAlreadyPresent) {
            map.put(paramE, paramE);
        }
        return notAlreadyPresent;
    }

    @Override
    public boolean remove(Object paramObject) {
        return map.remove(paramObject) != null;
    }

    @Override
    public boolean containsAll(Collection<?> paramCollection) {
        return map.keySet().containsAll(paramCollection);
    }

    @Override
    public boolean addAll(Collection<? extends E> paramCollection) {
        boolean mapChanged = false;
        for (E e : paramCollection) {
            mapChanged |= this.add(e);
        }
        return mapChanged;
    }

    @Override
    public boolean retainAll(Collection<?> paramCollection) {
        boolean mapChanged = false;
        for (Object e : paramCollection) {
            if (!this.contains(e)) {
                mapChanged = true;
                this.remove(e);
            }
        }
        return mapChanged;
    }

    @Override
    public boolean removeAll(Collection<?> paramCollection) {
        boolean mapChanged = false;
        for (Object e : paramCollection) {
            mapChanged |= this.remove(e);
        }
        return mapChanged;
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean offer(E paramE) {
        return this.add(paramE);
    }

    @Override
    public E remove() {
        E head = this.element();
        this.remove(head);
        return head;
    }

    @Override
    public E poll() {
        return this.isEmpty() ? null : this.remove();
    }

    @Override
    public E element() {
        E e = this.peek();
        if (e == null) {
            throw new NoSuchElementException("queue is empty");
        } else {
            return e;
        }
    }

    @Override
    public E peek() {
        return this.isEmpty() ? null : map.keySet().iterator().next();
    }

    @Override
    public E get(E e) {
        return map.get(e);
    }
}

Bug in retainAll

The method retainAll does not respect its contract. It is supposed to remove from this set all the elements that are not contained in the given set. However, the following code:

Set<String> set = new QueuedSetWithGetImpl<>();
set.add("foo");
set.add("bar");
set.retainAll(Arrays.asList("foo"));
System.out.println(set.size()); // prints 2!

does not remove the "bar" element from the set (the size is still 2).

The issue with the current code is that it doesn't loop over the elements of the set to find the ones not contained in the given collection. To implement it correctly, you can use an Iterator and call remove():

@Override
public boolean retainAll(Collection<?> paramCollection) {
    boolean mapChanged = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!paramCollection.contains(it.next())) {
            mapChanged = true;
            it.remove();
        }
    }
    return mapChanged;
}

Access control

LinkedHashMap<E, E> map = new LinkedHashMap<E, E>();

This map needs to be private. It is the backing map of your implementation and is not intended to be used by other classes.

Possible simplification

boolean notAlreadyPresent = !map.containsKey(paramE);
if (notAlreadyPresent) {
    map.put(paramE, paramE);
}
return notAlreadyPresent;

This can be simplified a bit by using the result of put, which is either the previous value or null if there was no mapping. As such, you can have:

return map.put(paramE, paramE) == null;

Note that will replace the old value with the given new value, but it won't break the contract of the Set which defines equality in terms of equals and not ==. To not replace, you could use putIfAbsent on Java 8, but since you're using Java 7, you could keep what you have.

This class feels as though it is trying to fulfill to many things. A Set, Queue and Hashmap are all different data structures for a reason.

As someone answered in the linked Stack Overflow question; there would be no point in having a get method for a Set object because each item in the Set needs to be unique. You acheive the same functinality by checking if the object is in the Set without having any issues with how to deal with the object not being in the Set (ie. returning the object if it is there or null if it isn't).

A Set by definition isn't really ordered either (and if its needed Java has the TreeSet class) . A method such as peek doesn't really make sense for a Set.

This seems like an unnecessary blend of multiple data structures. Specialized classes are a good thing. What use case would such a class have? It would likely lead to inexperienced programmers misusing it.


Comparing two strings to see if string 2 is inside string 1 Here is what I have to do:

  Write a function scramble(str1,str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

  For example:

  str1 is 'rkqodlw' and str2 is 'world' the output should return true.
  str1 is 'cedewaraaossoqqyt' and str2 is 'codewars' should return true.
  str1 is 'katas' and str2 is 'steak' should return false.

  Only lower case letters will be used (a-z). No punctuation or digits will be included.
  Performance needs to be considered

public class Scramblies {
    public static boolean scramble(String str1, String str2) {
        String temp = str1;
        int count = 0;
        boolean result = true;
        for(int i=0 ; i<str2.length() ; i++){
            char c = str2.charAt(i);
            if(temp.contains(String.valueOf(c))){
                temp = temp.replaceFirst(String.valueOf(c), "");
                count++;
            }
        }
        if (count == str2.length()){
            result = true;
        } else {
            result = false;
        }
        return result;
    }
 }

My code works perfectly, but the only problem now is efficiency. I am tested against how long it takes to finish the final test class, which times out. I get this:

  Process was terminated. It took longer than 10000ms to complete

How can this code be made more efficient to achieve the same result?

The problem with your approach is that you're traversing the second String as many times as there are elements in the first String with the replaceFirst call (which also involves a regular expression).

Also, this has nothing to do with performance, but you could just use

return count == str2.length();

instead of the long, and so more difficult to read,

boolean result = true;
if (count == str2.length()){
    result = true;
} else {
    result = false;
}
return result;

You can tackle this problem a lot more effectively by taking advantage of the fact that only lower case letters will be used (a-z). Consider the following approach:

We know that there are 26 lower case characters. Let us create an array of 26 values int[] array = new int[26];.
For each character c of the second String, we increment the value stored in the array at the position c - 'a': this corresponds to the alphabetical position of the character (based from 0: 'a' -> 0, 'b' -> 1, ..., 'z' -> 25).
Then for each character c of the first String, we decrement the value stored at the alphabetical position.
Finally, if at the end of this process, we end up with at least one value that is strictly positive, we know that the second String wasn't contained in the first one. This is because it means that we encountered a character in str2 more times than it was in str1 (it was incremented more times than it was decremented).

A sample implementation of this approach would be:

public static boolean scramble(String str1, String str2) {
    int[] array = new int[26];
    for (char c : str2.toCharArray()) {
        array[c - 'a']++;
    }
    for (char c : str1.toCharArray()) {
        array[c - 'a']--;
    }
    for (int value : array) {
        if (value > 0) {
            return false;
        }
    }
    return true;
}

You can test it with

public static void main(String[] args) {
    System.out.println(scramble("rkqodlw", "world")); // prints "true"
    System.out.println(scramble("cedewaraaossoqqyt", "codewars")); // prints "true"
    System.out.println(scramble("katas", "steak")); // prints "false"
}

Another method would be to sort all the letters in both strings.  If the first value in string 1 doesn't match the first value in string 2, skip it.  If the first value in both string 1 and string 2 match, skip both.  If you run out of string 1 while there are still values in string 2 there is no match.  If you consume all of string2's values, you match.


Tic-Tac-Toe code in C++ I wrote this as an exercise. I think that I have some repetitive code in the "winner" function but I don't know exactly how to reduce it. Any other general advice would be welcome too.

#include<iostream>
#include<iomanip>

char table[3][3];
int turn=1;

void print_table()
{
    for (int i=0;i<3;i++)
    {
        for (int j=0;j<3;j++)
            std::cout<<std::setw(3)<<table[i][j];
    std::cout<<std::endl;
    }
}

void create_table()
{
    for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
            table[i][j]='*';
}

void input(int turn)
{
    int x=0,y=0;
    std::cin>>x>>y;
    if(turn%2==1)
        table[x][y]='X';
    else
        table[x][y]='O';
}

char winner()
{
    for(int i=0;i<3;i++)
        if(table[0][i]==table[1][i]&&table[1][i]==table[2][i]&&table[0][i]=='X')
        {
            return 'X';
        }

    for(int i=0;i<3;i++)
        if(table[i][0]==table[i][1]&&table[i][1]==table[i][2]&&table[i][0]=='X')
        {
            return 'X';
        }

        for(int i=0;i<3;i++)
        if(table[0][i]==table[1][i]&&table[1][i]==table[2][i]&&table[0][i]=='O')
        {
            return 'O';
        }

    for(int i=0;i<3;i++)
        if(table[i][0]==table[i][1]&&table[i][1]==table[i][2]&&table[i][0]=='O')
        {
            return 'O';
        }

      if(table[0][0]==table[1][1]&&table[0][0]==table[2][2]&&table[0][0]=='O')
      {
            return 'O';
      }

      if(table[0][0]==table[1][1]&&table[0][0]==table[2][2]&&table[0][0]=='X')
      {
            return 'X';
      }

      return '\0'; ///default
}

int main(){

create_table();
print_table();

while (turn<=9&&winner()=='\0')
{
input(turn);
print_table();
winner();
turn++;
}

if(winner()!='\0')
    std::cout<<std::endl<<"winner:"<<winner();
else
    std::cout<<"Draw.";
}

1. Simplified winner() method

You could merge the checks for 'X' and 'O' by returning one of the chars in a match of three in a row:

char winner() {
  for (int i = 0; i < 3; i++) {
    if (table[0][i] == table[1][i] && table[1][i] == table[2][i]) {
      return table[0][i]; // 'X' if all are 'X' and 'O' if all are 'O'
    }
  }

  for (int i = 0; i < 3; i++) {
    if (table[i][0] == table[i][1] && table[i][1] == table[i][2]) {
      return table[i][0];
    }
  }

  if (table[0][0] == table[1][1] && table[1][1] == table[2][2]) {
    return table[1][1];
  }

  if (table[0][2] == table[1][1] && table[1][1] == table[2][0]) { // *
    return table[1][1];
  }

  return '\0';
}

*Note that your code is missing the forward slash diagonal

2. Consider eliminating your global variables

I know this is just a practice project, and your code is fine as it is. However, if you wanted to scale your code, then you've created some unnecessary problems for yourself in the future.

All of your functions depend on your two global variables, which limits you to one game and gets in the way of other features by polluting the global namespace. You could eliminate the globals by taking an object oriented approach or a more functional programming styled approach.

The Object Oriented way

The OO way would involve creating a TicTacToeGame class and making the global variables member variables members of your class.

class TicTacToeGame() {
private:
  char table[3][3];
  int turn;

public:
  TicTacToeGame() {
    for (int i=0;i<3;i++)
      for (int j=0;j<3;j++)
        table[i][j]='*';

    turn = 1;
  }

  char winner() {}

  void input() {
    // ...
    turn++;
  }

  void print() {}

  int getTurn() {
    return turn;
  }
}

int main() {

  TicTacToeGame game = TicTacToeGame();
  game.print();

  while (game.getTurn() <= 9 && game.winner() == '\0')
  {
    game.input();
    game.print();
    game.winner();
  }

  if(game.winner() != '\0')
    std::cout<<std::endl<<"winner:"<<winner();
  else
    std::cout<<"Draw.";
}

Creating a class comes with a few other benefits. Particularly that you can encapsulate how a Tic-tac-toe game is played which helps with code scalability.

A more functional approach

For the functional approach you can just pass the globals as parameters instead (be sure to pass by reference):

char[][] create_table() {
  // ...
  return table;
}

void input (int turn, char[][] &table) {
  // ...
}

char winner(char[][] &table) {
  // ...
}

int main() {

  int turn = 1;
  char[][] table = create_table();
  print_table(table);

  while (turn <= 9 && winner(table) == '\0') {
    input(turn, table);
    print_table(table);
    winner(table);
    turn++;
  }

  if(winner(table) != '\0')
    std::cout<<std::endl<<"winner:"<<winner(table);
  else
    std::cout<<"Draw.";
}

This way gives you a lot more control over when and where turn and board get declared. You can more easily create multiple games to be played simultaneously. The biggest benefit is that your functions have their dependencies explicitly defined; there are no hidden parameters.

Nice job overall! My second suggestion is mostly just to help with a few concepts with software development, and it isn't really applicable if you intend to keep your Tic-tac-toe game as simple as it is. Keep up the good work.

To replace the winner function

char  winner = "\0";

for(int i=0;i<3;i++){
    if(table[0][i]==table[1][i]&&table[1][i]==table[2][i]){
          winner  = table[0][i];
    }

    if(table[i][0]==table[i][1]&&table[i][1]==table[i][2]){
          winner  = table[i][0];
    }
}

if(table[0][0]==table[1][1]&&table[0][0]==table[2][2]){
  winner  = table[0][0];
}

if(table[2][0]==table[1][1]&&table[0][0]==table[0][2]){
   winner  = table[2][0];
}

return winner;

Summary of changes.

Merge all the loops
Merge the seperate checks for x and o


Reading Large Files in Java getting really slow I am trying to read a large file ~200 MB (~300 million lines of text). I am using a relatively standard way of reading like:

for (int i = 1; i <= numProcs; i++) {
    System.out.println("Parsing " + traceFilePrefix + i + ".prg");
    System.out.println("##########################");

    try {
        String line;
        int instrType;
        String hexAddr;
        ArrayList<Trace> traces = new ArrayList<Trace>();

        int lineNum = 1;

        BufferedReader br = new BufferedReader(new FileReader(traceFilePrefix + numProcs + "/" + traceFilePrefix + i + ".PRG"));
        while ((line = br.readLine()) != null) {
            line = line.toUpperCase();
            // validate line format
            if (line.matches(regexLineFormat)) {
                StringTokenizer tokenizer = new StringTokenizer(line);
                instrType = Integer.parseInt(tokenizer.nextToken());
                hexAddr = tokenizer.nextToken();

                traces.add(new Trace(instrType, hexAddr));
            } else {
                // line is in invalid format
                System.err.println("ERR: line " + lineNum + " is invalid \"" + line + "\"");
            }
            lineNum++;

            if (lineNum % 1000 == 0) System.out.println("line " + lineNum);
        }
        br.close();
        processorsTraces.add(i-1, traces);
    } catch (Exception e) {
        e.printStackTrace();
    }
}

I find that reading slows down at about line 20 million... in face it doesnt seem to progress at all ... how can I improve this? Whats the problem in this simple piece of code?

A latest run seem to run out of heap space ... I guess I cant store data in an arraylist like that?

This is supposed to be a simulator. It first parses trace files containing hexadecimal addresses of memory accesses. Then is supposed to run simulation of these data. This code snipplet only parses and stores the traces in an arraylist.

The issue is almost certainly in the structure of your Trace class, and it's memory efficiency. You should ensure that the instrType and hexAddress are stored as memory efficient structures. The instrType appears to be an int, which is good, but just make sure that it is declared as an int in the Trace class.

The more likely problem is the size of the hexAddress String. You may not realise it but Strings are notorious for 'leaking' memory. In this case, you have a line and you think you are just getting the hexString from it... but in reality, the hexString contains the entire line.... yeah, really. For example, look at the following code:

public class SToken {

    public static void main(String[] args) {
        StringTokenizer tokenizer = new StringTokenizer("99 bottles of beer");
        int instrType = Integer.parseInt(tokenizer.nextToken());
        String hexAddr = tokenizer.nextToken();
        System.out.println(instrType + hexAddr);
    }
}

Now, set a break-point in (I use eclipse) your IDE, and then run it, and you will see that hexAddr contains a char[] array for the entire line, and it has an offset of 3 and a count of 7.

Because of the way that String substring and other constructs work, they can consume huge amounts of memory for short strings... (in theory that memory is shared with other strings though). As a consequence, you are essentially storing the entire file in memory!!!!

At a minimum, you should change your code to:

hexAddr = new String(tokenizer.nextToken().toCharArray());

But even better would be:

long hexAddr = parseHexAddress(tokenizer.nextToken());

EDIT: Request to get help on how to debug the code:

To debug the code, you need to set a break-point in the method. Select the line System.out.println(...); and use the key-board short-cut Ctrl-Shift-B which will toggle a break-point, and you will get the 'dot' marker like the picture below:

Then, with that break-point enabled, you need to debug the program:

Right-click on the 'main' word in the public static void main (String[] ...) and select 'Debug As -> Java Application'

This should prompt you to go to the 'Debug' perspective, and you will have a window with the 'Variables' displayed. One of the variables will be hexAddr and you can expand it to show its contents. Here's a screen-shot:

From the variables section there are a few things of note. At the bottom, the 'value' variable is highlighted, and it's internal value is shown in the area below ( [9, 9,  , b, o, ......, r]

You can see the count and offset variables for hexAddr too. This means that the hexAddr variable stores the char[] array for the entire line, but also stores an offset and count in that array which it uses for managing the subset of the chars that this String instance is interested in

First thing you should change in the code is avoid reading binary file using FileReader. It is meant for reading streams of character. You can use FileInputStream.

Close io streams in finally block so that they are closed even if an exception is thrown.

Also try increasing the buffer size of the BufferedReader.


Flattening array in Javascript I have implemented a solution to flatten an array of multiple levels in Javascript. I am just a newbie so forgive any mistakes. Could someone give me any tips to improve the code?

function streamrollArray(arr) {
    var copyArr = arr;
    var to_return = [];

    while (true) {
        if (copyArr.length <= 0) { return to_return; }
        var head = copyArr[0];
        to_return = to_return.concat(getValues(head));
        //Chop head off since we have got all the values from it.
        copyArr = copyArr.splice(1);
    }
}

function getValues(arr) {
    var copyArr = arr;
    var to_return = [];

    if (!Array.isArray(arr)) {
        return arr;
    }

    while (true) {
        //A head can contain multiples arrays inside it.
        if (copyArr.length <= 0) { return to_return; }
        var head = copyArr[0];
        to_return = to_return.concat(getHead(head));
        copyArr = copyArr.slice(1);
    }
}

function getHead(head) {
    //If its an array we break into it getting the head and keep checking.
    while (Array.isArray(head)) {
        head = head[0];
    }
    return head;
}

I would think that this might be a problem best solved via recursion.

For example:

function flattenArray(arr) {
    var result = [];

    arr.forEach(function($val) {
        if(Array.isArray($val)) {
            result = result.concat(flattenArray($val));
        } else {
            result.push($val);
        }
    });

    return result;
}

Also consider a more meaningful name for your function like flattenArray vs. steamrollArray.  This better conveys what the function does.  Look at your question title for example. You used Flattening array to describe your code not Steamrolling array.

I would consider a slight modification of Mike's code to avoid creating so many intermediate arrays:

function flattenArray(arr, outputArray) {
    outputArray ||= [];

    arr.forEach(function($val) {
        if(Array.isArray($val)) {
            flattenArray($val, outputArray));
        } else {
            outputArray.push($val);
        }
    });

    return outputArray;
}


C++ implementation of queue using array I have written this code after studying from Introduction to Algorithm. I think this code is very basic and simple. I want to modify it.

#include <iostream>
int tail;
int head;

void initialise_head_tail(){
tail=0;
head=0;
}

void enqueue(int a[],int x,int s){
a[tail]=x;
if( tail+1==s)
    tail=0;
else
    tail++;
}

int dequeue(int a[],int s){
int x=a[head];
if(head+1==s)
    head=0;
else
    head++;
return x;
}
int main()
{
    initialise_head_tail();
    int a[5];
    enqueue(a,15,5);
    enqueue(a,6,5);
    enqueue(a,9,5);
    enqueue(a,8,5);
    enqueue(a,4,5);
    for(int i=0;i<5;i++){
        std::cout<<a[i]<<" ";
    }
    std::cout<<"\n"<<dequeue(a,5);
    return 0;
}

I want to learn if I can apply some better logic. I was thinking to use vector instead of array but there are already methods push_back() and pop_back(). Can we use vector?

Distributing the internal state of your queue over some globals and two arguments is an interesting decision. At least that way you can get the worst of all worlds.
enqueue assumes the queue is not full, dequeue assumes it is not empty. That's also a questionable decision.
You know that streaming a char is more efficient than streaming a length-1-string?
return 0; is implicit for main() in C++ and C99+.
I wonder why you wrap a conditional statement into its own block exactly one time. Some advocate using a block everywhere, others only where needed, but both camps are united in wanting consistency.
The inside of your first three functions somehow lost a level of indentation... and there should be a newline before main().

After seeing comments and answer I have tried to improve my code. Please tell me if I can improve further. Can I use any better logic for display() function

#include <iostream>

#define max 1000

class Queue{
int head,tail;
public:
    int a[max];
    Queue(){
    head=0;
    tail=0;
    }
  void enqueue(int x);
  int dequeue();
  void display();
};

void Queue::enqueue(int x){
a[tail]=x;
if( tail+1==(max-1))
    tail=0;
else
    tail++;
}

int Queue::dequeue(){
int x=a[head];
if(head==(max-1))
    head=0;
else
    head++;
return x;
}

void Queue::display(){
for(int i=head;i<tail;i++){
    std::cout<<a[i]<<" ";
}
}
int main()
{
    Queue queue1;
    queue1.enqueue(15);
    queue1.enqueue(6);
    queue1.enqueue(9);
    queue1.enqueue(8);
    queue1.enqueue(4);
    queue1.display();
    std::cout<<"\n"<<queue1.dequeue()<<"\n";
    queue1.display();
    return 0;
}


Simple registration form with Backbone I am trying to create simple registration form with Backbone.  I need to validate fields on blur, and whole form on submit.

HTML:

<form>

<input name="name" type="text" placeholder="Name"/>

<input name="surname" type="text" placeholder="Surname"/>

<input name="email" type="text" placeholder="Your mail"/>

<input name="password" type="password" placeholder="Password"/>

<input name="pagename" type="text" placeholder="Page name"/>

        <input type="submit" value="Go"></input>
</form>

Model:

app.__definitions.models.Signup = Backbone.Model.extend({
    url: '/app/signup',

    defaults: {
            name: '',
            surname: '',
            email: '',
            password: '',
            pagename: ''
    },

    validateOne: validator.validateOne,

    validate: function(fields) {
            var result = validator.validateAll(fields);
            if (result !== true) return result;
    }
 });

View:

app.__definitions.views.Signup = Backbone.View.extend({
    el: $('form'),

    events: {
        'submit': 'onFormSubmit',
        'change input[type!="submit"]': 'onInputChange',
        'blur input[type!="submit"]': 'onInputChange',
        'focus input': function(e) {
                this.resetInputErrors(e.target);
        }
    },

    templates: {
            'error': _.template('<%=error%>')
    },

    initialize: function() {
            this.model = new app.__definitions.models.Signup();

            this.model.on('invalid', this.onModelInvalid, this);
    },

    getInput: function(name) {
            return this.$el.find('[name="' + name + '"]');
    },

    onModelInvalid: function(model, errors) {
            var _this = this;
            _.each(errors, function(error, name) {
                    _this.showInputErrors(_this.getInput(name), error);
            })
    },

    onFormSubmit: function(e) {
            e.preventDefault();
            var model = this.model;

            this.$el.find('input[name]').each(function() {
                    model.set(this.name, this.value);
            })
            this.model.save();
    },

    onInputChange: function(e) {
            this.model.set(e.target.name, e.target.value);
            var result = this.model.validateOne(e.target.name, e.target.value);
            if (result !== true) this.showInputErrors(e.target, result)
    },

    resetInputErrors: function(target) {
            var $target = $(target);
            $target.removeClass('incorrect')
            $target.parent().find('.error').remove();
    },

    showInputErrors: function(target, errors) {
            var $target = $(target);
            var errorsHTML = '';

            this.resetInputErrors(target);

            for (var i = 0; i < errors.length; i++) {
                    errorsHTML += this.templates.error({error: se.errors.get(errors[i])});
            }

            $target.addClass('incorrect');
            $target.parent().append(errorsHTML);
    }
    });

Init:

 app.views.Signup = new app.__definitions.views.Signup();
 app.routers.Router = new app.__definitions.routers.Main({hashChange: true});

Questions:

Do I understand right how to make Backbone application?
Where is the mistakes? What can I do better or clearer?
Is there a better way to connect model with inputs on my form, or my getInput is ok?
In my case I don't need to use the collection? Am I right?

Generally it looks like your know what your doing, maybe you could be more efficient by removing the blur event since you wouldn't need to save/validate if the input is already populated or left empty, this will also save you calling onInputChange twice when an input is changed.

Backbone will automatically create this.$el from the el property so you can just do.

el: 'form' and then this.$el would be created for you.

Finally i would use listenTo rather than on for example.

this.model.on('invalid', this.onModelInvalid, this);

would be done like this using listenTo.

this.listenTo(this.model, 'invalid', this.onModelInvalid);

This allows you to keep track of events on the object and then remove them all at once later on.

I don't know too much about backbone, but here are my tips, i don't like, why?

1 - This is ugly: app.__definitions.models.Signup, i don't like to use globals, you should avoid it, and "Signup" what? your app i suppose but if you've another "sign up" in your app what you would call it? Ok, maybe you just have one, but try to explain more what you want in your variables.

2 - You're manipulating too much DOM elements in your methods, avoiding then to reuse them.

3 - Use more dependency injection, you're using unknown objects inside your methods, do you know about Law of Demeter (LoD) or principle of least knowledge ?

4 - One function one thing, you're doing too much inside of your functions.

like i said before, i don't know too much about backbone, but if this framework doesn't encourages you to modularize your code, run to another framework.