Connecting to Oracle using ODP.NET What can be improved in my code:

        using (var oracleConnection = new OracleConnection(ConnectionString))
        {
            using (var oracleCommand = oracleConnection.CreateCommand())
            {
                oracleConnection.Open();

                oracleCommand.CommandText =
                "SELECT *
                 FROM table_sample Table_Sample
                 WHERE table_sample.id > 1000";

                using (var reader = oracleCommand.ExecuteReader())
                {
                    while (reader.Read())
                    {
                        int id = reader.GetValue(0);
                    }
                }
            }
        }

As the most "dangerous" thing I see the ugly string statement for database query.

I dont want to use Entity Framework for Oracle - cause its not as actual as one for MS SQL Server. And also some Oracle features are not supported.

You're using using blocks to dispose your disposables, which is excellent. However these blocks increase the nesting of your code; since there's nothing between using (var oracleConnection = new OracleConnection(ConnectionString)) and using (var oracleCommand = oracleConnection.CreateCommand()) you could drop the curly braces and "stack" them, like this:

    using (var oracleConnection = new OracleConnection(ConnectionString))
    using (var oracleCommand = oracleConnection.CreateCommand())
    {
        ...
    }

Within that scope, you're reassigning variable Id at each row that gets read; ultimately the value of Id will be that of the last row that was read. I doubt this is the intended behavior.

As for the string query, I agree it's "dangerous" - I prefer (by far) to use an object-relational mapper such as Entity Framework (which as @svick has mentioned has an Oracle provider), but never used it for anything other than SQL Server. I believe you could look into NHibernate as well, or shop around - something like ".net ORM for oracle" should find you some interesting links :)


This code looks really repetitive. Any way to shorten it? I have something like this in my program:

    private void tspBrush_Click(object sender, EventArgs e)
    {
        currentTool = new Brush(tileLayers);

        UncheckToolstripButtons();

        tspBrush.Checked = true;
    }

    private void tspBucket_Click(object sender, EventArgs e)
    {
        currentTool = new Bucket(tileLayers);

        UncheckToolstripButtons();

        tspBucket.Checked = true;
    }

    private void tspCut_Click(object sender, EventArgs e)
    {
        currentTool = new Cut(tileLayers);

        UncheckToolstripButtons();

        tspCut.Checked = true;
    }

As I increase the amount of tools this list will only get longer. Is there something I could do to shorten it?

one way of shortening might be:

having a HashMap consisting of pairs of objects (sender) and Tools. This way you could look up the appropriate Tool for each sender in one single method like this:

HashMap<object, Tool> hashMap = new HashMap<object, Tool>( );

hashMap.put(sender1, new Brush(tileLayers));

// ...add the rest of the Tools
private void clickHandler(object sender, EventArgs e)
{
    currentTool = hashMap.get(sender);

    UncheckToolstripButtons( );
    tspBrush.Checked = true;
}

If tspXxxx cannot be retrieved from the sender directly, use another HashMap to map senders to tspXxxx objects.


Python function to get numbers around another number I made a function to get a list with numbers around another number. Example: I want to get in a range of 2 numbers around 4. This will return: [2, 6]. You can set a min number and a max_number. That means when I set a min_num, the lower number should not be lower than the min number.

import sys

def get_numbers_around(number: int, min_num: int = None, max_num: int = None, _range: int = 2, on_fail_no_error: bool = False) -> range:
    if max_num is None:
        max_num = sys.maxsize

    if min_num is None:
        min_num = -sys.maxsize - 1

    diff = max_num - min_num
    if diff < _range:
        if not on_fail_no_error:
            raise ValueError(
                "Range is too small. Range is {0} big but difference between max_num and min_num is {1} big! ({0} < {1}".format(
                    range, max_num - min_num))
        else:
            return range(number - diff, number + diff)

    final_list = [number - _range, number + _range]

    if final_list[0] < min_num:
        diff = abs(min_num - final_list[0])
        final_list[0] = min_num
        final_list[1] += diff

    if final_list[1] > max_num:
        diff = abs(final_list[1] - max_num)
        final_list[1] = max_num
        final_list[0] -= diff

    return range(final_list[0], final_list[1])

print(get_numbers_around(4)) # range(2, 6)
print(get_numbers_around(4, _range=5)) # range(-1, 9)
print(get_numbers_around(0, min_num=0, max_num=1, _range=4, on_fail_no_error=True)) # range(-1, 1)
print(get_numbers_around(0, min_num=0, max_num=1, _range=4)) # ValueError

I think it is possible to optimize this code but I don't know how. Does anoyne have any idea?

Your code seems really complicated, and so you should follow KISS and YAGNI.
max_num and min_num don't work the way I would expect them to.
The error goes against what I think is Pythonic. Just return the smaller set.

def get_numbers_around(number, size):
    return range(number - size, number + size)

If you then need to implement min_num and max_num create a filter:

def filter_between(values, minimum=float('-inf'), maximum=float('inf')):
    return (v for v in values if minimum <= v <= maximum)

>>> get_numbers_around(4, 5)
range(-1, 9)
>>> list(filter_between(_, 0))
[0, 1, 2, 3, 4, 5, 6, 7, 8]


How to use this jQuery search filter more effective? This is my code:

function search() {
    $("#myInput").keyup(function() {
        var value = this.value.toLowerCase();

        $("table").find("tr").each(function(index) {
            if (index === 0) return;
            var id = $(this).find("td").first().text().toLowerCase();
            $(this).toggle(id.indexOf(value) !== -1);
        });
    });
}

function searchFilt(value) {
    $("table").find("tr").each(function(index) {
        if (index === 0) return;
        var id = $(this).find("td").first().text();
        $(this).toggle(id.indexOf(value) !== -1);
    });
};

However I have used:

$("table").find("tr").each(function(index) {
            if (index === 0) return;
            var id = $(this).find("td").first().text().toLowerCase();
            $(this).toggle(id.indexOf(value) !== -1);
        });
    });

twice, and I am sure there would be a more effective way to do this. However I am not sure how to go about doing so - any advice?

In the function searchFilt you are using a parameter value, similar to the block of code in the search function. You can just call the searchFilt function from within the search function and pass the variable value:

function search() {
    $("#myInput").keyup(function() {
        var value = this.value.toLowerCase();
        searchFilt(value);
    });
}

function searchFilt(value) {
    $("table").find("tr").each(function(index) {
        if (index === 0) return;
        var id = $(this).find("td").first().text();
        $(this).toggle(id.indexOf(value) !== -1);
    });
}

Note: you don't exactly use the code twice, inside the search function you have .toLowerCase() at the end of the line where you get the id.


