Counting algorithms while loop's time complexity
I have found that questions were already created regarding these type of topics, but they looked very simple examples. I know how to count time complexity of for loops, but how would I go about counting this while loop inside the method?
public static void QuickSort(DataArray items, int left, int right)
{
int i = left, j = right;
double vid = items[(left + right) / 2];
while (i <= j)
{
while (items[i] < vid)
i++;
while (items[j] > vid)
j;
if (i <= j)
{
items.Swap(j, i, items[j], items[i]);
i++;
j;
}
}
if (left < j)
QuickSort(items, left, j);
if (i < right)
QuickSort(items, i, right);
}
See also questions close to this topic

PHP Select ALL from MySQL Between Two Times
I have a MySQL database with a Timestamp field and i am struggling to work out how to retrieve all rows (for ALL days) between two times (e.g 10am  11:am). time_field is indexed and data stored as YYYYMMDD H:i:s (20180320 10:15:03)
I have tried:
$q = "SELECT * FROM table WHERE time_field BETWEEN '10:00:00' AND '11:00:00'";
and also this:
$q = "SELECT * FROM table WHERE time_field >= '10:00:00' AND < '11:00:00'";
But, both return no results. If I run the SELECT statement including the a full date I can retrieve results, but that only does one day, not for all days. Would appreciate some assistance please. I have checked SO, but couldn't see anything that solved this.

Avg time on page excessively high analytics
Im opening an iframe with a page with analytics. To close the i frame i make a .remove() with jquery. It looks like analytics doesnt see this and the avg time on page is very high. How to make analytics understand that the page was closed? I also tried changing the src of the iframe before deleting it but it doesn see it either.
I open it like this:
$('#' + this.id ).html( '<iframe class="hpm_frame " frameBorder="0" src="'+window.RETARGET_BASE+'framed" allowtransparency="true" style="'+ ' minwidth: '+width+';'+ ' minheight: '+height+';'+ '"></iframe>' );
I close it like:
$(".hpm_desktop iframe").attr("src",window.RETARGET_BASE+"close" ); setTimeout(function(){ $(".hpm_desktop iframe").remove(); },3000);

eliminate dates that are not within a certain amount of days of the previous date (R)
I have a data frame in R called info which includes several dates under the column Date, they are ordered in "%Y%m%d" I want to only have those values that are less then 6 days apart and remove the "outliers" anyone know how this can be done?
what the data frame looks like
'> info Date ens seps 3 19510108 mem01 2 4 19510112 mem01 4 37 19591208 mem01 4 42 19591230 mem01 3 43 19600101 mem01 2 47 19610103 mem01 2 49 19610118 mem01 2 50 19610120 mem01 2 62 19641129 mem01 4 93 19710212 mem01 2 99 19720215 mem01 2 100 19720218 mem01 3 102 19720221 mem01 2 119 19811016 mem01 3 121 19811019 mem01 2 131 19841224 mem01 2 134 19870102 mem01 2

How can I speed up this MATLAB code with a while loop?
I'm using a code that calculates expectation value of probabilities. This code contains a whileloop that finds all possible combinations and adds up products of probability combinations. However, when the number of elements becomes large(over 40) it takes too much time, and I want to make the code faster. The code is as follow
function pcs = combsum(N,K,prbv) nprbv=1prbv; %prbv: probability vector WV = 1:K; % Working vector. lim = K; % Sets the limit for working index. inc = 0; % Controls which element of WV is being worked on. pcs = 0; stopp=0; while stopp==0 if logical((inc+lim)N) stp = inc; % This is where the for loop below stops. flg = 0; % Used for resetting inc. else stp = 1; flg = 1; end for jj = 1:stp WV(K + jj  inc) = lim + jj; % Faster than a vector assignment. end PV=nprbv; PV(WV)=prbv(WV); pcs=prod(PV)+pcs; inc = inc*flg + 1; % Increment the counter. lim = WV(K  inc + 1 ); % lim for next run. if (inc==K)&&(lim==NK) stopp=1; WV = (NK+1):N; PV=nprbv; PV(WV)=prbv(WV); pcs=prod(PV)+pcs; end end
Is there a way to reduce calculation time? I wonder if parallel computing using GPU would help.

