algos-and-data-structs

[opal oriole]

I recommend studying the Wikipedia.

How are summations implemented in code?

[delicate ore]

really need some help

[opal oriole]

Also the comment given: "x r = 1/diagonalTerm r * (bt r - At r {r+1:end} * x {r+1 to end})" is the solution pretty much exactly.

It's basically pseudocode.

It's the Wikipedia equation.

But without any programming experience / Python experience this is rough. Going straight to numpy.

How would you compute just the sum in the equation (in Python)?

.latex $\sum_{i=1}^{m-1}{l_{m,i}x_i}$

[opal oriole]

How would you compute any sum in Python?

[little stag]

Sorry didn't see, what do you mean by compute any sum in python?

[opal oriole]

.latex Such as $\sum_{i=1}^{10}{i^2}$

[opal oriole]

How do you do it by hand?

[little stag]

I really have never seen this, I would say that means i = 1 and it is the sum of 1^2 to 10^2 including all numbers between 1 and 10

[opal oriole]

Oh, what class is having you solve these matrices without the math experience?

[little stag]

How would that be solved?

[opal oriole]

But yes, it means sum from i = 1 to 10 where each term is i^2.

[little stag]

And should I know how to do this in python?

[opal oriole]

For this problem you have been assigned, yes.

[opal oriole]

This sum is basically like this: 1 + 4 + 9 + 16 + 25 + ... + 100.

[opal oriole]

Computing the equation given by Wikipedia is the problem you were given and it contains a sum, so you need to know how compute them.

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]

a = At[(num_rows-unknowns),(num_cols-unknowns)] #Get last number from matrix At
b = bt[(num_rowsBT-unknowns)] #Get last number from matrix bt
x = b/a
print(x)

I have my matrix declared, then I need to get last number of my matrix to start back substitution, with this code I get my first value of X which is the last one in my vector solution.

Now to proceed with the wikipedia formula I should get my value from my matrix At which is 1 and multiply this by my X result, and then complete the equation ((b-(x * L23))/L22) right?

[opal oriole]

Correct, note that the Wikipedia one is forward substitution, so the indices are a bit different, same pattern though.

You are trying to do back substitution.

[little stag]

Yes I noticed that, wikipedia starts from 1,1 and I should start from last i, last j

[opal oriole]

So if x_1 = b/a then x_2 = ? given what you just wrote?

And your matrix and vector names instead of L.

@little stag

[little stag]

x_2 = (b-x_1)/a which translates into x_2 = (-5-1)/-3 = 2

Is that right?

[opal oriole]

What happened to the L23?

The multiplication.

[little stag]

Oh true

x_2 = (b-(x_1*At23))/a

[opal oriole]

What is L23 with your variable names?

Ok, but now with numpy indexing?

[little stag]

that would be getting my position 23 with numpy right?

[opal oriole]

At23 is the element in the second row, third column of At, how do you get that value in Python/numpy?

[little stag]

At[1:2,2:3] this should return 1 which is 23 postion

[opal oriole]

Yeah, but you don't really need ranges, we just need 1 value.

You can simplify it.

[little stag]

At[1,2] like this?

[opal oriole]

Yes.

So now plugging it back in, what do we have for x_1 and x_2 now?

[little stag]

x_1 = b/a and x_2 = (b-(x_1*At[1,2]))/a

[opal oriole]

So one last fix now.

Note that in the wikipedia equation, for x_1 it has b_1. But for x_2 is has b_2.

Which means we can't reuse the b variable.

The same for the a variable.

One is L11 and the other is L22.

Two different values on the diagonal.

So while b/a is correct for x_1, it's not for x_2.

We need different b and a values that are updated.

Or instead of having the temporary variables a and b (that we need to update), we can just do At[whatever] and bt[whatever].

Same as how L23 was done.

[little stag]

So creating a loop should make At[x,y] values that change each iteration and move between rows and cols depending on what value I want to calculate right?

[opal oriole]

Yes, but before we get to looping. Try changing x_1 and x_2 in the way I just described.

We are setting up for looping. @little stag

[delicate ore]

is there any way to fuzzy matching a tuple in a set of tuples?

e.g. {(1,2), (1,3), (2,3)}

I just want to check if there is (1,*)

is it doable?

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

a = At[2,2] 
b = bt[2] 

a2 = At[1,1] 
b2 = bt[1] 

x_1 = b/a
x_2 = (b2-x_1 * At[1,2])/a2

print(x_1)
print(x_2)

I have this

Now I need to making them variables that can change instead of fix variables right?

[opal oriole]

Try substituting At[2, 2] and such directly into x_1 and x_2, no need to make those temporary variables a, b, a2 and b2.

[little stag]

x_1 = bt[2] /At[2,2]
x_2 = (bt[1] -x_1 * At[1,2])/At[1,1]

Like this?

[opal oriole]

Yup.

Now before looping there is one last thing, otherwise you will probably not get it right.

Can you compute x_3?

[little stag]

Just what I am trying give me a sec to do it

[opal oriole]

Wikipedia tells you how to compute the m-th x.

(x_m)

(So in this case m = 3)

Notice the sum in the equation goes from i = 1 to m - 1, which means there will be how many terms / multiplications?

[little stag]

