Reimplementation of Underscore _.throttle I've built a function that mimics _.throttle (returns a new, throttled version of the passed function, that, when invoked repeatedly, will only actually call the original function at most once per every wait milliseconds).

I would like to know what you think about my code, especially if the code is clean and essential and if i'm managing arguments correctly.

function throttle(func, interval){
   var toExecute = true,
       queue = false;
   var result;
   return function doThrottle(){
       var args = Array.prototype.slice.call(arguments);

       if(toExecute){
           toExecute = false;
           queue = false;
           result = func.apply(null, args);
           startTimer(interval);
       } else {
           queue = true;
       }

       function startTimer(interval){
           setTimeout(function(){
               toExecute = true;
               if(queue){
                   result = func.apply(null, args);
               }
            }, interval);
       }

       return result;

   }
}

Your code isn't quite right, as far as I can tell. In the snippet below, you can compare it to Underscore's version.

function throttle(func, interval){
   var toExecute = true,
       queue = false;
   var result;
   return function doThrottle(){
       var args = Array.prototype.slice.call(arguments);

       if(toExecute){
           toExecute = false;
           queue = false;
           result = func.apply(null, args);
           startTimer(interval);
       } else {
           queue = true;
       }

       function startTimer(interval){
           setTimeout(function(){
               toExecute = true;
               if(queue){
                   result = func.apply(null, args);
               }
            }, interval);
       }

       return result;
   }
}

var count = 0;

function printSomething(elementId, count) {
  document.getElementById(elementId).innerHTML += String(count) + "
";
}

var opThrottledPrint = throttle(printSomething, 2000),
    underscoreThrottledPrint = _.throttle(printSomething, 2000);

function invoke() {
  count++;
  opThrottledPrint("op", count);
  underscoreThrottledPrint("underscore", count);
}

<button type="button" onclick="invoke()">Click me a few times</button>

Printing is throttled by 2 seconds

    OP's code
    Underscore

Three things to note:

If you click twice in row, your throttler does introduce the right delay, but it reuses arguments from the first call when executing the throttled call. So in the snippet's example, your function will cause the same number to be printed twice, despite being called with a new number on each click. I'd consider this a pretty major bug.

The reason for all of this is the curious structure of your code. You set a timeout that's poised to repeat the current call - unless queue is false when the timer runs out. So your code actually creates a sort of "conditional repeater" rather than a throttler.

Again, this is just a strange construction.
If you click twice, and then click a third time as soon as both of the previous calls have executed, the third call executes immediately. In other words, if nothing's "queued" the call is handled immediately, even if it's been less than the delay-time since the most recent invocation.

To attempt some ascii illustration of the behavior of the snippet above:

Time ------->

click . click . . . . . . . . . . . . . . . . . . . click . . . .
  |        \__________________________________        |
  |                      timeout              \       |
print . . . . . . . . . . . . . . . . . . . print . print . . . .
                        ^                         ^
                  Correct delay               No delay!

Again, I'd consider this a major bug since your function is not actually throttling anything in that case.
Returning anything from the throttled function is pointless. Sure, if it executes immediately it will return whatever the wrapped function returns. But if it doesn't execute immediately due to throttling, things get weird.

The wrapper function itself returns immediately; if you set a timeout, it doesn't wait for it to run out. So setting result in the timed function happens long after result has already been returned.

But because result is a closure variable, it's actually worse than a common async mistake: If your call gets delayed/throttled, the previous invocation's return value gets returned.

Like the bug with reusing arguments, this is quite bad if you're expecting to be able to use return values. But, as mentioned, it's impossible to consistently provide return values, when the function may just return before the throttled code has run. So you're better off not returning anything at all.

So with your code, you get:

Delayed repetition instead of actual throttling.
Risk of no throttling at all.
Risk of incorrect return values.

Not really ideal.

I'd do something like this:

function throttle(func, delay) {
  var timer = null,
      queued = null;

  // simple function to introduce a delay
  function delay() {
    timer = setTimeout(resume, delay);
  }

  // end-of-delay handler
  function resume() {
    timer = null;
    if(queued) queued(); // call the queued invocation, if any
    queued = null;
  }

  return function () {
    var args, invocation;

    if(queued) return; // if something's already queued, stop here

    // otherwise get the args...
    args = [].slice.call(arguments);

    // and create a function to apply them
    invocation = function () {
      func.apply(null, args);
      delay(); // make sure any invocation will always cause a delay
    };

    if(!timer) {
      // if there's no timer, invoke immediately
      invocation();
    } else {
      // otherwise enqueue for later
      queued = invocation;
    }
  }
}

You can try it out below. It seems to behave the same as Underscore's.

function throttle(func, interval){
   var toExecute = true,
       queue = false;
   var result;
   return function doThrottle(){
       var args = Array.prototype.slice.call(arguments);

       if(toExecute){
           toExecute = false;
           queue = false;
           result = func.apply(null, args);
           startTimer(interval);
       } else {
           queue = true;
       }

       function startTimer(interval){
           setTimeout(function(){
               toExecute = true;
               if(queue){
                   result = func.apply(null, args);
               }
            }, interval);
       }

       return result;
   }
}

function throttle2(func, delay) {
  var timer = null,
      queued = null;

  function delay() {
    timer = setTimeout(resume, delay);
  }

  function resume() {
    timer = null;
    if(queued) queued();
    queued = null;
  }

  return function () {
    var args, invocation;

    if(queued) return;

    args = [].slice.call(arguments);

    invocation = function () {
      func.apply(null, args);
      delay();
    };

    if(!timer) {
      invocation();
    } else {
      queued = invocation;
    }
  }
}

var count = 0;

function printSomething(elementId, count) {
  document.getElementById(elementId).innerHTML += String(count) + "
";
}

var opThrottledPrint = throttle(printSomething, 2000),
    underscoreThrottledPrint = _.throttle(printSomething, 2000),
    reviewThrottledPrint = _.throttle(printSomething, 2000);

function invoke() {
  count++;
  opThrottledPrint("op", count);
  underscoreThrottledPrint("underscore", count);
  reviewThrottledPrint("review", count);
}

<button type="button" onclick="invoke()">Click me a few times</button>

Printing is throttled by 2 seconds

    OP's code
    Underscore
    Review code


Python implementation of netcat I'm trying to write a simple python script that acts like the nc program (netcat). I've got it working on OSX (the client that is) by testing against a netcat server, but I'm unsure about the way I've implemented it.

I'd appreciate it if anyone could give me some advice and/or let me know how you would implement it as I still consider myself a beginner. Maybe I should study more on threads and sockets before taking this task on?

By the way, I chose threads over polling for the reason that files in select don't work on Windows.

import sys
import socket
import select
import time
import threading

def _stdout_write(data):
    sys.stdout.write(data)
    sys.stdout.flush()

class NetSnake(object):
    def __init__(self):
        self._close_connection = threading.Event()
        self._stdin_handler = threading.Thread(target=self._handle_stdin)
        self._stdin_handler.daemon = True

    def connect(self, rhost, rport):
        # handle connection refused...
        self._active_sock = socket.create_connection((rhost, rport))
        self._active_sock.setblocking(0)
        self._stdin_handler.start()
        self._handle_active_sock()

    def reverse(self, *args, **kwargs):
        self.connect(*args, **kwargs)

    def _handle_stdin(self):
        while True:
            line = sys.stdin.readline()
            if not line:
                # eof
                break
            self._active_sock.sendall(line)
        # let other thread know that we want to close the connection
        # because eof has been reached.
        self._close_connection.set()

    def _handle_active_sock(self):
        # NOTE: select on windows may not be interrupted by Ctrl-C
        # if not, try time.sleep or event.wait instead.
        self._close_connection.clear()
        timeout = 0.1
        try:
            while not self._close_connection.is_set()
                ready = select.select([self._active_sock], [], [], timeout)
                if ready[0]:
                    data = self._active_sock.recv(4096)
                    if not data:
                        break
                    _stdout_write(data)
        except KeyboardInterrupt:
            _stdout_write('\n')
        finally:
            self._clean_up()

    def _clean_up(self):
        self._active_sock.close()

Edit: I've now realized that I can get rid of the event that signals
the main thread that EOF has been reached and just simply close the socket and handle select's error instead.

def _handle_stdin(self):
    try:
        while True:
            line = sys.stdin.readline()
            if not line:
                # eof
                break
            self._active_sock.sendall(line)
    finally:
        self._clean_up()

def _handle_active_sock(self):
    try:
        while True:
            ready = select.select([self._active_sock], [], [])
            if ready[0]:
                data = self._active_sock.recv(4096)
                if not data:
                    break
                _stdout_write(data)
    except KeyboardInterrupt:
        _stdout_write('\n')
    except select.error:
        pass
    finally:
        self._clean_up()

In case you don't know, sockets in Pythons can have an associated timeout. This will take care of the setblocking(0) + select part for you. Just catch the socket.timeout exception and decide what to do when the operation was canceled.

You can also set the timeout directly as the second argument to create_connection.

You can thus read from the socket using:

def print_recv(sock):
    while True:
        try:
            msg = sock.recv(4096)
        except socket.timeout:
            pass
        else:
            sys.stdout.write(msg)
            sys.stdout.flush()

Granted that the socket already has an associated timeout (or you can call sock.settimeout(0.1) as the first instruction of the function).

As a side note, this function does not account for shutdowns of the connexion from the server. If you want to handle this case, you can detect it when recv return an empty message. So the basic thing to add could be if not msg: break before sys.stdout.write(msg).

Using this function as a thread, you can close the socket from the outside, somehow like you did in your second version, but the socket will, at some point, trigger an OSError on sock.recv. Catching that could be a bad idea, as it may hide more serious issues. Instead, I’d still rely on threading.Event:

def print_recv(sock, event):
    while not event.is_set():
        try:
            msg = sock.recv(4096)
        except socket.timeout:
            pass
        else:
            if not msg:
                break
            sys.stdout.write(msg)
            sys.stdout.flush()

So you’ll have to event.set() before socket.close() outside of the thread. Note, however, that due to scheduling randomness, the order of execution could be:

while not event.is_set(): # Thread-1
event.set()               # Main thread
sock.close()              # Main thread
    msg = sock.recv(4096) # Thread-1

and still lead to an OSError. It will not happen so often, but it will. So you may want to come up with better synchronization if you want a cleaner termination.

You’ll also note that I’m using a function instead of a method to print the messages from the server. It feels cleaner as it separate concerns. In fact, there is no real need to create a class here, appart from keeping around a bunch of related objects. But your setup + teardown logic had me wondering: this is a job for a context manager:

class NetcatManager(object):
    def __init__(self, rhost, rport):
        self._event = threading.Event()
        self._socket = socket.create_connection((rhost, rport))
        self._socket.settimeout(0.1)

    def __enter__(self):
        self._reading_thread = threading.Thread(target=print_recv, args=(self._socket, self._event))
        self._reading_thread.start()
        return self._socket

    def __exit__(self, exc_type, exc_val, exc_tb):
        self._event.set()
        # Waiting for thread termination so there is no OSError when closing the socket
        self._reading_thread.join()
        self._socket.close()