Python loop not breaking out
I expect the whole loop to exit when my
isQuit
variable is"yes"
and customer becomesFalse
. However, the current loop seems to be repeated until theorder_item
is inmenu_items
.Can you please help me change my code so that the loops stop when the user wants to quit?
def order(menu): FISH_CHIPS_PRICES = menu menu_items = [] for item in FISH_CHIPS_PRICES: menu_items.append(item.lower()) orders = [] customer = True while customer: orders.append({}) for item in FISH_CHIPS_PRICES: orders[1][item] = 0 while True: while True: order_item = input("What do you want to buy?") if order_item.lower() not in menu_items: print("Item:", order_item, "not available") isQuit = input("Do you want to quit: yes / no:") if isQuit == "yes": customer = False else: break

Variable not defined in while loop in python?
I am trying to write a simple program in python to read command line arguments and print a final word based on the arguments. If there is any argument of the form "f=" then the will go to the front of the final printed word. Similarly for "e=" the text goes to the back and if there is caps as an argument then the final printed word will all be uppercase. I do a while loop to scan through the arguments and check for these flags. The full code is:
import sys i=1 while i<len(sys.argv): frnt_wrd = None lst_wrd = None arg_1 = str(sys.argv[i]) if arg_1.startswith('f='): front = arg_1.split('=') frnt_wrd = front[1] elif arg_1.startswith('e='): last = arg_1.split('=') lst_wrd = last[1] if arg_1.startswith('caps'): caps = True else: word = arg_1 i+=1 print (front) print (frnt_wrd)
I had a couple of if statements later on to print out the word based on whether frnt_wrd and lst_wrd were not equal to None (i.e. a value had been assigned to them) but nothing was printing out. To check the problem I did:
print (front) print (frnt_wrd)
and the output actually gives me front as the desired array (when there is an argument of the form "f=" but returns frnt_wrd as None even though I defined:
frnt_wrd = front[1]
When I type exactly this line outside of the while loop it actually works but why is it not defining the frnt_wrd inside the while loop?
Edit: The full code giving me frnt_wrd as None is above. What else do you need? I would like to learn how to do it with while and without argparse. I need to understand why I am defining a variable and it is not defining.
Traceback: enter image description here

Time optimization of function for signal processing
I have a program doing a LOT of iteration (thousands to millions to hundreds of millions). It's starting to take quite a lot of time (few minutes, to a few days), and despite all my effort to optimize it, I'm still a bit stuck.
Profile: using cProfile via console call
ncalls tottime percall cumtime percall filename:lineno(function) 500/1 0.018 0.000 119.860 119.860 {builtin method builtins.exec} 1 0.006 0.006 119.860 119.860 Simulations_profiling.py:6(<module>) 6/3 0.802 0.134 108.302 36.101 Simulations_profiling.py:702(optimization) 38147 0.581 0.000 103.411 0.003 Simulations_profiling.py:270(overlap_duo_combination) 107691 28.300 0.000 102.504 0.001 Simulations_profiling.py:225(duo_overlap) 12615015 69.616 0.000 69.616 0.000 {builtin method builtins.round}
The first question, is what are the 2 first lines? I assumed that it was the program being called.
I'm going to replace the
round()
method by tolerance comparison in myif / else
statements, thus avoiding this time consumption. I would like to optimize further the 2 following functions, but I can't find a new approach.import itertools import numpy as np class Signal: def __init__(self, fq, t0, tf, width=0.3): self.fq = fq # frequency in Hz self.width = float(width) # cathodic phase width in ms self.t0 = t0 # Instant of the first pulse in ms self.tf = tf # End point in ms # List of instant at which a stim pulse is triggered in ms self.timeline = np.round(np.arange(t0, self.tf, 1/fq*1000), 3) def find_closest_t(self, t): val = min(self.timeline, key=lambda x:abs(xt)) id = np.where(self.timeline==val)[0][0] if val <= t or id == 0: return val, id else: return self.timeline[id1], id1 def duo_overlap(S1, S2, perc): pulse_id_t1, pulse_id_t2 = [], [] start = max(S1.t0, S2.t0)  max(S1.width, S2.width) if start <= 0: start = 0 start_id_S1 = 0 start_id_S2 = 0 else: start_id_S1 = S1.find_closest_t(start)[1] start_id_S2 = S2.find_closest_t(start)[1] stop = min(S1.tf, S2.tf) + max(S1.width, S2.width) for i in range(start_id_S1, len(S1.timeline)): if S1.timeline[i] > stop: break for j in range(start_id_S2, len(S2.timeline)): if S2.timeline[j] > stop: break d = round(abs(S2.timeline[j]  S1.timeline[i]), 3) # Computation of the distance of the 2 point if S1.timeline[i] <= S2.timeline[j] and d < S1.width: pulse_id_t1.append(i) pulse_id_t2.append(j) continue elif S1.timeline[i] >= S2.timeline[j] and d < S2.width: pulse_id_t1.append(i) pulse_id_t2.append(j) continue else: continue return pulse_id_t1, pulse_id_t2 def overlap_duo_combination(signals, perc=0): overlap = dict() for i in range(len(signals)): overlap[i] = list() for subset in itertools.combinations(signals, 2): p1, p2 = duo_overlap(subset[0], subset[1], perc = perc) overlap[signals.index(subset[0])] += p1 overlap[signals.index(subset[1])] += p2 return overlap
Explanation of the program:
I have square signals of width
Signal.width
and of frequencySignal.fq
starting atSignal.t0
and ending atSignal.tf
. During the initialization of aSignal
instance, thetimeline
is computed: it's a 1Darray of float in whicheach number corresponds to the instant at which a pulse is triggered
.Example:
IN: Signal(50, 0, 250).timeline OUT: array([ 0., 20., 40., 60., 80., 100., 120., 140., 160., 180., 200., 220., 240.]) A pulse is triggered at t = 0, t = 20, t = 40, ... Each pulse has a width of 0.3.
duo_overlap()
takes 2 signals in input (and a percentage that we will keep fix at 0 for this example. This function computes the id of the the pulse for S1 and for S2 (ID in the timeline array) that overlap one with another.Example:
If a pulse starts at t = 0 for S1 and a pulse starts at t = 0.2 for S2, since 0.2  0 = 0.2 < 0.3 (S1.width), the 2 pulses overlap.
I tried to optimize this function by looping only on the ID in which they can possibly overlap (
start_id
,stop
) computed ahead.But as you can see, this function is still really timeconsuming because of the high number of calls.The last function,
overlap_duo_combination()
takes N signals in input as a list (or tuple / iterable) (2 <= N <= 6 in practice) and creates adict()
in which the key is the ID of the signal in the input list, and the value is a list of overlapping pulses ID (comparison 2 by 2 of the signals within the input list).Example:
Input: signals = (S1, S2, S3) The pulse n°2 of S1 overlap with pulse n°3 of S2 and the pulse n°3 of S2 overlap with pulse n°5 of S3.
Output: dict[0] = [2] / dict[1] = [3, 3] / dict[2] = [5]
The 3 pops out twice for S2 because it will be add the first tile
duo_overlap()
is called on S1 and S2, and the second time when it is caleed on S2 and S3. I don't want to avoid duplicates since it's an information on how many different pulses are overlapping (in this case, 2 pulses are overlapping with the pulse n°3 of S2).Would you have any idea, suggestion, code or whatever to redue the time complexity of this part of the code?
I am currently looking into PyCUDA implementation since I have a Nvidia 1080 Ti at disposal, but I don't know the C language. Would it be worth to switch to GPU this inner function that doesn't take long to execute when called but is called thousands of times?
Thanks for reading such a long post, and thanks for the help!

Is there an Algorithm for finding the minimum number of classrooms for scheduling n classes in O(nlogn)?
So the question is this :
we have n classes (n intervals) with start time and finish time [si , fi] and we want to find the minimum number of classrooms which we can satisfy all the classes(intervals) without any collusion
the book that I'm reading says we can solve this in O(nlogn) but i cannot find any algorithm better than O(n^2)
it says we should sort them by the starting time but doesn't say the rest of the solution, but that doesn't make any sense because before giving each class a room, shouldn't we check all the other intervals to see if we have a collusion or not? which makes it O(n^2) because for each interval we need to check all the other intervals
am i missing something ?

computational complexity of Annoy
I am using Annoy for finding knearest neighbors of a doc2vec model. I want to compute the Computational complexity.
I am looking for the computational complexity of Annoy library.
I calculate the complexity of Annoy algorithm based on the steps mentioned in this page.
I assume:
 dimension is d
 size of data is n
 number of binary tree is T
Then the time complexity would be:
Preprocessing time: Build up a bunch of binary trees. For each tree, split all points recursively by random hyperplane
O(Tlogn)
Query time: Insert the root of each tree into the priority queue
O(T logn)
Until we have _search_k _candidates, search all the trees using the priority queue
O(Tn logk)
Remove duplicate candidates
O(Tk)
Compute distances to candidates
O(TKd)
Sort candidates by distance
O(TKlog(TK))
Return the top ones
The time complexity of Annoy library is :
O(Tlogn)+ O(T logn)+O(T n log k)+O(Tk)+O(TKd)+O(TKlog(TK))
Can anyone help me?