x_3 = (bt[0] - x_1 * At[0,2] - x_2 * At[0,1])/At[0,0]
```Is it like this?

[opal oriole]

Yes.

Now that sum might look really familiar at this point...

https://en.wikipedia.org/wiki/Dot_product#Algebraic_definition

(sum of two things multiplied together)

(not sure how much linear algebra you know)

[little stag]

I am not sure where this is going?

[opal oriole]

It was only going somewhere with the appropriate linear algebra knowledge, lets just move on.

So now we want to loop.

[little stag]

Oh ok,

[opal oriole]

To compute x_1, x_2, ..., x_m.

[little stag]

Should I use a for or while loop?

[opal oriole]

Does not matter.

[little stag]

okey

[opal oriole]

But the Pythonic thing is go for a for loop.

while is kind of rare.

But both will get the job done.

[little stag]

I'd rather use a for loop as it is the one I don't understand so I get to know how it works

[opal oriole]

For lets you loop over something.

So for example, a list, or a range (of numbers).

Over some object.

[little stag]

so if i use for x in array, the loop while return everything in that array?

[opal oriole]

It does not "return" everything in the array, but yes.

(Return means a specific thing in programming (returning from a function))

It gives you each element in the array.

Loops over each element in the array.

[little stag]

So I should loop over in my matrix array in X range?

[opal oriole]

Looping over a range. Do you know what the range is?

[little stag]

Wouldn't the range be the amount of rows my input matrix has?

[opal oriole]

Yup, or as Wikipedia put it, 1 to m.

[little stag]

so for i in range(num_cols)

[opal oriole]

num_cols is not the number of rows I assume.

(It could be)

[little stag]

oh yes mb I meant rows

[opal oriole]

So you know how to compute x_1 to x_3, but note that each is slightly different because they have different number of terms in the sum.

The sum itself has a range.

The thing is, looping solutions need to have the exact same line(s) in each iteration of the loop.

So you need compute x_1 to x_m in the same way each time.

Which means accounting for different number of multiplications / summation terms in each.

[little stag]

What do you mean by this?

[opal oriole]

i = 1 to m - 1.

i has a range.

And if something has a range (like x_m) then what do we use to compute it?

[little stag]

The range from the equation you asked me before if I knew how to do the sum?

[opal oriole]

The Wikipedia equation, the x_m one.

[little stag]

Yes I see

[opal oriole]

.

[little stag]

that would be the for loop range, and range should be between m and i values right?

[opal oriole]

You have a loop right now for computing x_m, but each x_m has a sum that needs to be computed and that sum has a range for i.

[little stag]

I don't think I get this

[opal oriole]

Try creating the loop for computing x_m (the m-th x) and see what you get for now.

[little stag]

okey

[opal oriole]

You should run into the issue while trying to do so.

[little stag]

I can't do it, I tried creating a counter so my At[x,y] are variables instead of fixed positions but it doesnt work

[opal oriole]

What do you have so far?

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
counter = num_rows

for i in range(num_rows):
   x_1 = bt[counter-1] / At[counter-1,counter-1]
   x_m = bt[counter-2] -x_1 * At[counter-2, num_rows-1]/At[counter-2,counter-2]
   print(x_m)

[opal oriole]

This will compute x_1 multiple times.

Note that when we computed x_1 to x_3, that the x_m values depend on previous x_m values.

Take the x_1 to x_3 we did and write them out here.

What do we have so far for x_1, x_2, x_3?

[little stag]

  x_1 = bt[2] / At[2,2]
  x_2 = (bt[1] -x_1 * At[1,2]) / At[1,1]
  x_3 = (bt[0] - x_1 * At[0,2] - x_2 * At[0,1])/At[0,0]

This is x_1, x_2, x_3

[opal oriole]

Note how x_1 does not depend on any x values. x_2 depends on the previous x value, x_1, and x_3 depends on both x_1 and x_2.

[little stag]

bt and division At will always be the same but reducing their position by 1 right¿

[opal oriole]

That is the pattern.

[little stag]

I see

[opal oriole]

So what x values will x_4 depend on?

Without writing it out now.

Can we predict the pattern?

[little stag]

Do I need to keep x_1 for my loop?

[little stag]

Yes, as it would be the same as x_3 with now depending on x_3 values right?

[opal oriole]

If a calculation depends on a previous value, we need to keep it around for when we get to that calculation.

[opal oriole]

Which x_m values does it need?

x_3 needed x_1 and x_2.

x_2 needed x_1.

[little stag]

I need all the previous values

[opal oriole]

x_1 needed nothing.

Correct.

And if you look at the wikipedia equation for x_m you can see why.

The sum goes from i = 1 to m - 1.

So if m = 3, then i is 1 and 2.

And if m = 4...

[little stag]

I will be 1 2 3

[opal oriole]

If you look at the pattern of how you solve this problem by hand you can see that you do exactly this.

So what object is used in Python to keep around some arbitrary number of things and that number of things grows as you keep going?

[little stag]

Would that be a counter? That increases or reduces value in each for loop iteration

[opal oriole]

The counter keeps track of which x_m you are currently doing / on, but you also need to keep track of your previous x_m's.

Because each current x_m depends on the previous ones.

[little stag]

How do I keep track of the previous ones?

[opal oriole]

You need to store them somehow. To be used when needed.

You need to store multiple objects.

How do we store multiple objects / things in Python?

[little stag]

in an array

[opal oriole]

Correct.

[little stag]

results.append(x) like this?

[opal oriole]

That works.

New results now depend on previous results.

x_3 depends on x_1 and x_2, etc.

It's like Fibonacci numbers, except those only depend on the previous two, while this depends on all the previous.

[little stag]

I see how this works, but I can't find the connection between my stored results and my x_m in python

[opal oriole]

Try rewriting these x_1 to x_3 but with m instead of the number: x_3 = (bt[0] - x_1 * At[0,2] - x_2 * At[0,1])/At[0,0]

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []
counter = num_rows

for i in range(num_rows):
  x_m = (bt[counter-1])/At[counter -1, counter-1]

  results.append(x_m)
  counter = counter-1
  print(x_m)

If there is nothing wrong all I am missing is using x_m stored values to calculate next x_m values

[opal oriole]

(You basically end up with the wikipedia equation)

[opal oriole]

The minus sum vanished from your x_m equation.

[little stag]

is this what you meant by rewriting x_1 to x_3 with m?

[opal oriole]

Yes.

When you have computed specific cases (1 to 3) in mathematics, it's time to try to see if you can do all of them in the same generic way.

That generic way can be written into code.

[little stag]

Okey I see

[opal oriole]

That generic way is what Wikipedia is trying to say with its x_m.

It's showing some examples, then detects the pattern and makes it generic.

[little stag]

What I don't get now is how do I access my stored values in result array, to b more specific how to use those values in my minus

[opal oriole]

How do you access any value in an array?

[halcyon plank]

:ok_hand: applied mute to @fiery cosmos until <t:1666439113:f> (10 minutes) (reason: duplicates rule: sent 4 duplicated messages in 10s).

The <@&831776746206265384> have been alerted for review.

[opal oriole]

Are the matrices and vectors not arrays too?

[little stag]

yes

[opal oriole]

How did you access values for them?

[little stag]

At[1,2] so now it would be results[x]?

[opal oriole]

Except results is 1 dimensional.

[little stag]

And I can do bt[counter-1] - results[x]?

[opal oriole]

results[x] gives you one value.

But the sum expands into multiple values.

[little stag]

so i range between first and last value?

[opal oriole]

All previous x_m are involved.

Yup.

But it's not just minus the previous values, remember there is some multiplications going on too.

[wraith valley]

Hi, I want to create a dynamic array of abstract data types how can I do that?

[opal oriole]

And some summation happening.

[opal oriole]

A list.

[little stag]

Yep, I need to understand how to get the number of results in array range first

[opal oriole]

Well, you actually need ALL of the previous results, so...

[little stag]

Because If I do resutls[0:3] it will return 3 values, but how do I 0:end?

Is there a way or should I just use a big number¿

[opal oriole]

:

(default values)

[little stag]

Oh so just : takes all values

ok I got it

[opal oriole]

But is : not just the same as ALL of them?

[wraith valley]

yes I know I will create it with a list but len
getitem
settem
appendix
insert: I need to use these methods and I need to have n=0 and capacity=1 variables

[little stag]

Yep ty

[opal oriole]

Python lists keep track of the length and capacity internally. You can just append to them.

(They are dynamic arrays)

[little stag]

Do I need to calculate x_1 before the loop or will it work to calculate just x_m in the loop?

[opal oriole]

If the loop calculates all x_m, then surely it calculates x_1 as it is one of the x_m's.

[wraith valley]

class DynamicArray:
def init(self):

Remarks: you must have variables inside the constructor method, with n=0 and capacity=1 (their default values) first. When n==capacity you should always update to capacity *= 2.
Methods:
len
getitem
settem
appendix
insert: this is my task but I don't understand how to do it

[opal oriole]

If x_1 were somehow special / different, then you would need to do it separate, but all x_m are done in the same way.

[little stag]

As it would take x_m as 0 in the first iteration of the loop right?

[opal oriole]

Yeah, in math they start at 1, in programming we (usually) start at 0.

Same thing though.

[little stag]

x_m = (bt[counter-1]) - (results[:]) /At[counter -1, counter-1]

This is what I have, now what I am missing is the multiplication of At for resutls right?

[opal oriole]

x_m in the first iteration is just the b / a.

It does not depend on any previous values.

Or in other words its sum part is zero, so it's (b - 0) / a.

[opal oriole]

Look at the wikipedia equation again.

There is a summation happening, and each term has a multiplication happening.

(remember that results contains the previous x_m's)

[wraith valley]

class DynamicArray:
def init(self):

Remarks: you must have variables inside the constructor method, with n=0 and capacity=1 (their default values) first. When n==capacity you should always update to capacity *= 2.
Methods:
len
getitem
settem
appendix
insert: this is my task but I don't understand how to do it

[little stag]

the sumation is lmi Xi which are both multiplied right?

[opal oriole]

How would you write x_3 using results?

[little stag]

Taking last value of results [0] and multiplying it by At[0,2]

[opal oriole]

Can you write it out here?

[little stag]

x_3 = (bt[0] - (results[0] * At[0,2] + results[1] * At[0,1]))/At[0,0]

[opal oriole]

And how about x_1 and x_2?

[little stag]

isn't x_1 result = results[0]? Then I need to multiply that by At[] right?

[opal oriole]

The mth x depends on all previous results.

[little stag]

isn't results[] doing this : results[x_1, x_2, x_3]?

[opal oriole]

So the first depends on how many results?

[little stag]

With first do you mean x_1?

[opal oriole]

Yes.

[little stag]

X_1 does not depend on any result

[opal oriole]

Correct.

[little stag]

Because there is no previous result

[opal oriole]

So x_1 = ? and x_2 = ?

[little stag]

But X_2 depends on x_1 which should be results[0] as x_1 result is stored there right?

[opal oriole]

Yes.

results are the x's.

They are what we are solving for.

[little stag]

so by multiplying results[0] * At[0,2] would be the same as x_1 * At[0,2]

?

[opal oriole]

results[0] = x_1

Yes.

[little stag]

-(results[x] * At[x,y]) would be what I am looking for

[opal oriole]

.

So not exactly.

Almost.

x_i is the ith x.

m is the mth row.

[little stag]

So the Sum of results[i] * At[m,i] would be the answer?

[opal oriole]

Yes.

Question is, how do you do that sum?

[opal oriole]

When you wrote out x_3 you could do it just like that.

You know how many things are inside the - () because you know m = 3.

But if you are doing it generically, m is something.

So you don't know how many terms to write out.

[little stag]

Wouldn't m equal num_rows-1?

[opal oriole]

No, m is the current row.

Current iteration in your loop.

As your loop progresses, the number of terms in the sum increases (more previous values).

So you can't just write it out as some fixed number of terms.

Like with x_3.

Or x_2.

[little stag]

I need to find how to do the sum of the previous values

which is results[i] * At[m,i] where m is the current iteration

[opal oriole]

It's the sum where each term is that.

See the Wikipedia equation again.

Sum of those multiplications.

m is the current iteration / current x being processed, yes.

The for loop gives us the current thing.

That is what the blah in range gives.

[little stag]

But I need to multiply lets say results[0] * At[0.2] and then sum this value to results[1] * At[0.1]

[opal oriole]

Yes.

A sum is an accumulation. You build up a value.

How can we build up a value?

Bit by bit.

What are we using to build up results bit by bit?

[little stag]

I don't get what you mean by this

[opal oriole]

You have two parts here.

Imagine we start at 0.

We can add the first, then the second.

Building up the value.

To the final total.

[little stag]

Like we did with resutls.append(x_m)? We build an array with each value

[opal oriole]

Yeah, but we only did an array because need to keep around all the previous values.

When adding things together, do we need to keep all the stuff around?

[little stag]

Now we just need to store one value

[opal oriole]

Yes.

[little stag]

Which is the sum of each multiplication

[opal oriole]

Yes.

And it works for any number of terms.

[little stag]

So I need to create a new variable like this a += results[i] * At[m,i]

[opal oriole]

Yes.

A key idea is that iteration is about building things up, bit by bit.

Whether it's an array, number, or whatever.

(Or multiple things / a combination of them at the same time)

(And the building often depends on the previous results (1 or more))

[wraith valley]

hello I really need help can you help me?

[little stag]

a += results[0] * At[0,0]

This returns list index out of range, am I missing something¿

[little stag]

Okey I get it

[opal oriole]

Is there a results[0] if you are doing the first x?

[little stag]

Nope, I declared results[] with no value that was the issue ty

[opal oriole]

Remember that when computing the first x, since it depends on nothing, its sum part of the equation is zero.

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = [0]
counter = num_rows


for i in range(num_rows):
  a += results[0] * At[0, 2]
  print(a)
  x_m = ((bt[counter-1]) - a) / At[counter -1, counter-1]

  results.append(x_m)
  counter = counter-1

I can't seem to find what I am doing wrong, my print(a) returns -20326.852483258834
-20326.852483258834
-20326.852483258834

[opal oriole]

a += results[0] * At[0, 2], this is doing the same sum for all of the x_m, but each x_m has a unique sum.

[little stag]

Yes, before I had variables this was just to test what is wrong

[opal oriole]

In a separate file. Try computing:

[little stag]

In this case where results[0] and At[0,2] a should be equal to 1 * 2 ?

[opal oriole]

.latex $\sum_{i=1}^{10}{i^2}$

[little stag]

Im working on it

i = 1

for x in range(10):
  i += i*i
  print(i)
``` Like this?