Now all what is left to do is to send messages from stdin to the netcat server. Using the above context manager, it should look like the following:

def netcat_session(rhost, rport):
    with NetcatManager(rhost, rport) as netcat_socket:
        # Process stdin and use netcat_socket.send

And that’s it.

Now, on the topic of processing stdin, be aware that Ctrl+C (which is translated to KeyboardInterrupt) does not mean EOF: Ctrl+D does. So catching the KeyboardInterrupt is meant to recover from an unusual termination of the program; it may or may not be what you want.

Putting everything together, we can come to:

import sys
import socket
import threading

class NetcatManager(object):
    def __init__(self, rhost, rport, timeout=0.1):
        self._event = threading.Event()
        self._socket = socket.create_connection((rhost, rport))
        self._socket.settimeout(timeout)

    def __enter__(self):
        self._reading_thread = threading.Thread(target=print_recv, args=(self._socket, self._event))
        self._reading_thread.start()
        return self._socket

    def __exit__(self, exc_type, exc_val, exc_tb):
        self._event.set()
        # Waiting for thread termination so there is no OSError when closing the socket
        self._reading_thread.join()
        self._socket.close()

def print_recv(sock, event):
    while not event.is_set():
        try:
            msg = sock.recv(4096)
        except socket.timeout:
            pass
        else:
            if not msg:
                break
            sys.stdout.write(msg)
            sys.stdout.flush()

def netcat_session(rhost, rport, input_file=sys.stdin):
    with NetcatManager(rhost, rport) as netcat_socket:
        # We do not iterate (for line in input_file) because stdin does not behave well in Python 2
        while True:
            line = input_file.readline()
            if not line:
                # EOF reached
                break
            netcat_socket.sendall(line)
    # Leave with the screen in a clean state
    print

Note the use of default values. You can now provide any file-like object as the third parameter of netcat_session and it will send instructions from there (so you can save a test session in a file and replay it over and over again using with open('the_file.txt') as f: netcat_session('localhost', 5555, f)).


Python custom list class initialization Consider the class AB below that is to be used as a simple customized list of A objects for lookup operations.

Can this code be improved to avoid instantiating AB with an empty list [] (i.e., perhaps modify __add__ in some way)?

class A():
    def __init__(self, arg):
        self.arg = arg

class AB():
    def __init__(self, list):
        self.list = list

    def __add__(self, other):
        return AB(self.list + [other])

ab = AB([])
ab += A(1)
ab += A(2)

Sure, you can play with the default argument value:

class AB:
    def __init__(self, data=None):
        self.data = data if data is not None else []

    def __add__(self, other):
        return AB(self.data + [other.arg])

Other notes:

list is a bad variable name as it is shadowing the built-in list keyword
remove redundant parentheses after the class name

Demo:

In [1]: ab = AB()

In [2]: ab += A(1)

In [3]: ab += A(2)

In [4]: print(ab.data)
[<__main__.A instance at 0x10afb14d0>, <__main__.A instance at 0x10afa0998>]


Fast bitswap in assembly Can the following code to swap two bits be optimized?

  //ecx = bita, the index of the first bit to be swapped
  //edx = bitb, the index of the second bit to be swapped.
  //r8 = data, the int32 who's bits are to be swapped
  //code        ;latency //comments
  mov eax,1     ;1
  shl eax,cl    ;1     // Set bitA
  mov ecx,[r8]  ;3     // ecx = input
  bts eax,edx   ;0     // Set bitB
  mov edx,eax   ;1     // save the mask for later
  and eax,ecx   ;0     // Let's see if bitA = BitB, if so we don't need to swap
  popcnt eax,eax ;1    // if the bits are not the same, popcount will be 1
  xor edx,ecx    ;0    // Invert the bits in the input, just in case
  sub eax,1      ;1    // is eax odd?, i.e. are the bits different?
  cmovnz ecx,edx ;2    // Bits are different, result is swapped, if not result = input
  mov [r8],ecx   ;3    // write the result

Total latency: 13 cycles.
The code exploits the fact that bit xor 1 inverts and only bits that are different need to be swapped. Still it's a lot of instructions just to swap two bits.

I'm still a bit fuzzy on how to compute latency, but using iaca v2.2, it reports your code as:

Block Throughput: 10.65 Cycles
Throughput Bottleneck: Dependency chains

I'm calling that "the number to beat."

A brief fiddle with your code gives me:

xor eax, eax
xor r10d, r10d

mov r9d, [r8]   ; read the value
btr r9d, edx    ; read and clear the edx bit

setc al         ; convert cf to bit
shl eax, cl     ; shift bit to ecx position

btr r9d, ecx    ; read and clear the ecx bit

mov ecx, edx    ; need edx in ecx for shift
setc r10b       ; convert cf to bit
shl r10d, cl    ; shift bit to edx position

or r9d, eax     ; copy in old edx bit
or r9d, r10d    ; copy in old ecx bit

mov [r8], r9d   ; store result

Which iaca describes as:

Block Throughput: 4.30 Cycles
Throughput Bottleneck: FrontEnd

That's the best I can do for the moment.

Update: Actually, I can do a bit (haha) better:

xor eax, eax        ; build a mask using both bits
bts eax, ecx
bts eax, edx

mov r9d, [r8]       ; read the value
mov r10d, r9d       ; copy the value

and r10d, eax       ; and out the 2 bits we are looking for
jpe done            ; if neither or both bits are set, we're done

xor r9d, eax        ; swap the bits
mov [r8], r9d       ; store the result

done:

jpe is a relatively uncommon instruction which means 'jump parity even.'  Parity is set by the and to indicate the parity of the result.  Parity 'even' means that an even number of bits are set (0 is even).  If an even number of bits are set, then either both bits were zero, or both bits were 1.  In either case, swapping will have no effect since the bits are the same.

iaca v2.3 rates this as:

Block Throughput: 2.00 Cycles
Throughput Bottleneck: FrontEnd

FYI: If you change this api such that the parameter is a mask containing the 2 bits to swap instead of 2 discrete parameters, the time drops to 1.24.  Not knowing the details of the caller, I'm not sure how practical that is.  If you are really working with 2 different computed values for your bit positions, moving this work up to the caller doesn't buy you anything (in fact it probably makes things worse).  But it's something to think about.

So, we started with 10.64 (OP's code).  First cut dropped that to 4.3.  Using BMI2 instructions, I dropped it to 3.  Now using common instructions again, we're down to 2.00 (with a chance at 1.24).

I'm pretty sure I'm done now.  Pretty sure.

Update 2: <sigh>

xor eax, eax        ; build a mask using both bits
bts eax, ecx
bts eax, edx

test [r8], eax      ; compute parity
jpe done            ; if neither or both bits are set, we're done

xor [r8], eax       ; swap the bits

done:

While I might think that loading r8 into a register, testing it, modifying it and then writing it back would be faster, iaca doesn't see it that way.  I'd probably have to test it to be sure.  I'll leave that as an exercise for the student.  Still, this gives us:

Block Throughput: 1.50 Cycles
Throughput Bottleneck: FrontEnd

If this thing gets any faster, it's going to start giving cycles back...

As OP has pointed out, the JPE that I used above only works for bits in the first byte.  Oops.

So, this is my next best:

xor r9d, r9d    ; build mask
bts r9d, ecx
bts r9d, edx

mov r10d, r9d   ; duplicate mask

and r9d, [r8]   ; Load the bits
jz done         ; neither bit set

cmp r9d, r10d   ; Both bits set?
je done

xor [r8], r10d  ; Swap the bits

done:

It's not the 1.5 I was getting above, but it's a respectable 2.00.  Still a pretty good improvement from the 10.65 we started with.

There are some things that might be worth trying when you roll this back into your original code.  While iaca is useful for counting latency, nothing beats real life tests.

I was a little bit iffy about the two jumps, but iaca doesn't much care for replacing them with cmovxx.
Seems like loading the value into a register instead of anding directly from memory, then using that register instead of xoring back into memory should have been a win.
And as I've mentioned below, writing this in C instead of asm might also be a win (nb: MSVC's _bittestandset doesn't optimize well, so creativity may be required).  However since this post was about asm, that's what I'm limiting myself to.

One last point:

Since this code has now gone from 'small' to 'trivial,' I'd suggest re-visiting the decision to write it in assembler.  While I doubt that a C compiler will end up using the jpe instruction, it seems likely it could do a credible job of producing code using basically this approach.

And let's not forget that there are costs associated with calling assembly code from C:

7 very valuable and scarce registers (rax, rcx, rdx, r8-r11) are assumed changed by the code (even if the asm never actually uses them).  Avoiding/spilling these has performance implications for the code making the call.
The stack must be set up/torn down (even though this code never uses the stack, by spec room must always be allocated for the first 4 parameters).
The actual call and ret statements must be executed, while an optimizer might well inline a C routine.
There is no chance that the C optimizer can interleave instructions from the surrounding code to take advantage of available ports/microfusing, or can improve the code based on compile time constant values.

Given all this, I'd expect that writing this in C using intrinsics (ie _bittestandset) would turn out to be a net win despite the fact that it might use a (slightly) less optimal set of instructions (assuming it doesn't figure out a way to do it even better).

I'm struggling with myself to NOT do this here, since it is clearly a separate question.  No wonder I can't rack up any karma.


Flight combinations between two cities I am trying to obtain all possible ways to go from a city A to a city B on a given day by plane, with a maximum of 2 stops.

I have as input a list of dictionaries:

flights = [
        ...
        {'dep': 'FRA', 'arr': 'AMS', 'dep_dt': '2017-05-01 12:00:00', 'arr_dt': '2017-05-01 13:15:00', 'price': 100},
        {'dep': 'FRA', 'arr': 'CPH', 'dep_dt': '2017-05-01 10:00:00', 'arr_dt': '2017-05-01 12:00:00', 'price': 80},
        {'dep': 'FRA', 'arr': 'MAD', 'dep_dt': '2017-05-01 09:00:00', 'arr_dt': '2017-05-01 10:50:00', 'price': 30},
        {'dep': 'CPH', 'arr': 'AMS', 'dep_dt': '2017-05-01 15:00:00', 'arr_dt': '2017-05-01 16:30:00', 'price': 60},
        {'dep': 'CPH', 'arr': 'MAD', 'dep_dt': '2017-05-01 14:15:00', 'arr_dt': '2017-05-01 17:10:00', 'price': 70},
        {'dep': 'MAD', 'arr': 'AMS', 'dep_dt': '2017-05-01 19:00:00', 'arr_dt': '2017-05-01 21:40:00', 'price': 20},
       ...
    ]

With thousands of records between many cities on many dates.

