New answers tagged algorithm
2
Document your code. In the code.
• what use is MovingAverage?
• is size fixed for the lifetime of any given MovingAverage instance?
I don't know even scrutinising the code: size is neither final nor private
• what does next(int value) return?
accumulate ints into longs - even the sum of two ints can overflow.
program against interfaces - and give ...
2
Document your code. In the code: while
quick_sort(arr) is telling to an extent (sort into (ascending "natural") order (between pairs of arr's elements), additional space no worse than proportional to input size, processing time no worse than proportional to its square),
arr isn't: what, in Python, is an array? The way arr is used, any sequence would do ...
3
Unnecessary else:
if length <= 1:
return arr
else:
pivot = arr.pop()
...
If the first path is taken, the method exits. If the second path is taken, then execution continues with the remainder of the method. So you could write the rest of the method inside the else: clause:
if length <= 1:
return arr
...
2
In addition to Sam I want to point out some other things
Avoid typing long list/dict constants
Very often you can construct them by code, which is less error prone. Instead of
d_dict = {"0" : 0, "1" : 1, "2" : 2, "3" : 3, "4" : 4, "5" : 5, "6" : 6, "7" : 7, "8" : 8, "9" : 9, "A" : 10, "B" : 11, "C" : 12, "D" : 13, "E" : 14, "F": 15}
you do
import string
...
4
First -- document your code! I read through your d_func function and here's my attempt at writing a docstring for what it does, with Python-2-compatible type hints. Hopefully I got it right. :)
def d_func(digit, mode):
# type: (Union[str, int], int) -> Union[int, str, None]
"""Mode 1: give the int value of the hex digit.
Other modes: give ...
3
In Go, measure performance. Run benchmarks using the Go testing package.
For example,
$ go test transpose_test.go -bench=. -benchmem
BenchmarkTranspose-4 2471407 473 ns/op 320 B/op 13 allocs/op
BenchmarkTransposeOpt-4 9023720 136 ns/op 224 B/op 2 allocs/op
$
As you can see, minimizing allocations is important. Efficient memory ...
1
Care about final
Your parameters are never modified, so it is good practice to mark them final. Probably the method too, unless you expect it can be overridden.
public final int shortestDistance(final String[] words, final String word1, final String word2)
Compare by indices
Instead of your for loop, you can use the indices of the elements.
public final ...
1
Δt
Since you have the timestamps of the velocity measurements, there is no need to calculate the step size. For all you know, the steps are not even all equal.
You can use np.diff to calculate the differences between all the data points:
time_differences = (np.diff(time))
or in pure python:
time_differences = [b - a for a, b in zip(time, time[1:])]
or ...
3
My main issue with this code is the function interface as you already identified yourself. These are the most glaring issues in my opinion:
Parameter names are not clear. Names like i and n might be good enough in very short, self-contained loops/closures, but not as function parameters. I similarly don't like abbreviations like orig, and cur because the ...
1
Just a few things I noticed.
Utilize built in functions
This
S = 0
for k in range(1, N):
S += function[a + k * h]
can be this
S = sum(function[a + k * h] for k in range(1, N))
Python3's sum takes an iterable, and returns the sum of all the values in that iterable. So, you can pass in the for loop and it will return the sum for you. Looks neater, ...
3
Don't use #define ll long long int and don't use long long int either. Use auto for values and size_t for indices and cardinalities.
Your method should take iterators as parameters. It will still work with vectors, but also with linked lists and other containers.
Have a well defined behaviour for corner cases, such as empty lists. This behaviour should be ...
1
For the algorithm, it can be shortened by only checking if a sub-sequence qualifies when it is finished.
using ll = long long;
int LongestSubSeq(const std::vector<ll>& arr)
{
int numSeq = 0;
int longest = 0;
int length = 0;
size_t size = arr.size();
for(size_t i = 1; i < size; ++i)
{
++length;
if(arr[i] &...
4
The code
Before switching to a better algorithm, let's polish the code first. Almost every line of your code can be improved.
Get rid of #define ll long long int. This is a standard way to lower the quality of your code. If you mean long long, use long long.
Qualify names from the std namespace with std::.
Make the parameter temp a const reference (const ...
4
I have no C/C++ compiler at the moment, but the algorithm only needs one loop, the while+flag being a tiny bit too unreadable.
There are two counters:
Finding the maximum length: maxLength
Sequences with next value >= prior value.
Counting the maximum length: maxCount.
length > maxLength reset maxCount to 1
length == maxLength increment maxCount
So (in ...
6
If the grader is complaining about "time limit exceeded," it must be because some loop is executing too many times. All of your functions are clearly O(1) — they have no loops. So which loop is executing too many times? It must be the only loop in the entire program:
while(!isFull(n)){
cin>>a;
push(a);
}
Is it possible that ...
0
Avoid Global Variables
In the code there are 2 global variables:
int minEle = 0;
stack<int> s;
Using global variables is something that all experienced programmers avoid. Global variables make the code very hard to write, debug and maintain. It is very difficult in programs larger than this one to local where a global variable is modified. Global ...
3
You can get an immediate speed-up by ditching the defaultdict(int), and using a bytearray(blockCount+1) instead. Both have roughly \$O(1)\$ lookup time, but the latter has a much smaller constant factor. In the former, each key must be hashed, then binned, then a linear search through the bin is required to find the correct key entry, if it exists, and ...
4
First thoughts
Read and act on the warnings provided by the compiler. That's one of the biggest points of a compiled language. Do not ignore the 10+ warnings. You have a ton of unused imports, unused variables, and non-idiomatic variable names.
Run Rustfmt, a tool for automatically formatting Rust code to the community-accepted style.
Run Clippy, a tool for ...
1
1 + 2 + ... + n = n * (n + 1) / 2, for example, 1 + 2 + 3 = 3 * (3 + 1)/2 = 6,
so the \$O(N)\$ is that:
sum the array, O(n) (no sorting)
check sum == n * (n + 1) / 2
3
I'll just review bubble_sort as an example. My quick notes:
Add a useful docstring and/or types (I had to read the entire function to realize that it was a generator)
When iterating over a range, use for in range rather than while. I also prefer using brief, generic variable names like i and j in lieu of names like index and test_index that are longer ...
0
Some benchmarking data as promised:
Cut to the chase, results:
--------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------
stl/100 3940 ns 3940 ns 173735
member/100 4756 ns 4756 ns 147187
lambda/100 ...
4
Indeed, your sortby when used in the style shown, with data members, will not be quite as fast as if you used the STL with a lambda. Look at the difference in assembly between
struct Date {
int year, month, day;
};
void test1(std::array<Date, 100>& a) {
sortby(a, &Date::month);
sortby(a, &Date::year);
}
void test2(std::array&...
2
The thing that sticks out the most is that your PriorityList, a priority queue, is a list instead of a heap.
You sort() the list every iteration, which (if implemented correctly) would be O(n log n), but in a proper priority queue adding/removing elements should be O(log n)
Your actual comparison-sort implementation is O(n), which is impossible, meaning it ...
1
I suggest to use numpy instead of Python lists.
For example your Grid class
class YourGrid:
def __init__(self,width,height):
self.board = []
self.width = width;
self.height = height;
for x in range(width*height):
self.board.append([])
for x in range(width):
for y in range(height):
...
1
So, the time complexity of the solution posted in the question is O(n^2 log(n)).
Answering each query takes n log(n), and we have n queries in total.
We don't necessarily need to merge the left and right subtrees to find the inversion count; given that the sublists are sorted, we can exploit binary search.
import bisect
from functools import lru_cache
...
3
assorted findings
your code does not document what predict() accomplishes
• I don't even get how the name predict is telling/helpful
• your code documents neither the approach chosen nor alternatives disregarded
comparing a cheaper monotone function of Euclidean distance: nice
• naming the variables without fussing that it's equivalent Euclidean at the end ...
4
If you use the .str attribute of the column, you get most of the standard Python string functions. In particular, with Python strings you can ask if a string contains another string with the __contains__() method (i.e. the in operator):
>>> "asdf" in "asdfqwerty"
True
>>> "asdfqwerty".__contains__("asdf") # equivalently
True
Pandas ...
5
I don't really know the libraries that you're using, but maybe the overhead of dropping rows from the CSV one by one is significant? You could try batching the drop (it looks like that drop function takes a list of indices but you're only passing it one at a time) and see if that speeds things up:
from pandas import DataFrame
from typing import List
def ...
0
Segment trees and Fenwick trees are usually implemented as implicit
data
structures. That
is, as an array with the tree structure implicitly given by the array
indices. Your code instead stores the tree as a Python dictionary
which is very inefficient.
The second problem with your segment tree is that you are using
recursion. Refer to this sample
code for ...
3
Needless for loop usage
for loops in Python are heavy. Using for loops needlessly leads to performance loss. For instance, rather than doing this:
for j in range(m):
if mat[i[0]-1][j]=="0" and mat[i[1]-1][j]=="0":
You could just count the number of ones using int(), bin() and | as below:
orResult = int(mat[i[0] - 1], 2) | int(mat[j[0] - 1], 2)
...
2
I don't have much time, and don't see any quick performance suggestions, but,
mat = []
for i in range(n):
mat.append(input())
Can be written more terse as a list comprehension:
mat = [input() for _ in range(n)]
And note how you never use i. If you don't use a variable, you can indicate that it isn't needed by calling it _. That's a placeholder ...
3
Here are some comments on your revised code, many of which apply to your original code as well.
for (auto& T: U) transform(T).find(max_perim, proc);
You're using the names T and U to refer to things that are not template type parameters. In fact, U is a reference to a static data member of the enclosing class, whose only declaration appears many lines ...
2
An answer to document how to integrate some of the excellent feedback points from @G. Sliepen in his accepted answer above.
The following have been changed from the original question above:
Remove constexpr since it is not required and opens up options for using the STL algorithms (except for the static U, where constexpr allows inline definition of this ...
2
Use of the lambda to process each triple
Sure, why not. Nothing wrong with using a lambda in main() here instead of writing a normal function.
Way of constraining the template to prevent unsuitable lambda's being passed. (C++20 concepts needed to do it cleanly?)
If you could live with pythag::triple::find() not being constexpr, then you don't need C++20 ...
1
Is there a way to improve the time complexity of this solution without
exceeding the space limitation?
Yes, there's a way. We don't actually need any additional array of numbers because we can check all numbers from 1 to the maximum possible mask for given elements of the array. Then, we will perform AND of the current number candidate with all array ...
3
Hi and welcome to the site. Your code already looks quite good. However, there are still some issues beyond what @Björn Linqvist wrote.
const correctness
This means that all variables as well as function arguments that are not mutated should be declared const. In addition methods that do not change the state of the object, aka pure observers should also be ...
3
The code is pretty good as it is. Here is how I would improve it:
Constant handling
In C++, you should prefer const over #define. So
#define INITIAL_CAPACITY 5
becomes
const int INITIAL_CAPACITY = 5;
Also don't use all uppercase names for non constant variables. It is
confusing and breaks the 50 year old tradition.
Clearer names
I renamed a few of ...
0
First of all, thanks to all the answers, I learned something new from all those answers.
Now coming back to the problem-statement, as no answer gave me an exact way of solving the problem in an efficient manner, so I did some research about the way the binary addition is performed, and I found that the algorithm described is known as No-Carry Adder in ...
1
I made a scrip that executes your data structure to test it. It doesn't verify correctness, it's just for timing purposes.
tic
uf = UnionFind;
uf.addItem(1);
for ii = 2:10000
uf.addItem(ii);
n = randi(4);
if n == 4 % happens in 25% of cases
uf.Union(ii, uf.Find(randi(ii-1)));
end
if n ~= 1 % happens in 75% of cases
uf....
1
Unfinished ?
You have the variable run set to false and then use it in a ternary to set i. run is never set to true. I assume you intended to set it true after scanning a plateau.
JavaScript Style
In JavaScript we put the opening { on the same line and else on the same line as the closing }
Spaces between operators. eg arr[i+1]; becomes arr[i + 1];
Always ...
1
You initialize a certain value as x but you never update it - even though this value is completely arbitrary. Which means you are not really using it in the solution. This is a certain indication that your solution is wrong, and only works on the special case that you tested.
If the "pivot" point (i.e. the point where the the max value is followed by the ...
2
Use <stdint.h>
If your system has it, use it. I bet your long is probably the same as long long, but to be sure of what you're using, use intN_t.
Use strtol safely:
(This part is about OP's own answer; not the question itself, which doesn't use strtol())
Using strtol is good because it can be safer, but it is a pain in the ass to use it safely.
...
1
First of all thanks to all the authors @user3629249 @G.Sliepen @chux-Reinstate Monica who provided valuable insights to the source-code of a command-line based merge-sort algorithm described in the Problem Description..
I have made important changes to the source code in order to make it better in terms of security, loopholes, buffer-overflows, ...
Top 50 recent answers are included