[opal oriole]

Almost, we don't want to add to i though.

Oh nvm.

Yeah that is right, it's just that usually i and x are swapped.

So x would be the accumulator, and i the current iteration.

Oh wait, nvm again.

It's x * x in your code, not i * i.

[little stag]

Oh okey, now the output makes more sense

[opal oriole]

Also, your x starts at 0, but that sum I gave starts at 1.

[little stag]

So what the code is doing is taking x from 1 to 10 and iterating this values? as x = 0, x = 1, x = 2...

[opal oriole]

However, it turns out it does not matter because i * i is 0 when i is 0, so nothing is added extra.

It actually goes from 0 to 9.

The way range works is inclusive, exclusive.

[little stag]

Oh true python indexing

[opal oriole]

range can have a start value

range(1, 11) would be 1 to 10.

[little stag]

so my for i in range(num_rows): goes from i= 0 to i = num_rows-1

[opal oriole]

Yes.

Can you compute this sum though?

.latex $\sum_{i=1}^{N}{i^2}$

[opal oriole]

Where N is given as input by the user.

[little stag]

N = int(input())
x = 0

for i in range(N+1):
  x += i*i
  print(x)

[opal oriole]

Can you swap i and x names?

Typically, it's for i in ...

[little stag]

Done

[opal oriole]

Also note that you need N+1, because otherwise it goes up to only N-1, and also it needs to start at 1.

Math summations are inclusive on both ends.

So it's i = 1 to N inclusive both.

[little stag]

So now it goes until user input

[opal oriole]

Ok, so now.

[opal oriole]

What would this look like?

[little stag]

for i in range(m)
  total += l[m,i] * x[i]

[opal oriole]

Yup , but you are using x twice in two different ways, name conflict.

Those are different variables.

[little stag]

True

Does a new variable work?

[opal oriole]

Here I would use s or total instead of x.

(s for sum)

[opal oriole]

Now, how does this fit into your original problem?

Also note that total needs to start at some value (0).

[little stag]

If I understood correctly I would need a loop inside my loop that returns the sum of all previous values, as just he main loop it will just return one value right?

[opal oriole]

Loop inside loop is how it will look yeah.

When you see a sum in math, think loop.

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = [0]
counter = num_rows
total = 0


for i in range(num_rows):
  for j in range(num_rows):
    total += results[i] * At[counter-1, i]
    
  x_m = ((bt[counter-1])-total) / At[counter -1, counter-1]
  
  results.append(x_m)
  counter = counter-1