Example

Let's say I want all possibilities to go from FRA to AMS. To find all possible trips, I've split the problem in 3:

Direct flights
Flights with 1 stopover
Flights with 2 stopovers

(I omit the date constraints below for simplicity)

In order to get the direct flights, I can do:

direct_flights = [f for f in flights if f['dep']=='FRA' and f['arr']=='AMS']

To get trips with one stopover, I've gone for a nested loop. Not optimal, but it works:

first_segment = [f for f in flights if f['dep']=='FRA']
second_segment = [f for f in flights if f['arr']=='AMS']

flights_w_1stop = []
for s1 in first_segment:
    for s2 in second_segment:
        if (s1['arr'] == s2['dep'] and
            s1['arr_dt'] < s2['dep_dt']):
            flights_w_1stop.append((s1, s2))

Now, to get all trips with two stopovers, I only could come up with a similar approach than above, but this makes two nested loops, which looks horrible and will be very slow when I have many flights.

first_segment = [f for f in flights if f['dep']=='FRA']
second_segment = [f for f in flights]
third_segment = [f for f in flights if f['arr']=='AMS']

flights_w_2stops = []
for s1 in first_segment:
    for s2 in second_segment:
        for s3 in third_segment:
            if (s1['arr'] == s2['dep'] and
                s2['arr'] == s3['dep'] and
                s1['arr_dt'] < s2['dep_dt'] and
                s2['arr_dt'] < s3['dep_dt']):
                flights_w_2stops.append((s1, s2, s3))

Finally, I would merge all 3 different lists with the same data structure and sort them either by price or by total duration.

Question

How could this be done more efficiently?

Note: I have read about graphs, but I don't think I will ever want to consider more than two stopovers. In addition, it would mean learning a new methodology. It is always good to learn, so if it is the best option I would invest the time. But if a similar thing can be done in another way (rearranging the nested loops somehow?), I would prefer so.

I found a similar question in SO and CodeReview, but I do not see how to apply that to my case.

Your code's runtime is \$O(n^3)\$, this is almost definitely not the performance that you want. The simplest way to solve your problem is by, you guessed it, a graph. Take the following directed graph of your selected flights:

Using a graph gives the ability to check only the actual routes. And so it wouldn't check if it is possible to fly from say; FRA -> CPH, and then FRA -> MAD, as the original code does. This benefit is good, however there is a larger benefit when there are say two, or more, flights in each edge. When that is the case, the original would go through roughly \$432\$ different arrangement of flights. Where a graph would only check the four routes to AMS, which would include travelling all \$6\$ edges. The graph could then return the \$1\$, or \$4\$, routes to AMS, and then go on to return all \$8\$, or \$18\$, permutations of those flights. And so the graph would check roughly \$28\$ permutations of these flights, as opposed to \$432\$.

Another example of this is if you wanted to obtain all the routes from from FRA -> MAD. And so you'd return the flights from FRA -> MAD and FRA -> CPH -> MAD. The first algorithm would still visit all \$6\$ airports, as you want to check if there are any three flights that can get to the desired destination. This time the code would return the above \$2\$ routes, which would lead to the graph quickly returning all \$6\$ possible flight combinations. Leading to roughly \$12\$ permutations.

Note: My maths is vague, and rough, it's not scientific, and depending on where it's measure, I'd not be suppressed if you obtained more permutations. It is merely to show the difference in magnitude between the two approaches.

There are two algorithms that I describe above, the first, can be implemented by:

Make an 'array' of the starting airport.
while 'the array' is not empty repeat the following commands:

Pop a route from 'the array'.
Get the last airports name from the route
If the name is the destination yield it.
If the route's length is equal to the depth we limit to, continue.
Extend 'the array' with the last airports possible flights to.

And so could be:

def _routes(self, destination, depth=1):
    depth += 1
    l = [[self.name]]
    while l:
        route = l.pop()
        name = route[-1]
        if name == destination:
            yield route
        if len(route) == depth:
            continue
        l.extend([
            (route + [a])
            for a in self._graph[name]._flights.keys()
        ])

The second algorithm, is much simpler. You want to produce the product of the flights between each airport, for each route.
Which can be:

def routes(self, destination, depth=1):
    root = self._graph
    return chain.from_iterable(
        product(*(
            root[dep].flights(arr)
            for dep, arr in pairwise(route)
        ))
        for route in self._routes(destination, depth)
    )

And so in total I'd use the below code. I added some un-used functions; remove_flight, and flights_to so that if you did want to use it rather than a list, you have a simpler interface.

from collections import defaultdict, namedtuple
from itertools import chain, product, tee

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

_DEFAULT = object()
class FlightGraph:
    Flight = namedtuple('Flight', 'dep arr dep_dt arr_dt price')
    class Airport:
        __slots__ = ['name', '_graph', '_flights']
        def __init__(self, graph, name):
            self._graph = graph
            self.name = name
            self._flights = defaultdict(set)

        def __getitem__(self, airport):
            if airport not in self._flights:
                raise KeyError('Airport has no flights to {!r}'.format(airport))
            return self._graph[airport]

        def __iter__(self):
            return iter(self._flights.items())

        def add_flight(self, airport, flight):
            # ensure airport exists
            self._graph[airport]
            self._flights[airport].add(flight)

        def remove_flight(self, airport, flight):
            self._flights[airport].remove(flight)

        def flights(self, airport, default=_DEFAULT):
            if airport in self._flights:
                return frozenset(self._flights[airport])
            if default is _DEFAULT:
                raise KeyError('Airport has no flights to {!r}'.format(airport))
            else:
                return default

        def flights_to(self):
            return tuple(self._flights.keys())

        def _routes(self, destination, depth=1):
            depth += 1
            l = [[self.name]]
            while l:
                route = l.pop()
                name = route[-1]
                if name == destination:
                    yield route
                if len(route) == depth:
                    continue
                l.extend([
                    (route + [a])
                    for a in self._graph[name]._flights.keys()
                ])

        def routes(self, destination, depth=1):
            root = self._graph
            return chain.from_iterable(
                product(*(
                    root[dep].flights(arr)
                    for dep, arr in pairwise(route)
                ))
                for route in self._routes(destination, depth)
            )

    def __init__(self, flights=[]):
        self._airports = {}
        for flight in flights:
            flight = self.Flight(**flight)
            self[flight.dep].add_flight(flight.arr, flight)

    def __getitem__(self, key):
        try:
            return self._airports[key]
        except KeyError:
            ret = self._airports[key] = self.Airport(self, key)
            return ret

flights = FlightGraph([
    {'dep': 'FRA', 'arr': 'AMS', 'dep_dt': '2017-05-01 12:00:00', 'arr_dt': '2017-05-01 13:15:00', 'price': 100},
    {'dep': 'FRA', 'arr': 'AMS', 'dep_dt': '2017-05-01 12:00:00', 'arr_dt': '2017-05-01 13:15:00', 'price': 150},
    {'dep': 'FRA', 'arr': 'CPH', 'dep_dt': '2017-05-01 10:00:00', 'arr_dt': '2017-05-01 12:00:00', 'price': 80},
    {'dep': 'FRA', 'arr': 'MAD', 'dep_dt': '2017-05-01 09:00:00', 'arr_dt': '2017-05-01 10:50:00', 'price': 30},
    {'dep': 'CPH', 'arr': 'AMS', 'dep_dt': '2017-05-01 15:00:00', 'arr_dt': '2017-05-01 16:30:00', 'price': 60},
    {'dep': 'CPH', 'arr': 'MAD', 'dep_dt': '2017-05-01 14:15:00', 'arr_dt': '2017-05-01 17:10:00', 'price': 70},
    {'dep': 'MAD', 'arr': 'AMS', 'dep_dt': '2017-05-01 19:00:00', 'arr_dt': '2017-05-01 21:40:00', 'price': 20},
])

for route in flights['FRA'].routes('AMS', 3):
    # TODO: filter if the arr_dt and dep_dt don't allow the route to be possible
    print(', '.join('{0.dep} -> {0.arr} ({0.price})'.format(f) for f in route))


Merge sort approach in Python I'm working my way through a book on algorithms. One of the first challenges is the merge sort. I've seen this implemented before, but as the book suggested I coded one from just the method without looking at the code. When I looked it was very different from mine. Many online examples match the way the book does it.

I am asking about this because I want to learn the reasons this code is better, or if there are trade-offs, or things that are merely style choices, rather than just adopting the pattern of the example code.

Here's mine in Python:

A = [1,5,7,3,4,3,1,8,9,12,64,22,83,223,11]

def merge(A1,A2):
    B1 = []
    while(len(A1)>0 and len(A2) > 0):
        if(A1[0] < A2[0]):
            B1.append(A1.pop(0))
        else:
            B1.append(A2.pop(0))
    B1 = B1 + A1 + A2
    return B1

def mergesort(B):
    if len(B)>1:
        q = len(B)//2
        B1 = mergesort(B[:q])
        B2 = mergesort(B[q:])
        return merge(B1,B2)
    else:
        return (B)

print("mergesort(A) =",mergesort(A))

Here's an example a lot like in my book and in many websites, from GeeksForGeeks

  Python program for implementation of MergeSort

# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m

    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)

    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L[i] = arr[l + i]

    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]

    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray

    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
    if l < r:

        # Same as (l+r)/2, but avoids overflow for
        # large l and h
        m = (l+(r-1))/2

        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
    print ("%d" %arr[i]),

mergeSort(arr,0,n-1)
print ("\n\nSorted array is")
for i in range(n):
    print ("%d" %arr[i]),

# This code is contributed by Mohit Kumra

First, I notice this is manipulating the initial list in place by tracking indices, and I am creating several copies of the data.

I would suppose that I am using more memory, however the example posted lower does create temporary lists to perform the merge. But there they also use index tracking instead of destroying the two arrays with pop as they are consumed.

So again, I'm trying to learn why the differences matter. Which is more educational than just taking on this way of doing it.

There is a couple of problems with your implementation.

The most important trait of the merge sort is stability: the elements compared equal retain their relative order. It does not matter when sorting integers, but is extremely important when sorting more complex data. The comparison

    if(A1[0] < A2[0]):

loses stability, because in case A1[0] is equal to A2[0] the element from A2 will be merged first. The correct way is to if A1[0] <= A2[0].
pop(0) has a linear time complexity, which renders the overall performance quadratic. B1 = B1 + A1 + A2 creates yet another copy of the list, and it doesn't help the performance either.

Manipulating indices, if done right, does reduce memory allocations and deallocations indeed. Unfortunately the GeeksForGeeks code you provided doesn't do it right.


Convert Sql LIKE to Regex I have a bit of code that converts a Sql Like expression to a regex expression for the purposes of a Linq to objects Like extension method. For some time I have been using this conversion.

This conversion replaces all "%" with ".*?" which works for contains patterns but is over matching for starts with or ends with patterns. So the conversion of %abc to .*?abc is capturing both "abcdef" and "123abcdef".