Big O notation for Reverse String I have here some methods which reverse string characters. Example if given string is "HELLO", it will returns "OLLEH". Are my big o notation for these approaches correct? And which approach is the most efficient (both time and space complexity)?

 /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_TwoArrays(string str)
    {
        char[] arr2 = new char[str.Length];

        for (int i = 0; i < str.Length; i++)
        {
            arr2[i] = str[str.Length - 1 - i];
        }
        return string.Join("",arr2);
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ClassicForLoop_ArrayIndex(string str)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = str.Length - 1; i >= 0; i--)
        {
            sb.Append(str[i]);
        }
        return sb.ToString();
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ForEachConcat(string str)
    {

        string newStr = "";
        foreach (var item in str)
        {
            newStr = item.ToString() + newStr;
        }
        return newStr;
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_Stack(string str)
    {
        var stack = new Stack();
        foreach (var item in str) // Time Complexity: o(n)
        {
            stack.Push(item); // Time Complexity: o(1)
        }
        return string.Join("", stack.ToArray());
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ArrayReverse(string str)
    {
        char[] arrChar = str.ToCharArray();
        Array.Reverse(arrChar);
        return string.Join("", arrChar);
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_LINQ(string str)
        => string.Join("", str.Reverse());

There are a couple of constructs in there that can be improved.

string.Join("", charArray), repeated a lot. string has a constructor that takes a char[], which is a lot faster. They are both linear time, which your question seems to focus on, but in terms of actual efficiency the difference is nearly two orders of magnitude in some tests (actual impact of course varies).
new Stack(), so.. the old stack, from the .NET 1.1 days? Don't use that one, use Stack<T>. Especially if the things you're putting in them are value types, which would have to be boxed in the old non-generic Stack.

For ReverseString_ForEachConcat, I don't agree that the time complexity is O(n). At every step, the old string is copied over into the new string, with something concatenated in front of it. So in the second iteration there is 1 copied character, in the third iteration there are 2 copied characters etc. That's a classic O(n²) pattern.

I think we could also argue about whether or not it takes constant space. The many old versions of the string can disappear quickly, but while the concatenation is happening, both the old string and the result of the concatenation need to exist. In the last iteration, that means that while the final result is being made (the size of which doesn't count), there is an other string in play of nearly the same size, so O(n) worth of auxiliary space.


Running a given command after each change in a file I would love to hear some comments on this small script, which (I hope) reduces repetitive tasks such as page refreshing, compilation and so on to minimum.

# -*- coding: utf-8 -*-
# Author: Jacek 'Sabr' Karolak (j.karolak@sabr.pl)
# Watch [files] for change, and after every change run given [command]
#
#
# Example watchdog script: safari.py
#  #!/usr/bin/env python
#  # -*- coding: utf-8 -*-
#
#  from loop import Loop
#
#  if __name__ == "__main__":
#      Loop(["osascript", "-e", """tell application "Safari"
#              do JavaScript "window.location.reload()" in front document
#          end tell"""]).run()
#   EOF
#
# Make safari.py executable (chmox +x safari.py) or use it with python.
# python safari.py FILES_TO_WATCH
# Whenever FILES_TO_WATCH change, refresh Safari in background :-)
#

__all__ = ["Loop"]

import argparse, subprocess
from os import getcwd, listdir, stat
from os.path import exists
from time import sleep

class Loop(object):

    def __init__(self, cmd):
        self._command = cmd
        self._files_to_watch = {}

    def _watchdog(self):
        '''Check wheter any file in self._files_to_watch changed,
        if so fire self._command'''

        check_file = lambda f: stat(f).st_mtime
        files = self._files_to_watch

        any_file_changed = False

        while True:

            # Check each file for st_mtime change (modification)
            for f in files.keys():
                actual_mtime = check_file(f)
                if not files[f] == actual_mtime:
                    any_file_changed = f
                    files[f] = actual_mtime

            if any_file_changed:
                # run command
                print('File: \'{}\' changed since last check.'\
                        .format(any_file_changed))
                any_file_changed = False
                subprocess.call(self._command)

            # sleep before next check
            sleep(0.5)

    def _set_files_to_watch(self, files):
        '''Process args files wheter they exists and include current directory
        content if requested.'''
        if '.' in files:
            files.remove('.')
            # combine all other given files with current working directory
            # content, without dot files
            files += [f for f in listdir(getcwd())\
                    if not f.startswith('.')]

        # make f list unique
        files = set(files)

        # check rights (in order to perform system stat) and wheter they exist
        for f in files:
            if not exists(f):
                msg = 'file \'{}\' does not exists, or I don\'t\
                        have access rights.'.format(f)
                raise IOError(msg)

        # save files to watch in instance variable
        self._files_to_watch = dict.fromkeys(files)

        # set modification times
        for file_key in self._files_to_watch.keys():
            self._files_to_watch[file_key] = stat(file_key).st_mtime

    def run(self):
        '''Parses command line arguments, processes files list,
        and fires watchdog.'''
        parser = argparse.ArgumentParser(description='Checkes wheter given \
                files change, when they do, runs given command.')
        parser.add_argument('files', metavar='F', type=str, nargs='+',\
                help='list files to process, if you add . in list it will\
                watch also all non dot files in current dir.\
                If you want to have all non dot files and some dot ones use:\
                \n.file1 .file2 .file2 . .file3 it will combine specified dot\
                files and all others.')

        args = parser.parse_args()

        self._set_files_to_watch(args.files)

        print('Started watching...')
        self._watchdog()

if __name__ == '__main__':
    pass

class Loop(object):

Loop isn't a very descriptive name for this object. Something like WatchDog or FileWatcher would make more sense

    def __init__(self, cmd):
        self._command = cmd
        self._files_to_watch = {}

This is a mapping from filenames to modification times, but the name doesn't reflect that. I suggest calling _file_modification_times.

    def _watchdog(self):
        '''Check wheter any file in self._files_to_watch changed,
        if so fire self._command'''

        check_file = lambda f: stat(f).st_mtime

check_file isn't a great name, because it doesn't tell me what the function actually does, return the modification time. Since its only used once in this function its also not clear whether its helpful.

        files = self._files_to_watch

What does copy _files_to_watch into a local variable help?

        any_file_changed = False

Move this inside the while loop. You aren't using it to carry information across loop iterations, so limit the scope to being inside the loop.

        while True:

            # Check each file for st_mtime change (modification)
            for f in files.keys():
                actual_mtime = check_file(f)
                if not files[f] == actual_mtime:
                    any_file_changed = f
                    files[f] = actual_mtime

            if any_file_changed:

A simpler approach:

new_modification_times = dict( (filename, os.stat(filename).st_mtime) for filename in files)
if new_modication_times != files:
     self._file_modification_times = new_modification_times

Generally, if you find yourself wanting to set boolean flags, that's a sign you aren't doing things the pythonic way.

                # run command
                print('File: \'{}\' changed since last check.'\
                        .format(any_file_changed))
                any_file_changed = False
                subprocess.call(self._command)

            # sleep before next check
            sleep(0.5)

    def _set_files_to_watch(self, files):
        '''Process args files wheter they exists and include current directory
        content if requested.'''
        if '.' in files:
            files.remove('.')

This special interpretation of '.' is likely to end up being confusing.

            # combine all other given files with current working directory
            # content, without dot files
            files += [f for f in listdir(getcwd())\
                    if not f.startswith('.')]

        # make f list unique
        files = set(files)

Since you put them in a dictionary later, uniquifiying here is kinda pointless.

        # check rights (in order to perform system stat) and wheter they exist
        for f in files:
            if not exists(f):
                msg = 'file \'{}\' does not exists, or I don\'t\
                        have access rights.'.format(f)
                raise IOError(msg)

Rather then prechecking this, why don't you just let the os.stat() complain when it tries to access the files

        # save files to watch in instance variable
        self._files_to_watch = dict.fromkeys(files)

        # set modification times
        for file_key in self._files_to_watch.keys():
            self._files_to_watch[file_key] = stat(file_key).st_mtime

There's no benefit to prepopulating the dictionary here. Instead, you can create an empty dictionary and loop over files instead of .keys(). Better yet, you can use the dictionary trick I used above to fill it. You can put it into a function and call it in both places.

    def run(self):
        '''Parses command line arguments, processes files list,
        and fires watchdog.'''
        parser = argparse.ArgumentParser(description='Checkes wheter given \
                files change, when they do, runs given command.')
        parser.add_argument('files', metavar='F', type=str, nargs='+',\
                help='list files to process, if you add . in list it will\
                watch also all non dot files in current dir.\
                If you want to have all non dot files and some dot ones use:\
                \n.file1 .file2 .file2 . .file3 it will combine specified dot\
                files and all others.')

        args = parser.parse_args()

        self._set_files_to_watch(args.files)

        print('Started watching...')
        self._watchdog()

You should probably put command line parsing logic somewhere besides this class. It makes it harder to reuse this class if it mixes command line parsing with actual logic. I'd parse a command line in a seperate main function and then have it call this.

if __name__ == '__main__':
    pass

Why?


Find consecutive numbers and turn them into ranges I have array

int[] arr = { -2, 0, 1, 2, 3, 4, 5, 8, 9, 11, 13, 15, 18, 22, 25, 28, 29, 30 };

I need to write function that shows it as string and if numbers are near, for example 1,2,3,4,5 - I need to show them 1-5.

I wrote this function in repository

public string[] GetArray()
{
    int[] arr = { -2, 0, 1, 2, 3, 4, 5, 8, 9, 11, 13, 15, 18, 22, 25, 28, 29, 30 };

    int? lastValue = arr.FirstOrDefault();

    var groupDataIntoAdjacentBlocks = arr.Segment(i =>
    {
        var result = lastValue != null && (lastValue != (i - 1));
        lastValue = i;
        return result;
    }
    );

    var convertSetsIntoRanges = groupDataIntoAdjacentBlocks.Select(z =>
    {
        var data = z.ToList();
        if (data.Count() == 1)
            return data.First().ToString();

        return data.First().ToString() + "-" + data.Last().ToString();
    });

    var finalresult = (string.Join(",", convertSetsIntoRanges));
    return new[] { finalresult };

}

And call it like this in controller

public JsonResult GetArray()
{
    var arrayresult = _arrayrepo.GetArray();
    return Json(arrayresult, JsonRequestBehavior.AllowGet);
}

Any suggestions how I can improve my code?

Letting a single method do everything is not such a good idea. You should rather separate the logic for finding consecutive numbers from creating a string from ranges and let them produce the final result by chaining them as extensions.

The first extension only knows how to find ranges. If you don't have range class/struct yet then you can use tuples.

public static IEnumerable<(int Min, int Max)> ToRanges(this IEnumerable<int> source)
{
    using (var e = source.GetEnumerator())
    {
        if (!e.MoveNext())
        {
            yield break;
        }

        var previous = e.Current;

        var range = (Min: previous, Max: e.Current);

        while (e.MoveNext())
        {
            var isConsecutive = e.Current - previous == 1;
            if (isConsecutive)
            {
                range = (range.Min, e.Current);
            }
            else
            {
                yield return range;
                range = (e.Current, e.Current);
            }
            previous = e.Current;
        }

        yield return range;
    }
}

The other extension consumes the result of ToRanges and returns a string.

public static string Stringify(this IEnumerable<(int Min, int Max)> ranges)
{
    var values = ranges.Select(range => $"{(IsEmpty(range) ? $"{range.Min}" : $"{range.Min}-{range.Max}")}");
    return string.Join(", ", values);

    bool IsEmpty((int Min, int Max) range)
    {
        return range.Max - range.Min == 0;
    }
}

The advantages of having two separated methods are:
- you can focus on one task at a time
- you are now able to test only one feature at a time
- you can reuse ToRange to calculate their lengths if necessary

Other things that you should address are:
- variable names should not sound like they were methods, e.g. groupDataIntoAdjacentBlocks; a much better name would be adjacentBlocks or something along the same lines
- int? lastValue = arr.FirstOrDefault(); this is wrong since the default value for int is 0 and not null.
- the result of the GetArray() method does not make much sense; why would you return an array of strings if there is always only one item? I guess this is not your real code but the range finding part and you edited it for the sake of the question so I won't comment on that one.


Python mint hashcash token This is a Python program to mint a hashcash token, but my code is a lot slower than using a library.  What is slowing my program down?  It takes over 10 seconds to mint a 20-bit stamp, but using a library, it takes less than a second.

This is my program:

from os import urandom
from hashlib import sha1
import time

def mint(name, bits):
    t = time.strftime("%y%m%d")
    out = " "
    count = 0
    while out[:bits] != bits*"0":
        RandomData = urandom(8).encode("base64").replace("\n", "")
        data = "1:%d:%s:%s::%s:%s"%(bits, t, name, RandomData, format(count, 'x'))
        out = (''.join(format(ord(x), '08b') for x in sha1(data).digest()))
        count += 1
    return data

print mint("email_address", 20)

This is the library I am using for comparison.

The first thing to do is to profile your code. Hashcash is really designed to make you perform 2^20 hashes: if you do more work than those hashes, something's wrong!

Profiling

python -m cProfile -s cumtime original.py

Let's look at all the places where the algorithms spends more than 0.001 seconds (I've asked for 15 bits since 20 bits is too slow on my computer) :

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1414287    4.087    0.000    7.665    0.000 original.py:12(<genexpr>)
  1414287    2.433    0.000    2.433    0.000 {format}
   134695    1.737    0.000    9.402    0.000 {method 'join' of 'str' objects}
  1346940    1.295    0.000    1.295    0.000 {ord}
        1    0.886    0.886   12.709   12.709 original.py:5(mint)
    67347    0.536    0.000    0.969    0.000 base64.py:310(encodestring)
    67347    0.432    0.000    0.432    0.000 {posix.urandom}
    67347    0.258    0.000    1.292    0.000 base64_codec.py:13(base64_encode)
    67347    0.231    0.000    1.525    0.000 {method 'encode' of 'str' objects}
    67348    0.141    0.000    0.141    0.000 {_hashlib.openssl_sha1}
    67347    0.131    0.000    0.131    0.000 {method 'digest' of '_hashlib.HASH' objects}
   134694    0.131    0.000    0.131    0.000 {len}
    67347    0.126    0.000    0.126    0.000 {binascii.b2a_base64}
    67348    0.110    0.000    0.110    0.000 {range}
    67347    0.109    0.000    0.109    0.000 {method 'replace' of 'str' objects}
    67347    0.066    0.000    0.066    0.000 {method 'append' of 'list' objects}
        1    0.001    0.001    0.001    0.001 hashlib.py:55(<module>)
        1    0.001    0.001    0.001    0.001 base64.py:3(<module>)

This specific run took 12.7 seconds (original.py:5). It spent 4 seconds in the for x in ... generator, 2.4 seconds in format(ord(x), '08b'), 1.7 seconds in ''.join(...), and 1.3 seconds in ord(x).

That's a total of... 9.5 seconds out of 12.7 seconds spent in the out = (''.join(format(ord(x), '08b') for x in sha1(data).digest())) line. This would have been impossible to figure out without profiling (as you can see in kyle k's comment). It's the number one rule of optimizations: since you'll spent 80% of your time in 20% of the code, only optimize what you know to be slow!

Removing the 80%

So, how can we replace this line? The idea is to use hexdigest instead of digest. The issue with hexdigest is that we only see hexadecimal digits, not bits. Since 20 bits is 5 hexadecimal numbers, that's not an issue here. If you needed 21 bits, then you would ask for 6 hexadecimal numbers, which is more hashes than necessary, but still worth the speed up.

Here's the new code:

from os import urandom
from hashlib import sha1
import time
from math import ceil

def mint(name, bits):
    t = time.strftime("%y%m%d")
    out = " "
    count = 0
    digits = int(ceil(bits/4.0))

    while out[:digits] != digits*"0":
        RandomData = urandom(8).encode("base64").replace("\n", "")
        RandomData = 'AHZlx9LYMyo='
        data = "1:%d:%s:%s::%s:%s"%(bits, t, name, RandomData, format(count, 'x'))
        out = sha1(data).hexdigest()
        count += 1
    return data

print mint("email_address", 15)

And the new profiling:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.750    0.750    3.212    3.212 improved.py:6(mint)
    67347    0.529    0.000    0.959    0.000 base64.py:310(encodestring)
    67347    0.427    0.000    0.427    0.000 {posix.urandom}
    67347    0.251    0.000    1.274    0.000 base64_codec.py:13(base64_encode)
    67347    0.227    0.000    1.503    0.000 {method 'encode' of 'str' objects}
    67347    0.155    0.000    0.155    0.000 {format}
    67348    0.138    0.000    0.138    0.000 {_hashlib.openssl_sha1}
    67347    0.134    0.000    0.134    0.000 {method 'hexdigest' of '_hashlib.HASH' objects}
   134694    0.131    0.000    0.131    0.000 {len}
    67347    0.122    0.000    0.122    0.000 {binascii.b2a_base64}
    67348    0.109    0.000    0.109    0.000 {range}
    67347    0.105    0.000    0.105    0.000 {method 'replace' of 'str' objects}
    67348    0.066    0.000    0.066    0.000 {method 'join' of 'str' objects}
    67347    0.066    0.000    0.066    0.000 {method 'append' of 'list' objects}
        1    0.001    0.001    0.001    0.001 hashlib.py:55(<module>)
        1    0.001    0.001    3.213    3.213 improved.py:1(<module>)
        1    0.001    0.001    0.001    0.001 base64.py:3(<module>)

Yay! Only 3.2 seconds in mint().

Removing another 80%

But hashing is still not the most expensive part. It's now the computing of RandomData (0.5 + 0.2 seconds in base64 encoding, 0.4 seconds in urandom, and so on). @cHao is right, you only need to compute that RandomData once and find the count that provides the correct sha1 hash. Let's move it out of the while loop:

from os import urandom
from hashlib import sha1
import time
from math import ceil

def mint(name, bits):
    t = time.strftime("%y%m%d")
    out = " "
    count = 0
    digits = int(ceil(bits/4.0))
    RandomData = urandom(8).encode("base64").replace("\n", "")
    RandomData = 'AHZlx9LYMyo='

    while out[:digits] != digits*"0":
        data = "1:%d:%s:%s::%s:%s"%(bits, t, name, RandomData, format(count, 'x'))
        out = sha1(data).hexdigest()
        count += 1
    return data

print mint("email_address", 15)

The new profile is:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.414    0.414    0.795    0.795 improved.py:6(mint)
    67347    0.134    0.000    0.134    0.000 {format}
    67348    0.124    0.000    0.124    0.000 {_hashlib.openssl_sha1}
    67347    0.121    0.000    0.121    0.000 {method 'hexdigest' of '_hashlib.HASH' objects}
        1    0.001    0.001    0.001    0.001 hashlib.py:55(<module>)
        1    0.001    0.001    0.796    0.796 improved.py:1(<module>)
        1    0.001    0.001    0.001    0.001 base64.py:3(<module>)

We only took 0.8 seconds (down from 12.7). format still takes time, but only one third of the time. I don't know what to do about it, so I'll leave it as it is, but you got your 10x speedup with two simple changes.


Faster way to concat dataframes with different columns vertically I am trying to concat two huge dataframes (around 15GB) like the following:

a_df:

            A       B       C       D
2018-10-16  a16     b16     c16     d16
2018-10-17  a17     b17     c17     d17
2018-10-18  a18     b18     c18     d18
2018-10-19  a19     b19     c19     d19
2018-10-20  a20     b20     c20     d20

b_df:

            A       C       Y       Z
2018-10-21  a21     c21     y21     z21
2018-10-22  a22     c22     y22     z22

to get a final dataframe:

            A       B       C       D       Y       Z
2018-10-16  a16     b16     c16     d16
2018-10-17  a17     b17     c17     d17
2018-10-18  a18     b18     c18     d18
2018-10-19  a19     b19     c19     d19
2018-10-20  a20     b20     c20     d20
2018-10-21  a21             c21             y21     z21
2018-10-22  a22             c22             y22     z22

I am trying that code:

dfs = [a_df, b_df]

unique_columns = []
for df in dfs:
    for column in df.columns:
        unique_columns.append(column)
unique_columns = sorted(set(unique_columns))

same_columns_dfs = []
for df in dfs:
    empty_df = pd.DataFrame(np.nan, index=df.index, columns=unique_columns)
    empty_df.loc[:, df.columns] = df.values
    same_columns_dfs.append(empty_df)

final_df = pd.concat(same_columns_dfs, axis=0, sort=True)

Is there a more efficient way to do this?

Yep, you can do this in one line, no need to create other lists or empty dataframes when concat will cover your use-case entirely:

import pandas as pd
# to artificially fill a dataframe
import random

# for the purpose of transparency, here's how the dataframes were constructed
a_cols = list('ABCD')
b_cols = list('ACYZ')
a_index = [f'2018-10-{i}' for i in range(16, 21)]
b_index = [f'2018-10-{i}' for i in range(21, 23)]

# creation of the two dataframes
a = pd.DataFrame([{col: random.randint(0, 10) for col in a_cols} for i in a_index], index=a_index)
            A  B  C  D
2018-10-16  6  8  7  4
2018-10-17  5  6  2  5
2018-10-18  4  1  6  5
2018-10-19  4  3  7  9
2018-10-20  7  6  7  5

b = pd.DataFrame([{col: random.randint(0, 10) for col in b_cols} for i in b_index], index=b_index)
            A  C  Y   Z
2018-10-21  1  9  4  10
2018-10-22  1  6  4   6

# and here's your function call
pd.concat([a, b], axis=0, sort=True)
            A    B  C    D    Y     Z
2018-10-16  6  8.0  7  4.0  NaN   NaN
2018-10-17  5  6.0  2  5.0  NaN   NaN
2018-10-18  4  1.0  6  5.0  NaN   NaN
2018-10-19  4  3.0  7  9.0  NaN   NaN
2018-10-20  7  6.0  7  5.0  NaN   NaN
2018-10-21  1  NaN  9  NaN  4.0  10.0
2018-10-22  1  NaN  6  NaN  4.0   6.0

Now the only issue would be the RAM you have at your disposal, and since that wasn't mentioned, I'm assuming this is sufficient. If you are looking for a more memory-optimized solution, we would have to see how those frames are created, since pandas will always load the entire structure into RAM


Robust .mpg file copier #!/usr/bin/env python

"""
Safely copies .mpg files from one volume to another using
temporary filenames and hash verification
"""

import os
from datetime import datetime
from hashlib import sha256
from shutil import copy2

#ask user for origin (where to get files)
def choose_drive(drives, label):
    while True:
        for d in drives:
            print '%s - %s' % (drives.index(d)+1,d)
        drive = raw_input('Select %s: ' % label)
        if not drive in str(range(0, len(drives)+1)):
            continue
        else:
            return os.path.join('/Volumes', drives[int(drive)-1])

# safe copy
def safe_copy(src, dst):
    dst_temp_name = dst+'_INCOMPLETE'
    try:
        copy2(src,dst_temp_name)
        if compare_hashes(src, dst_temp_name):
            try:
                os.rename(dst_temp_name, dst)
            except Exception as e:
                print 'Error trying to rename the file: ', e
        else:
            safe_copy(src, dst)
    except Exception as e:
        print 'Error trying to copy the file: ', e

# hash a file and return the hash string
def get_local_hash(filename, block_size=2**20):
    """
    Hashes a file using SHA1
    """
    # print 'Starting hash of %s at %s' % (filename, datetime.now().time())
    print 'Hashing', filename
    try:
        local_file = open(filename,'rb')
    except Exception as e:
        print 'Error while opening file for hashing: ', e
    hasher = sha256()
    while True:
        data = local_file.read(block_size)
        if not data:
            break
        hasher.update(data)
    # print 'Finished hash at %s' % datetime.now().time()
    result = hasher.hexdigest()
    local_file.close()
    return unicode(result)

def compare_hashes(file1, file2):
    if get_local_hash(file1) == get_local_hash(file2):
        return True

#main
def main():
    # get list of volumes
    drives = [d for d in os.listdir('/Volumes')]
    # ask user for origin drive
    origin = choose_drive(drives, 'Origin')
    origin_files = os.listdir(origin)
    # ask user for destination drive
    destination = choose_drive(drives, 'Destination')
    destination_files = os.listdir(destination)
    # for each file on origin, check if it exists on destination
    for of in origin_files:
        if of.endswith('.mpg'):
            if of in destination_files:
                if compare_hashes(os.path.join(origin, of), os.path.join(destination, of)):
                    print 'already exists and is identical... skipping', of
                else:
                    print 'already exists but is different... copying', of
                    safe_copy(os.path.join(origin, of), os.path.join(destination, of))
            else:
                print 'does not exists... copying', of
                safe_copy(os.path.join(origin, of), os.path.join(destination, of))

if __name__ == "__main__":

    main()

Responses in comments starting with koj -.

#!/usr/bin/env python

"""
Safely copies .mpg files from one volume to another using
temporary filenames and hash verification
"""

import os
from datetime import datetime
from hashlib import sha256
from shutil import copy2

#ask user for origin (where to get files)
def choose_drive(drives, label):
    # koj - needs documentation
    while True:
        for d in drives: # koj - use for d, drive in enumerate(drives)
            print '%s - %s' % (drives.index(d)+1,d) # koj - print '%d - %s' % (d+1,drive)
        drive = raw_input('Select %s: ' % label)
        # koj - cast to int here inside a try/except. (except ValueError, continue).
        if not drive in str(range(0, len(drives)+1)): # koj - Then, no cast to string
            continue
        else:
            return os.path.join('/Volumes', drives[int(drive)-1]) # koj - no need to cast to int anymore

# safe copy
def safe_copy(src, dst):
    # koj - needs documentation
    dst_temp_name = dst+'_INCOMPLETE'
    try:
        copy2(src,dst_temp_name)
        if compare_hashes(src, dst_temp_name):
            try:
                os.rename(dst_temp_name, dst)
            except Exception as e:
                print 'Error trying to rename the file: ', e
        else:
            safe_copy(src, dst)
    except Exception as e:
        print 'Error trying to copy the file: ', e

# hash a file and return the hash string
def get_local_hash(filename, block_size=2**20):
    """
    Hashes a file using SHA1
    """
    # print 'Starting hash of %s at %s' % (filename, datetime.now().time())
    print 'Hashing', filename
    try: # koj - use a with statement to manage the file handle
        local_file = open(filename,'rb')
    except Exception as e:
        print 'Error while opening file for hashing: ', e
    hasher = sha256()
    while True:
        data = local_file.read(block_size)
        if not data:
            break
        hasher.update(data)
    # print 'Finished hash at %s' % datetime.now().time()
    result = hasher.hexdigest()
    local_file.close()
    return unicode(result)

def compare_hashes(file1, file2):
    # koj - needs documentation
    if get_local_hash(file1) == get_local_hash(file2):
        return True # koj - sure, but why not just return get_local_hash(file1) == get_local_hash(file2) ?

#main
# koj - did you really need that label?
def main():
    # get list of volumes
    drives = [d for d in os.listdir('/Volumes')]
    # ask user for origin drive
    origin = choose_drive(drives, 'Origin')
    origin_files = os.listdir(origin) # koj - filter here: (orig for orig in os.listdir(origin) if orig.endswith('.mpg'))
    # ask user for destination drive
    destination = choose_drive(drives, 'Destination')
    destination_files = os.listdir(destination)
    # for each file on origin, check if it exists on destination
    for of in origin_files:
        if of.endswith('.mpg'): # koj - see filter on line 76 above, don't need this.
            if of in destination_files:
                if compare_hashes(os.path.join(origin, of), os.path.join(destination, of)):
                    print 'already exists and is identical... skipping', of
                else:
                    print 'already exists but is different... copying', of
                    safe_copy(os.path.join(origin, of), os.path.join(destination, of))
            else:
                print 'does not exists... copying', of
                safe_copy(os.path.join(origin, of), os.path.join(destination, of))

if __name__ == "__main__":

    main()


Three ways to read a number for a BitInputStream I'm trying to learn how to write more readable code without introducing easily avoidable performance killers.

This is part of a BitInputStream Java class I'm experimenting with. There are code parts before and after this provided segment to read less than 8 bits from iBuffer if data is not aligned to bytes - that's why aNumberOfBits is needed to know how many bits have to be read later on.

I think variant 3 below is best when implemented in Java, but variant 1 may be worth the more complex formula for slightly better (theoretical) performance in C for realtime applications.

Variant 1:

int i = aNumberOfBits / 8;
aNumberOfBits -= i * 8;
for (; i > 0; --i) {
   iBuffer = iIs.read();
   if (iBuffer == -1) {
      throw new EOFException();
   }
   value = (value << 8) | iBuffer;
}

Variant 2 (obviously worse performant on most CPUs?):

for (int i = aNumberOfBits / 8; i > 0; --i) {
   iBuffer = iIs.read();
   if (iBuffer == -1) {
      throw new EOFException();
   }
   value <<= 8;
   value |= iBuffer;
   aNumberOfBits -= 8;
}

Variant 3:

for (int i = aNumberOfBits / 8; i > 0; --i) {
   iBuffer = iIs.read();
   if (iBuffer == -1) {
      throw new EOFException();
   }
   value = (value << 8) | iBuffer;
}
aNumberOfBits %= 8;

Now what about variant 2: should aNumberOfBits be decremented by 8 in the loop for a better understanding why it is decremented? (And isn't shifting value and then ORing the next part of data even more complicated to read than doing it in one step?)

If you are so concerned about performance, then you should run a benchmark.  I would bet that there is no appreciable difference in performance, as the task is going to be IO-bound rather than CPU-bound.  A much bigger impact on performance would be, for example, whether the input stream is buffered.  Therefore, you should just pick the code that looks the best.  I personally prefer a variant of variant 3.

It seems that you are interested in the values of value and aNumberOfBits after the loop.  Since i is unimportant, let's just ditch it.  Also, iBuffer seems to be a temporary variable, so its scope should be limited to the loop.

Finally, let's get rid of the Hungarian notation!

for (; bitCount >= 8; bitCount -= 8) {
    int b = input.read();
    if (b == -1) {
        throw new EOFException();
    }
    value = (value << 8) | b;
}

What might make a performance impact is reading a byte[] array at once instead of a byte at a time.  Handling possible buffer underruns correctly would be a pain, though, so I don't recommend it here.


Calculate sum, mean, sum of squares, and standard deviation of array elements Also, I've commented out a function I was trying to do to count the elements of an array; I realized that is not possible due to the fact that I won't be be able to return a NULL on an array.

Although this part of a beginner to C exercise, I'd like to know if there is anything I can do to improve my coding.

#include <stdio.h>
#include <math.h>

#define MAX_ITEM 1000

double x[MAX_ITEM];
int arr_count(double x[]);
double sum(double x[], int arr_count);
double mean(double sum, int arr_count);
double sum_sqr(double x[], int arr_count);
double st_dev(double sum_sqr, double mean, int arr_count);

/*
int arr_count(double x[]) {
  int i = 0;
  int count = 0;

  for (i = 0; i < MAX_ITEM; i++) {
    if (x[i] != NULL){
      count++;
    }
  }
  return count;
}
*/

double sum(double x[], int arr_count){
  int i = 0;
  double my_sum = 0;

  for (i = 0; i < arr_count; i++){
    my_sum += x[i];
  }
  return my_sum;
}

double mean(double sum, int arr_count) {
  return sum / arr_count;
}

double sum_sqr(double x[], int arr_count){
  int i = 0;
  double my_sum = 0;

  for (i = 0; i < arr_count; i++){
    my_sum += x[i] * x[i];
  }
  return my_sum;
}

double st_dev(double sum_sqr, double mean, int arr_count) {
  return sqrt(sum_sqr/ arr_count - mean * mean);
}

int main(void){
  int i;
  int num;
  int my_arr_count = 0;
  double my_sum = 0;
  double my_mean = 0;
  double my_st_dev = 0;

  printf("Enter the number of elements you want in the array between 0 and 1,000\n");
  scanf("%d", &num);

  //generate elements
  for (i = 0; i < num; i++) {
    x[i] = rand(time(NULL));
  }

  // print the generated elements
  printf("The elements are:\n");
  for (i = 0; i < num; i++){
    printf("[%d] %lf\n", i+ 1, x[i]);
  }

  // my_arr_count = arr_count(x);
  my_arr_count = num;
  my_sum = sum(x, my_arr_count);
  my_mean = mean(my_sum, my_arr_count);
  my_st_dev = st_dev(sum_sqr(x,my_arr_count), my_mean, my_arr_count);

  printf("There are %d elements in the random array", my_arr_count);
  printf("the Sum is %lf", my_sum);
  printf("The Mean is %lf", my_mean);
  printf("The Standard Deviation is %lf", my_st_dev);

}

Let the compiler help you

The first thing to do is to compile with a decent compiler and look at the warnings. With gcc -O -Wall -W:

dassouki.c: In function ‘main’:
dassouki.c:70: warning: implicit declaration of function ‘rand’
dassouki.c:70: warning: implicit declaration of function ‘time’
dassouki.c:90: warning: control reaches end of non-void function

You're missing two headers, stdlib.h and time.h, where the functions rand and time are declared. Once you add them you see another error:

small_fixes.c: In function ‘main’:
small_fixes.c:72: error: too many arguments to function ‘rand’

For now, to get code that compiles, remove the arguments to rand, it doesn't take any. I'll explain about rand below.

The last warning is there because main function returns an int value; you neglected to do that. If your implementation conforms to C99 (few do, and the one I compiled with doesn't), there is a special dispensation for the main function: you can omit the return statement, and it's as if you'd written return EXIT_SUCCESS. For utmost portability, return EXIT_SUCCESS to indicate success, or EXIT_FAILURE to indicate failure. On unix and Windows, EXIT_SUCCESS is 0 and EXIT_FAILURE is 1, though any nonzero value (positive and up to 255, though you should stick to small values) indicates failure. If you don't return a value from main (and aren't using a C99 compiler), the effect on most platforms is that your program returns whatever was in a particular register when main finishes executing, which is not good.

General style

Generally speaking, your code is well-organized and well-presented, congratulations. Here are a few minor improvements:

The array x doesn't actually need to be global, you can make it local to main. If you make it global, give it a longer name — global variables should be used sparingly and should be easily noticeable and searchable.
Don't use abbreviations in the names of global variables or functions. Call your functions square_sum or sum_of_squares, standard_deviation.
The proper type for an array length is size_t. On some machines, you can have arrays whose size doesn't fit into an int. Note that size_t is an unsigned type, which has the advantage that you won't run into the occasional difficulties of signed arithmetic, but you need to be careful with downwards loops (for (i=n; i>=0; i--) is an infinite loop if i is unsigned).

Output

You're missing newlines (\n) at the end of several printf calls.
The printf conversion specifier for a double is %f (or %e or %g), not %lf. Many implementations allow %lf as a synonym for %f, but this is not universal.
The printf conversion specified for a size_t is %z, but that only exists if your implementation conforms to C99, which is still not the norm today. In C89 (the prevalent standard today), your best bet is to cast to unsigned long, e.g.

printf("[%lu] %lf\n", (unsigned long)i, x[i]);

Why are you printing i+1 next to element number i? It's confusing. Print i and x[i] (as above).

Random number generation

rand() generates a random integer between 0 and RAND_MAX. On many platforms, RAND_MAX is 32767. Here, you're storing this into a floating point array, so it looks like you want to generate a random floating-point number. This is a difficult problem, and the solution depends on what distribution you want. On unix/POSIX platforms, there is a function drand48 which generates a random floating-point number in the range [0,1] with a uniform distribution. This issue is unrelated to the meat of your program, so you may be content with generating a random integer with rand().

A second issue is that rand() and friends use a pseudo-random number generator. This means that they will always return the same sequence of numbers if they are initialized in the same way. Initializing a random generator is called seeding it, and the function to seed the PRNG is srand(int). If you never call that function, your program will always fill the array with the same values. A common way of initializing the PRNG for testing is srand(time(NULL)); this will make your program use different values every second (on most machines).

Random number generation is a fairly complex topic; I recommend reading the clc FAQ, questions 13.15–13.20, especially Each time I run my program, I get the same sequence of numbers back from rand() and How can I generate floating-point random numbers?.

For the time being, add srand(time(NULL)); near the beginning of your main() function, and fix the call to rand().

Input validation

You read an integer with scanf. This function is convenient for quick tests but tricky to use correctly. It's difficult to react properly if the user enters garbage.

Since num should be a positive integer, make it an unsigned type. In C99, make it size_t and call scanf("%z", &num). In C89, make it unsigned long and call scanf("%lu", &num).

Perform at least some token validation of num. The number should be positive (if you want to allow 0, you need to add a special case to some of your calculations). And it must not be larger than the size of the array.

scanf("%lu", &num);
if (num == 0 || num >= sizeof(x)/sizeof(x[0])) {
  printf("Invalid number of elements, goodbye.\n");
  return EXIT_FAILURE;
}

sizeof(x)/sizeof(x[0]) (which can also be written sizeof(x)/sizeof(*x)) is an idiom to denote the number of elements in the array x: it's the size of the array divided by the size of one element. Note that this only works if x is an array, not if x is a pointer. Pointers to arrays don't contain any indication of the size of the array, and the size needs to be specified separately (hence your arr_count argument when you pass a pointer to the array to the various functions).


Generic 'temporary instance' class I've been reading about WeakPointer and WeakPointer<T> today, and it looks very useful.  Rather than just using it as-is though, I decided to write a wrapper around it that covers a common usage case for me.

Code as follows:

public class Temporary<T> where T : class
{
    Func<T> generator = null;
    WeakReference<T> reference = null;

    public T Value
    {
        get
        {
            return GetValue();
        }
    }

    public Temporary(T value)
        : this(value, null)
    { }

    public Temporary(Func<T> generator)
        : this(null, generator)
    { }

    public Temporary(T value, Func<T> generator)
    {
        reference = new WeakReference<T>(value);
        this.generator = generator;
    }

    public T GetValue()
    {
        if (reference == null)
            return null;
        T res;
        if (!reference.TryGetTarget(out res) && generator != null)
        {
            res = generator();
            reference.SetTarget(res);
        }
        return res;
    }
}

I've tested this against my use-case and it works as I expect - the garbage collector cleans out items with no active references, and they are re-instantiated at need.

I'm looking for critiques of the implementation and suggestions for improvements/additions.

It's pretty good, clean and simple code. Not a lot to critique really. A few minor things:

Some people (myself included) prefer to prefix private fields with _. This way it's easy to see that it's a field rather than a local variable (and gets rid of the this. in most cases).
You shouldn't have a public property and a public method which do the same thing. How is a programer supposed to know whether to use Value or GetValue? It's not obvious what the difference is or if there is one at all.
Not 100% sure about the null check in GetValue(). There is no code path where reference should ever be null. So it would actually indicate a bug if it were the case which you are hiding with this check. Consider removing the check or actually throwing an InvalidOperationException or similar instead. Detecting bugs early is important. Another option would be to look at Code Contracts to state the invariants of that method.
I have started to try and avoid null checks where possible by making sure that there is always an object. In your case this could be something like this:

public class Temporary<T> where T : class
{
    private static Func<T> NullGenerator = () => null;

    Func<T> generator = NullGenerator;
    WeakReference reference = null;

    public T Value
    {
        get
        {
            return GetValue();
        }
    }

    public Temporary(T value)
        : this(value, NullGenerator)
    { }

    public Temporary(Func<T> generator)
        : this(null, generator)
    { }

    public Temporary(T value, Func<T> generator)
    {
        if (generator == null)
            throw new ArgumentNullException("generator");
        reference = new WeakReference(value);
        this.generator = generator;
    }

    private T GetValue()
    {
        T res;
        if (!reference.TryGetTarget(out res))
        {
            res = generator();
            reference.SetTarget(res);
        }
        return res;
    }
}


Javascript XML Parser wrapper I created an XML wrapper to easily access XML data.
Please tell me what do you think about it.

Performance
Scalability
Anything else...

This is how you use it:

var xml = new Xml(dataString);
xml.load("UserEmail");
alert(xml.length + ", " + xml.getValueAt(0)); // Out: 2, jchen@contoso.com

XML source file:

<Users>
    <Users>
        <UserEmail>jchen@contoso.com</UserEmail>
        <UserPassword>
            BA56E5E0366D003E98EA1C7F04ABF8FCB3753889
        </UserPassword>
    </Users>
    <Users>
        <UserEmail>Kim@contoso.com</UserEmail>
        <UserPassword>
            07B7F3EE06F278DB966BE960E7CBBD103DF30CA6
        </UserPassword>
    </Users>
</Users>

Source:

function Xml(xmlString) {
    var parser = function() {
        if (typeof window.DOMParser != "undefined") {
            return (new window.DOMParser()).parseFromString(xmlString,
                    "text/xml");
        }
        else if (typeof window.ActiveXObject != "undefined"
                && new window.ActiveXObject("Microsoft.XMLDOM")) {
            var xmlDoc = new window.ActiveXObject("Microsoft.XMLDOM");
            xmlDoc.async = "false";
            xmlDoc.loadXML(xmlString);
            return xmlDoc;
        }
        else {
            throw new Error("XML parser not found");
        }
    };

    var data = parser(xmlString);
    var elements = null;
    this.length = 0;

    this.load = function(nodeName){
        elements = data.documentElement.getElementsByTagName(nodeName);
        this.length = elements.length;
    };

    this.getValueAt = function(index) {
        if(!elements || index >= this.length){
            return null;
        }
        var element = elements.item(index);

        return element.childNodes[0].data;
    };
}

From a quick read :

Xml seems like a bad name for your wrapper, you should consider something like xmlParser ?
I would allow access to data and elements by using this instead of var because you wrap so little of the XML parser API
this.length seems wrong ( the parser has no length), maybe loadedElementCount, but even that is pretty bad, I would just let the caller use elements.length.
I would return elements in this.load, since that is pretty much what the caller would need next.
You are not checking for falsey values of nodeName in this.load
I would not create a var element in getValueAt, I would just return elements.item(index).childNodes[0].data


Vectorizing a pixel-averaging operation in Numpy I am reading from a file containing some segments (irregular parcels of the image) and trying to average the entire segment to have one pixel value. This is the code I use:

band = band[:,:,0] #take the first band of the image

for i in range(numSegments): #for every segment
    tx = band[segments==i]   #select all the pixels in segment
    avg = np.average(tx)     #average the values
    band[segments==i] = avg  #write the average back into the image

I am omiting some transformation steps and code for printing running time from the snippet.

This takes quite sometime to run for even one band. Almost 1000 seconds. I was wondering if there is a way to vectorize this operation to make it faster?

Data:
Segment2009: an image of all the segments in the image.
This is what the segments look like:

Bands: 3000x3000 pixels, float32 values.

Full context:

workFolder = '/home/shaunak/Work/ChangeDet_2016/SLIC/003_lee_m0_alpha'
bandlist=os.path.join(workFolder,'bandlist.txt')
configfile = os.path.join(workFolder,'config.txt')

segmentfile = os.path.join(workFolder,'Segments2009')

#%% Load the bands -- can refer to subfolders in the bandlist
files = utilities.readBandList(bandlist)
destinations = []
for f in files:
    destinations.append(f.split('.')[0]+"_SP."+f.split('.')[1])

(lines,samples,bands) = utilities.readConfigImSizeBand(configfile)
#%% Superpixel file
segments = np.fromfile(segmentfile,dtype='float32')
segments = np.reshape(segments,(lines,samples))
numSegments = int(np.max(segments))

#%% simple avg
for idx,f in enumerate(files):
    band = np.fromfile(f,dtype='float32').reshape((lines,samples))
    start = time.time()
    for i in range(numSegments):
        tx = band[segments==i]
        avg = np.average(tx)
        band[segments==i] = avg

    band.tofile(destinations[idx])

I am writing the values back to the original after averaging. It is not necessary, also not the most expensive part -- and helps me visualize the results better so I kept it in. I used the following approach also:

avgOut = np.zeros((numSegments,bands),dtype='float32')
#avgOutJoined = np.zeros((lines,samples,bands),dtype='float32')

for i in range(numSegments):
    tx = band[segments==i]
    avgOut[i,:] = np.average(tx,axis=0)
#    avgOutJoined[segments==i,:] = np.average(tx,axis=0)

np.tofile(outputSeperated,avgOut)
#np.tofile(outputJoined,avgOutJoined)

Since not writing the averaged result back did not save much time, I kept it in.

The function scipy.ndimage.measurements.mean takes a labelled array and computes the mean of the values at each label. So instead of:

for i in range(numSegments):
    tx = band[segments==i]
    avg = np.average(tx)
    band[segments==i] = avg

you can write:

segment_mean = scipy.ndimage.measurements.mean(band, segments, range(numSegments))
band = segment_mean[segments]

Though I should add that the last operation here (the reconstruction of band) seems quite wasteful to me: all the information you need is already in the array segments and the array segment_mean (which has just one value per segment). Why do you then need to reconstruct the full array, filling each segment with its mean value? Could you not refactor the subsequent processing to use segments and segment_mean directly?

Update: you clarified the question to explain that writing the mean values back to band was just for visualization and is not an essential part of your application. In that case, you just need the one call to scipy.ndimage.measurements.mean.


Project Euler # 15 Lattice paths in Python Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down,

there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?

from time import time
from functools import lru_cache

def make_grid(grid_size):
    """Return a list of lists containing grid."""
    grid = tuple((0,) * (grid_size + 1) for _ in range(grid_size + 1))
    return grid

@lru_cache(None)
def count_lattice_paths(matrix, row, column):
    """Return number of all possible paths from top left to bottom right of n * n grid."""
    if row == 0 or column == 0:
        return 1
    return count_lattice_paths(matrix, row - 1, column) + count_lattice_paths(matrix, row, column - 1)

if __name__ == '__main__':
    start_time = time()
    g = make_grid(20)
    length = len(g) - 1
    print(count_lattice_paths(g, length, length))
    print(f'Time: {time() - start_time} seconds.')

Performance Counter

When you use time.time(), you are getting the number of seconds since January 1, 1970, 00:00:00 UTC.  This value is (as I'm writing this) around 1565401846.889736 ... so has about microsecond resolution.

When you use time.perf_counter(), you are getting "a clock with the highest available resolution to measure a short duration".  As I was writing this, I retrieved the value 53.149949335 ... so it has approximately nanosecond resolution.

For profiling code, you want the highest resolution timer at your disposal ... so eschew time.time() in favour of time.perf_counter().

Timed Decorator

Since you are doing a lot of performance measurements in your exploration of Project Euler, you should package up the performance measurement code in a neat little package that can be easily reused.  You were given a decorator for this in an answer to your "Time & Space of Python Containers" question.  But here it is again, slightly modified for just doing timing:

from time import perf_counter
from functools import wraps

def timed(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = perf_counter()
        result = func(*args, **kwargs)
        end = perf_counter()
        print(f"{func.__name__}: {end-start:.6f} seconds")
        return result
    return wrapper

You can decorate a function with @timed, and it will report how long that function takes.  You can even decorate multiple functions!

And it moves the timing code out of your if __name__ == '__main__': block.

Use Test Cases

Project Euler 15 gives you the answer to a 2x2 lattice grid.  You should run that test case in your code, to give yourself confidence you are getting the correct answer.  Eg)

@timed
def count_lattice_paths(rows, cols):
    # ...

def pe15(rows, cols):
    paths = count_lattice_paths(rows, cols)
    print(f"{rows} x {cols} = {paths} paths")

if __name__ == '__main__':
    pe15(2, 2)
    pe15(20, 20)

A few import points.

The if __name__ == '__main__': block clearly runs two cases

a 2x2 lattice, and
a 20x20 lattice.

The pe15(rows, cols) calls count_lattice_paths(rows, cols) to get the result, and then prints out the result with a description of the case.
The count_lattice_paths(rows, cols) is the @timed function, so the time spent printing the result report in not counted in the timing.
The count_lattice_paths() method can be generalized to work with an NxM lattice; it doesn't need to be square, even though the problem asked for the result for a square lattice and gives a square lattice test case.

Count Lattice Paths (without a cache)

As you noticed, a 2x2 lattice is better represented by a 3x3 grid of nodes.

It should be obvious there is only 1 way to reach every node along the top edge.
It should be obvious there is only 1 way to reach every node along the left edge.

So, our initial array of counts would look like:

1 1 1
1 . .
1 . .

At each node (other than the top edge and left edge), the number of paths is equal to the sum of the paths to the node above it and the paths to the node to the left of it.  So, there are 1+1 = 2 paths to the node at 1,1:

1 1 1
1 2 .
1 . .

Since the value at each point is defined entirely by the values above and left of it, we can directly loop over each node, and compute the required values, and finally return the value at the lower right corner of the grid.  We don't even need to store the entire grid; we can compute the next row from the current row.

@timed
def count_lattice_paths(rows, cols):
    steps = [1] * (cols + 1)
    for _ in range(rows):
        for i in range(cols):
            steps[i+1] += steps[i]
    return steps[-1]


Generation of all numbers of arbitrary length and base quux (['0'..9'] ++ ['A'..F']) 2 generates hexademical numbers of length 2 (with leading zeros), but it's obviously possible to generate any base and any length.

quux digits length = iterate foo return !! length $ [] where
    foo bb aa = map (: aa) digits >>= bb

Can this code be simplified, while retaining the idea of iterating in list monad?

It turns out that this is exactly what replicateM does in the [] monad. For the sake of completeness, let's look at exactly how replicateM works.

replicateM :: Monad m => Int -> m a -> m [a]
replicateM n x = sequence (replicate n x)

replicate :: Int -> a -> [a]
replicate n x = [ x | _ <- [1..n] ]

replicateM turns out to just pass off the heavy lifting to replicate and sequence. replicate is pretty simple, so the interesting part happens in sequence:

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (x:xs) = do
    x'  <- x
    xs' <- sequence xs
    return (x' : xs')

And in fact, that's exactly what leaning on the [] monad instance for iteration looks like. A couple of binds and a return.


Improving sub select query on two tables without relationship I am trying to return the count of employees by salary band and can return data using the following sql but wondered if this was the most efficient way of achieving it?

I know creating a join between the tables would be better but that is not possible in this instance.

select *, (select count(*) from EmployeeSalary where salary between minsalary and maxsalary) from SalaryBands

It's odd you say it is not possible, because it is possible, right?

select ID, Name, MinSalary, MaxSalary, count(Salary) as SalaryCount
from SalaryBands
left outer join EmployeeSalary on salary between minsalary and maxsalary
group by ID, Name, MinSalary, MaxSalary

Now, I am not sure I would actually use that... I would actually go with your query, but transformed to be more readable...

select ID,
       Name,
       MinSalary,
       MaxSalary,
       (select count(*)
        from EmployeeSalary
        where salary between minsalary and maxsalary
       ) as BandCount
from SalaryBands


Project Euler - Shortening Problem 2 You might have read my question on shortening my code to a one-liner for Problem 1. So, I was wondering, is there any more tricks of the trade to shorten my Problem 2 solution:

fib = [0, 1]
final = 1
ra = 0
while final < 4000000:
    fib.append(fib[-1] + fib[-2])
    final = fib[-1]
fib.pop()
for a in fib:
    if a%2 == 0:
        ra += a
print(ra)

Down to one line??
This is the official Problem 2 question:Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Thanks!

The first few are probably OK, but you really shouldn't be publishing solutions to Project Euler problems online: don't spoil the fun for others!

This said, there are several things you could consider to improve your code. As you will find if you keep doing Project Euler problems, eventually efficiency becomes paramount. So to get the hang of it, you may want to try and write your program as if being asked for a much, much larger threshold. So some of the pointers I will give you would generally be disregarded as micro optimizations, and rightfully so, but that's the name of the game in Project Euler!

Keeping the general structure of your program, here are a few pointers:

Why start with [0, 1] when they tell you to go with [1, 2]? The performance difference is negligible, but it is also very unnecessary.
You don't really need several of your intermediate variables.
You don't need to pop the last value, just ignore it when summing.
An important thing is that in the Fibonacci sequence even numbers are every third element of the sequence, so you can avoid the divisibility check.

Putting it all together:

import operator

def p2bis(n) :
    fib = [1, 2]
    while fib[-1] < n :
        fib.append(fib[-1] + fib[-2])
    return reduce(operator.add, fib[1:-1:3])

This is some 30% faster than your code, not too much, but the idea of not checking divisibility, but stepping in longer strides over a sequence, is one you want to hold to:

In [4]: %timeit p2(4000000)
10000 loops, best of 3: 64 us per loop

In [5]: %timeit p2bis(4000000)
10000 loops, best of 3: 48.1 us per loop

If you wanted to really streamline things, you could get rid of the list altogether and keep a running sum while building the sequence:

def p2tris(n) :
    a, b, c = 1, 1, 2
    ret = 2
    while c < n :
        a = b + c
        b = c + a
        c = a + b
        ret += c
    return ret - c

This gives a 7x performance boost, not to mention the memory requirements:

In [9]: %timeit p2tris(4000000)
100000 loops, best of 3: 9.21 us per loop

So now you can compute things that were totally unthinkable before:

In [19]: %timeit p2tris(4 * 10**20000)
1 loops, best of 3: 3.49 s per loop

This type of optimization eventually becomes key in solving more advanced problems.


Find first questions with answers posted within 24 hours So, sᴉɔuɐɹɥԀ suggested I write a SEDE query to find first questions with answers posted within 24 hours, and here it is:

WITH QData(OwnerId, CDate)
AS
(
  SELECT
  Q.OwnerUserId [OwnerId]
  ,MIN(Q.CreationDate) [CDate]
  FROM Posts Q
  WHERE Q.PostTypeId = 1 AND Q.OwnerUserId IS NOT NULL
  GROUP BY Q.OwnerUserId
),

FirstQs(QCreationDate, QPostId, QUserId)
AS
(
  SELECT
  CDate [QCreationDate]
  ,Q.Id [QPostId]
  ,OwnerId [QUserId]
  From QData JOIN Posts Q On (Q.CreationDate = CDate AND Q.OwnerUserId = OwnerId)
  WHERE Q.PostTypeId = 1
  GROUP BY OwnerId, Q.Id, CDate
),

FirstQsA(ACreationDate, APostId, AParentId)
AS
(
  SELECT
  MIN(p.CreationDate) [ACreationDate]
  ,MIN(p.Id) [APostId]
  ,p.ParentId [AParentId]
  FROM Posts p, FirstQs
  WHERE (p.PostTypeId = 2 AND p.ParentId = QPostId)
  GROUP BY p.ParentId
)

SELECT QUserId [User Link]
,MIN(QCreationDate) [QCreationDate]
,MIN(ACreationDate) [ACreationDate]
,QPostId[Post Link]
,APostId[Post Link]
FROM
  FirstQs JOIN FirstQsA ON QPostId = AParentId
  WHERE DATEDIFF(HOUR, QCreationDate, ACreationDate) <= 24
GROUP BY QUserId, QPostId, APostId
ORDER BY QUserId

The query can be found here: First Questions with Answers Posted Within 24 Hours.

I have to compliment you on how well your query reads. Your aliases are short enough not to be a PITA to reference, yet descriptive enough to not have to scratch your head about what they mean.

Your CTEs are well formatted, pretty easy to read and have good names. Overall, if I was a DBA and saw that in my code base, I'd think the person who wrote it put some work into making it good.

Well done.

Now for a few things to make it even better.

Magic Numbers

Here:

WHERE Q.PostTypeId = 1
-- and later
WHERE (p.PostTypeId = 2

1 and 2 are primary keys in the PostTypes table. This is fine for someone who knows the schema already, but for someone who sees this for the first time, they will have to query the table with those keys to know what they actually mean. So, I recommend using variables, like so:

DECLARE @QuestionPostType INT;
SET @QuestionPostType = 1;
DECLARE @AnswerPostType INT;
SET @AnswerPostType = 2;

Then just reference them by name in your query:

WHERE Q.PostTypeId = @QuestionPostType
-- and later
WHERE (p.PostTypeId = @AnswerPostType

Proliferation of CTEs

It's easy to get lost in data sets in SQL, and while yours works fine, I think it could be simplified a bit. Take for instance:

WITH QData(OwnerId, CDate)
AS
(
  SELECT
  Q.OwnerUserId [OwnerId]
  ,MIN(Q.CreationDate) [CDate]
  FROM Posts Q
  WHERE Q.PostTypeId = 1 AND Q.OwnerUserId IS NOT NULL
  GROUP BY Q.OwnerUserId
),

You have a whole CTE following to extract basically this:

(Q.CreationDate = CDate AND Q.OwnerUserId = OwnerId)

You could just adapt that in your first CTE and simplify it, kind of like this:

WITH QData(OwnerId, CDate)
AS
(
  SELECT
  Q.OwnerUserId [OwnerId]
  ,MIN(Q.CreationDate) [CDate]
  FROM Posts Q
  WHERE Q.PostTypeId = 1 AND Q.OwnerUserId IS NOT NULL
  AND (Q.CreationDate = CDate AND Q.OwnerUserId = OwnerId)
  GROUP BY Q.OwnerUserId
),

Take advantage of joins

Many think of joins as basically just linking keys between one table and another. But, you can use joins to filter data, and keep related conditions/filters together in one join, rather than splitting them up in a bunch of CTEs or where clauses.

For example, you could extract some of the Q & A logic into a join. Whether or not it is desirable, it-depends. But for the sake of example, this:

FROM
  FirstQs JOIN FirstQsA ON QPostId = AParentId

...along with your other filters which are included in your CTEs, could be something like:

FROM
  FirstQs
  JOIN FirstQsA
    ON QPostId = AParentId
   AND Q.PostTypeId = 1 -- or @QuestionPostType
   AND A.PostTypeId = 2 -- or @AnswerPostType


Passing anonymous functions and getting variables from an outer scope I'm doing something quite strange.  I'm trying to create a tiny system for creating templates inline in PHP, so that I can refactor by creating multiple templates in the original script, and eventually move the templates to separate scripts.

Here's the silly/basic template library that just calls an anonymous function that gets passed in after some HTML header stuff, and then calls a footer:

<?php
// System for using simple, native php templates.

// TODO: Put this in a namespace to keep it clean and separate.

function display_page_inline($templates, $options, $data){
    $title = @$options['title'];
    echo "<title>".$title."</title>";

    if(is_array($templates)){
        foreach($templates as $template_function){
            $template_function($data);
        }
    } else{
        $template($data); // Call & display the template.
    }

    echo "
Footer
";
    echo "";
}

?>

Here's where it's going to get strange.  In the scripts I'm creating anonymous functions, saved to variables, and then passing them to the template library for outputting.  To avoid having to call an array element (and check whether the element exists each time), I'm trying to export the array passed in to get standard variables in the template (e.g. $name instead of $data_array['name']).  Is there a way to abstract away this behavior in PHP?

<?php
require_once('core.php');

// Inclusion of the template library
require_once('../core/inline_templates.php');
// Initialization Logic
$title = 'Bob';

// Decide what will be able to be output and put it into an array to pass to the template
$template_output_variables = array('name'=>'no name');

// The page gets displayed at the bottom.

// =================== Templates ========================================
// Todo: Potentially namespace the stuff here.
// Define the anonymous template function here, has html and such in native php here.
$contact_us = function ($template_output_variables=null){
    extract($template_output_variables); // Pull the variables.
    // Leave php in the template function.
    ?>

    Hello World Body Text, Hello <?php h($name);?>.

    <?php
}; // End of template function declaration.

$killer_section = function ($data=null){
    extract($data); // Pull the variables.
    ?>
    Breaking news, There is a killer among us.

    <?php
}; // End of killer section anon. function.

// Display the page.

// call & display the template via delayed execution, display it within a pre-set head and footer.
display_page_inline($templates=array($contact_us, $killer_section), $options=array('title'=>$title), $template_output_variables);

?>

It's very strange, I know, but I'm trying to do a whole new approach to refactoring, and make use of some new PHP 5.3 features while doing it.  The goal is to have inline templates that I can put in any script, as many as I want, and move anywhere I want later, or merge the templates, etc.

Something like this would get you most of the way there:

<?php
function h($val) {
    echo $val;
}

function template_function($template_body) {
    return function(array $template_output_variables = null) use ($template_body) {
        if ($template_output_variables !== null) {
            extract($template_output_variables);
        }
        $contents = eval('?>'.$template_body.'<?php');
        echo $contents;
    };
}

$contact_us = template_function('
    <body>
    Hello World Body Text, Hello <?php h($name);?>.
    </body>'
);

$contact_us(array('name' => 'Johnny Boy'));

But it's evil, and you will likely end up with very odd, very hard-to-debug errors once your templates are of reasonable size/complexity. It's an interesting idea though -- if you pursue it, make sure you have a thorough set of test cases ;)

The easiest way to clean it up, IMO, would be to do away with allowing raw php in the templates. I'm pretty partial to Twig, you may be able to find some inspiration there.


High execution time to count overlapping substrings I was doing this HackerRank problem which basically boils down to counting overlapping substrings in a string. I used this solution from StackOverflow to build this program -

def overlapping_occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count

def find_health(start, end, d, genes, gene_health):
    hv = 0
    beneficial = set(genes[start:end+1])
    for b in beneficial:
        # b is just a single letter, so no possibilities of overlapping
        if len(b) == 1:
            occurrences = d.count(b)
        else:
            occurrences = overlapping_occurrences(d, b)
        total_value = sum(gene_health[b])
        hv += total_value*occurrences
    return hv

if __name__ == '__main__':
    n = int(raw_input())
    genes = list(raw_input().split())
    health = list(raw_input().split())
    gene_health = {}
    for idx in xrange(n):
        try:
            gene_health[genes[idx]].append(int(health[idx]))
        except:
            gene_health[genes[idx]] = []
            gene_health[genes[idx]].append(int(health[idx]))
    s = int(raw_input())
    health_values = []
    for _ in xrange(s):
        start, end, d = raw_input().split()
        health_values.append(find_health(int(start), int(end), d, genes, gene_health))
    low = min(health_values)
    high = max(health_values)
    print "%d %d" % (low, high)

I've used a dictionary gene_health because as the first example in the problem description shows, a single gene can have multiple different values, so I store all those values in a list which I sum over to get the total_value.

My problem is that this program takes a very long time and exceeds the time limit on most of the test cases. I do think that this algorithm is CORRECT, since for the few test cases where it doesn't time out, it gives the correct answer. So I'm just looking for a way to speed up the program, and I think the only place where any speedups can be performed is in the overlapping_occurrences method.

I've searched for other similar questions on StackOverflow but all of them use regex but regex will make it even slower (I think).

Any suggestions or poking in the right direction will help. Thank you!

overlapping_occurrences has \$O(MN)\$ complexity where \$M\$ and \$N\$ are the sizes of the string and the substring respectively. You can reduce it to \$O(M+N)\$ using KMP algorithm. However, looking at the constraints, I feel that even that might not be sufficient - the highest score for the problem is only 50.


Trie Data Structure Implementation in C++11 using Smart Pointers This implementation is part of my open source project forest.

I wrote the following header file to implement a trie data structure that supports inserting and searching strings consisting of 26 lower-case letters of the English alphabet. I am looking forward to hearing your opinion about this implementation and any suggestions/fixes you may have.

/**
 * @file trie.h
 */

#ifndef TRIE_H
#define TRIE_H

#include <iostream>
#include <string>
#include <memory>

#define ALPHABET_SIZE 26

/**
 * @brief The forest library namespace
 */
namespace forest {
  namespace trie {
    /**
     * @brief trie node struct
     */
    struct node {
      std::shared_ptr<node> children[ALPHABET_SIZE];
      bool end;
      /**
       * @brief Constructor of a trie node
       */
      node() {
        this->end = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
          this->children[i] = NULL;
        }
      }
    };
    /**
     * @brief trie class
     */
    class tree {
    private:
      std::shared_ptr<node> root;
    public:
      tree() {
              root = std::make_shared<node>();
      }
      /**
       * @brief Inserts the given key into the trie
       * @param key The key to be inserted
       * @return void
       */
      void insert(const std::string &key) {
        std::shared_ptr<node> n = root;
        for (int i = 0; i < key.length(); i++) {
          int index = key[i] - 'a';
          if (n->children[index] == nullptr) {
            n->children[index] = std::make_shared<node>();
          }
          n = n->children[index];
        }
        n->end = true;
      }
      /**
       * @brief Searches for the given key in the trie
       * @param key The key to be inserted
       * @return true if key exists in the trie and false otherwise
       */
      const bool search(const std::string &key) {
        std::shared_ptr<node> n = root;
        for (int i = 0; i < key.length(); i++) {
          int index = key[i] - 'a';
          if (n->children[index] == nullptr) {
            return false;
          }
          n = n->children[index];
        }
        return (n != nullptr && n->end == true);
      }
    };
  }
}

#endif

Your include guard might clash with another file.  After all, you used an outer namespace because the name is not unique enough; the same is true for the header.  Suggest you use a UUID for that, and also #pragma once .  (Personally, I chose to use the pragma only with the idea that if I ever need guards they can be mechanically generated, all correctly.  But all the major platforms take the pragma so I never needed guards.)

#define ALPHABET_SIZE 26

Noooo…  Don’t use #define for simple constants, especially in a header file!

Let’s look at your node constructor:

(and what's with all the this-> on every member access?)

this->end = false;

You should not be assigning initial values in the constructor.  You should initialize things.  Here, you can simply use an inline initializer on the data member declaration, and be done with it.

// data member
bool end = false;

Continuing with the node constructor:

for (int i = 0; i < ALPHABET_SIZE; i++) {
      this->children[i] = NULL;

Wow!  Lots to go over here.

First, don’t use NULL.  Not ever!  If you are writing in C++11, it is dead and should be forgotten about.

Second, don’t write legacy for loops to go over a collection.  Use the range-for form instead.

for (auto el : children)
    el.reset();

Third, don’t write loops at all if you can use algorithms.

std::fill (std::begin(children), std::end(children), nullptr);

but I don’t like the need to give two separate points like that when I just want the whole thing.  The std algorithms are behind in this respect.  But, we have Boost as a proving ground for library stuff that we want to add to the standard or simply make commonly used:  (see doc page)

boost::fill (children, nullptr);

But… just don't!  A shared_ptr is automatically initialized to the empty state, which means the constructor is already doing this before the body of your code is run!

So, add the inline initializer for end, and then delete the entire constructor.

Now look at the constructor for tree.

Same thing:  don’t assign in the body, but initialize members.  The inline member init will work fine here.

// data member of tree
std::shared_ptr<node> root = std::make_shared<node>();

and then delete the whole tree() constructor function.

tree::insert

In C++ (unlike C) the style is to put the * or & of the type with the type, not the name being defined.  So write string& name not string &name.

Use auto (almost everywhere).

auto n = root;

For the for loop, the same comments as before.  Stop thinking of index numbers into an array or other collection that then need to be subscripted.  Rather, think about iterator positions in any kind of collection, or constructs that do the traversal and just give you a reference to the item to work on.

So, no i.

for (auto ch : key) {

Don’t compare pointers (or smart pointers) against null.  They have a truth value that works for this directly.

Remember you can make a reference (an alias) to any part of your data, so don’t repeat children[index] three times.

auto& slot = n->children[index];
if (!slot)  slot = make_shared<node>();
n= slot;

Similar for search.
Returning a const bool doesn’t do anything; just return bool.
At the end of that function, testing against true is just silly.  It is already a bool!  What value does it hold?  true.

Also, not explicitly testing against nullptr here helps you see how the idiom works well for guarding the real test:

return n && n->end;

Oh, and don’t put redundant parenthesis around return values.

BTW, your algorithm and approach is quite sound.  It’s only the C++ language fluency and idioms that I commented on.


Uint8Array indexOf method that allows to search for byte sequences Uint8Array.prototype.indexOfMulti = function(searchElements, fromIndex) {
    fromIndex = fromIndex || 0;

    var index = Array.prototype.indexOf.call(this, searchElements[0], fromIndex);
    if(searchElements.length === 1 || index === -1) {
        // Not found or no other elements to check
        return index;
    }

    for(var i = index, j = 0; j < searchElements.length && i < this.length; i++, j++) {
        if(this[i] !== searchElements[j]) {
            return this.indexOfMulti(searchElements, index + 1);
        }
    }

    return (i === index + searchElements.length) ? index : -1;
};

It works fine but I wonder if I missed any important case or if anyone sees a way to optimize this.

First things first. This code is fairly difficult to read. indexOfMulti could mean

You're searching for any one of multiple values.
You're searching for all occurrences of a value (less likely -- might be indicesOf or findAll).
You're searching for the first occurrence of a sequence.

I'd name this something like find, findSequence, findSubstring. I'd also rename searchElements to something like needle, targetSequence.

You have two different efficiency issues here.

First, if this code is running in an implementation without tail-call optimization (I can't tell if any do, much less whether it's common), your memory usage may blow up whenever the first part of needle is common in your haystack but the full needle isn't found, because you'll blow up the stack. Better to implement this non-recursively.

Second, you've chosen the naive string search algorithm (see http://en.wikipedia.org/wiki/String_searching_algorithm). It will work fine when needle and haystack are small, or when prefixes of needle are rare in haystack, but it will be quite slow on the following example:

haystack = "aaaaaaaaaaaaaaaaaaaaab";
needle = "aaaab";
haystack.findSequence(needle);

You'd be better off selecting one of the other algorithms in that wikipedia article; a good choice is Boyer-Moore.


Managing IDs using AVL trees In a txt file there are IDs and next to them there are their neighbours like this:

1  1
1  2
1  3
2  1
2  4
2  8
3  5

Using AVL trees I store the IDs in one AVL tree and for every ID in this AVL
I make another AVL tree in which I store its neighbours.In the end I make another txt file that in every line has an ID , its number of neighbours and then its neighbours.Using the above example the output txt is :

1 3 1 2 3
2 2 1 4 8
3 1 5

I managed to make it work but the problem is that when I have many IDs the program gets very slow because I suspect there are too many IDs in the first AVL
tree to search insert and balance everytime.Is there any shortcut to make it faster?
Some of the functions I used :

Node* AVLTree::search(Node *node, int ID)
{
    if(node == NULL)
    {
        return NULL;
    }
    if(node->ID == ID)
    {
        return node;
    }
    else if(node->ID < ID)
    {
        return search(node->right, ID);
    }
    else
    {
        return search(node->left, ID);
    }
}

void AVLTree::balance(Node *&node)
{
    if (node == NULL)
    {
        return;
    }
    int height_diff = heightDifference(node);
    if (height_diff > 1)
    {
        if( heightDifference(node->left) > 0)
        {
            node = left_rotation(node);
        }
        else
        {
            node = left_right_rotation(node);
        }
    }
    else if (height_diff < -1)
    {
        if (heightDifference(node->right) > 0)
        {
            node = right_left_rotation(node);
        }
        else
        {
            node = right_rotation(node);
        }
    }
    balance(node->left);
    balance(node->right);
}

Node* AVLTree::insert(Node *node, int ID)
{
    if(node == NULL)
    {
        node = newNode(ID);
        size++;
        return node;
    }
    else if(node->ID > ID)
    {
        node->left = insert(node->left, ID);
        balance(node);
    }
    else if(node->ID < ID)
    {
        node->right = insert(node->right, ID);
        balance(node);
    }
    return node;
}

int AVLTree::height(Node *node)
{
    if (node != NULL)
    {
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        int maxHeight = max(leftHeight, rightHeight);
        return maxHeight + 1;
    }
    else
    {
        return 0;
    }
}

int AVLTree::heightDifference(Node *node)
{
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return leftHeight - rightHeight;
}

Calling the number next to the ids "neighbours" is confusing, actually the ids are more like keys and the second parameter can be considered a value?

You have an AVL tree listing all the keys, and for each key, an AVL storing all the values.

You have 350000 ids with 50 values for each key. 50 is a small number, making it not completely necessary to use an AVL tree. A simple array or vector could work, it would remove a lot of the overhead of dynamically allocating nodes for each new value.

AVL trees are supposed to do every basic operation in \$O(log(n))\$, meaning insert, search, delete. Meaning, individual operations should still be very fast even after 350000 IDs are inserted (for reference, \$log_2(350000)\$ ~ 18).

The reason your program slows down should be the insert method in the AVL tree. It balances the tree after every insertion, starting from the root. Which in turn calculates the height difference and the height of both subtrees recursively:

int AVLTree::height(Node *node)
{
    if (node != NULL)
    {
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        int maxHeight = max(leftHeight, rightHeight);
        return maxHeight + 1;
    }
    else
    {
        return 0;
    }
}

This function is actually \$O(n)\$ since it goes recursively through each child of node. Meaning, each time you get the height of a node when rebalancing the tree, it will be slow.

The solution is to keep track of the height of each node. It could look something like this for the insert function:

Node* AVLTree::insert(Node *node, int ID)
{
    if(!node) //if you want to use a comparison to null here, use nullptr instead of NULL
    {
        node = newNode(ID); //node->height should be 0 at init
        size++;
        return node;
    }

    if (node->ID == ID) {
        return node;
    }

    if(node->ID > ID)
    {
        node->left = insert(node->left, ID);
    }
    else if(node->ID < ID)
    {
        node->right = insert(node->right, ID);
    }

    updateHeight(node);
    balance(node);

    return node;
}

Then the updateHeight function could be like this:

void AVLTree::updateHeight(Node *node) {
    if (!node) {
        return;
    }

    node->height = max(height(node->left), height(node->right)) + 1;
}

And the height function would be simplified and non-recursive:

int AVLTree::height(Node *node)
{
    if (!node) {
        //since the value of a leaf is 0, the value of a non existing-node is -1
        //if you want 0 here the value for a new node should be 1
        return -1;
    }
    return node->height;
}

The node's height is only updated for nodes that are traversed during the insert function, so this operation only has a complexity of \$O(log(n))\$.

Of course you also have to update the height manually when rotating the nodes or deleting the nodes, by calling updateHeight() on the appropriate nodes. (Note that children have to have their heights updated before the parents).

There is also another area in the balance function that introduces complexity:

balance(node->left);
balance(node->right);

It will traverse the whole subtree and be applied to every node in the tree, causing a complexity of \$O(n)\$. In the insert function balance is already applied to all the ancestry of a node that gets a new child, so in the balance function you should only do recursive calls when necessary.

I'm not sure the calls to balance the children are necessary if the rotations are properly done (maybe they are) but at least they are not necessary when the current node is already balanced, so changing the beginning of the balance function to this will reduce its complexity to \$O(log(n))\$:

void AVLTree::balance(Node *&node)
{
    if (!node)
    {
        return;
    }
    int height_diff = heightDifference(node);
    if (abs(height_diff) <= 1)
    {
        return;
    }

    //...

As it will stop going down the subtree if it is balanced.

No comments on the rest of your code, it's very readable and I wouldn't sacrifice that over small optimizations when they are not needed.

PS: If you keep this:

balance(node->left);
balance(node->right);

At the end of the balance function, don't forget to call updateHeight(node) as the height of the children have potentially changed. But those two calls seem weird to me as balancing children can change their height and potentially unbalance the current node again.