```Like this?

[opal oriole]

total keeps increasing across different x_m because it's on the way outside.

[little stag]

What do you mean?

[opal oriole]

We want to compute a sum for each x_m, previous sum value should not carry over to the next x_m.

[little stag]

should I reset the value total to 0 at the end of the iteration?

So the values are not carried through the new iteration

[opal oriole]

When did you set the accumulator to zero in these?

[little stag]

I didn't have to

That means I don't have to do it now either right

?

[opal oriole]

You set x to zero in that one.

The accumulator needs to start at 0.

[little stag]

before the loop

[opal oriole]

Yes.

[little stag]

I have my total at 0 before the for i in range(num_rows)

is that what you mean?

[opal oriole]

Yes.

The total is only used for that x_m.

It must not carry over.

And we need to set it to 0 to start the summation.

Because sums start at nothing.

[little stag]

I don't see what you mean

[opal oriole]

If I do 1 + 2 + 3 + 4.

When you add those up, what value do you start with?

[azure osprey]

Are there any general tips on how to detect and find recursion errors?

[little stag]

Before starting my loop I have my total at 0, but I should have my total at 0 when the loop starts over again right?

[little stag]

10

[opal oriole]

A debugger and view the stack trace.

[little stag]

So I need my sum at 0 before doing it again to end up with the same value right?

[azure osprey]

Well I don't get an error, but I think its infinite recursion

[opal oriole]

That is the end result. What do you start on?

[little stag]

0

[opal oriole]

Yeah.

[opal oriole]

Set a break point that triggers when being hit N number of times (depth N). Then view the stack trace and local variables. Try to find out from that.

[little stag]

for j in range(num_rows):
    total = 0
    total += results[i] * At[counter-1, i]

Is this what you mean?

[opal oriole]

That would give the wrong result.

[azure osprey]

By using pdb?

[opal oriole]

Total would be equal to the final term.

[opal oriole]

Yes, or some graphical debugger.

[azure osprey]

Vscode has no such feature

[opal oriole]

Any debugger will do, but your mileage will vary depending on its quality.

[opal oriole]

Need a better debugger then.

[little stag]

I don't get it

[opal oriole]

VSCode has a primitive debugging experience.

[opal oriole]

In that loop, total is always zero, then added the current term.

[azure osprey]

I still don't understand how infinite recursion is cause at all, I am passing the object in question by reference

[opal oriole]

The last thing the loop is on is the last term.

So total is equal to the last term.

[wraith valley]

@opal oriole Can you help me?

[little stag]

for i in range(num_rows):
  total = 0
  for j in range(num_rows):
    total += results[i] * At[counter-1, i]

Now when the first loop starts total is set to 0 but it does not affect the second loop right?

[opal oriole]

Yes.

The total value is set to zero each time in the outer loop.

So it does not carry over.

(total is reset each time, which is what we want, a fresh new sum for computing x_m)

[little stag]

So now this should work fine right? Or am I missing something?

[opal oriole]

The inner loop, is the sum from 1 to m - 1.

m is the current index of the outer loop remember?

So your i is m.

Well, it's the m for the forward subtitution.

counter is m.

counter is backwards i.

Reverse direction.

[little stag]

what do you mean? I kinda got lost with so many i and m

[opal oriole]

So you start at the end of the matrix and go up in the outer loop.

You did this by creating the variable counter.

[little stag]

Yes

[opal oriole]

Which counts down.

Your variable i counts up.

They move in opposite directions from opposite ends.

The inner loop uses j, and needs to do that sum in the wikipedia equation which goes from 1 to m - 1.

[little stag]

so in my code m = counter and i = j?

[opal oriole]

Uh no, i'm getting confused too now.

Because counter is a redundant variable.

[little stag]

what would be the correct approach?

[opal oriole]

What I can say is that the inner loop does not go to num_rows.

Because imagine it's doing the first x.

Then it depends on nothing, so the sum is 0.

But the sum is doing a loop up to num_rows.

So that can't be right.

It needs to loop over the previous values.

(Which changes (how many of them))

[little stag]

so for j in range(num_rows-1) is wrong¿

[opal oriole]

Yes.

The number of results is not num_rows, nor num_rows - 1.

num_rows never changes.

[little stag]

the number of results depends on x_m being m the value that I need right?

[opal oriole]

Yes.

Which is i.

When it does the first one, i is zero.

(no results)

When it does the second, i is 1.

(1 result so far)

etc

[opal oriole]

range(i)

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = [0]
counter = num_rows



for i in range(num_rows):
  total = 0
  for j in range(i):
    total += results[1] * At[1, 2]
    
  x_m = ((bt[counter-1])-total) / At[counter -1, counter-1]
  print(x_m)
  results.append(x_m)

  counter = counter-1

Yes I got range(i), now I am getting confused with "total += results[1] * At[1, 2]" what should my values be here?

[opal oriole]

Look at the Wikipedia equation's sum again.

You should know how to convert the sum into code now.

Also results should start empty, there are no results in the beginning.

[little stag]

results[]?

[opal oriole]

No above, at the start.

[little stag]

Its just that I got to confused now, besides those values evrything else should be ok?

[little stag]

What line do you mean?

[opal oriole]

results = [0]

[little stag]

that should be results = []

I mistyped in the first answer I meant results = [] not results[]

[opal oriole]

.

You variable names differ, but same thing.

I need to modify that sum for back substitution since that is for forward.

[grand haven]

Failed to render input.

View Logs

[opal oriole]

.latex $\sum_{i=1}^{m-1}{l_{rows-m,i}x_i}$

[opal oriole]

rows - m, you have that

(counter)

[little stag]

my row_number - counter

[opal oriole]

rows is number of rows.

m is i.

i in this sum is j

[little stag]

At[num_rows, j] this is what you mean right?

[opal oriole]

Half right.

[little stag]

At[num_rows - j, i]

[opal oriole]

Colder.

[little stag]

so rows = rows_number, m = i

At[num_rows - i, j] and results[j]

Is that correct?

[opal oriole]

Yes.

But slight correction.

Need a - 1.

Because when i = 0, you get num_rows.

Which is out of bounds.

Also counter = num_rows - i.

[little stag]

Where do I need a -1?

[little stag]

Yes

[opal oriole]

You did counter - 1.

Why?

[little stag]

To move between rows as I start with 3 and move to 2 1 0

[opal oriole]

counter is num_rows - i.

[opal oriole]

.

If you replace num_rows - i with counter, what error do you get?

That you avoided before.

With - 1.

[little stag]

Out of bounds error

as index 3 is too big

[opal oriole]

So what is the code now?

[little stag]

so I can change all counters with num_rows-i¿

[opal oriole]

Yes.

They are the same thing.

counter is redundant.

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []



for i in range(num_rows):
  total = 0
  for j in range(i):
    total += results[j] * At[num_rows-i, j]

    
  x_m = ((bt[num_rows-i])-total) / At[num_rows-i, num_rows-i]
 
  results.append(x_m)
  print(x_m)

Without counter I am getting this error: x_m = ((bt[num_rows-i])-total) / At[num_rows-i, num_rows-i] out of bounds, but I can add a -1 as I had before, is that correct?

[bronze ibex]

hey guys

[opal oriole]

Yes, see what happens when i = 0.

[bronze ibex]

i need A Python programmer, to code an ai

i got some investors for my project

[opal oriole]

!rule 9

[halcyon plank]

Rules

9. Do not offer or ask for paid work of any kind.

[little stag]

I get the out of bounds error right?

[opal oriole]

Yes.

[bronze ibex]

im just offering a place to work, not paid yet

[opal oriole]

Free labor?

[little stag]

How do I run code here? Like you did before?

[bronze ibex]

kind of equity on a project

[opal oriole]

exclamation mark e.

[little stag]

!e

import numpy as np
At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []



for i in range(num_rows):
  total = 0
  for j in range(i):
    total += results[j] * At[num_rows-i, j]

    
  x_m = ((bt[num_rows-i-1])-total) / At[num_rows-i-1, num_rows-i-1]
 
  results.append(x_m)
  print(x_m)

[halcyon plank]

@little stag :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 1.0
002 | 1.6666666666666667
003 | 2.0

[little stag]

The first value is correct, but the other 2 are not did I miss something?

[opal oriole]

At[num_rows-i, j]

[little stag]

Where?

[opal oriole]

In the sum.

[little stag]

total += results[j] * At[num_rows-i, j] here?

[opal oriole]

Yes.

[little stag]

But that is what I already have?

[opal oriole]

Yeah it's not right.

[little stag]

Oh okey

[opal oriole]

Look at your other At.

[little stag]

The one below that divides?

[opal oriole]

Yeah.

What change did you just make to it.

What error did you avoid?

[little stag]

I added the minus 1

to avoid out of bounds

[opal oriole]

What did you do to the At in the sum?

What does it do that you decided was an error.

[little stag]

The same as the At below without adding the -1

[little stag]

What do you mean?

[opal oriole]

When i = 0.

What is num_rows - i?

[little stag]

it is the m in the last equation you sent

which the sum is m-1

[opal oriole]

At[num_rows - i - 1, j].

At[num_rows - i, j] is an error when i = 0 and when i > 0, it's off by 1.

[little stag]

So I need to add the -1 to num_rows - i?

[opal oriole]

Yes.

[little stag]

At = np.array([[5, 4, 2], [0, -3, 1], [0, 0, 45]]) #Code input
bt = np.array([5,-5,45])

num_rows, num_cols = At.shape
num_rowsBT = np.shape(bt)[0]
results = []



for i in range(num_rows):
  total = 0
  for j in range(i):
    total += results[j] * At[num_rows-i-1, j]

    
  x_m = ((bt[num_rows-i-1])-total) / At[num_rows-i-1, num_rows-i-1]
 
  results.append(x_m)

  print(x_m)

Like this?

[opal oriole]

There is still 1 problem with At[num_rows-i-1, j].

Because we are doing back substitution, we need to start at the last column.

And go the other way.

[little stag]

At[rows, columns] that is the correct order right?

[opal oriole]

.latex $\sum_{i=1}^{m-1}{l_{rows-m,cols-i}x_i}$

[opal oriole]

Yes.

[little stag]

total += results[j] * At[num_rows-i-1, num_cols - j - 1]

[opal oriole]

Yes.

[little stag]

Okey now I have completed my function, thank you for everything @opal oriole I learned a lot from you today ^^

[opal oriole]

One last thing.

Doing the num_rows-i-1 everywhere is ugly.

It would be great if we could instead just have the outer loop go in reverse order.

Then we don't need the num_rows - i - 1, just i.

And Python has reversed for that.

reversed(some range).

range(i) needs to change though (num_rows - i)

[little stag]

Wouldn't creating a variable for a = num_rows-i-1 work?

[opal oriole]

That works too.

[little stag]

Like a visual solution

[fiery cosmos]

i'll be working on my script all day today if anyone is around / bored / wants to help / curious

how do i read this:

return lambda k, i, m: (h(k) + i) % m

[haughty mountain]

def something(k, i, m):
  return (h(k) + i) % m
return something

[fiery cosmos]

seems like it should work as is, according to my understanding

[haughty mountain]

if you're going to give the lambda a name just use a function

[fiery cosmos]

love to get your thoughts on how the author and one coder solved this:

https://pastebin.com/TV4svw3E

the openslot function will need a modification for when there are buckets of size 3

keep getting int object is not subscriptable

why would this throw 'int' object is not subscriptable::
if self.table[loc].keys[0] is None:

just seems like my approach overcomplicates things

although i do like the objects as buckets within the table idea

[haughty mountain]

I think people typically usually refer to these as tombstones

class Deleted:

elements that are deleted from the hashtable, but you should search further because there might still be elements ahead

e.g. if I insert A, B and C that all collide they form a sequence A -> B -> C in the probing

if I delete B I can't just set B to be empty

because I still need to be able to look up C

and normally seeing something empty means (no more collisions here)

these things are actually nice, though I would not write them as lambdas

def linear_probing_hash_function(h):
  """Return a function that performs linear probing.
    Parameter:
    h -- a primary hash function

    Returns:
    A function with parameters:
        h -- primary hash function
        k -- key to be hashed
        i -- iteration number
        m -- size of hash table
    """
  return lambda k, i, m: (h(k) + i) % m

[haughty mountain]

just do this instead of returning a lambda

[fiery cosmos]

yeah so i wrote that as:

but it'll need a mod for when keys can range 0-2

which should be simple enough

but im still getting Exception has occurred: TypeError 'int' object is not subscriptable

on 3 different lines if im understanding the IDE properly

yeah i liked their implementation, seemed very concise

[haughty mountain]

smells like self.table[loc].keys is an int

[fiery cosmos]

that's weird, let me try a print statement

[haughty mountain]

yes, that should kinda be the first thing to try

what version of python are you running?

I think later versions should give you pretty good indication what is actually None

this is more or less the CLRS repeat loop

    i = 0
    # Continue probing until finding an element with key k, finding an empty slot,
    # or have searched all m slots.
    while True:
      q = self.hash_func(k, i, self.m)
      if self.table[q] is None:  # empty slot
        return None  # not found
      elif self.get_key(self.table[q]) == k:
        return q  # found the object in slot q
      else:
        i += 1
        if i == self.m:  # searched entire table?
          return None  # not found

though they have an extra check they don't need, this is not as clean as it could be

    # Empty hash table.
    if self.m == 0:
      return None
    i = 0
    # Continue probing until finding an element with key k, finding an empty slot,
    # or have searched all m slots.
    while True:
      q = self.hash_func(k, i, self.m)
      if self.table[q] is None:  # empty slot
        return None  # not found
      elif self.get_key(self.table[q]) == k:
        return q  # found the object in slot q
      else:
        i += 1
        if i == self.m:  # searched entire table?
          return None  # not found

the first if statement could be part of the loop, and everything would end up cleaner

[fiery cosmos]

3.10

[haughty mountain]

here is a nicer version

    i = 0
    # Continue probing until finding an element with key k, finding an empty slot,
    # or have searched all m slots.
    while i != self.m:
      q = self.hash_func(k, i, self.m)
      if self.table[q] is None:  # empty slot
        return None  # not found
      elif self.get_key(self.table[q]) == k:
        return q  # found the object in slot q
      i += 1

[fiery cosmos]

so this: print(mytable.table[0].keys)
prints: [None]

though thats not in the proper context

yeah need to check loc

[haughty mountain]

so what is the actual error you get?

[fiery cosmos]

Exception has occurred: TypeError 'int' object is not subscriptable

[haughty mountain]

that's not all

[fiery cosmos]

on 3 diff lines

[haughty mountain]

if you run the program you should have more info

[fiery cosmos]

Exception has occurred: TypeError 'int' object is not subscriptable File "path", line 31, in openslot if self.table[loc].keys[0] is None: File "path", line 44, in insert if self.openslot(j): File "path", line 82, in <module> mytable.insert(datum)
modified path to not contain my name

how might i run a print statement like within the class so that it has access to all the variables? its not helpful to run it outside where it doesn't have scope to loc

[haughty mountain]

I swear there were changes to actually point out the part with the error

maybe I'm misremembering

[fiery cosmos]

let me screenshot

[haughty mountain]

why don't you print next to where the error is thrown?

above line 31 82

[fiery cosmos]

check the call stack too

[haughty mountain]

I keep forgetting python is one of the languages where the stack traces are reversed

but yeah, the error happens at line 31

print there

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @fiery cosmos until <t:1666460186:f> (10 minutes) (reason: newlines rule: sent 122 newlines in 10s).

The <@&831776746206265384> have been alerted for review.

[haughty mountain]

lol

moderators should fix things soon enough 😛

hey @main bison feel like pardoning @fiery cosmos?

[north belfry]

No need to ping specific folks. We get notified.

!unmute 243149174487384066

[halcyon plank]

:incoming_envelope: :ok_hand: pardoned infraction mute for @fiery cosmos.

[haughty mountain]

yeah, gotcha

thanks

[fiery cosmos]

thank you

[north belfry]

!paste If you need to share something large.

[halcyon plank]

Pasting large amounts of code

If your code is too long to fit in a codeblock in Discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

[fiery cosmos]

soo basically it printed None, \n, [None], \n, ... tablesize, then an int

[haughty mountain]

so you're assigning an int to keys somewhere

[fiery cosmos]

only at the end

here is my insert function:

[haughty mountain]

I feel like their linear probing version has a bug

[fiery cosmos]

it could, i haven't tried running it

[haughty mountain]

exactly the case where you delete an element in a probing chain

they seem to just put None there

[fiery cosmos]

they have more versions than that

1 sec

that was their 'open address' hashtable, they also have a chained one, where im sure they have accounted for that

[haughty mountain]

yes, I'm saying I think their open address one has a bug

[fiery cosmos]

oh

[haughty mountain]

do you have the definition of KeyObject?

[fiery cosmos]

let me check their functions

[haughty mountain]

it's in some separate file

[fiery cosmos]

on it

its not in their hash functions file

[haughty mountain]

key_object.py I'm guessing

based on the import

[fiery cosmos]

found it. it's in utility functions

which is not in any chapter but its own directory at the end:

class KeyObject:
    """Used for testing anything that requires a key."""

    def __init__(self, string, key):
        self.string = string
        self.key = key

    @staticmethod
    def get_key(x):
        return x.key

    @staticmethod
    def set_key(x, key):
        x.key = key

    def __gt__(self, obj2):
        return self.key > obj2.key

    def __str__(self):
        return self.string


# Testing
if __name__ == '__main__':
    obja = KeyObject('a', 1)
    objb = KeyObject('b', 2)
    print(obja < objb)
    print(obja > objb)

[haughty mountain]

wait what?

that's not what I expected

is string the value?

[fiery cosmos]

if you go https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ and hit 'resources', all the python code is there in a .zip

i'm not sure, i'm just trying to get my janky code going lol

i'm not in a position to be teasing out errors made by the preeminent algorithms authors and what is essentially the best technology Uni in the US

(Berkeley, Harvard, Stanford would like a word, I know)

its also super painful that i can't just repurpose this and use it, but that'd be plagiarizing 🤷‍♂️

oh wow, they have an opencourseware for this, super cool

we should get that pinned

[haughty mountain]

oh, their linear delete packs stuff together?

I guess that's one potentially expensive way of dealing with deletions

[fiery cosmos]

how so

[haughty mountain]

check the while loop in their linear_probing_hash_delete

huh, their thing is supports duplicates

interesting

[haughty mountain]

yeah, their deletion logic is far from trivial

though seems correct after looking at it closely

[fiery cosmos]

i'd hope its correct after all these years

CLRS was originally released a million years ago

so what is wrong with these that are causing this error? i don't understand

hmm let me tack on that index to keys and see whats up

just prints None a bunch of times

ooooh i did a thing

oh nvm

maybe i can tease it out in python tutor

welp

[haughty mountain]

this is the error, no?

self.table[j].keys = key

[fiery cosmos]

also i think there is an infinite loop somewhere

[haughty mountain]

still, this

[fiery cosmos]

this is also erroring:
if self.openslot(j):

[haughty mountain]

wdym also?

it's in the stack trace from before because it's the call that later causes an error

[fiery cosmos]

oh i see

[haughty mountain]

e.g. this is not 3 errors, but 1

the top message is where the error happened, then as you go down you see where it was called from

[fiery cosmos]

https://tenor.com/view/yoda-star-wars-learning-am-i-gif-16531775

[haughty mountain]

that's what a stack trace is

a trace of the function call stack

[fiery cosmos]

i don't understand what the issue is. i'm looking in my table at location j as given by the linear probe, and pointing at an attribute keys that the bucket there has, and saying if it's None, then return True, telling my insert function its safe to insert there. am i missing like a .Bucket or something?

[haughty mountain]

did you fix this yet?

[fiery cosmos]

that's what i'm trying to understand how it's incorrect

[haughty mountain]

what is keys and what is key?

[fiery cosmos]

keys = [None], key is my datum i want to insert

[haughty mountain]

there is a very important difference between the two

[fiery cosmos]

oh i was missing an index for keys?

self.table[j].keys[0] = key?

[haughty mountain]

right, keys is (supposed to be) a list

you're replacing keys with key

[fiery cosmos]

ok now i'm just inserting the same key in every bucket

[haughty mountain]

I have a feeling I know what the issue might be then

and it's a thing we've covered a bunch of times

[fiery cosmos]

🤦‍♂️

[haughty mountain]

how are you defining your list of buckets?

[fiery cosmos]

ok ok im with you, will fix

so you were correct in that i had some statement you previously pointed out was false. however, i have changed it to instead append the proper number of None's, and the issue persists

[haughty mountain]

which issue exactly?

[fiery cosmos]

where i was erroneously declaring a list by multiplying the same pointer a bunch of times

oh

the current issue is that the same input gets written into every bucket over and over

into what appears to be every single bucket.keys

[haughty mountain]

can you provide the relevant code for how you create the list of buckets, and the bucket code itself?

that part is fine, and in this case it's safe to do [None]*bucketsize

[fiery cosmos]

oh

man coding so confusing

[haughty mountain]

because None is immutable

this is more of a confusing python thing

[fiery cosmos]

why does None being immutable make it work here and not elsewhere

[haughty mountain]

[None]*n creates a bunch of references to the same object, but that doesn't matter since you can't change None

same for [123]*n

you can't modify the int

you can only overwrite it

for something like [[]]*n you can modify the list

[fiery cosmos]

but then i'd being entering a triply nested list structure?

[haughty mountain]

wdym?

[fiery cosmos]

unless i am misunderstanding list comprehensions

what you wrote above will not make a list within a list then?

[haughty mountain]

also "can you provide the relevant code for how you create the list of buckets?"

[haughty mountain]

[[]]*n will create a list that contains n references to the same list

ok, so the problem is not that

wait, wtf is your insert code doing?

yes, it's no surprise this puts the key everywhere

[fiery cosmos]

oh duh

hmm so thats clearly a function of the loop here and in my data insertion statement, so.. i need a pass?

[haughty mountain]

pass is not what you want

pass does...nothing

[fiery cosmos]

hmm

[haughty mountain]

like, that's the point of pass

to do nothing

[fiery cosmos]

break

it never prints the full out 🤦‍♂️

ok that seems to be working, some kind of way, though again im seeing known inputs that are not present

nvm that was my IDE

VS code only prints as many lines as can be shown in the terminal window

why am i unable to access keys with mytable.table.keys

guess i am missing indices

ok. so i have confirmed it is storing every datum in data

now i need to get my quadratic probe working

[fiery cosmos]

i wonder how spotify's data is arranged and what their pointer structures look like

[austere sparrow]

I doubt their data is all in RAM 🙂

[azure osprey]

Are dataclasses stateless or stateful?

Ig they are stateful

But their state isn't dependant on anything else

[haughty mountain]

they are bundles of data

[azure osprey]

Sure

[haughty mountain]

stateful and stateless has more to do with api design

[azure osprey]

[haughty mountain]

if there is some internal state that changes as you interact with the class/function

[azure osprey]

That's stateful right?

[haughty mountain]

yes

[azure osprey]

Well know I know the terms

I am really second guessing my use of stateful classes

They were difficult to implement for one

[haughty mountain]

I just feel it's odd to call a bundle of data stateful or not

but for something like a class api the terms make a lot of sense

[azure osprey]

Imo stateful is better when you need to deal with modifications right?

[haughty mountain]

if your methods modify the class internals it is stateful

[azure osprey]

Or want to keep two layers of data in sync?

[haughty mountain]

[azure osprey]

Like keep the binary data and parsed objects in sync

[opal oriole]

If what a function does depends on a previous run, there is some internal state / it is stateful.

[haughty mountain]

like an adapter class?

[azure osprey]

Yea kinda

[haughty mountain]

that keeps the annoying binary internally and exposes a nicer api

[azure osprey]

Yes

FLP is really such a trashcan format i swear to god

Really always a PITA to do something

I wanna learn about what's the procedures for implementing APIs for dealing with binary formats better. Is there anything special or is it like always super low level - parse structs and call it a day?

[opal oriole]

There is not actually stateless code, it's just to try to describe the idea that it does not have hidden surprises due to previous runs / not just what you gave as input this time.

[haughty mountain]

there are pretty nice libraries to parse binary data

[azure osprey]

Yea I use construct to parse the structs

[haughty mountain]

There is not actually stateless code

pure functions are a thing, no?

[opal oriole]

Yes but they use memory still. A program that does not manipulate state just generates heat (not useful, unless you are cold).

[azure osprey]

That's not the worry (although its quite slow). My problems start at the API I created on top of it

[azure osprey]

What about lazily evaluated properties from state passed via class stor?

[opal oriole]

Any data in a computer's memory has some state / is in some state.

No matter which programming method used.

Like x = 1, is some state.

"stateless" refers to what one can expect from the API / the design of the API.

It's essentially the idea of "pure".

No surprises.

[azure osprey]

So a parser that parses everything in a single go is stateless more or less?

[opal oriole]

If it only depends on the input given to be parsed and not data from a previous run or other hidden state.

The state given in the form of the input is considered "temporary" and so not stateful.

[azure osprey]

Then it depends on how the format works I guess

[opal oriole]

However, there is at least one hidden state which is accepted to not count.

That is the code of the program in memory.

Technically that is a state.

(And it can be modified too dynamically during a run)

[azure osprey]

I think that's a different concern altogether

[opal oriole]

Yeah, which is why it does not count.

What "stateless" really means is something else, it's a bad term.

It's an API style.

/ programming style

It's part of the principle of least surprise idea in programming.

[azure osprey]

So when for example there are "pointers" or "ids" referencing to other objects in some data, it needs a state so what's that called?

Stateful?

Or more precisely sort of a state machine?

[opal oriole]

So there are two options generally. You can have some function which takes in some object and modifies it "in place" / destructively, or you can generate a new result based on the previous one.

The first is seen as stateful because it requires keeping around the thing that is modified multiple times.

[azure osprey]

The first one is quite a common pattern in C, outparams

[haughty mountain]

rust likes the destructive option

[opal oriole]

It just sits there in memory, for a longer duration than with the second option.

The first option is faster, but it's error prone.

It's also more effort to code typically.

Because there has to be some pointer / reference wrangling and such.

[azure osprey]

Well sometimes inplace "patches" are the only option, when you can't regenerate or reorder a bunch of items correctly / the complete representation is not known

[opal oriole]

For functions that operate on primitives, such as an int and return primitive, they are typically the second option.

Like ```c
int square(int x) {
return x * x;
}