I've amended the conversion algorithm to account for starts with and ends with LIKE expressions.

Here is my code:

internal static string ConvertLikeToRegex(string pattern)
{
    // Turn "off" all regular expression related syntax in the pattern string.
    StringBuilder builder = new StringBuilder(Regex.Escape(pattern));

    // these are needed because the .*? replacement below at the begining or end of the string is not
    // accounting for cases such as LIKE '%abc' or LIKE 'abc%'
    bool startsWith = pattern.StartsWith("%") && !pattern.EndsWith("%");
    bool endsWith = !pattern.StartsWith("%") && pattern.EndsWith("%");

    // this is a little tricky
    // ends with in like is '%abc'
    // in regex it's 'abc$'
    // so need to tanspose
    if (startsWith)
    {
        builder.Replace("%", "", 0, 1);
        builder.Append("$");
    }

    // same but inverse here
    if (endsWith)
    {
        builder.Replace("%", "", pattern.Length - 1, 1);
        builder.Insert(0, "^");
    }

    /* Replace the SQL LIKE wildcard metacharacters with the
    * equivalent regular expression metacharacters. */
    builder.Replace("%", ".*?").Replace("_", ".");

    /* The previous call to Regex.Escape actually turned off
    * too many metacharacters, i.e. those which are recognized by
    * both the regular expression engine and the SQL LIKE
    * statement ([...] and [^...]). Those metacharacters have
    * to be manually unescaped here. */
    builder.Replace(@"\[", "[").Replace(@"\]", "]").Replace(@"\^", "^");

    return builder.ToString();
}

My initial units test are passing but not being overly conversant in regex syntax I am wondering if this is the best approach or if there are gaps in the conversion I am not seeing.

I think you're overcomplicating this and your code still doesn't work correctly. The LIKE pattern bcd shouldn't match abcde, but it does with your code.

What you should do is to always add ^ at the start and $ at the end.

This means the following conversions:

bcd → ^bcd$
%bcd → ^.*?bcd$
bcd% → ^bcd.*?$
%bcd% → ^.*?bcd.*?$

In the cases where the pattern starts with %, the ^ is not necessary (and similarly for $ and % at the end), but it also doesn't do any harm.


Max Sum of Nodes in Each Path in Binary Tree I wanted to get a review on an algorithm I wrote for a binary tree problem. The problem is the following.

  Return the maximum sum between all branches in a binary tree. A branch
  is defined as all paths from root to leaf.

class Node(object):
    def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None

#branch one
root = Node(10)

second = Node(5)
root.left = second

third = Node(1)
second.left = third

fourth = Node(3)
third.left = fourth

tenth = Node(5)
third.right = tenth

fifth = Node(20)
root.right = fifth

sixth = Node(60)
fifth.left = sixth

seventh = Node(3)
fifth.right = seventh

nineth = Node(40)
seventh.right = nineth

def find_max_sum_of_binary_tree_path(root):
    curr_list = []
    curr_max = [0]

    def binary_tree_recurse(node):
        if node:
            if not node.left and not node.right:
                curr_list.append(node.value)
                list_sum = sum(curr_list)
                if list_sum > curr_max[0]:
                    curr_max[0] = list_sum
                curr_list.pop()

            curr_list.append(node.value)
            binary_tree_recurse(node.left)
            binary_tree_recurse(node.right)
            curr_list.pop()

    binary_tree_recurse(root)
    return curr_max[0]

  #      10
  #      / \
  #     5   20
  #    /   / \
  #   1   60   3
  #  / \       \
  # 3   5       40

find_max_sum_of_binary_tree_path(root) #should return 90 based on my tree
>90

I'd like to stick to a recursive approach, but open to suggestions on anything else. I am mostly concerned about time complexity and improving the performance of this function. Does anyone know what the current time complexity is?

It seems like you are doing a little too much work.

The maximum sum of a node that is None will be 0.

The maximum sum of a node that is not None will be the value of the node, plus the max of the sums of the two children.

That recursion alone should be enough to avoid using intermediate data structures. Something like:

def find_max_sum_of_binary_tree_path(root):
    if root is None:
        return 0

    left_sum = find_max_sum_of_binary_tree_path(root.left)
    right_sum = find_max_sum_of_binary_tree_path(root.right)

    return root.value + max((left_sum, right_sum))


Filtering data for jQuery DataTables Using DataTables (Table plug-in for jQuery) with server-side processing, I had to create filtering for my data with good performance. However, in my opinion it's kinda ugly, especially the part of (.Where(...)), where I have to manually compare each property with the search variable. Is it possible to make it better?

using System.Linq.Dynamic; // because of special .OrderBy

public class SomeRepository
{
    public DataTableDTO GetAllFromBase(int start, int length, string sortColumn, string sortColumnDir, string search)
    {
        var dataFiltered = db.User
            .AsNoTracking()
            .Select(x => new { x.Id, x.FirstName, x.LastName, x.Description})
            .OrderBy(sortColumn + " " + sortColumnDir)
            .Where(search.Length > 0, x => x.Id.ToString().Contains(search.ToLower())
                                        || x.FirstName.ToLower().Contains(search.ToLower())
                                        || x.LastName.ToLower().Contains(search.ToLower())
                                        || x.Description.ToLower().Contains(search.ToLower()));

        var recordsFiltered = dataFiltered.Count();
        var recordsTotal = db.User.Count();

        var dataToShow = dataFiltered
            .Skip(start)
            .Take(length)
            .ToList();

        var dataForTable = new DataTableDTO
        {
            Data = dataToShow,
            RecordsTotal = recordsTotal,
            RecordsFiltered = recordsFiltered
        };

        return dataForTable;
    }
}

public static class LinqExtensions
{
    public static IQueryable<T> Where<T>(this IQueryable<T> query, bool condition, Expression<Func<T, bool>> whereClause)
    {
        if (condition)
        {
            return query.Where(whereClause);
        }
        return query;
    }
}

I would suggest to add some guard evaluation.

if (string.IsNullOrEmpty(search))
    return new DataTableDTO();

You can also convert string 'search' to lower case ones at the beginning of method.

search = search.ToLower();

Then you can ommit the first condition in Where statement:

.Where(search.Length > 0,


Yet another C++ Json Parser (Recursive) Following on from this request Yet another C++ Json Parser

A friend pointed out that he though a recursive decent parser would be more efficient.
Before I agree I want to test it so I wrote it for testing.

I found the implementation of the parser much more complex than using yacc (but that could be a result of using yacc a few times and not trying to write recursive descent parsers).

Any comments on the implementation appreciated:

JsonRecParser.h

#ifndef THORSANVIL_JSON_PARSER_JSON_REC_PARSER_H
#define THORSANVIL_JSON_PARSER_JSON_REC_PARSER_H

#include "JsonRecParser.h"
#include "JsonParser.tab.hpp"

class yyFlexLexer;

using namespace ThorsAnvil::JsonParser;

namespace ThorsAnvil
{
    namespace JsonParser
    {

class JsonRecParser
{
    yyFlexLexer&    lexer;

        int JsonValueParse(int val);
        int JsonMapValueListParse(int val);
        int JsonArrayValueListParse(int val);
        int JsonMapParse(int val);
        int JsonArrayParse(int val);
        int JsonObjectParse(int val);

    public:
        JsonRecParser(yyFlexLexer& lexer)
            : lexer(lexer)
        {}
        int parse();
};
    }
}

#endif

JsonRecParser.cpp

#include "JsonParser.tab.hpp"

using namespace ThorsAnvil::JsonParser;

int JsonRecParser::JsonValueParse(int val)
{
    switch(val)
    {
        case '{':                                       return JsonMapParse(lexer.yylex());
        case '[':                                       return JsonArrayParse(lexer.yylex());
        case yy::JsonParser::token::JSON_STRING:   return 0;
        case yy::JsonParser::token::JSON_NUMBER:   return 0;
        case yy::JsonParser::token::JSON_TRUE:     return 0;
        case yy::JsonParser::token::JSON_FALSE:    return 0;
        case yy::JsonParser::token::JSON_NULL:     return 0;
        default:                                        break;
    }
    return val;
}
int JsonRecParser::JsonMapValueListParse(int val)
{
    if ((val == yy::JsonParser::token::JSON_STRING) && ((val = lexer.yylex()) == ':') && ((val = JsonValueParse(lexer.yylex())) == 0))
    {
        val = lexer.yylex();
        switch(val)
        {
            case '}':   return 0;
            case ',':   return JsonMapValueListParse(lexer.yylex());
            default:    break;
        }
    }
    return val;
}
int JsonRecParser::JsonArrayValueListParse(int val)
{
    if ((val = JsonValueParse(val)) == 0)
    {
        val = lexer.yylex();
        switch(val)
        {
            case ']':   return 0;
            case ',':   return JsonArrayValueListParse(lexer.yylex());
            default:    break;
        }
    }
    return val;
}
int JsonRecParser::JsonMapParse(int val)
{
    if (val == '}')
    {   return 0;   /* Empty Map */
    }
    return JsonMapValueListParse(val);
}
int JsonRecParser::JsonArrayParse(int val)
{
    if (val == ']')
    {   return 0;   /* Empty Array */
    }
    return JsonArrayValueListParse(val);
}
int JsonRecParser::JsonObjectParse(int val)
{
    switch(val)
    {
        case '{':   return JsonMapParse(lexer.yylex());
        case '[':   return JsonArrayParse(lexer.yylex());
        default:    break;
    }
    return val;
}
int JsonRecParser::parse()
{
    return JsonObjectParse(lexer.yylex());
}

All other files are the same.
With this small change to main:

Changes to main.cpp

    //yy::JsonShiftParser parser(lexer);
    ThorsAnvil::JsonParser::JsonRecParser   parser(lexer);

#

Recursion generally isn't more efficient, just easier to program and understand. For simpler examples it also leads to much neater code however can be harder to understand if you have multiple levels of recursion jumping around.

Each function call will add stuff to the stack as such it will use more memory and take longer as it has to allocate and initialize that memory, even when using pointers/references. You might also find you run into a depth limit in the form of a stack overflow (like the site name ☺).

With that said for most JSON it wouldn't likely be an issue, unless someone was sending malicious JSON your way which you should assume for any external input.


Query for customer quotes by date range I have a table (Oracle):

customer_quote
------
int id
int part_key (fk)
int condition_code (fk)
number unit_price
int qty_quoted
date entry_date

With a query that selects data from the past year:

SELECT cq.part_key
    , cq.condition_code
    , COUNT(*) AS cq_count
    , SUM(cq.unit_price * cq.qty_quoted) AS cq_total
    , SUM(cq.qty_quoted) cq_qty
FROM customer_quote cq
WHERE cq.entry_date > TO_DATE('09-Jun-2017', 'dd-mm-yyyy')
GROUP BY cq.part_key
    , cq.condition_code

But I needed the data to include parts with activity from the past two years but data older than 1 year shouldn't calculate into the totals. So I wrote this query:

SELECT cq.part_key
    , cq.condition_code
    , COUNT(case when cq.entry_date > TO_DATE('09-Jun-2017', 'dd-mm-yyyy') then 1 END) AS cq_count
    , SUM(case when cq.entry_date > TO_DATE('09-Jun-2017', 'dd-mm-yyyy') then (cq.unit_price * cq.qty_quoted) END) AS cq_total
    , SUM(case when cq.entry_date > TO_DATE('09-Jun-2017', 'dd-mm-yyyy') then cq.qty_quoted END) cq_qty
FROM customer_quote cq
WHERE cq.entry_date > TO_DATE('09-Jun-2016', 'dd-mm-yyyy')
GROUP BY cq.part_key
    , cq.condition_code

The where date is 2 years ago but the case when dates are all 1 year ago. This query works, but is it optimal? I think there's probably a way to merge the case when statements into 1.

Performance is my main concern, readability is only marginally important.

Worth noting: the final SQL query will be a parameterized SQL Java object so the date will be a CASE WHEN cq.entry_date > ? THEN and inserted using PreparedStatement::setDate() so with my solution I will need to do setDate() x 4.

I think the query is optimal enough. The truth is query can retrieve a result only by accessing 2 years data, so given WHERE condition is must. And the query access rows only once. At performance aspect, table access method (through index or by full scan) is critical, but Oracle Optimizer will choose it by referring statistics information.


Filtering a DataFrame based on two logical conditions, first one numpy array values, second one current day based The following is just a working example.
I have a DataFrame containings a monotonous growing function.
Some of the values are actuals, some are forecasted.
I need to filter specific actuals values based on a set of milestones and I have to avoid to take forecasted values from the dataframe
I created this following script.
It works, but I think is not so much pythoninc.
I am a self taught and my working eviroment is Google Colab
Expected Output

I would avoid the for loop and the if condition

Understand if there is room of improvement in the code quality
#importing libraries
import pandas as pd
import numpy as np
import datetime

#working code mock-up
th_array = np.arange(0, 11000, 1000)
cumulated_array = np.arange(0, 5000, 185)

df_index = pd.date_range(end = "20/04/2021",
                         periods = len(cumulated_array))
df = pd.DataFrame(data = cumulated_array,index = df_index,
                columns = ["cumulated"])

df_filtered = pd.DataFrame()
current_day =  pd.to_datetime(datetime.date.today())

#filtering loop
for y in th_array:
  x = df[(df['cumulated'] > y) & (df.index < current_day)]
  if x.empty is False:
      df_filtered = df_filtered.append(x.iloc[0])

One way to refactor the loop is to locate the desired rows with idxmax() and then index them in one shot:
df = df[df.index < current_day]
th_array = th_array[th_array < df.cumulated.max()]

indexes = pd.DataFrame(df.cumulated.values[:, None] > th_array).idxmax()
df.iloc[indexes]

#             cumulated
# 2021-03-25        185
# 2021-03-30       1110
# 2021-04-04       2035
# 2021-04-10       3145

Explanation
First, keep only the rows before current_day:
df = df[df.index < current_day]

#             cumulated
# 2021-03-24          0
# 2021-03-25        185
# ...
# 2021-04-10       3145
# 2021-04-11       3330

And keep only the th_array values less than cumulated.max():
th_array = th_array[th_array < df.cumulated.max()]

# array([   0, 1000, 2000, 3000])

Then use array broadcasting to build a boolean matrix of cumulated > th_array where rows correspond to cumulated and columns to th_array:
valid = pd.DataFrame(df.cumulated.values[:, None] > th_array)

#         0      1      2      3
# 0   False  False  False  False
# 1    True  False  False  False
# 2    True  False  False  False
# 3    True  False  False  False
# 4    True  False  False  False
# 5    True  False  False  False
# 6    True   True  False  False
# 7    True   True  False  False
# 8    True   True  False  False
# 9    True   True  False  False
# 10   True   True  False  False
# 11   True   True   True  False
# 12   True   True   True  False
# 13   True   True   True  False
# 14   True   True   True  False
# 15   True   True   True  False
# 16   True   True   True  False
# 17   True   True   True   True
# 18   True   True   True   True

So for each column (th_array), we want the first True row (cumulated). These can be found with idxmax(). Since False is 0 and True is 1, all the True indexes are tied for the max, and the first one wins the tiebreaker:
indexes = valid.idxmax()

# 0     1
# 1     6
# 2    11
# 3    17
# dtype: int64

Then just iloc these indexes for the final filtered df:
df.iloc[indexes]

#             cumulated
# 2021-03-25        185
# 2021-03-30       1110
# 2021-04-04       2035
# 2021-04-10       3145

Timing
For the sample data, the indexing method runs ~11 times faster than looping+appending:
>>> %timeit iloc(df, th_array)
989 µs ± 15.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

>>> %timeit loop(df, th_array)
10.9 ms ± 202 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Testing functions for reference:
def iloc(df, th_array):
    df = df[df.index < current_day]
    th_array = th_array[th_array < df.cumulated.max()]
    indexes = pd.DataFrame(df.cumulated.values[:, None] > th_array).idxmax()
    return df.iloc[indexes]

def loop(df, th_array):
    df_filtered = pd.DataFrame()
    for y in th_array:
        x = df[(df['cumulated'] > y) & (df.index < current_day)]
        if x.empty is False:
            df_filtered = df_filtered.append(x.iloc[0])
    return df_filtered


Rearrange string to an anagram of the string - get new position, old position values I'm writing a function to take an anagram pair (words or phrases spelled with the same letters) and determine how you could move the letters to change one into the other.

For example: Admirer -> Married

The results would be something like this:

[[0, 1], [1, 6], [2, 0], [3, 4], [4, 2], [5, 5], [6, 3]]

The character in the 0 (a) position moves to 1, the character in position 1 (d) moves to 6, etc. I've already successfully solved this but perhaps there's a better way!

Language of choice (required!) is javascript. Here's my current, working function:

function _get_new_positions(source, target) {
    // convert both strings to arrays - uppercase so we can find the destination
    // spot without worrying about cases
    source = source.toUpperCase().split('');
    target = target.toUpperCase().split('');

    var transform = [];
    var repeated = [];
    var found = 0;

    for(var i=0; i<source.length; i++) {
        // keep track of how many times we've found and 'moved' this letter
        repeated[source[i]] = repeated[source[i]] ? repeated[source[i]] + 1 : 1;
        found = 0;
        want  = repeated[source[i]];
        for(var j=0; j<target.length; j++) {
            if( target[j] == source[i] ) {
                found++;
                console.log('found is ' + found);
                if( found == want ) {
                    transform.push([i,j]);
                    break;
                }
            }
        }
    }
    return transform;
}

Thank you for your input.

You can simplify the logic by setting each character you find in target to NULL. I also like to use a "while" loop as shown below.

function _get_new_positions(source, target) {
    var transform = [], i, j, found, want;
// convert both strings to arrays - uppercase so we can find the destination without worrying about cases
    source = source.toUpperCase().split('');
    target = target.toUpperCase().split('');
    for(i=0; i<source.length; i++) {
        j = 0;
        found = false;
        want  = source[i];
        while((j < target.length) && !(found = (target[j] == want))){j++}
        if (! found) {
            console.log("Cannot find character: " + want + " at [i]: " + i);
        } else {
            console.log("Found character: " + want + " at [i,j]: " + i + j);
            target[j] = ''; //blank out the character for future searches
            transform.push([i,j])
        }
    }
    return transform;
}


Triggering editing mode for a form I think that my code isn't perfect and I need a help to understand how to optimize it.

In my application I have a main form and several forms for data editing.
The user can:

Add a new item
Edit the selected item
Delete the selected item
Duplicate an item with a new name

You can see an example of my code below. I think that the approach to trigger editing mode isn't good.

An alternative way is to create a new form without parameters and then run methods AddItem(), EditItem(), etc., but I don't think that's a good idea either.

Editor modes:

public enum EditMode { Add, Edit, Delete, Copy };

Main form has several buttons:

    private void AddItemBarButton_ItemClick(object sender, ItemClickEventArgs e)
    {
        ItemForm IF = new ItemForm(EditMode.Add);
        IF.ShowDialog();
        IF.Dispose();
    }

    private void EditItemBarButton_ItemClick(object sender, ItemClickEventArgs e)
    {
        if (ActiveItem != null)
        {
            ItemForm IF = new ItemForm(EditMode.Edit, ActiveItem);
            MIF.ShowDialog();
            MIF.Dispose();
        }
    }

    private void DeleteItemBarButton_ItemClick(object sender, ItemClickEventArgs e)
    {
        if (ActiveItem != null)
        {
            ItemForm IF = new ItemForm(EditMode.Delete, ActiveItem);
            MIF.Dispose();
        }
    }

    private void CopyItemBarButton_ItemClick(object sender, ItemClickEventArgs e)
    {
        if (ActiveItem != null)
        {
            ItemForm IF = new ItemForm(EditMode.Delete, ActiveItem, "somenewname");
            MIF.Dispose();
        }
    }

Editor form:

    private Item T = null;
    private EditMode Mode;

    private ItemForm()
    {
        InitializeComponent();
    }

    public ItemForm(EditMode mode) : this()
    {
        Mode = mode;
        switch (Mode)
        {
            case EditMode.Add:
                T = new Item();
                T.Sort_Order = DateTime.Now;
                break;
        }
    }

    public ItemForm(EditMode mode, Item item) : this()
    {
        Mode = mode;
        T = item;
        switch (Mode)
        {
            case EditMode.Edit:
                NameEdit.Text = T.Name;
                CountEdit.Text = T.Countnum.ToString();
                break;

            case EditMode.Delete:
                cDB.Item.DeleteOnSubmit(T);
                cDB.SubmitChanges();
                break;
        }
    }

    public ItemForm(EditMode mode, Item item, string new_name) : this()
    {
        Mode = mode;
        switch (Mode)
        {
            case EditMode.Copy:
                T = new Item();
                T.Name = new_name;
                T.Countnum = item.Countnum;
                T.Sort_Order = item.Sort_Order;
                cDB.Item.InsertOnSubmit(T);
                cDB.SubmitChanges();
                break;
        }
    }

    private void OKButton_Click(object sender, EventArgs e)
    {
            T.Name = NameEdit.Text;
            T.Countnum = Convert.ToInt(CountEdit.Text);

            if (Mode == EditMode.Add) cDB.Item.InsertOnSubmit(T);
            cDB.SubmitChanges();

            this.Close();
        }
    }

A small note on naming:

Being new to your code base, I have no idea what MIF represents and worse, IF looks a lot like if and it confuses my eyes. As a rule of thumb, don't abbreviate names. Spell them out so that the maintainer coming behind you understands what everything is.


