@unborn hawk in functional languages, this operation is generally called "scan"
#algos-and-data-structs
ivory yacht
@haughty sleet You can use struct.calcsize() to get the number of bytes used on your system for various C numeric types.
unborn hawk
@brave oak thanks for your reply!
What would be the name for a similar operation that just performs operations between two adjacent elements without accumulating them? For example, getting the differences between adjacent elements, like [3, 2, 5, 1] returning the list [1, -3, 4], whereas an accumulate / scan would return [1, -4, -5].
ivory yacht
@unborn hawk There's an itertools "recipe" using the other functions at the end of the docs for this:
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
This uses tee to duplicate the iterator - allowing you to consume it twice. Then you discard the first item, and zip it together. You could then do starmap(func, pairwise(iterable)) to add the function on top.
unborn hawk
Ahh cool, didn't know what it was called! Thank you! Was wanting to include these functions in a small project but wanted to keep the naming scheme consistent with general usage. So map, filter, reduce, scan, and pairwise.
(I guess pairwise generalized to any n adjacent elements would be called an n-wise iteration - example being the Tribonacci sequence, a 3-wise iteration)
brave oak
you should look into fold
royal kestrel
just as a word of warning, tee doesn't actually "duplicate" iterators. Under the hood it creates a FIFO queue, so if you were to do something like a, b = tee(it); max(a); min(b) it would create a full queue from the iterator, defeating the point of lazy iterators and potentially being a memory hog. But in use cases like the pair wise the two iterators are never apart that much, meaning the inner FIFO queue only has to store a few items
long sleet
since on help channels noone helps i ask here xD
can someone help me using ffmpeg for python pls? ive followed the docs and examples there
but it seems to have no effect
bronze gazelle
That’s off topic for this channel
long sleet
isnt ffmpeg related with computer science? owo
bronze gazelle
No
long sleet
where then
bronze gazelle
A help channel
bronze gazelle
Have patience then
long sleet
ive been asking on help for 2-3 days XD
bronze gazelle
That doesn’t mean spam in unrelated channels
long sleet
i didnt think this was unrelated
fiery cosmos
I heared about it and I also know how to use it in small form factor
haughty sleet
what does it mean to concatenate a list destructively not copying the inputs
besides making a new list that has all the elements of two lists what does the destructive part even mean?
warm marsh
I guess they mean they want you to modify list A and add elements of B, thus "destroying" the original state of at least list A, instead of copying both into a new list and leaving the originals untouched
stark bridge
yep
>>> original = [1, 2, 3]
>>> new = ['a', 'b', 'c']
>>> original + new
[1, 2, 3, 'a', 'b', 'c']
>>> original
[1, 2, 3]
>>> new
['a', 'b', 'c']
versus
>>> original = [1, 2, 3]
>>> new = ['a', 'b', 'c']
>>> original.extend(new)
>>> original
[1, 2, 3, 'a', 'b', 'c']
past aspen
essentially got to continue doing this - for gcse comp science - really cant be bothered
last blaze
Yeah, your solution is what I think they were looking for, I was essentially trying to solve a different problem
balmy siren
and what is it for ?
last blaze
I was thinking in terms of levels of a tree
but this is fine
This book seems to take a slightly different approach to teaching trees than most other courses/books I've seen
balmy siren
ohhh .. so i'm doing it right?
but i didn't get the way they are doing it
can you please provide me any best idea of how to do it ?
last blaze
but its probably valid
balmy siren
in constant time
last blaze
In fact, I'm not entirely clear on what they've implemented
I don't think I'm really able to help you without actually reading the book myself. They definitely seem to teach this in a weird way
balmy siren
let me tell you, they already created an abstract base class of some Accessors of Trees and now they created an ADT of Binary tree (using some accessors of Abstract base class by inheriting it) so in Binary Tree ADT they defined three methods and those are left(), right() and siblings()
the left(node) method, return the position of node's left child
and right() also doing the same
And, now if we talk about sibling function then they just want to find the sibling of given node ..
But wait, i think .. if we have a binary tree and it's basic property is "Each parent have atmost 2 children" So suppose i've a tree something like this
A
/ \
B C
Okay, so if i need to find the sibling of 'B' then i only need to call the right() func. -> which return the position of 'C' and vice versa
I think, i get what they are trying to do
they created left() and right() for only binary trees, right? Coz each parent have atmost 2 childrens and you either get left child or right child
last blaze
I think, to find the sibling of B, you need to call right on the parent of B. So right(b.parent)
balmy siren
ohh yeah correct
thanks for mentioningthis
last blaze
so what they're doing in there function is checking the children of the parent node, and seeing if its the node you're looking for siblings of, if its a different node, it returns that
balmy siren
absolutely right ... you clear every doubts
last blaze
So assuming you want a version of the sibling function that works for a tree with any amount of children you'd end up with like
def siblings(node)
parent_node = node.parent
siblings = []
for child in parent_node.children:
if child != node:
siblings.append(child)
return siblings
which is what you originally had
and that is O(N) time
as for doing it in O(1) time, I'm not entirely sure how its possible
balmy siren
that would be case of finding simbling for every node, right?
balmy siren
and yeah that would be O(n) coz it iterate through each children but if we only want to find sibling of particular node of binary tree then acc. to your previous reply it done in O(1)
Really thanks man, you helped a lot
Now i get it what the author want to explain also this book is quite helpful for beginners and intermediate students coz the way of explaining such topics maybe lil. bit complicated at first but it's pure worth
or do you have any other Lectures of pdf's ??
I've also watched some MIT Intro. to Algorithms lecture but they are bit advanced and every topic is taken from Intro. to Algorithm book by cormen
last blaze
The MIT one is the one I've used and reccomended before
A lot of the time complexity analysis goes over my head
but I think the explanations of the core concepts are pretty strong
balmy siren
Yeah correct.. it's sometimes feel frustuated...
Also, can you tell me how much time should i need to give on which concepts of Tree DS ? currently i've some topics like mentioned in the attached picture .. are those enough, or there's more than that to cover in Trees
last blaze
It depends on what you're goal is - but in general traversal is pretty important, and being able to work with trees no matter how they're implemented is quite importatn
balmy siren
I'm interested in Sub-fields of AI like Machine learning and Computer vision .. so i checked few things about how Trees DS contribute in Machine learning and there comes the Decision Tree (a proper binary Tree)
last blaze
Decision trees aren't necessarily binary. For example I don't think ID3 is binary
But yeah, trees and graphs pop up all over the place
balmy siren
Why decision tree isn't a Binary ?? Is it because it may support more childrens.
Until now, i considered them as Binary Tree (coz it support the basic property of them like, number of external nodes is greater than number of internal nodes, each node have atmost 2childrens,
Number of external nodes = Number of internal nodes + 1)
tender wedge
what is external nodes of binary tree?
open kayak
An external node is one without child branches, while an internal node has at least one child branch. ?
tender wedge
so just leaves?
brave oak
yes, an external node is a leaf
an internal node is everything else.
@balmy siren I think most common implementations of decision trees are binary, but they need not be
tender wedge
A little paper showing runtime of python (with numba) vs go / c++ for the N queen problem :
(Pdf)
balmy siren
@brave oak can decision tree have more than 2childrens? (like, both of it's Parent childrens act as - if ... Then ... else clause) But is it possible to do something like this in decision tree
Age
/ | \
A<20 (A>20andA<40) (A>40 and A<80)
rich nymph
Why should it not be possible, that's the question you should be asking yourselrn
balmy siren
@tender wedge i guess the pdf you mentioned is all about
First we write the implementation
Then, we troubleshoot the implementation
And finally, we use Numba compiler to eliminate them
Also, there's two more compiler
- Nuitka
- Shedskin
tender wedge
Is that citation from the article ?
balmy siren
no ofc. not
tender wedge
Then i don't get your point
balmy siren
it's like as we know that python is slow in terms of it's performance also we've an intermediate called interpreter which convert bytecode into the machine code, so i guess it's bit like a heavy burden on python ...
so what that research paper mentioned in the last is -> We can achieve the same performance similiar to like C++ or go, in Python too, if we use numba compiler and if in any case, it doesn't provide the actual performance then we can write our implementation in any other language and use Cypython or any similiar thing
tender wedge
i still don't get what you're trying to say ahah
yeah they are comparing python + numba against C++/Go and find similar performances on the N Queen problem to argue that since python is more easy to write and
balmy siren
Ah sorry .. not good at explaining things
but you can check out the conclusion part of the file you sent
tender wedge
maintanable it's a suitable language for research
balmy siren
but Numba have some limitations too
tender wedge
This suggests that a perfectly valid workflow is to first write and debug a program in ordinary Python; identify the computational bottlenecks; and use Numba to eliminate them. This will work most of the time. In the rare cases where it does not, we can rewrite the relevant section of the code in C++ and call it from Python, which can be achieved using Cython [2] or pybind11 [4].
the full citation is this
this is what you meant?
balmy siren
Oh yeah ..
But i guess there's one more reason of why python is being slow and that reason is execution process of python program .. isn't it ?
i just wrote 3 points to summarize the entire conclusion part
tender wedge
your 3 points didn't refer to what is them so i had hard time understanding what you were pointing at
so are you saying that Python is slow because it's interpreted ? 😮
balmy siren
no not bcz it's interpreter but the modules or libraries which are designed for python is kinda heavy to run fast (Numpy or networkX)
and i guess, this problem can be overcome by using JIT Compilers which translates your bytecode into machine code
and provide faster execution
tender wedge
modules or libraries which are designed for python is kinda heavy to run fast
heavy in what sense?
balmy siren
heavy in terms of complexity, i guess
What are thoughts on it?
tender wedge
i was understanding the main problems comes from Python being dynamically typed, so you can't convert it easily to lower languages + the famous GIL thingy
balmy siren
let me tell you a scenario .. previous year i installed Pyaudio on my i3machine and at the time of installing it, All the cpu cores were using 100% and average swap amount was also more than 500mb and in the end it freeze
Dynamically typed is the advantage of python, isn't it?
tender wedge
it's so advantageous that Typescript and Type hinting are all the rages now :p
balmy siren
what do you use in general imperative programming? i mean, loops or list comprehension, generators expression, what?
acoustic fox
I'm looking up imperative programming and it just looks like shit scripting code. Do you have a resource that shows the advantages of imperative programming?
(When I say shit code, I mean the kind of code that I wrote when I was first learning python which was maximally garbage )
stark bridge
"imperative" is the opposite of "functional" -- it just means "modifying variables"
brave oak
I would say that "imperative" is the opposite of "declarative"...?
stark bridge
hm, could be
coral cedar
Hi
proven folio
last blaze
n * (log(n)**2)
proven folio
its just n^2
last blaze
I think log(n)^2 just becomes n right?
candid basin
whats the easiest way to peform OCR on easy clear numbers in a known location from a video game ?
Is there some librarie that can achieve this, or is it best to just collect a bunch of instances and train my own mnist ?
last blaze
OpenCV
I think you can do something like OpenCV+Tesseract
or possibly even easier
But OpenCV is probably part of the solution
candid basin
yeah i saw some "complicated" solutions that work but are too much effort, to not just use template matching for the 9 numbers
cunning bane
Hey, so I am a freshman in college aspiring to become a software engineer based in Austin and I was wondering if there is anyone available to speak with me regarding some questions I have
half lotus
If you have questions just go ahead and ask them, don't wait for someone to be available. When someone becomes available and they see your questions, they'll reply.
Just make sure your questions are fit for this channel. I suspect you may actually want to ask in #career-advice but I haven't seen your questions
warm echo
just started computer science course for gcse and im really passionate about it and i wanted to know of any good starting books/online courses/documentaries
currently (outside of class) im learning python and html - though mostly python - and have been receiving tasks to do from friends of mine who are taking more advanced computer science courses (uni, college)
i find it good for learning, though when i come across a hard issue i find it difficult to figure out a way around said problem, so i would like to know for any good starting stuff
chrome needle
stark bridge
postgres? It has a very good tutorial in the official docs, iirc
vestal umbra
yo guys if I need to pathfind (need to know if its possible and impossible to get from origin to destination T/F) and output the shortest path(moves taken), what algo do I need to implement? BFT?
gusty grove
you could go for A* if you want a efficient algo, usually A* performs pretty well at finding the shortest path
ofc if there is no path all algos will perform the same
vestal umbra
does A* works for a different kind of step? like a knight step on chess
gusty grove
yeah
vestal umbra
I implemented the A*, got some of the test_cases correct
I forgot to say that there might be more shortest way to the destination like 3 ways to there with same number of steps, and I need to know those too can I do that on A*?
but the way I understood A*, I cannot no?
jolly crypt
Guys i need help with this problem
So i can get a list of 100 random Hs and Ts, but how do i to get number of streaks in that list by implementing it in Python is what i am not sure about
stark bridge
ah.
you'll have to go through the list, one flip at a time, and keep saying "OK, is this the same as the last one I just saw? If so, increment a counter; if not, set it to zero"
stark bridge
@jolly crypt here's how I'd do it (I've been working on this for the last 35 minutes, so it wasn't super easy): ```py
import dataclasses
import operator
import random
@dataclasses.dataclass
class Streak:
starting_index: int
length: int
item: object
def run_length_encode(seq):
current_streak = None
for index, elt in enumerate(seq):
if current_streak is None:
current_streak = Streak(index, 1, elt)
elif elt != current_streak.item:
yield current_streak
current_streak = Streak(index, 1, elt)
else:
current_streak.length += 1
if current_streak is not None:
yield current_streak
flips = ''.join(random.choices("HT", k=100))
print(flips)
longest_streak = max(run_length_encode(flips), key=operator.attrgetter('length'))
print(' ' * longest_streak.starting_index, end='^\n')
print(longest_streak)
python3 rle.py
HTHTHTTHTTTHHHTTTHHTTHHHTTHTTHTHTTTHTTHTHHHHHTHHHHHTTHTTTTTHHHTHTTTHHHTHHHTHHTHTHTTTTTHHHHTHTTTTHTTH
^
Streak(starting_index=40, length=5, item='H')
if you didn't had to generate a list, i'd just store streaks
stark bridge
I kinda went overboard there, but it was fun
stable pecan
i think the easiest way to visualize a cyclic-hypergraph is to draw a 'tube' around the nodes the edge contains
fierce inlet
so wait is the wiki pic an example of a cyclic hypergraph?
fierce inlet
ohh right by cyclic hypergraph youre referring to the hypergraph with the cyclictuple edges
right?
i keep hearing cyclic and try to relate it to previous knowledge of graphs/edges/cycles
but i suppose this a different type of cyclic?
fierce inlet
so what do you use a cyclic hypergraph for
stable pecan
this would be a cyclic hyper edge
stable pecan
yeah, kind of
fierce inlet
xzibit.jpg
makes me think of some kind of state machine with overlapping transitions/states
stable pecan
we were using them almost in that sense, these edges
fierce inlet
physics simulation?
stable pecan
apologize for my bad art, but if you have two 'interacting' edges (adjacent edges) either one could transition to a new state illustrated like this:
the node a in the second edge, gets replaced with node b
particle systems don't have much to do with physics besides their motivation
fierce inlet
huh i see... i think
stable pecan
they're just a type of stochastic process
fierce inlet
wish i was better at math lol
stable pecan
ditto
these things are closer to conway's game of life than they are to physics though
vestal umbra
guys I have 2 lists on numbers and I need to compare if A list is a permutation of B list, assuming that all elemeents on A list is only 1 digit numbers and B list can contain any digit number, A list could only be a permutation of B list if all elements on B is also single digit right? 0-9 does that make sense?
stark bridge
why not just turn both lists into a set and then see if the two sets are the same?
placid sun
Hello, I'm asking myself how the == operator is made. I know it checks two if 2 values are equal, but i don't know how it does it. I can't find any reliable information on the internet, everything explains what it does not how it works in detail.
I know about bitwise operations aswell.
placid sun
Thanks a lot
stark bridge
not 100% sure that's the right spot in the code
placid sun
I need to look for the function returned right ?
stark bridge
beats me
I don't really know how to read the python source; I just know that the == operator is defined in there somewhere
placid sun
I found the function there but it doesn't explain how it works 😭
Can i search into the whole code in github or not ?
placid sun
I found every entry using the search bar and i'm trying to find what i'm looking for but thanks ^^
hallow raven
I've been wanting to learn how to calculate the complexity of my code. pretty much all about Big O notation. Is there a good resource out there?
young frigate
hallow raven
@cookie thanks
fiery cosmos
nice ping
gilded wigeon
hey guys, i kinda need help with an assignment, anyone good with algorithms and data structures?
hollow stump
ask
halcyon plankBOT
tender wedge
You still didn't ask your question
honest wasp
This is the problem
We need to go through every city from csv files with the data structures and algorithms provided in this picture
honest wasp
import csv # imported to handle csv files with "with"
from collections import deque # to use data structure deque
import math # to use math.sqrt
import sympy #to check number is prime or not
import time # to calculate time taken for the program
open the cities.csv in only read
with open('cities.csv', 'r') as file:
file_read = csv.reader(file)
# to put citiies and coordinates into list
cities = list(file_read)
# calculate 10% of the list
subnum = len(cities)//10
# to use the first 10% of the list, (first data structure, list)
sub_cities = cities[1:subnum]
print(len(sub_cities))
function to calculate straight distance between cities
def calculate_distance(x1,y1,x2,y2):
distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
return distance
#to know the starting time
start_time = time.time()
all_cities = len(sub_cities)
current_city = sub_cities[0]
sub_cities.pop(0)
shortest_distance = 0
close_city = 0
deque is used it can be used for insertion and deletion at both ends
d = deque()
d.append('0')
total_distance = 0
while (len(d) < all_cities):
# algorithm 1
# loops through the list of sub_cities to find the shortest distance to travel and select that city
for i in range(0, len(sub_cities)):
current_distance = calculate_distance(float(current_city[1]),float(current_city[2]),float(sub_cities[i][1]),float(sub_cities[i][2]))
if (shortest_distance == 0 or current_distance < shortest_distance):
shortest_distance = current_distance
close_city = i
# check if cities are multiples of 10 and whether number is prime
if len(d) % 10 == 0 and sympy.isprime(current_city[0]) == False:
shortest_distance = shortest_distance * 1.1
current_city = sub_cities[close_city] # sets our current_city as close_city
d.append(current_city[0]) # puts that city into deque
total_distance += shortest_distance #shortest distance combined into total
sub_cities.pop(close_city) # pop the closest city from list so that we do not have the same city twice
shortest_distance = 0
start_distance = calculate_distance(float(cities[1][1]),float(cities[1][2]),float(current_city[1]),float(current_city[2]))
total_distance = total_distance + start_distance
d.append('0')
print('Final order:')
print(d)
print('Total distance:', total_distance)
print("Time taken is", time.time() - start_time, "seconds.")
this is my assignemnt 1
we only need to use 10%
but now, we need to use all data
and we need to use one of those algorithms and data strcutures
tender wedge
hey, try to put your code between ```python
honest wasp
'''
import csv # imported to handle csv files with "with"
from collections import deque # to use data structure deque
import math # to use math.sqrt
import sympy #to check number is prime or not
import time # to calculate time taken for the program
'''
like dat?
tender wedge
import csv # imported to handle csv files with "with"
from collections import deque # to use data structure deque
import math # to use math.sqrt
import sympy #to check number is prime or not
import time # to calculate time taken for the program
# open the cities.csv in only read
with open('cities.csv', 'r') as file:
file_read = csv.reader(file)
# to put citiies and coordinates into list
cities = list(file_read)
# calculate 10% of the list
subnum = len(cities)//10
# to use the first 10% of the list, (first data structure, list)
sub_cities = cities[1:subnum]
print(len(sub_cities))
# function to calculate straight distance between cities
def calculate_distance(x1,y1,x2,y2):
distance = math.sqrt((x2 - x1)2 + (y2 - y1)2)
return distance
#to know the starting time
start_time = time.time()
all_cities = len(sub_cities)
current_city = sub_cities[0]
sub_cities.pop(0)
shortest_distance = 0
close_city = 0
# deque is used it can be used for insertion and deletion at both ends
d = deque() d.append('0')
total_distance = 0 while (len(d) < all_cities):
# algorithm 1
# loops through the list of sub_cities to find the shortest distance to travel and select that city
for i in range(0, len(sub_cities)):
current_distance =calculate_distance(float(current_city[1]),float(current_city[2]),float(sub_cities[i][1]),float(sub_cities[i][2]))
if (shortest_distance == 0 or current_distance < shortest_distance):
shortest_distance = current_distance close_city = i
# check if cities are multiples of 10 and whether number is prime
if len(d) % 10 == 0 and sympy.isprime(current_city[0]) == False: shortest_distance = shortest_distance * 1.1
current_city = sub_cities[close_city]
# sets our current_city as close_city
d.append(current_city[0])
# puts that city into deque
total_distance += shortest_distance
#shortest distance combined into
total sub_cities.pop(close_city)
# pop the closest city from list so that we do not have the same city twice
shortest_distance = 0
start_distance = calculate_distance(float(cities[1][1]),float(cities[1][2]),float(current_city[1]),float(current_city[2])) total_distance = total_distance + start_distance d.append('0')
print('Final order:') print(d) print('Total distance:', total_distance)
print("Time taken is", time.time() - start_time, "seconds.") ```so this is your bfs?
(just for style, people usually comment before an instruction and not after)
viscid mulch
@spiral swallow so also, how would the number of workers be affected by the number of cores on a pc
spiral swallow
Well, if the task is cpu bound, a worker is going to max out a core, so more cores allow for more fulltime running workers
If the task is io-bound, a worker can advance while others on the same core are waiting on io
viscid mulch
could you show me how to create a script that would allow me to choose how many cores to use and then run a parralelizable script that is cpu bound?
spiral swallow
Not right now, i'm on phone, and i'm sure examples of that abounds, look at map/reduce tasks for example, also, hash collision is one that should work well.
What you need is to have:
a function that can process a bit of the data indepenantly
a worker that can take some input, apply the function to them
a manager to start as many workers as you need, giving each a part of your whole input
For hash collision you could end as soon as one of the workers found a solution, or all of them are done without success.
viscid mulch
I like that hash collision example yeah
um so to test how # of cores increases efficiency, I would want to create the max amount of workers per core?
spiral swallow
I'm not expert in that, i often see people use n+1 workers on such tasks, n being the number of cores
The +1 would make use of the times on any core that is still spent on io
But when you are done building it you can actually test and see how many gives optimal results :)
It's certainly ≥ n
Remember that python is special though, if you use threads, you'll need to remove the GIL in your worker, which is possible if you implement it in cython or C
Multiprocessing should work without that, but it does bring different constraints (memory sharing), or you could just run N python processes, using subprocesses in threads.
spiral swallow
Have fun :)
viscid mulch
If I can't find anything, or am really struggling, would there be a time later when you would have access to a pc and would be able to help me?
spiral swallow
Sure, just ask, i'll see if i can help then, or someone else maybe will :)
viscid mulch
@spiral swallow hey sorry to bother you. I've tried looking for the last few hours and cannot find any script online that would allow me to choose how many cores to run a hash collision script
I need to collect data for my class in 6 hours and am super stuck 😦
spiral swallow
oh, you can't really activate/deactivate cores at runtime, i think you can tell your kernel to only use some cores if you are on linux, but that's pretty low level
but you can choose how many processes/threads you run, and the OS will be able to make them run on different cores automatically
if you have one monothread program, it can only run on one core at a time, but if you have multiple threads it can run on multiple cores at the same time, each thread on a different core at any given time (they can change core from time to time, it's a time shared system, the OS decides what runs where, it's not your concern)
viscid mulch
I just need a program where I can prove amdahls law
spiral swallow
how much time did you get for this assignement?
viscid mulch
was supposed to get 3 days, but I only got one due to flex schedule at my school 😦
spiral swallow
also, you need a bit more than running on multiple cores to prove amdhal's law, is it's about the amount of code that is parallelizable in your app
did you read https://en.wikipedia.org/wiki/Amdahl's_law ?
spiral swallow
ah, so your assigment wasn't specificificaly about it?
viscid mulch
how would I determine the amount of code that is parallelizable in my app though?
spiral swallow
two days seems a bit short for a student to build a program that demonstrates it
i don't have a generic answer to that question, it's pretty big i think
viscid mulch
so my assignment was to choose one or the other and collect data to create a correlation between num of cores and speed
spiral swallow
it's easier to answer about the amount of code you know is not parallelizable
if you have a critical section (semaphores), then you know two sections using this semaphore won't be able to run at the same time
if your worker needs to wait on the availability of work from another worker, then it can't run concurrently, it's not really parallelizable
etc
you can of course simulate that by having your workers wait some time in parallel, then adding a semaphore in some of the waiting, simulating that say 50% of the work is not parallelizable
viscid mulch
hmmm
couldn't there be some code online that would say what percentage of the code is paralleilable?
i just cant seem to find anything
but I feel there should be something
I don't need to create my own code I can use code online
spiral swallow
i don't think it's something that can be programatically determined
viscid mulch
okay
so what other experiment could I do in general to determine the corrleation between cores and speed?
if not related to amdahls law if we don't know the theoretical part of the program that is parallelizable
viscid mulch
but what happens if for example
I go to windows
set affiniity
and run something that is 0% paraleziable
then it wont matter on the number of cores I chose
it'll all take the same time
how can I make sure I don't do that to myself
spiral swallow
do you understand this
from sys import argv
from time import sleep, time
from threading import Thread, Lock
lock = Lock()
def worker(lock_wait, unlock_wait):
if lock_wait:
lock.acquire()
sleep(lock_wait)
lock.release()
sleep(unlock_wait)
def manager(lock_wait, unlock_wait, workers):
jobs = []
for w in range(workers):
job = Thread(target=worker, args=(lock_wait, unlock_wait))
jobs.append(job)
job.start()
for j in jobs:
j.join()
if __name__ == '__main__':
lock_wait = float(argv[1])
unlock_wait = float(argv[2])
workers = int(argv[3])
begin = time()
manager(lock_wait, unlock_wait, workers)
end = time()
print(end - begin)
?
i'm practically handing you the solution, you just need to plot with various values
viscid mulch
what does the Lock method do?
spiral swallow
it prevents multiple things happening at the same time
it's a semaphore
well, a lock, which is a specialized case of the semaphore
this doesn't really use the cpu much, it simulates work using sleep, but it could to real work instead, like calling a factorial of a certain amount instead
viscid mulch
gotcha
so the different argv indexes
3 is number of workers?
I dont quite understand what 1 and 2 are
spiral swallow
3 is the amount of workers yes, 1 and 2 are the amount of time to spend in lock (preventing parallel), and in parallel
viscid mulch
so how many workers could i put?
would it ever break if i put a stupid high number?
spiral swallow
this part i'll leave to you, you have to understand these things to pass your course
viscid mulch
the problem is im in highschool and the only one taking this "course"
I'll try and read some more though i guess
spiral swallow
maybe reread my answers, i think i explained the relation between cores and workers already
but congrats on studying that already, the things i programmed in high school were much less CS oriented
viscid mulch
I took AP CS A in 9th grade and my school doesn't offer any other CS classes. The teacher offered me my own "CS" course since she saw I really liked the course but since theres no curriculum its kinda rough
spiral swallow
then i guess she'll be very understanding and spend some more time explaining you the parts you are missing if you come back without a full answer to the question he asked, as long as you did the research, as you seem to have
viscid mulch
i hope so
do you think that if I messed with the values of argv[1] and [2]
to set them up in a proportion
like overall out of 10
so [1]+[2]=10
and then change the number of works from 1 to n+1 for each "proportion"
that would be sufficient data?
spiral swallow
yes, that's exactly what you want to do 🙂
though, with this simulation of work, you could gain even more "speed" by putting more than workers, because they don't max out a cpu, if you had something that takes linear time on the cpu to do instead of sleep, it would be a better simulation
viscid mulch
the one issue I run into is I would expect that if I ran the script with 5 5 1
it would take longer than 5 5 2
but its the opposite
5 5 2 takes longer
I thought workers would reduce the time
warm marsh
well, chromium. that's rather a question for #web-development or off-topic though ¯_(ツ)_/¯
hallow raven
@long vigil sorry about that, I'll post it over there.
long vigil
@hallow raven tagged wrong byte ;)
viscid mulch
@spiral swallow any idea of what I'm doing wrong?
spiral swallow
@viscid mulch hm, i now realize the amount of work is not constant, the total amount of second waited is different based on the number of workers
and since you have 5 seconds on each time that can't be run concurrently, then you have 5 second more when you add a worker, bummer, sorry for providing a bad example 😦
carmine scroll
Hello everyone! Anyone willing to help me in my problem about Unet? The output seems buggy, cause prediction results are always grey.
fiery cosmos
I see you guys there are very experts 🙂 Can you tell builtsin.open function is CPU bound or IO bound and why?
I found that IO bound programs are common functions with network / database, but what’s hell with open?
spiral swallow
Acces to disk is IO, just like network and whatever DB you use, the cpu spends most of its time waiting for data to arrive so it can work, that's what IO bound means.
IO means input/output
tall nebula
How can a black and white image be represented as binary?
gusty grove
if its black its 0 if its white its 1
if you know the image width and height you can just have it be one long list of 0/1
tall nebula
Is this a good answer
For a black and white picture, a 1-bit binary code, using 1 for black and 0 for white, is sufficient. A higher resolution image can be produced by using more, smaller pixels.
stark bridge
sounds like an exam question 🙂
In any case, if you just use 1 for black and 0 for white, you won't have any grey, unless you are very careful and clever
bronze gazelle
Not much of a question
small quarry
is this a question channel?
bronze gazelle
It's definitely not an insult channel
small quarry
ok
unreal mirage
@small quarry what's an example of other than grade 1 stuff brah?
blissful stone
Binary trees
warm veldt
If I'm going to be creating a program that performs calculations on points in 3 dimensional spaces that are affected by rotations, should I interpret them as quaternions or just keep it simple. It has to do with rubiks cubes if that provides more info lol.
spiral swallow
it's probably safer to just work with quaternions for all transformations, you can still convert to euler or something else for displaying, as it's easier to visualize
warm veldt
Ah alrighty; what makes them safer to work with over anything else? Is it computationally more efficient to do so?
ivory yacht
Yes.
For euler angles, you can't really do anything to them - there's no direct formula for rotating one.
There's also the problem of "gimbal lock" - if you rotate certain directions, you can end up with two axes lining up with each other - then you loose one axis and so can't rotate in all directions without recalculating the angle.
Quaternions don't have that, and also can be interpolated - you can calculate the rotation 30% from A to B, pretty important for animating and whatnot.
tiny whale
would parsers and EBNF be on topic for this channel?
spiral swallow
that seems quite appropriate yes
icy crater
need some help with cv2
basically I'm trying to put a png logo (with text) into an image but i keep getting results without shadow on the text
even if I make the text stroke (and glow) with color it stills removes it and just outputs a white text
balmy spoke
Hey, i do not remember who suggested me 3 blue 1 brown, but that guy is awesome! I completely forgot everything i learned about matrices, but after starting to watch videos i think it's the first time in my life when linear algebra started to make sense!
gusty grove
Yeah hes pretty great
spiral swallow
+1 to that, it's incredibly well done and educational, even for quite advanced topics (the ones about fourier transform, or about quaternions takes you so gently through the concepts, it would be a stretch to say it makes them easy, but it goes a long way)
also, he shares the software he uses to create the animations as open source
stable pecan
written in python!
timid surge
and it's available on github
warped pewter
data structures
south slate
I am struggling to see any real difference between Remote Desktop connection and remote login .
can someone please help me here?
old forge
@south slate could you clarify your question?
main bison
what has this to do with computer science @south slate ?
main bison
since it has nothing to do with python, you should post it in off-topic
south slate
Done
median trout
I want to work on a 2D logic game who has an arbitrary grid (square cell, triangular cell, ... , and mixed type cell !). I need to keep information about the cell (content, neighbor), the edges (state) and the dots (= two end of an edge) coordinates for later imaging. Is there some kind of known best class/structure to work with these grid ?
old forge
@median trout https://wiki.python.org/moin/PythonGraphApi
cell and dot are the same thing - mentally incorporate the dot info into the cell it is touching
sometimes people call these 'nodes'
edges are the links between nodes
median trout
Thanks ! Looks interresting 🙂
trail light
vocal raft
To those who self-learned or took classes, how do you write computer science notes? Should I try to write down code on pencil and paper?
Normally I use the Cornell Note Taking Method for my other classes, however I don't know how effective that would be for programming.
slim vault
It depends on what works for you, but I haven't taken that many notes during my degree I don't think
We were always given all learning material, slides, lecture recordings, etc
last blaze
Paper notes have been shown to be incredibly effective
slim vault
I think it's good to just program a lot, program things that interest you, do all labs, and come to labs as much as you can
slim vault
I draw / scribble a lot when thinking, trying to visualize concepts and ideas, but I dont take that many notes
But its super individual, you can experiment and see what works for you
Just try to be comfortable in your learning is what I'd recommend
frosty hornet
Pls recommend me some good books on nlp
I am unable to properly understand the concepts through standford’s video lectures
last blaze
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/
MIT 6.006 is a great course for an introduction to algorithms and data structures. The course covers quite a range of stuff, from data structures like trees and heaps, to shortest path with Djikstra. The explanations they provide are much better than anything I've encountered elsewhere, and they provide some exercises (some based in Python) that can be used to practice.
fiery cosmos
Are there any Discord’s for Java ?
outer lake
Someone just shared this one: https://discord.gg/hVtnwGd
azure matrix
from typing import List
def f(_list: List[int]) -> List[int]:
n = len(_list)
return list(x * n for x in _list)
Intuitively I feel like this function would commonly be described as O(n). You iterate through each item in the array and perform a multiplication operation.
But things like multiplication aren't really O(1), they have time complexities like O(n**2) or O(nlogn) depending on the underlying implementation (https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions).
So is the function above O(n) or not?
(*note: the time complexity for these functions has n referring to the number of digits but my question stands)
feral shale
the O(n*2) / O(nlogn) for multiplication is for a different n
i.e. the number of digits of the numbers
you would assume n is the size of the list when asking the complexity of f()
hollow mauve
hello!
i'm taking intro to CS right now and i need help with a couple practice problems
high stratus
!ask
halcyon plankBOT
high stratus
no, i mean read the tips
hollow mauve
oh okay
high stratus
just ask for what you're talking about
hollow mauve
here, i'll go find the instructions
brb
Write a program that uses two input statements to get two words as input. Then, print the words on one line separated by a space.
those are the instructions
i'll go run my code in codeskulptor, brb
a = input('Input a character.')
b = input('Input another character.')
print(a " " + b)
so there's my code
and here's the error i'm getting
Line 3: SyntaxError: bad input ('" "')
hollow mauve
i figured that out, but thank you
verbal phoenix
oh, haha
hollow mauve
it had to be (a + " " + b)
verbal phoenix
yup
hollow mauve
that was a typo and it worked haha
verbal phoenix
it works now?
hollow mauve
yeah
i have another one i might need help with
one second
so for me to put a comma, would i just do the same thing
?
like (b + "," + a)
hollow mauve
okay
verbal phoenix
who told you that?
verbal phoenix
🤔
hollow mauve
oh it is?
verbal phoenix
(b, a)
hollow mauve
ohh i did it
print(b + "," + a)
i put that
i'm gonna go run it through the judge to make sure
it said wrong answer
well class is over
thank you for your help
royal kestrel
@azure matrix depends on what "n" here is defined to be
If n is defined as "the size of the list" then the loop takes O(n) iterations and the multiplication takes O(log n p) where p is the total amount of bits present in the array
azure matrix
But it seems like we usually just act like multiplication is O(1) right? E.g. "multiply all items in an array together" -- I feel like commonly people just go oh yeah that'd be O(n)
'cause n items
or exponentiation etc
brave oak
yes
because for the bit lengths we see normally
it might as well be constant time
just like in Scala the time taken to access an element in a Vector (type of collection) is technically O(log n), but the base of the logarithm is so high that accessing an element in the biggest possible Vector (2 ** 31 - 1) takes only 6x the amount of time it would to access the single element in a one-element Vector
small quarry
import turtle
alex = turtle.Turtle()
jason = 1
alex.speed(10)
simon = 0.1
while jason != 2:
alex.forward(simon)
alex.right(simon)
simon = simon + jason
atom
high stratus
alright so i'm managing to be big dumb somehow i think? i'm converting images to numpy arrays for storage in an hdf5 file. last time i've done this it managed to half the total size of the images i was handling but now, before i'm even storing them in .h5, the size of the array of all the images loaded ends up being more than double that of the original. (from 15.9MB to 59MB...)
how can i fix this so it's not absolutely terrible or what am i doing wrong (or don't know is happening)
spiral swallow
@high stratus what do you store in numpy, rgba values, or the png/jpeg/whatever encoded data?
Because usually the former is much bigger than the latter
high stratus
@spiral swallow i'm just straight up doing np.array(Image.open(image))
so i'm unsure of which
they are RGB, not intending to grayscale them
gusty grove
You might want to change the datatype
I dont remember if pillow uses 0-255 or 0-1, but if its the first one, store as uint8 :)
high stratus
it stores as UINT8 for both as it understands the values
pillow is just 0-255, it only reads the image as is. you have to specifically rescale the image for 0 to 1 values
that's not my issue
spiral swallow
I'm pretty sure what you get here is rgba, so i't going to take as many bytes as 4 times the amount of pixels in each image, do you need yo treat them as image? If you just read them as files, it'll be much smaller.
@high stratus
high stratus
@spiral swallow i just need it to be able to be re-read properly and intact. as long as the image can still be read from bytes or whatever that's all i need. how would i go about fixing this? i'm unsure honestly
spiral swallow
Use open, not Image.open
You can open them as images later when you read back from your hdf5 file for usage
Not sure what you need numpy for and what you use the hdf5 file for, just saying that pillow will decode a png or jpeg file into a rgba array, wich is much bigger, like a bmp, because it's more convenient to work with in memory, but if you don't need that, it's quite wasteful
willow radish
Is there a scope for Markov chains to be used somewhere ? Like I've seen one https://www.reddit.com/r/SubredditSimulator/.
tribal pendant
Hello, I've several questions related to math operation with python.
x: int
#Is this O(1) in complexity? Because it always return 1
x**0
#Is this O(1) in complexity? Because it always return x
x**1
#Is this O(1) in complexity? Because it always return 0 if x≠0 and 1 if x=0
0**x
Unfortunately I don't find answers on the web
spiral swallow
can you think of experiments to confirm/infirm these hypotheses?
high stratus
@spiral swallow I attempted reading the bytes of the image before (unless you just mean open(image, 'r').read() instead of open(image, 'rb').read())
Also doing hdf5 as a faster read for what I'm doing instead of dealing with a generator over a folder
tribal pendant
@spiral swallow Well, yes, I can test with like 1**0 and py 2345621123456789842123456789876543567890987654322345678998764323456789865432345678**0 but it seems a bit primitive
spiral swallow
i would construct a loop and see how it evolves with time, but if the example you gave is instant, i would assume it's 0(1)
the only way to be sure is certainly to read python source code
high stratus
What would you suggest me doing then by the way?
spiral swallow
hm, i don't know much about hdf5, looking at the doc it does seem it could be more convenient to use numpy, but you should be able to create the bytes from reading the file directly, with rb mode, but i didn't experiement with that
tribal pendant
$ python3 -m timeit "1**0"
20000000 loops, best of 5: 16 nsec per loop
$ python3 -m timeit "2345621123456789842123456789876543567890987654322345678998764323456789865432345678**0"
20000000 loops, best of 5: 15.3 nsec per loop
For the record it's definitively O(1)
spiral swallow
yeah, i would have been surprised by the contrary 🙂
tribal pendant
$ python3 -m timeit "1**1"
20000000 loops, best of 5: 15.7 nsec per loop
$ python3 -m timeit "2345621123456789842123456789876543567890987654322345678998764323456789865432345678**1"
500000 loops, best of 5: 617 nsec per loop```
😱Wow
$ python3 -m timeit "1**1"
20000000 loops, best of 5: 15.4 nsec per loop
$ python3 -m timeit "1**2345621123456789842123456789876543567890987654322345678998764323456789865432345678"
50000 loops, best of 5: 6.18 usec per loop```still pretty flat, but indeed not 0(1)
tribal pendant
Yep, with any number different than 1 it cannot compute
(Or I didn't wait enough most probably)
fiery cosmos
Hey, I have a question, regarding more of "is it possible" rather than "how to program XYZ"
do you think there are more "unknown" sortings of arrays we don't know about?
or you think the fastest one has already been 'revealed' ?
stark bridge
very unlikely we'll find a faster one than quicksort, but they probably thought that in 1960 too
stark bridge
whatever it is.
fiery cosmos
I mean, they are quite the same but timsort is quicksort on steroids
stark bridge
python probably uses timsort for reasons other than simply "it's fast"; it probably has some qualities that make it particularly suited for python.
brave oak
why do you say that timsort is quicksort on steroids?
fiery cosmos
iirc from university they were similar in code but timsort was efficient in some ways
or maybe it was another type of sorting, like merge
brave oak
think you're thinking of mergesort
timsort is like mergesort except it does better when input is already partially sorted
timsort is stable and quicksort isn't
balmy siren
I heard that sorting function of python uses timsort?
Or it is timsort
balmy siren
And does it make a use of insertion sort also ? For small inputs?
spiral swallow
i think there is a pretty thorough description of it in the PEP that introduced it
royal kestrel
@tribal pendant assuming you are talking about CPython, because it is an implementation detail, for exponent 0 there is a special branch to return early
which actually also handles if the significand is 0
for 1 I don't think such a thing exists
but it also only does one iteration of any given loop in the function so one could argue that it is in fact O(1)
plush idol
if i implement a recursive function, the time complexity would be similar to loop right?
stark bridge
depends on the function
plush idol
binary search
stark bridge
if you are traversing, say, a list in the simple obvious recursive way, then the time complexity would be linear, like a loop
binary search should be logarithmic
plush idol
stark bridge
that's so hard to do with a loop that I suspect nobody does it
plush idol
yeah i assume
but the prof wants the way to calculate the exact number of operations
so idk how to explain
i assume its something like log(n) + 1
but idk how to explain that in terms of exact number of operations
last blaze
Write it out on paper for a few examples
brave oak
@stark bridge wouldn't you just use a stack for that?
balmy spoke
What's the best way of implementing tree structures in python? Native collections do not have something similar. I probably can do a ghetto tree by using dict of child-parent pairing or a set of cross-referenced objects, but odds are it would be horribly unoptimised compared to a tree made by you know - competent programmer.
- Is there a tree structure in well-supported lib? 2)Why there are no trees in standart library?
stark bridge
@brave oak you could indeed use a stack for that -- the easiest way is to use python's runtime stack, which is another way of saying: write a recursive function 🙂
brave oak
yes, I agree that recursion is a much more natural way of expressing solutions to such problems...but if one were to do it iteratively...I would suggest a stack
an explicit staack
stark bridge
fairy nuff
tribal pendant
@royal kestrel Thanks for the insights
Btw, I'm searching how is implemented the pow function in CPython, I've searched it on the GitHub repo but couldn't find it. I'm asking because I made a similar function which is thousands times slower, and I want to understand why. I suspect the function is written in C
stark bridge
almost certainly C
it's also possible that the Python C code uses some third-party library to do the math for it
balmy spoke
Hm... I remember something about it
Lemme check
Basically, there is #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
Bigger numbers than that use optimised algo
Apparently, that one https://en.wikipedia.org/wiki/Karatsuba_algorithm
It's just i accidentaly stumbled on a mention about it in blogpost about int implementation
feral shale
well you cut off the rest of the text so how are we supposed to respond
it does depend on tail call elimination to work well though so it's probably that
royal kestrel
I think the point being made here is that it would be much simpler to maintain and express this as a simple loop
This example is really a poor use of recursion. When recursion is properly used, it is difficult to convert the recursion into a simple loop structure. In this case, the analysis will involve a recurrence relation that needs to be solved. To see what might happen, consider the following program, which turns out to be a horrible use of recursion:
tender wedge
Who wrote that?
spiral swallow
recursion is always the worst way to solve a problem, sometime it's also the best one, but that's because it's the only one. 😛
(you can make that recursive program fast by using memoization though, but it's still better to use a loop)
spiral swallow
recursive solution tend to confuse people though, they can be hard to reason about
tender wedge
true
i did at work once, and they removed it
because they were not sure how it worked
; - ;
main bison
i could not agree more with @spiral swallow here.
fibonacci sequence is such a perfect bad example for teaching recursion
its a perfect example because it fits the solution. but it makes it hard to convert that to a real world problem
my favorite recursion example is to implement quick_sort using recursion
no need for fancy memoization, no need for deep DP techniques to make it work. just a simple (no pun intended) sort 😄
anyone that has implemented quick sort using normal functions will be amazed on how great and readable the recursive one is.
spiral swallow
yeah, it's been a long time i implemented it, but keeping track of where you are is a pain without recursion i'm sure
main bison
want me to show you the recursive way?
spiral swallow
sure 🙂
main bison
im an advocate to stop using fibonnacci to teach recursion 😄
so lets sort this list
l = [i for i in range(100_000)]
random.shuffle(l)
the base case is that the current list we are sorting has a length of 1
or 0
then we know that the list is sorted
the pivot needs to be picked at random
import random
def quick_sort(list_of_numbers):
if len(list_of_numbers) <= 1:
return list_of_numbers
pivot = random.choice(list_of_numbers)
this makes a very simple base case that is easy to understand
so the algorithm tells us that we need to pick a pivot, and sort values that are less_then equal and greater_then
so now list-comprehension to the rescue
less_then = [n for n in list_of_numbers if n < pivot]
equal = [n for n in list_of_numbers if n == pivot]
greater_then = [n for n in list_of_numbers if n > pivot]
so we want to return the lists in this order as a recursive call
and since we are working with lists, we can use + between them
return quick_sort(less_then) + equal + quick_sort(greater_then)
and we are done
spiral swallow
%s/_then/_than/g
main bison
with more or less 4 lines of actual code
!e
import random
def quick_sort(list_of_numbers):
if len(list_of_numbers) <= 1:
return list_of_numbers
pivot = random.choice(list_of_numbers)
less_then = [n for n in list_of_numbers if n < pivot]
equal = [n for n in list_of_numbers if n == pivot]
greater_then = [n for n in list_of_numbers if n > pivot]
return quick_sort(less_then) + equal + quick_sort(greater_then)
l = [i for i in range(100_000)]
random.shuffle(l)
sorted_l = quick_sort(l)
print(sorted_l[:10])
@main bison :white_check_mark: Your eval job has completed with return code 0.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
yes. its not efficient. its just to teach recursion
spiral swallow
yep, for that, sure
main bison
but it is still very fast
it creates 100_000 lists and join them together
well.. not that many i guess.. but still.. working with lists does not scale well for larger things.
i once saw a 200 lines implementation of this, using 3 or 4 helper functions..
it was a real mess
spiral swallow
i remember implementing it in C, in place, on paper, for an exam
main bison
i did the same, on paper, but with java
spiral swallow
i really felt like i got it right, but with hinsight, that seems quite unlikely 😄
main bison
😄
stable pecan
should teach finding inner mosted nested parens with recursion
spiral swallow
hm, sounds like it should be pretty straightforward with a simple loop and two integers?
ok, 3 integers, position of current deepest paren found, depth it's at, and current depth
stable pecan
that's pretty close to how i did it, granted i don't think my solution is very elegant
i had this little bit of code when building my own reg ex:
def find_matching_parens(expression):
"""Find matching parenthesis in some expression."""
scope = 0
for i, symbol in enumerate(expression):
if symbol == '(':
if not scope:
start = i
scope += 1
elif symbol == ')':
scope -= 1
if not scope:
return start, i
def find_deepest_parens(expression, indices=(0, -1), offset=0):
"""Find a most nested pair of matching parenthesis."""
if (new_indices := find_matching_parens(expression)):
start, end = new_indices
return find_deepest_parens(expression[start + 1: end],
indices=(start + offset, end + offset),
offset=offset + start + 1)
return indices
there's probably a much nicer way to do this
spiral swallow
hm, what's the expected result for '(()' for example?
def find_deepest_matching_parens(string):
max_depth = 0
current_depth = 0
result = None
begin = None
for i, c in enumerate(string):
if c == ')' and current_depth > 0:
if current_depth > max_depth:
result = begin, i
max_depth = current_depth
current_depth -= 1
elif c == '(':
begin = i
current_depth += 1
return result
assert find_deepest_matching_parens('') == None
assert find_deepest_matching_parens('()') == (0, 1)
assert find_deepest_matching_parens('(()') == (1, 2)
assert find_deepest_matching_parens('(())') == (1, 2)
assert find_deepest_matching_parens('((())') == (2, 3)
assert find_deepest_matching_parens('((())(((()))))') == (8, 9)
assert find_deepest_matching_parens('(((aaaa))(((()))))))') == (12, 13)
assert find_deepest_matching_parens('(((aaaa))))(((()))))))') == (14, 15)
assert find_deepest_matching_parens('))(((aaaa))))(((()))))))') == (16, 17)
assert find_deepest_matching_parens('))(((aaaa))))(((())))))()()())') == (16, 17)
i return the pos of the closing parens, not opening one, it's a bit arbitary, but it's not a lot harder to return the opening one
stable pecan
(() not a valid expression, so i didn't consider it
spiral swallow
is my solution valid to you? i kind of prefer it as it avoid recursion, and seems easier to understand to me.
i guess i could return the beggining as well, like you
stable pecan
seems fine, my strategy was just to keep finding matching parens until the expression was atomic -- it wasn't necessarily the deepest parens in hindsight, just there were no inner parens left
but you might find an even simpler solution given that --- i think we could just search for a ( followed by a ) in hindsight
hmm, find the first ) and rewind maybe
plush idol
what should the general equation to calculate the output for s given n
i tried to solve it for 1 hour but couldnt figure out the pattern
i hope this is allowed even tho its cpp
stable pecan
i can tell you if you know what cpp function returns the number of ones in the binary representation of a number
plush idol
i only know how to do binary representation in digital circuit 
, im dumb when it comes to cs related stuff
stable pecan
In [173]: def f(n):
...: if n % 2 == 1:
...: return f(n-1) + 1
...: return 2 * n - bin(n).count('1')
In [174]: def g(n):
...: s = 0
...: while n > 0:
...: s += n
...: n //=2
...: return s
In [175]: all(f(i) == g(i) for i in range(100))
Out[175]: True
well, i can provide solution in python
or we can one- line it:
def f(n):
return 2 * (n - (n % 2)) - bin(n - (n % 2)).count('1') + (n % 2)
def f(n):
m = n//2 * 2
return 2 * m - bin(m).count('1') + (n % 2)
how about that?
wet wave
Is this channel open for me to post a question?
stark bridge
I guess so
wet wave
I posted it in #help-coconut too hoping someone would answer
stable pecan
ooo, turns out this works too:
def f(n):
return 2 * n - bin(n).count('1')
odd numbers don't need a special case
runic tinsel
it's an intrinsic, something like __builtin_popcount
if you know what cpp function returns the number of ones
tribal pendant
I'm a bit late, but thanks for the info on the implementation of the pow function!
fiery cosmos
Hi, I have a question regarding Asymptotic notation,
if i have a function that gets N and does this:
def some_func(N):
for i in range(2**N):
for j in range(N):
do_something...
the first loop executes 2**N times, and inside of that a for loop of N times gets executed
so its N that happens 2**N times = O(N*2**N)?
spiral swallow
Yes
acoustic fox
I've learned doing coding problems that is is perfectly find having a constant number of N loops
def something_():
for i in n:
i_opperation()
for i in n:
i_opperation()
for i in n:
i_opperation()
that is only O(3n)
fiery cosmos
Is it possible to do AI ML in pure javascript? Is it possible to do the same stuff in javascript as in python? In the AI perspective
last blaze
Its probably possible, but there won't be near as much support or as many resources
fiery cosmos
Yeah true. I wanna learn ai and ml and I know JavaScript 100 x better then python
But code is code, it should be possible with JavaScript but maybe from scratch, not like the python have all packages with ml premade stuff
And tensorflow
last blaze
Honestly, writing Python with the ml/science libraries is very different to writing it for software development
I'd definitely reccomend sticking to Python for it
eager hamlet
so, im doing this USACO problem (i dont know if this is appropriate but it is algo-related so...): https://train.usaco.org/usacoprob2?a=6uQfUN1HTTB&S=castle
and here's my current implementation of the problem: https://paste.pythondiscord.com/bilukopiba.py
but the problem is it runs too slow if holyMusicStops.txt has this data inside it: https://paste.pythondiscord.com/geqojibujo.py
so is there an alternative implementation that would have me rewrite my whole code, or is there a way to simply optimize my current code?
(ping 4 reply thx)
fiery cosmos
Can someone plz help me get internship for data science please
royal kestrel
In asymptotic notation O(3n) isn't a thing it's just O(n)
spiral swallow
and to be clear ```py
def something_(n):
for i in range(3):
for i in n:
i_operation()
has the exact same O(n) complexity, counting the number of nested loop is not a good way of estimating complexity.
north zealot
O(n) just says that the complexity is proportional to the size of the input
brave mortar
Anyone ever used blind app? Heard it's good for carrer advice. I really need one.
high stratus
this channel is moreso for cs topics
sly patio
@fiery cosmos try NimLang. It compiles to JS and has a great FFI for it.
It's also gaining ground in the scientific programming space.
tribal pendant
What's the fastest to access? a in my_list or my_dic[a]?
I would say naively my_dic[a] because that's why dictionary should exits, but I'm not sure
royal kestrel
the answer is it depends
But generally it is faster to do lookups in dictionaries
If you want to think about it on a purely theoretical basis then dictionary lookup is O(1) but list search is O(n) (unless you know the data is sorted, in which case it is O(log n))
tribal pendant
after testing a bit, it's effectively much faster to do it with a dictionary, the testing code:
>>> import time
>>> a = {i: i for i in range(10**6)}
>>> b = [i for i in range(10**6)]
>>> timeit.timeit("980_000 in b", "from __main__ import a,b", number = 100)
2.9832702999999583
>>> timeit.timeit("980_000 in a", "from __main__ import a,b", number = 10000)
0.0016012419999924532
yeah, in list will do a linear search, comparing each element until it finds a match, which is O(n) for list size n. On average n/2 more precisely.
tribal pendant
I'll go with a dict then 😉
warm marsh
a dictionary is a hash table, so what happens when you look up an element is you compute its hash (some number) modulo the length of your internal dictionary data structure, to get the position of where the element is - or would be, if it were stored in the dict.
so that's O(1) with some constant but really small but overhead for the hash/index computation
tribal pendant
ok
is there any notable difference of speed between d[a] and d.get(a)? With d a dict, and a a key
I would prefer to use get, since I works even if the key is not in the dict
warm marsh
try, but should not be significant.
Complexity is the same, at most you have the overhead of a function call, I believe
nothing to worry about imo, that would be a premature optimization
tribal pendant
yep
fiery cosmos
Will this add a config file in /.aws and the data ?root@app:~/.aws# echo [default] region=eu-north-1 output=json > config
warm marsh
you should put the text in quotes, otherwise the shell might evaluate parts of it
in this case it should probably be fine, but as a general rule
it will create or replace the ~/.aws/config file though, not append to it.
to append instead of override, you'd use >> instead
fiery cosmos
When i do cat config it outputs [default] region=eu-north-1 output=json so i guess it worked? @warm marsh
warm marsh
if that's your desired outcome, sure.
fiery cosmos
I need to have a config file in a .aws folder on my server Configuration and Credential File Settings
For AWS to be able to work
So i think i just did that
And a credentials file
tribal pendant
I frequently hear that Python isn't quite bad when it comes to recursivity, do you know what makes it ineffective?
warm marsh
it has no tail call optimization, unlike some other languages that are more optimized for recursion
tail call optimization would "unroll" a recursive function that has the call to itself as very last instruction, and execute each recursion in the same stack frame, instead of making a proper function call
that is faster and avoids maximum recursion depth errors
tribal pendant
oh ok, that's why functional languages are generally better suited for recursion
eager hamlet
how should i implement this problem? no idea for even where to start
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.
In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.
You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.
(ping 4 reply thx)
fiery cosmos
if i have a simple "newbie" question, where shall i ask it?
spiral swallow
@eager hamlet hm, if you go through the list, everytime you see a decreasing order of two neighbourg elements, what does that mean?
@fiery cosmos questions are not organized by complexity level, if it's about computer science, then it's fine to ask it here, if you find a better suited topical channel, ask there instead, and if you are not sure, probably just ask in one of the help channels, making sure the one you chose is not being used at the moment (discussion going on in it).
fiery cosmos
okay, gimme a sec 🙂 @spiral swallow
1/3
2/3
3/3
@spiral swallow I was trying to follow a guide on Youtube since im new and want to learn, but it seems to me im doing nothing wrong but still it wont work for me =/
slim vault
Your init is called int
spiral swallow
oh, good call
i could have missed it for a long time.
__init__ not __int__
for info, it was more a python question than a CS question, CS is the field of study of algorithms and data types, mostly, rather than being about a language in particular, it's about the abstract ideas we use to make efficient programs.
fiery cosmos
jesus christ I have been trying to fix it for a while 😌
Thank you! @slim vault
Oh okay, where shall i ask Python related questions?
@spiral swallow
spiral swallow
sadly stupid errors like this are going to happen often, and you'll lose a lot of time on them, when things don't work and you don't understand why, check the things that you think absolutely can't be wrong.
any help-x channel really
also it's better, if you can to copy paste code, in a code block, rather than doing a screenshot of your IDE
type !code block in the bot commands channel for instructions for how to paste code
fiery cosmos
Okay! Got it!
spiral swallow
👍
fiery cosmos
So if I got it right, you have to wait for a room to be inactive before you ask? @spiral swallow
spiral swallow
there is a !free command you can also use in #bot-commands to get the least recently active channels.
if no discussion happened in more than 15mn, there is a good chance it's free.
fiery cosmos
damn nice 😄
Thank you for everything! Love your bun btw
spiral swallow
😄
tribal pendant
@vapid fiber I think you'll more chance to get an answer in #web-development 😉
vapid fiber
@tribal pendant Thanks
tribal pendant
np
balmy spoke
Is there any difference between a stack and a linked list with push() and pop() methods?
half lotus
A stack just means it needs to exhibit LIFO behaviour. A linked list just means each item stores a pointer to the next one. Stacks can be implemented using
Linked lists so in that case there is no difference
In a linked list a push could either add to the start or end, there's no restriction on which behaviour it should follow. It's just more efficient to add it to the front of the list since a pointer to the head is easily available.
And the pop could remove from either the front or the back. Inherently there is no definition on how a linked list should behave in these regards.
balmy spoke
What are "atomic" data structures that i should be aware of, that form more advanced structures? AFAIK there are arrays and various forms of linked list. Maybe a tree, but it can be interpreted as linked list with variable number of children. I thought hashtable was "atomic", but apparently it's a hash function + array.
I have no experience with low-level programming, so i still struggle to distinguish what represent concrete things and what are higher-level abstractions.
spiral swallow
@balmy spoke i like the computer science crash course on youtube, it does present things going from low level to high level, explicitely saying when the next thing is an abstraction on the previous thing, it's easily accessible too, it's not going into a lot of details about everything, but it's a good overview.
balmy spoke
Thanks, I'll check it out
Went throught MIT introductory course (the edx Python one), but unfortunately it wasn't enough
cursive drum
yep
fierce inlet
how does the top right show that not all nodes that will be walkable to will be orthogonal?
oh, the lights are nodes?
the white glowy square things?
i suppose you could maybe do a little pathfinding using the nodes to get from one landmark on the map to another
that would help make their movements seem a little less erratic
i.e. rather than just loitering the npcs are all going somewhere with a purpose e.g. from their house to a shop and back
depends on the algorithm
and you can use a lot of strategies to alleviate this as numbers go up
e.g. limiting the number of npcs moving at a time, or generating, caching then reusing paths from a pool
all paths visited? you mean as part of the pathfinding algorithm?
or the caching of final generated paths?
a cached final path shouldn't take very much space at all. let's say worst case scenario, a full map traversal of every node, so 300 items. you store each one as a reference to the node object in a list, that's 300 * 8 bytes + some list management overhead, maybe about 60ish bytes, cant remember exactly. so then you have roughly 2kb per worst case scenario path. and you generate let's say, 1000 such paths over time. so about 2mb. i wouldn't consider that much space.
(and this is just speaking in terms of how you might do it in python hypothetically)
it would also depend on how you store paths, what the language youre using affords you, etc
👍
past lava
hi i need some help with file input output
open kayak
ask away
open kayak
how long is it
desert cedar
!paste
halcyon plankBOT
open kayak
If it's not long you can do it in codeblock too
eager hamlet
@spiral swallow i was thinking more of getting all the 1's to the place first, then the 2's to the places after the ones, etc.
spiral swallow
but the problem asks you to figure the minimum about of swaps.
eager hamlet
yea @spiral swallow
but if i go through each neighbouring elements, then ill just end up swapping way more than necessary
copper siren
does big O have calculus applied in it? or can calculus be applied in big O
spiral swallow
big O is a way to describe the relation between growth of some quantity and the growth of another quantity
what happens to Y when X becomes one larger, does it increase by a fixed quantity? a ratio of itself? does it double? etc, big O draws an upper bound to the value of how things evolve.
stable pecan
big-O reminds me of hausdorff dimension
which is, you measure how fast the area of a ball in that space grows as you increase the radius of that ball --- well, it's the ratio of the log of the area growth to the log of the radius growth
so really all that matters is the exponents
just like big-O
acoustic fox
Having an issue with the time computation of a program I am working on
Basically you are given a list of test cases
x = [1,2,5,6,] of some size and arbitrary order
You are provided some y , -> y =10
you are given a range on x, lets say x[a:b] inclusive
You are supposed to report the max xor(test_case[i] , x ) for each i
x = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
y= 10
a = 4
b = 8
x[a,b] = 4,5,6,7,8
result = max([exor_add(x, y for x in x[a:b]])
Actual code
def xorKey(x, queries):
max_list = []
for queries in queries:
max_list.append(max([int(bin(query^queries[0]),2) for query in x[queries[1]-1: queries[2]]]))
return max_list
Got it down to one line of code at least
desert cedar
That's not a good thing.
acoustic fox
It's not
But as the origional problem was stated
but as the original problem is stated I am traversing through
n test cases
m tests per n
n*m where m can be bigger/smaller than n
So it's pretty bad complexity
It feels like there is some trick that I am missing with binary xors or something
runic tinsel
@acoustic fox what's the idea behind converting to binary and immediately converting back?
I don't think there's a trick
acoustic fox
UH
Hmm
Maybe converting back takes too much time
I don't know if max() allows for binary arguments
desert cedar
max takes anything that is comparable
spiral swallow
!ask
halcyon plankBOT
covert warren
Does anyone know of an updated YouTube series that covers the fundamentals of Python?
scenic mason
Yk dojo has good one
spare raven
Hey folks, I need some help solving this problem:
given a 2D array of size M x N, find all possible combinations of J size.
J might be <= M or M might be <= J
if J is > M, use -1 as the value at combination[j]
eager hamlet
all possible combinations of what? @spare raven
spare raven
each row
eager hamlet
wut
spare raven
[-1,-1,-1,1,6,11,]
[-1,-1,0,5,10,15,]
[-1,2,6,11,16,-1,]
[2,7,11,16,-1,-1,]
[5,10,14,19,-1,-1,]
[8,13,17,-1,-1,-1,]
[12,17,-1,-1,-1,-1,]
so, pull one value out of each row, and put it in combinations[]
eager hamlet
ah
so a combination would be one from row 1, one from row 2, one from row 3, etc. etc.?
spare raven
but combinations[] might have a size of like 2 or 10 or exactly the number of rows.
yes, exactly.
spare raven
Right.
eager hamlet
also does order matter?
spare raven
what do you mean?
eager hamlet
can we pull in this order: 3,2,1?
spare raven
as long as all combos of J size are created, it's fine.
eager hamlet
ok
i remember there was something involving zip() that did this
oh yea
do you know abt from itertools import permutations?
spare raven
no.
spare raven
permutations is the word I've been looking for for this.
eager hamlet
you can do this:
in all permuations of all the permutations of all the rows, you take the first element of each
wait no
just take the zip()
of each column
or smth like that
spare raven
is zip() part of that?
spare raven
yeah, that permutations thing doesn't iterate on elements of rows of 2D arrays
hmm, found this:
d = [[1, 1], [0, 0]]
from itertools import permutations, chain
from pprint import pprint
pprint(sorted([i[:2], i[2:]] for i in set(permutations(chain.from_iterable(d)))))
hmmm
it's not quite what I'm looking for.. https://repl.it/@matkatmusic/py i'm not sure how to pull only one element from each row to make the combinations.
tender wedge
At some point you do word[1] == character
Do you mean word[0]
I can't really read well your code cause it looks weird on phone
@fiery cosmos
balmy siren
Hey everyone ..
can someone tells me if my predicted result is correct ...
this is the algo.
for (k=1; k<= n; k++)
op
for (j =1; j<=n*n; j++)
op
op
op
end for
end for
so in this case, is the amount of work equals to -> n*3n**2 ??
gusty grove
i think its O(n**3)
balmy siren
@gusty grove you're using that left n with n**2, right?
gusty grove
yeah and you can leave the 3 out, because thats a constant
balmy siren
so it's O(n^3) right?
ohh yeah ..
thanks @gusty grove for replying
@gusty grove here the 'op' cost is 1(constant) right ?
gusty grove
yup
gusty bramble
Has anyone had an experience with Tesseract, and its accuracy?
(not sure if this is a CS question, but its the closest channel I can find)
gusty grove
find a slow way to combine some lists hahah
tribal pendant
Because None isn't a irrational number ^^
gusty grove
slow and mem intensive
tribal pendant
ah ok
gusty grove
oh, it was completely unrelated to that 🙂
tribal pendant
That's... eh, interesting
gusty grove
hahah
gusty grove
yeah i love that kind of stuff
thats one of the reasons i got into gpu programming
speed is key!
i hope the next code jam's qualifier will be something you can test for speed 😉
tribal pendant
Is python suited for that?
gusty grove
it ends up being the bottleneck but by that point you are already very fast
tribal pendant
I may be wrong, but I don't think code Jam will be about pure algorithms or math-related, because it only talk to a minor subset of programmers
gusty grove
for simple math its not worth it. but for stuff like partikle sims the gpu is blazingly fast compared to the cpu
a couple of cj ago, the qualifier was to write a password generator. i had a lot of fun getting the fastest time out of everyone 😉
tribal pendant
isn't gpu hardware related?
gusty grove
hm?
tribal pendant
I mean, gpu is a physical component
gusty grove
yeah
as long as you have a gpu from the last decade you should be fine. i've never actually used 100% of my gpu for my programs
every time the python function calling the gpu is the slowest part
tribal pendant
you never used 100% of your gpu?
gusty grove
not with my projects
no, thats not true
i have!
the game of life used 100% i think
tribal pendant
You made a bunch of cool stuffs
gusty grove
hell yeah:
(24800, 14400) sized world
thanks @tribal pendant ! one of the early versions of the text art project is actually pinned in #python-discussion 🙂
i should probs update the gif...
fiery cosmos
@gusty grove teach me how become like u sensei
solid cloud
@gusty grove there's a cool way to do voronoi which doesn't even need shader work
basically put a cone at the location of every element and the z-buffer will do the rest
came across it while trying to do hw accelerated voronoi on webgl
stable pecan
i just used scipy
solid cloud
stable pecan
still runs pretty fast without a shader though---it's all c extenstions
solid cloud
the hw accelerated methods are usually for interactivity at realtime speeds
stable pecan
that gif above is interactive in real time
clicking on the image makes the cells move
spiral swallow
did one in glsl some time ago, fine up to some number of points 😅
junior onyx
Conway's Life, nice
The game I'm making uses that as a mechanic, which I originally wrote in Python and then Cythonized
north zealot
The technique used in the voronoi testure is just awesome
It is so simple and provide some very good looking and very useful result
junior onyx
Yeah, I found all these interesting optimizations that you can make
like, if you precompute the per-cell neighbor offsets and store that in an array, you don't have to compute those on each cell
gusty grove
@solid cloud yup, but the problem is that you will get way worse looking results if you want the same performance
solid cloud
it was pretty much pixel perfect for us
gusty grove
Cones are like spheres, where you need a lot of vertices to make it look smooth
So I can easily get 16x multi sampling, but the same would require hundreds of vertices per cone
solid cloud
yeah true
gusty grove
It doesn't really matter if you are just using a few hundred cones though
solid cloud
we were doing about 10 million cones at hundreds of vertices with instancing, it held up at 60 fps along the rest of the application that was rendering 10 million data points
but yeah i'd go for your solution if it was possible on webgl
gusty grove
Yeah instancing is very cool
solid cloud
when i came across the cone method id kinda blew my mind. So simple when you see it but I don't think I'd ever think of doing it that way
hidden pebble
Yo so can anyone tell me what knowledge I need to get about cs to be better than everyone else on uni atm
I'm going to do uni after 2 years
tribal pendant
Be better in math
high stratus
that's not a straight forward answer sadly lol
it depends on what you're looking to get into. i don't think it's a good idea to look at it as "i want to be better than everyone else" as that makes you seem very rude. rather, look for what you need to learn to get to where you want to be
hidden pebble
Like what book should I read about the fundamentals of cs, fyi I'm a python coder
You can guess from my code at github "MahdeenSky"
slim tinsel
I see some discussion on cython here
high stratus
i don't have any direct books i know to suggest personally. what i can suggest is just getting very familiar with object oriented programming (or OOP for short) concepts.
these concepts are the core of every object oriented language, no matter what it is, and is the mold you will end up following in your day to day life wherever you end up
last blaze
@hidden pebble I'd reccomend the MIT OpenCourseware introduction to Computer Science
its linked in !resources
but it is a set of video lectures rather than content to read
spiral swallow
i guess if you want to be better than everyone else you are supposed to read "the art of computer programming" by Donald Knuth 🙂
but as you should expect, it's not an easy read
reading the EWD essays is also enlightening, it's been some time i didn't and i certainly should
gusty grove
huh. is exponential complexity common?
so O(e^x)
i can fit my timing data to a r^2 of .999998 with a exp. function
spiral swallow
well, people tend to look for better solutions, so it’s certainly avoided, but i’m sure it can't always be avoided.
balmy spoke
If only one book was enough to become better than anyone else 🙂
BTW, is there a curated list for math books and resourses? There are a LOT of resourses to learn about, say, graph theory but some are intended for math majors, some are intended for being youtube clickbait and some are just right, but explain material badly. Unfortunately, to know which is which you have to go through everything.
spiral swallow
the art of computer programming is not "one book" though, but yeah, i didn't read it, and i'm sure you'd still have plenty to learn after that, you'd have pretty solid fundations though
last blaze
Yeah, this isn't really the right channel #ot2-never-nester’s-nightmare might be a better place to ask. But in essence there are more tools available for linux
past flare