The second option feels more natural.

No pointers needed or anything.

[opal oriole]

Yes, sometimes in place modification is the only viable option.

But this is where the magic of how functional programming languages work comes in.

They act like they are always doing option 2, but the compiler can turn it into option 1 for you.

[haughty mountain]

destructive semantics can be better performance I think

[azure osprey]

C has these "continuable" string conversion methods, perfect example of stateful methods.

[haughty mountain]

strtok 🤢

[opal oriole]

Yes, C standard lib has internal hidden state.

It's really bad. Don't use the C standard lib.

[haughty mountain]

some parts are fine

[azure osprey]

No I was talking about mbstate in particular

[opal oriole]

Passable at best.

[azure osprey]

C is really really bare bones

And its adding on really niche features, like #embed

[opal oriole]

int main() {
  string date = cstr("10/22/2022");
  string month = string_split(&date, "/");
  string day = string_split(&date, "/");
  string year = string_split(&date, "/");
  print("Month: {string}, Day: {string}, Year: {string}", month, day, year);
  return 0;
}
``` With a proper standard lib for C, coding it in it can be comfy / high level.

(My personal lib)

[azure osprey]

There's even type safe vectors and dicts in C

Macro magic all of it

[opal oriole]

Yeah I have dynamic arrays and hashmaps that are generic.

[azure osprey]

I had used stb_ds once

[opal oriole]

It's kind of crazy how stb exploded in popularity.

[haughty mountain]

C tends to devolve into preprocessor nonsense

because C lacks nice features like generics

(not counting void*)

[opal oriole]

Yup, which is why we let people that know the issues make a couple and everyone just uses that standard lib.

But outside of that, no macros allowed.

[azure osprey]

Arguably the preprocessor and various compiler extensions are more powerful and feature rich than the language itself

[haughty mountain]

Or pick a saner languages where you can avoid the c preprocessor in most cases

[opal oriole]

Yeah.

[azure osprey]

Or implement OOP in C

😁

[opal oriole]

But when you gotta do the C, at least you can make it much more comfy and avoid the pitfall of the using its standard lib.

It's pretty bad that a language's entire standard lib is basically a trap.

[haughty mountain]

there is a part in the cpython source about that...

let me try to find it

[azure osprey]

C++ STL is equally crazy. I just love everything was just implemented so simpler in python

[haughty mountain]

found it

/* Nothing is actually declared to be a PyObject, but every pointer to
 * a Python object can be cast to a PyObject*.  This is inheritance built
 * by hand.  Similarly every pointer to a variable-size Python object can,
 * in addition, be cast to PyVarObject*.
 */
struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
};

[opal oriole]

It has much more usable parts at least.

[azure osprey]

Isn't that downcasting? In C there's no such thing tho pointer is 4/8 bytes flat

[haughty mountain]

I think this would be more like reinterpret_cast in C++

[opal oriole]

It's C style OOP, which basically is just putting the base object at the top of the struct and casting down.

Inheritance is just composition with some language sugar to hide it.

[azure osprey]

With vtables its possible to implement "instance methods" for structs making them closer to classes

Although you need to call it in an unbound fashion everytime

[opal oriole]

vtables make it full OOP style.

Also implemented manually in C.

An example of an API that makes use of option 2, not in place, would be numpy. And it makes numpy very nice to work with.

Option 2 is made even more nice when your language has automatic memory management, because one does not need to manage the newly generated stuff.

(Don't need to manage anything really with option 1, it can just sit there the whole lifespan of the program)

(Some of numpy is in place, but a lot of what one does will spit out new arrays left and right)

(Option 2 can secretly be made to be option 1 under the hood (in some cases) for more speed (common in C and functional languages))

[stray fractal]

seems to be data structure discussion so it's all good

[vocal gorge]

I got more appreciation for C's annoying-as-fuck signatures after reading https://matklad.github.io/2022/10/06/hard-mode-rust.html
I wonder what's a good way to write code that can be used in both "modify this thing I pass you because oh boy is it annoying to allocate a new one" and "return a new one idc" ways

[opal oriole]

What if I told you that C++ is crazy and has language features for this kind of stuff?

That language has everything.

[vocal gorge]

what feature is that?

[opal oriole]

In C++ you can not only pass by value or by reference, but also move.

Rust does move everything.

By default.

"passing ownership"

[haughty mountain]

C++ move is mostly a lie

[opal oriole]

Rust is based on C++ and they really liked move semantics in C++.

[vocal gorge]

Don't think I get how this helps.

[haughty mountain]

std::move is only a cast in C++

[opal oriole]

Except, you know, C++ implements everything in a way that is really ugly, so new language and Rust is born (also from smart pointers).

[vocal gorge]

I'm basically talking about

fn f(inp: &[A]) -> Vec<B>
\\ versus
fn f(inp: &[A], out: &mut [B])

where the former is nice and convenient but only the latter works in not-that-simple-to-make-an-allocation environments, and it'd be nice to allow both somehow

[opal oriole]

^

Optional output parameter.

In C++ check if nullptr.

Or function overloading.

[vocal gorge]

huh, and output is also a nullable pointer(vec, whatever)? seems very ugly, it doesn't capture the invariant that "output is null iff out argument isn't"

[haughty mountain]

rust doesn't have function overloading, right?

[vocal gorge]

nope

[opal oriole]

In C++ you would have a function overload.

[opal oriole]

Uff.

In C optional by null.

[vocal gorge]

Hmm, and would you write the overloads manually, in C++?

[opal oriole]

The version that does not take an out parameter would just call the one that does and also make a new result to return.

[vocal gorge]

since then you can do it in Rust too, just write two functions (and for simple cases you might even be able to make a macro do it for you)

[haughty mountain]

You can just define several functions with the same name in C++

[vocal gorge]

hmm, fair enough

[haughty mountain]

as long as their function signature is different

[opal oriole]

From the user's pov it's foo(a) or foo(a, out).

[vocal gorge]

yeah, I know, but it's functionally not very dissimilar from different functions

[haughty mountain]

it is for generics

rust's response to this is traits (for better or worse)

(for generics)

[opal oriole]

Python uses a bunch of default values to get around not having function overloading.

[onyx root]

it's funny to word it that way. it's a different choice of how to give programmers flexibility

[opal oriole]

Yeah. This POV comes the fact that with function overloading I can have two different functions that do two very different things and they are separate. With default values my one function now needs to play role of both of those functions that would be separate (e.g. via if statement to check the default and then either do what would be function A or function B).

In a compiled language with heavy optimization they amount to the same end result, but in code it appears as one larger function (that may call what would be those two separate ones) vs two separate ones.

[austere sparrow]

if the functions do "very different things" why are they called the same

[onyx root]

compiled isn't really the issue here, it's about the semantics of the language. Python can only have one thing with a name.

[opal oriole]

Because they are doing the same idea, but the actual operations happening may be different. For optimization purposes for example.

[austere sparrow]

yeah Elixir has some kind of overloading

I mean, you can emulate overloading with a decorator like functools.singledispatch

[opal oriole]

Yeah, I thought I would just mention that that is not an issue, it would compile down to the same thing because the compiler knows the default values at compile time.

[austere sparrow]

and then some "compiled" languages like Rust or Haskell don't have overloading

[opal oriole]

I do often see code in libraries such as scipy or numpy that are basically just checking the keywords / default values and branching into more functions for those specific cases, effectively doing what function overloading gives, but with more code.

Not exactly a huge issue.

[haughty mountain]

other than maybe some overhead

I guess not that much in python

but in compiled langs

[opal oriole]

Yeah, but as mentioned in C++ this would compile out.

It sees the default values at comp time.

And the branches would be removed.

if (some_default_known_at_comp_time) vanishes.

So in theory, function overloading and default value with branch approaches can be compiled to the exact same end result. So speed is not the issue.

[haughty mountain]

if things are known at compile time yes

[opal oriole]

Yeah, IDK if that holds in Python or not.

But not that the branches matter for Python anyhow.

[haughty mountain]

what is a branch or a cache miss to python? not much 😛

[opal oriole]

Some of the other main uses of function overloading Python avoids by not being statically typed. For example, in C++ one would use function overloading to have a sqrt that works on integers, floats, doubles, etc. In Python you just pass in whatever.

(Although C++ can also use templates, because ofc C++ has N ways of doing anything)

[delicate ore]

is there any way to encode 3 sets together and pass as one parameter and then inside function unpack the 3 sets?

[opal oriole]

A tuple with the 3 sets in it.

[delicate ore]

but it's pass by ref

is there any high efficiency way to pass by value?

I mean, I think pickle is not that efficient, right?

I am not so familiar with pickle, if you can give me any idea

[opal oriole]

I don't know what you are doing. The original question asked has nothing to do with pickle.

"encode 3 sets together" what is meant by this?

What is the problem you are trying to solve?

[delicate ore]

i want to have a common interface,

def func(A, B, C)

But for C, it might be a tuple of sets
I have to t=tuple(set1, set2, ...)
and pass t to C

But this is pass by reference, if I want to pass by value, I have to copy t.

I wander which one is more efficient, pickle all sets to an variable and then unpickle, or simply deepcopy

[opal oriole]

(set1.copy(), set2.copy(), set3.copy())

[delicate ore]

alright, I guess this is the common way, I will follow the mainstream

[haughty mountain]

Why would you ever pickle if you're not storing things in a file or similar?

[azure osprey]

Is there any library that provides a cache like lru_cache, but better?

Which lets me bind callbacks for its invalidation?

I am unsure I should be using it that way. Its better to have data slower than to get a previous copy of invalid data, isn't it?

[haughty mountain]

lru_cache kinda assumes that data wouldn't change

you could easily write your own invalidation aware cache though

something like

def invalidation_aware_cache(f):
  cache = {}
  def wrapper(*args, **kwargs):
    key = (*args, *kwargs.items())  # hacky
    if key not in cache or not is_valid(ret := cache[key]):
      ret = cache[key] = f(*args, **kwargs)
    return ret
  return wrapper

functools.wraps goodness left as an exercise to the reader

[azure osprey]

I am reversing a struct containing a 4 byte integer, it contains the values used by a knob in a GUI. The first row is the values when the knob is at a complete 0. However even if I move it a tiny bit the 3rd byte always turns to 63. So I am wondering what type of integer encoding this really is. If I turn the knob back to a complete 0% it changes back to (0, 0, 0, 0, ...)

maybe 63 is just a flag, but why is that even needed? the first 2 bytes can indicate the knob value

[haughty mountain]

what are the actual values on the knob?

[azure osprey]

0 - 100% not useful yes 😅

[haughty mountain]

I mean the values for each of those

[azure osprey]

(0, 240) is max value

[haughty mountain]

interesting max value

[azure osprey]

1% is approx 33920
10% is approx 47512

100% is 61440

maybe it is a float32?

[haughty mountain]

let me think in my head if that makes any sense...

[azure osprey]

i think its a logarithmic or exponential knob

not a linear one def

[haughty mountain]

there should be [1, 8, 23] bits for sign, exponent and mantissa

not entirely sure if that makes any sense

probably not considering the 4th byte is unused

[azure osprey]

i think it is because I have seen these values occuring a lot

and I though yea, it might be an int32 all the time i.e. (0, 240, 63, 0)

but i was maybe wrong

the real value could just be 2 byte

[haughty mountain]

yeah, 2 byte value would make more sense

though the values for 1% 10% and 100% are quite weird