Calculate sum of multiple series within array The exercise is as follows:

Player A will write list \$ a \$ consisting of \$ n \$ numbers. Player B will take a look at the paper. After that the A player will ask player B \$q\$ questions. Each question will be of the following form:
If I give you two \$ R \$ and \$ L \$ in \$ a \$ such that (\$ 1<=L<=R<=n\$ ), calculate the following value:
$$ 1*a[L] + 2*a[L+1] + 4*a[L+2] + ... + 2^{R-L-1}*a[R-1]+2^{R-L}*a[R] $$
Because the numbers can be really large, we need to find the residue that the result will give when divided by \$ 10^9 + 7\$.
Input is as follows:

n q
a1 a2 an
L1 R1
L2 R2
Lq Rq

The output is: on one line the result for one query.

The problem:
I need to improve performance so it is finished within 1 second. I think the problem may be because I have 2 for loops. Because the number of numbers can be up to 200,000 as well as the pairs. This means that in the worst case it has to go through the process 40,000,000,000 times.
Can someone please tell me how to improve the performance?
#include <iostream>

using namespace std;

const int MAXN = 200000;

int residues[MAXN];
int numbers[MAXN];
int pairs[MAXN][2];

void findResidues(int i)
{
    residues[i] = (residues[i - 1] * 2) % 1000000007;
}

long long int sumBetween(int first, int second)
{
    long long int sum = 0;
    int pos = first;
    while(pos <= second)
    {
        sum += (long long)residues[pos - first] * numbers[pos];
        sum %= 1000000007;
        pos++;
    }
    return sum;
}

int main()
{
    residues[0] = 1;
    int n, q ;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> numbers[i];
        findResidues(i + 1);
    }
    for(int i = 0; i < q; i++)
    {
        cin >> pairs[i][0] >> pairs[i][1];
        cout << sumBetween(pairs[i][0] - 1, pairs[i][1] - 1) << endl;
    }
    return 0;
}

int pairs[MAXN][2]; wastes memory. You don't need to read all the queries at once:
  for(int i = 0; i < q; i++)
  {
      cin >> L >> R;
      cout << sumBetween(L - 1, R - 1) << endl;
  }

works equally well. Besides, the problem statement doesn't say how many queries are there; it could be way more than the size of the array.

Your feeling that you use the wrong algorithm is well founded. Bruteforcing is almost always wrong. Look at the underlying math first. I don't want to spell out everything, just a couple of hints:

\$1*a_{L} + 2*a_{L+1}+ ... + 2^{R-L}*a_{R} = \dfrac{2^L*a_{L} + 2^{L+1}*a_{L+1}+... + 2^R*a_{R}}{2^L}\$

The numerator above is a difference of two partial sums of the \$2^n*a_{n}\$ sequence.

\$1000000007\$ is a prime number, so division by \$2^L\$ modulo 1000000007 is a multiplication by a multiplicative inverse of 2 modulo 1000000007 (which is trivial to find) to the same power.

I hope it is enough to get you going in the right direction. You should be able to answer each query in constant time.


Foreach removal of Magic Quotes PHP I'm looking to remove all magic quotes at the start of my PHP script (if they are turned on). The code I'm using to do this is rather simple, so I was wondering if I was overlooking anything:

if (get_magic_quotes_gpc())
{
    foreach ($_GET as $key => $value)
        $_GET[$key] = stripslashes($value);

    foreach ($_REQUEST as $key => $value)
        $_REQUEST[$key] = stripslashes($value);

    foreach ($_POST as $key => $value)
        $_POST[$key] = stripslashes($value);

    foreach ($_COOKIE as $key => $value)
        $_COOKIE[$key] = stripslashes($value);
}

Am I missing / overlooking anything? Thanks.

If you are sanitizing your input just for the sake of sanitizing your input, you're wasting time (both yours in coding and the computer in execution). Do you need to sanitize $_COOKIE if you never use it? What about $_SESSION?

