Well, you put me at ease, I feared I missed an hashtricks in my toolset.
You can have O(1) lookup with infinite precision as long as you have a cumsum table and the size of the bins is smaller than the smallest probability, btw (the hasttable gives you two candidates, and you chose between the two using the cumsum table).
But you have to regenerate part of the table every time you adjust probabilities, so it's not good unless lookups dominate reconfiguring the probabilities
Actually, if probabilities reconfigurations dominate the lookups, the tree is also unefficient.
I mean, it works like thiis: assuming you have 64 items, 000000 to 111111 in binary. The tree trick store partial sums of pprobabilites. For example, you can have an internal node [01] that store the sum of all 01???? items probabilities.
When you change the probability of 010110, you have to update [], [0], [01], [010], [0101] and [01011] nodes sums. Which is log. But if you're updating a lot of probabilities at the same time, you may need to recompute a large part of the nodes, and the O(log) isn't interesting anymore, and dichotomy can suffice.
The main issue with large hash tables is that even the construction isn't O but O(p) where p is the size of the table, and there's a large risk that p>>n.
Well, you put me at ease, I feared I missed an hashtricks in my toolset.
You can have O(1) lookup with infinite precision as long as you have a cumsum table and the size of the bins is smaller than the smallest probability, btw (the hasttable gives you two candidates, and you chose between the two using the cumsum table).
Actually, if probabilities reconfigurations dominate the lookups, the tree is also unefficient.
I mean, it works like thiis: assuming you have 64 items, 000000 to 111111 in binary. The tree trick store partial sums of pprobabilites. For example, you can have an internal node [01] that store the sum of all 01???? items probabilities.
When you change the probability of 010110, you have to update [], [0], [01], [010], [0101] and [01011] nodes sums. Which is log. But if you're updating a lot of probabilities at the same time, you may need to recompute a large part of the nodes, and the O(log) isn't interesting anymore, and dichotomy can suffice.
The main issue with large hash tables is that even the construction isn't O but O(p) where p is the size of the table, and there's a large risk that p>>n.
(That's actually something I expect to hear from students from time to time... I know you're joking, but some are serious, they don't see that the size p of the table must be at least larger than n, or there's items you'll never draw)
(That's actually something I expect to hear from students from time to time... I know you're joking, but some are serious, they don't see that the size p of the table must be at least larger than n, or there's items you'll never draw)
Funny story, I interviewed at Blizzard once, I actually got the job (didn't accept though), and I did well on the whole interview but the recruiting manager said that what sold them and clenched the deal is when they asked me to find the space complexity of some algorithm and I instantly said O(1). They were kind of bewildered but I explained that you just need an upper bound on the memory usage, so you can just let P equal the largest amount of memory on any computer ever created, and there's O(1). Obviously the delivery is everything, you have to make it clear that you actually know it's a joke and follow up with a real answer
Funny... I don't know if I would have the guts to try a joke as my first answer in an interview for a job I'm interested in, though.
Complexity is a funny thing, anyway... I remember reading a time complexity that required... a data size larger than the amount of data any supercomputer could hold to actually be better than a worse complexity, because of the prefactor...
Kinda like the sieve of Atkin that normally best the crible of Eratosthene, except that most of the time, when you try to implement it, you get something slower or barely faster.
Speaking of complexity, even with some knowledge on quantum computing, I still don't understand why spaghetti sorting is O(1) either
How often do the probabilities change? And are some probabilities dependent on others? Eg suppose the top of your tree has left and right nodes with 50% each, and each of those has two more children with 50% each. Does this mean there are 4 nodes with 25% selection each? And if you changed the top 2 nodes to 60/40 then the weights would change to 30/30/20/20?
I can still think of a solution with O(1) lookups but it will not work depending on if you need the scenario described above unless they don't change frequently
that's more or less correct, the actual scheme is that each node has a range and knows the cumulative range of nodes beneath it, this is maintained in update and has the property that the root node knows the entire range, thus the probability of any node n being selected is n.range / totalrange. it's not calculated that way but that's what it amounts to and what it means is that by updating the range in one node and propagating that change up the tree, other values have their probability influenced and the sum of all probabilities is always 1.
IE I have 4 values again each has the range value of 1, thus each value has 25% chance of being selected. now if I raise one of those 4 values to a range of 2 it has 2/5 or 40% chance of being selected and the others have 1/5 or 20% chance of being selected
Like I said before it doesn't matter that I generate an exact probability for all the elements but rather that they are able to smoothly be increased and decreased.
Usually, I would say the tree approach is the most efficient one (as far as I know).
But if you change regularly a large number of probabilities at the same time, the O(log) update for each single probability update will not be interesting compared to a O reconstruction... and in the case you lose the advantage of a O(log) update, a simple dichotomic research over a cumulative table with also be O construction and O(log) query.
And yes, as Cpp_Is_King said, hastables can speed up the queries (although I'd be curious to know the exact idea behind the O(1) assuming probabilities are real values, unless you use a REALLY large table, or it's a O(p) where p is the length of the binary representation)
The current design is for improved query time so it basically works like a binary max heap, on updating the tree I reorder the heap if necessary and recalculate affected range sums.
I expect very small update batches relative to the number of values, maybe 32 or 64 at a time out of hundreds of thousands or millions, potentially more.
The current design is for improved query time so it basically works like a binary max heap, on updating the tree I reorder the heap if necessary and recalculate affected range sums.
I fail to see why you should ever change the shape of the tree or move nodes. Or "reorder the heap" if I understand what you mean by this.
I suspect that you have the best complexity, but maybe not the best prefactor or the simplest solution...
Quick'n dirty in Python, so that we can see whether we're talking about the same idea...
Assuming you have a table of values, such as [ 1, 2, 3, 4, 5, 6 ], and a table of "probabilities", [ 0.5, 0.1, 0.7, 0.2, 0.4, 0.3 ] (they don't need to be normalized)
Building a table that build the binary tree of probabilities and their sums (by pairs), O
(the children of a node at index k are at index 2k+1 and index 2k+2, each node has a value which is the sum of its two children)
Code:
def build(probs) :
h = 1 + ceil( log2( len(probs) ) )
tree = zeros(2**h-1, dtype=float)
tree[2**(h-1)-1:2**(h-1)-1+len(probs)] = probs
for i in reversed(range(2**(h-1)-1)) :
tree[i] = tree[2*i+1] + tree[2*i+2]
return tree
Getting a random value, based on (non-normalized) probabilities, O(log):
Code:
def get(tree, values) :
r = random()*tree[0]
k = 0
while k < len(tree)//2 :
k = 2*k+1
if r > tree[k] :
r -= tree[k]
k += 1
return values[k-len(tree)//2]
Updating a probability, by updating the values in the tree, O(log):
(update a leaf, and the nodes above)
Code:
def update(tree, n, p) :
k = n + len(tree)//2
tree[k] = p
while k>0 :
k = (k-1)//2
tree[k] = tree[2*k+1] + tree[2*k+2]
Fits your complexity criteria, seems simple enough, and I think there's not much better (though you can reduce the number of nodes in the right part of the tree, if the number of values isn't close to 2^p)
Yes, returning from the leaves only makes the tree simpler to maintain and create, only requiring the cumulative probability. The point of the max heap setup is to make querying faster, particularly for when certain selections have very high probability.
ie something might have a 50% overall chance of being selected, then 50% of the time the query returns in 1 node.
From a complexity standpoint though a batch of updates in your simpler tree can be achieved in no more than O by simply seeding all the appropriate leaf nodes first then calling the update at each leaf with the additional condition that execution terminates if
tree[k] is already equal to tree[2*k+1] + tree[2*k+2].
Yes, returning from the leaves only makes the tree simpler to maintain and create, only requiring the cumulative probability. The point of the max heap setup is to make querying faster, particularly for when certain selections have very high probability.
ie something might have a 50% overall chance of being selected, then 50% of the time the query returns in 1 node.
Yes... but that depends on the way the probabilities are distributed.
In fact, you can have Query in O(1) (for example with probabilities 1/2, 1/4, 1/8, 1/16...). For the probability update, it would be interesting to check.
I suggested you the simpler solution because the heap solution is still O(log) in the worst case. So unless you know more about your probabilities that you suggested...
Also, yes, O(log) is worse than O(1), but even with 1 million values, log2 is only 20, so a O(1) with a large prefactor is often worse than a really simple O(log) algorithm.
From a complexity standpoint though a batch of updates in your simpler tree can be achieved in no more than O by simply seeding all the appropriate leaf nodes first then calling the update at each leaf with the additional condition that execution terminates if
tree[k] is already equal to tree[2*k+1] + tree[2*k+2].
Hey, does anyone know a good, step-by-step procedure for solving recurrence relations with repeated substitution. I feel like I always mess up at the last stage - when the actual substitution happens.
Example, could someone explain how to solve this recurrence relation using repeated substituion?
Hey, does anyone know a good, step-by-step procedure for solving recurrence relations with repeated substitution. I feel like I always mess up at the last stage - when the actual substitution happens.
Example, could someone explain how to solve this recurrence relation using repeated substituion?
I guess I need to see the correct problem. Because as written, if T = 4T(n/4) + n when n > 1, then T(2) = 4T(0.5) + n, and T(0.5) doesn't make any sense.
If we assume that it's powers of 4 though, then I think it helps to actually express n that way. If n is a power of 4, then n = 4^k. n = 1 implies k = 0. So now we're looking for a formula for S(k), for 0 <= k <= infinity, where S(k) = T(4^k)
S(k) = 1 when k = 0
S(k) = 4S(k-1) + 4^k when k > 0
Hey, does anyone know a good, step-by-step procedure for solving recurrence relations with repeated substitution. I feel like I always mess up at the last stage - when the actual substitution happens.
Example, could someone explain how to solve this recurrence relation using repeated substituion?
Been a while since I've been in school and I've had support/systems admin-ish jobs since then. I fucking hate them. Would like to get into software dev or something similar if possible but my programming skills are pretty terrible at the moment. Should I learn/"brush up" on Java first? I'm kind of interested in everything at the moment - I wanna make shit for fun, maybe an app, maybe a game in my spare time, job, etc. Is Java my best bet?
Interestingly, once you have the closed form solution you can use it to find the answer for values that are not powers of 4, even though the recurrence is only defined for powers of 4. For example, earlier I said T(2) doesn't make any sense, but once you have the closed form just plug in 2.
T(2) = (log_4(2) + 1) * 2 = (0.5 + 1) * 2 = 3
Then checking to see if it satisfies the recurrence, calculate T(0.5) and verify.
You can actually do this with most recurrence relations. For example, factorial is only defined for integers but its closed form, the gamma function, is defined for everything. So you can compute the "factorial" of Pi, for example.
If you want to have your mind blown, see if you can figure out the recurrence for this closed form solution:
Let p = the golden ratio
T = [p^n - (-p)^(-n)] / Sqrt[5]
Cpp_is_king posts are nothing short of great, and Jokab has the hammer to solve such problems... Just some random thoughts...
Since the question obviously comes from a CS course, the whole equation is obviously related to a recursive function, and an attempt to compute O(?) complexity from it. A divide and conquer approach where you cut your data into four parts. If it's not an actual complexity estimation, it's a training to prepare this...
So I'm pretty sure the relation behind the curtain is actually
T = n + T(floor(floor(n/2)/2)) + T(floor(ceil(n/2)/2)) + T(ceil(floor(n/2)/2)) + T(ceil(ceil(n/2)/2))
or, which is the same :
T = n + (n%4) T(n//4) + (4-n%4) T(n//4+1)
except that you need T(1), T(2) and T(3) (or T(0) and T(1)) so that it's fully defined...
It's similar to the one in Quicksort for example where the number or comparison is
In the example, I think T(10) is probably 10 + T(2)+T(2)+T(3)+T(3)
Not that it's important, because since T is increasing, computing T(4^k) will be sufficient to have a O(???) complexity estimation.
The 'master theorem' is indeed really useful for this... when you can find a place where you have the details of the results you haven't memorized faster than actually solving the issue without the theorem. I usually fail in this, I have a cheatsheet somewhere but my desk is a mess, and I could solve those while sleeping now
The actual maths behind are interesting, but in those simple cases, I found that a visual image of what you're trying to count can give you the result without writing anything...
T(16) is 16 + 4 times T(4).
T(4) is 4 + 4 times T(1)...
There's obviously 16 blocks per line, and there's log4(16)+1 lines
Thus T is n times (log4+1)
Another virtually useless comment... From a computer point of view, using closed form to extrapolate non-4^k values usually gives slightly lower results than the number of operations in algorithm, because algorithms deal with integers (10 = 2+2+3+3 and not 2.5+2.5+2.5+2.5, so the divide-and-conquer is slightly less efficient because of convexity).
I had some time to waste, so I plotted T for different possible terminations T(2) and T(3), in color, and the closed form, in black dashed. They can't part much, since they match for n=4^k, but there is sometimes a ~30% difference.
You can actually find a T that is e.g. affine by pieces from pretty much any T(2) and T(3), but it's not always easy, or useful... That won't change the fact that it's O(n log).
If you want to have your mind blown, see if you can figure out the recurrence for this closed form solution:
Let p = the golden ratio
T = [p^n - (-p)^(-n)] / Sqrt[5]
To be honest, I knew that there was a generalization of this, but I couldn't have remembered it without searching or finding it again by calculus... I sure didn't remember the result.
To be honest, I knew that there was a generalization of this, but I couldn't have remembered it without searching or finding it again by calculus... I sure didn't remember the result.
I memorized this one because it is such a common question during job interviews (the recurrence obviously, not this formula), and they always expect you to write a recursive function to solve it and then analyze the complexity and talk about how to optimize it with dynamic programming or whatever. So now, if I ever get asked this question, I just write this formula up on the board and say it's O(1) and done.
I memorized this one because it is such a common question during job interviews (the recurrence obviously, not this formula), and they always expect you to write a recursive function to solve it and then analyze the complexity and talk about how to optimize it with dynamic programming or whatever.
I find it quite "stupid", actually, if they really want to discuss recursivity and dynamic programming...
Actually, recursivity and DP is among the things I have to teach, and they took time to put a "please DO NOT stop at the Fibonacci recursion since it's totally useless and meaningless" in the official texts.
I never took job interviews, but my first reaction would indeed be "O(1), do you want me to find the formula?".
Out of curiosity, I took a piece of paper to check I could find the formula from scratch, from the other end.
Interestingly enough, I found a different one:
fib = (p^n + (1-p)^n) / sqrt(5)
but after checking, it's actually the very same one.
Though if I had to go further, it gets interesting when you go over 16 digits... it's easier to create longints than longfloats, so you need to compute the above formula only with integers. You can create an integer approximation of the square root, so it's doable. Getting large values of fibonacci numbers efficiently (i.e. not with DP and recursion) seems an interesting problem (and no more O(1), although probably far less than O )
Yea, it's pretty common. I haven't gotten it recently because I guess I'm more senior now, but I've gotten at least 5-6 times during my career (including during that Blizzard interview on a phone screen), and I know tons of people who ask it. It's not a bad weed-out question, it's good to start with stuff that is supposed to be trivial and obvious, because a lot of people can't even get those right, and you definitely don't want to go further with them if that's the case.
I have (simplifying things a bit) a QLayoutHBox, with two widgets.
The left widget, let's call it A, is always the same.
The right widget is a stack of three widgets, B, C and D.
When I display A and B, I want a 50/50 split.
<------A------><------B------>
When I display A and C, I want more place for C, with a minimal width for A, and C filling the rest of the window (let's say 30% for A, 70% for C, no less than 250 pixels for A)
<---A---><---------C--------->
D is basically an empty widget, so I'd like A to take the width it wants, and D to resize accordingly, to 0 if needed (let's say 100% for A if width<600, 600 for A and the rest for D of width>600)
<---------A--------->
Where/how do you set minimum width and relative width of widgets? I guess I'll find it somewhere in the properties, but with so much inheritance, it's well hidden, so any help is welcome ^_^
Edit: I really don't understand... Since the widget A is a custom one, I can set freely the size, sizeHint, etc.
A (inherited from QWidget) and B (QWidget that contains a QStackedWidget) have
- the same size()
- the same sizeHint()
- the same sizeIncrement()
- the same sizePolicy()
and B is still larger than A when the window is narrow.
Well, at least, he won't type a long problem for nothing.
(About he Qt question, I've done the things differently, so I don't need an answer, but I still wonder... I have a strange nasty bug, too, a widget whose property .isVisible returns the wrong boolean )
I have (simplifying things a bit) a QLayoutHBox, with two widgets.
The left widget, let's call it A, is always the same.
The right widget is a stack of three widgets, B, C and D.
When I display A and B, I want a 50/50 split.
<------A------><------B------>
When I display A and C, I want more place for C, with a minimal width for A, and C filling the rest of the window (let's say 30% for A, 70% for C, no less than 250 pixels for A)
<---A---><---------C--------->
D is basically an empty widget, so I'd like A to take the width it wants, and D to resize accordingly, to 0 if needed (let's say 100% for A if width<600, 600 for A and the rest for D of width>600)
<---------A--------->
Where/how do you set minimum width and relative width of widgets? I guess I'll find it somewhere in the properties, but with so much inheritance, it's well hidden, so any help is welcome ^_^
I could be wrong, but after playing around with this for a bit, my conclusion is that the stack widget isn't designed to change size based on which page is currently visible. It just tries to reserve enough room any page to be displayed and gives the same amount to all pages. You may be able to hack it by changing the stretch factor along with changing the page, and hiding it rather than displaying an empty page. You may want a horizontal spacer for that, as well. Not sure.
Are you sure it returns the wrong value? Just because QWidget::isVisible returns true doesn't mean the widget should be shown. It will also be hidden if it's parent is hidden, or be effectively hidden if its size is 0.
I could be wrong, but after playing around with this for a bit, my conclusion is that the stack widget isn't designed to change size based on which page is currently visible. It just tries to reserve enough room any page to be displayed and gives the same amount to all pages.
Indeed, the size of the stack widget is computed based on the larger widget in it. But when you have an HBox that contains a stack and another widget, the horizontal size should be shared between both.
What I don't understand is that I can't set the size, sizeHint and policy of the OTHER widget so that it's 50/50. I'm far from a Qt specialist (I admit I prefer FLTK in C++) and I obvioulsy miss something in the way Qt compute size of widgets, and it's annoying ^_^
You may be able to hack it by changing the stretch factor along with changing the page, and hiding it rather than displaying an empty page. You may want a horizontal spacer for that, as well. Not sure.
Are you sure it returns the wrong value? Just because QWidget::isVisible returns true doesn't mean the widget should be shown. It will also be hidden if it's parent is hidden, or be effectively hidden if its size is 0.
No, the bug is really strange. I do something based on visibility. When I use .hide(), the value change since isVisible is now false.
When I use .show() again, isVisible() returns true in the function that called .show() but a later function that update other widgets has .isVisible() returnung false.
If I use prints, I have in the terminal:
isVisible is true
hide called
isVisible is false <- in the function that called hide
isVisible is false <- outside
show called
isVisible is true <- in the function that called hide
isVisible is false <- outside, and that's the strange thing?
I guess it may be a racing condition between threads, but I'm surprised the printouts are not in order.
Dear developers if you are going to depend on MS build or other VS tools for the love of God make sure that people with up-to-date installs can run your stuff, especially before the new version launches. I keep running into things that require VS2015 and fail with VS2017. These are things like npm packages (if you use non-javascript in your npm module there is a special place in hell for you, ditto for gems and non-ruby).
Dear developers if you are going to depend on MS build or other VS tools for the love of God make sure that people with up-to-date installs can run your stuff, especially before the new version launches. I keep running into things that require VS2015 and fail on VS2017.
I'm far from up-to-date with Emscripten, but isn't this unrelated to VS, and mostly because Emscripten developpers hasn't updated their code so that it supports 2017 LLVM?
Must be really annoying, but there's not many things developpers can do beside creating their own Emscripten (or contribute to it)?
Dear developers if you are going to depend on MS build or other VS tools for the love of God make sure that people with up-to-date installs can run your stuff, especially before the new version launches. I keep running into things that require VS2015 and fail with VS2017. These are things like npm packages (if you use non-javascript in your npm module there is a special place in hell for you, ditto for gems and non-ruby).
Anyone got a good resource(s) on data structures & algorithms? In Java, preferably, but I don't really care language wise. I'd just like something that explains them well.
Text that my school uses for it is riddled with errors, least according to reviews, so I'm skeptical going ahead with it considering I'm not touching that course until September.
Anyone got a good resource(s) on data structures & algorithms? In Java, preferably, but I don't really care language wise. I'd just like something that explains them well.
Text that my school uses for it is riddled with errors, least according to reviews, so I'm skeptical going ahead with it considering I'm not touching that course until September.
What's the rush? Your professor's probably going to teach you in a particular way and expect you to do things as they do. Could end up screwing yourself there.
Spend your time learning stuff your school won't be teaching you.
What's the rush? Your professor's probably going to teach you in a particular way and expect you to do things as they do. Could end up screwing yourself there.
Spend your time learning stuff your school won't be teaching you.
I'm sure you feel well intentioned and everything, but I don't see why any of that matters.
There's no rush. I already know how both profs teach it since they've left their resources up (from lectures to sample midterms/finals) for this past school year, so I don't think I can screw myself on this. I'm just curious, and I want to read up on it some. Also, nah. Profs don't tend to force us to do things a specific way at my uni - long as the solution is right, it's whatever. 👀
Kill me for it. ¯_(ツ_/¯
Don't assume I'm not learning other things or doing other things. I have 4.5 out of 5 months of break left ahead of me. I may as well fill what time isn't already dedicated to projects with some things that might give me even a slight leg up.
Indeed, the size of the stack widget is computed based on the larger widget in it. But when you have an HBox that contains a stack and another widget, the horizontal size should be shared between both.
What I don't understand is that I can't set the size, sizeHint and policy of the OTHER widget so that it's 50/50. I'm far from a Qt specialist (I admit I prefer FLTK in C++) and I obvioulsy miss something in the way Qt compute size of widgets, and it's annoying ^_^
If you want some particular result, it definitely can be annoying fighting with the Qt layout policies. The stuff you want to do is all possible, but the system is definitely not intuitive. The names of the size policies got me turned around every time I read them. For example, QSizePolicy::Maximum means that the maximum size of the widget is the sizeHint, but naively you'd think it would mean the widget would try to maximize its size. It's basically the exact opposite. Of course, familiarity makes things easier. You eventually get a feel for how Qt does its stuff.
If both widgets have the same growth policy (e.g. expanding), and there's room for both, I believe it will be split according to the stretch factor, which is 1:1 by default. So, achieving 50/50 should be the easy one. Of course, if there's not enough room and either widget has a layout with children that can't shrink, then that's not what happens. Instead, it gives space to the one that needs space for its children.
If both widgets have the same growth policy (e.g. expanding), and there's room for both, I believe it will be split according to the stretch factor, which is 1:1 by default. So, achieving 50/50 should be the easy one.
That's what I thought, but since I wasn't getting the expected result with, as far as I could say, this exact conditions, I was puzzled.
It was probably a bug somewhere. I've managed to do things differently (I ditched QStackedLayout and use hide/show), but I'll try again later, I want to understand (I've put a tag on the bugged version ). I appreciate your help.
Some of the problems probably come from the strange behavior of QWebView (which seems to have a fixed size and behave curiously)
Today, it's annoying... Since yesterday, I have an ache in my left forefinger, so I can't type properly. I avoid using it, but it feels ackward. I hope it won't last too long :/
Anyone experiences sometimes the same kind of thing? Any useful suggestion? Pretty sure it happened to me in the past, but I don't remember the details.
Not a book, but once again I'm going to recommend Codefights. Open an account, set your preferred language to Python, and start going though the arcade. They'll give you progressively harder interview-style problems to solve. No time limit, and you'll probably have to hit StackOverFlow over and over to figure out the right way to do things.
Python or Python 3k? And what exactly are you meaning by "advanced"?
Some suggestions:
Python Essential Reference, by Beazley: really good and complete side-book, even if it's old. They decided to cover the intersection of Python and Python3k, even if Python3k wasn't popular at this time. A couple of mistakes, but nothing serious. I'd welcome a 5th edition focused on 3k.
Fluent Python, by Ramahlo: a recent one, to get better at Python 3k. Really great book for coding styling and tips, plently of interesting things even for advanced python programmers, I'd say.
Dive into Python: I've already said it, but after staying away from Python for a lot of years because I disliked my first experiences on the language in the late 90s/early 2000s (bad books), this is the book that interested me in the language, and now, Python often my first pick for quick'n dirty things or small-scale projects (and sometimes when I just need portability). I'd say it's written by a programmer for programmers, if it means anything ^_^ Not a complete CS beginner book, but you can read this book without any knowledge on Python and go quite far with it.
So again I'm making a Discord bot that enables users to type /clip to make the bot upload an audio clip of the last 40 or so seconds of voice that was sent to a voice channel. This is now working fine for one user, and I can upload clips automatically or stream it back to Discord.
The problem happens with several users. The recording code is this (using the library Discord.js):
Code:
record(userId) {
this.connection.on('speaking', (user, speaking) => {
if (speaking) {
var stream = this.receiver.createPCMStream(user.id);
this.streams.push(stream);
}
});
}
So when the voice connection receives a speaking event, I create a PCM stream for the user that spoke and store it in a list. When the user stops speaking, the stream closes and is then stored in the streams list. The framework (as well as the official Discord API I believe) I use can only create a stream for one user simultaneously. Furthermore, the silence inbetween the user speaking is not captured. When the clip command is issued, I collect the streams in order and do something with the audio pretty much.
However when I have many users talking at the same time, their respective streams will be put in the streams list and output in sequence, not in the interleaved way they are transmitted. Not sure how I'm going to solve this. I had a few ideas but they all seem terrible tbh lol. The fact that silence is not captured makes things even harder since I have to align the streams in some way too.
Yeah I'm using ffmpeg. That's not the issue though. Perhaps I explained it poorly.
So what happens is that when a user starts speaking, a stream is created that captures the audio of that user. I put this stream inside a list. When another user starts speaking, another stream is created, that's put as the second element in the list. So we get:
Code:
list: [user1] [user2]
Then the first user stops speaking, and the user1 stream is closed. The whole sequence that user1 spoke is still in the first element of the list though. When I later collect the voice audio sequentially from the order that it appears in the list, it will appear as though user1 spoke, finished, and then user2 started speaking. This is not what happened -- user2 started speaking while user1 was speaking.
And as I said, to make things more complicated the silence between the streams is not captured, so I can't simply (however simple that is I dunno) somehow mix it in (again, however that is done ) at the correct point depending on when the stream started.
Not sure what you're having trouble with. If the first voice starts at t=0 and last 10 seconds, and the second voice starts at t=6 and lasts 5 seconds, just start mixing the second stream at t=6?
Do you need to tell it up front how long the resulting stream is? If so just compute max(end) for each item in the list, you can then create a silent stream of the corresponding duration, then go through mixing each item in the list in
Studying pretty hard for my exam; I actually made myself sick, lol. This semester was particularly stressful. One more exam, though. A lot of things I am finding easier once I stopped relying on textbook explanations of things and went to YouTube for visualizations. I hope I can do well.