Only sanitize what you need, when you need it. Switching to a PDO system to have it sanitize your database queries would solve that aspect (and the #1 reason to sanitize).


Two classes to avoid confusion when handling degrees and radians Experimenting with operator overloading for the first time. Based on my reading, it appears to be a bit of a minefield.

Have I fallen into any traps?

namespace Units
{
    class Degree; // Forward declare Degree so it can be passed by reference into Radian.

    /// \class Radian
    /// Encapsulates a double, and used to represent a radian.
    class Radian
    {

    public:
        /// Constructor.
        /// \param radian The  angle (radians).
        Radian(double radian) : angle_(radian) {}

        /// Constructor.
        /// \param degree The  angle (degrees).
        Radian(const Degree& degree);

        /// Function Call Operator.
        /// \return <double> The angle value (radians).
        operator double() const { return angle_; }

    private:
        double angle_;

    };

    /// \class Degree
    /// Encapsulates a degree, and used to represent a degree.
    class Degree
    {
    public:
        /// Constructor.
        /// \param degree The angle value (degrees).
        Degree(double degree) : angle_(degree) {}

        /// Constructor.
        /// \param radian The  angle (radians).
        Degree(const Radian& radian);

        /// Function Call Operator.
        /// \return <double> The angle (degrees).
        operator double() const { return angle_; }

    private:
        double angle_;
    };

    /// Constructor.
    /// Constructor defined outside of class declaration, to allow Degree class to be defined before it.
    /// \param degree The  angle (degrees).
    Radian::Radian(const Degree& degree)
    : angle_(degree * SoC::Maths::Trigonometry::DegToRad)
    {}

    /// Constructor.
    /// Constructor defined outside of class declaration, to allow Radian class to be defined before it.
    /// \param radian The  angle (radians).
    Degree::Degree(const Radian& radian)
    : angle_(radian * SoC::Maths::Trigonometry::RadToDeg)
    {}

} // namespace Units

#endif // UNITS_H

EDIT

and initialised in the way:

const Units::Degree latitude = 48.8566;

Design

While it might seem that the current design is working fine, I think there are two distinct issues lurking beneath the surface.

Issue #1: operator double

From what I can tell, the intention behind these unit classes seems to be the prevention of unit mismatches. Providing an access function to the contained value is not a bad idea, but using the implicit conversion operator for doing so is probably not the wisest choice here.

Consider the following snippet:

auto angle = Degrees{ 180.0 };
auto sine = std::sin(angle);

It compiles easy enough, but will then fail silently at runtime. It likely won't even crash the application, but quietly produce values different to those expected.

Of course, this is a contrived case ("std::sin is not really in the scope of this library (yet)!"), but nonetheless it shows a problem: As it is, there is hardly any prevention of accidental unit mismatches.

Adding the keyword explicit to operator double() might help with some of these cases (though not with std::sin), but not all of them.

  If this were the only issue, it would be easy to fix with a getter function with a descriptive name (e.g. getDegrees).

Issue #2: Extensibility

Let's say that in the future, you (as the library developer) want to add another representation for angles (e.g. gons/gradians). Sounds simple, right?

And at that point, it is. Adding one more class according to the given scheme, four more converting constructors, and it is done.

  Someone familiar with the SOLID principles might already spot a code smell in the last sentence: four more converting constructors, two of which have to be added to the existing and otherwise rather independent classes Degrees and Radians, thus violating the Open-Closed part of SOLID.

After that comes another user A of the library and wants to add his own custom angle representation RepA. And then comes user B with RepB.

And suddenly, we're having twenty converting constructors just for those five classes. And each additional representation is going to add a lot more: For \$N\$ representations, we need \$N \cdot (N - 1)\$ converting constructors to cover all combinations.

  And that is assuming independent developers add converting constructors for each others implementation. Otherwise, operator double will again lurk in the shadows, allowing for code to compile that really should not.

class Gradians {
public:
    Gradians(double);
    Gradians(const Degrees&);
    Gradians(const Radians&);
    operator double() const;
    // ...
};

class Turns {
public:
    Turns(double);
    Turns(const Degrees&);
    Turns(const Radians&);
    operator double() const;
    // ...
};

  Now stuff like auto a = Gons(300.0); auto b = Turns(a); will actually compile, but produce wrong results (b == 300.0 instead of b == 0.75).

How can we solve this conundrum?

A first step would be to separate the value from its representation(s) by choosing one internal representation which can be converted on demand:

class Angle {
public:
    static Angle fromDegrees(double degrees);
    static Angle fromRadians(double radians);

    double radians() const;
    double degrees() const;
private:
    Angle(double radians) : radians_{ radians } {}

    double radians_;
};

Angle Angle::fromDegrees(double degrees) {
    auto radians = degrees * SoC::Maths::Trigonometry::DegToRad;
    return Angle{ radians };
}

Angle Angle::fromRadians(double radians) {
    return Angle{ radians };
}

double Angle::degrees() const {
    return radians_ * SoC::Maths::Trigonometry::RadToDeg;
}

double Angle::radians() const {
    return radians_;
}

As you can see, I chose radians for my internal representation (mostly because that's what the trigonometric functions of the standard libary expect). For adding a new representation, we now only need to add one factory function (fromXyz(...)) and one getter function (xyz()).

  While this is a lot cleaner (and takes care of some issues), SOLID devotees will not fail to notice that the violation of the Open-Closed principle hasn't been fixed yet, just moved.

  To address this, we could introduce a hierarchy of derived classes, but that seems like overkill for this problem.

  Another easy solution would be to use templates:

struct Degrees {
    static double toRadians(double degrees) {
        return degrees * SoC::Maths::Trigonometry::DegToRad;
    }
    static double fromRadians(double radians) {
        return radians * SoC::Maths::Trigonometry::RadToDeg;
    }
};

struct Radians {
    static double toRadians(double radians) { return radians; }
    static double fromRadians(double radians) { return radians; }
};

class Angle {
public:
    template<typename Representation>
    static Angle from(double value) {
        return Angle{ Representation::toRadian(value) };
    }

    template<typename Representation>
    double as() const {
        return Repreentation::fromRadians(radians_);
    }

private:
    Angle(double radians) : radians_{ radians } {}

    double radians_;
};

 // Usage
 auto angle = Angle::from<Degrees>(180.0);
 auto sine = std::sin(angle.as<Radians>());

Of course, this is far from done, yet:

Operators for addition, subtraction (angles), multiplication and/or division (scalars) could be overloaded for this Angle class
For demonstration purposes I didn't mark the member functions above noexcept or constexpr. This should likely be amended.
Helper functions like sin, cos, tan and similar could be provided for this Angle class.
For the template version: The templates could be restricted to only accept types with correct signatures for fromRadians and toRadians.

Implementation

Aside from the design considerations mentioned above, I can add these points for the general implementation:

Consider marking converting constructors and conversion operators as explicit.
Very likely sizeof(Degree) == sizeof(double), so there probable won't be a benefit for taking a const Degree& parameter over just Degree.
I'd suggest checking the precision of the constants ' DegToRadandRadToDeg`, especially if calculated on your own. If the precision on these constants is poor, there might be small numeric errors that accumulate over multiple conversions to and fro.
A comment reads /// Function Call Operator: Actually, no, this is a conversion operator. A function call operator would look like this: double operator()() const.
Generally, the comments don't tell me much about anything. Unless there is a hard requirement for them (in which case they should be improved) I'd suggest removing them. In their current form, they are at best visual clutter, and confusing at worst.


Creating lstlistings for Java files in multiple Java folders I did write it to have a solution for my problem. But I don't know if my code is ok. Can you please check it?

Problem:

I want to include all my Java files from all my projects (created with Netbeans), the projects are stored in one folder, into a LaTeX document. I solved it with this code:

package dir;

import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

public class Dir {

    private static String fileType;
    private static String fileName;
    private static String pathName;
    private static String folderName;
    private static String oldFolderName = "";

    public static void main(String[] args) {
        File currentDir = new File(".");
        content(currentDir);
    }

    public static void content(File dir) {
        try {
            File[] files = dir.listFiles();
            for (File file : files) {
                if (file.isDirectory()) {
                    pathName = file.getName();
                    if (pathName.equals("src")) {
                        pathName = "main";
                    }
                    content(file);
                } else {
                    fileType = Files.probeContentType(Paths.get(file.getAbsolutePath()));

                    if (fileType.equals("text/x-java")) {
                        fileName = file.getName();
                        folderName = file.getParentFile().getName();

                        if(folderName.equals("src")){
                            folderName = file.getParentFile().getParentFile().getName();
                        }else{
                            folderName = file.getParentFile().getParentFile().getParentFile().getName();
                        }

                        if(!folderName.equals(oldFolderName)){
                            System.out.println("\\section{" + folderName + "}");
                        }

                        if(!pathName.equals("")){
                        System.out.println("\\subsection{" + pathName + "}");
                        }

                        System.out.println("\\subsubsection{" + fileName + "}");
                        System.out.println("\\lstinputlisting[language=java]{" + file.getCanonicalPath() + "}");
                        System.out.println("");
                        pathName = "";
                        oldFolderName = folderName;
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

I am especially frustrated about following part:

if(folderName.equals("src")){
    folderName = file.getParentFile().getParentFile().getName();
}else{
    folderName = file.getParentFile().getParentFile().getParentFile().getName();
}

Is there a better way to loop through all the .getParentFile() until you get the .getParentFile().getName() of the folder named "src"?

Furthermore one question: my code doesn't iterate sorted through my folders and files. I mean, if the subfolder of the folder I am in are like 3, 4, 5 and 6, the code just don't open folder 3 first, but just chooses a random file. It would be nice if you could help me to fix it.

to me it stroke odd that you use old java.io classes to list files, while using the newer (not-so-new-anymore) java 7 java.nio classes to determine file type.
I say you should use Files.isDirectory(Path p) and Files.newDirectoryStream(Path p) to check and list files in directory.

Furthermore, if you want to traverse a directory tree, you have the wonderful Files.walkFileTree() that does all the traversing for you.  You need to implement a FileVisitor that has interception points for start and end of directory and of course for visiting a file.  I believe this can help you in detecting src directories.


constexpr Endian conversion in c++14 This is my take for constexpr big / little endian conversions.

The code supports only little and big endian; mixed endian such PDP is not supported.

#include <cstdio>
#include <cstdint>

namespace myendian_impl_{

    template<typename UINT>
    UINT byteswap(UINT const a);

    template<>
    constexpr uint16_t byteswap(uint16_t const a){
        constexpr uint8_t b[] = {
            8 * (2 - 1)
        };

        auto const x =
            (0x00ffULL & a) << b[0] |
            (0xff00ULL & a) >> b[0]
        ;

        return static_cast<uint16_t>(x);
    }

    template<>
    constexpr uint32_t byteswap(uint32_t const a){
        constexpr uint8_t b[] = {
            8 * (2 - 1),
            8 * (4 - 1)
        };

        auto const x =
            (0x000000ffULL & a) << b[1] |
            (0x0000ff00ULL & a) << b[0] |
            (0x00ff0000ULL & a) >> b[0] |
            (0xff000000ULL & a) >> b[1]
        ;

        return static_cast<uint32_t>(x);
    }

    template<>
    constexpr uint64_t byteswap(uint64_t const a){
        constexpr uint8_t b[] = {
            8 * (2 - 1),
            8 * (4 - 1),
            8 * (6 - 1),
            8 * (8 - 1)
        };

        auto const x =
            (0x00000000000000ffULL & a) << b[3] |
            (0x000000000000ff00ULL & a) << b[2] |
            (0x0000000000ff0000ULL & a) << b[1] |
            (0x00000000ff000000ULL & a) << b[0] |
            (0x000000ff00000000ULL & a) >> b[0] |
            (0x0000ff0000000000ULL & a) >> b[1] |
            (0x00ff000000000000ULL & a) >> b[2] |
            (0xff00000000000000ULL & a) >> b[3]
        ;

        return static_cast<uint64_t>(x);
    }

    // ==============================

    class isBE{
        constexpr static uint32_t u4 = 1;
        constexpr static uint8_t  u1  = (const uint8_t &) u4;
    public:
        constexpr static bool value = u1 == 0;
    };

    // ==============================

    template<bool b>
    struct be_tag{};

    // ==============================

    template<typename UINT>
    constexpr UINT htobe(UINT const a, be_tag<true>){
        return a;
    }

    template<typename UINT>
    constexpr UINT htobe(UINT const a, be_tag<false>){
        return byteswap(a);
    }

} // namespace myendian_impl_

constexpr inline uint16_t htobe16(uint16_t const a){
    using namespace  myendian_impl_;
    return htobe(a, be_tag<isBE::value>{});
}

constexpr inline uint32_t htobe32(uint32_t const a){
    using namespace  myendian_impl_;
    return htobe(a, be_tag<isBE::value>{});
}

constexpr inline uint64_t htobe64(uint64_t const a){
    using namespace  myendian_impl_;
    return htobe(a, be_tag<isBE::value>{});
}

int main(){
    printf("%16x %16x\n",   0x1122,         htobe16(0x1122)         );
    printf("%16x %16x\n",   0x11223344,     htobe32(0x11223344)     );
    printf("%16lx %16lx\n", 0x1122334455667788, htobe64(0x1122334455667788) );
}

In all, this looks pretty solid to me, so I have only a few suggestions:

Eliminate spurious inline

The inline keyword is only useful if this is moved to a header file, so it's not strictly needed in the context of the code in the question.

Consider defining a string literal

Here's a small enhancement: provide the ability to define a string literal.  Here's how it might be done:

constexpr uint32_t operator"" _be32(unsigned long long num) {
    return htobe32(num);
}

Usage:

printf("%16x %16x\n",   0x11223344,     0x11223344_be32     );

This makes things very tidy and easy to use.  Naturally, 16- and 64-bit versions are almost identical except for return type and name.


Merge sort implementation efficiency I made a merge sort implementation in C++, which I have tested with the values:

6, 38, 27, 7, 12, 58, 92, 43, 3, 9, 82, 10

producing the correct output of:

3 6 7 9 10 12 27 38 43 58 82 92

However, when running my program, it seemed pretty slow, and I was wondering if there were any places in my code where there is an inefficiency, or if the entire implementation (recursive in most places, but iterative in parts of the merging) is the wrong way forward.

#include <iostream>
#include <vector>

template<typename InputIt>
void merge(InputIt f1,
    InputIt l1,
    InputIt f2,
    InputIt l2)
{
    size_t d1 = std::distance(f1, l1),
        d2 = std::distance(f2, l2);

    if (d1 == 1 && d2 == 1 && *f1 > *f2) {
        std::iter_swap(f1, f2);
    }
    else {
        for (size_t i = 0; i < d1; ++i) {
            for (size_t j = 0; j < d2; ++j) {
                if (*(f1 + i) > *(f2 + j)) {
                    std::iter_swap(f1 + i, f2 + j);
                }
            }
        }
    }
}

template<typename InputIt>
void merge_sort(InputIt first,
    InputIt last)
{
    size_t dist = std::distance(first, last);
    size_t left = (size_t)(dist / 2);
    size_t right = dist - left;

    //traverse left
    if (left > 1) {
        merge_sort(first, first + left);
    }

    //furthest left point found, merge upwards

    merge(first, first + left, first + left, last);

    //ensure that all the way right (limited to left section) has been reached
    if (right > 1) {
        merge_sort(first + left, last);
    }

    //furthest right point in left section found, merge upwards
    merge(first, first + left, first + left, last);

    //traverse right
    if (right > 1) {
        merge_sort(first + left, last);
    }

    //furthest right point found, merge upwards

    merge(first, first + left, first + left, last);

    //ensure that all the way left (limited to right section) has been reached
    if (left > 1) {
        merge_sort(first, first + left);
    }

    //furthest left point in right section found, merge upwards
    merge(first, first + left, first + left, last);
}

int main()
{
    std::vector<int> v{6, 38, 27, 7, 12, 58, 92, 43, 3, 9, 82, 10};

    merge_sort(v.begin(), v.end());

    for (auto& x : v) {
        std::cout << x << " ";
    }

    std::cout << std::endl;

    getchar();
}

Not a merge sort

This step in the merge() function:

    for (size_t i = 0; i < d1; ++i) {
        for (size_t j = 0; j < d2; ++j) {
            if (*(f1 + i) > *(f2 + j)) {
                std::iter_swap(f1 + i, f2 + j);
            }
        }
    }

is an \$O(N^2)\$ operation and works more like an insertion sort or bubble sort rather than a merge.  Also, you should only have to merge once instead of four times.  The pseudocode for the mergesort function should be:

mergesort(leftHalf);
mergesort(rightHalf);
merge(leftHalf, rightHalf);

I believe your merge function is not only slow but also doesn't merge properly in one pass, which is why your program seems to require calling it four times.


Refer to other cells besides the one in the Cells.Find I have the following that loops through a range.  When the initial value is found on the second sheet it goes to the cell to be able to compare some date values on the same row.  Once the comparison is complete another value from the same row is copied to be placed back onto the first sheet.  I believe the Application.Goto which activiates the second sheet and the other Sheets("Data").Activate is really slowing this down.  It loops through about 26k rows and takes about 12 minutes.  I don't know of another way to refer to the other cells in the second sheet in regards to the found value in both sheets without activating sheets back and forth.

Sub oiyuou()

Dim rFound As Range
Dim dtStartTime As Date
dtStartTime = Now()

Application.ScreenUpdating = False
Range("A2").Select

Do Until ActiveCell.Offset(0, 4).Value = ""

    Application.StatusBar = ActiveCell.Row
    sdate = ActiveCell.Offset(0, 6).Value
    sCat = ActiveCell.Offset(0, 1).Value & ActiveCell.Offset(0, 3).Value 'concat of two cells

    'find in other worksheet
    Set rFound = Sheets("User").Cells.Find(What:=sCat, _
                                            After:=ActiveCell, _
                                            LookIn:=xlValues, _
                                            LookAt:=xlPart, _
                                            SearchOrder:=xlByRows, _
                                            SearchDirection:=xlNext, _
                                            MatchCase:=False, _
                                            SearchFormat:=False)

    If rFound Is Nothing Then
        sdept = ""
    Else: Application.Goto rFound, True 'i assume this is the way to go so i can compare my sdate with these other values
        If (sdate >= ActiveCell.Offset(0, 3).Value And sdate <= ActiveCell.Offset(0, 4).Value) Or ActiveCell.Offset(0, 4).Value = "" Then
            sdept = ActiveCell.Offset(0, 2).Value
        Else: sdept = ""
        End If
    End If

    Sheets("Data").Activate  'back to first sheet to populate with found value sdept
    ActiveCell.Value = sdept
    ActiveCell.Offset(1, 0).Select

Loop

Application.ScreenUpdating = True
MsgBox "Macro ran successfully in " & _
            FormatDateTime(Now() - dtStartTime, 3), vbInformation
End Sub

EDIT
I was able to get around the back and forth of updating sheets but it still takes the same amount of time.  So this narrows it down to the loop itself.
This is what I replaced in case it helps anyone.  I found it extremly helpful that you could call the rFound.address.  Once I knew I could call that then I could use the offset to refer to the other values.

Set rFound = Sheets("User").Cells.Find(What:=sCat, _
                                            After:=ActiveCell, _
                                            LookIn:=xlValues, _
                                            LookAt:=xlPart, _
                                            SearchOrder:=xlByRows, _
                                            SearchDirection:=xlNext, _
                                            MatchCase:=False, _
                                            SearchFormat:=False)

    sEff = rFound.Offset(0, 3).Value
    sTerm = rFound.Offset(0, 4).Value

    If rFound Is Nothing Then
        sdept = ""
    End If

    If (sdate >= sEff And sdate <= sTerm) Or sTerm = "" Then
        sdept = rFound.Offset(0, 2).Value
    Else: sdept = ""
    End If

   ' Sheets("Data").Activate
    ActiveCell.Value = sdept
    ActiveCell.Offset(1, 0).Select

Firstly, I think you could use VLOOKUP or INDEX & MATCH functions. You code could always fill column A of the Data sheet with the MATCH function and then read down the rows, using the result of the function, instead of the Find method.

Your code currently only finds the first match found, if you want to check for other matches you will need another loop.

If you want to keep this in "traditional" VBA, rather than use ADODB as suggested by @RubberDuck, then there are a couple things you can try:

Try to avoid using ActiveSheet, ActiveCell and Select at all times. I did some testing and this didn't produce much of an imporvement in speed although it makes your code more robust.
Not a performance issue, but in your code you currently have these lines of code:

sEff = rFound.Offset(0, 3).Value
sTerm = rFound.Offset(0, 4).Value

immediately after the Find method but before you have tested if rFound Is Nothing so these lines will throw an error when the Find doesn't return a Range object.
Do you need to search the whole of the User sheet for a matching entry or can you search a single column? Reducing the number of cells through which the Find method must check will give you a big performance increase. So, for example, you could use:

Set rFound = Sheets("User").Range("A1:A26000").Find(What:=sCat, _
                                               LookIn:=xlValues, _
                                               LookAt:=xlPart, _
                                               SearchOrder:=xlByRows, _
                                               SearchDirection:=xlNext, _
                                               MatchCase:=False, _
                                               SearchFormat:=False)

In VBA, the AND and OR operators are not "lazy" and will always test both expressions. You might get some improvement if you split the following line into several If .. Then tests:

If (sDate >= sEff And sDate <= sTerm) Or sTerm = "" Then


Switching between tabs inside of a web application I'm making a web application for the administration of a restaurant kind of type. The purpose of this application is to make customers, and the orders of those customers, which has products in it, etc...

This application is written in PHP combined with jQuery.

I have many tabs, such as:

Displaying the orders
A screen to make a new order (same  div as displaying the list from the orders)
A screen to show you all products, which you can click on to put them inside of a orders.
A screen where more order information appears whenever clicking on it.

On this moment, I'm using this kind of snippets to manage this:

if (orderListScreen.css('visibility', 'hidden')) {
    orderListScreen.css("visibility", "visible");
    newOrderScreen.css("visibility", "hidden");
}

if (availableProductsScreen.css("visibility", "hidden")) {
    availableProductsScreen.css("visibility", "hidden");
    orderInformationScreen.css("visibility", "visible");
}

Note: This is one block of code.
Note: the orderListScreen and all the other variables refer to different div elements.

Problem

This is very confusing to work with.
This takes me more time to actually think which one is active and which one is not.

My own try

I've made a small function which also switches between the visibility of the elements, but I still don't like it; it makes it too confusing.

function switchTab(activate, deactivate) {
    var _activate = $(activate);
    var _deactivate = $(deactivate);

    if (_activate.css("visibility", "hidden")) {
        _activate.css("visibility", "visible");
        _deactivate.css("visibility", "hidden");
    }
}

The if statement doesn't do what you think it does.

Optional details about the .css() function:

   The .css() function is overloaded in a number of ways. It can take one string, two strings, or an object.

 In the first form, it returns the current value of the specified property. This will probably not be exactly as you specified it. For example, $("body").css("background-color", "red").css("background-color") returns "rgb(255, 0, 0)" for me.

 In the second, it sets the specified property (first string) to the given value, and returns the jQuery object. In the third, it sets the specified properties (given as keys of the object) to their respective values. This form also returns the jQuery object, for more method chaining.

 As you can see, if you're intent on using the .css() function to check a value, the first form is what you want.

A better way of checking visibility would be to use the .is() function in conjunction with the :visible selector.

Here's my revision. I took the liberty of renaming the parameters. I also used the common practice of naming jQuery variables using Hungarian notation.

function switchTab(toActivate, toDeactivate) {
    var $toActivate = $(toActivate);
    var $toDeactivate = $(toDeactivate);

    if (!$toActivate.is(":visible")) {
        $toActivate.css("visibility", "visible");
        $toDeactivate.css("visibility", "hidden");
    }
}

Another way:

If there's some common selector between the tabs (for example, if they all have the class .tab) and you're fine with display: none; instead of visibility: hidden;, you can simplify to the following:

function switchTab(toActivate) {
    $(".tab").hide();
    $(toActivate).show();
}


Todo app for displaying a list of tasks The main view in my (toy!) Todo app is, of course, to display the list of tasks.  These are grouped by some criterion, and the tasks structure below is actually a list of pairs (header, list of tasks).

{% for tasks in tasks %}

{{ tasks.0 }}:

    {% for t in tasks.1 %}

            = 1 %}prio-medium{% endif %}
                {% if t.priority >= 2 %}prio-high{% endif %}
                ">
                {{ t.description }}

            {% if t.due_date %}
                due,
                <span class="
                    {% if t.days_to_due_date < 15 %}date-soon{% endif %}
                    {% if t.days_to_due_date < 3 %}date-very-soon{% endif %}
                    {% if t.days_to_due_date < 0 %}date-overdue{% endif %}
                    ">
                    {{ t.relative_due_date }}

            {% endif %}
            -
            {% if not t.done %}
                Done!
            {% else %}
                Not done!
            {% endif %}
            -
            Edit

    {% endfor %}

{% empty %}

Cool! Nothing to do...

{% endfor %}

In particular, I'm wondering if deciding which CSS class to assign is considered to be the view function's role, or if it's correct to put it in the template.

Similarly, I'm also wondering about the presence of several URLs in the template. Would they be better in the tasks structure itself?  Or should they be provided through some methods in the Task class? After all, relative_due_date is already a function that's only used for display (it returns a string like 'Yesterday', 'Tomorrow' or 'In 3 days'). And shouldn't I use reverse()?

I would suggest moving the CSS selection logic to a custom template tag or even a filter, e.g. {{ t.relative_due_date }}. After that your templates will look much cleaner and that logic would still belong to the presentation part of MVT (Model, View, Template).
You can split your tuple in the definition of the loop so that you don't redefine the tasks variable. {% for header, task_list in tasks %} ....
Use reverse URLs, no question about it. You'd hate the day you have to change them otherwise :) Go even further, use URL namespaces.


Comparing objects in a list against each other I have a list of ~27000 objects. Each object represents a line from a file where each line is one record of a measurement from some instrument.

The most import aspects of the object are:

Instrument name: int (49099, 89, …)
Station Name: string (K-900, MK-45, …)
Time: datetime object (13:34:17  01/02/2017)

All these objects are going to be used in creating a Hierarchical Data Format file where the top most "layer" is a measurement. Each measurement contains multiple line objects which have the same name and have a difference in time within some duration (30 minutes).
 One major problem is that the data files I read to create the line objects are very unstructured. I cannot assume that subsequent lines in one file have anything to do with each other, so I cannot compare each line to the previous line to have some filtering logic in the reading part. Even files that have been generated on the same date SHOULD look similar, just with different instrument name, but this is not the case for this problem.
 That is why I am reading them all in and THEN comparing all lines to each other. But it is taking a very long time and is not scalable at all.

The code provided is what I am currently doing and I would love to hear any improvements I could make or different ways to tackle my problem.

new = []
for i, r in enumerate(self.records):
    x = (y for y in self.records if  y.compare_record_same_name(r))
    if any(r in x for x in new):
        continue
    else:
        new.append(x)

class Record():
    def compare_record_same_name(self, other):
        duration = abs(self.date_time - other.date_time)
        duration = duration.total_seconds()
        return (self.name == other.name and duration < TIME_SEPERATOR
                and duration > 0)

I find the problem you are trying to solve to be as hard to grasp from the code presented as from the description:
- document your code, using the conventions of the language (&environment) of choice.
- use telling names

In the for-loop, you don't use i: don't use enumerate().
I think the first comprehension easier to understand with reading (? "r") mentioned first:
measurement = (y for y in self.records if reading.<predicate>(y))
I think it confusing to use the same identifier for unrelated objects in one and the same statement - suggesting if not any(reading in n for n in new):
instead of if <condition>: <pass> else: <act> do
if not <condition>: <act>
compare_record_same_name() is a horrible name, as it mentions only half of what the function checks. It seems it is there to check whether the other record belongs to the same "measurement" - name it for that: same_measurement().
instead of converting duration to seconds each and very time, make TIME_SEPARATOR a timedelta

I'd try a different approach:

readings with different instrument names do not belong to the same measurement, anyway:
use a separate collection for each name
sort each collection by time (hoping the method used makes good use of what order is bound to exist in input)
any gaps exceeding TIME_SEPARATOR separate measurements
if the time covered by any group g is too big for one measurement, split at large internal gaps or evenly by number of readings or time range or …